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