← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: Monty Taylor
  • Date: 2010-12-24 02:13:05 UTC
  • mto: This revision was merged to the branch mainline in revision 2038.
  • Revision ID: mordred@inaugust.com-20101224021305-e3slv1cyjczqorij
Changed the bzrignore file.

Show diffs side-by-side

added added

removed removed

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