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

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