1/*****************************************************************************
2
3Copyright (c) 1994, 2011, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify
6it under the terms of the GNU General Public License, version 2.0,
7as published by the Free Software Foundation.
8
9This program is also distributed with certain software (including
10but not limited to OpenSSL) that is licensed under separate terms,
11as designated in a particular file or component or in included license
12documentation.  The authors of MySQL hereby grant you an additional
13permission to link the program and your derivative works with the
14separately licensed software that they have included with MySQL.
15
16This program is distributed in the hope that it will be useful,
17but WITHOUT ANY WARRANTY; without even the implied warranty of
18MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19GNU General Public License, version 2.0, for more details.
20
21You should have received a copy of the GNU General Public License along with
22this program; if not, write to the Free Software Foundation, Inc.,
2351 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24
25*****************************************************************************/
26
27/********************************************************************//**
28@file include/ha0ha.ic
29The hash table with external chains
30
31Created 8/18/1994 Heikki Tuuri
32*************************************************************************/
33
34#include "ut0rnd.h"
35#include "mem0mem.h"
36#include "btr0types.h"
37
38/***********************************************************//**
39Deletes a hash node. */
40UNIV_INTERN
41void
42ha_delete_hash_node(
43/*================*/
44	hash_table_t*	table,		/*!< in: hash table */
45	ha_node_t*	del_node);	/*!< in: node to be deleted */
46
47/******************************************************************//**
48Gets a hash node data.
49@return	pointer to the data */
50UNIV_INLINE
51const rec_t*
52ha_node_get_data(
53/*=============*/
54	const ha_node_t*	node)	/*!< in: hash chain node */
55{
56	return(node->data);
57}
58
59/******************************************************************//**
60Sets hash node data. */
61UNIV_INLINE
62void
63ha_node_set_data_func(
64/*==================*/
65	ha_node_t*	node,	/*!< in: hash chain node */
66#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
67	buf_block_t*	block,	/*!< in: buffer block containing the data */
68#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
69	const rec_t*	data)	/*!< in: pointer to the data */
70{
71#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
72	node->block = block;
73#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
74	node->data = data;
75}
76
77#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
78/** Sets hash node data.
79@param n	in: hash chain node
80@param b	in: buffer block containing the data
81@param d	in: pointer to the data */
82# define ha_node_set_data(n,b,d) ha_node_set_data_func(n,b,d)
83#else /* UNIV_AHI_DEBUG || UNIV_DEBUG */
84/** Sets hash node data.
85@param n	in: hash chain node
86@param b	in: buffer block containing the data
87@param d	in: pointer to the data */
88# define ha_node_set_data(n,b,d) ha_node_set_data_func(n,d)
89#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
90
91/******************************************************************//**
92Gets the next node in a hash chain.
93@return	next node, NULL if none */
94UNIV_INLINE
95ha_node_t*
96ha_chain_get_next(
97/*==============*/
98	ha_node_t*	node)	/*!< in: hash chain node */
99{
100	return(node->next);
101}
102
103/******************************************************************//**
104Gets the first node in a hash chain.
105@return	first node, NULL if none */
106UNIV_INLINE
107ha_node_t*
108ha_chain_get_first(
109/*===============*/
110	hash_table_t*	table,	/*!< in: hash table */
111	ulint		fold)	/*!< in: fold value determining the chain */
112{
113	return((ha_node_t*)
114	       hash_get_nth_cell(table, hash_calc_hash(fold, table))->node);
115}
116
117#ifdef UNIV_DEBUG
118/********************************************************************//**
119Assert that the synchronization object in a hash operation involving
120possible change in the hash table is held.
121Note that in case of mutexes we assert that mutex is owned while in case
122of rw-locks we assert that it is held in exclusive mode. */
123UNIV_INLINE
124void
125hash_assert_can_modify(
126/*===================*/
127	hash_table_t*	table,	/*!< in: hash table */
128	ulint		fold)	/*!< in: fold value */
129{
130	if (table->type == HASH_TABLE_SYNC_MUTEX) {
131		ut_ad(mutex_own(hash_get_mutex(table, fold)));
132	} else if (table->type == HASH_TABLE_SYNC_RW_LOCK) {
133# ifdef UNIV_SYNC_DEBUG
134		prio_rw_lock_t* lock = hash_get_lock(table, fold);
135		ut_ad(rw_lock_own(lock, RW_LOCK_EX));
136# endif
137	} else {
138		ut_ad(table->type == HASH_TABLE_SYNC_NONE);
139	}
140}
141
142/********************************************************************//**
143Assert that the synchronization object in a hash search operation is held.
144Note that in case of mutexes we assert that mutex is owned while in case
145of rw-locks we assert that it is held either in x-mode or s-mode. */
146UNIV_INLINE
147void
148hash_assert_can_search(
149/*===================*/
150	hash_table_t*	table,	/*!< in: hash table */
151	ulint		fold)	/*!< in: fold value */
152{
153	if (table->type == HASH_TABLE_SYNC_MUTEX) {
154		ut_ad(mutex_own(hash_get_mutex(table, fold)));
155	} else if (table->type == HASH_TABLE_SYNC_RW_LOCK) {
156# ifdef UNIV_SYNC_DEBUG
157		prio_rw_lock_t* lock = hash_get_lock(table, fold);
158		ut_ad(rw_lock_own(lock, RW_LOCK_EX)
159		      || rw_lock_own(lock, RW_LOCK_SHARED));
160# endif
161	} else {
162		ut_ad(table->type == HASH_TABLE_SYNC_NONE);
163	}
164}
165#endif /* UNIV_DEBUG */
166
167/*************************************************************//**
168Looks for an element in a hash table.
169@return pointer to the data of the first hash table node in chain
170having the fold number, NULL if not found */
171UNIV_INLINE
172const rec_t*
173ha_search_and_get_data(
174/*===================*/
175	hash_table_t*	table,	/*!< in: hash table */
176	ulint		fold)	/*!< in: folded value of the searched data */
177{
178	ha_node_t*	node;
179
180	hash_assert_can_search(table, fold);
181	ut_ad(btr_search_enabled);
182
183	node = ha_chain_get_first(table, fold);
184
185	while (node) {
186		if (node->fold == fold) {
187
188			return(node->data);
189		}
190
191		node = ha_chain_get_next(node);
192	}
193
194	return(NULL);
195}
196
197/*********************************************************//**
198Looks for an element when we know the pointer to the data.
199@return	pointer to the hash table node, NULL if not found in the table */
200UNIV_INLINE
201ha_node_t*
202ha_search_with_data(
203/*================*/
204	hash_table_t*	table,	/*!< in: hash table */
205	ulint		fold,	/*!< in: folded value of the searched data */
206	const rec_t*	data)	/*!< in: pointer to the data */
207{
208	ha_node_t*	node;
209
210	hash_assert_can_search(table, fold);
211
212	ut_ad(btr_search_enabled);
213
214	node = ha_chain_get_first(table, fold);
215
216	while (node) {
217		if (node->data == data) {
218
219			return(node);
220		}
221
222		node = ha_chain_get_next(node);
223	}
224
225	return(NULL);
226}
227
228/*********************************************************//**
229Looks for an element when we know the pointer to the data, and deletes
230it from the hash table, if found.
231@return	TRUE if found */
232UNIV_INLINE
233ibool
234ha_search_and_delete_if_found(
235/*==========================*/
236	hash_table_t*	table,	/*!< in: hash table */
237	ulint		fold,	/*!< in: folded value of the searched data */
238	const rec_t*	data)	/*!< in: pointer to the data */
239{
240	ha_node_t*	node;
241
242	hash_assert_can_modify(table, fold);
243	ut_ad(btr_search_enabled);
244
245	node = ha_search_with_data(table, fold, data);
246
247	if (node) {
248		ha_delete_hash_node(table, node);
249
250		return(TRUE);
251	}
252
253	return(FALSE);
254}
255