← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/innobase/ha/ha0ha.c

  • Committer: Monty Taylor
  • Date: 2008-09-05 22:55:50 UTC
  • mfrom: (373.1.9 stl-client-progs)
  • Revision ID: monty@inaugust.com-20080905225550-zco374c9s7kxwqyb
Merged removal of DYNAMIC_STRING.

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/innobase/ha/ha0ha.c
1
 
/************************************************************************
2
 
The hash table with external chains
3
 
 
4
 
(c) 1994-1997 Innobase Oy
5
 
 
6
 
Created 8/22/1994 Heikki Tuuri
7
 
*************************************************************************/
8
 
 
9
 
#include "ha0ha.h"
10
 
#ifdef UNIV_NONINL
11
 
#include "ha0ha.ic"
12
 
#endif
13
 
 
14
 
#ifdef UNIV_DEBUG
15
 
# include "buf0buf.h"
16
 
#endif /* UNIV_DEBUG */
17
 
#ifdef UNIV_SYNC_DEBUG
18
 
# include "btr0sea.h"
19
 
#endif /* UNIV_SYNC_DEBUG */
20
 
#include "page0page.h"
21
 
 
22
 
/*****************************************************************
23
 
Creates a hash table with >= n array cells. The actual number of cells is
24
 
chosen to be a prime number slightly bigger than n. */
25
 
UNIV_INTERN
26
 
hash_table_t*
27
 
ha_create_func(
28
 
/*===========*/
29
 
                                /* out, own: created table */
30
 
        ulint   n,              /* in: number of array cells */
31
 
#ifdef UNIV_SYNC_DEBUG
32
 
        ulint   mutex_level,    /* in: level of the mutexes in the latching
33
 
                                order: this is used in the debug version */
34
 
#endif /* UNIV_SYNC_DEBUG */
35
 
        ulint   n_mutexes)      /* in: number of mutexes to protect the
36
 
                                hash table: must be a power of 2, or 0 */
37
 
{
38
 
        hash_table_t*   table;
39
 
        ulint           i;
40
 
 
41
 
        table = hash_create(n);
42
 
 
43
 
#ifdef UNIV_DEBUG
44
 
        table->adaptive = TRUE;
45
 
#endif /* UNIV_DEBUG */
46
 
        /* Creating MEM_HEAP_BTR_SEARCH type heaps can potentially fail,
47
 
        but in practise it never should in this case, hence the asserts. */
48
 
 
49
 
        if (n_mutexes == 0) {
50
 
                table->heap = mem_heap_create_in_btr_search(
51
 
                        ut_min(4096, MEM_MAX_ALLOC_IN_BUF));
52
 
                ut_a(table->heap);
53
 
 
54
 
                return(table);
55
 
        }
56
 
 
57
 
        hash_create_mutexes(table, n_mutexes, mutex_level);
58
 
 
59
 
        table->heaps = mem_alloc(n_mutexes * sizeof(void*));
60
 
 
61
 
        for (i = 0; i < n_mutexes; i++) {
62
 
                table->heaps[i] = mem_heap_create_in_btr_search(4096);
63
 
                ut_a(table->heaps[i]);
64
 
        }
65
 
 
66
 
        return(table);
67
 
}
68
 
 
69
 
/*****************************************************************
70
 
Empties a hash table and frees the memory heaps. */
71
 
UNIV_INTERN
72
 
void
73
 
ha_clear(
74
 
/*=====*/
75
 
        hash_table_t*   table)  /* in, own: hash table */
76
 
{
77
 
        ulint   i;
78
 
        ulint   n;
79
 
 
80
 
#ifdef UNIV_SYNC_DEBUG
81
 
        ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EXCLUSIVE));
82
 
#endif /* UNIV_SYNC_DEBUG */
83
 
 
84
 
        /* Free the memory heaps. */
85
 
        n = table->n_mutexes;
86
 
 
87
 
        for (i = 0; i < n; i++) {
88
 
                mem_heap_free(table->heaps[i]);
89
 
        }
