← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

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
#include "buf0buf.h"
 
15
 
 
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. */
 
19
 
 
20
hash_table_t*
 
21
ha_create_func(
 
22
/*===========*/
 
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 */
 
33
{
 
34
        hash_table_t*   table;
 
35
        ulint           i;
 
36
 
 
37
        table = hash_create(n);
 
38
 
 
39
        if (in_btr_search) {
 
40
                table->adaptive = TRUE;
 
41
        } else {
 
42
                table->adaptive = FALSE;
 
43
        }
 
44
 
 
45
        /* Creating MEM_HEAP_BTR_SEARCH type heaps can potentially fail,
 
46
        but in practise it never should in this case, hence the asserts. */
 
47
 
 
48
        if (n_mutexes == 0) {
 
49
                if (in_btr_search) {
 
50
                        table->heap = mem_heap_create_in_btr_search(4096);
 
51
                        ut_a(table->heap);
 
52
                } else {
 
53
                        table->heap = mem_heap_create_in_buffer(4096);
 
54
                }
 
55
 
 
56
                return(table);
 
57
        }
 
58
 
 
59
        hash_create_mutexes(table, n_mutexes, mutex_level);
 
60
 
 
61
        table->heaps = mem_alloc(n_mutexes * sizeof(void*));
 
62
 
 
63
        for (i = 0; i < n_mutexes; i++) {
 
64
                if (in_btr_search) {
 
65
                        table->heaps[i] = mem_heap_create_in_btr_search(4096);
 
66
                        ut_a(table->heaps[i]);
 
67
                } else {
 
68
                        table->heaps[i] = mem_heap_create_in_buffer(4096);
 
69
                }
 
70
        }
 
71
 
 
72
        return(table);
 
73
}
 
74
 
 
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
 
78
is inserted. */
 
79
 
 
80
ibool
 
81
ha_insert_for_fold(
 
82
/*===============*/
 
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
 
89
                                node is created! */
 
90
        void*           data)   /* in: data, must not be NULL */
 
91
{
 
92
        hash_cell_t*    cell;
 
93
        ha_node_t*      node;
 
94
        ha_node_t*      prev_node;
 
95
        buf_block_t*    prev_block;
 
96
        ulint           hash;
 
97
 
 
98
        ut_ad(table && data);
 
99
        ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
 
100
 
 
101
        hash = hash_calc_hash(fold, table);
 
102
 
 
103
        cell = hash_get_nth_cell(table, hash);
 
104
 
 
105
        prev_node = cell->node;
 
106
 
 
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++;
 
114
                        }
 
115
 
 
116
                        prev_node->data = data;
 
117
 
 
118
                        return(TRUE);
 
119
                }
 
120
 
 
121
                prev_node = prev_node->next;
 
122
        }
 
123
 
 
124
        /* We have to allocate a new chain node */
 
125
 
 
126
        node = mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t));
 
127
 
 
128
        if (node == NULL) {
 
129
                /* It was a btr search type memory heap and at the moment
 
130
                no more memory could be allocated: return */
 
131
 
 
132
                ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);
 
133
 
 
134
                return(FALSE);
 
135
        }
 
136
 
 
137
        ha_node_set_data(node, data);
 
138
 
 
139
        if (table->adaptive) {
 
140
                buf_block_align(data)->n_pointers++;
 
141
        }
 
142
 
 
143
        node->fold = fold;
 
144
 
 
145
        node->next = NULL;
 
146
 
 
147
        prev_node = cell->node;
 
148
 
 
149
        if (prev_node == NULL) {
 
150
 
 
151
                cell->node = node;
 
152
 
 
153
                return(TRUE);
 
154
        }
 
155
 
 
156
        while (prev_node->next != NULL) {
 
157
 
 
158
                prev_node = prev_node->next;
 
159
        }
 
160
 
 
161
        prev_node->next = node;
 
162
 
 
163
        return(TRUE);
 
164
}
 
165
 
 
166
/***************************************************************
 
167
Deletes a hash node. */
 
168
 
 
169
void
 
170
ha_delete_hash_node(
 
171
/*================*/
 
172
        hash_table_t*   table,          /* in: hash table */
 
173
        ha_node_t*      del_node)       /* in: node to be deleted */
 
174
{
 
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--;
 
178
        }
 
179
 
 
180
        HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
 
181
}
 
182
 
 
183
/*****************************************************************
 
184
Deletes an entry from a hash table. */
 
185
 
 
186
void
 
