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