90
 
 
91
 
        /* Clear the hash table. */
92
 
        n = hash_get_n_cells(table);
93
 
 
94
 
        for (i = 0; i < n; i++) {
95
 
                hash_get_nth_cell(table, i)->node = NULL;
96
 
        }
97
 
}
98
 
 
99
 
/*****************************************************************
100
 
Inserts an entry into a hash table. If an entry with the same fold number
101
 
is found, its node is updated to point to the new data, and no new node
102
 
is inserted. */
103
 
UNIV_INTERN
104
 
ibool
105
 
ha_insert_for_fold_func(
106
 
/*====================*/
107
 
                                /* out: TRUE if succeed, FALSE if no more
108
 
                                memory could be allocated */
109
 
        hash_table_t*   table,  /* in: hash table */
110
 
        ulint           fold,   /* in: folded value of data; if a node with
111
 
                                the same fold value already exists, it is
112
 
                                updated to point to the same data, and no new
113
 
                                node is created! */
114
 
#ifdef UNIV_DEBUG
115
 
        buf_block_t*    block,  /* in: buffer block containing the data */
116
 
#endif /* UNIV_DEBUG */
117
 
        void*           data)   /* in: data, must not be NULL */
118
 
{
119
 
        hash_cell_t*    cell;
120
 
        ha_node_t*      node;
121
 
        ha_node_t*      prev_node;
122
 
        ulint           hash;
123
 
 
124
 
        ut_ad(table && data);
125
 
        ut_ad(block->frame == page_align(data));
126
 
        ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
127
 
 
128
 
        hash = hash_calc_hash(fold, table);
129
 
 
130
 
        cell = hash_get_nth_cell(table, hash);
131
 
 
132
 
        prev_node = cell->node;
133
 
 
134
 
        while (prev_node != NULL) {
135
 
                if (prev_node->fold == fold) {
136
 
#ifdef UNIV_DEBUG
137
 
                        if (table->adaptive) {
138
 
                                buf_block_t* prev_block = prev_node->block;
139
 
                                ut_a(prev_block->frame
140
 
                                     == page_align(prev_node->data));
141
 
                                ut_a(prev_block->n_pointers > 0);
142
 
                                prev_block->n_pointers--;
143
 
                                block->n_pointers++;
144
 
                        }
145
 
 
146
 
                        prev_node->block = block;
147
 
#endif /* UNIV_DEBUG */
148
 
                        prev_node->data = data;
149
 
 
150
 
                        return(TRUE);
151
 
                }
152
 
 
153
 
                prev_node = prev_node->next;
154
 
        }
155
 
 
156
 
        /* We have to allocate a new chain node */
157
 
 
158
 
        node = mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t));
159
 
 
160
 
        if (node == NULL) {
161
 
                /* It was a btr search type memory heap and at the moment
162
 
                no more memory could be allocated: return */
163
 
 
164
 
                ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);
165
 
 
166
 
                return(FALSE);
167
 
        }
168
 
 
169
 
        ha_node_set_data(node, block, data);
170
 
 
171
 
#ifdef UNIV_DEBUG
172
 
        if (table->adaptive) {
173
 
                block->n_pointers++;
174
 
        }
175
 
#endif /* UNIV_DEBUG */
176
 
        node->fold = fold;
177
 
 
178
 
        node->next = NULL;
179
 
 
180
 
        prev_node = cell->node;
181
 
 
182
 
        if (prev_node == NULL) {
183
 
 
184
 
                cell->node = node;
185
 
 
186
 
                return(TRUE);
187
 
        }
188
 
 
189
 
        while (prev_node->next != NULL) {
190
 
 
191
 
                prev_node = prev_node->next;
192
 
        }
193
 
 
194
 
        prev_node->next = node;
195
 
 
196
 
        return(TRUE);
197
 
}
198
 
 
199
 
/***************************************************************
200
 
Deletes a hash node. */
201
 
UNIV_INTERN
202
 
void
203
 
ha_delete_hash_node(
204
 
/*================*/
205
 
        hash_table_t*   table,          /* in: hash table */
206
 
        ha_node_t*      del_node)       /* in: node to be deleted */
