Drizzled Public API Documentation

hash0hash.h File Reference
#include "univ.i"
#include "mem0mem.h"
#include "sync0sync.h"

Go to the source code of this file.

Classes

struct  hash_cell_struct
 
struct  hash_table_struct
 

Macros

#define hash0hash_h
 
#define hash_create   hash0_create
 
#define hash_create_mutexes(t, n, level)   hash_create_mutexes_func(t,n)
 
#define HASH_ASSERT_OWNED(TABLE, FOLD)   ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));
 
#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)
 
#define HASH_ASSERT_VALID(DATA)   do {} while (0)
 
#define HASH_INVALIDATE(DATA, NAME)   do {} while (0)
 
#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)
 
#define HASH_GET_FIRST(TABLE, HASH_VAL)   (hash_get_nth_cell(TABLE, HASH_VAL)->node)
 
#define HASH_GET_NEXT(NAME, DATA)   ((DATA)->NAME)
 
#define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)
 
#define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST)
 
#define HASH_DELETE_AND_COMPACT(TYPE, NAME, TABLE, NODE)
 
#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC)
 

Typedefs

typedef struct hash_table_struct hash_table_t
 
typedef struct hash_cell_struct hash_cell_t
 
typedef void * hash_node_t
 

Functions

UNIV_INTERN hash_table_thash_create (ulint n)
 
UNIV_INTERN void hash_create_mutexes_func (hash_table_t *table, ulint n_mutexes)
 
UNIV_INTERN void hash_table_free (hash_table_t *table)
 
UNIV_INLINE ulint hash_calc_hash (ulint fold, hash_table_t *table)
 
UNIV_INLINE hash_cell_thash_get_nth_cell (hash_table_t *table, ulint n)
 
UNIV_INLINE void hash_table_clear (hash_table_t *table)
 
UNIV_INLINE ulint hash_get_n_cells (hash_table_t *table)
 
UNIV_INLINE ulint hash_get_mutex_no (hash_table_t *table, ulint fold)
 
UNIV_INLINE mem_heap_thash_get_nth_heap (hash_table_t *table, ulint i)
 
UNIV_INLINE mem_heap_thash_get_heap (hash_table_t *table, ulint fold)
 
UNIV_INLINE mutex_thash_get_nth_mutex (hash_table_t *table, ulint i)
 
UNIV_INLINE mutex_thash_get_mutex (hash_table_t *table, ulint fold)
 
UNIV_INTERN void hash_mutex_enter (hash_table_t *table, ulint fold)
 
UNIV_INTERN void hash_mutex_exit (hash_table_t *table, ulint fold)
 
UNIV_INTERN void hash_mutex_enter_all (hash_table_t *table)
 
UNIV_INTERN void hash_mutex_exit_all (hash_table_t *table)
 

Detailed Description

The simple hash table utility

Created 5/20/1997 Heikki Tuuri

Definition in file hash0hash.h.

Macro Definition Documentation

#define HASH_ASSERT_OWNED (   TABLE,
  FOLD 
)    ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));

Assert that the mutex for the table in a hash operation is owned.

Definition at line 92 of file hash0hash.h.

#define HASH_DELETE (   TYPE,
  NAME,
  TABLE,
  FOLD,
  DATA 
)
Value:
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)
#define HASH_ASSERT_OWNED(TABLE, FOLD)
Definition: hash0hash.h:92
UNIV_INLINE ulint hash_calc_hash(ulint fold, hash_table_t *table)
#define ut_a(EXPR)
Definition: ut0dbg.h:105
UNIV_INLINE hash_cell_t * hash_get_nth_cell(hash_table_t *table, ulint n)

Deletes a struct from a hash table.

Definition at line 137 of file hash0hash.h.

Referenced by buf_relocate(), dict_table_change_id_in_cache(), dict_table_remove_from_cache(), and dict_table_rename_in_cache().

#define HASH_DELETE_AND_COMPACT (   TYPE,
  NAME,
  TABLE,
  NODE 
)

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'.

Definition at line 252 of file hash0hash.h.

#define HASH_GET_FIRST (   TABLE,
  HASH_VAL 
)    (hash_get_nth_cell(TABLE, HASH_VAL)->node)

Gets the first struct in a hash chain, NULL if none.

Definition at line 166 of file hash0hash.h.

Referenced by fil_validate(), and recv_apply_hashed_log_recs().

