MySQL 8.0.31
Source Code Documentation
hash0hash.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 1997, 2022, Oracle and/or its affiliates.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License, version 2.0, as published by the
7Free Software Foundation.
8
9This program is also distributed with certain software (including but not
10limited to OpenSSL) that is licensed under separate terms, as designated in a
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
13your derivative works with the separately licensed software that they have
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for 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 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#include "ut0rnd.h"
41#ifndef UNIV_HOTBACKUP
42#include "sync0rw.h"
43#endif /* !UNIV_HOTBACKUP */
44
45class hash_table_t;
46struct hash_cell_t;
47
48typedef void *hash_node_t;
49
50/* Different types of hash_table based on the synchronization
51method used for it. */
53 HASH_TABLE_SYNC_NONE = 0, /*!< Don't use any internal
54 synchronization objects for
55 this hash_table. */
56 HASH_TABLE_SYNC_RW_LOCK /*!< Use rw_locks to control
57 access to this hash_table. */
58};
59
61 void *node; /*!< hash chain node, NULL if none */
62};
63
64#ifndef UNIV_HOTBACKUP
65
66/** Creates a sync object array to protect a hash table.
67@param[in] table hash table
68@param[in] id latch ID
69@param[in] n_sync_obj number of sync objects, must be a power of 2 */
71 size_t n_sync_obj);
72#endif /* !UNIV_HOTBACKUP */
73
74/** Calculates the cell index from a hashed value for a specified hash table.
75@param[in] hash_value hashed value
76@param[in] table hash table
77@return cell index for specified hash table*/
78static inline uint64_t hash_calc_cell_id(uint64_t hash_value,
79 hash_table_t *table);
80
81/** Gets the nth cell in a hash table.
82@param[in] table hash table
83@param[in] n cell index
84@return pointer to cell */
85static inline hash_cell_t *hash_get_nth_cell(hash_table_t *table, size_t n);
86
87/** Inserts a struct to a hash table. */
88
89#define HASH_INSERT(TYPE, NAME, TABLE, HASH_VALUE, DATA) \
90 do { \
91 hash_cell_t *cell3333; \
92 TYPE *struct3333; \
93 const uint64_t hash_value3333 = HASH_VALUE; \
94 \
95 hash_assert_can_modify(TABLE, hash_value3333); \
96 \
97 (DATA)->NAME = NULL; \
98 \
99 cell3333 = \
100 hash_get_nth_cell(TABLE, hash_calc_cell_id(hash_value3333, TABLE)); \
101 \
102 if (cell3333->node == NULL) { \
103 cell3333->node = DATA; \
104 } else { \
105 struct3333 = (TYPE *)cell3333->node; \
106 \
107 while (struct3333->NAME != NULL) { \
108 struct3333 = (TYPE *)struct3333->NAME; \
109 } \
110 \
111 struct3333->NAME = DATA; \
112 } \
113 } while (0)
114
115#ifdef UNIV_HASH_DEBUG
116#define HASH_ASSERT_VALID(DATA) ut_a((void *)(DATA) != (void *)-1)
117#define HASH_INVALIDATE(DATA, NAME) *(void **)(&DATA->NAME) = (void *)-1
118#else
119#define HASH_ASSERT_VALID(DATA) \
120 do { \
121 } while (0)
122#define HASH_INVALIDATE(DATA, NAME) \
123 do { \
124 } while (0)
125#endif
126
127/** Deletes a struct from a hash table. */
128
129#define HASH_DELETE(TYPE, NAME, TABLE, HASH_VALUE, DATA) \
130 do { \
131 hash_cell_t *cell3333; \
132 TYPE *struct3333; \
133 const uint64_t hash_value3333 = HASH_VALUE; \
134 \
135 hash_assert_can_modify(TABLE, hash_value3333); \
136 \
137 cell3333 = \
138 hash_get_nth_cell(TABLE, hash_calc_cell_id(hash_value3333, TABLE)); \
139 \
140 if (cell3333->node == DATA) { \
141 HASH_ASSERT_VALID(DATA->NAME); \
142 cell3333->node = DATA->NAME; \
143 } else { \
144 struct3333 = (TYPE *)cell3333->node; \
145 \
146 while (struct3333->NAME != DATA) { \
147 struct3333 = (TYPE *)struct3333->NAME; \
148 ut_a(struct3333); \
149 } \
150 \
151 struct3333->NAME = DATA->NAME; \
152 } \
153 HASH_INVALIDATE(DATA, NAME); \
154 } while (0)
155
156/** Gets the first struct in a hash chain, NULL if none. */
157
158static inline void *&hash_get_first(hash_table_t *table, size_t cell_id) {
159 return hash_get_nth_cell(table, cell_id)->node;
160}
161
162/** Gets the next struct in a hash chain, NULL if none. */
163
164#define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME)
165
166/** Looks for a struct in a hash table. */
167#define HASH_SEARCH(NAME, TABLE, HASH_VALUE, TYPE, DATA, ASSERTION, TEST) \
168 { \
169 const uint64_t hash_value3333 = HASH_VALUE; \
170 \
171 hash_assert_can_search(TABLE, hash_value3333); \
172 \
173 (DATA) = \
174 (TYPE)hash_get_first(TABLE, hash_calc_cell_id(hash_value3333, TABLE)); \
175 HASH_ASSERT_VALID(DATA); \
176 \
177 while ((DATA) != NULL) { \
178 ASSERTION; \
179 if (TEST) { \
180 break; \
181 } else { \
182 HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA)); \
183 (DATA) = (TYPE)HASH_GET_NEXT(NAME, DATA); \
184 } \
185 } \
186 }
187
188/** Looks for an item in all hash cells. */
189#define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \
190 do { \
191 size_t i3333; \
192 \
193 for (i3333 = (TABLE)->get_n_cells(); i3333--;) { \
194 (DATA) = (TYPE)hash_get_first(TABLE, i3333); \
195 \
196 while ((DATA) != NULL) { \
197 HASH_ASSERT_VALID(DATA); \
198 ASSERTION; \
199 \
200 if (TEST) { \
201 break; \
202 } \
203 \
204 (DATA) = (TYPE)HASH_GET_NEXT(NAME, DATA); \
205 } \
206 \
207 if ((DATA) != NULL) { \
208 break; \
209 } \
210 } \
211 } while (0)
212
213/** Clears a hash table so that all the cells become empty. */
214static inline void hash_table_clear(
215 hash_table_t *table); /*!< in/out: hash table */
216
217/** Returns the number of cells in a hash table.
218 @return number of cells */
219static inline size_t hash_get_n_cells(hash_table_t *table); /*!< in: table */
220
221/** Deletes a struct which is stored in the heap of the hash table, and compacts
222 the heap. The hash value must be stored in the struct NODE in a field named
223 'hash_value'. */
224#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE) \
225 do { \
226 TYPE *node111; \
227 TYPE *top_node111; \
228 hash_cell_t *cell111; \
229 uint64_t hash_value111; \
230 \
231 hash_value111 = (NODE)->hash_value; \
232 \
233 HASH_DELETE(TYPE, NAME, TABLE, hash_value111, NODE); \
234 \
235 top_node111 = \
236 (TYPE *)mem_heap_get_top(hash_get_heap(TABLE), sizeof(TYPE)); \
237 \
238 /* If the node to remove is not the top node in the heap, compact the \
239 heap of nodes by moving the top node in the place of NODE. */ \
240 \
241 if (NODE != top_node111) { \
242 /* Copy the top node in place of NODE */ \
243 \
244 *(NODE) = *top_node111; \
245 \
246 cell111 = hash_get_nth_cell( \
247 TABLE, hash_calc_cell_id(top_node111->hash_value, TABLE)); \
248 \
249 /* Look for the pointer to the top node, to update it */ \
250 \
251 if (cell111->node == top_node111) { \
252 /* The top node is the first in the chain */ \
253 \
254 cell111->node = NODE; \
255 } else { \
256 /* We have to look for the predecessor of the top \
257 node */ \
258 node111 = static_cast<TYPE *>(cell111->node); \
259 \
260 while (top_node111 != HASH_GET_NEXT(NAME, node111)) { \
261 node111 = static_cast<TYPE *>(HASH_GET_NEXT(NAME, node111)); \
262 } \
263 \
264 /* Now we have the predecessor node */ \
265 \
266 node111->NAME = NODE; \
267 } \
268 } \
269 \
270 /* Free the space occupied by the top node */ \
271 \
272 mem_heap_free_top(hash_get_heap(TABLE), sizeof(TYPE)); \
273 } while (0)
274
275#ifndef UNIV_HOTBACKUP
276/** Move all hash table entries from OLD_TABLE to NEW_TABLE. */
277
278#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, HASH_FUNC) \
279 do { \
280 size_t i2222; \
281 size_t cell_count2222; \
282 \
283 cell_count2222 = hash_get_n_cells(OLD_TABLE); \
284 \
285 for (i2222 = 0; i2222 < cell_count2222; i2222++) { \
286 NODE_TYPE *node2222 = \
287 static_cast<NODE_TYPE *>(hash_get_first((OLD_TABLE), i2222)); \
288 \
289 while (node2222) { \
290 NODE_TYPE *next2222 = static_cast<NODE_TYPE *>(node2222->PTR_NAME); \
291 uint64_t hash_value2222 = HASH_FUNC(node2222); \
292 \
293 HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE), hash_value2222, \
294 node2222); \
295 \
296 node2222 = next2222; \
297 } \
298 } \
299 } while (0)
300
301/** Gets the sync object index for a hash value in a hash table.
302@param[in] table hash table
303@param[in] hash_value hash value
304@return index */
305static inline uint64_t hash_get_sync_obj_index(hash_table_t *table,
306 uint64_t hash_value);
307
308/** Gets the heap for a hash value in a hash table.
309@param[in] table hash table
310@return mem heap */
311static inline mem_heap_t *hash_get_heap(hash_table_t *table);
312
313/** Gets the nth rw_lock in a hash table.
314@param[in] table hash table
315@param[in] i index of the rw_lock
316@return rw_lock */
317static inline rw_lock_t *hash_get_nth_lock(hash_table_t *table, size_t i);
318
319/** Gets the rw_lock for a hash value in a hash table.
320@param[in] table hash table
321@param[in] hash_value hash value
322@return rw_lock */
323static inline rw_lock_t *hash_get_lock(hash_table_t *table,
324 uint64_t hash_value);
325
326/** If not appropriate rw_lock for a hash value in a hash table,
327relock S-lock the another rw_lock until appropriate for a hash value.
328@param[in] hash_lock latched rw_lock to be confirmed
329@param[in] table hash table
330@param[in] hash_value hash value
331@return latched rw_lock */
332static inline rw_lock_t *hash_lock_s_confirm(rw_lock_t *hash_lock,
333 hash_table_t *table,
334 uint64_t hash_value);
335
336/** If not appropriate rw_lock for a hash value in a hash table,
337relock X-lock the another rw_lock until appropriate for a hash value.
338@param[in] hash_lock latched rw_lock to be confirmed
339@param[in] table hash table
340@param[in] hash_value hash value
341@return latched rw_lock */
342static inline rw_lock_t *hash_lock_x_confirm(rw_lock_t *hash_lock,
343 hash_table_t *table,
344 uint64_t hash_value);
345
346#ifdef UNIV_DEBUG
347
348/** Verifies that the current thread holds X-latch on all shards.
349Assumes type==HASH_TABLE_SYNC_RW_LOCK.
350@param[in] table the table in question
351@return true iff the current thread holds X-latch on all shards*/
352bool hash_lock_has_all_x(const hash_table_t *table);
353
354#endif /* UNIV_DEBUG */
355
356/** Reserves all the locks of a hash table, in an ascending order. */
357void hash_lock_x_all(hash_table_t *table); /*!< in: hash table */
358
359/** Releases all the locks of a hash table, in an ascending order. */
360void hash_unlock_x_all(hash_table_t *table); /*!< in: hash table */
361
362/** Releases all but passed in lock of a hash table,
363@param[in] table Hash table
364@param[in] keep_lock Lock to keep */
365void hash_unlock_x_all_but(hash_table_t *table, rw_lock_t *keep_lock);
366
367#else /* !UNIV_HOTBACKUP */
368#define hash_get_heap(table) ((table)->heap)
369#define hash_lock_x_all(t) ((void)0)
370#define hash_unlock_x_all(t) ((void)0)
371#define hash_unlock_x_all_but(t, l) ((void)0)
372#endif /* !UNIV_HOTBACKUP */
374/* The hash table structure */
376 public:
377 hash_table_t(size_t n) {
378 const auto prime = ut::find_prime(n);
379 cells = ut::make_unique<hash_cell_t[]>(prime);
380 set_n_cells(prime);
381
382 /* Initialize the cell array */
384 }
386
387 /** Returns number of cells in cells[] array.
388 If type==HASH_TABLE_SYNC_RW_LOCK it can be used:
389 - without any latches to peek a value, before hash_lock_[sx]_confirm
390 - when holding S-latch for at least one n_sync_obj to get the "real" value
391 @return value of n_cells
392 */
393 size_t get_n_cells() { return n_cells.load(std::memory_order_relaxed); }
394
395 /** Returns a helper class for calculating fast modulo n_cells.
396 If type==HASH_TABLE_SYNC_RW_LOCK it can be used:
397 - without any latches to peek a value, before hash_lock_[sx]_confirm
398 - when holding S-latch for at least one n_sync_obj to get the "real" value */
400 return n_cells_fast_modulo.load();
401 }
402
403 /** Sets the number of n_cells, to the provided one.
404 If type==HASH_TABLE_SYNC_RW_LOCK it can be used only when holding x-latches on
405 all shards.
406 @param[in] n The new size of cells[] array
407 */
408 void set_n_cells(size_t n) {
409#ifndef UNIV_HOTBACKUP
411#endif
412 n_cells.store(n);
414 }
415
416 public:
417 /** Either:
418 a) HASH_TABLE_SYNC_NONE in which case n_sync_obj is 0 and rw_locks is nullptr
419 or
420 b) HASH_TABLE_SYNC_RW_LOCK in which case n_sync_obj > 0 is the number of
421 rw_locks elements, each of which protects a disjoint fraction of cells.
422 The default type of hash_table is HASH_TABLE_SYNC_NONE i.e.: the caller is
423 responsible for access control to the table. */
425
426#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
427#ifndef UNIV_HOTBACKUP
428 /* true if this is the hash table of the adaptive hash index */
429 bool adaptive = false;
430#endif /* !UNIV_HOTBACKUP */
431#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
432 private:
433 /** The number of cells in the hash table.
434 If type==HASH_TABLE_SYNC_RW_LOCK it is:
435 - modified when holding X-latches on all n_sync_obj
436 - read
437 - without any latches to peek a value, before hash_lock_[sx]_confirm
438 - when holding S-latch for at least one n_sync_obj to get the "real" value
439 */
440 std::atomic<size_t> n_cells;
441 /** Utility to calculate the modulo n_cells fast. It is set together with
442 n_cells. It can be read without latches in parallel to set_n_cells, and as it
443 is a complex object, it is not set atomically. Because of this the
444 multi-threaded version is used. */
446
447 public:
448 /** The pointer to the array of cells.
449 If type==HASH_TABLE_SYNC_RW_LOCK it is:
450 - modified when holding X-latches on all n_sync_obj
451 - read when holding an S-latch for at least one n_sync_obj
452 */
454#ifndef UNIV_HOTBACKUP
455 /** if rw_locks != nullptr, then it's their number (must be a power of two).
456 Otherwise, 0. Is zero iff the type is HASH_TABLE_SYNC_NONE. */
457 size_t n_sync_obj = 0;
458 /** nullptr, or an array of n_sync_obj rw_locks used to protect segments of
459 the hash table. Is nullptr iff the type is HASH_TABLE_SYNC_NONE. */
460 rw_lock_t *rw_locks = nullptr;
462#endif /* !UNIV_HOTBACKUP */
463 mem_heap_t *heap = nullptr;
464#ifdef UNIV_DEBUG
465 static constexpr uint32_t HASH_TABLE_MAGIC_N = 76561114;
466 uint32_t magic_n = HASH_TABLE_MAGIC_N;
467#endif /* UNIV_DEBUG */
468};
469
470#include "hash0hash.ic"
471
472#endif
Definition: hash0hash.h:373
static constexpr uint32_t HASH_TABLE_MAGIC_N
Definition: hash0hash.h:463
hash_table_t(size_t n)
Definition: hash0hash.h:375
size_t n_sync_obj
if rw_locks != nullptr, then it's their number (must be a power of two).
Definition: hash0hash.h:455
uint32_t magic_n
Definition: hash0hash.h:464
void set_n_cells(size_t n)
Sets the number of n_cells, to the provided one.
Definition: hash0hash.h:406
enum hash_table_sync_t type
Either: a) HASH_TABLE_SYNC_NONE in which case n_sync_obj is 0 and rw_locks is nullptr or b) HASH_TABL...
Definition: hash0hash.h:422
rw_lock_t * rw_locks
nullptr, or an array of n_sync_obj rw_locks used to protect segments of the hash table.
Definition: hash0hash.h:458
ut::mt_fast_modulo_t n_cells_fast_modulo
Utility to calculate the modulo n_cells fast.
Definition: hash0hash.h:443
bool adaptive
Definition: hash0hash.h:427
std::atomic< size_t > n_cells
The number of cells in the hash table.
Definition: hash0hash.h:438
const ut::fast_modulo_t get_n_cells_fast_modulo()
Returns a helper class for calculating fast modulo n_cells.
Definition: hash0hash.h:397
~hash_table_t()
Definition: hash0hash.h:383
size_t get_n_cells()
Returns number of cells in cells[] array.
Definition: hash0hash.h:391
ut::unique_ptr< hash_cell_t[]> cells
The pointer to the array of cells.
Definition: hash0hash.h:451
mem_heap_t * heap
Definition: hash0hash.h:461
Allows to execute x % mod for a specified mod in a fast way, without using a slow operation of divisi...
Definition: ut0math.h:144
A class that allows to atomically set new modulo value for fast modulo computations.
Definition: ut0math.h:236
fast_modulo_t load()
Definition: ut0math.h:244
void store(uint64_t new_mod)
Definition: ut0math.h:251
void * hash_node_t
Definition: hash0hash.h:46
static rw_lock_t * hash_lock_s_confirm(rw_lock_t *hash_lock, hash_table_t *table, uint64_t hash_value)
If not appropriate rw_lock for a hash value in a hash table, relock S-lock the another rw_lock until ...
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:83
static void *& hash_get_first(hash_table_t *table, size_t cell_id)
Gets the first struct in a hash chain, NULL if none.
Definition: hash0hash.h:158
static rw_lock_t * hash_lock_x_confirm(rw_lock_t *hash_lock, hash_table_t *table, uint64_t hash_value)
If not appropriate rw_lock for a hash value in a hash table, relock X-lock the another rw_lock until ...
static uint64_t hash_get_sync_obj_index(hash_table_t *table, uint64_t hash_value)
Gets the sync object index for a hash value in a hash table.
hash_table_sync_t
Definition: hash0hash.h:52
@ HASH_TABLE_SYNC_RW_LOCK
Use rw_locks to control access to this hash_table.
Definition: hash0hash.h:56
@ HASH_TABLE_SYNC_NONE
Don't use any internal synchronization objects for this hash_table.
Definition: hash0hash.h:53
static hash_cell_t * hash_get_nth_cell(hash_table_t *table, size_t n)
Gets the nth cell in a hash table.
void hash_lock_x_all(hash_table_t *table)
Reserves all the locks of a hash table, in an ascending order.
Definition: hash0hash.cc:54
static uint64_t hash_calc_cell_id(uint64_t hash_value, hash_table_t *table)
Calculates the cell index from a hashed value for a specified hash table.
static rw_lock_t * hash_get_lock(hash_table_t *table, uint64_t hash_value)
Gets the rw_lock for a hash value in a hash table.
static mem_heap_t * hash_get_heap(hash_table_t *table)
Gets the heap for a hash value in a hash table.
static rw_lock_t * hash_get_nth_lock(hash_table_t *table, size_t i)
Gets the nth rw_lock in a hash table.
bool hash_lock_has_all_x(const hash_table_t *table)
Verifies that the current thread holds X-latch on all shards.
Definition: hash0hash.cc:42
static void hash_table_clear(hash_table_t *table)
Clears a hash table so that all the cells become empty.
void hash_create_sync_obj(hash_table_t *table, latch_id_t id, size_t n_sync_obj)
Creates a sync object array to protect a hash table.
Definition: hash0hash.cc:103
static size_t hash_get_n_cells(hash_table_t *table)
Returns the number of cells in a hash table.
void hash_unlock_x_all(hash_table_t *table)
Releases all the locks of a hash table, in an ascending order.
Definition: hash0hash.cc:69
The simple hash table utility.
The memory management.
uint64_t find_prime(uint64_t n)
Looks for a prime number slightly greater than the given argument.
Definition: ut0math.cc:35
std::conditional_t< !std::is_array< T >::value, std::unique_ptr< T, detail::Deleter< T > >, std::conditional_t< detail::is_unbounded_array_v< T >, std::unique_ptr< T, detail::Array_deleter< std::remove_extent_t< T > > >, void > > unique_ptr
The following is a common type that is returned by all the ut::make_unique (non-aligned) specializati...
Definition: ut0new.h:2436
Definition: hash0hash.h:60
void * node
hash chain node, NULL if none
Definition: hash0hash.h:61
The info structure stored at the beginning of a heap block.
Definition: mem0mem.h:299
The structure used in the spin lock implementation of a read-write lock.
Definition: sync0rw.h:361
The read-write lock (for threads, not for database transactions)
latch_id_t
Each latch has an ID.
Definition: sync0types.h:339
Version control for database, common definitions, and include files.
#define ut_ad(EXPR)
Debug assertion.
Definition: ut0dbg.h:68
Random numbers and hashing.
int n
Definition: xcom_base.cc:505