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 UNIV_HASH_DEBUG 156 # define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1) 157 # define HASH_INVALIDATE(DATA, NAME) *(void**) (&DATA->NAME) = (void*) -1 158 #else 159 # define HASH_ASSERT_VALID(DATA) do {} while (0) 160 # define HASH_INVALIDATE(DATA, NAME) do {} while (0) 161 #endif 162 163 /*******************************************************************//** 164 Deletes a struct from a hash table. */ 165 166 #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\ 167 do {\ 168 hash_cell_t* cell3333;\ 169 TYPE* struct3333;\ 170 \ 171 HASH_ASSERT_OWN(TABLE, FOLD)\ 172 \ 173 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ 174 \ 175 if (cell3333->node == DATA) {\ 176 HASH_ASSERT_VALID(DATA->NAME);\ 177 cell3333->node = DATA->NAME;\ 178 } else {\ 179 struct3333 = (TYPE*) cell3333->node;\ 180 \ 181 while (struct3333->NAME != DATA) {\ 182 \ 183 struct3333 = (TYPE*) struct3333->NAME;\ 184 ut_a(struct3333);\ 185 }\ 186 \ 187 struct3333->NAME = DATA->NAME;\ 188 }\ 189 HASH_INVALIDATE(DATA, NAME);\ 190 } while (0) 191 192 /*******************************************************************//** 193 Gets the first struct in a hash chain, NULL if none. */ 194 195 #define HASH_GET_FIRST(TABLE, HASH_VAL)\ 196 (hash_get_nth_cell(TABLE, HASH_VAL)->node) 197 198 /*******************************************************************//** 199 Gets the next struct in a hash chain, NULL if none. */ 200 201 #define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME) 202 203 /********************************************************************//** 204 Looks for a struct in a hash table. */ 205 #define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\ 206 {\ 207 \ 208 HASH_ASSERT_OWN(TABLE, FOLD)\ 209 \ 210 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\ 211 HASH_ASSERT_VALID(DATA);\ 212 \ 213 while ((DATA) != NULL) {\ 214 ASSERTION;\ 215 if (TEST) {\ 216 break;\ 217 } else {\ 218 HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\ 219 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\ 220 }\ 221 }\ 222 } 223 224 /********************************************************************//** 225 Looks for an item in all hash buckets. */ 226 #define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \ 227 do { \ 228 ulint i3333; \ 229 \ 230 for (i3333 = (TABLE)->n_cells; i3333--; ) { \ 231 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \ 232 \ 233 while ((DATA) != NULL) { \ 234 HASH_ASSERT_VALID(DATA); \ 235 ASSERTION; \ 236 \ 237 if (TEST) { \ 238 break; \ 239 } \ 240 \ 241 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \ 242 } \ 243 \ 244 if ((DATA) != NULL) { \ 245 break; \ 246 } \ 247 } \ 248 } while (0) 249 250 /************************************************************//** 251 Gets the nth cell in a hash table. 252 @return pointer to cell */ 253 UNIV_INLINE 254 hash_cell_t* 255 hash_get_nth_cell( 256 /*==============*/ 257 hash_table_t* table, /*!< in: hash table */ 258 ulint n); /*!< in: cell index */ 259 260 /*************************************************************//** 261 Clears a hash table so that all the cells become empty. */ 262 UNIV_INLINE 263 void 264 hash_table_clear( 265 /*=============*/ 266 hash_table_t* table); /*!< in/out: hash table */ 267 268 /*************************************************************//** 269 Returns the number of cells in a hash table. 270 @return number of cells */ 271 UNIV_INLINE 272 ulint 273 hash_get_n_cells( 274 /*=============*/ 275 hash_table_t* table); /*!< in: table */ 276 /*******************************************************************//** 277 Deletes a struct which is stored in the heap of the hash table, and compacts 278 the heap. The fold value must be stored in the struct NODE in a field named 279 'fold'. */ 280 281 #define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\ 282 do {\ 283 TYPE* node111;\ 284 TYPE* top_node111;\ 285 hash_cell_t* cell111;\ 286 ulint fold111;\ 287 \ 288 fold111 = (NODE)->fold;\ 289 \ 290 HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\ 291 \ 292 top_node111 = (TYPE*) mem_heap_get_top(\ 293 hash_get_heap(TABLE, fold111),\ 294 sizeof(TYPE));\ 295 \ 296 /* If the node to remove is not the top node in the heap, compact the\ 297 heap of nodes by moving the top node in the place of NODE. */\ 298 \ 299 if (NODE != top_node111) {\ 300 \ 301 /* Copy the top node in place of NODE */\ 302 \ 303 *(NODE) = *top_node111;\ 304 \ 305 cell111 = hash_get_nth_cell(TABLE,\ 306 hash_calc_hash(top_node111->fold, TABLE));\ 307 \ 308 /* Look for the pointer to the top node, to update it */\ 309 \ 310 if (cell111->node == top_node111) {\ 311 /* The top node is the first in the chain */\ 312 \ 313 cell111->node = NODE;\ 314 } else {\ 315 /* We have to look for the predecessor of the top\ 316 node */\ 317 node111 = static_cast<TYPE*>(cell111->node);\ 318 \ 319 while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\ 320 \ 321 node111 = static_cast<TYPE*>(\ 322 HASH_GET_NEXT(NAME, node111));\ 323 }\ 324 \ 325 /* Now we have the predecessor node */\ 326 \ 327 node111->NAME = NODE;\ 328 }\ 329 }\ 330 \ 331 /* Free the space occupied by the top node */\ 332 \ 333 mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\ 334 } while (0) 335 336 #ifndef UNIV_HOTBACKUP 337 /****************************************************************//** 338 Move all hash table entries from OLD_TABLE to NEW_TABLE. */ 339 340 #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \ 341 do {\ 342 ulint i2222;\ 343 ulint cell_count2222;\ 344 \ 345 cell_count2222 = hash_get_n_cells(OLD_TABLE);\ 346 \ 347 for (i2222 = 0; i2222 < cell_count2222; i2222++) {\ 348 NODE_TYPE* node2222 = HASH_GET_FIRST((OLD_TABLE), i2222);\ 349 \ 350 while (node2222) {\ 351 NODE_TYPE* next2222 = node2222->PTR_NAME;\ 352 ulint fold2222 = FOLD_FUNC(node2222);\ 353 \ 354 HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\ 355 fold2222, node2222);\ 356 \ 357 node2222 = next2222;\ 358 }\ 359 }\ 360 } while (0) 361 362 /************************************************************//** 363 Gets the sync object index for a fold value in a hash table. 364 @return index */ 365 UNIV_INLINE 366 ulint 367 hash_get_sync_obj_index( 368 /*====================*/ 369 hash_table_t* table, /*!< in: hash table */ 370 ulint fold); /*!< in: fold */ 371 /************************************************************//** 372 Gets the nth heap in a hash table. 373 @return mem heap */ 374 UNIV_INLINE 375 mem_heap_t* 376 hash_get_nth_heap( 377 /*==============*/ 378 hash_table_t* table, /*!< in: hash table */ 379 ulint i); /*!< in: index of the heap */ 380 /************************************************************//** 381 Gets the heap for a fold value in a hash table. 382 @return mem heap */ 383 UNIV_INLINE 384 mem_heap_t* 385 hash_get_heap( 386 /*==========*/ 387 hash_table_t* table, /*!< in: hash table */ 388 ulint fold); /*!< in: fold */ 389 /************************************************************//** 390 Gets the nth mutex in a hash table. 391 @return mutex */ 392 UNIV_INLINE 393 ib_mutex_t* 394 hash_get_nth_mutex( 395 /*===============*/ 396 hash_table_t* table, /*!< in: hash table */ 397 ulint i); /*!< in: index of the mutex */ 398 /************************************************************//** 399 Gets the nth rw_lock in a hash table. 400 @return rw_lock */ 401 UNIV_INLINE 402 rw_lock_t* 403 hash_get_nth_lock( 404 /*==============*/ 405 hash_table_t* table, /*!< in: hash table */ 406 ulint i); /*!< in: index of the rw_lock */ 407 /************************************************************//** 408 Gets the mutex for a fold value in a hash table. 409 @return mutex */ 410 UNIV_INLINE 411 ib_mutex_t* 412 hash_get_mutex( 413 /*===========*/ 414 hash_table_t* table, /*!< in: hash table */ 415 ulint fold); /*!< in: fold */ 416 /************************************************************//** 417 Gets the rw_lock for a fold value in a hash table. 418 @return rw_lock */ 419 UNIV_INLINE 420 rw_lock_t* 421 hash_get_lock( 422 /*==========*/ 423 hash_table_t* table, /*!< in: hash table */ 424 ulint fold); /*!< in: fold */ 425 /************************************************************//** 426 Reserves the mutex for a fold value in a hash table. */ 427 UNIV_INTERN 428 void 429 hash_mutex_enter( 430 /*=============*/ 431 hash_table_t* table, /*!< in: hash table */ 432 ulint fold); /*!< in: fold */ 433 /************************************************************//** 434 Releases the mutex for a fold value in a hash table. */ 435 UNIV_INTERN 436 void 437 hash_mutex_exit( 438 /*============*/ 439 hash_table_t* table, /*!< in: hash table */ 440 ulint fold); /*!< in: fold */ 441 /************************************************************//** 442 Reserves all the mutexes of a hash table, in an ascending order. */ 443 UNIV_INTERN 444 void 445 hash_mutex_enter_all( 446 /*=================*/ 447 hash_table_t* table); /*!< in: hash table */ 448 /************************************************************//** 449 Releases all the mutexes of a hash table. */ 450 UNIV_INTERN 451 void 452 hash_mutex_exit_all( 453 /*================*/ 454 hash_table_t* table); /*!< in: hash table */ 455 /************************************************************//** 456 Releases all but the passed in mutex of a hash table. */ 457 UNIV_INTERN 458 void 459 hash_mutex_exit_all_but( 460 /*====================*/ 461 hash_table_t* table, /*!< in: hash table */ 462 ib_mutex_t* keep_mutex); /*!< in: mutex to keep */ 463 /************************************************************//** 464 s-lock a lock for a fold value in a hash table. */ 465 UNIV_INTERN 466 void 467 hash_lock_s( 468 /*========*/ 469 hash_table_t* table, /*!< in: hash table */ 470 ulint fold); /*!< in: fold */ 471 /************************************************************//** 472 x-lock a lock for a fold value in a hash table. */ 473 UNIV_INTERN 474 void 475 hash_lock_x( 476 /*========*/ 477 hash_table_t* table, /*!< in: hash table */ 478 ulint fold); /*!< in: fold */ 479 /************************************************************//** 480 unlock an s-lock for a fold value in a hash table. */ 481 UNIV_INTERN 482 void 483 hash_unlock_s( 484 /*==========*/ 485 486 hash_table_t* table, /*!< in: hash table */ 487 ulint fold); /*!< in: fold */ 488 /************************************************************//** 489 unlock x-lock for a fold value in a hash table. */ 490 UNIV_INTERN 491 void 492 hash_unlock_x( 493 /*==========*/ 494 hash_table_t* table, /*!< in: hash table */ 495 ulint fold); /*!< in: fold */ 496 /************************************************************//** 497 Reserves all the locks of a hash table, in an ascending order. */ 498 UNIV_INTERN 499 void 500 hash_lock_x_all( 501 /*============*/ 502 hash_table_t* table); /*!< in: hash table */ 503 /************************************************************//** 504 Releases all the locks of a hash table, in an ascending order. */ 505 UNIV_INTERN 506 void 507 hash_unlock_x_all( 508 /*==============*/ 509 hash_table_t* table); /*!< in: hash table */ 510 /************************************************************//** 511 Releases all but passed in lock of a hash table, */ 512 UNIV_INTERN 513 void 514 hash_unlock_x_all_but( 515 /*==================*/ 516 hash_table_t* table, /*!< in: hash table */ 517 rw_lock_t* keep_lock); /*!< in: lock to keep */ 518 519 #else /* !UNIV_HOTBACKUP */ 520 # define hash_get_heap(table, fold) ((table)->heap) 521 # define hash_mutex_enter(table, fold) ((void) 0) 522 # define hash_mutex_exit(table, fold) ((void) 0) 523 # define hash_mutex_enter_all(table) ((void) 0) 524 # define hash_mutex_exit_all(table) ((void) 0) 525 # define hash_mutex_exit_all_but(t, m) ((void) 0) 526 # define hash_lock_s(t, f) ((void) 0) 527 # define hash_lock_x(t, f) ((void) 0) 528 # define hash_unlock_s(t, f) ((void) 0) 529 # define hash_unlock_x(t, f) ((void) 0) 530 # define hash_lock_x_all(t) ((void) 0) 531 # define hash_unlock_x_all(t) ((void) 0) 532 # define hash_unlock_x_all_but(t, l) ((void) 0) 533 #endif /* !UNIV_HOTBACKUP */ 534 535 struct hash_cell_t{ 536 void* node; /*!< hash chain node, NULL if none */ 537 }; 538 539 /* The hash table structure */ 540 struct hash_table_t { 541 enum hash_table_sync_t type; /*<! type of hash_table. */ 542 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG 543 # ifndef UNIV_HOTBACKUP 544 ibool adaptive;/* TRUE if this is the hash 545 table of the adaptive hash 546 index */ 547 # endif /* !UNIV_HOTBACKUP */ 548 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ 549 ulint n_cells;/* number of cells in the hash table */ 550 hash_cell_t* array; /*!< pointer to cell array */ 551 #ifndef UNIV_HOTBACKUP 552 ulint n_sync_obj;/* if sync_objs != NULL, then 553 the number of either the number 554 of mutexes or the number of 555 rw_locks depending on the type. 556 Must be a power of 2 */ 557 union { 558 ib_mutex_t* mutexes;/* NULL, or an array of mutexes 559 used to protect segments of the 560 hash table */ 561 rw_lock_t* rw_locks;/* NULL, or an array of rw_lcoks 562 used to protect segments of the 563 hash table */ 564 } sync_obj; 565 566 mem_heap_t** heaps; /*!< if this is non-NULL, hash 567 chain nodes for external chaining 568 can be allocated from these memory 569 heaps; there are then n_mutexes 570 many of these heaps */ 571 #endif /* !UNIV_HOTBACKUP */ 572 mem_heap_t* heap; 573 #ifdef UNIV_DEBUG 574 ulint magic_n; 575 # define HASH_TABLE_MAGIC_N 76561114 576 #endif /* UNIV_DEBUG */ 577 }; 578 579 #ifndef UNIV_NONINL 580 #include "hash0hash.ic" 581 #endif 582 583 #endif 584