← Back to branch summary

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

« back to all changes in this revision

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

  • 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/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
 
 
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
 
 
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
 
 
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
/***********************************************************************
 
105
Deletes a struct from a hash table. */
 
106
 
 
107
#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
 
108
do {\
 
109
        hash_cell_t*    cell3333;\
 
110
        TYPE*           struct3333;\
 
111
\
 
112
        HASH_ASSERT_OWNED(TABLE, FOLD)\
 
113
\
 
114
        cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
 
115
\
 
116
        if (cell3333->node == DATA) {\
 
117
                cell3333->node = DATA->NAME;\
 
118
        } else {\
 
119
                struct3333 = cell3333->node;\
 
120
\
 
121
                while (struct3333->NAME != DATA) {\
 
122
\
 
123
                        struct3333 = struct3333->NAME;\
 
124
                        ut_a(struct3333);\
 
125
                }\
 
126
\
 
127
                struct3333->NAME = DATA->NAME;\
 
128
        }\
 
129
} while (0)
 
130
 
 
131
/***********************************************************************
 
132
Gets the first struct in a hash chain, NULL if none. */
 
133
 
 
134
#define HASH_GET_FIRST(TABLE, HASH_VAL)\
 
135
        (hash_get_nth_cell(TABLE, HASH_VAL)->node)
 
136
 
 
137
/***********************************************************************
 
138
Gets the next struct in a hash chain, NULL if none. */
 
139
 
 
140
#define HASH_GET_NEXT(NAME, DATA)       ((DATA)->NAME)
 
141
 
 
142
/************************************************************************
 
143
Looks for a struct in a hash table. */
 
144
#define HASH_SEARCH(NAME, TABLE, FOLD, DATA, TEST)\
 
145
{\
 
146
\
 
147
        HASH_ASSERT_OWNED(TABLE, FOLD)\
 
148
\
 
149
        (DATA) = HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\
 
150
\
 
151
        while ((DATA) != NULL) {\
 
152
                if (TEST) {\
 
153
                        break;\
 
154
                } else {\
 
155
                        (DATA) = HASH_GET_NEXT(NAME, DATA);\
 
156
                }\
 
157
        }\
 
158
}
 
159
 
 
160
/****************************************************************
 
161
Gets the nth cell in a hash table. */
 
162
UNIV_INLINE
 
163
hash_cell_t*
 
164
hash_get_nth_cell(
 
165
/*==============*/
 
166
                                /* out: pointer to cell */
 
167
        hash_table_t*   table,  /* in: hash table */
 
168
        ulint           n);     /* in: cell index */
 
169
/*****************************************************************
 
170
Returns the number of cells in a hash table. */
 
171
UNIV_INLINE
 
172
ulint
 
173
hash_get_n_cells(
 
174
/*=============*/
 
175
                                /* out: number of cells */
 
176
        hash_table_t*   table); /* in: table */
 
177
/***********************************************************************
 
178
Deletes a struct which is stored in the heap of the hash table, and compacts
 
179
the heap. The fold value must be stored in the struct NODE in a field named
 
180
'fold'. */
 
181
 
 
182
#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\
 
183
do {\
 
184
        TYPE*           node111;\
 
185
        TYPE*           top_node111;\
 
186
        hash_cell_t*    cell111;\
 
187
        ulint           fold111;\
 
188
\
 
189
        fold111 = (NODE)->fold;\
 
190
\
 
191
        HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\
 
192
\
 
193
        top_node111 = (TYPE*)mem_heap_get_top(\
 
194
                                hash_get_heap(TABLE, fold111),\
 
195
                                                        sizeof(TYPE));\
 
196
\
 
197
        /* If the node to remove is not the top node in the heap, compact the\
 
198
        heap of nodes by moving the top node in the place of NODE. */\
 
199
\
 
200
        if (NODE != top_node111) {\
 
201
\
 
202
                /* Copy the top node in place of NODE */\
 
203
\
 
204
                *(NODE) = *top_node111;\
 
205
\
 
206
                cell111 = hash_get_nth_cell(TABLE,\
 
207
                                hash_calc_hash(top_node111->fold, TABLE));\
 
208
\
 
209
                /* Look for the pointer to the top node, to update it */\
 
210
\
 
211
                if (cell111->node == top_node111) {\
 
212
                        /* The top node is the first in the chain */\
 
213
\
 
214
                        cell111->node = NODE;\
 
215
                } else {\
 
216
                        /* We have to look for the predecessor of the top\
 
217
                        node */\
 
218
                        node111 = cell111->node;\
 
219
\
 
220
                        while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\
 
221
\
 
222
                                node111 = HASH_GET_NEXT(NAME, node111);\
 
223
                        }\
 
224
\
 
225
                        /* Now we have the predecessor node */\
 
226
\
 
227
                        node111->NAME = NODE;\
 
228
                }\
 
229
        }\
 
230
\
 
231
        /* Free the space occupied by the top node */\
 
232
\
 
233
        mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\
 
234
} while (0)
 
235
 
 
236
/********************************************************************
 
237
Move all hash table entries from OLD_TABLE to NEW_TABLE.*/
 
238
 
 
239
#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
 
