MySQL  8.0.19
Source Code Documentation
hash0hash.h File Reference
#include <stddef.h>
#include "mem0mem.h"
#include "univ.i"
#include "sync0rw.h"
#include "hash0hash.ic"

Go to the source code of this file.

Classes

struct  hash_cell_t
 
struct  hash_table_t
 

Macros

#define hash_create   hash0_create
 
#define HASH_ASSERT_OWN(TABLE, FOLD)
 Assert that the mutex for the table is held. More...
 
#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)
 Inserts a struct to a hash table. More...
 
#define HASH_ASSERT_VALID(DATA)
 
#define HASH_INVALIDATE(DATA, NAME)
 
#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)
 Deletes a struct from a hash table. More...
 
#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. More...
 
#define HASH_GET_NEXT(NAME, DATA)   ((DATA)->NAME)
 Gets the next struct in a hash chain, NULL if none. More...
 
#define HASH_SEARCH(NAME, TABLE, FOLD, TYPE, DATA, ASSERTION, TEST)
 Looks for a struct in a hash table. More...
 
#define HASH_SEARCH_ALL(NAME, TABLE, TYPE, DATA, ASSERTION, TEST)
 Looks for an item in all hash buckets. More...
 
#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. More...
 
#define HASH_MIGRATE(OLD_TABLE, NEW_TABLE, NODE_TYPE, PTR_NAME, FOLD_FUNC)
 Move all hash table entries from OLD_TABLE to NEW_TABLE. More...
 
#define HASH_TABLE_MAGIC_N   76561114
 

Typedefs

typedef void * hash_node_t
 

Enumerations

enum  hash_table_sync_t { HASH_TABLE_SYNC_NONE = 0, HASH_TABLE_SYNC_MUTEX, HASH_TABLE_SYNC_RW_LOCK }
 

Functions

hash_table_thash_create (ulint n)
 Creates a hash table with >= n array cells. More...
 
void hash_create_sync_obj (hash_table_t *table, hash_table_sync_t type, latch_id_t id, ulint n_sync_obj)
 Creates a sync object array array to protect a hash table. More...
 
void hash_table_free (hash_table_t *table)
 Frees a hash table. More...
 
UNIV_INLINE ulint hash_calc_hash (ulint fold, hash_table_t *table)
 Calculates the hash value from a folded value. More...
 
UNIV_INLINE hash_cell_thash_get_nth_cell (hash_table_t *table, ulint n)
 Gets the nth cell in a hash table. More...
 
UNIV_INLINE void hash_table_clear (hash_table_t *table)
 Clears a hash table so that all the cells become empty. More...
 
UNIV_INLINE ulint hash_get_n_cells (hash_table_t *table)
 Returns the number of cells in a hash table. More...
 
UNIV_INLINE ulint hash_get_sync_obj_index (hash_table_t *table, ulint fold)
 Gets the sync object index for a fold value in a hash table. More...
 
UNIV_INLINE mem_heap_thash_get_nth_heap (hash_table_t *table, ulint i)
 Gets the nth heap in a hash table. More...
 
UNIV_INLINE mem_heap_thash_get_heap (hash_table_t *table, ulint fold)
 Gets the heap for a fold value in a hash table. More...
 
UNIV_INLINE ib_mutex_t * hash_get_nth_mutex (hash_table_t *table, ulint i)
 Gets the nth mutex in a hash table. More...
 
UNIV_INLINE rw_lock_thash_get_nth_lock (hash_table_t *table, ulint i)
 Gets the nth rw_lock in a hash table. More...
 
UNIV_INLINE ib_mutex_t * hash_get_mutex (hash_table_t *table, ulint fold)
 Gets the mutex for a fold value in a hash table. More...
 
UNIV_INLINE rw_lock_thash_get_lock (hash_table_t *table, ulint fold)
 Gets the rw_lock for a fold value in a hash table. More...
 
UNIV_INLINE rw_lock_thash_lock_s_confirm (rw_lock_t *hash_lock, hash_table_t *table, ulint fold)
 If not appropriate rw_lock for a fold value in a hash table, relock S-lock the another rw_lock until appropriate for a fold value. More...
 
UNIV_INLINE rw_lock_thash_lock_x_confirm (rw_lock_t *hash_lock, hash_table_t *table, ulint fold)
 If not appropriate rw_lock for a fold value in a hash table, relock X-lock the another rw_lock until appropriate for a fold value. More...
 
void hash_lock_x_all (hash_table_t *table)
 Reserves all the locks of a hash table, in an ascending order. More...
 
void hash_unlock_x_all (hash_table_t *table)
 Releases all the locks of a hash table, in an ascending order. More...
 
void hash_unlock_x_all_but (hash_table_t *table, rw_lock_t *keep_lock)
 Releases all but passed in lock of a hash table,. More...
 

