← Back to branch summary

~xnox/ubuntu/saucy/drizzle/merge

« back to all changes in this revision

Viewing changes to plugin/innobase/ha/ha0ha.cc

  • Committer: Bazaar Package Importer
  • Author(s): Monty Taylor
  • Date: 2011-01-01 13:55:03 UTC
  • Revision ID: james.westby@ubuntu.com-20110101135503-x2ub1akxoisgwi6z
Tags: 2010.12.06-0ubuntu4
* Fixed missing build depends.
* Added Lee to uploaders.

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/ha/ha0ha.cc
 
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., 51 Franklin
 
15
St, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
*****************************************************************************/
 
18
 
 
19
/********************************************************************//**
 
20
@file ha/ha0ha.c
 
21
The hash table with external chains
 
22
 
 
23
Created 8/22/1994 Heikki Tuuri
 
24
*************************************************************************/
 
25
 
 
26
#include "ha0ha.h"
 
27
#ifdef UNIV_NONINL
 
28
#include "ha0ha.ic"
 
29
#endif
 
30
 
 
31
#ifdef UNIV_DEBUG
 
32
# include "buf0buf.h"
 
33
#endif /* UNIV_DEBUG */
 
34
#include "btr0sea.h"
 
35
#include "page0page.h"
 
36
 
 
37
/*************************************************************//**
 
38
Creates a hash table with at least n array cells.  The actual number
 
39
of cells is chosen to be a prime number slightly bigger than n.
 
40
@return own: created table */
 
41
UNIV_INTERN
 
42
hash_table_t*
 
43
ha_create_func(
 
44
/*===========*/
 
45
        ulint   n,              /*!< in: number of array cells */
 
46
#ifdef UNIV_SYNC_DEBUG
 
47
        ulint   mutex_level,    /*!< in: level of the mutexes in the latching
 
48
                                order: this is used in the debug version */
 
49
#endif /* UNIV_SYNC_DEBUG */
 
50
        ulint   n_mutexes)      /*!< in: number of mutexes to protect the
 
51
                                hash table: must be a power of 2, or 0 */
 
52
{
 
53
        hash_table_t*   table;
 
54
#ifndef UNIV_HOTBACKUP
 
55
        ulint           i;
 
56
#endif /* !UNIV_HOTBACKUP */
 
57
 
 
58
        ut_ad(ut_is_2pow(n_mutexes));
 
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 = static_cast<mem_block_info_t **>(mem_alloc(n_mutexes * sizeof(mem_block_info_t *)));
 
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
        ut_ad(table);
 
103
        ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 
104
#ifdef UNIV_SYNC_DEBUG
 
105
        ut_ad(rw_lock_own(&btr_search_latch, RW_LOCK_EXCLUSIVE));
 
106
#endif /* UNIV_SYNC_DEBUG */
 
107
 
 
108
#ifndef UNIV_HOTBACKUP
 
109
        /* Free the memory heaps. */
 
110
        n = table->n_mutexes;
 
111
 
 
112
        for (i = 0; i < n; i++) {
 
113
                mem_heap_free(table->heaps[i]);
 
114
        }
 
115
#endif /* !UNIV_HOTBACKUP */
 
116
 
 
117
        /* Clear the hash table. */
 
118
        n = hash_get_n_cells(table);
 
119
 
 
120
        for (i = 0; i < n; i++) {
 
121
                hash_get_nth_cell(table, i)->node = NULL;
 
122
        }
 
123
}
 
124
 
 
125
/*************************************************************//**
 
126
Inserts an entry into a hash table. If an entry with the same fold number
 
127
is found, its node is updated to point to the new data, and no new node
 
128
is inserted. If btr_search_enabled is set to FALSE, we will only allow
 
129
updating existing nodes, but no new node is allowed to be added.
 
130
@return TRUE if succeed, FALSE if no more memory could be allocated */
 
131
UNIV_INTERN
 
