diff options
Diffstat (limited to 'storage/xtradb/include/hash0hash.h')
| -rw-r--r-- | storage/xtradb/include/hash0hash.h | 429 |
1 files changed, 429 insertions, 0 deletions
diff --git a/storage/xtradb/include/hash0hash.h b/storage/xtradb/include/hash0hash.h new file mode 100644 index 00000000000..2b3eea62754 --- /dev/null +++ b/storage/xtradb/include/hash0hash.h @@ -0,0 +1,429 @@ +/***************************************************************************** + +Copyright (c) 1997, 2009, Innobase Oy. All Rights Reserved. + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; version 2 of the License. + +This program is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. + +You should have received a copy of the GNU General Public License along with +this program; if not, write to the Free Software Foundation, Inc., 59 Temple +Place, Suite 330, Boston, MA 02111-1307 USA + +*****************************************************************************/ + +/****************************************************** +The simple hash table utility + +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; + +/* Fix Bug #13859: symbol collision between imap/mysql */ +#define hash_create hash0_create + +/***************************************************************** +Creates a hash table with >= n array cells. The actual number +of cells is chosen to be a prime number slightly bigger than n. */ +UNIV_INTERN +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. */ +UNIV_INTERN +void +hash_create_mutexes_func( +/*=====================*/ + hash_table_t* table, /* in: hash table */ +#ifdef UNIV_SYNC_DEBUG + ulint sync_level, /* in: latching order level of the + mutexes: used in the debug version */ +#endif /* UNIV_SYNC_DEBUG */ + ulint n_mutexes); /* in: number of mutexes */ +#ifdef UNIV_SYNC_DEBUG +# define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,level,n) +#else /* UNIV_SYNC_DEBUG */ +# define hash_create_mutexes(t,n,level) hash_create_mutexes_func(t,n) +#endif /* UNIV_SYNC_DEBUG */ + +/***************************************************************** +Frees a hash table. */ +UNIV_INTERN +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 */ +/************************************************************************ +Assert that the mutex for the table in a hash operation is owned. */ +#define HASH_ASSERT_OWNED(TABLE, FOLD) \ +ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD))); + +/*********************************************************************** +Inserts a struct to a hash table. */ + +#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\ +do {\ + hash_cell_t* cell3333;\ + TYPE* struct3333;\ +\ + HASH_ASSERT_OWNED(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 = (TYPE*) cell3333->node;\ +\ + while (struct3333->NAME != NULL) {\ +\ + struct3333 = (TYPE*) struct3333->NAME;\ + }\ +\ + struct3333->NAME = DATA;\ + }\ +} while (0) + +#ifdef UNIV_HASH_DEBUG +# define HASH_ASSERT_VALID(DATA) ut_a((void*) (DATA) != (void*) -1) +# define HASH_INVALIDATE(DATA, NAME) DATA->NAME = (void*) -1 +#else +# define HASH_ASSERT_VALID(DATA) do {} while (0) +# define HASH_INVALIDATE(DATA, NAME) do {} while (0) +#endif + +/*********************************************************************** +Deletes a struct from a hash table. */ + +#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\ +do {\ + hash_cell_t* cell3333;\ + TYPE* struct3333;\ +\ + HASH_ASSERT_OWNED(TABLE, FOLD)\ +\ + cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\ +\ + if (cell3333->node == DATA) {\ + HASH_ASSERT_VALID(DATA->NAME);\ + cell3333->node = DATA->NAME;\ + } else {\ + struct3333 = (TYPE*) cell3333->node;\ +\ + while (struct3333->NAME != DATA) {\ +\ + struct3333 = (TYPE*) struct3333->NAME;\ + ut_a(struct3333);\ + }\ +\ + struct3333->NAME = DATA->NAME;\ + }\ + HASH_INVALIDATE(DATA, NAME);\ +} while (0) + +/*********************************************************************** +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, TYPE, DATA, ASSERTION, TEST)\ +{\ +\ + HASH_ASSERT_OWNED(TABLE, FOLD)\ +\ + (DATA) = (TYPE) HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));\ + HASH_ASSERT_VALID(DATA);\ +\ + while ((DATA) != NULL) {\ + ASSERTION;\ + if (TEST) {\ + break;\ + } else {\ + HASH_ASSERT_VALID(HASH_GET_NEXT(NAME, DATA));\ + (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA);\ + }\ + }\ +} + +/************************************************************************ +Looks for an item in all hash buckets. */ +#define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST) \ +do { \ + ulint i3333; \ + \ + for (i3333 = (TABLE)->n_cells; i3333--; ) { \ + (DATA) = (TYPE) HASH_GET_FIRST(TABLE, i3333); \ + \ + while ((DATA) != NULL) { \ + HASH_ASSERT_VALID(DATA); \ + ASSERTION; \ + \ + if (TEST) { \ + break; \ + } \ + \ + (DATA) = (TYPE) HASH_GET_NEXT(NAME, DATA); \ + } \ + \ + if ((DATA) != NULL) { \ + break; \ + } \ + } \ +} while (0) + +/**************************************************************** +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 */ + +/***************************************************************** +Clears a hash table so that all the cells become empty. */ +UNIV_INLINE +void +hash_table_clear( +/*=============*/ + hash_table_t* table); /* in/out: hash table */ + +/***************************************************************** +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)\ +do {\ + 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));\ +} while (0) + +/******************************************************************** +Move all hash table entries from OLD_TABLE to NEW_TABLE.*/ + +#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC) \ +do {\ + ulint i2222;\ + ulint cell_count2222;\ +\ + cell_count2222 = hash_get_n_cells(OLD_TABLE);\ +\ + for (i2222 = 0; i2222 < cell_count2222; i2222++) {\ + NODE_TYPE* node2222 = HASH_GET_FIRST((OLD_TABLE), i2222);\ +\ + while (node2222) {\ + NODE_TYPE* next2222 = node2222->PTR_NAME;\ + ulint fold2222 = FOLD_FUNC(node2222);\ +\ + HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\ + fold2222, node2222);\ +\ + node2222 = next2222;\ + }\ + }\ +} while (0) + + +/**************************************************************** +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. */ +UNIV_INTERN +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. */ +UNIV_INTERN +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. */ +UNIV_INTERN +void +hash_mutex_enter_all( +/*=================*/ + hash_table_t* table); /* in: hash table */ +/**************************************************************** +Releases all the mutexes of a hash table. */ +UNIV_INTERN +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 { +#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG + ibool adaptive;/* TRUE if this is the hash table of the + adaptive hash index */ +#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */ + 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 |