240
do {\
 
241
        ulint           i2222;\
 
242
        ulint           cell_count2222;\
 
243
\
 
244
        cell_count2222 = hash_get_n_cells(OLD_TABLE);\
 
245
\
 
246
        for (i2222 = 0; i2222 < cell_count2222; i2222++) {\
 
247
                NODE_TYPE*      node2222 = HASH_GET_FIRST((OLD_TABLE), i2222);\
 
248
\
 
249
                while (node2222) {\
 
250
                        NODE_TYPE*      next2222 = node2222->PTR_NAME;\
 
251
                        ulint           fold2222 = FOLD_FUNC(node2222);\
 
252
\
 
253
                        HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\
 
254
                                fold2222, node2222);\
 
255
\
 
256
                        node2222 = next2222;\
 
257
                }\
 
258
        }\
 
259
} while (0)
 
260
 
 
261
 
 
262
/****************************************************************
 
263
Gets the mutex index for a fold value in a hash table. */
 
264
UNIV_INLINE
 
265
ulint
 
266
hash_get_mutex_no(
 
267
/*==============*/
 
268
                                /* out: mutex number */
 
269
        hash_table_t*   table,  /* in: hash table */
 
270
        ulint           fold);  /* in: fold */
 
271
/****************************************************************
 
272
Gets the nth heap in a hash table. */
 
273
UNIV_INLINE
 
274
mem_heap_t*
 
275
hash_get_nth_heap(
 
276
/*==============*/
 
277
                                /* out: mem heap */
 
278
        hash_table_t*   table,  /* in: hash table */
 
279
        ulint           i);     /* in: index of the heap */
 
280
/****************************************************************
 
281
Gets the heap for a fold value in a hash table. */
 
282
UNIV_INLINE
 
283
mem_heap_t*
 
284
hash_get_heap(
 
285
/*==========*/
 
286
                                /* out: mem heap */
 
287
        hash_table_t*   table,  /* in: hash table */
 
288
        ulint           fold);  /* in: fold */
 
289
/****************************************************************
 
290
Gets the nth mutex in a hash table. */
 
291
UNIV_INLINE
 
292
mutex_t*
 
293
hash_get_nth_mutex(
 
294
/*===============*/
 
295
                                /* out: mutex */
 
296
        hash_table_t*   table,  /* in: hash table */
 
297
        ulint           i);     /* in: index of the mutex */
 
298
/****************************************************************
 
299
Gets the mutex for a fold value in a hash table. */
 
300
UNIV_INLINE
 
301
mutex_t*
 
302
hash_get_mutex(
 
303
/*===========*/
 
304
                                /* out: mutex */
 
305
        hash_table_t*   table,  /* in: hash table */
 
306
        ulint           fold);  /* in: fold */
 
307
/****************************************************************
 
308
Reserves the mutex for a fold value in a hash table. */
 
309
 
 
310
void
 
311
hash_mutex_enter(
 
312
/*=============*/
 
313
        hash_table_t*   table,  /* in: hash table */
 
314
        ulint           fold);  /* in: fold */
 
315
/****************************************************************
 
316
Releases the mutex for a fold value in a hash table. */
 
317
 
 
318
void
 
319
hash_mutex_exit(
 
320
/*============*/
 
321
        hash_table_t*   table,  /* in: hash table */
 
322
        ulint           fold);  /* in: fold */
 
323
/****************************************************************
 
324
Reserves all the mutexes of a hash table, in an ascending order. */
 
325
 
 
326
void
 
327
hash_mutex_enter_all(
 
328
/*=================*/
 
329
        hash_table_t*   table); /* in: hash table */
 
330
/****************************************************************
 
331
Releases all the mutexes of a hash table. */
 
332
 
 
333
void
 
334
hash_mutex_exit_all(
 
335
/*================*/
 
336
        hash_table_t*   table); /* in: hash table */
 
337
 
 
338
 
 
339
struct hash_cell_struct{
 
340
        void*   node;   /* hash chain node, NULL if none */
 
341
};
 
342
 
 
343
/* The hash table structure */
 
344
struct hash_table_struct {
 
345
        ibool           adaptive;/* TRUE if this is the hash table of the
 
346
                                adaptive hash index */
 
347
        ulint           n_cells;/* number of cells in the hash table */
 
348
        hash_cell_t*    array;  /* pointer to cell array */
 
349
        ulint           n_mutexes;/* if mutexes != NULL, then the number of
 
350
                                mutexes, must be a power of 2 */
 
351
        mutex_t*        mutexes;/* NULL, or an array of mutexes used to
 
352
                                protect segments of the hash table */
 
353
        mem_heap_t**    heaps;  /* if this is non-NULL, hash chain nodes for
 
354
                                external chaining can be allocated from these
 
355
                                memory heaps; there are then n_mutexes many of
 
356
                                these heaps */
 
357
        mem_heap_t*     heap;
 
358
        ulint           magic_n;
 
359
};
 
360
 
 
361
#define HASH_TABLE_MAGIC_N      76561114
 
362
 
 
363
#ifndef UNIV_NONINL
 
364
#include "hash0hash.ic"
 
365
#endif
 
366
 
 
367
#endif