← Back to branch summary

~stewart/haildb/trunk

« back to all changes in this revision

Viewing changes to ha/ha0ha.c

  • Committer: Stewart Smith
  • Date: 2010-04-09 07:57:43 UTC
  • Revision ID: stewart@flamingspork.com-20100409075743-jfh1oml3el1uouvh
Embedded InnoDB 1.0.0 released

2009-04-21      The InnoDB Team

        Embedded InnoDB 1.0.0 released

Show diffs side-by-side

added added

removed removed

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