89#define HASH_INSERT(TYPE, NAME, TABLE, HASH_VALUE, DATA) \
91 hash_cell_t *cell3333; \
93 const uint64_t hash_value3333 = HASH_VALUE; \
95 hash_assert_can_modify(TABLE, hash_value3333); \
97 (DATA)->NAME = NULL; \
100 hash_get_nth_cell(TABLE, hash_calc_cell_id(hash_value3333, TABLE)); \
102 if (cell3333->node == NULL) { \
103 cell3333->node = DATA; \
105 struct3333 = (TYPE *)cell3333->node; \
107 while (struct3333->NAME != NULL) { \
108 struct3333 = (TYPE *)struct3333->NAME; \
111 struct3333->NAME = DATA; \
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
119#define HASH_ASSERT_VALID(DATA) \
122#define HASH_INVALIDATE(DATA, NAME) \
129#define HASH_DELETE(TYPE, NAME, TABLE, HASH_VALUE, DATA) \
131 hash_cell_t *cell3333; \
133 const uint64_t hash_value3333 = HASH_VALUE; \
135 hash_assert_can_modify(TABLE, hash_value3333); \
138 hash_get_nth_cell(TABLE, hash_calc_cell_id(hash_value3333, TABLE)); \
140 if (cell3333->node == DATA) { \
141 HASH_ASSERT_VALID(DATA->NAME); \
142 cell3333->node = DATA->NAME; \
144 struct3333 = (TYPE *)cell3333->node; \
146 while (struct3333->NAME != DATA) { \
147 struct3333 = (TYPE *)struct3333->NAME; \
151 struct3333->NAME = DATA->NAME; \
153 HASH_INVALIDATE(DATA, NAME); \
164#define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME)
167#define HASH_SEARCH(NAME, TABLE, HASH_VALUE, TYPE, DATA, ASSERTION, TEST) \
169 const uint64_t hash_value3333 = HASH_VALUE; \
171 hash_assert_can_search(TABLE, hash_value3333); \
174 (TYPE)hash_get_first(TABLE, hash_calc_cell_id(hash_value3333, TABLE)); \
175 HASH_ASSERT_VALID(DATA); \
177 while ((DATA) != NULL) { \
182 HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA)); \
183 (DATA) = (TYPE)HASH_GET_NEXT(NAME, DATA); \
189#define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \
193 for (i3333 = (TABLE)->get_n_cells(); i3333--;) { \
194 (DATA) = (TYPE)hash_get_first(TABLE, i3333); \
196 while ((DATA) != NULL) { \
197 HASH_ASSERT_VALID(DATA); \
204 (DATA) = (TYPE)HASH_GET_NEXT(NAME, DATA); \
207 if ((DATA) != NULL) { \
224#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE) \
228 hash_cell_t *cell111; \
229 uint64_t hash_value111; \
231 hash_value111 = (NODE)->hash_value; \
233 HASH_DELETE(TYPE, NAME, TABLE, hash_value111, NODE); \
236 (TYPE *)mem_heap_get_top(hash_get_heap(TABLE), sizeof(TYPE)); \
241 if (NODE != top_node111) { \
244 *(NODE) = *top_node111; \
246 cell111 = hash_get_nth_cell( \
247 TABLE, hash_calc_cell_id(top_node111->hash_value, TABLE)); \
251 if (cell111->node == top_node111) { \
254 cell111->node = NODE; \
258 node111 = static_cast<TYPE *>(cell111->node); \
260 while (top_node111 != HASH_GET_NEXT(NAME, node111)) { \
261 node111 = static_cast<TYPE *>(HASH_GET_NEXT(NAME, node111)); \
266 node111->NAME = NODE; \
272 mem_heap_free_top(hash_get_heap(TABLE), sizeof(TYPE)); \
275#ifndef UNIV_HOTBACKUP
278#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, HASH_FUNC) \
281 size_t cell_count2222; \
283 cell_count2222 = hash_get_n_cells(OLD_TABLE); \
285 for (i2222 = 0; i2222 < cell_count2222; i2222++) { \
286 NODE_TYPE *node2222 = \
287 static_cast<NODE_TYPE *>(hash_get_first((OLD_TABLE), i2222)); \
290 NODE_TYPE *next2222 = static_cast<NODE_TYPE *>(node2222->PTR_NAME); \
291 uint64_t hash_value2222 = HASH_FUNC(node2222); \
293 HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE), hash_value2222, \
296 node2222 = next2222; \
306 uint64_t hash_value);
324 uint64_t hash_value);
334 uint64_t hash_value);
344 uint64_t hash_value);
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)
379 cells = ut::make_unique<hash_cell_t[]>(prime);
409#ifndef UNIV_HOTBACKUP
426#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
427#ifndef UNIV_HOTBACKUP
454#ifndef UNIV_HOTBACKUP
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.
static PFS_engine_table_share_proxy table
Definition: pfs.cc:60
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:2437
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:301
The structure used in the spin lock implementation of a read-write lock.
Definition: sync0rw.h:362
The read-write lock (for threads, not for database transactions)
latch_id_t
Each latch has an ID.
Definition: sync0types.h:342
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:508