207
 
{
208
 
#ifdef UNIV_DEBUG
209
 
        if (table->adaptive) {
210
 
                ut_a(del_node->block->frame = page_align(del_node->data));
211
 
                ut_a(del_node->block->n_pointers > 0);
212
 
                del_node->block->n_pointers--;
213
 
        }
214
 
#endif /* UNIV_DEBUG */
215
 
        HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
216
 
}
217
 
 
218
 
/*****************************************************************
219
 
Deletes an entry from a hash table. */
220
 
UNIV_INTERN
221
 
void
222
 
ha_delete(
223
 
/*======*/
224
 
        hash_table_t*   table,  /* in: hash table */
225
 
        ulint           fold,   /* in: folded value of data */
226
 
        void*           data)   /* in: data, must not be NULL and must exist
227
 
                                in the hash table */
228
 
{
229
 
        ha_node_t*      node;
230
 
 
231
 
        ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
232
 
 
233
 
        node = ha_search_with_data(table, fold, data);
234
 
 
235
 
        ut_a(node);
236
 
 
237
 
        ha_delete_hash_node(table, node);
238
 
}
239
 
 
240
 
/*************************************************************
241
 
Looks for an element when we know the pointer to the data, and updates
242
 
the pointer to data, if found. */
243
 
UNIV_INTERN
244
 
void
245
 
ha_search_and_update_if_found_func(
246
 
/*===============================*/
247
 
        hash_table_t*   table,  /* in: hash table */
248
 
        ulint           fold,   /* in: folded value of the searched data */
249
 
        void*           data,   /* in: pointer to the data */
250
 
#ifdef UNIV_DEBUG
251
 
        buf_block_t*    new_block,/* in: block containing new_data */
252
 
#endif
253
 
        void*           new_data)/* in: new pointer to the data */
254
 
{
255
 
        ha_node_t*      node;
256
 
 
257
 
        ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
258
 
        ut_ad(new_block->frame == page_align(new_data));
259
 
 
260
 
        node = ha_search_with_data(table, fold, data);
261
 
 
262
 
        if (node) {
263
 
#ifdef UNIV_DEBUG
264
 
                if (table->adaptive) {
265
 
                        ut_a(node->block->n_pointers > 0);
266
 
                        node->block->n_pointers--;
267
 
                        new_block->n_pointers++;
268
 
                }
269
 
 
270
 
                node->block = new_block;
271
 
#endif /* UNIV_DEBUG */
272
 
                node->data = new_data;
273
 
        }
274
 
}
275
 
 
276
 
/*********************************************************************
277
 
Removes from the chain determined by fold all nodes whose data pointer
278
 
points to the page given. */
279
 
UNIV_INTERN
280
 
void
281
 
ha_remove_all_nodes_to_page(
282
 
/*========================*/
283
 
        hash_table_t*   table,  /* in: hash table */
284
 
        ulint           fold,   /* in: fold value */
285
 
        const page_t*   page)   /* in: buffer page */
286
 
{
287
 
        ha_node_t*      node;
288
 
 
289
 
        ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
290
 
 
291
 
        node = ha_chain_get_first(table, fold);
292
 
 
293
 
        while (node) {
294
 
                if (page_align(ha_node_get_data(node)) == page) {
295
 
 
296
 
                        /* Remove the hash node */
297
 
 
298
 
                        ha_delete_hash_node(table, node);
299
 
 
300
 
                        /* Start again from the first node in the chain
301
 
                        because the deletion may compact the heap of
302
 
                        nodes and move other nodes! */
303
 
 
304
 
                        node = ha_chain_get_first(table, fold);
305
 
                } else {
306
 
                        node = ha_chain_get_next(node);
307
 
                }
308
 
        }
309
 
#ifdef UNIV_DEBUG
310
 
        /* Check that all nodes really got deleted */
311
 
 
312
 
        node = ha_chain_get_first(table, fold);
313
 
 
314
 
        while (node) {
315
 
                ut_a(page_align(ha_node_get_data(node)) != page);
316
 
 
317
 
                node = ha_chain_get_next(node);
318
 
        }
319
 
#endif
320
 
}
321
 
 
322
 