132
ibool
 
133
ha_insert_for_fold_func(
 
134
/*====================*/
 
135
        hash_table_t*   table,  /*!< in: hash table */
 
136
        ulint           fold,   /*!< in: folded value of data; if a node with
 
137
                                the same fold value already exists, it is
 
138
                                updated to point to the same data, and no new
 
139
                                node is created! */
 
140
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
141
        buf_block_t*    block,  /*!< in: buffer block containing the data */
 
142
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 
143
        void*           data)   /*!< in: data, must not be NULL */
 
144
{
 
145
        hash_cell_t*    cell;
 
146
        ha_node_t*      node;
 
147
        ha_node_t*      prev_node;
 
148
        ulint           hash;
 
149
 
 
150
        ut_ad(data);
 
151
        ut_ad(table);
 
152
        ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 
153
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
154
        ut_a(block->frame == page_align(data));
 
155
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 
156
        ASSERT_HASH_MUTEX_OWN(table, fold);
 
157
 
 
158
        hash = hash_calc_hash(fold, table);
 
159
 
 
160
        cell = hash_get_nth_cell(table, hash);
 
161
 
 
162
        prev_node = static_cast<ha_node_t *>(cell->node);
 
163
 
 
164
        while (prev_node != NULL) {
 
165
                if (prev_node->fold == fold) {
 
166
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
167
# ifndef UNIV_HOTBACKUP
 
168
                        if (table->adaptive) {
 
169
                                buf_block_t* prev_block = prev_node->block;
 
170
                                ut_a(prev_block->frame
 
171
                                     == page_align(prev_node->data));
 
172
                                ut_a(prev_block->n_pointers > 0);
 
173
                                prev_block->n_pointers--;
 
174
                                block->n_pointers++;
 
175
                        }
 
176
                        ut_ad(!btr_search_fully_disabled);
 
177
# endif /* !UNIV_HOTBACKUP */
 
178
 
 
179
                        prev_node->block = block;
 
180
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 
181
                        prev_node->data = data;
 
182
 
 
183
                        return(TRUE);
 
184
                }
 
185
 
 
186
                prev_node = prev_node->next;
 
187
        }
 
188
 
 
189
        /* We are in the process of disabling hash index, do not add
 
190
        new chain node */
 
191
        if (!btr_search_enabled) {
 
192
                ut_ad(!btr_search_fully_disabled);
 
193
                return(TRUE);
 
194
        }
 
195
 
 
196
        /* We have to allocate a new chain node */
 
197
 
 
198
        node = static_cast<ha_node_t *>(mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t)));
 
199
 
 
200
        if (node == NULL) {
 
201
                /* It was a btr search type memory heap and at the moment
 
202
                no more memory could be allocated: return */
 
203
 
 
204
                ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);
 
205
 
 
206
                return(FALSE);
 
207
        }
 
208
 
 
209
        ha_node_set_data(node, block, data);
 
210
 
 
211
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
212
# ifndef UNIV_HOTBACKUP
 
213
        if (table->adaptive) {
 
214
                block->n_pointers++;
 
215
        }
 
216
# endif /* !UNIV_HOTBACKUP */
 
217
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 
218
 
 
219
        node->fold = fold;
 
220
 
 
221
        node->next = NULL;
 
222
 
 
223
        prev_node = static_cast<ha_node_t *>(cell->node);
 
224
 
 
225
        if (prev_node == NULL) {
 
226
 
 
227
                cell->node = node;
 
228
 
 
229
                return(TRUE);
 
230
        }
 
231
 
 
232
        while (prev_node->next != NULL) {
 
233
 
 
234
                prev_node = prev_node->next;
 
235
        }
 
236
 
 
237
        prev_node->next = node;
 
238
 
 
239
        return(TRUE);
 
240
}
 
241
 
 
242
/***********************************************************//**
 
243
Deletes a hash node. */
 
244
UNIV_INTERN
 
