drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
hash0hash.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (C) 1997, 2009, Innobase Oy. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
15St, Fifth Floor, Boston, MA 02110-1301 USA
16
17*****************************************************************************/
18
19/**************************************************/
25
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
36typedef struct hash_table_struct hash_table_t;
37typedef struct hash_cell_struct hash_cell_t;
38
39typedef void* hash_node_t;
40
41/* Fix Bug #13859: symbol collision between imap/mysql */
42#define hash_create hash0_create
43
44/*************************************************************/
48UNIV_INTERN
49hash_table_t*
50hash_create(
51/*========*/
52 ulint n);
53#ifndef UNIV_HOTBACKUP
54/*************************************************************/
56UNIV_INTERN
57void
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/*************************************************************/
75UNIV_INTERN
76void
78/*============*/
79 hash_table_t* table);
80/**************************************************************/
83UNIV_INLINE
84ulint
86/*===========*/
87 ulint fold,
88 hash_table_t* table);
89#ifndef UNIV_HOTBACKUP
90/********************************************************************/
92# define HASH_ASSERT_OWNED(TABLE, FOLD) \
93ut_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/*******************************************************************/
100
101#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
102do {\
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/*******************************************************************/
136
137#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
138do {\
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/*******************************************************************/
165
166#define HASH_GET_FIRST(TABLE, HASH_VAL)\
167 (hash_get_nth_cell(TABLE, HASH_VAL)->node)
168
169/*******************************************************************/
171
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) \
198do { \
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/************************************************************/
224UNIV_INLINE
225hash_cell_t*
227/*==============*/
228 hash_table_t* table,
229 ulint n);
230
231/*************************************************************/
233UNIV_INLINE
234void
236/*=============*/
237 hash_table_t* table);
238
239/*************************************************************/
242UNIV_INLINE
243ulint
245/*=============*/
246 hash_table_t* table);
247/*******************************************************************/
251
252#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\
253do {\
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/****************************************************************/
308Move all hash table entries from OLD_TABLE to NEW_TABLE. */
309
310#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
311do {\
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/************************************************************/
335UNIV_INLINE
336ulint
338/*==============*/
339 hash_table_t* table,
340 ulint fold);
341/************************************************************/
344UNIV_INLINE
345mem_heap_t*
347/*==============*/
348 hash_table_t* table,
349 ulint i);
350/************************************************************/
353UNIV_INLINE
354mem_heap_t*
356/*==========*/
357 hash_table_t* table,
358 ulint fold);
359/************************************************************/
362UNIV_INLINE
363mutex_t*
365/*===============*/
366 hash_table_t* table,
367 ulint i);
368/************************************************************/
371UNIV_INLINE
372mutex_t*
374/*===========*/
375 hash_table_t* table,
376 ulint fold);
377/************************************************************/
379UNIV_INTERN
380void
382/*=============*/
383 hash_table_t* table,
384 ulint fold);
385/************************************************************/
387UNIV_INTERN
388void
390/*============*/
391 hash_table_t* table,
392 ulint fold);
393/************************************************************/
395UNIV_INTERN
396void
398/*=================*/
399 hash_table_t* table);
400/************************************************************/
402UNIV_INTERN
403void
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 */
413struct hash_cell_struct{
414 void* node;
415};
417/* The hash table structure */
418struct 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
UNIV_INLINE hash_cell_t * hash_get_nth_cell(hash_table_t *table, ulint n)
UNIV_INLINE mutex_t * hash_get_mutex(hash_table_t *table, ulint fold)
UNIV_INTERN void hash_mutex_exit(hash_table_t *table, ulint fold)
Definition hash0hash.cc:55
UNIV_INLINE mutex_t * hash_get_nth_mutex(hash_table_t *table, ulint i)
UNIV_INTERN void hash_mutex_enter_all(hash_table_t *table)
Definition hash0hash.cc:67
UNIV_INTERN void hash_create_mutexes_func(hash_table_t *table, ulint n_mutexes)
Definition hash0hash.cc:158
UNIV_INTERN void hash_mutex_enter(hash_table_t *table, ulint fold)
Definition hash0hash.cc:43
UNIV_INLINE ulint hash_get_n_cells(hash_table_t *table)
UNIV_INLINE ulint hash_get_mutex_no(hash_table_t *table, ulint fold)
UNIV_INTERN void hash_table_free(hash_table_t *table)
Definition hash0hash.cc:139
UNIV_INLINE mem_heap_t * hash_get_heap(hash_table_t *table, ulint fold)
UNIV_INLINE ulint hash_calc_hash(ulint fold, hash_table_t *table)
UNIV_INLINE void hash_table_clear(hash_table_t *table)
UNIV_INLINE mem_heap_t * hash_get_nth_heap(hash_table_t *table, ulint i)
UNIV_INTERN void hash_mutex_exit_all(hash_table_t *table)
Definition hash0hash.cc:83
mem_heap_t ** heaps
Definition hash0hash.h:430
hash_cell_t * array
Definition hash0hash.h:424
#define mutex_t
Definition sync0types.h:31