← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/innobase/include/hash0hash.h

Merge Stewart.

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/include/hash0hash.h
1
 
/*****************************************************************************
2
 
 
3
 
Copyright (C) 1997, 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 include/hash0hash.h
21
 
The simple hash table utility
22
 
 
23
 
Created 5/20/1997 Heikki Tuuri
24
 
*******************************************************/
25
 
 
26
 
#ifndef hash0hash_h
27
 
#define hash0hash_h
28
 
 
29
 
#include "univ.i"
30
 
#include "mem0mem.h"
31
 
#ifndef UNIV_HOTBACKUP
32
 
# include "sync0sync.h"
33
 
#endif /* !UNIV_HOTBACKUP */
34
 
 
35
 
typedef struct hash_table_struct hash_table_t;
36
 
typedef struct hash_cell_struct hash_cell_t;
37
 
 
38
 
typedef void*   hash_node_t;
39
 
 
40
 
/* Fix Bug #13859: symbol collision between imap/mysql */
41
 
#define hash_create hash0_create
42
 
 
43
 
/*************************************************************//**
44
 
Creates a hash table with >= n array cells. The actual number
45
 
of cells is chosen to be a prime number slightly bigger than n.
46
 
@return own: created table */
47
 
UNIV_INTERN
48
 
hash_table_t*
49
 
hash_create(
50
 
/*========*/
51
 
        ulint   n);     /*!< in: number of array cells */
52
 
#ifndef UNIV_HOTBACKUP
53
 
/*************************************************************//**
54
 
Creates a mutex array to protect a hash table. */
55
 
UNIV_INTERN
56
 
void
57
 
hash_create_mutexes_func(
58
 
/*=====================*/
59
 
        hash_table_t*   table,          /*!< in: hash table */
60
 
#ifdef UNIV_SYNC_DEBUG
61
 
        ulint           sync_level,     /*!< in: latching order level of the
62
 
                                        mutexes: used in the debug version */
63
 
#endif /* UNIV_SYNC_DEBUG */
64
 
        ulint           n_mutexes);     /*!< in: number of mutexes */
65
 
#ifdef UNIV_SYNC_DEBUG
66
 
# define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,level,n)
67
 
#else /* UNIV_SYNC_DEBUG */
68
 
# define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,n)
69
 
#endif /* UNIV_SYNC_DEBUG */
70
 
#endif /* !UNIV_HOTBACKUP */
71
 
 
72
 
/*************************************************************//**
73
 
Frees a hash table. */
74
 
UNIV_INTERN
75
 
void
76
 
hash_table_free(
77
 
/*============*/
78
 
        hash_table_t*   table); /*!< in, own: hash table */
79
 
/**************************************************************//**
80
 
Calculates the hash value from a folded value.
81
 
@return hashed value */
82
 
UNIV_INLINE
83
 
ulint
84
 
hash_calc_hash(
85
 
/*===========*/
86
 
        ulint           fold,   /*!< in: folded value */
87
 
        hash_table_t*   table); /*!< in: hash table */
88
 
#ifndef UNIV_HOTBACKUP
89
 
/********************************************************************//**
90
 
Assert that the mutex for the table in a hash operation is owned. */
91
 
# define HASH_ASSERT_OWNED(TABLE, FOLD)                                 \
92
 
ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));
93
 
#else /* !UNIV_HOTBACKUP */
94
 
# define HASH_ASSERT_OWNED(TABLE, FOLD)
95
 
#endif /* !UNIV_HOTBACKUP */
96
 
 
97
 
/*******************************************************************//**
98
 
Inserts a struct to a hash table. */
99
 
 
100
 
#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
101
 
do {\
102
 
        hash_cell_t*    cell3333;\
103
 
        TYPE*           struct3333;\
104
 
\
105
 
        HASH_ASSERT_OWNED(TABLE, FOLD)\
106
 
\
107
 
        (DATA)->NAME = NULL;\
108
 
\
109
 
        cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
110
 
\
111
 
        if (cell3333->node == NULL) {\
112
 
                cell3333->node = DATA;\
113
 
        } else {\
114
 
                struct3333 = (TYPE*) cell3333->node;\
115
 
\
116
 
                while (struct3333->NAME != NULL) {\
117
 
\
118
 
                        struct3333 = (TYPE*) struct3333->NAME;\
119
 
                }\
120
 
\
121
 
                struct3333->NAME = DATA;\
122
 
        }\
123
 
} while (0)
124
 
 
125
 