Detailed Description

The simple hash table utility

Created 5/20/1997 Heikki Tuuri

Macro Definition Documentation

◆ HASH_ASSERT_OWN

#define HASH_ASSERT_OWN (   TABLE,
  FOLD 
)
Value:

Assert that the mutex for the table is held.

◆ HASH_ASSERT_VALID

#define HASH_ASSERT_VALID (   DATA)
Value:
do { \
} while (0)

◆ hash_create

#define hash_create   hash0_create

◆ HASH_DELETE

#define HASH_DELETE (   TYPE,
  NAME,
  TABLE,
  FOLD,
  DATA 
)
Value:
do { \
hash_cell_t *cell3333; \
TYPE *struct3333; \
\
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)

Deletes a struct from a hash table.

◆ HASH_DELETE_AND_COMPACT

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

◆ HASH_GET_FIRST

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

◆ HASH_GET_NEXT

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

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

◆ HASH_INSERT

#define HASH_INSERT (   TYPE,
  NAME,
  TABLE,
  FOLD,
  DATA 
)
Value:
do { \
hash_cell_t *cell3333; \
TYPE *struct3333; \
\
(DATA)->NAME = NULL; \
\
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)

Inserts a struct to a hash table.

◆ HASH_INVALIDATE

#define HASH_INVALIDATE (   DATA,
  NAME 
)
Value:
do { \
} while (0)

◆ HASH_MIGRATE

#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)

Move all hash table entries from OLD_TABLE to NEW_TABLE.

◆ HASH_SEARCH

