← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

Moved the last of the libdrizzleclient calls into Protocol.

Show diffs side-by-side

added added

removed removed

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