#ifdef UNIV_HASH_DEBUG
126
 
# define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1)
127
 
# define HASH_INVALIDATE(DATA, NAME) DATA->NAME = (void*) -1
128
 
#else
129
 
# define HASH_ASSERT_VALID(DATA) do {} while (0)
130
 
# define HASH_INVALIDATE(DATA, NAME) do {} while (0)
131
 
#endif
132
 
 
133
 
/*******************************************************************//**
134
 
Deletes a struct from a hash table. */
135
 
 
136
 
#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
137
 
do {\
138
 
        hash_cell_t*    cell3333;\
139
 
        TYPE*           struct3333;\
140
 
\
141
 
        HASH_ASSERT_OWNED(TABLE, FOLD)\
142
 
\
143
 
        cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
144
 
\
145
 
        if (cell3333->node == DATA) {\
146
 
                HASH_ASSERT_VALID(DATA->NAME);\
147
 
                cell3333->node = DATA->NAME;\
148
 
        } else {\
149
 
                struct3333 = (TYPE*) cell3333->node;\
150
 
\
151
 
                while (struct3333->NAME != DATA) {\
152
 
\
153
 
                        struct3333 = (TYPE*) struct3333->NAME;\
154
 
                        ut_a(struct3333);\
155
 
                }\
156
 
\
157
 
                struct3333->NAME = DATA->NAME;\
158
 
        }\
159
 
        HASH_INVALIDATE(DATA, NAME);\
160
 
} while (0)
161
 
 
162
 
/*******************************************************************//**
163
 
Gets the first struct in a hash chain, NULL if none. */
164
 
 
165
 
#define HASH_GET_FIRST(TABLE, HASH_VAL)\
166
 
        (hash_get_nth_cell(TABLE, HASH_VAL)->node)
167
 
 
168
 
/*******************************************************************//**
169
 
Gets the next struct in a hash chain, NULL if none. */
170
 
 
171
 
#define HASH_GET_NEXT(NAME, DATA)       ((DATA)->NAME)
172
 
 
173
 
/********************************************************************//**
174
 
Looks for a struct in a hash table. */
175
 
#define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\
176
 