245
void
 
246
ha_delete_hash_node(
 
247
/*================*/
 
248
        hash_table_t*   table,          /*!< in: hash table */
 
249
        ha_node_t*      del_node)       /*!< in: node to be deleted */
 
250
{
 
251
        ut_ad(table);
 
252
        ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 
253
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
254
# ifndef UNIV_HOTBACKUP
 
255
        if (table->adaptive) {
 
256
                ut_a(del_node->block->frame = page_align(del_node->data));
 
257
                ut_a(del_node->block->n_pointers > 0);
 
258
                del_node->block->n_pointers--;
 
259
        }
 
260
# endif /* !UNIV_HOTBACKUP */
 
261
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 
262
 
 
263
        HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
 
264
}
 
265
 
 
266
/*********************************************************//**
 
267
Looks for an element when we know the pointer to the data, and updates
 
268
the pointer to data, if found. */
 
269
UNIV_INTERN
 
270
void
 
271
ha_search_and_update_if_found_func(
 
272
/*===============================*/
 
273
        hash_table_t*   table,  /*!< in/out: hash table */
 
274
        ulint           fold,   /*!< in: folded value of the searched data */
 
275
        void*           data,   /*!< in: pointer to the data */
 
276
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
277
        buf_block_t*    new_block,/*!< in: block containing new_data */
 
278
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 
279
        void*           new_data)/*!< in: new pointer to the data */
 
280
{
 
281
        ha_node_t*      node;
 
282
 
 
283
        ut_ad(table);
 
284
        ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 
285
        ASSERT_HASH_MUTEX_OWN(table, fold);
 
286
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
287
        ut_a(new_block->frame == page_align(new_data));
 
288
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 
289
 
 
290
        node = ha_search_with_data(table, fold, data);
 
291
 
 
292
        if (node) {
 
293
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
294
# ifndef UNIV_HOTBACKUP
 
295
                if (table->adaptive) {
 
296
                        ut_a(node->block->n_pointers > 0);
 
297
                        node->block->n_pointers--;
 
298
                        new_block->n_pointers++;
 
299
                }
 
300
# endif /* !UNIV_HOTBACKUP */
 
301
 
 
302
                node->block = new_block;
 
303
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 
304
                node->data = new_data;
 
305
        }
 
306
}
 
307
 
 
308
#ifndef UNIV_HOTBACKUP
 
309
/*****************************************************************//**
 
310
Removes from the chain determined by fold all nodes whose data pointer
 
311
points to the page given. */
 
312
UNIV_INTERN
 
313
void
 
314
ha_remove_all_nodes_to_page(
 
315
/*========================*/
 
316
        hash_table_t*   table,  /*!< in: hash table */
 
317
        ulint           fold,   /*!< in: fold value */
 
318
        const page_t*   page)   /*!< in: buffer page */
 
319
{
 
320
        ha_node_t*      node;
 
321
 
 
322
        ut_ad(table);
 
323
        ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 
324
        ASSERT_HASH_MUTEX_OWN(table, fold);
 
325
 
 
326
        node = ha_chain_get_first(table, fold);
 
327
 
 
328
        while (node) {
 
329
                if (page_align(ha_node_get_data(node)) == page) {
 
330
 
 
331
                        /* Remove the hash node */
 
332
 
 
333
                        ha_delete_hash_node(table, node);
 
334
 
 
335
                        /* Start again from the first node in the chain
 
336
                        because the deletion may compact the heap of
 
337
                        nodes and move other nodes! */
 
338
 
 
339
                        node = ha_chain_get_first(table, fold);
 
340
                } else {
 
341
                        node = ha_chain_get_next(node);
 
342
                }
 
343
        }
 
344
#ifdef UNIV_DEBUG
 
345
        /* Check that all nodes really got deleted */
 
346
 
 
347
        node = ha_chain_get_first(table, fold);
 
348
 
 
349
        while (node) {
 
350
                ut_a(page_align(ha_node_get_data(node)) != page);
 
351
 
 
352
                node = ha_chain_get_next(node);
 
353
        }
 
354
#endif
 
355
}
 