/*****************************************************************
323
 
Validates a given range of the cells in hash table. */
324
 
UNIV_INTERN
325
 
ibool
326
 
ha_validate(
327
 
/*========*/
328
 
                                        /* out: TRUE if ok */
329
 
        hash_table_t*   table,          /* in: hash table */
330
 
        ulint           start_index,    /* in: start index */
331
 
        ulint           end_index)      /* in: end index */
332
 
{
333
 
        hash_cell_t*    cell;
334
 
        ha_node_t*      node;
335
 
        ibool           ok      = TRUE;
336
 
        ulint           i;
337
 
 
338
 
        ut_a(start_index <= end_index);
339
 
        ut_a(start_index < hash_get_n_cells(table));
340
 
        ut_a(end_index < hash_get_n_cells(table));
341
 
 
342
 
        for (i = start_index; i <= end_index; i++) {
343
 
 
344
 
                cell = hash_get_nth_cell(table, i);
345
 
 
346
 
                node = cell->node;
347
 
 
348
 
                while (node) {
349
 
                        if (hash_calc_hash(node->fold, table) != i) {
350
 
                                ut_print_timestamp(stderr);
351
 
                                fprintf(stderr,
352
 
                                        "InnoDB: Error: hash table node"
353
 
                                        " fold value %lu does not\n"
354
 
                                        "InnoDB: match the cell number %lu.\n",
355
 
                                        (ulong) node->fold, (ulong) i);
356
 
 
357
 
                                ok = FALSE;
358
 
                        }
359
 
 
360
 
                        node = node->next;
361
 
                }
362
 
        }
363
 
 
364
 
        return(ok);
365
 
}
366
 
 
367
 
/*****************************************************************
368
 
Prints info of a hash table. */
369
 
UNIV_INTERN
370
 
void
371
 
ha_print_info(
372
 
/*==========*/
373
 
        FILE*           file,   /* in: file where to print */
374
 
        hash_table_t*   table)  /* in: hash table */
375
 
{
376
 
#ifdef UNIV_DEBUG
377
 
/* Some of the code here is disabled for performance reasons in production
378
 
builds, see http://bugs.mysql.com/36941 */
379
 
#define PRINT_USED_CELLS
380
 
#endif /* UNIV_DEBUG */
381
 
 
382
 
#ifdef PRINT_USED_CELLS
383
 
        hash_cell_t*    cell;
384
 
        ulint           cells   = 0;
385
 
        ulint           i;
386
 
#endif /* PRINT_USED_CELLS */
387
 
        ulint           n_bufs;
388
 
 
389
 
#ifdef PRINT_USED_CELLS
390
 
        for (i = 0; i < hash_get_n_cells(table); i++) {
391
 
 
392
 
                cell = hash_get_nth_cell(table, i);
393
 
 
394
 
                if (cell->node) {
395
 
 
396
 
                        cells++;
397
 
                }
398
 
        }
399
 
#endif /* PRINT_USED_CELLS */
400
 
 
401
 
        fprintf(file, "Hash table size %lu",
402
 
                (ulong) hash_get_n_cells(table));
403
 
 
404
 
#ifdef PRINT_USED_CELLS
405
 
        fprintf(file, ", used cells %lu", (ulong) cells);
406
 
#endif /* PRINT_USED_CELLS */
407
 
 
408
 
        if (table->heaps == NULL && table->heap != NULL) {
409
 
 
410
 
                /* This calculation is intended for the adaptive hash
411
 
                index: how many buffer frames we have reserved? */
412
 
 
413
 
                n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;
414
 
 
415
 
                if (table->heap->free_block) {
416
 
                        n_bufs++;
417
 
                }
418
 
 
419
 
                fprintf(file, ", node heap has %lu buffer(s)\n",
420
 
                        (ulong) n_bufs);
421
 
        }
422
 
}