MySQL  8.0.19
Source Code Documentation
hash0hash.h
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (c) 1997, 2018, Oracle and/or its affiliates. All Rights Reserved.
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 /** Creates a sync object array array to protect a hash table. "::sync_obj"
71 can be mutexes or rw_locks depening on the type of hash table.
72 @param[in] table hash table
73 @param[in] type HASH_TABLE_SYNC_MUTEX or HASH_TABLE_SYNC_RW_LOCK
74 @param[in] id mutex/rw_lock ID
75 @param[in] n_sync_obj number of sync objects, must be a power of 2*/
77  latch_id_t id, ulint n_sync_obj);
78 #endif /* !UNIV_HOTBACKUP */
79 
80 /** Frees a hash table. */
81 void hash_table_free(hash_table_t *table); /*!< in, own: hash table */
82 
83 /** Calculates the hash value from a folded value.
84 @param[in] fold folded value
85 @param[in] table hash table
86 @return hashed value */
87 UNIV_INLINE
88 ulint hash_calc_hash(ulint fold, hash_table_t *table);
89 
90 #ifndef UNIV_HOTBACKUP
91 /** Assert that the mutex for the table is held */
92 #define HASH_ASSERT_OWN(TABLE, FOLD) \
93  ut_ad((TABLE)->type != HASH_TABLE_SYNC_MUTEX || \
94  (mutex_own(hash_get_mutex((TABLE), FOLD))));
95 #else /* !UNIV_HOTBACKUP */
96 #define HASH_ASSERT_OWN(TABLE, FOLD)
97 #endif /* !UNIV_HOTBACKUP */
98 
99 /** Inserts a struct to a hash table. */
100 
101 #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA) \
102  do { \
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  struct3333 = (TYPE *)struct3333->NAME; \
119  } \
120  \
121  struct3333->NAME = DATA; \
122  } \
123  } while (0)
124 
125 #ifdef UNIV_HASH_DEBUG
126 #define HASH_ASSERT_VALID(DATA) ut_a((void *)(DATA) != (void *)-1)
127 #define HASH_INVALIDATE(DATA, NAME) *(void **)(&DATA->NAME) = (void *)-1
128 #else
129 #define HASH_ASSERT_VALID(DATA) \
130  do { \
131  } while (0)
132 #define HASH_INVALIDATE(DATA, NAME) \
133  do { \
134  } while (0)
135 #endif
136 
137 /** Deletes a struct from a hash table. */
138 
139 #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA) \
140  do { \
141  hash_cell_t *cell3333; \
142  TYPE *struct3333; \
143  \
144  HASH_ASSERT_OWN(TABLE, FOLD) \
145  \
146  cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE)); \
147  \
148  if (cell3333->node == DATA) { \
149  HASH_ASSERT_VALID(DATA->NAME); \
150  cell3333->node = DATA->NAME; \
151  } else { \
152  struct3333 = (TYPE *)cell3333->node; \
153  \
154  while (struct3333->NAME != DATA) { \
155  struct3333 = (TYPE *)struct3333->NAME; \
156  ut_a(struct3333); \
157  } \
158  \
159  struct3333->NAME = DATA->NAME; \
160  } \
161  HASH_INVALIDATE(DATA, NAME); \
162  } while (0)
163 
164 /** Gets the first struct in a hash chain, NULL if none. */
165 
166 #define HASH_GET_FIRST(TABLE, HASH_VAL) \
167  (hash_get_nth_cell(TABLE, HASH_VAL)->node)
168 
169 /** Gets the next struct in a hash chain, NULL if none. */
170 
171 #define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME)
172 
173 /** Looks for a struct in a hash table. */
174 #define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST) \
175  { \
176  HASH_ASSERT_OWN(TABLE, FOLD) \
177  \
178  (DATA) = (TYPE)HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE)); \
179  HASH_ASSERT_VALID(DATA); \
180  \
181  while ((DATA) != NULL) { \
182  ASSERTION; \
183  if (TEST) { \
184  break; \
185  } else { \
186  HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA)); \
187  (DATA) = (TYPE)HASH_GET_NEXT(NAME, DATA); \
188  } \
189  } \
190  }
191 
192 /** Looks for an item in all hash buckets. */
193 #define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \
194  do { \
195  ulint i3333; \
196  \
197  for (i3333 = (TABLE)->n_cells; i3333--;) { \
198  (DATA) = (TYPE)HASH_GET_FIRST(TABLE, i3333); \
199  \
200  while ((DATA) != NULL) { \
201  HASH_ASSERT_VALID(DATA); \
202  ASSERTION; \
203  \
204  if (TEST) { \
205  break; \
206  } \
207  \
208  (DATA) = (TYPE)HASH_GET_NEXT(NAME, DATA); \
209  } \
210  \
211  if ((DATA) != NULL) { \
212  break; \
213  } \
214  } \
215  } while (0)
216 
217 /** Gets the nth cell in a hash table.
218 @param[in] table hash table
219 @param[in] n cell index
220 @return pointer to cell */
221 UNIV_INLINE
223 
224 /** Clears a hash table so that all the cells become empty. */
225 UNIV_INLINE
226 void hash_table_clear(hash_table_t *table); /*!< in/out: hash table */
227 
228 /** Returns the number of cells in a hash table.
229  @return number of cells */
230 UNIV_INLINE
231 ulint hash_get_n_cells(hash_table_t *table); /*!< in: table */
232 /** Deletes a struct which is stored in the heap of the hash table, and compacts
233  the heap. The fold value must be stored in the struct NODE in a field named
234  'fold'. */
235 
236 #define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE) \
237  do { \
238  TYPE *node111; \
239  TYPE *top_node111; \
240  hash_cell_t *cell111; \
241  ulint fold111; \
242  \
243  fold111 = (NODE)->fold; \
244  \
245  HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE); \
246  \
247  top_node111 = \
248  (TYPE *)mem_heap_get_top(hash_get_heap(TABLE, fold111), sizeof(TYPE)); \
249  \
250  /* If the node to remove is not the top node in the heap, compact the \
251  heap of nodes by moving the top node in the place of NODE. */ \
252  \
253  if (NODE != top_node111) { \
254  /* Copy the top node in place of NODE */ \
255  \
256  *(NODE) = *top_node111; \
257  \
258  cell111 = \
259  hash_get_nth_cell(TABLE, hash_calc_hash(top_node111->fold, TABLE)); \
260  \
261  /* Look for the pointer to the top node, to update it */ \
262  \
263  if (cell111->node == top_node111) { \
264  /* The top node is the first in the chain */ \
265  \
266  cell111->node = NODE; \
267  } else { \
268  /* We have to look for the predecessor of the top \
269  node */ \
270  node111 = static_cast<TYPE *>(cell111->node); \
271  \
272  while (top_node111 != HASH_GET_NEXT(NAME, node111)) { \
273  node111 = static_cast<TYPE *>(HASH_GET_NEXT(NAME, node111)); \
274  } \
275  \
276  /* Now we have the predecessor node */ \
277  \
278  node111->NAME = NODE; \
279  } \
280  } \
281  \
282  /* Free the space occupied by the top node */ \
283  \
284  mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE)); \
285  } while (0)
286 
287 #ifndef UNIV_HOTBACKUP
288 /** Move all hash table entries from OLD_TABLE to NEW_TABLE. */
289 
290 #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
291  do { \
292  ulint i2222; \
293  ulint cell_count2222; \
294  \
295  cell_count2222 = hash_get_n_cells(OLD_TABLE); \
296  \
297  for (i2222 = 0; i2222 < cell_count2222; i2222++) { \
298  NODE_TYPE *node2222 = \
299  static_cast<NODE_TYPE *>(HASH_GET_FIRST((OLD_TABLE), i2222)); \
300  \
301  while (node2222) { \
302  NODE_TYPE *next2222 = static_cast<NODE_TYPE *>(node2222->PTR_NAME); \
303  ulint fold2222 = FOLD_FUNC(node2222); \
304  \
305  HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE), fold2222, node2222); \
306  \
307  node2222 = next2222; \
308  } \
309  } \
310  } while (0)
311 
312 /** Gets the sync object index for a fold value in a hash table.
313 @param[in] table hash table
314 @param[in] fold fold
315 @return index */
316 UNIV_INLINE
317 ulint hash_get_sync_obj_index(hash_table_t *table, ulint fold);
318 
319 /** Gets the nth heap in a hash table.
320 @param[in] table hash table
321 @param[in] i index of the mutex
322 @return mem heap */
323 UNIV_INLINE
324 mem_heap_t *hash_get_nth_heap(hash_table_t *table, ulint i);
325 
326 /** Gets the heap for a fold value in a hash table.
327 @param[in] table hash table
328 @param[in] fold fold
329 @return mem heap */
330 UNIV_INLINE
331 mem_heap_t *hash_get_heap(hash_table_t *table, ulint fold);
332 
333 /** Gets the nth mutex in a hash table.
334 @param[in] table hash table
335 @param[in] i index of the mutex
336 @return mutex */
337 UNIV_INLINE
338 ib_mutex_t *hash_get_nth_mutex(hash_table_t *table, ulint i);
339 
340 /** Gets the nth rw_lock in a hash table.
341 @param[in] table hash table
342 @param[in] i index of the mutex
343 @return rw_lock */
344 UNIV_INLINE
345 rw_lock_t *hash_get_nth_lock(hash_table_t *table, ulint i);
346 
347 /** Gets the mutex for a fold value in a hash table.
348 @param[in] table hash table
349 @param[in] fold fold
350 @return mutex */
351 UNIV_INLINE
352 ib_mutex_t *hash_get_mutex(hash_table_t *table, ulint fold);
353 
354 /** Gets the rw_lock for a fold value in a hash table.
355 @param[in] table hash table
356 @param[in] fold fold
357 @return rw_lock */
358 UNIV_INLINE
359 rw_lock_t *hash_get_lock(hash_table_t *table, ulint fold);
360 
361 /** If not appropriate rw_lock for a fold value in a hash table,
362 relock S-lock the another rw_lock until appropriate for a fold value.
363 @param[in] hash_lock latched rw_lock to be confirmed
364 @param[in] table hash table
365 @param[in] fold fold value
366 @return latched rw_lock */
367 UNIV_INLINE
369  ulint fold);
370 
371 /** If not appropriate rw_lock for a fold value in a hash table,
372 relock X-lock the another rw_lock until appropriate for a fold value.
373 @param[in] hash_lock latched rw_lock to be confirmed
374 @param[in] table hash table
375 @param[in] fold fold value
376 @return latched rw_lock */
377 UNIV_INLINE
379  ulint fold);
380 
381 /** Reserves all the locks of a hash table, in an ascending order. */
382 void hash_lock_x_all(hash_table_t *table); /*!< in: hash table */
383 /** Releases all the locks of a hash table, in an ascending order. */
384 void hash_unlock_x_all(hash_table_t *table); /*!< in: hash table */
385 /** Releases all but passed in lock of a hash table, */
386 void hash_unlock_x_all_but(hash_table_t *table, /*!< in: hash table */
387  rw_lock_t *keep_lock); /*!< in: lock to keep */
388 
389 #else /* !UNIV_HOTBACKUP */
390 #define hash_get_heap(table, fold) ((table)->heap)
391 #define hash_lock_x_all(t) ((void)0)
392 #define hash_unlock_x_all(t) ((void)0)
393 #define hash_unlock_x_all_but(t, l) ((void)0)
394 #endif /* !UNIV_HOTBACKUP */
395 
396 struct hash_cell_t {
397  void *node; /*!< hash chain node, NULL if none */
398 };
399 
400 /* The hash table structure */
401 struct hash_table_t {
402  enum hash_table_sync_t type; /*!< type of hash_table. */
403 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
404 #ifndef UNIV_HOTBACKUP
405  ibool adaptive; /* TRUE if this is the hash
406  table of the adaptive hash
407  index */
408 #endif /* !UNIV_HOTBACKUP */
409 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
410  ulint n_cells; /* number of cells in the hash table */
411  hash_cell_t *cells; /*!< pointer to cell array */
412 #ifndef UNIV_HOTBACKUP
413  ulint n_sync_obj; /* if sync_objs != NULL, then
414  the number of either the number
415  of mutexes or the number of
416  rw_locks depending on the type.
417  Must be a power of 2 */
418  union {
419  ib_mutex_t *mutexes; /* NULL, or an array of mutexes
420  used to protect segments of the
421  hash table */
422  rw_lock_t *rw_locks; /* NULL, or an array of rw_lcoks
423  used to protect segments of the
424  hash table */
426 
427  mem_heap_t **heaps; /*!< if this is non-NULL, hash
428  chain nodes for external chaining
429  can be allocated from these memory
430  heaps; there are then n_mutexes
431  many of these heaps */
432 #endif /* !UNIV_HOTBACKUP */
434 #ifdef UNIV_DEBUG
435  ulint magic_n;
436 #define HASH_TABLE_MAGIC_N 76561114
437 #endif /* UNIV_DEBUG */
438 };
439 
440 #include "hash0hash.ic"
441 
442 #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:431
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_t::sync_obj
union hash_table_t::@129 sync_obj
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:409
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::n_sync_obj
ulint n_sync_obj
Definition: hash0hash.h:411
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:337
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:394
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:433
hash_table_t
Definition: hash0hash.h:399
hash_table_t::mutexes
ib_mutex_t * mutexes
Definition: hash0hash.h:417
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:425
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:344
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:400
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:395
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
HttpMethod::type
int type
Definition: http_common.h:411
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:408
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 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:555
hash_table_t::adaptive
ibool adaptive
Definition: hash0hash.h:403
n
int n
Definition: xcom_base.c:425
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
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:420