1/*****************************************************************************
2
3Copyright (c) 1997, 2016, Oracle and/or its affiliates. All Rights Reserved.
4Copyright (c) 2018, MariaDB Corporation.
5
6This program is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free Software
8Foundation; version 2 of the License.
9
10This program is distributed in the hope that it will be useful, but WITHOUT
11ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License along with
15this program; if not, write to the Free Software Foundation, Inc.,
1651 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
17
18*****************************************************************************/
19
20/**************************************************//**
21@file include/hash0hash.h
22The simple hash table utility
23
24Created 5/20/1997 Heikki Tuuri
25*******************************************************/
26
27#ifndef hash0hash_h
28#define hash0hash_h
29
30#include "univ.i"
31#include "mem0mem.h"
32#include "sync0rw.h"
33
34struct hash_table_t;
35struct hash_cell_t;
36
37typedef void* hash_node_t;
38
39/* Fix Bug #13859: symbol collision between imap/mysql */
40#define hash_create hash0_create
41
42/* Differnt types of hash_table based on the synchronization
43method used for it. */
44enum hash_table_sync_t {
45 HASH_TABLE_SYNC_NONE = 0, /*!< Don't use any internal
46 synchronization objects for
47 this hash_table. */
48 HASH_TABLE_SYNC_MUTEX, /*!< Use mutexes to control
49 access to this hash_table. */
50 HASH_TABLE_SYNC_RW_LOCK /*!< Use rw_locks to control
51 access to this hash_table. */
52};
53
54/*************************************************************//**
55Creates a hash table with >= n array cells. The actual number
56of cells is chosen to be a prime number slightly bigger than n.
57@return own: created table */
58hash_table_t*
59hash_create(
60/*========*/
61 ulint n); /*!< in: number of array cells */
62
63/*************************************************************//**
64Creates a sync object array array to protect a hash table.
65::sync_obj can be mutexes or rw_locks depening on the type of
66hash table. */
67void
68hash_create_sync_obj(
69/*=================*/
70 hash_table_t* table, /*!< in: hash table */
71 hash_table_sync_t type, /*!< in: HASH_TABLE_SYNC_MUTEX
72 or HASH_TABLE_SYNC_RW_LOCK */
73 latch_id_t id, /*!< in: mutex/rw_lock ID */
74 ulint n_sync_obj);/*!< in: number of sync objects,
75 must be a power of 2 */
76
77/*************************************************************//**
78Frees a hash table. */
79void
80hash_table_free(
81/*============*/
82 hash_table_t* table); /*!< in, own: hash table */
83/**************************************************************//**
84Calculates the hash value from a folded value.
85@return hashed value */
86UNIV_INLINE
87ulint
88hash_calc_hash(
89/*===========*/
90 ulint fold, /*!< in: folded value */
91 hash_table_t* table); /*!< in: hash table */
92/********************************************************************//**
93Assert that the mutex for the table is held */
94#define HASH_ASSERT_OWN(TABLE, FOLD) \
95 ut_ad((TABLE)->type != HASH_TABLE_SYNC_MUTEX \
96 || (mutex_own(hash_get_mutex((TABLE), FOLD))));
97
98/*******************************************************************//**
99Inserts a struct to a hash table. */
100
101#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
102do {\
103 hash_cell_t* cell3333;\
104 TYPE* struct3333;\
105\
106 HASH_ASSERT_OWN(TABLE, FOLD)\
107\
108 (DATA)->NAME = NULL;\
109\
110 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
111\
112 if (cell3333->node == NULL) {\
113 cell3333->node = DATA;\
114 } else {\
115 struct3333 = (TYPE*) cell3333->node;\
116\
117 while (struct3333->NAME != NULL) {\
118\
119 struct3333 = (TYPE*) struct3333->NAME;\
120 }\
121\
122 struct3333->NAME = DATA;\
123 }\
124} while (0)
125
126/*******************************************************************//**
127Inserts a struct to the head of hash table. */
128
129#define HASH_PREPEND(TYPE, NAME, TABLE, FOLD, DATA) \
130do { \
131 hash_cell_t* cell3333; \
132 TYPE* struct3333; \
133 \
134 HASH_ASSERT_OWN(TABLE, FOLD) \
135 \
136 (DATA)->NAME = NULL; \
137 \
138 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
139 \
140 if (cell3333->node == NULL) { \
141 cell3333->node = DATA; \
142 DATA->NAME = NULL; \
143 } else { \
144 struct3333 = (TYPE*) cell3333->node; \
145 \
146 DATA->NAME = struct3333; \
147 \
148 cell3333->node = DATA; \
149 } \
150} while (0)
151#ifdef UNIV_HASH_DEBUG
152# define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1)
153# define HASH_INVALIDATE(DATA, NAME) *(void**) (&DATA->NAME) = (void*) -1
154#else
155# define HASH_ASSERT_VALID(DATA) do {} while (0)
156# define HASH_INVALIDATE(DATA, NAME) do {} while (0)
157#endif
158
159/*******************************************************************//**
160Deletes a struct from a hash table. */
161
162#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
163do {\
164 hash_cell_t* cell3333;\
165 TYPE* struct3333;\
166\
167 HASH_ASSERT_OWN(TABLE, FOLD)\
168\
169 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
170\
171 if (cell3333->node == DATA) {\
172 HASH_ASSERT_VALID(DATA->NAME);\
173 cell3333->node = DATA->NAME;\
174 } else {\
175 struct3333 = (TYPE*) cell3333->node;\
176\
177 while (struct3333->NAME != DATA) {\
178\
179 struct3333 = (TYPE*) struct3333->NAME;\
180 ut_a(struct3333);\
181 }\
182\
183 struct3333->NAME = DATA->NAME;\
184 }\
185 HASH_INVALIDATE(DATA, NAME);\
186} while (0)
187
188/*******************************************************************//**
189Gets the first struct in a hash chain, NULL if none. */
190
191#define HASH_GET_FIRST(TABLE, HASH_VAL)\
192 (hash_get_nth_cell(TABLE, HASH_VAL)->node)
193
194/*******************************************************************//**
195Gets the next struct in a hash chain, NULL if none. */
196
197#define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME)
198
199/********************************************************************//**
200Looks for a struct in a hash table. */
201#define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\
202{\
203\
204 HASH_ASSERT_OWN(TABLE, FOLD)\
205\
206 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\
207 HASH_ASSERT_VALID(DATA);\
208\
209 while ((DATA) != NULL) {\
210 ASSERTION;\
211 if (TEST) {\
212 break;\
213 } else {\
214 HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\
215 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\
216 }\
217 }\
218}
219
220/********************************************************************//**
221Looks for an item in all hash buckets. */
222#define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \
223do { \
224 ulint i3333; \
225 \
226 for (i3333 = (TABLE)->n_cells; i3333--; ) { \
227 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \
228 \
229 while ((DATA) != NULL) { \
230 HASH_ASSERT_VALID(DATA); \
231 ASSERTION; \
232 \
233 if (TEST) { \
234 break; \
235 } \
236 \
237 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \
238 } \
239 \
240 if ((DATA) != NULL) { \
241 break; \
242 } \
243 } \
244} while (0)
245
246/************************************************************//**
247Gets the nth cell in a hash table.
248@return pointer to cell */
249UNIV_INLINE
250hash_cell_t*
251hash_get_nth_cell(
252/*==============*/
253 hash_table_t* table, /*!< in: hash table */
254 ulint n); /*!< in: cell index */
255
256/*************************************************************//**
257Clears a hash table so that all the cells become empty. */
258UNIV_INLINE
259void
260hash_table_clear(
261/*=============*/
262 hash_table_t* table); /*!< in/out: hash table */
263
264/*************************************************************//**
265Returns the number of cells in a hash table.
266@return number of cells */
267UNIV_INLINE
268ulint
269hash_get_n_cells(
270/*=============*/
271 hash_table_t* table); /*!< in: table */
272/*******************************************************************//**
273Deletes a struct which is stored in the heap of the hash table, and compacts
274the heap. The fold value must be stored in the struct NODE in a field named
275'fold'. */
276
277#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\
278do {\
279 TYPE* node111;\
280 TYPE* top_node111;\
281 hash_cell_t* cell111;\
282 ulint fold111;\
283\
284 fold111 = (NODE)->fold;\
285\
286 HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\
287\
288 top_node111 = (TYPE*) mem_heap_get_top(\
289 hash_get_heap(TABLE, fold111),\
290 sizeof(TYPE));\
291\
292 /* If the node to remove is not the top node in the heap, compact the\
293 heap of nodes by moving the top node in the place of NODE. */\
294\
295 if (NODE != top_node111) {\
296\
297 /* Copy the top node in place of NODE */\
298\
299 *(NODE) = *top_node111;\
300\
301 cell111 = hash_get_nth_cell(TABLE,\
302 hash_calc_hash(top_node111->fold, TABLE));\
303\
304 /* Look for the pointer to the top node, to update it */\
305\
306 if (cell111->node == top_node111) {\
307 /* The top node is the first in the chain */\
308\
309 cell111->node = NODE;\
310 } else {\
311 /* We have to look for the predecessor of the top\
312 node */\
313 node111 = static_cast<TYPE*>(cell111->node);\
314\
315 while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\
316\
317 node111 = static_cast<TYPE*>(\
318 HASH_GET_NEXT(NAME, node111));\
319 }\
320\
321 /* Now we have the predecessor node */\
322\
323 node111->NAME = NODE;\
324 }\
325 }\
326\
327 /* Free the space occupied by the top node */\
328\
329 mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\
330} while (0)
331
332/****************************************************************//**
333Move all hash table entries from OLD_TABLE to NEW_TABLE. */
334
335#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
336do {\
337 ulint i2222;\
338 ulint cell_count2222;\
339\
340 cell_count2222 = hash_get_n_cells(OLD_TABLE);\
341\
342 for (i2222 = 0; i2222 < cell_count2222; i2222++) {\
343 NODE_TYPE* node2222 = static_cast<NODE_TYPE*>(\
344 HASH_GET_FIRST((OLD_TABLE), i2222));\
345\
346 while (node2222) {\
347 NODE_TYPE* next2222 = static_cast<NODE_TYPE*>(\
348 node2222->PTR_NAME);\
349 ulint fold2222 = FOLD_FUNC(node2222);\
350\
351 HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\
352 fold2222, node2222);\
353\
354 node2222 = next2222;\
355 }\
356 }\
357} while (0)
358
359/************************************************************//**
360Gets the sync object index for a fold value in a hash table.
361@return index */
362UNIV_INLINE
363ulint
364hash_get_sync_obj_index(
365/*====================*/
366 hash_table_t* table, /*!< in: hash table */
367 ulint fold); /*!< in: fold */
368/************************************************************//**
369Gets the nth heap in a hash table.
370@return mem heap */
371UNIV_INLINE
372mem_heap_t*
373hash_get_nth_heap(
374/*==============*/
375 hash_table_t* table, /*!< in: hash table */
376 ulint i); /*!< in: index of the heap */
377/************************************************************//**
378Gets the heap for a fold value in a hash table.
379@return mem heap */
380UNIV_INLINE
381mem_heap_t*
382hash_get_heap(
383/*==========*/
384 hash_table_t* table, /*!< in: hash table */
385 ulint fold); /*!< in: fold */
386/************************************************************//**
387Gets the nth mutex in a hash table.
388@return mutex */
389UNIV_INLINE
390ib_mutex_t*
391hash_get_nth_mutex(
392/*===============*/
393 hash_table_t* table, /*!< in: hash table */
394 ulint i); /*!< in: index of the mutex */
395/************************************************************//**
396Gets the nth rw_lock in a hash table.
397@return rw_lock */
398UNIV_INLINE
399rw_lock_t*
400hash_get_nth_lock(
401/*==============*/
402 hash_table_t* table, /*!< in: hash table */
403 ulint i); /*!< in: index of the rw_lock */
404/************************************************************//**
405Gets the mutex for a fold value in a hash table.
406@return mutex */
407UNIV_INLINE
408ib_mutex_t*
409hash_get_mutex(
410/*===========*/
411 hash_table_t* table, /*!< in: hash table */
412 ulint fold); /*!< in: fold */
413/************************************************************//**
414Gets the rw_lock for a fold value in a hash table.
415@return rw_lock */
416UNIV_INLINE
417rw_lock_t*
418hash_get_lock(
419/*==========*/
420 hash_table_t* table, /*!< in: hash table */
421 ulint fold); /*!< in: fold */
422
423/** If not appropriate rw_lock for a fold value in a hash table,
424relock S-lock the another rw_lock until appropriate for a fold value.
425@param[in] hash_lock latched rw_lock to be confirmed
426@param[in] table hash table
427@param[in] fold fold value
428@return latched rw_lock */
429UNIV_INLINE
430rw_lock_t*
431hash_lock_s_confirm(
432 rw_lock_t* hash_lock,
433 hash_table_t* table,
434 ulint fold);
435
436/** If not appropriate rw_lock for a fold value in a hash table,
437relock X-lock the another rw_lock until appropriate for a fold value.
438@param[in] hash_lock latched rw_lock to be confirmed
439@param[in] table hash table
440@param[in] fold fold value
441@return latched rw_lock */
442UNIV_INLINE
443rw_lock_t*
444hash_lock_x_confirm(
445 rw_lock_t* hash_lock,
446 hash_table_t* table,
447 ulint fold);
448
449/************************************************************//**
450Reserves all the locks of a hash table, in an ascending order. */
451void
452hash_lock_x_all(
453/*============*/
454 hash_table_t* table); /*!< in: hash table */
455/************************************************************//**
456Releases all the locks of a hash table, in an ascending order. */
457void
458hash_unlock_x_all(
459/*==============*/
460 hash_table_t* table); /*!< in: hash table */
461/************************************************************//**
462Releases all but passed in lock of a hash table, */
463void
464hash_unlock_x_all_but(
465/*==================*/
466 hash_table_t* table, /*!< in: hash table */
467 rw_lock_t* keep_lock); /*!< in: lock to keep */
468
469struct hash_cell_t{
470 void* node; /*!< hash chain node, NULL if none */
471};
472
473/* The hash table structure */
474struct hash_table_t {
475 enum hash_table_sync_t type; /*<! type of hash_table. */
476#ifdef BTR_CUR_HASH_ADAPT
477# if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
478 ibool adaptive;/* TRUE if this is the hash
479 table of the adaptive hash
480 index */
481# endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
482#endif /* BTR_CUR_HASH_ADAPT */
483 ulint n_cells;/* number of cells in the hash table */
484 hash_cell_t* array; /*!< pointer to cell array */
485
486 ulint n_sync_obj;/* if sync_objs != NULL, then
487 the number of either the number
488 of mutexes or the number of
489 rw_locks depending on the type.
490 Must be a power of 2 */
491 union {
492 ib_mutex_t* mutexes;/* NULL, or an array of mutexes
493 used to protect segments of the
494 hash table */
495 rw_lock_t* rw_locks;/* NULL, or an array of rw_lcoks
496 used to protect segments of the
497 hash table */
498 } sync_obj;
499
500 mem_heap_t** heaps; /*!< if this is non-NULL, hash
501 chain nodes for external chaining
502 can be allocated from these memory
503 heaps; there are then n_mutexes
504 many of these heaps */
505 mem_heap_t* heap;
506#ifdef UNIV_DEBUG
507 ulint magic_n;
508# define HASH_TABLE_MAGIC_N 76561114
509#endif /* UNIV_DEBUG */
510};
511
512#include "hash0hash.ic"
513
514#endif
515