#define HASH_SEARCH (   NAME,
  TABLE,
  FOLD,
  TYPE,
  DATA,
  ASSERTION,
  TEST 
)
Value:
{ \
HASH_ASSERT_OWN(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 a struct in a hash table.

◆ HASH_SEARCH_ALL

#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)

Looks for an item in all hash buckets.

◆ HASH_TABLE_MAGIC_N

#define HASH_TABLE_MAGIC_N   76561114

Typedef Documentation

◆ hash_node_t

typedef void* hash_node_t

Enumeration Type Documentation

◆ hash_table_sync_t

Enumerator
HASH_TABLE_SYNC_NONE 

Don't use any internal synchronization objects for this hash_table.

HASH_TABLE_SYNC_MUTEX 

Use mutexes to control access to this hash_table.

HASH_TABLE_SYNC_RW_LOCK 

Use rw_locks to control access to this hash_table.

Function Documentation

◆ hash_calc_hash()

UNIV_INLINE ulint hash_calc_hash ( ulint  fold,
hash_table_t table 
)

Calculates the hash value from a folded value.

Parameters
[in]foldfolded value
[in]tablehash table
Returns
hashed value

◆ hash_create()

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

The actual number of cells is chosen to be a prime number slightly bigger than n.

Returns
own: created table

◆ hash_create_sync_obj()

void hash_create_sync_obj ( hash_table_t table,
enum hash_table_sync_t  type,
latch_id_t  id,
ulint  n_sync_obj 
)

Creates a sync object array array to protect a hash table.

"::sync_obj" can be mutexes or rw_locks depening on the type of hash table.

Parameters
[in]tablehash table
[in]typeHASH_TABLE_SYNC_MUTEX or HASH_TABLE_SYNC_RW_LOCK
[in]idmutex/rw_lock ID
[in]n_sync_objnumber of sync objects, must be a power of 2

Creates a sync object array array to protect a hash table.

"::sync_obj" can be mutexes or rw_locks depening on the type of hash table.

Parameters
[in]tablehash table
[in]typeHASH_TABLE_SYNC_MUTEX or HASH_TABLE_SYNC_RW_LOCK
[in]idlatch ID
[in]n_sync_objnumber of sync objects, must be a power of 2

◆ hash_get_heap()

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.

Parameters
[in]tablehash table
[in]foldfold
Returns
mem heap

◆ hash_get_lock()

UNIV_INLINE rw_lock_t* hash_get_lock ( hash_table_t table,
ulint  fold 
)

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

Parameters
[in]tablehash table
[in]foldfold
Returns
rw_lock

◆ hash_get_mutex()

UNIV_INLINE ib_mutex_t* hash_get_mutex ( hash_table_t table,
ulint  fold 
)

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

Parameters
[in]tablehash table
[in]foldfold
Returns
mutex

◆ hash_get_n_cells()

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

◆ hash_get_nth_cell()

UNIV_INLINE hash_cell_t* hash_get_nth_cell ( hash_table_t table,
ulint  n 
)

Gets the nth cell in a hash table.

Parameters
[in]tablehash table
[in]ncell index
Returns
pointer to cell

◆ hash_get_nth_heap()

UNIV_INLINE mem_heap_t* hash_get_nth_heap ( hash_table_t table,
ulint  i 
)

Gets the nth heap in a hash table.

Parameters
[in]tablehash table
[in]iindex of the mutex
Returns
mem heap

◆ hash_get_nth_lock()

UNIV_INLINE rw_lock_t* hash_get_nth_lock ( hash_table_t table,
ulint  i 
)

Gets the nth rw_lock in a hash table.

Parameters
[in]tablehash table
[in]iindex of the mutex
Returns
rw_lock

◆ hash_get_nth_mutex()

UNIV_INLINE ib_mutex_t* hash_get_nth_mutex ( hash_table_t table,
ulint  i 
)

Gets the nth mutex in a hash table.

Parameters
[in]tablehash table
[in]iindex of the mutex
Returns
mutex

◆ hash_get_sync_obj_index()

UNIV_INLINE ulint hash_get_sync_obj_index ( hash_table_t table,
ulint  fold 
)

Gets the sync object index for a fold value in a hash table.

Parameters
[in]tablehash table
[in]foldfold
Returns
index

◆ hash_lock_s_confirm()

UNIV_INLINE rw_lock_t* hash_lock_s_confirm ( rw_lock_t hash_lock,
hash_table_t table,
ulint  fold 
)

If not appropriate rw_lock for a fold value in a hash table, relock S-lock the another rw_lock until appropriate for a fold value.

Parameters
[in]hash_locklatched rw_lock to be confirmed
[in]tablehash table
[in]foldfold value
Returns
latched rw_lock

◆ hash_lock_x_all()

void hash_lock_x_all ( hash_table_t table)

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

in: hash table

◆ hash_lock_x_confirm()

UNIV_INLINE rw_lock_t* hash_lock_x_confirm ( rw_lock_t hash_lock,
hash_table_t table,
ulint  fold 
)

If not appropriate rw_lock for a fold value in a hash table, relock X-lock the another rw_lock until appropriate for a fold value.

Parameters
[in]hash_locklatched rw_lock to be confirmed
[in]tablehash table
[in]foldfold value
Returns
latched rw_lock

◆ hash_table_clear()

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

◆ hash_table_free()

void hash_table_free ( hash_table_t table)

Frees a hash table.

in, own: hash table

◆ hash_unlock_x_all()

void hash_unlock_x_all ( hash_table_t table)

Releases all the locks of a hash table, in an ascending order.

in: hash table

◆ hash_unlock_x_all_but()

void hash_unlock_x_all_but ( hash_table_t table,
rw_lock_t keep_lock 
)

Releases all but passed in lock of a hash table,.

in: lock to keep

Parameters
tablein: hash table
NULL
#define NULL
Definition: types.h:55
ut_a
#define ut_a(EXPR)
Abort execution if EXPR does not evaluate to nonzero.
Definition: ut0dbg.h:53
ut_ad
#define ut_ad(EXPR)
Debug assertion.
Definition: ut0dbg.h:65
TABLE
Definition: table.h:1305
HASH_TABLE_SYNC_MUTEX
@ HASH_TABLE_SYNC_MUTEX
Use mutexes to control access to this hash_table.
Definition: hash0hash.h:58
mutex_own
#define mutex_own(M)
Checks that the current thread owns the mutex.
Definition: ut0mutex.h:156
hash_calc_hash
UNIV_INLINE ulint hash_calc_hash(ulint fold, hash_table_t *table)
Calculates the hash value from a folded value.
while
while(-- *argc > 0 &&*(pos= *(++*argv))=='-')
Definition: do_ctype.cc:83
HASH_GET_NEXT
#define HASH_GET_NEXT(NAME, DATA)
Gets the next struct in a hash chain, NULL if none.
Definition: hash0hash.h:171
if
if(!(yy_init))
Definition: lexyy.cc:1144
HASH_INSERT
#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)
Inserts a struct to a hash table.
Definition: hash0hash.h:101
HASH_ASSERT_OWN
#define HASH_ASSERT_OWN(TABLE, FOLD)
Assert that the mutex for the table is held.
Definition: hash0hash.h:92
hash_get_n_cells
UNIV_INLINE ulint hash_get_n_cells(hash_table_t *table)
Returns the number of cells in a hash table.
for
for(i=0;i< 3;i++)
Definition: do_ctype.cc:54
HttpMethod::type
int type
Definition: http_common.h:411
hash_get_nth_cell
UNIV_INLINE hash_cell_t * hash_get_nth_cell(hash_table_t *table, ulint n)
Gets the nth cell in a hash table.
HASH_GET_FIRST
#define HASH_GET_FIRST(TABLE, HASH_VAL)
Gets the first struct in a hash chain, NULL if none.
Definition: hash0hash.h:166
hash_get_mutex
UNIV_INLINE ib_mutex_t * hash_get_mutex(hash_table_t *table, ulint fold)
Gets the mutex for a fold value in a hash table.