{\
177
 
\
178
 
        HASH_ASSERT_OWNED(TABLE, FOLD)\
179
 
\
180
 
        (DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\
181
 
        HASH_ASSERT_VALID(DATA);\
182
 
\
183
 
        while ((DATA) != NULL) {\
184
 
                ASSERTION;\
185
 
                if (TEST) {\
186
 
                        break;\
187
 
                } else {\
188
 
                        HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\
189
 
                        (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\
190
 
                }\
191
 
        }\
192
 
}
193
 
 
194
 
/********************************************************************//**
195
 
Looks for an item in all hash buckets. */
196
 
#define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST)       \
197
 
do {                                                                    \
198
 
        ulint   i3333;                                                  \
199
 
                                                                        \
200
 
        for (i3333 = (TABLE)->n_cells; i3333--; ) {                     \
201
 
                (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333);           \
202
 
                                                                        \
203
 
                while ((DATA) != NULL) {                                \
204
 
                        HASH_ASSERT_VALID(DATA);                        \
205
 
                        ASSERTION;                                      \
206
 
                                                                        \
207
 
                        if (TEST) {                                     \
208
 
                                break;                                  \
209
 
                        }                                               \
210
 
                                                                        \
211
 
                        (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);      \
212
 
                }                                                       \
213
 
                                                                        \
214
 
                if ((DATA) != NULL) {                                   \
215
 
                        break;                                          \
216
 
                }                                                       \
217
 
        }                                                               \
218
 
} while (0)
219
 
 
220
 
/************************************************************//**
221
 
Gets the nth cell in a hash table.
222
 
@return pointer to cell */
223
 
UNIV_INLINE
224
 
hash_cell_t*
225
 
hash_get_nth_cell(
226
 
/*==============*/
227
 
        hash_table_t*   table,  /*!< in: hash table */
228
 
        ulint           n);     /*!< in: cell index */
229
 
 
230
 
/*************************************************************//**
231
 
Clears a hash table so that all the cells become empty. */
232
 
UNIV_INLINE
233
 
void
234
 
hash_table_clear(
235
 
/*=============*/
236
 
        hash_table_t*   table); /*!< in/out: hash table */
237
 
 
238
 
/*************************************************************//**
239
 
Returns the number of cells in a hash table.
240
 
@return number of cells */
241
 
UNIV_INLINE
242
 
ulint
243
 
hash_get_n_cells(
244
 
/*=============*/
245
 
        hash_table_t*   table); /*!< in: table */
246
 
/*******************************************************************//**
247
 
Deletes a struct which is stored in the heap of the hash table, and compacts
248
 
the heap. The fold value must be stored in the struct NODE in a field named
249
 
'fold'. */
250
 
 
251
 
#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\
252
 
do {\
253
 
        TYPE*           node111;\
254
 
        TYPE*           top_node111;\
255
 
        hash_cell_t*    cell111;\
256
 
        ulint           fold111;\
257
 
\
258
 
        fold111 = (NODE)->fold;\
259
 
\
260
 
        HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\
261
 
\
262
 
        top_node111 = (TYPE*)mem_heap_get_top(\
263
 
                                hash_get_heap(TABLE, fold111),\
264
 
                                                        sizeof(TYPE));\
265
 
\
266
 
        /* If the node to remove is not the top node in the heap, compact the\
267
 
        heap of nodes by moving the top node in the place of NODE. */\
268
 
\
269
 
        if (NODE != top_node111) {\
270
 
\
271
 
                /* Copy the top node in place of NODE */\
272
 
\
273
 
                *(NODE) = *top_node111;\
274
 
\
275
 
                cell111 = hash_get_nth_cell(TABLE,\
276
 
                                hash_calc_hash(top_node111->fold, TABLE));\
277
 
\
278
 
                /* Look for the pointer to the top node, to update it */\
279
 
\
280
 
                if (cell111->node == top_node111) {\
281
 
                        /* The top node is the first in the chain */\
282
 
\
283
 
                        cell111->node = NODE;\
284
 
                } else {\
285
 
                        /* We have to look for the predecessor of the top\
286
 
                        node */\
287
 
                        node111 = static_cast<TYPE *>(cell111->node);\
288
 
\
289
 
                        while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\
290
 
\
291
 
                                node111 = static_cast<TYPE *>(HASH_GET_NEXT(NAME, node111));\
292
 
                        }\
293
 
\
294
 
                        /* Now we have the predecessor node */\
295
 
\
296
 
                        node111->NAME = NODE;\
297
 
                }\
298
 
        }\
299
 
\
300
 
        /* Free the space occupied by the top node */\
301
 
\
302
 
        mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\
303
 
} while (0)
304
 
 
305
 
#ifndef UNIV_HOTBACKUP
306
 
/****************************************************************//**
307
 
Move all hash table entries from OLD_TABLE to NEW_TABLE. */
308
 
 
309
 
#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
310
 
do {\
311
 
        ulint           i2222;\
312
 
        ulint           cell_count2222;\
313
 
\
314
 
        cell_count2222 = hash_get_n_cells(OLD_TABLE);\
315
 
\
316
 
        for (i2222 = 0; i2222 < cell_count2222; i2222++) {\
317
 
                NODE_TYPE*      node2222 = static_cast<NODE_TYPE *>(HASH_GET_FIRST((OLD_TABLE), i2222));\
318
 
\
319
 
                while (node2222) {\
320
 
                        NODE_TYPE*      next2222 = static_cast<NODE_TYPE *>(node2222->PTR_NAME);\
321
 
                        ulint           fold2222 = FOLD_FUNC(node2222);\
322
 
\
323
 
                        HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\
324
 
                                fold2222, node2222);\
325
 
\
326
 
                        node2222 = next2222;\
327
 
                }\
328
 
        }\
329
 
} while (0)
330
 
 
331
 
/************************************************************//**
332
 
Gets the mutex index for a fold value in a hash table.
333
 
@return mutex number */
334
 
UNIV_INLINE
335
 
ulint
336
 
hash_get_mutex_no(
337
 
/*==============*/
338
 
        hash_table_t*   table,  /*!< in: hash table */
339
 
        ulint           fold);  /*!< in: fold */
340
 
/************************************************************//**
341
 
Gets the nth heap in a hash table.
342
 
@return mem heap */
343
 
UNIV_INLINE
344
 
mem_heap_t*
345
 
hash_get_nth_heap(
346
 
/*==============*/
347
 
        hash_table_t*   table,  /*!< in: hash table */
348
 
        ulint           i);     /*!< in: index of the heap */
