Drizzled Public API Documentation
Main Page
Related Pages
Modules
Namespaces
Classes
Files
File List
File Members
hash0hash.h
Go to the documentation of this file.
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
/**************************************************/
26
#pragma once
27
#ifndef hash0hash_h
28
#define hash0hash_h
29
30
#include "univ.i"
31
#include "
mem0mem.h
"
32
#ifndef UNIV_HOTBACKUP
33
# include "
sync0sync.h
"
34
#endif
/* !UNIV_HOTBACKUP */
35
36
typedef
struct
hash_table_struct
hash_table_t
;
37
typedef
struct
hash_cell_struct
hash_cell_t
;
38
39
typedef
void
* hash_node_t;
40
41
/* Fix Bug #13859: symbol collision between imap/mysql */
42
#define hash_create hash0_create
43
44
/*************************************************************/
48
UNIV_INTERN
49
hash_table_t
*
50
hash_create(
51
/*========*/
52
ulint n);
53
#ifndef UNIV_HOTBACKUP
54
/*************************************************************/
56
UNIV_INTERN
57
void
58
hash_create_mutexes_func(
59
/*=====================*/
60
hash_table_t
* table,
61
#ifdef UNIV_SYNC_DEBUG
62
ulint sync_level,
64
#endif
/* UNIV_SYNC_DEBUG */
65
ulint n_mutexes);
66
#ifdef UNIV_SYNC_DEBUG
67
# define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,level,n)
68
#else
/* UNIV_SYNC_DEBUG */
69
# define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,n)
70
#endif
/* UNIV_SYNC_DEBUG */
71
#endif
/* !UNIV_HOTBACKUP */
72
73
/*************************************************************/
75
UNIV_INTERN
76
void
77
hash_table_free(
78
/*============*/
79
hash_table_t
* table);
80
/**************************************************************/
83
UNIV_INLINE
84
ulint
85
hash_calc_hash
(
86
/*===========*/
87
ulint fold,
88
hash_table_t
* table);
89
#ifndef UNIV_HOTBACKUP
90
/********************************************************************/
92
# define HASH_ASSERT_OWNED(TABLE, FOLD) \
93
ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));
94
#else
/* !UNIV_HOTBACKUP */
95
# define HASH_ASSERT_OWNED(TABLE, FOLD)
96
#endif
/* !UNIV_HOTBACKUP */
97
98
/*******************************************************************/
101
#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
102
do {\
103
hash_cell_t* cell3333;\
104
TYPE* struct3333;\
105
\
106
HASH_ASSERT_OWNED(TABLE, FOLD)\
107
\
108
(DATA)->NAME = NULL;\
109
\
110
cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
111
\
112
if (cell3333->node == NULL) {\
113
cell3333->node = DATA;\
114
} else {\
115
struct3333 = (TYPE*) cell3333->node;\
116
\
117
while (struct3333->NAME != NULL) {\
118
\
119
struct3333 = (TYPE*) struct3333->NAME;\
120
}\
121
\
122
struct3333->NAME = DATA;\
123
}\
124
} while (0)
125
126
#ifdef UNIV_HASH_DEBUG
127
# define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1)
128
# define HASH_INVALIDATE(DATA, NAME) DATA->NAME = (void*) -1
129
#else
130
# define HASH_ASSERT_VALID(DATA) do {} while (0)
131
# define HASH_INVALIDATE(DATA, NAME) do {} while (0)
132
#endif
133
134
/*******************************************************************/
137
#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
138
do {\
139
hash_cell_t* cell3333;\
140
TYPE* struct3333;\
141
\
142
HASH_ASSERT_OWNED(TABLE, FOLD)\
143
\
144
cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
145
\
146
if (cell3333->node == DATA) {\
147
HASH_ASSERT_VALID(DATA->NAME);\
148
cell3333->node = DATA->NAME;\
149
} else {\
150
struct3333 = (TYPE*) cell3333->node;\
151
\
152
while (struct3333->NAME != DATA) {\
153
\
154
struct3333 = (TYPE*) struct3333->NAME;\
155
ut_a(struct3333);\
156
}\
157
\
158
struct3333->NAME = DATA->NAME;\
159
}\
160
HASH_INVALIDATE(DATA, NAME);\
161
} while (0)
162
163
/*******************************************************************/
166
#define HASH_GET_FIRST(TABLE, HASH_VAL)\
167
(hash_get_nth_cell(TABLE, HASH_VAL)->node)
168
169
/*******************************************************************/
172
#define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME)
173
174
/********************************************************************/
176
#define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\
177
{\
178
\
179
HASH_ASSERT_OWNED(TABLE, FOLD)\
180
\
181
(DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\
182
HASH_ASSERT_VALID(DATA);\
183
\
184
while ((DATA) != NULL) {\
185
ASSERTION;\
186
if (TEST) {\
187
break;\
188
} else {\
189
HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\
190
(DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\
191
}\
192
}\
193
}
194
195
/********************************************************************/
197
#define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \
198
do { \
199
ulint i3333; \
200
\
201
for (i3333 = (TABLE)->n_cells; i3333--; ) { \
202
(DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \
203
\
204
while ((DATA) != NULL) { \
205
HASH_ASSERT_VALID(DATA); \
206
ASSERTION; \
207
\
208
if (TEST) { \
209
break; \
210
} \
211
\
212
(DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \
213
} \
214
\
215
if ((DATA) != NULL) { \
216
break; \
217
} \
218
} \
219
} while (0)
220
221
/************************************************************/
224
UNIV_INLINE
225
hash_cell_t
*
226
hash_get_nth_cell
(
227
/*==============*/
228
hash_table_t
* table,
229
ulint n);
231
/*************************************************************/
233
UNIV_INLINE
234
void
235
hash_table_clear
(
236
/*=============*/
237
hash_table_t
* table);
239
/*************************************************************/
242
UNIV_INLINE
243
ulint
244
hash_get_n_cells
(
245
/*=============*/
246
hash_table_t
* table);
247
/*******************************************************************/
252
#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\
253
do {\
254
TYPE* node111;\
255
TYPE* top_node111;\
256
hash_cell_t* cell111;\
257
ulint fold111;\
258
\
259
fold111 = (NODE)->fold;\
260
\
261
HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\
262
\
263
top_node111 = (TYPE*)mem_heap_get_top(\
264
hash_get_heap(TABLE, fold111),\
265
sizeof(TYPE));\
266
\
267
/* If the node to remove is not the top node in the heap, compact the\
268
heap of nodes by moving the top node in the place of NODE. */
\
269
\
270
if (NODE != top_node111) {\
271
\
272
/* Copy the top node in place of NODE */
\
273
\
274
*(NODE) = *top_node111;\
275
\
276
cell111 = hash_get_nth_cell(TABLE,\
277
hash_calc_hash(top_node111->fold, TABLE));\
278
\
279
/* Look for the pointer to the top node, to update it */
\
280
\
281
if (cell111->node == top_node111) {\
282
/* The top node is the first in the chain */
\
283
\
284
cell111->node = NODE;\
285
} else {\
286
/* We have to look for the predecessor of the top\
287
node */
\
288
node111 = static_cast<TYPE *>(cell111->node);\
289
\
290
while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\
291
\
292
node111 = static_cast<TYPE *>(HASH_GET_NEXT(NAME, node111));\
293
}\
294
\
295
/* Now we have the predecessor node */
\
296
\
297
node111->NAME = NODE;\
298
}\
299
}\
300
\
301
/* Free the space occupied by the top node */
\
302
\
303
mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\
304
} while (0)
305
306
#ifndef UNIV_HOTBACKUP
307
/****************************************************************/
310
#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
311
do {\
312
ulint i2222;\
313
ulint cell_count2222;\
314
\
315
cell_count2222 = hash_get_n_cells(OLD_TABLE);\
316
\
317
for (i2222 = 0; i2222 < cell_count2222; i2222++) {\
318
NODE_TYPE* node2222 = static_cast<NODE_TYPE *>(HASH_GET_FIRST((OLD_TABLE), i2222));\
319
\
320
while (node2222) {\
321
NODE_TYPE* next2222 = static_cast<NODE_TYPE *>(node2222->PTR_NAME);\
322
ulint fold2222 = FOLD_FUNC(node2222);\
323
\
324
HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\
325
fold2222, node2222);\
326
\
327
node2222 = next2222;\
328
}\
329
}\
330
} while (0)
331
332
/************************************************************/
335
UNIV_INLINE
336
ulint
337
hash_get_mutex_no
(
338
/*==============*/
339
hash_table_t
* table,
340
ulint fold);
341
/************************************************************/
344
UNIV_INLINE
345
mem_heap_t
*
346
hash_get_nth_heap
(
347
/*==============*/
348
hash_table_t
* table,
349
ulint i);
350
/************************************************************/
353
UNIV_INLINE
354
mem_heap_t
*
355
hash_get_heap
(
356
/*==========*/
357
hash_table_t
* table,
358
ulint fold);
359
/************************************************************/
362
UNIV_INLINE
363
mutex_t
*
364
hash_get_nth_mutex
(
365
/*===============*/
366
hash_table_t
* table,
367
ulint i);
368
/************************************************************/
371
UNIV_INLINE
372
mutex_t
*
373
hash_get_mutex
(
374
/*===========*/
375
hash_table_t
* table,
376
ulint fold);
377
/************************************************************/
379
UNIV_INTERN
380
void
381
hash_mutex_enter(
382
/*=============*/
383
hash_table_t
* table,
384
ulint fold);
385
/************************************************************/
387
UNIV_INTERN
388
void
389
hash_mutex_exit(
390
/*============*/
391
hash_table_t
* table,
392
ulint fold);
393
/************************************************************/
395
UNIV_INTERN
396
void
397
hash_mutex_enter_all(
398
/*=================*/
399
hash_table_t
* table);
400
/************************************************************/
402
UNIV_INTERN
403
void
404
hash_mutex_exit_all(
405
/*================*/
406
hash_table_t
* table);
407
#else
/* !UNIV_HOTBACKUP */
408
# define hash_get_heap(table, fold) ((table)->heap)
409
# define hash_mutex_enter(table, fold) ((void) 0)
410
# define hash_mutex_exit(table, fold) ((void) 0)
411
#endif
/* !UNIV_HOTBACKUP */
412
413
struct
hash_cell_struct
{
414
void
*
node
;
415
};
416
417
/* The hash table structure */
418
struct
hash_table_struct
{
419
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
420
# ifndef UNIV_HOTBACKUP
421
ibool adaptive;
/* TRUE if this is the hash table of the
422
adaptive hash index */
423
# endif
/* !UNIV_HOTBACKUP */
424
#endif
/* UNIV_AHI_DEBUG || UNIV_DEBUG */
425
ulint n_cells;
/* number of cells in the hash table */
426
hash_cell_t
*
array
;
427
#ifndef UNIV_HOTBACKUP
428
ulint n_mutexes;
/* if mutexes != NULL, then the number of
429
mutexes, must be a power of 2 */
430
mutex_t
* mutexes;
/* NULL, or an array of mutexes used to
431
protect segments of the hash table */
432
mem_heap_t
**
heaps
;
436
#endif
/* !UNIV_HOTBACKUP */
437
mem_heap_t
* heap;
438
#ifdef UNIV_DEBUG
439
ulint magic_n;
440
# define HASH_TABLE_MAGIC_N 76561114
441
#endif
/* UNIV_DEBUG */
442
};
443
444
#ifndef UNIV_NONINL
445
#include "hash0hash.ic"
446
#endif
447
448
#endif
plugin
innobase
include
hash0hash.h
Generated on Tue Jun 19 2012 18:56:54 for drizzle by
1.8.1