#define HASH_GET_NEXT (   NAME,
  DATA 
)    ((DATA)->NAME)

Gets the next struct in a hash chain, NULL if none.

Definition at line 172 of file hash0hash.h.

Referenced by fil_validate(), and recv_apply_hashed_log_recs().

#define HASH_INSERT (   TYPE,
  NAME,
  TABLE,
  FOLD,
  DATA 
)
Value:
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)
#define HASH_ASSERT_OWNED(TABLE, FOLD)
Definition: hash0hash.h:92
UNIV_INLINE ulint hash_calc_hash(ulint fold, hash_table_t *table)
UNIV_INLINE hash_cell_t * hash_get_nth_cell(hash_table_t *table, ulint n)

Inserts a struct to a hash table.

Definition at line 101 of file hash0hash.h.

Referenced by buf_LRU_free_block(), buf_page_init_for_read(), buf_pool_watch_set(), buf_relocate(), dict_table_add_to_cache(), dict_table_change_id_in_cache(), dict_table_rename_in_cache(), fil_space_create(), get_share(), and ha_storage_put_memlim().

#define HASH_MIGRATE (   OLD_TABLE,
  NEW_TABLE,
  NODE_TYPE,
  PTR_NAME,
  FOLD_FUNC 
)
Value:
do {\
ulint i2222;\
ulint cell_count2222;\
\
cell_count2222 = hash_get_n_cells(OLD_TABLE);\
\
for (i2222 = 0; i2222 < cell_count2222; i2222++) {\
NODE_TYPE* node2222 = static_cast<NODE_TYPE *>(HASH_GET_FIRST((OLD_TABLE), i2222));\
\
while (node2222) {\
NODE_TYPE* next2222 = static_cast<NODE_TYPE *>(node2222->PTR_NAME);\
ulint fold2222 = FOLD_FUNC(node2222);\
HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE),\
fold2222, node2222);\
\
node2222 = next2222;\
}\
}\
} while (0)
#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)
Definition: hash0hash.h:101
#define HASH_GET_FIRST(TABLE, HASH_VAL)
Definition: hash0hash.h:166
UNIV_INLINE ulint hash_get_n_cells(hash_table_t *table)

Move all hash table entries from OLD_TABLE to NEW_TABLE.

Definition at line 310 of file hash0hash.h.

#define HASH_SEARCH (   NAME,
  TABLE,
  FOLD,
  TYPE,
  DATA,
  ASSERTION,
  TEST 
)
Value:
{\
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);\
}\
}\
}
#define HASH_ASSERT_OWNED(TABLE, FOLD)
Definition: hash0hash.h:92
UNIV_INLINE ulint hash_calc_hash(ulint fold, hash_table_t *table)
#define HASH_GET_NEXT(NAME, DATA)
Definition: hash0hash.h:172
#define HASH_GET_FIRST(TABLE, HASH_VAL)
Definition: hash0hash.h:166

Looks for a struct in a hash table.

Definition at line 176 of file hash0hash.h.

Referenced by dict_table_add_to_cache(), dict_table_rename_in_cache(), and get_share().

#define HASH_SEARCH_ALL (   NAME,
  TABLE,
  TYPE,
  DATA,
  ASSERTION,
  TEST 
)
Value:
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)
#define HASH_GET_NEXT(NAME, DATA)
Definition: hash0hash.h:172
#define HASH_GET_FIRST(TABLE, HASH_VAL)
Definition: hash0hash.h:166

Looks for an item in all hash buckets.

Definition at line 197 of file hash0hash.h.

Referenced by dict_table_add_to_cache().

Function Documentation

UNIV_INLINE ulint hash_calc_hash ( ulint  fold,
hash_table_t table 
)

Calculates the hash value from a folded value.

Returns
hashed value in: hash table
Parameters
foldin: folded value

Referenced by ha_insert_for_fold_func().

UNIV_INTERN hash_table_t* hash_create ( ulint  n)

Creates a hash table with >= n array cells. The actual number of cells is chosen to be a prime number slightly bigger than n.

Returns
own: created table in: number of array cells

Creates a hash table with >= n array cells. The actual number of cells is chosen to be a prime number slightly bigger than n.

Returns
own: created table
Parameters
nin: number of array cells

Definition at line 102 of file hash0hash.cc.

