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