356
 
 
357
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 
358
/*************************************************************//**
 
359
Validates a given range of the cells in hash table.
 
360
@return TRUE if ok */
 
361
UNIV_INTERN
 
362
ibool
 
363
ha_validate(
 
364
/*========*/
 
365
        hash_table_t*   table,          /*!< in: hash table */
 
366
        ulint           start_index,    /*!< in: start index */
 
367
        ulint           end_index)      /*!< in: end index */
 
368
{
 
369
        hash_cell_t*    cell;
 
370
        ha_node_t*      node;
 
371
        ibool           ok      = TRUE;
 
372
        ulint           i;
 
373
 
 
374
        ut_ad(table);
 
375
        ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 
376
        ut_a(start_index <= end_index);
 
377
        ut_a(start_index < hash_get_n_cells(table));
 
378
        ut_a(end_index < hash_get_n_cells(table));
 
379
 
 
380
        for (i = start_index; i <= end_index; i++) {
 
381
 
 
382
                cell = hash_get_nth_cell(table, i);
 
383
 
 
384
                node = cell->node;
 
385
 
 
386
                while (node) {
 
387
                        if (hash_calc_hash(node->fold, table) != i) {
 
388
                                ut_print_timestamp(stderr);
 
389
                                fprintf(stderr,
 
390
                                        "InnoDB: Error: hash table node"
 
391
                                        " fold value %lu does not\n"
 
392
                                        "InnoDB: match the cell number %lu.\n",
 
393
                                        (ulong) node->fold, (ulong) i);
 
394
 
 
395
                                ok = FALSE;
 
396
                        }
 
397
 
 
398
                        node = node->next;
 
399
                }
 
400
        }
 
401
 
 
402
        return(ok);
 
403
}
 
404
#endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */
 
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
        ut_ad(table);
 
416
        ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
 
417
#ifdef UNIV_DEBUG
 
418
/* Some of the code here is disabled for performance reasons in production
 
419
builds, see http://bugs.mysql.com/36941 */
 
420
#define PRINT_USED_CELLS
 
421
#endif /* UNIV_DEBUG */
 
422
 
 
423
#ifdef PRINT_USED_CELLS
 
424
        hash_cell_t*    cell;
 
425
        ulint           cells   = 0;
 
426
        ulint           i;
 
427
#endif /* PRINT_USED_CELLS */
 
428
        ulint           n_bufs;
 
429
 
 
430
#ifdef PRINT_USED_CELLS
 
431
        for (i = 0; i < hash_get_n_cells(table); i++) {
 
432
 
 
433
                cell = hash_get_nth_cell(table, i);
 
434
 
 
435
                if (cell->node) {
 
436
 
 
437
                        cells++;
 
438
                }
 
439
        }
 
440
#endif /* PRINT_USED_CELLS */
 
441
 
 
442
        fprintf(file, "Hash table size %lu",
 
443
                (ulong) hash_get_n_cells(table));
 
444
 
 
445
#ifdef PRINT_USED_CELLS
 
446
        fprintf(file, ", used cells %lu", (ulong) cells);
 
447
#endif /* PRINT_USED_CELLS */
 
448
 
 
449
        if (table->heaps == NULL && table->heap != NULL) {
 
450
 
 
451
                /* This calculation is intended for the adaptive hash
 
452
                index: how many buffer frames we have reserved? */
 
453
 
 
454
                n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;
 
455
 
 
456
                if (table->heap->free_block) {
 
457
                        n_bufs++;
 
458
                }
 
459
 
 
460
                fprintf(file, ", node heap has %lu buffer(s)\n",
 
461
                        (ulong) n_bufs);
 
462
        }
 
463
}
 
464
#endif /* !UNIV_HOTBACKUP */