References hash_table_struct::array, hash_table_clear(), hash_table_struct::heaps, ut_d, ut_find_prime(), and ut_malloc().

Referenced by fil_init(), ha_create_func(), innobase_init(), lock_sys_create(), recv_sys_init(), and trx_i_s_cache_init().

UNIV_INTERN void hash_create_mutexes_func ( hash_table_t table,
ulint  n_mutexes 
)

Creates a mutex array to protect a hash table. in: number of mutexes

Creates a mutex array to protect a hash table.

Parameters
tablein: hash table
n_mutexesin: number of mutexes, must be a power of 2

Definition at line 158 of file hash0hash.cc.

References ut_a, ut_ad, and ut_is_2pow.

UNIV_INLINE mem_heap_t* hash_get_heap ( hash_table_t table,
ulint  fold 
)

Gets the heap for a fold value in a hash table.

Returns
mem heap in: fold
Parameters
tablein: hash table

Referenced by ha_insert_for_fold_func().

UNIV_INLINE mutex_t* hash_get_mutex ( hash_table_t table,
ulint  fold 
)

Gets the mutex for a fold value in a hash table.

Returns
mutex in: fold
Parameters
tablein: hash table

Referenced by hash_mutex_enter(), and hash_mutex_exit().

UNIV_INLINE ulint hash_get_mutex_no ( hash_table_t table,
ulint  fold 
)

Gets the mutex index for a fold value in a hash table.

Returns
mutex number in: fold
Parameters
tablein: hash table
UNIV_INLINE ulint hash_get_n_cells ( hash_table_t table)

Returns the number of cells in a hash table.

Returns
number of cells in: table

Referenced by fil_validate(), ha_clear(), ha_print_info(), and recv_apply_hashed_log_recs().

UNIV_INLINE hash_cell_t* hash_get_nth_cell ( hash_table_t table,
ulint  n 
)

Gets the nth cell in a hash table.

Returns
pointer to cell in: cell index
Parameters
tablein: hash table

Referenced by ha_clear(), ha_insert_for_fold_func(), and ha_print_info().

UNIV_INLINE mem_heap_t* hash_get_nth_heap ( hash_table_t table,
ulint  i 
)

Gets the nth heap in a hash table.

Returns
mem heap in: index of the heap
Parameters
tablein: hash table
UNIV_INLINE mutex_t* hash_get_nth_mutex ( hash_table_t table,
ulint  i 
)

Gets the nth mutex in a hash table.

Returns
mutex in: index of the mutex
Parameters
tablein: hash table
UNIV_INTERN void hash_mutex_enter ( hash_table_t table,
ulint  fold 
)

Reserves the mutex for a fold value in a hash table. in: fold

Reserves the mutex for a fold value in a hash table.

Parameters
tablein: hash table
foldin: fold

Definition at line 43 of file hash0hash.cc.

References hash_get_mutex().

UNIV_INTERN void hash_mutex_enter_all ( hash_table_t table)

Reserves all the mutexes of a hash table, in an ascending order. in: hash table

Reserves all the mutexes of a hash table, in an ascending order.

Parameters
tablein: hash table

Definition at line 67 of file hash0hash.cc.

UNIV_INTERN void hash_mutex_exit ( hash_table_t table,
ulint  fold 
)

Releases the mutex for a fold value in a hash table. in: fold

Releases the mutex for a fold value in a hash table.

Parameters
tablein: hash table
foldin: fold

Definition at line 55 of file hash0hash.cc.

References hash_get_mutex().

UNIV_INTERN void hash_mutex_exit_all ( hash_table_t table)

Releases all the mutexes of a hash table. in: hash table

Releases all the mutexes of a hash table.

Parameters
tablein: hash table

Definition at line 83 of file hash0hash.cc.

UNIV_INLINE void hash_table_clear ( hash_table_t table)

Clears a hash table so that all the cells become empty. in/out: hash table

Referenced by hash_create().

UNIV_INTERN void hash_table_free ( hash_table_t table)

Frees a hash table. in, own: hash table

Frees a hash table.

Parameters
tablein, own: hash table

Definition at line 139 of file hash0hash.cc.

References hash_table_struct::array, mem_free, ut_a, ut_ad, and ut_free().

Referenced by btr_search_sys_free(), fil_close(), lock_sys_close(), recv_sys_close(), recv_sys_mem_free(), and trx_i_s_cache_free().