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 6 it under the terms of the GNU General Public License, version 2.0, 7 as published by the Free Software Foundation. 8 9 This program is also distributed with certain software (including 10 but not limited to OpenSSL) that is licensed under separate terms, 11 as designated in a particular file or component or in included license 12 documentation. The authors of MySQL hereby grant you an additional 13 permission to link the program and your derivative works with the 14 separately licensed software that they have included with MySQL. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License, version 2.0, for more details. 20 21 You should have received a copy of the GNU General Public License along with 22 this program; if not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA 24 25 *****************************************************************************/ 26 27 /**************************************************//** 28 @file include/hash0hash.h 29 The simple hash table utility 30 31 Created 5/20/1997 Heikki Tuuri 32 *******************************************************/ 33 34 #ifndef hash0hash_h 35 #define hash0hash_h 36 37 #include "univ.i" 38 #include "mem0mem.h" 39 #ifndef UNIV_HOTBACKUP 40 # include "sync0sync.h" 41 # include "sync0rw.h" 42 #endif /* !UNIV_HOTBACKUP */ 43 44 struct hash_table_t; 45 struct hash_cell_t; 46 47 typedef void* hash_node_t; 48 49 /* Fix Bug #13859: symbol collision between imap/mysql */ 50 #define hash_create hash0_create 51 52 /* Differnt types of hash_table based on the synchronization 53 method used for it. */ 54 enum hash_table_sync_t { 55 HASH_TABLE_SYNC_NONE = 0, /*!< Don't use any internal 56 synchronization objects for 57 this hash_table. */ 58 HASH_TABLE_SYNC_MUTEX, /*!< Use mutexes to control 59 access to this hash_table. */ 60 HASH_TABLE_SYNC_RW_LOCK /*!< Use rw_locks to control 61 access to this hash_table. */ 62 }; 63 64 /*************************************************************//** 65 Creates a hash table with >= n array cells. The actual number 66 of cells is chosen to be a prime number slightly bigger than n. 67 @return own: created table */ 68 UNIV_INTERN 69 hash_table_t* 70 hash_create( 71 /*========*/ 72 ulint n); /*!< in: number of array cells */ 73 #ifndef UNIV_HOTBACKUP 74 /*************************************************************//** 75 Creates a sync object array array to protect a hash table. 76 ::sync_obj can be mutexes or rw_locks depening on the type of 77 hash table. */ 78 UNIV_INTERN 79 void 80 hash_create_sync_obj_func( 81 /*======================*/ 82 hash_table_t* table, /*!< in: hash table */ 83 enum hash_table_sync_t type, /*!< in: HASH_TABLE_SYNC_MUTEX 84 or HASH_TABLE_SYNC_RW_LOCK */ 85 #ifdef UNIV_SYNC_DEBUG 86 ulint sync_level,/*!< in: latching order level 87 of the mutexes: used in the 88 debug version */ 89 #endif /* UNIV_SYNC_DEBUG */ 90 ulint n_sync_obj);/*!< in: number of sync objects, 91 must be a power of 2 */ 92 #ifdef UNIV_SYNC_DEBUG 93 # define hash_create_sync_obj(t, s, n, level) \ 94 hash_create_sync_obj_func(t, s, level, n) 95 #else /* UNIV_SYNC_DEBUG */ 96 # define hash_create_sync_obj(t, s, n, level) \ 97 hash_create_sync_obj_func(t, s, n) 98 #endif /* UNIV_SYNC_DEBUG */ 99 #endif /* !UNIV_HOTBACKUP */ 100 101 /*************************************************************//** 102 Frees a hash table. */ 103 UNIV_INTERN 104 void 105 hash_table_free( 106 /*============*/ 107 hash_table_t* table); /*!< in, own: hash table */ 108 /**************************************************************//** 109 Calculates the hash value from a folded value. 110 @return hashed value */ 111 UNIV_INLINE 112 ulint 113 hash_calc_hash( 114 /*===========*/ 115 ulint fold, /*!< in: folded value */ 116 hash_table_t* table); /*!< in: hash table */ 117 #ifndef UNIV_HOTBACKUP 118 /********************************************************************//** 119 Assert that the mutex for the table is held */ 120 # define HASH_ASSERT_OWN(TABLE, FOLD) \ 121 ut_ad((TABLE)->type != HASH_TABLE_SYNC_MUTEX \ 122 || (mutex_own(hash_get_mutex((TABLE), FOLD)))); 123 #else /* !UNIV_HOTBACKUP */ 124 # define HASH_ASSERT_OWN(TABLE, FOLD) 125 #endif /* !UNIV_HOTBACKUP */ 126 127 /*******************************************************************//** 128 Inserts a struct to a hash table. */ 129 130 #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\ 131 do {\ 132 hash_cell_t* cell3333;\ 133 TYPE* struct3333;\ 134 \ 135 HASH_ASSERT_OWN(TABLE, FOLD)\ 136 \ 137 (DATA)->NAME = NULL;\ 138 \ 139 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ 140 \ 141 if (cell3333->node == NULL) {\ 142 cell3333->node = DATA;\ 143 } else {\ 144 struct3333 = (TYPE*) cell3333->node;\ 145 \ 146 while (struct3333->NAME != NULL) {\ 147 \ 148 struct3333 = (TYPE*) struct3333->NAME;\ 149 }\ 150 \ 151 struct3333->NAME = DATA;\ 152 }\ 153 } while (0) 154 155 #ifdef WITH_WSREP 156 /*******************************************************************//** 157 Inserts a struct to the head of hash table. */ 158 159 #define HASH_PREPEND(TYPE, NAME, TABLE, FOLD, DATA) \ 160 do { \ 161 hash_cell_t* cell3333; \ 162 TYPE* struct3333; \ 163 \ 164 HASH_ASSERT_OWN(TABLE, FOLD) \ 165 \ 166 (DATA)->NAME = NULL; \ 167 \ 168 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ 169 \ 170 if (cell3333->node == NULL) { \ 171 cell3333->node = DATA; \ 172 DATA->NAME = NULL; \ 173 } else { \ 174 struct3333 = (TYPE*) cell3333->node; \ 175 \ 176 DATA->NAME = struct3333; \ 177 \ 178 cell3333->node = DATA; \ 179 } \ 180 } while (0) 181 #endif /*WITH_WSREP */ 182 #ifdef UNIV_HASH_DEBUG 183 # define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1) 184 # define HASH_INVALIDATE(DATA, NAME) *(void**) (&DATA->NAME) = (void*) -1 185 #else 186 # define HASH_ASSERT_VALID(DATA) do {} while (0) 187 # define HASH_INVALIDATE(DATA, NAME) do {} while (0) 188 #endif 189 190 /*******************************************************************//** 191 Deletes a struct from a hash table. */ 192 193 #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\ 194 do {\ 195 hash_cell_t* cell3333;\ 196 TYPE* struct3333;\ 197 \ 198 HASH_ASSERT_OWN(TABLE, FOLD)\ 199 \ 200 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ 201 \ 202 if (cell3333->node == DATA) {\ 203 HASH_ASSERT_VALID(DATA->NAME);\ 204 cell3333->node = DATA->NAME;\ 205 } else {\ 206 struct3333 = (TYPE*) cell3333->node;\ 207 \ 208 while (struct3333->NAME != DATA) {\ 209 \ 210 struct3333 = (TYPE*) struct3333->NAME;\ 211 ut_a(struct3333);\ 212 }\ 213 \ 214 struct3333->NAME = DATA->NAME;\ 215 }\ 216 HASH_INVALIDATE(DATA, NAME);\ 217 } while (0) 218 219 /*******************************************************************//** 220 Gets the first struct in a hash chain, NULL if none. */ 221 222 #define HASH_GET_FIRST(TABLE, HASH_VAL)\ 223 (hash_get_nth_cell(TABLE, HASH_VAL)->node) 224 225 /*******************************************************************//** 226 Gets the next struct in a hash chain, NULL if none. */ 227 228 #define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME) 229 230 /********************************************************************//** 231 Looks for a struct in a hash table. */ 232 #define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\ 233 {\ 234 \ 235 HASH_ASSERT_OWN(TABLE, FOLD)\ 236 \ 237 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\ 238 HASH_ASSERT_VALID(DATA);\ 239 \ 240 while ((DATA) != NULL) {\ 241 ASSERTION;\ 242 if (TEST) {\ 243 break;\ 244 } else {\ 245 HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\ 246 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\ 247 }\ 248 }\ 249 } 250 251 /********************************************************************//** 252 Looks for an item in all hash buckets. */ 253 #define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \ 254 do { \ 255 ulint i3333; \ 256 \ 257 for (i3333 = (TABLE)->n_cells; i3333--; ) { \ 258 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \ 259 \ 260 while ((DATA) != NULL) { \ 261 HASH_ASSERT_VALID(DATA); \ 262 ASSERTION; \ 263 \ 264 if (TEST) { \ 265 break; \ 266 } \ 267 \ 268 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \ 269 } \ 270 \ 271 if ((DATA) != NULL) { \ 272 break; \ 273 } \ 274 } \ 275 } while (0) 276 277 /************************************************************//** 278 Gets the nth cell in a hash table. 279 @return pointer to cell */ 280 UNIV_INLINE 281 hash_cell_t* 282 hash_get_nth_cell( 283 /*==============*/ 284 hash_table_t* table, /*!< in: hash table */ 285 ulint n); /*!< in: cell index */ 286 287 /*************************************************************//** 288 Clears a hash table so that all the cells become empty. */ 289 UNIV_INLINE 290 void 291 hash_table_clear( 292 /*=============*/ 293 hash_table_t* table); /*!< in/out: hash table */ 294 295 /*************************************************************//** 296 Returns the number of cells in a hash table. 297 @return number of cells */ 298 UNIV_INLINE 299 ulint 300 hash_get_n_cells( 301 /*=============*/ 302 hash_table_t* table); /*!< in: table */ 303 /*******************************************************************//** 304 Deletes a struct which is stored in the heap of the hash table, and compacts 305 the heap. The fold value must be stored in the struct NODE in a field named 306 'fold'. */ 307 308 #define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\ 309 do {\ 310 TYPE* node111;\ 311 TYPE* top_node111;\ 312 hash_cell_t* cell111;\ 313 ulint fold111;\ 314 \ 315 fold111 = (NODE)->fold;\ 316 \ 317 HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\ 318 \ 319 top_node111 = (TYPE*) mem_heap_get_top(\ 320 hash_get_heap(TABLE, fold111),\ 321 sizeof(TYPE));\ 322 \ 323 /* If the node to remove is not the top node in the heap, compact the\ 324 heap of nodes by moving the top node in the place of NODE. */\ 325 \ 326 if (NODE != top_node111) {\ 327 \ 328 /* Copy the top node in place of NODE */\ 329 \ 330 *(NODE) = *top_node111;\ 331 \ 332 cell111 = hash_get_nth_cell(TABLE,\ 333 hash_calc_hash(top_node111->fold, TABLE));\ 334 \ 335 /* Look for the pointer to the top node, to update it */\ 336 \ 337 if (cell111->node == top_node111) {\ 338 /* The top node is the first in the chain */\ 339 \ 340 cell111->node = NODE;\ 341 } else {\ 342 /* We have to look for the predecessor of the top\ 343 node */\ 344 node111 = static_cast<TYPE*>(cell111->node);\ 345 \ 346 while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\ 347 \ 348 node111 = static_cast<TYPE*>(\ 349 HASH_GET_NEXT(NAME, node111));\ 350 }\ 351 \ 352 /* Now we have the predecessor node */\ 353 \ 354 node111->NAME = NODE;\ 355 }\ 356 }\ 357 \ 358 /* Free the space occupied by the top node */\ 359 \ 360 mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\ 361 } while (0) 362 363 #ifndef UNIV_HOTBACKUP 364 /****************************************************************//** 365 Move all hash table entries from OLD_TABLE to NEW_TABLE. */ 366 367 #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \ 368 do {\ 369 ulint i2222;\ 370 ulint cell_count2222;\ 371 \ 372 cell_count2222 = hash_get_n_cells(OLD_TABLE);\ 373 \ 374 for (i2222 = 0; i2222 < cell_count2222; i2222++) {\ 375 NODE_TYPE* node2222 = HASH_GET_FIRST((OLD_TABLE), i2222);\ 376 \ 377 while (node2222) {\ 378 NODE_TYPE* next2222 = node2222->PTR_NAME;\ 379 ulint fold2222 = FOLD_FUNC(node2222);\ 380 \ 381 HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\ 382 fold2222, node2222);\ 383 \ 384 node2222 = next2222;\ 385 }\ 386 }\ 387 } while (0) 388 389 /************************************************************//** 390 Gets the sync object index for a fold value in a hash table. 391 @return index */ 392 UNIV_INLINE 393 ulint 394 hash_get_sync_obj_index( 395 /*====================*/ 396 hash_table_t* table, /*!< in: hash table */ 397 ulint fold); /*!< in: fold */ 398 /************************************************************//** 399 Gets the nth heap in a hash table. 400 @return mem heap */ 401 UNIV_INLINE 402 mem_heap_t* 403 hash_get_nth_heap( 404 /*==============*/ 405 hash_table_t* table, /*!< in: hash table */ 406 ulint i); /*!< in: index of the heap */ 407 /************************************************************//** 408 Gets the heap for a fold value in a hash table. 409 @return mem heap */ 410 UNIV_INLINE 411 mem_heap_t* 412 hash_get_heap( 413 /*==========*/ 414 hash_table_t* table, /*!< in: hash table */ 415 ulint fold); /*!< in: fold */ 416 /************************************************************//** 417 Gets the nth mutex in a hash table. 418 @return mutex */ 419 UNIV_INLINE 420 ib_mutex_t* 421 hash_get_nth_mutex( 422 /*===============*/ 423 hash_table_t* table, /*!< in: hash table */ 424 ulint i); /*!< in: index of the mutex */ 425 /************************************************************//** 426 Gets the nth rw_lock in a hash table. 427 @return rw_lock */ 428 UNIV_INLINE 429 rw_lock_t* 430 hash_get_nth_lock( 431 /*==============*/ 432 hash_table_t* table, /*!< in: hash table */ 433 ulint i); /*!< in: index of the rw_lock */ 434 /************************************************************//** 435 Gets the mutex for a fold value in a hash table. 436 @return mutex */ 437 UNIV_INLINE 438 ib_mutex_t* 439 hash_get_mutex( 440 /*===========*/ 441 hash_table_t* table, /*!< in: hash table */ 442 ulint fold); /*!< in: fold */ 443 /************************************************************//** 444 Gets the rw_lock for a fold value in a hash table. 445 @return rw_lock */ 446 UNIV_INLINE 447 rw_lock_t* 448 hash_get_lock( 449 /*==========*/ 450 hash_table_t* table, /*!< in: hash table */ 451 ulint fold); /*!< in: fold */ 452 /************************************************************//** 453 Reserves the mutex for a fold value in a hash table. */ 454 UNIV_INTERN 455 void 456 hash_mutex_enter( 457 /*=============*/ 458 hash_table_t* table, /*!< in: hash table */ 459 ulint fold); /*!< in: fold */ 460 /************************************************************//** 461 Releases the mutex for a fold value in a hash table. */ 462 UNIV_INTERN 463 void 464 hash_mutex_exit( 465 /*============*/ 466 hash_table_t* table, /*!< in: hash table */ 467 ulint fold); /*!< in: fold */ 468 /************************************************************//** 469 Reserves all the mutexes of a hash table, in an ascending order. */ 470 UNIV_INTERN 471 void 472 hash_mutex_enter_all( 473 /*=================*/ 474 hash_table_t* table); /*!< in: hash table */ 475 /************************************************************//** 476 Releases all the mutexes of a hash table. */ 477 UNIV_INTERN 478 void 479 hash_mutex_exit_all( 480 /*================*/ 481 hash_table_t* table); /*!< in: hash table */ 482 /************************************************************//** 483 Releases all but the passed in mutex of a hash table. */ 484 UNIV_INTERN 485 void 486 hash_mutex_exit_all_but( 487 /*====================*/ 488 hash_table_t* table, /*!< in: hash table */ 489 ib_mutex_t* keep_mutex); /*!< in: mutex to keep */ 490 /************************************************************//** 491 s-lock a lock for a fold value in a hash table. */ 492 UNIV_INTERN 493 void 494 hash_lock_s( 495 /*========*/ 496 hash_table_t* table, /*!< in: hash table */ 497 ulint fold); /*!< in: fold */ 498 /************************************************************//** 499 x-lock a lock for a fold value in a hash table. */ 500 UNIV_INTERN 501 void 502 hash_lock_x( 503 /*========*/ 504 hash_table_t* table, /*!< in: hash table */ 505 ulint fold); /*!< in: fold */ 506 /************************************************************//** 507 unlock an s-lock for a fold value in a hash table. */ 508 UNIV_INTERN 509 void 510 hash_unlock_s( 511 /*==========*/ 512 513 hash_table_t* table, /*!< in: hash table */ 514 ulint fold); /*!< in: fold */ 515 /************************************************************//** 516 unlock x-lock for a fold value in a hash table. */ 517 UNIV_INTERN 518 void 519 hash_unlock_x( 520 /*==========*/ 521 hash_table_t* table, /*!< in: hash table */ 522 ulint fold); /*!< in: fold */ 523 /************************************************************//** 524 Reserves all the locks of a hash table, in an ascending order. */ 525 UNIV_INTERN 526 void 527 hash_lock_x_all( 528 /*============*/ 529 hash_table_t* table); /*!< in: hash table */ 530 /************************************************************//** 531 Releases all the locks of a hash table, in an ascending order. */ 532 UNIV_INTERN 533 void 534 hash_unlock_x_all( 535 /*==============*/ 536 hash_table_t* table); /*!< in: hash table */ 537 /************************************************************//** 538 Releases all but passed in lock of a hash table, */ 539 UNIV_INTERN 540 void 541 hash_unlock_x_all_but( 542 /*==================*/ 543 hash_table_t* table, /*!< in: hash table */ 544 rw_lock_t* keep_lock); /*!< in: lock to keep */ 545 546 #else /* !UNIV_HOTBACKUP */ 547 # define hash_get_heap(table, fold) ((table)->heap) 548 # define hash_mutex_enter(table, fold) ((void) 0) 549 # define hash_mutex_exit(table, fold) ((void) 0) 550 # define hash_mutex_enter_all(table) ((void) 0) 551 # define hash_mutex_exit_all(table) ((void) 0) 552 # define hash_mutex_exit_all_but(t, m) ((void) 0) 553 # define hash_lock_s(t, f) ((void) 0) 554 # define hash_lock_x(t, f) ((void) 0) 555 # define hash_unlock_s(t, f) ((void) 0) 556 # define hash_unlock_x(t, f) ((void) 0) 557 # define hash_lock_x_all(t) ((void) 0) 558 # define hash_unlock_x_all(t) ((void) 0) 559 # define hash_unlock_x_all_but(t, l) ((void) 0) 560 #endif /* !UNIV_HOTBACKUP */ 561 562 struct hash_cell_t{ 563 void* node; /*!< hash chain node, NULL if none */ 564 }; 565 566 /* The hash table structure */ 567 struct hash_table_t { 568 enum hash_table_sync_t type; /*<! type of hash_table. */ 569 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 570 # ifndef UNIV_HOTBACKUP 571 ibool adaptive;/* TRUE if this is the hash 572 table of the adaptive hash 573 index */ 574 # endif /* !UNIV_HOTBACKUP */ 575 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 576 ulint n_cells;/* number of cells in the hash table */ 577 hash_cell_t* array; /*!< pointer to cell array */ 578 #ifndef UNIV_HOTBACKUP 579 ulint n_sync_obj;/* if sync_objs != NULL, then 580 the number of either the number 581 of mutexes or the number of 582 rw_locks depending on the type. 583 Must be a power of 2 */ 584 union { 585 ib_mutex_t* mutexes;/* NULL, or an array of mutexes 586 used to protect segments of the 587 hash table */ 588 rw_lock_t* rw_locks;/* NULL, or an array of rw_lcoks 589 used to protect segments of the 590 hash table */ 591 } sync_obj; 592 593 mem_heap_t** heaps; /*!< if this is non-NULL, hash 594 chain nodes for external chaining 595 can be allocated from these memory 596 heaps; there are then n_mutexes 597 many of these heaps */ 598 #endif /* !UNIV_HOTBACKUP */ 599 mem_heap_t* heap; 600 #ifdef UNIV_DEBUG 601 ulint magic_n; 602 # define HASH_TABLE_MAGIC_N 76561114 603 #endif /* UNIV_DEBUG */ 604 }; 605 606 #ifndef UNIV_NONINL 607 #include "hash0hash.ic" 608 #endif 609 610 #endif 611