diff options
Diffstat (limited to 'innobase/include/hash0hash.h')
| -rw-r--r-- | innobase/include/hash0hash.h | 345 |
1 files changed, 345 insertions, 0 deletions
diff --git a/innobase/include/hash0hash.h b/innobase/include/hash0hash.h new file mode 100644 index 00000000000..378925a5bea --- /dev/null +++ b/innobase/include/hash0hash.h @@ -0,0 +1,345 @@ +/****************************************************** +The simple hash table utility + +(c) 1997 Innobase Oy + +Created 5/20/1997 Heikki Tuuri +*******************************************************/ + +#ifndef hash0hash_h +#define hash0hash_h + +#include "univ.i" +#include "mem0mem.h" +#include "sync0sync.h" + +typedef struct hash_table_struct hash_table_t; +typedef struct hash_cell_struct hash_cell_t; + +typedef void* hash_node_t; + +/***************************************************************** +Creates a hash table with >= n array cells. The actual number +of cells is chosen to be a prime number slightly bigger than n. */ + +hash_table_t* +hash_create( +/*========*/ + /* out, own: created table */ + ulint n); /* in: number of array cells */ +/***************************************************************** +Creates a mutex array to protect a hash table. */ + +void +hash_create_mutexes( +/*================*/ + hash_table_t* table, /* in: hash table */ + ulint n_mutexes, /* in: number of mutexes */ + ulint sync_level); /* in: latching order level of the + mutexes: used in the debug version */ +/***************************************************************** +Frees a hash table. */ + +void +hash_table_free( +/*============*/ + hash_table_t* table); /* in, own: hash table */ +/****************************************************************** +Calculates the hash value from a folded value. */ +UNIV_INLINE +ulint +hash_calc_hash( +/*===========*/ + /* out: hashed value */ + ulint fold, /* in: folded value */ + hash_table_t* table); /* in: hash table */ +/*********************************************************************** +Inserts a struct to a hash table. */ + +#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\ +{\ + hash_cell_t* cell3333;\ + TYPE* struct3333;\ +\ + ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));\ +\ + (DATA)->NAME = NULL;\ +\ + cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ +\ + if (cell3333->node == NULL) {\ + cell3333->node = DATA;\ + } else {\ + struct3333 = cell3333->node;\ +\ + while (struct3333->NAME != NULL) {\ +\ + struct3333 = struct3333->NAME;\ + }\ +\ + struct3333->NAME = DATA;\ + }\ +} + +/*********************************************************************** +Deletes a struct from a hash table. */ + +#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\ +{\ + hash_cell_t* cell3333;\ + TYPE* struct3333;\ +\ + ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));\ +\ + cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ +\ + if (cell3333->node == DATA) {\ + cell3333->node = DATA->NAME;\ + } else {\ + struct3333 = cell3333->node;\ +\ + while (struct3333->NAME != DATA) {\ +\ + ut_ad(struct3333)\ + struct3333 = struct3333->NAME;\ + }\ +\ + struct3333->NAME = DATA->NAME;\ + }\ +} + +/*********************************************************************** +Gets the first struct in a hash chain, NULL if none. */ + +#define HASH_GET_FIRST(TABLE, HASH_VAL)\ + (hash_get_nth_cell(TABLE, HASH_VAL)->node) + +/*********************************************************************** +Gets the next struct in a hash chain, NULL if none. */ + +#define HASH_GET_NEXT(NAME, DATA) ((DATA)->NAME) + +/************************************************************************ +Looks for a struct in a hash table. */ +#define HASH_SEARCH(NAME, TABLE, FOLD, DATA, TEST)\ +{\ +\ + ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));\ +\ + (DATA) = HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\ +\ + while ((DATA) != NULL) {\ + if (TEST) {\ + break;\ + } else {\ + (DATA) = HASH_GET_NEXT(NAME, DATA);\ + }\ + }\ +} + +/**************************************************************** +Gets the nth cell in a hash table. */ +UNIV_INLINE +hash_cell_t* +hash_get_nth_cell( +/*==============*/ + /* out: pointer to cell */ + hash_table_t* table, /* in: hash table */ + ulint n); /* in: cell index */ +/***************************************************************** +Returns the number of cells in a hash table. */ +UNIV_INLINE +ulint +hash_get_n_cells( +/*=============*/ + /* out: number of cells */ + hash_table_t* table); /* in: table */ +/*********************************************************************** +Deletes a struct which is stored in the heap of the hash table, and compacts +the heap. The fold value must be stored in the struct NODE in a field named +'fold'. */ + +#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)\ +{\ + TYPE* node111;\ + TYPE* top_node111;\ + hash_cell_t* cell111;\ + ulint fold111;\ +\ + fold111 = (NODE)->fold;\ +\ + HASH_DELETE(TYPE, NAME, TABLE, fold111, NODE);\ +\ + top_node111 = (TYPE*)mem_heap_get_top(\ + hash_get_heap(TABLE, fold111),\ + sizeof(TYPE));\ +\ + /* If the node to remove is not the top node in the heap, compact the\ + heap of nodes by moving the top node in the place of NODE. */\ +\ + if (NODE != top_node111) {\ +\ + /* Copy the top node in place of NODE */\ +\ + *(NODE) = *top_node111;\ +\ + cell111 = hash_get_nth_cell(TABLE,\ + hash_calc_hash(top_node111->fold, TABLE));\ +\ + /* Look for the pointer to the top node, to update it */\ +\ + if (cell111->node == top_node111) {\ + /* The top node is the first in the chain */\ +\ + cell111->node = NODE;\ + } else {\ + /* We have to look for the predecessor of the top\ + node */\ + node111 = cell111->node;\ +\ + while (top_node111 != HASH_GET_NEXT(NAME, node111)) {\ +\ + node111 = HASH_GET_NEXT(NAME, node111);\ + }\ +\ + /* Now we have the predecessor node */\ +\ + node111->NAME = NODE;\ + }\ + }\ +\ + /* Free the space occupied by the top node */\ +\ + mem_heap_free_top(hash_get_heap(TABLE, fold111), sizeof(TYPE));\ +} + +/*********************************************************************** +Calculates the number of stored structs in a hash table. */ + +#define HASH_GET_N_NODES(TYPE, NAME, TABLE, N)\ +{\ + hash_cell_t* cell3333;\ + TYPE* struct3333;\ + ulint i3333;\ +\ + (N) = 0;\ +\ + for (i3333 = 0; i3333 < hash_get_n_cells(TABLE); i3333++) {\ +\ + cell3333 = hash_get_nth_cell(TABLE, i3333);\ +\ + struct3333 = cell3333->node;\ +\ + while (struct3333) {\ +\ + (N) = (N) + 1;\ +\ + struct = HASH_GET_NEXT(NAME, struct3333);\ + }\ + }\ +} + +/**************************************************************** +Gets the mutex index for a fold value in a hash table. */ +UNIV_INLINE +ulint +hash_get_mutex_no( +/*==============*/ + /* out: mutex number */ + hash_table_t* table, /* in: hash table */ + ulint fold); /* in: fold */ +/**************************************************************** +Gets the nth heap in a hash table. */ +UNIV_INLINE +mem_heap_t* +hash_get_nth_heap( +/*==============*/ + /* out: mem heap */ + hash_table_t* table, /* in: hash table */ + ulint i); /* in: index of the heap */ +/**************************************************************** +Gets the heap for a fold value in a hash table. */ +UNIV_INLINE +mem_heap_t* +hash_get_heap( +/*==========*/ + /* out: mem heap */ + hash_table_t* table, /* in: hash table */ + ulint fold); /* in: fold */ +/**************************************************************** +Gets the nth mutex in a hash table. */ +UNIV_INLINE +mutex_t* +hash_get_nth_mutex( +/*===============*/ + /* out: mutex */ + hash_table_t* table, /* in: hash table */ + ulint i); /* in: index of the mutex */ +/**************************************************************** +Gets the mutex for a fold value in a hash table. */ +UNIV_INLINE +mutex_t* +hash_get_mutex( +/*===========*/ + /* out: mutex */ + hash_table_t* table, /* in: hash table */ + ulint fold); /* in: fold */ +/**************************************************************** +Reserves the mutex for a fold value in a hash table. */ + +void +hash_mutex_enter( +/*=============*/ + hash_table_t* table, /* in: hash table */ + ulint fold); /* in: fold */ +/**************************************************************** +Releases the mutex for a fold value in a hash table. */ + +void +hash_mutex_exit( +/*============*/ + hash_table_t* table, /* in: hash table */ + ulint fold); /* in: fold */ +/**************************************************************** +Reserves all the mutexes of a hash table, in an ascending order. */ + +void +hash_mutex_enter_all( +/*=================*/ + hash_table_t* table); /* in: hash table */ +/**************************************************************** +Releases all the mutexes of a hash table. */ + +void +hash_mutex_exit_all( +/*================*/ + hash_table_t* table); /* in: hash table */ + + +struct hash_cell_struct{ + void* node; /* hash chain node, NULL if none */ +}; + +/* The hash table structure */ +struct hash_table_struct { + ulint n_cells;/* number of cells in the hash table */ + hash_cell_t* array; /* pointer to cell array */ + ulint n_mutexes;/* if mutexes != NULL, then the number of + mutexes, must be a power of 2 */ + mutex_t* mutexes;/* NULL, or an array of mutexes used to + protect segments of the hash table */ + mem_heap_t** heaps; /* if this is non-NULL, hash chain nodes for + external chaining can be allocated from these + memory heaps; there are then n_mutexes many of + these heaps */ + mem_heap_t* heap; + ulint magic_n; +}; + +#define HASH_TABLE_MAGIC_N 76561114 + +#ifndef UNIV_NONINL +#include "hash0hash.ic" +#endif + +#endif |