The world's most popular open source database
mysql/src/5.1-dbg/storage/innobase/include/hash0hash.h
Go to the documentation of this file.00001 /****************************************************** 00002 The simple hash table utility 00003 00004 (c) 1997 Innobase Oy 00005 00006 Created 5/20/1997 Heikki Tuuri 00007 *******************************************************/ 00008 00009 #ifndef hash0hash_h 00010 #define hash0hash_h 00011 00012 #include "univ.i" 00013 #include "mem0mem.h" 00014 #include "sync0sync.h" 00015 00016 typedef struct hash_table_struct hash_table_t; 00017 typedef struct hash_cell_struct hash_cell_t; 00018 00019 typedef void* hash_node_t; 00020 00021 /***************************************************************** 00022 Creates a hash table with >= n array cells. The actual number 00023 of cells is chosen to be a prime number slightly bigger than n. */ 00024 00025 hash_table_t* 00026 hash_create( 00027 /*========*/ 00028 /* out, own: created table */ 00029 ulint n); /* in: number of array cells */ 00030 /***************************************************************** 00031 Creates a mutex array to protect a hash table. */ 00032 00033 void 00034 hash_create_mutexes( 00035 /*================*/ 00036 hash_table_t* table, /* in: hash table */ 00037 ulint n_mutexes, /* in: number of mutexes */ 00038 ulint sync_level); /* in: latching order level of the 00039 mutexes: used in the debug version */ 00040 /***************************************************************** 00041 Frees a hash table. */ 00042 00043 void 00044 hash_table_free( 00045 /*============*/ 00046 hash_table_t* table); /* in, own: hash table */ 00047 /****************************************************************** 00048 Calculates the hash value from a folded value. */ 00049 UNIV_INLINE 00050 ulint 00051 hash_calc_hash( 00052 /*===========*/ 00053 /* out: hashed value */ 00054 ulint fold, /* in: folded value */ 00055 hash_table_t* table); /* in: hash table */ 00056 /************************************************************************ 00057 Assert that the mutex for the table in a hash operation is owned. */ 00058 #ifdef UNIV_SYNC_DEBUG 00059 # define HASH_ASSERT_OWNED(TABLE, FOLD) \ 00060 ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD))); 00061 #else 00062 # define HASH_ASSERT_OWNED(TABLE, FOLD) 00063 #endif 00064 00065 /*********************************************************************** 00066 Inserts a struct to a hash table. */ 00067 00068 #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\ 00069 do {\ 00070 hash_cell_t* cell3333;\ 00071 TYPE* struct3333;\ 00072 \ 00073 HASH_ASSERT_OWNED(TABLE, FOLD)\ 00074 \ 00075 (DATA)->NAME = NULL;\ 00076 \ 00077 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ 00078 \ 00079 if (cell3333->node == NULL) {\ 00080 cell3333->node = DATA;\ 00081 } else {\ 00082 struct3333 = cell3333->node;\ 00083 \ 00084 while (struct3333->NAME != NULL) {\ 00085 \ 00086 struct3333 = struct3333->NAME;\ 00087 }\ 00088 \ 00089 struct3333->NAME = DATA;\ 00090 }\ 00091 } while (0) 00092 00093 /*********************************************************************** 00094 Deletes a struct from a hash table. */ 00095 00096 #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\ 00097 do {\ 00098 hash_cell_t* cell3333;\ 00099 TYPE* struct3333;\ 00100 \ 00101 HASH_ASSERT_OWNED(TABLE, FOLD)\ 00102 \ 00103 cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ 00104 \ 00105 if (cell3333->node == DATA) {\ 00106 cell3333->node = DATA->NAME;\ 00107 } else {\ 00108 struct3333 = cell3333->node;\ 00109 \ 00110 while (struct3333->NAME != DATA) {\ 00111 \ 00112 struct3333 = struct3333->NAME;\ 00113 ut_a(struct3333);\ 00114 }\ 00115 \ 00116 struct3333->NAME = DATA->NAME;\ 00117 }\ 00118 } while (0) 00119 00120 /*********************************************************************** 00121 Gets the first struct in a hash chain, NULL if none. */ 00122 00123 #define HASH_GET_FIRST(TABLE, HASH_VAL)\ 00124 (hash_get_nth_cell(TABLE, HASH_VAL)->node) 00125 00126 /*********************************************************************** 00127 Gets the next struct in a hash chain, NULL if none. */ 00128 00129 #define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME) 00130 00131 /************************************************************************ 00132 Looks for a struct in a hash table. */ 00133 #define HASH_SEARCH(NAME, TABLE, FOLD, DATA, TEST)\ 00134 {\ 00135 \ 00136 HASH_ASSERT_OWNED(TABLE, FOLD)\ 00137 \ 00138 (DATA) = HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\ 00139 \ 00140 while ((DATA) != NULL) {\ 00141 if (TEST) {\ 00142 break;\ 00143 } else {\ 00144 (DATA) = HASH_GET_NEXT(NAME, DATA);\ 00145 }\ 00146 }\ 00147 } 00148 00149 /**************************************************************** 00150 Gets the nth cell in a hash table. */ 00151 UNIV_INLINE 00152 hash_cell_t* 00153 hash_get_nth_cell( 00154 /*==============*/ 00155 /* out: pointer to cell */ 00156 hash_table_t* table, /* in: hash table */ 00157 ulint n); /* in: cell index */ 00158 /***************************************************************** 00159 Returns the number of cells in a hash table. */ 00160 UNIV_INLINE 00161 ulint 00162 hash_get_n_cells( 00163 /*=============*/ 00164 /* out: number of cells */ 00165 hash_table_t* table); /* in: table */ 00166 /*********************************************************************** 00167 Deletes a struct which is stored in the heap of the hash table, and compacts 00168 the heap. The fold value must be stored in the struct NODE in a field named 00169 'fold'. */ 00170 00171 #define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\ 00172 do {\ 00173 TYPE* node111;\ 00174 TYPE* top_node111;\ 00175 hash_cell_t* cell111;\ 00176 ulint fold111;\ 00177 \ 00178 fold111 = (NODE)->fold;\ 00179 \ 00180 HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\ 00181 \ 00182 top_node111 = (TYPE*)mem_heap_get_top(\ 00183 hash_get_heap(TABLE, fold111),\ 00184 sizeof(TYPE));\ 00185 \ 00186 /* If the node to remove is not the top node in the heap, compact the\ 00187 heap of nodes by moving the top node in the place of NODE. */\ 00188 \ 00189 if (NODE != top_node111) {\ 00190 \ 00191 /* Copy the top node in place of NODE */\ 00192 \ 00193 *(NODE) = *top_node111;\ 00194 \ 00195 cell111 = hash_get_nth_cell(TABLE,\ 00196 hash_calc_hash(top_node111->fold, TABLE));\ 00197 \ 00198 /* Look for the pointer to the top node, to update it */\ 00199 \ 00200 if (cell111->node == top_node111) {\ 00201 /* The top node is the first in the chain */\ 00202 \ 00203 cell111->node = NODE;\ 00204 } else {\ 00205 /* We have to look for the predecessor of the top\ 00206 node */\ 00207 node111 = cell111->node;\ 00208 \ 00209 while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\ 00210 \ 00211 node111 = HASH_GET_NEXT(NAME, node111);\ 00212 }\ 00213 \ 00214 /* Now we have the predecessor node */\ 00215 \ 00216 node111->NAME = NODE;\ 00217 }\ 00218 }\ 00219 \ 00220 /* Free the space occupied by the top node */\ 00221 \ 00222 mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\ 00223 } while (0) 00224 00225 /******************************************************************** 00226 Move all hash table entries from OLD_TABLE to NEW_TABLE.*/ 00227 00228 #define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \ 00229 do {\ 00230 ulint i2222;\ 00231 ulint cell_count2222;\ 00232 \ 00233 cell_count2222 = hash_get_n_cells(OLD_TABLE);\ 00234 \ 00235 for (i2222 = 0; i2222 < cell_count2222; i2222++) {\ 00236 NODE_TYPE* node2222 = HASH_GET_FIRST((OLD_TABLE), i2222);\ 00237 \ 00238 while (node2222) {\ 00239 NODE_TYPE* next2222 = node2222->PTR_NAME;\ 00240 ulint fold2222 = FOLD_FUNC(node2222);\ 00241 \ 00242 HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\ 00243 fold2222, node2222);\ 00244 \ 00245 node2222 = next2222;\ 00246 }\ 00247 }\ 00248 } while (0) 00249 00250 00251 /**************************************************************** 00252 Gets the mutex index for a fold value in a hash table. */ 00253 UNIV_INLINE 00254 ulint 00255 hash_get_mutex_no( 00256 /*==============*/ 00257 /* out: mutex number */ 00258 hash_table_t* table, /* in: hash table */ 00259 ulint fold); /* in: fold */ 00260 /**************************************************************** 00261 Gets the nth heap in a hash table. */ 00262 UNIV_INLINE 00263 mem_heap_t* 00264 hash_get_nth_heap( 00265 /*==============*/ 00266 /* out: mem heap */ 00267 hash_table_t* table, /* in: hash table */ 00268 ulint i); /* in: index of the heap */ 00269 /**************************************************************** 00270 Gets the heap for a fold value in a hash table. */ 00271 UNIV_INLINE 00272 mem_heap_t* 00273 hash_get_heap( 00274 /*==========*/ 00275 /* out: mem heap */ 00276 hash_table_t* table, /* in: hash table */ 00277 ulint fold); /* in: fold */ 00278 /**************************************************************** 00279 Gets the nth mutex in a hash table. */ 00280 UNIV_INLINE 00281 mutex_t* 00282 hash_get_nth_mutex( 00283 /*===============*/ 00284 /* out: mutex */ 00285 hash_table_t* table, /* in: hash table */ 00286 ulint i); /* in: index of the mutex */ 00287 /**************************************************************** 00288 Gets the mutex for a fold value in a hash table. */ 00289 UNIV_INLINE 00290 mutex_t* 00291 hash_get_mutex( 00292 /*===========*/ 00293 /* out: mutex */ 00294 hash_table_t* table, /* in: hash table */ 00295 ulint fold); /* in: fold */ 00296 /**************************************************************** 00297 Reserves the mutex for a fold value in a hash table. */ 00298 00299 void 00300 hash_mutex_enter( 00301 /*=============*/ 00302 hash_table_t* table, /* in: hash table */ 00303 ulint fold); /* in: fold */ 00304 /**************************************************************** 00305 Releases the mutex for a fold value in a hash table. */ 00306 00307 void 00308 hash_mutex_exit( 00309 /*============*/ 00310 hash_table_t* table, /* in: hash table */ 00311 ulint fold); /* in: fold */ 00312 /**************************************************************** 00313 Reserves all the mutexes of a hash table, in an ascending order. */ 00314 00315 void 00316 hash_mutex_enter_all( 00317 /*=================*/ 00318 hash_table_t* table); /* in: hash table */ 00319 /**************************************************************** 00320 Releases all the mutexes of a hash table. */ 00321 00322 void 00323 hash_mutex_exit_all( 00324 /*================*/ 00325 hash_table_t* table); /* in: hash table */ 00326 00327 00328 struct hash_cell_struct{ 00329 void* node; /* hash chain node, NULL if none */ 00330 }; 00331 00332 /* The hash table structure */ 00333 struct hash_table_struct { 00334 ibool adaptive;/* TRUE if this is the hash table of the 00335 adaptive hash index */ 00336 ulint n_cells;/* number of cells in the hash table */ 00337 hash_cell_t* array; /* pointer to cell array */ 00338 ulint n_mutexes;/* if mutexes != NULL, then the number of 00339 mutexes, must be a power of 2 */ 00340 mutex_t* mutexes;/* NULL, or an array of mutexes used to 00341 protect segments of the hash table */ 00342 mem_heap_t** heaps; /* if this is non-NULL, hash chain nodes for 00343 external chaining can be allocated from these 00344 memory heaps; there are then n_mutexes many of 00345 these heaps */ 00346 mem_heap_t* heap; 00347 ulint magic_n; 00348 }; 00349 00350 #define HASH_TABLE_MAGIC_N 76561114 00351 00352 #ifndef UNIV_NONINL 00353 #include "hash0hash.ic" 00354 #endif 00355 00356 #endif
Generated on Sat Sep 9 00:50:26 2006 for MySQL 5.1 by
1.4.7
© 1995-2008 MySQL AB, 2008- Sun Microsystems, Inc.