349
 
/************************************************************//**
350
 
Gets the heap for a fold value in a hash table.
351
 
@return mem heap */
352
 
UNIV_INLINE
353
 
mem_heap_t*
354
 
hash_get_heap(
355
 
/*==========*/
356
 
        hash_table_t*   table,  /*!< in: hash table */
357
 
        ulint           fold);  /*!< in: fold */
358
 
/************************************************************//**
359
 
Gets the nth mutex in a hash table.
360
 
@return mutex */
361
 
UNIV_INLINE
362
 
mutex_t*
363
 
hash_get_nth_mutex(
364
 
/*===============*/
365
 
        hash_table_t*   table,  /*!< in: hash table */
366
 
        ulint           i);     /*!< in: index of the mutex */
367
 
/************************************************************//**
368
 
Gets the mutex for a fold value in a hash table.
369
 
@return mutex */
370
 
UNIV_INLINE
371
 
mutex_t*
372
 
hash_get_mutex(
373
 
/*===========*/
374
 
        hash_table_t*   table,  /*!< in: hash table */
375
 
        ulint           fold);  /*!< in: fold */
376
 
/************************************************************//**
377
 
Reserves the mutex for a fold value in a hash table. */
378
 
UNIV_INTERN
379
 
void
380
 
hash_mutex_enter(
381
 
/*=============*/
382
 
        hash_table_t*   table,  /*!< in: hash table */
383
 
        ulint           fold);  /*!< in: fold */
384
 
/************************************************************//**
385
 
Releases the mutex for a fold value in a hash table. */
386
 
UNIV_INTERN
387
 
void
388
 
hash_mutex_exit(
389
 
/*============*/
390
 
        hash_table_t*   table,  /*!< in: hash table */
391
 
        ulint           fold);  /*!< in: fold */
392
 
/************************************************************//**
393
 
Reserves all the mutexes of a hash table, in an ascending order. */
394
 
UNIV_INTERN
395
 
void
396
 
hash_mutex_enter_all(
397
 
/*=================*/
398
 
        hash_table_t*   table); /*!< in: hash table */
399
 
/************************************************************//**
400
 
Releases all the mutexes of a hash table. */
401
 
UNIV_INTERN
402
 
void
403
 
hash_mutex_exit_all(
404
 
/*================*/
405
 
        hash_table_t*   table); /*!< in: hash table */
406
 
#else /* !UNIV_HOTBACKUP */
407
 
# define hash_get_heap(table, fold)     ((table)->heap)
408
 
# define hash_mutex_enter(table, fold)  ((void) 0)
409
 
# define hash_mutex_exit(table, fold)   ((void) 0)
410
 
#endif /* !UNIV_HOTBACKUP */
411
 
 
412
 
struct hash_cell_struct{
413
 
        void*   node;   /*!< hash chain node, NULL if none */
414
 
};
415
 
 
416
 
/* The hash table structure */
417
 
struct hash_table_struct {
418
 
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
419
 
# ifndef UNIV_HOTBACKUP
420
 
        ibool           adaptive;/* TRUE if this is the hash table of the
421
 
                                adaptive hash index */
422
 
# endif /* !UNIV_HOTBACKUP */
423
 
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
424
 
        ulint           n_cells;/* number of cells in the hash table */
425
 
        hash_cell_t*    array;  /*!< pointer to cell array */
426
 
#ifndef UNIV_HOTBACKUP
427
 
        ulint           n_mutexes;/* if mutexes != NULL, then the number of
428
 
                                mutexes, must be a power of 2 */
429
 
        mutex_t*        mutexes;/* NULL, or an array of mutexes used to
430
 
                                protect segments of the hash table */
431
 
        mem_heap_t**    heaps;  /*!< if this is non-NULL, hash chain nodes for
432
 
                                external chaining can be allocated from these
433
 
                                memory heaps; there are then n_mutexes many of
434
 
                                these heaps */
435
 
#endif /* !UNIV_HOTBACKUP */
436
 
        mem_heap_t*     heap;
437
 
#ifdef UNIV_DEBUG
438
 
        ulint           magic_n;
439
 
# define HASH_TABLE_MAGIC_N     76561114
440
 
#endif /* UNIV_DEBUG */
441
 
};
442
 
 
443
 
#ifndef UNIV_NONINL
444
 
#include "hash0hash.ic"
445
 
#endif
446
 
 
447
 
#endif