1
/************************************************************************
2
The hash table with external chains
4
(c) 1994-1997 Innobase Oy
6
Created 8/22/1994 Heikki Tuuri
7
*************************************************************************/
16
/*****************************************************************
17
Creates a hash table with >= n array cells. The actual number of cells is
18
chosen to be a prime number slightly bigger than n. */
23
/* out, own: created table */
24
ibool in_btr_search, /* in: TRUE if the hash table is used in
25
the btr_search module */
26
ulint n, /* in: number of array cells */
27
#ifdef UNIV_SYNC_DEBUG
28
ulint mutex_level, /* in: level of the mutexes in the latching
29
order: this is used in the debug version */
30
#endif /* UNIV_SYNC_DEBUG */
31
ulint n_mutexes) /* in: number of mutexes to protect the
32
hash table: must be a power of 2, or 0 */
37
table = hash_create(n);
40
table->adaptive = TRUE;
42
table->adaptive = FALSE;
45
/* Creating MEM_HEAP_BTR_SEARCH type heaps can potentially fail,
46
but in practise it never should in this case, hence the asserts. */
50
table->heap = mem_heap_create_in_btr_search(4096);
53
table->heap = mem_heap_create_in_buffer(4096);
59
hash_create_mutexes(table, n_mutexes, mutex_level);
61
table->heaps = mem_alloc(n_mutexes * sizeof(void*));
63
for (i = 0; i < n_mutexes; i++) {
65
table->heaps[i] = mem_heap_create_in_btr_search(4096);
66
ut_a(table->heaps[i]);
68
table->heaps[i] = mem_heap_create_in_buffer(4096);
75
/*****************************************************************
76
Inserts an entry into a hash table. If an entry with the same fold number
77
is found, its node is updated to point to the new data, and no new node
83
/* out: TRUE if succeed, FALSE if no more
84
memory could be allocated */
85
hash_table_t* table, /* in: hash table */
86
ulint fold, /* in: folded value of data; if a node with
87
the same fold value already exists, it is
88
updated to point to the same data, and no new
90
void* data) /* in: data, must not be NULL */
95
buf_block_t* prev_block;
99
ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
101
hash = hash_calc_hash(fold, table);
103
cell = hash_get_nth_cell(table, hash);
105
prev_node = cell->node;
107
while (prev_node != NULL) {
108
if (prev_node->fold == fold) {
109
if (table->adaptive) {
110
prev_block = buf_block_align(prev_node->data);
111
ut_a(prev_block->n_pointers > 0);
112
prev_block->n_pointers--;
113
buf_block_align(data)->n_pointers++;
116
prev_node->data = data;
121
prev_node = prev_node->next;
124
/* We have to allocate a new chain node */
126
node = mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t));
129
/* It was a btr search type memory heap and at the moment
130
no more memory could be allocated: return */
132
ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);
137
ha_node_set_data(node, data);
139
if (table->adaptive) {
140
buf_block_align(data)->n_pointers++;
147
prev_node = cell->node;
149
if (prev_node == NULL) {
156
while (prev_node->next != NULL) {
158
prev_node = prev_node->next;
161
prev_node->next = node;
166
/***************************************************************
167
Deletes a hash node. */
172
hash_table_t* table, /* in: hash table */
173
ha_node_t* del_node) /* in: node to be deleted */
175
if (table->adaptive) {
176
ut_a(buf_block_align(del_node->data)->n_pointers > 0);
177
buf_block_align(del_node->data)->n_pointers--;
180
HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
183
/*****************************************************************
184
Deletes an entry from a hash table. */
189
hash_table_t* table, /* in: hash table */
190
ulint fold, /* in: folded value of data */
191
void* data) /* in: data, must not be NULL and must exist
196
ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
198
node = ha_search_with_data(table, fold, data);
202
ha_delete_hash_node(table, node);
205
/*************************************************************
206
Looks for an element when we know the pointer to the data, and updates
207
the pointer to data, if found. */
210
ha_search_and_update_if_found(
211
/*==========================*/
212
hash_table_t* table, /* in: hash table */
213
ulint fold, /* in: folded value of the searched data */
214
void* data, /* in: pointer to the data */
215
void* new_data)/* in: new pointer to the data */
219
ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
221
node = ha_search_with_data(table, fold, data);
224
if (table->adaptive) {
225
ut_a(buf_block_align(node->data)->n_pointers > 0);
226
buf_block_align(node->data)->n_pointers--;
227
buf_block_align(new_data)->n_pointers++;
230
node->data = new_data;
234
/*********************************************************************
235
Removes from the chain determined by fold all nodes whose data pointer
236
points to the page given. */
239
ha_remove_all_nodes_to_page(
240
/*========================*/
241
hash_table_t* table, /* in: hash table */
242
ulint fold, /* in: fold value */
243
page_t* page) /* in: buffer page */
247
ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
249
node = ha_chain_get_first(table, fold);
252
if (buf_frame_align(ha_node_get_data(node)) == page) {
254
/* Remove the hash node */
256
ha_delete_hash_node(table, node);
258
/* Start again from the first node in the chain
259
because the deletion may compact the heap of
260
nodes and move other nodes! */
262
node = ha_chain_get_first(table, fold);
264
node = ha_chain_get_next(node);
268
/* Check that all nodes really got deleted */
270
node = ha_chain_get_first(table, fold);
273
ut_a(buf_frame_align(ha_node_get_data(node)) != page);
275
node = ha_chain_get_next(node);
280
/*****************************************************************
281
Validates a given range of the cells in hash table. */
286
/* out: TRUE if ok */
287
hash_table_t* table, /* in: hash table */
288
ulint start_index, /* in: start index */
289
ulint end_index) /* in: end index */
296
ut_a(start_index <= end_index);
297
ut_a(start_index < hash_get_n_cells(table));
298
ut_a(end_index < hash_get_n_cells(table));
300
for (i = start_index; i <= end_index; i++) {
302
cell = hash_get_nth_cell(table, i);
307
if (hash_calc_hash(node->fold, table) != i) {
308
ut_print_timestamp(stderr);
310
"InnoDB: Error: hash table node"
311
" fold value %lu does not\n"
312
"InnoDB: match the cell number %lu.\n",
313
(ulong) node->fold, (ulong) i);
325
/*****************************************************************
326
Prints info of a hash table. */
331
FILE* file, /* in: file where to print */
332
hash_table_t* table) /* in: hash table */
339
for (i = 0; i < hash_get_n_cells(table); i++) {
341
cell = hash_get_nth_cell(table, i);
350
"Hash table size %lu, used cells %lu",
351
(ulong) hash_get_n_cells(table), (ulong) cells);
353
if (table->heaps == NULL && table->heap != NULL) {
355
/* This calculation is intended for the adaptive hash
356
index: how many buffer frames we have reserved? */
358
n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;
360
if (table->heap->free_block) {
364
fprintf(file, ", node heap has %lu buffer(s)\n",
added
removed
storage/innobase/ha/ha0ha.c
