00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00026 #pragma once
00027 #ifndef hash0hash_h
00028 #define hash0hash_h
00029
00030 #include "univ.i"
00031 #include "mem0mem.h"
00032 #ifndef UNIV_HOTBACKUP
00033 # include "sync0sync.h"
00034 #endif
00035
00036 typedef struct hash_table_struct hash_table_t;
00037 typedef struct hash_cell_struct hash_cell_t;
00038
00039 typedef void* hash_node_t;
00040
00041
00042 #define hash_create hash0_create
00043
00044
00048 UNIV_INTERN
00049 hash_table_t*
00050 hash_create(
00051
00052 ulint n);
00053 #ifndef UNIV_HOTBACKUP
00054
00056 UNIV_INTERN
00057 void
00058 hash_create_mutexes_func(
00059
00060 hash_table_t* table,
00061 #ifdef UNIV_SYNC_DEBUG
00062 ulint sync_level,
00064 #endif
00065 ulint n_mutexes);
00066 #ifdef UNIV_SYNC_DEBUG
00067 # define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,level,n)
00068 #else
00069 # define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,n)
00070 #endif
00071 #endif
00072
00073
00075 UNIV_INTERN
00076 void
00077 hash_table_free(
00078
00079 hash_table_t* table);
00080
00083 UNIV_INLINE
00084 ulint
00085 hash_calc_hash(
00086
00087 ulint fold,
00088 hash_table_t* table);
00089 #ifndef UNIV_HOTBACKUP
00090
00092 # define HASH_ASSERT_OWNED(TABLE, FOLD) \
00093 ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));
00094 #else
00095 # define HASH_ASSERT_OWNED(TABLE, FOLD)
00096 #endif
00097
00098
00101 #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
00102 do {\
00103 hash_cell_t* cell3333;\
00104 TYPE* struct3333;\
00105 \
00106 HASH_ASSERT_OWNED(TABLE, FOLD)\
00107 \
00108 (DATA)->NAME = NULL;\
00109 \
00110 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
00111 \
00112 if (cell3333->node == NULL) {\
00113 cell3333->node = DATA;\
00114 } else {\
00115 struct3333 = (TYPE*) cell3333->node;\
00116 \
00117 while (struct3333->NAME != NULL) {\
00118 \
00119 struct3333 = (TYPE*) struct3333->NAME;\
00120 }\
00121 \
00122 struct3333->NAME = DATA;\
00123 }\
00124 } while (0)
00125
00126 #ifdef UNIV_HASH_DEBUG
00127 # define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1)
00128 # define HASH_INVALIDATE(DATA, NAME) DATA->NAME = (void*) -1
00129 #else
00130 # define HASH_ASSERT_VALID(DATA) do {} while (0)
00131 # define HASH_INVALIDATE(DATA, NAME) do {} while (0)
00132 #endif
00133
00134
00137 #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
00138 do {\
00139 hash_cell_t* cell3333;\
00140 TYPE* struct3333;\
00141 \
00142 HASH_ASSERT_OWNED(TABLE, FOLD)\
00143 \
00144 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
00145 \
00146 if (cell3333->node == DATA) {\
00147 HASH_ASSERT_VALID(DATA->NAME);\
00148 cell3333->node = DATA->NAME;\
00149 } else {\
00150 struct3333 = (TYPE*) cell3333->node;\
00151 \
00152 while (struct3333->NAME != DATA) {\
00153 \
00154 struct3333 = (TYPE*) struct3333->NAME;\
00155 ut_a(struct3333);\
00156 }\
00157 \
00158 struct3333->NAME = DATA->NAME;\
00159 }\
00160 HASH_INVALIDATE(DATA, NAME);\
00161 } while (0)
00162
00163
00166 #define HASH_GET_FIRST(TABLE, HASH_VAL)\
00167 (hash_get_nth_cell(TABLE, HASH_VAL)->node)
00168
00169
00172 #define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME)
00173
00174
00176 #define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)\
00177 {\
00178 \
00179 HASH_ASSERT_OWNED(TABLE, FOLD)\
00180 \
00181 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\
00182 HASH_ASSERT_VALID(DATA);\
00183 \
00184 while ((DATA) != NULL) {\
00185 ASSERTION;\
00186 if (TEST) {\
00187 break;\
00188 } else {\
00189 HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\
00190 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\
00191 }\
00192 }\
00193 }
00194
00195
00197 #define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \
00198 do { \
00199 ulint i3333; \
00200 \
00201 for (i3333 = (TABLE)->n_cells; i3333--; ) { \
00202 (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \
00203 \
00204 while ((DATA) != NULL) { \
00205 HASH_ASSERT_VALID(DATA); \
00206 ASSERTION; \
00207 \
00208 if (TEST) { \
00209 break; \
00210 } \
00211 \
00212 (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \
00213 } \
00214 \
00215 if ((DATA) != NULL) { \
00216 break; \
00217 } \
00218 } \
00219 } while (0)
00220
00221
00224 UNIV_INLINE
00225 hash_cell_t*
00226 hash_get_nth_cell(
00227
00228 hash_table_t* table,
00229 ulint n);
00231
00233 UNIV_INLINE
00234 void
00235 hash_table_clear(
00236
00237 hash_table_t* table);
00239
00242 UNIV_INLINE
00243 ulint
00244 hash_get_n_cells(
00245
00246 hash_table_t* table);
00247
00252 #define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\
00253 do {\
00254 TYPE* node111;\
00255 TYPE* top_node111;\
00256 hash_cell_t* cell111;\
00257 ulint fold111;\
00258 \
00259 fold111 = (NODE)->fold;\
00260 \
00261 HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\
00262 \
00263 top_node111 = (TYPE*)mem_heap_get_top(\
00264 hash_get_heap(TABLE, fold111),\
00265 sizeof(TYPE));\
00266 \
00267
00268 \
00269 \
00270 if (NODE != top_node111) {\
00271 \
00272 \
00273 \
00274 *(NODE) = *top_node111;\
00275 \
00276 cell111 = hash_get_nth_cell(TABLE,\
00277 hash_calc_hash(top_node111->fold, TABLE));\
00278 \
00279 \
00280 \
00281 if (cell111->node == top_node111) {\
00282 \
00283 \
00284 cell111->node = NODE;\
00285 } else {\
00286
00287 \
00288 node111 = static_cast<TYPE *>(cell111->node);\
00289 \
00290 while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\
00291 \
00292 node111 = static_cast<TYPE *>(HASH_GET_NEXT(NAME, node111));\
00293 }\
00294 \
00295 \
00296 \
00297 node111->NAME = NODE;\
00298 }\
00299 }\
00300 \
00301 \
00302 \
00303 mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\
00304 } while (0)
00305
00306 #ifndef UNIV_HOTBACKUP
00307
00310 #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \
00311 do {\
00312 ulint i2222;\
00313 ulint cell_count2222;\
00314 \
00315 cell_count2222 = hash_get_n_cells(OLD_TABLE);\
00316 \
00317 for (i2222 = 0; i2222 < cell_count2222; i2222++) {\
00318 NODE_TYPE* node2222 = static_cast<NODE_TYPE *>(HASH_GET_FIRST((OLD_TABLE), i2222));\
00319 \
00320 while (node2222) {\
00321 NODE_TYPE* next2222 = static_cast<NODE_TYPE *>(node2222->PTR_NAME);\
00322 ulint fold2222 = FOLD_FUNC(node2222);\
00323 \
00324 HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\
00325 fold2222, node2222);\
00326 \
00327 node2222 = next2222;\
00328 }\
00329 }\
00330 } while (0)
00331
00332
00335 UNIV_INLINE
00336 ulint
00337 hash_get_mutex_no(
00338
00339 hash_table_t* table,
00340 ulint fold);
00341
00344 UNIV_INLINE
00345 mem_heap_t*
00346 hash_get_nth_heap(
00347
00348 hash_table_t* table,
00349 ulint i);
00350
00353 UNIV_INLINE
00354 mem_heap_t*
00355 hash_get_heap(
00356
00357 hash_table_t* table,
00358 ulint fold);
00359
00362 UNIV_INLINE
00363 mutex_t*
00364 hash_get_nth_mutex(
00365
00366 hash_table_t* table,
00367 ulint i);
00368
00371 UNIV_INLINE
00372 mutex_t*
00373 hash_get_mutex(
00374
00375 hash_table_t* table,
00376 ulint fold);
00377
00379 UNIV_INTERN
00380 void
00381 hash_mutex_enter(
00382
00383 hash_table_t* table,
00384 ulint fold);
00385
00387 UNIV_INTERN
00388 void
00389 hash_mutex_exit(
00390
00391 hash_table_t* table,
00392 ulint fold);
00393
00395 UNIV_INTERN
00396 void
00397 hash_mutex_enter_all(
00398
00399 hash_table_t* table);
00400
00402 UNIV_INTERN
00403 void
00404 hash_mutex_exit_all(
00405
00406 hash_table_t* table);
00407 #else
00408 # define hash_get_heap(table, fold) ((table)->heap)
00409 # define hash_mutex_enter(table, fold) ((void) 0)
00410 # define hash_mutex_exit(table, fold) ((void) 0)
00411 #endif
00412
00413 struct hash_cell_struct{
00414 void* node;
00415 };
00416
00417
00418 struct hash_table_struct {
00419 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
00420 # ifndef UNIV_HOTBACKUP
00421 ibool adaptive;
00422
00423 # endif
00424 #endif
00425 ulint n_cells;
00426 hash_cell_t* array;
00427 #ifndef UNIV_HOTBACKUP
00428 ulint n_mutexes;
00429
00430 mutex_t* mutexes;
00431
00432 mem_heap_t** heaps;
00436 #endif
00437 mem_heap_t* heap;
00438 #ifdef UNIV_DEBUG
00439 ulint magic_n;
00440 # define HASH_TABLE_MAGIC_N 76561114
00441 #endif
00442 };
00443
00444 #ifndef UNIV_NONINL
00445 #include "hash0hash.ic"
00446 #endif
00447
00448 #endif