Drizzled Public API Documentation

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
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
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
227 /*==============*/
228  hash_table_t* table,
229  ulint n);
231 /*************************************************************/
233 UNIV_INLINE
234 void
236 /*=============*/
237  hash_table_t* table);
239 /*************************************************************/
242 UNIV_INLINE
243 ulint
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
338 /*==============*/
339  hash_table_t* table,
340  ulint fold);
341 /************************************************************/
344 UNIV_INLINE
345 mem_heap_t*
347 /*==============*/
348  hash_table_t* table,
349  ulint i);
350 /************************************************************/
353 UNIV_INLINE
354 mem_heap_t*
356 /*==========*/
357  hash_table_t* table,
358  ulint fold);
359 /************************************************************/
362 UNIV_INLINE
363 mutex_t*
365 /*===============*/
366  hash_table_t* table,
367  ulint i);
368 /************************************************************/
371 UNIV_INLINE
372 mutex_t*
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 */
413 struct hash_cell_struct{
414  void* node;
415 };
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