MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
hash0hash.h
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (c) 1997, 2011, Oracle and/or its affiliates. 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.,
15 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16 
17 *****************************************************************************/
18 
19 /**************************************************/
26 #ifndef hash0hash_h
27 #define hash0hash_h
28 
29 #include "univ.i"
30 #include "mem0mem.h"
31 #ifndef UNIV_HOTBACKUP
32 # include "sync0sync.h"
33 # include "sync0rw.h"
34 #endif /* !UNIV_HOTBACKUP */
35 
36 struct hash_table_t;
37 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 /* Differnt types of hash_table based on the synchronization
45 method used for it. */
46 enum hash_table_sync_t {
47  HASH_TABLE_SYNC_NONE = 0,
50  HASH_TABLE_SYNC_MUTEX,
52  HASH_TABLE_SYNC_RW_LOCK
54 };
55 
56 /*************************************************************/
60 UNIV_INTERN
61 hash_table_t*
62 hash_create(
63 /*========*/
64  ulint n);
65 #ifndef UNIV_HOTBACKUP
66 /*************************************************************/
70 UNIV_INTERN
71 void
72 hash_create_sync_obj_func(
73 /*======================*/
74  hash_table_t* table,
75  enum hash_table_sync_t type,
77 #ifdef UNIV_SYNC_DEBUG
78  ulint sync_level,
81 #endif /* UNIV_SYNC_DEBUG */
82  ulint n_sync_obj);
84 #ifdef UNIV_SYNC_DEBUG
85 # define hash_create_sync_obj(t, s, n, level) \
86  hash_create_sync_obj_func(t, s, level, n)
87 #else /* UNIV_SYNC_DEBUG */
88 # define hash_create_sync_obj(t, s, n, level) \
89  hash_create_sync_obj_func(t, s, n)
90 #endif /* UNIV_SYNC_DEBUG */
91 #endif /* !UNIV_HOTBACKUP */
92 
93 /*************************************************************/
95 UNIV_INTERN
96 void
97 hash_table_free(
98 /*============*/
99  hash_table_t* table);
100 /**************************************************************/
103 UNIV_INLINE
104 ulint
105 hash_calc_hash(
106 /*===========*/
107  ulint fold,
108  hash_table_t* table);
109 #ifndef UNIV_HOTBACKUP
110 /********************************************************************/
112 # define HASH_ASSERT_OWN(TABLE, FOLD) \
113  ut_ad((TABLE)->type != HASH_TABLE_SYNC_MUTEX \
114  || (mutex_own(hash_get_mutex((TABLE), FOLD))));
115 #else /* !UNIV_HOTBACKUP */
116 # define HASH_ASSERT_OWN(TABLE, FOLD)
117 #endif /* !UNIV_HOTBACKUP */
118 
119 /*******************************************************************/
122 #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
123 do {\
124  hash_cell_t* cell3333;\
125  TYPE* struct3333;\
126 \
127  HASH_ASSERT_OWN(TABLE, FOLD)\
128 \
129  (DATA)->NAME = NULL;\
130 \
131  cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
132 \
133  if (cell3333->node == NULL) {\
134  cell3333->node = DATA;\
135  } else {\
136  struct3333 = (TYPE*) cell3333->node;\
137 \
138  while (struct3333->NAME != NULL) {\
139 \
140  struct3333 = (TYPE*) struct3333->NAME;\
141  }\
142 \
143  struct3333->NAME = DATA;\
144  }\
145 } while (0)
146 
147 #ifdef UNIV_HASH_DEBUG
148 # define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1)
149 # define HASH_INVALIDATE(DATA, NAME) *(void**) (&DATA->NAME) = (void*) -1
150 #else
151 # define HASH_ASSERT_VALID(DATA) do {} while (0)
152 # define HASH_INVALIDATE(DATA, NAME) do {} while (0)
153 #endif
154 
155 /*******************************************************************/
158 #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
159 do {\
160  hash_cell_t* cell3333;\
161  TYPE* struct3333;\
162 \
163  HASH_ASSERT_OWN(TABLE, FOLD)\
164 \
165  cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
166 \
167  if (cell3333->node == DATA) {\
168  HASH_ASSERT_VALID(DATA->NAME);\
169  cell3333->node = DATA->NAME;\
170  } else {\
171  struct3333 = (TYPE*) cell3333->node;\
172 \
173  while (struct3333->NAME != DATA) {\
174 \
175  struct3333 = (TYPE*) struct3333->NAME;\
176  ut_a(struct3333);\
177  }\
178 \
179  struct3333->NAME = DATA->NAME;\
180  }\
181  HASH_INVALIDATE(DATA, NAME);\
182 } while (0)
183 
184 /*******************************************************************/
187 #define HASH_GET_FIRST(TABLE, HASH_VAL)\
188  (hash_get_nth_cell(TABLE, HASH_VAL)->node)
189 
190 /*******************************************************************/
193 #define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME)
194 
195 /********************************************************************/
197 #define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\
198 {\
199 \
200  HASH_ASSERT_OWN(TABLE, FOLD)\
201 \
202  (DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\
203  HASH_ASSERT_VALID(DATA);\
204 \
205  while ((DATA) != NULL) {\
206  ASSERTION;\
207  if (TEST) {\
208  break;\
209  } else {\
210  HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\
211  (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\
212  }\
213  }\
214 }
215 
216 /********************************************************************/
218 #define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \
219 do { \
220  ulint i3333; \
221  \
222  for (i3333 = (TABLE)->n_cells; i3333--; ) { \
223  (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \
224  \
225  while ((DATA) != NULL) { \
226  HASH_ASSERT_VALID(DATA); \
227  ASSERTION; \
228  \
229  if (TEST) { \
230  break; \
231  } \
232  \
233  (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \
234  } \
235  \
236  if ((DATA) != NULL) { \
237  break; \
238  } \
239  } \
240 } while (0)
241 
242 /************************************************************/
245 UNIV_INLINE
246 hash_cell_t*
247 hash_get_nth_cell(
248 /*==============*/
249  hash_table_t* table,
250  ulint n);
252 /*************************************************************/
254 UNIV_INLINE
255 void
256 hash_table_clear(
257 /*=============*/
258  hash_table_t* table);
260 /*************************************************************/
263 UNIV_INLINE
264 ulint
265 hash_get_n_cells(
266 /*=============*/
267  hash_table_t* table);
268 /*******************************************************************/
273 #define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\
274 do {\
275  TYPE* node111;\
276  TYPE* top_node111;\
277  hash_cell_t* cell111;\
278  ulint fold111;\
279 \
280  fold111 = (NODE)->fold;\
281 \
282  HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\
283 \
284  top_node111 = (TYPE*) mem_heap_get_top(\
285  hash_get_heap(TABLE, fold111),\
286  sizeof(TYPE));\
287 \
288  /* If the node to remove is not the top node in the heap, compact the\
289  heap of nodes by moving the top node in the place of NODE. */\
290 \
291  if (NODE != top_node111) {\
292 \
293  /* Copy the top node in place of NODE */\
294 \
295  *(NODE) = *top_node111;\
296 \
297  cell111 = hash_get_nth_cell(TABLE,\
298  hash_calc_hash(top_node111->fold, TABLE));\
299 \
300  /* Look for the pointer to the top node, to update it */\
301 \
302  if (cell111->node == top_node111) {\
303  /* The top node is the first in the chain */\
304 \
305  cell111->node = NODE;\
306  } else {\
307  /* We have to look for the predecessor of the top\
308  node */\
309  node111 = static_cast<TYPE*>(cell111->node);\
310 \
311  while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\
312 \
313  node111 = static_cast<TYPE*>(\
314  HASH_GET_NEXT(NAME, node111));\
315  }\
316 \
317  /* Now we have the predecessor node */\
318 \
319  node111->NAME = NODE;\
320  }\
321  }\
322 \
323  /* Free the space occupied by the top node */\
324 \
325  mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\
326 } while (0)
327 
328 #ifndef UNIV_HOTBACKUP
329 /****************************************************************/
332 #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
333 do {\
334  ulint i2222;\
335  ulint cell_count2222;\
336 \
337  cell_count2222 = hash_get_n_cells(OLD_TABLE);\
338 \
339  for (i2222 = 0; i2222 < cell_count2222; i2222++) {\
340  NODE_TYPE* node2222 = HASH_GET_FIRST((OLD_TABLE), i2222);\
341 \
342  while (node2222) {\
343  NODE_TYPE* next2222 = node2222->PTR_NAME;\
344  ulint fold2222 = FOLD_FUNC(node2222);\
345 \
346  HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\
347  fold2222, node2222);\
348 \
349  node2222 = next2222;\
350  }\
351  }\
352 } while (0)
353 
354 /************************************************************/
357 UNIV_INLINE
358 ulint
359 hash_get_sync_obj_index(
360 /*====================*/
361  hash_table_t* table,
362  ulint fold);
363 /************************************************************/
366 UNIV_INLINE
367 mem_heap_t*
368 hash_get_nth_heap(
369 /*==============*/
370  hash_table_t* table,
371  ulint i);
372 /************************************************************/
375 UNIV_INLINE
376 mem_heap_t*
377 hash_get_heap(
378 /*==========*/
379  hash_table_t* table,
380  ulint fold);
381 /************************************************************/
384 UNIV_INLINE
385 ib_mutex_t*
386 hash_get_nth_mutex(
387 /*===============*/
388  hash_table_t* table,
389  ulint i);
390 /************************************************************/
393 UNIV_INLINE
394 rw_lock_t*
395 hash_get_nth_lock(
396 /*==============*/
397  hash_table_t* table,
398  ulint i);
399 /************************************************************/
402 UNIV_INLINE
403 ib_mutex_t*
404 hash_get_mutex(
405 /*===========*/
406  hash_table_t* table,
407  ulint fold);
408 /************************************************************/
411 UNIV_INLINE
412 rw_lock_t*
413 hash_get_lock(
414 /*==========*/
415  hash_table_t* table,
416  ulint fold);
417 /************************************************************/
419 UNIV_INTERN
420 void
421 hash_mutex_enter(
422 /*=============*/
423  hash_table_t* table,
424  ulint fold);
425 /************************************************************/
427 UNIV_INTERN
428 void
429 hash_mutex_exit(
430 /*============*/
431  hash_table_t* table,
432  ulint fold);
433 /************************************************************/
435 UNIV_INTERN
436 void
437 hash_mutex_enter_all(
438 /*=================*/
439  hash_table_t* table);
440 /************************************************************/
442 UNIV_INTERN
443 void
444 hash_mutex_exit_all(
445 /*================*/
446  hash_table_t* table);
447 /************************************************************/
449 UNIV_INTERN
450 void
451 hash_mutex_exit_all_but(
452 /*====================*/
453  hash_table_t* table,
454  ib_mutex_t* keep_mutex);
455 /************************************************************/
457 UNIV_INTERN
458 void
459 hash_lock_s(
460 /*========*/
461  hash_table_t* table,
462  ulint fold);
463 /************************************************************/
465 UNIV_INTERN
466 void
467 hash_lock_x(
468 /*========*/
469  hash_table_t* table,
470  ulint fold);
471 /************************************************************/
473 UNIV_INTERN
474 void
475 hash_unlock_s(
476 /*==========*/
477 
478  hash_table_t* table,
479  ulint fold);
480 /************************************************************/
482 UNIV_INTERN
483 void
484 hash_unlock_x(
485 /*==========*/
486  hash_table_t* table,
487  ulint fold);
488 /************************************************************/
490 UNIV_INTERN
491 void
492 hash_lock_x_all(
493 /*============*/
494  hash_table_t* table);
495 /************************************************************/
497 UNIV_INTERN
498 void
499 hash_unlock_x_all(
500 /*==============*/
501  hash_table_t* table);
502 /************************************************************/
504 UNIV_INTERN
505 void
506 hash_unlock_x_all_but(
507 /*==================*/
508  hash_table_t* table,
509  rw_lock_t* keep_lock);
511 #else /* !UNIV_HOTBACKUP */
512 # define hash_get_heap(table, fold) ((table)->heap)
513 # define hash_mutex_enter(table, fold) ((void) 0)
514 # define hash_mutex_exit(table, fold) ((void) 0)
515 # define hash_mutex_enter_all(table) ((void) 0)
516 # define hash_mutex_exit_all(table) ((void) 0)
517 # define hash_mutex_exit_all_but(t, m) ((void) 0)
518 # define hash_lock_s(t, f) ((void) 0)
519 # define hash_lock_x(t, f) ((void) 0)
520 # define hash_unlock_s(t, f) ((void) 0)
521 # define hash_unlock_x(t, f) ((void) 0)
522 # define hash_lock_x_all(t) ((void) 0)
523 # define hash_unlock_x_all(t) ((void) 0)
524 # define hash_unlock_x_all_but(t, l) ((void) 0)
525 #endif /* !UNIV_HOTBACKUP */
526 
527 struct hash_cell_t{
528  void* node;
529 };
530 
531 /* The hash table structure */
532 struct hash_table_t {
533  enum hash_table_sync_t type; /*<! type of hash_table. */
534 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
535 # ifndef UNIV_HOTBACKUP
536  ibool adaptive;/* TRUE if this is the hash
537  table of the adaptive hash
538  index */
539 # endif /* !UNIV_HOTBACKUP */
540 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
541  ulint n_cells;/* number of cells in the hash table */
542  hash_cell_t* array;
543 #ifndef UNIV_HOTBACKUP
544  ulint n_sync_obj;/* if sync_objs != NULL, then
545  the number of either the number
546  of mutexes or the number of
547  rw_locks depending on the type.
548  Must be a power of 2 */
549  union {
550  ib_mutex_t* mutexes;/* NULL, or an array of mutexes
551  used to protect segments of the
552  hash table */
553  rw_lock_t* rw_locks;/* NULL, or an array of rw_lcoks
554  used to protect segments of the
555  hash table */
556  } sync_obj;
557 
558  mem_heap_t** heaps;
563 #endif /* !UNIV_HOTBACKUP */
564  mem_heap_t* heap;
565 #ifdef UNIV_DEBUG
566  ulint magic_n;
567 # define HASH_TABLE_MAGIC_N 76561114
568 #endif /* UNIV_DEBUG */
569 };
570 
571 #ifndef UNIV_NONINL
572 #include "hash0hash.ic"
573 #endif
574 
575 #endif