← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

Added autoconf tests for location of cstdint and cinttypes. Use those in C++ programs now, so that we don't have to define _STDC_LIMIT_MACROS, etc by hand. Stop, in fact, defining those by hand.

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 */