Drizzled Public API Documentation

hash0hash.h
Go to the documentation of this file.
00001 /*****************************************************************************
00002 
00003 Copyright (C) 1997, 2009, Innobase Oy. All Rights Reserved.
00004 
00005 This program is free software; you can redistribute it and/or modify it under
00006 the terms of the GNU General Public License as published by the Free Software
00007 Foundation; version 2 of the License.
00008 
00009 This program is distributed in the hope that it will be useful, but WITHOUT
00010 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00011 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
00012 
00013 You should have received a copy of the GNU General Public License along with
00014 this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
00015 St, Fifth Floor, Boston, MA 02110-1301 USA
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 /* !UNIV_HOTBACKUP */
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 /* Fix Bug #13859: symbol collision between imap/mysql */
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 /* UNIV_SYNC_DEBUG */
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 /* UNIV_SYNC_DEBUG */
00069 # define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,n)
00070 #endif /* UNIV_SYNC_DEBUG */
00071 #endif /* !UNIV_HOTBACKUP */
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 /* !UNIV_HOTBACKUP */
00095 # define HASH_ASSERT_OWNED(TABLE, FOLD)
00096 #endif /* !UNIV_HOTBACKUP */
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   /* If the node to remove is not the top node in the heap, compact the\
00268   heap of nodes by moving the top node in the place of NODE. */\
00269 \
00270   if (NODE != top_node111) {\
00271 \
00272     /* Copy the top node in place of NODE */\
00273 \
00274     *(NODE) = *top_node111;\
00275 \
00276     cell111 = hash_get_nth_cell(TABLE,\
00277         hash_calc_hash(top_node111->fold, TABLE));\
00278 \
00279     /* Look for the pointer to the top node, to update it */\
00280 \
00281     if (cell111->node == top_node111) {\
00282       /* The top node is the first in the chain */\
00283 \
00284       cell111->node = NODE;\
00285     } else {\
00286       /* We have to look for the predecessor of the top\
00287       node */\
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       /* Now we have the predecessor node */\
00296 \
00297       node111->NAME = NODE;\
00298     }\
00299   }\
00300 \
00301   /* Free the space occupied by the top node */\
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 /* !UNIV_HOTBACKUP */
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 /* !UNIV_HOTBACKUP */
00412 
00413 struct hash_cell_struct{
00414   void* node; 
00415 };
00416 
00417 /* The hash table structure */
00418 struct hash_table_struct {
00419 #if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
00420 # ifndef UNIV_HOTBACKUP
00421   ibool   adaptive;/* TRUE if this is the hash table of the
00422         adaptive hash index */
00423 # endif /* !UNIV_HOTBACKUP */
00424 #endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
00425   ulint   n_cells;/* number of cells in the hash table */
00426   hash_cell_t*  array;  
00427 #ifndef UNIV_HOTBACKUP
00428   ulint   n_mutexes;/* if mutexes != NULL, then the number of
00429         mutexes, must be a power of 2 */
00430   mutex_t*  mutexes;/* NULL, or an array of mutexes used to
00431         protect segments of the hash table */
00432   mem_heap_t**  heaps;  
00436 #endif /* !UNIV_HOTBACKUP */
00437   mem_heap_t* heap;
00438 #ifdef UNIV_DEBUG
00439   ulint   magic_n;
00440 # define HASH_TABLE_MAGIC_N 76561114
00441 #endif /* UNIV_DEBUG */
00442 };
00443 
00444 #ifndef UNIV_NONINL
00445 #include "hash0hash.ic"
00446 #endif
00447 
00448 #endif