release/src/router/mysql/storage/innodb_plugin/include/hash0hash.h

   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.,
  15 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  16
  17 *****************************************************************************/
  18
  19 /**************************************************//**
  20 @file include/hash0hash.h
  21 The simple hash table utility
  22
  23 Created 5/20/1997 Heikki Tuuri
  24 *******************************************************/
  25
  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 #endif /* !UNIV_HOTBACKUP */
  34
  35 typedef struct hash_table_struct hash_table_t;
  36 typedef struct hash_cell_struct hash_cell_t;
  37
  38 typedef void*   hash_node_t;
  39
  40 /* Fix Bug #13859: symbol collision between imap/mysql */
  41 #define hash_create hash0_create
  42
  43 /*************************************************************//**
  44 Creates a hash table with >= n array cells. The actual number
  45 of cells is chosen to be a prime number slightly bigger than n.
  46 @return own: created table */
  47 UNIV_INTERN
  48 hash_table_t*
  49 hash_create(
  50 /*========*/
  51         ulint   n);     /*!< in: number of array cells */
  52 #ifndef UNIV_HOTBACKUP
  53 /*************************************************************//**
  54 Creates a mutex array to protect a hash table. */
  55 UNIV_INTERN
  56 void
  57 hash_create_mutexes_func(
  58 /*=====================*/
  59         hash_table_t*   table,          /*!< in: hash table */
  60 #ifdef UNIV_SYNC_DEBUG
  61         ulint           sync_level,     /*!< in: latching order level of the
  62                                         mutexes: used in the debug version */
  63 #endif /* UNIV_SYNC_DEBUG */
  64         ulint           n_mutexes);     /*!< in: number of mutexes */
  65 #ifdef UNIV_SYNC_DEBUG
  66 # define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,level,n)
  67 #else /* UNIV_SYNC_DEBUG */
  68 # define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,n)
  69 #endif /* UNIV_SYNC_DEBUG */
  70 #endif /* !UNIV_HOTBACKUP */
  71
  72 /*************************************************************//**
  73 Frees a hash table. */
  74 UNIV_INTERN
  75 void
  76 hash_table_free(
  77 /*============*/
  78         hash_table_t*   table); /*!< in, own: hash table */
  79 /**************************************************************//**
  80 Calculates the hash value from a folded value.
  81 @return hashed value */
  82 UNIV_INLINE
  83 ulint
  84 hash_calc_hash(
  85 /*===========*/
  86         ulint           fold,   /*!< in: folded value */
  87         hash_table_t*   table); /*!< in: hash table */
  88 #ifndef UNIV_HOTBACKUP
  89 /********************************************************************//**
  90 Assert that the mutex for the table in a hash operation is owned. */
  91 # define HASH_ASSERT_OWNED(TABLE, FOLD)                                 \
  92 ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));
  93 #else /* !UNIV_HOTBACKUP */
  94 # define HASH_ASSERT_OWNED(TABLE, FOLD)
  95 #endif /* !UNIV_HOTBACKUP */
  96
  97 /*******************************************************************//**
  98 Inserts a struct to a hash table. */
  99
 100 #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
 101 do {\
 102         hash_cell_t*    cell3333;\
 103         TYPE*           struct3333;\
 104 \
 105         HASH_ASSERT_OWNED(TABLE, FOLD)\
 106 \
 107         (DATA)->NAME = NULL;\
 108 \
 109         cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
 110 \
 111         if (cell3333->node == NULL) {\
 112                 cell3333->node = DATA;\
 113         } else {\
 114                 struct3333 = (TYPE*) cell3333->node;\
 115 \
 116                 while (struct3333->NAME != NULL) {\
 117 \
 118                         struct3333 = (TYPE*) struct3333->NAME;\
 119                 }\
 120 \
 121                 struct3333->NAME = DATA;\
 122         }\
 123 } while (0)
 124
 125 #ifdef UNIV_HASH_DEBUG
 126 # define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1)
 127 # define HASH_INVALIDATE(DATA, NAME) DATA->NAME = (void*) -1
 128 #else
 129 # define HASH_ASSERT_VALID(DATA) do {} while (0)
 130 # define HASH_INVALIDATE(DATA, NAME) do {} while (0)
 131 #endif
 132
 133 /*******************************************************************//**
 134 Deletes a struct from a hash table. */
 135
 136 #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
 137 do {\
 138         hash_cell_t*    cell3333;\
 139         TYPE*           struct3333;\
 140 \
 141         HASH_ASSERT_OWNED(TABLE, FOLD)\
 142 \
 143         cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
 144 \
 145         if (cell3333->node == DATA) {\
 146                 HASH_ASSERT_VALID(DATA->NAME);\
 147                 cell3333->node = DATA->NAME;\
 148         } else {\
 149                 struct3333 = (TYPE*) cell3333->node;\
 150 \
 151                 while (struct3333->NAME != DATA) {\
 152 \
 153                         struct3333 = (TYPE*) struct3333->NAME;\
 154                         ut_a(struct3333);\
 155                 }\
 156 \
 157                 struct3333->NAME = DATA->NAME;\
 158         }\
 159         HASH_INVALIDATE(DATA, NAME);\
 160 } while (0)
 161
 162 /*******************************************************************//**
 163 Gets the first struct in a hash chain, NULL if none. */
 164
 165 #define HASH_GET_FIRST(TABLE, HASH_VAL)\
 166         (hash_get_nth_cell(TABLE, HASH_VAL)->node)
 167
 168 /*******************************************************************//**
 169 Gets the next struct in a hash chain, NULL if none. */
 170
 171 #define HASH_GET_NEXT(NAME, DATA)       ((DATA)->NAME)
 172
 173 /********************************************************************//**
 174 Looks for a struct in a hash table. */
 175 #define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\
 176 {\
 177 \
 178         HASH_ASSERT_OWNED(TABLE, FOLD)\
 179 \
 180         (DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\
 181         HASH_ASSERT_VALID(DATA);\
 182 \
 183         while ((DATA) != NULL) {\
 184                 ASSERTION;\
 185                 if (TEST) {\
 186                         break;\
 187                 } else {\
 188                         HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\
 189                         (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\
 190                 }\
 191         }\
 192 }
 193
 194 /********************************************************************//**
 195 Looks for an item in all hash buckets. */
 196 #define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST)       \
 197 do {                                                                    \
 198         ulint   i3333;                                                  \
 199                                                                         \
 200         for (i3333 = (TABLE)->n_cells; i3333--; ) {                     \
 201                 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333);           \
 202                                                                         \
 203                 while ((DATA) != NULL) {                                \
 204                         HASH_ASSERT_VALID(DATA);                        \
 205                         ASSERTION;                                      \
 206                                                                         \
 207                         if (TEST) {                                     \
 208                                 break;                                  \
 209                         }                                               \
 210                                                                         \
 211                         (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);      \
 212                 }                                                       \
 213                                                                         \
 214                 if ((DATA) != NULL) {                                   \
 215                         break;                                          \
 216                 }                                                       \
 217         }                                                               \
 218 } while (0)
 219
 220 /************************************************************//**
 221 Gets the nth cell in a hash table.
 222 @return pointer to cell */
 223 UNIV_INLINE
 224 hash_cell_t*
 225 hash_get_nth_cell(
 226 /*==============*/
 227         hash_table_t*   table,  /*!< in: hash table */
 228         ulint           n);     /*!< in: cell index */
 229
 230 /*************************************************************//**
 231 Clears a hash table so that all the cells become empty. */
 232 UNIV_INLINE
 233 void
 234 hash_table_clear(
 235 /*=============*/
 236         hash_table_t*   table); /*!< in/out: hash table */
 237
 238 /*************************************************************//**
 239 Returns the number of cells in a hash table.
 240 @return number of cells */
 241 UNIV_INLINE
 242 ulint
 243 hash_get_n_cells(
 244 /*=============*/
 245         hash_table_t*   table); /*!< in: table */
 246 /*******************************************************************//**
 247 Deletes a struct which is stored in the heap of the hash table, and compacts
 248 the heap. The fold value must be stored in the struct NODE in a field named
 249 'fold'. */
 250
 251 #define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\
 252 do {\
 253         TYPE*           node111;\
 254         TYPE*           top_node111;\
 255         hash_cell_t*    cell111;\
 256         ulint           fold111;\
 257 \
 258         fold111 = (NODE)->fold;\
 259 \
 260         HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\
 261 \
 262         top_node111 = (TYPE*)mem_heap_get_top(\
 263                                 hash_get_heap(TABLE, fold111),\
 264                                                         sizeof(TYPE));\
 265 \
 266         /* If the node to remove is not the top node in the heap, compact the\
 267         heap of nodes by moving the top node in the place of NODE. */\
 268 \
 269         if (NODE != top_node111) {\
 270 \
 271                 /* Copy the top node in place of NODE */\
 272 \
 273                 *(NODE) = *top_node111;\
 274 \
 275                 cell111 = hash_get_nth_cell(TABLE,\
 276                                 hash_calc_hash(top_node111->fold, TABLE));\
 277 \
 278                 /* Look for the pointer to the top node, to update it */\
 279 \
 280                 if (cell111->node == top_node111) {\
 281                         /* The top node is the first in the chain */\
 282 \
 283                         cell111->node = NODE;\
 284                 } else {\
 285                         /* We have to look for the predecessor of the top\
 286                         node */\
 287                         node111 = cell111->node;\
 288 \
 289                         while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\
 290 \
 291                                 node111 = HASH_GET_NEXT(NAME, node111);\
 292                         }\
 293 \
 294                         /* Now we have the predecessor node */\
 295 \
 296                         node111->NAME = NODE;\
 297                 }\
 298         }\
 299 \
 300         /* Free the space occupied by the top node */\
 301 \
 302         mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\
 303 } while (0)
 304
 305 #ifndef UNIV_HOTBACKUP
 306 /****************************************************************//**
 307 Move all hash table entries from OLD_TABLE to NEW_TABLE. */
 308
 309 #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
 310 do {\
 311         ulint           i2222;\
 312         ulint           cell_count2222;\
 313 \
 314         cell_count2222 = hash_get_n_cells(OLD_TABLE);\
 315 \
 316         for (i2222 = 0; i2222 < cell_count2222; i2222++) {\
 317                 NODE_TYPE*      node2222 = HASH_GET_FIRST((OLD_TABLE), i2222);\
 318 \
 319                 while (node2222) {\
 320                         NODE_TYPE*      next2222 = node2222->PTR_NAME;\
 321                         ulint           fold2222 = FOLD_FUNC(node2222);\
 322 \
 323                         HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\
 324                                 fold2222, node2222);\
 325 \
 326                         node2222 = next2222;\
 327                 }\
 328         }\
 329 } while (0)
 330
 331 /************************************************************//**
 332 Gets the mutex index for a fold value in a hash table.
 333 @return mutex number */
 334 UNIV_INLINE
 335 ulint
 336 hash_get_mutex_no(
 337 /*==============*/
 338         hash_table_t*   table,  /*!< in: hash table */
 339         ulint           fold);  /*!< in: fold */
 340 /************************************************************//**
 341 Gets the nth heap in a hash table.
 342 @return mem heap */
 343 UNIV_INLINE
 344 mem_heap_t*
 345 hash_get_nth_heap(
 346 /*==============*/
 347         hash_table_t*   table,  /*!< in: hash table */
 348         ulint           i);     /*!< in: index of the heap */
 349 /************************************************************//**
 350 Gets the heap for a fold value in a hash table.
 351 @return mem heap */
 352 UNIV_INLINE
 353 mem_heap_t*
 354 hash_get_heap(
 355 /*==========*/
 356         hash_table_t*   table,  /*!< in: hash table */
 357         ulint           fold);  /*!< in: fold */
 358 /************************************************************//**
 359 Gets the nth mutex in a hash table.
 360 @return mutex */
 361 UNIV_INLINE
 362 mutex_t*
 363 hash_get_nth_mutex(
 364 /*===============*/
 365         hash_table_t*   table,  /*!< in: hash table */
 366         ulint           i);     /*!< in: index of the mutex */
 367 /************************************************************//**
 368 Gets the mutex for a fold value in a hash table.
 369 @return mutex */
 370 UNIV_INLINE
 371 mutex_t*
 372 hash_get_mutex(
 373 /*===========*/
 374         hash_table_t*   table,  /*!< in: hash table */
 375         ulint           fold);  /*!< in: fold */
 376 /************************************************************//**
 377 Reserves the mutex for a fold value in a hash table. */
 378 UNIV_INTERN
 379 void
 380 hash_mutex_enter(
 381 /*=============*/
 382         hash_table_t*   table,  /*!< in: hash table */
 383         ulint           fold);  /*!< in: fold */
 384 /************************************************************//**
 385 Releases the mutex for a fold value in a hash table. */
 386 UNIV_INTERN
 387 void
 388 hash_mutex_exit(
 389 /*============*/
 390         hash_table_t*   table,  /*!< in: hash table */
 391         ulint           fold);  /*!< in: fold */
 392 /************************************************************//**
 393 Reserves all the mutexes of a hash table, in an ascending order. */
 394 UNIV_INTERN
 395 void
 396 hash_mutex_enter_all(
 397 /*=================*/
 398         hash_table_t*   table); /*!< in: hash table */
 399 /************************************************************//**
 400 Releases all the mutexes of a hash table. */
 401 UNIV_INTERN
 402 void
 403 hash_mutex_exit_all(
 404 /*================*/
 405         hash_table_t*   table); /*!< in: hash table */
 406 #else /* !UNIV_HOTBACKUP */
 407 # define hash_get_heap(table, fold)     ((table)->heap)
 408 # define hash_mutex_enter(table, fold)  ((void) 0)
 409 # define hash_mutex_exit(table, fold)   ((void) 0)
 410 #endif /* !UNIV_HOTBACKUP */
 411
 412 struct hash_cell_struct{
 413         void*   node;   /*!< hash chain node, NULL if none */
 414 };
 415
 416 /* The hash table structure */
 417 struct hash_table_struct {
 418 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
 419 # ifndef UNIV_HOTBACKUP
 420         ibool           adaptive;/* TRUE if this is the hash table of the
 421                                 adaptive hash index */
 422 # endif /* !UNIV_HOTBACKUP */
 423 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
 424         ulint           n_cells;/* number of cells in the hash table */
 425         hash_cell_t*    array;  /*!< pointer to cell array */
 426 #ifndef UNIV_HOTBACKUP
 427         ulint           n_mutexes;/* if mutexes != NULL, then the number of
 428                                 mutexes, must be a power of 2 */
 429         mutex_t*        mutexes;/* NULL, or an array of mutexes used to
 430                                 protect segments of the hash table */
 431         mem_heap_t**    heaps;  /*!< if this is non-NULL, hash chain nodes for
 432                                 external chaining can be allocated from these
 433                                 memory heaps; there are then n_mutexes many of
 434                                 these heaps */
 435 #endif /* !UNIV_HOTBACKUP */
 436         mem_heap_t*     heap;
 437 #ifdef UNIV_DEBUG
 438         ulint           magic_n;
 439 # define HASH_TABLE_MAGIC_N     76561114
 440 #endif /* UNIV_DEBUG */
 441 };
 442
 443 #ifndef UNIV_NONINL
 444 #include "hash0hash.ic"
 445 #endif
 446
 447 #endif