187
ha_delete(
 
188
/*======*/
 
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
 
192
                                in the hash table */
 
193
{
 
194
        ha_node_t*      node;
 
195
 
 
196
        ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
 
197
 
 
198
        node = ha_search_with_data(table, fold, data);
 
199
 
 
200
        ut_a(node);
 
201
 
 
202
        ha_delete_hash_node(table, node);
 
203
}
 
204
 
 
205
/*************************************************************
 
206
Looks for an element when we know the pointer to the data, and updates
 
207
the pointer to data, if found. */
 
208
 
 
209
void
 
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 */
 
216
{
 
217
        ha_node_t*      node;
 
218
 
 
219
        ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
 
220
 
 
221
        node = ha_search_with_data(table, fold, data);
 
222
 
 
223
        if (node) {
 
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++;
 
228
                }
 
229
 
 
230
                node->data = new_data;
 
231
        }
 
232
}
 
233
 
 
234
/*********************************************************************
 
235
Removes from the chain determined by fold all nodes whose data pointer
 
236
points to the page given. */
 
237
 
 
238
void
 
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 */
 
244
{
 
245
        ha_node_t*      node;
 
246
 
 
247
        ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
 
248
 
 
249
        node = ha_chain_get_first(table, fold);
 
250
 
 
251
        while (node) {
 
252
                if (buf_frame_align(ha_node_get_data(node)) == page) {
 
253
 
 
254
                        /* Remove the hash node */
 
255
 
 
256
                        ha_delete_hash_node(table, node);
 
257
 
 
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! */
 
261
 
 
262
                        node = ha_chain_get_first(table, fold);
 
263
                } else {
 
264
                        node = ha_chain_get_next(node);
 
265
                }
 
266
        }
 
267
#ifdef UNIV_DEBUG
 
268
        /* Check that all nodes really got deleted */
 
269
 
 
270
        node = ha_chain_get_first(table, fold);
 
271
 
 
272
        while (node) {
 
273
                ut_a(buf_frame_align(ha_node_get_data(node)) != page);
 
274
 
 
275
                node = ha_chain_get_next(node);
 
276
        }
 
277
#endif
 
278
}
 
279
 
 
280
/*****************************************************************
 
281
Validates a given range of the cells in hash table. */
 
282
 
 
283
ibool
 
284
ha_validate(
 
285
/*========*/
 
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 */
 
290
{
 
291
        hash_cell_t*    cell;
 
292
        ha_node_t*      node;
 
293
        ibool           ok      = TRUE;
 
294
        ulint           i;
 
295
 
 
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));
 
299
 
 
300
        for (i = start_index; i <= end_index; i++) {
 
301
 
 
302
                cell = hash_get_nth_cell(table, i);
 
303
 
 
304
                node = cell->node;
 
305
 
 
306
                while (node) {
 
307
                        if (hash_calc_hash(node->fold, table) != i) {
 
308
                                ut_print_timestamp(stderr);
 
309
                                fprintf(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);
 
314
 
 
315
                                ok = FALSE;
 
316
                        }
 
317
 
 
318
                        node = node->next;
 
319
                }
 
320
        }
 
321
 
 
322
        return(ok);
 
323
}
 
324
 
 
325
/*****************************************************************
 
326
Prints info of a hash table. */
 
327
 
 
328
void
 
329
ha_print_info(
 
330
/*==========*/
 
331
        FILE*           file,   /* in: file where to print */
 
332
        hash_table_t*   table)  /* in: hash table */
 
333
{
 
334
#ifdef UNIV_DEBUG
 
335
/* Some of the code here is disabled for performance reasons in production
 
336
builds, see http://bugs.mysql.com/36941 */
 
337
#define PRINT_USED_CELLS
 
338
#endif /* UNIV_DEBUG */
 
339
 
 
340
#ifdef PRINT_USED_CELLS
 
341
        hash_cell_t*    cell;
 
342
        ulint           cells   = 0;
 
343
        ulint           i;
 
344
#endif /* PRINT_USED_CELLS */
 
345
        ulint           n_bufs;
 
346
 
 
347
#ifdef PRINT_USED_CELLS
 
348
        for (i = 0; i < hash_get_n_cells(table); i++) {
 
349
 
 
350
                cell = hash_get_nth_cell(table, i);
 
351
 
 
352
                if (cell->node) {
 
353
 
 
354
                        cells++;
 
355
                }
 
356
        }
 
357
#endif /* PRINT_USED_CELLS */
 
358
 
 
359
        fprintf(file, "Hash table size %lu",
 
360
                (ulong) hash_get_n_cells(table));
 
361
 
 
362
#ifdef PRINT_USED_CELLS
 
363
        fprintf(file, ", used cells %lu", (ulong) cells);
 
364
#endif /* PRINT_USED_CELLS */
 
365
 
 
366
        if (table->heaps == NULL && table->heap != NULL) {
 
367
 
 
368
                /* This calculation is intended for the adaptive hash
 
369
                index: how many buffer frames we have reserved? */
 
370
 
 
371
                n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;
 
372
 
 
373
                if (table->heap->free_block) {
 
374
                        n_bufs++;
 
375
                }
 
376
 
 
377
                fprintf(file, ", node heap has %lu buffer(s)\n",
 
378
                        (ulong) n_bufs);
 
379
        }
 
380
}