MySQL 9.5.0
Source Code Documentation
Classes | Macros | Typedefs | Enumerations | Functions
hash0hash.h File Reference

The simple hash table utility. More...

#include <stddef.h>
#include "mem0mem.h"
#include "univ.i"
#include "ut0rnd.h"
#include "sync0rw.h"
#include "hash0hash.ic"

Go to the source code of this file.

Classes

struct  hash_cell_t
 
class  hash_table_t
 

Macros

#define HASH_INSERT(TYPE, NAME, TABLE, HASH_VALUE, 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, HASH_VALUE, DATA)
 Deletes a struct from a hash table. 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, HASH_VALUE, 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 cells. 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, HASH_FUNC)
 Move all hash table entries from OLD_TABLE to NEW_TABLE. More...
 

Typedefs

typedef void * hash_node_t
 

Enumerations

enum  hash_table_sync_t { HASH_TABLE_SYNC_NONE = 0 , HASH_TABLE_SYNC_RW_LOCK }
 

Functions

void hash_create_sync_obj (hash_table_t *table, latch_id_t id, size_t n_sync_obj)
 Creates a sync object array to protect a hash table. More...
 
static uint64_t hash_calc_cell_id (uint64_t hash_value, hash_table_t const *table)
 Calculates the cell index from a hashed value for a specified hash table. More...
 
static hash_cell_t * hash_get_nth_cell (hash_table_t *table, size_t n)
 Gets the nth cell in a hash table. More...
 
static void *& hash_get_first (hash_table_t *table, size_t cell_id)
 Gets the first struct in a hash chain, NULL if none. More...
 
static void hash_table_clear (hash_table_t *table)
 Clears a hash table so that all the cells become empty. More...
 
static size_t hash_get_n_cells (hash_table_t const *table)
 Returns the number of cells in a hash table. More...
 
static uint64_t hash_get_sync_obj_index (hash_table_t *table, uint64_t hash_value)
 Gets the sync object index for a hash value in a hash table. More...
 
static mem_heap_t * hash_get_heap (hash_table_t *table)
 Gets the heap for a hash value in a hash table. More...
 
static rw_lock_t * hash_get_nth_lock (hash_table_t *table, size_t i)
 Gets the nth rw_lock in a hash table. More...
 
static rw_lock_t * hash_get_lock (hash_table_t *table, uint64_t hash_value)
 Gets the rw_lock for a hash value in a hash table. More...
 
static rw_lock_t * hash_lock_s_confirm (rw_lock_t *hash_lock, hash_table_t *table, uint64_t hash_value)
 If not appropriate rw_lock for a hash value in a hash table, relock S-lock the another rw_lock until appropriate for a hash value. More...
 
static rw_lock_t * hash_lock_x_confirm (rw_lock_t *hash_lock, hash_table_t *table, uint64_t hash_value)
 If not appropriate rw_lock for a hash value in a hash table, relock X-lock the another rw_lock until appropriate for a hash value. More...
 
bool hash_lock_has_all_x (const hash_table_t *table)
 Verifies that the current thread holds X-latch on all shards. 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_VALID

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

◆ HASH_DELETE

#define HASH_DELETE (   TYPE,
  NAME,
  TABLE,
  HASH_VALUE,
  DATA 
)
Value:
do { \
hash_cell_t *cell3333; \
TYPE *struct3333; \
const uint64_t hash_value3333 = HASH_VALUE; \
\
hash_assert_can_modify(TABLE, hash_value3333); \
\
cell3333 = \
hash_get_nth_cell(TABLE, hash_calc_cell_id(hash_value3333, 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)
hash_calc_cell_id
static uint64_t hash_calc_cell_id(uint64_t hash_value, hash_table_t const *table)
Calculates the cell index from a hashed value for a specified hash table.
hash_assert_can_modify
static void hash_assert_can_modify(hash_table_t *table, uint64_t hash_value)
Assert that the synchronization object in a hash operation involving possible change in the hash tabl...
Definition: hash0hash.ic:176
if
if(!(yy_init))
Definition: lexyy.cc:1144
TABLE
Definition: table.h:1435
ut_a
#define ut_a(EXPR)
Abort execution if EXPR does not evaluate to nonzero.
Definition: ut0dbg.h:93
NAME
#define NAME(f)
Definition: xcom_base.cc:4185

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 hash value must be stored in the struct NODE in a field named 'hash_value'.

◆ 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,
  HASH_VALUE,
  DATA 
)
Value:
do { \
hash_cell_t *cell3333; \
TYPE *struct3333; \
const uint64_t hash_value3333 = HASH_VALUE; \
\
hash_assert_can_modify(TABLE, hash_value3333); \
\
(DATA)->NAME = NULL; \
\
cell3333 = \
hash_get_nth_cell(TABLE, hash_calc_cell_id(hash_value3333, 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)
NULL
#define NULL
Definition: types.h:55

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,
  HASH_FUNC 
)
Value:
do { \
size_t i2222; \
size_t 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); \
uint64_t hash_value2222 = HASH_FUNC(node2222); \
\
HASH_INSERT(NODE_TYPE, PTR_NAME, (NEW_TABLE), hash_value2222, \
node2222); \
\
node2222 = next2222; \
} \
} \
} while (0)
HASH_INSERT
#define HASH_INSERT(TYPE, NAME, TABLE, HASH_VALUE, DATA)
Inserts a struct to a hash table.
Definition: hash0hash.h:90
hash_get_first
static void *& hash_get_first(hash_table_t *table, size_t cell_id)
Gets the first struct in a hash chain, NULL if none.
Definition: hash0hash.h:159
hash_get_n_cells
static size_t hash_get_n_cells(hash_table_t const *table)
Returns the number of cells in a hash table.

Move all hash table entries from OLD_TABLE to NEW_TABLE.

◆ HASH_SEARCH

#define HASH_SEARCH (   NAME,
  TABLE,
  HASH_VALUE,
  TYPE,
  DATA,
  ASSERTION,
  TEST 
)
Value:
{ \
const uint64_t hash_value3333 = HASH_VALUE; \
\
hash_assert_can_search(TABLE, hash_value3333); \
\
(DATA) = \
(TYPE)hash_get_first(TABLE, hash_calc_cell_id(hash_value3333, 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); \
} \
} \
}
HASH_GET_NEXT
#define HASH_GET_NEXT(NAME, DATA)
Gets the next struct in a hash chain, NULL if none.
Definition: hash0hash.h:165
hash_assert_can_search
static void hash_assert_can_search(hash_table_t *table, uint64_t hash_value)
Assert that the synchronization object in a hash search operation is held.
Definition: hash0hash.ic:195

Looks for a struct in a hash table.

◆ HASH_SEARCH_ALL

#define HASH_SEARCH_ALL (   NAME,
  TABLE,
  TYPE,
  DATA,
  ASSERTION,
  TEST 
)
Value:
do { \
size_t i3333; \
\
for (i3333 = (TABLE)->get_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 cells.

Typedef Documentation

◆ hash_node_t

typedef void* hash_node_t

Enumeration Type Documentation

◆ hash_table_sync_t

enum hash_table_sync_t
Enumerator
HASH_TABLE_SYNC_NONE 

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

HASH_TABLE_SYNC_RW_LOCK 

Use rw_locks to control access to this hash_table.

Function Documentation

◆ hash_calc_cell_id()

static uint64_t hash_calc_cell_id ( uint64_t  hash_value,
hash_table_t const *  table 
)
inlinestatic

Calculates the cell index from a hashed value for a specified hash table.

Parameters
[in]hash_valuehashed value
[in]tablehash table
Returns
cell index for specified hash table

◆ hash_create_sync_obj()

void hash_create_sync_obj ( hash_table_t *  table,
latch_id_t  id,
size_t  n_sync_obj 
)

Creates a sync object array to protect a hash table.

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

◆ hash_get_first()

static void *& hash_get_first ( hash_table_t *  table,
size_t  cell_id 
)
inlinestatic

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

◆ hash_get_heap()

static mem_heap_t * hash_get_heap ( hash_table_t *  table)
inlinestatic

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

Parameters
[in]tablehash table
Returns
mem heap

◆ hash_get_lock()

static rw_lock_t * hash_get_lock ( hash_table_t *  table,
uint64_t  hash_value 
)
inlinestatic

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

Parameters
[in]tablehash table
[in]hash_valuehash value
Returns
rw_lock

◆ hash_get_n_cells()

static size_t hash_get_n_cells ( hash_table_t const *  table)
inlinestatic

Returns the number of cells in a hash table.

Returns
number of cells in: table

◆ hash_get_nth_cell()

static hash_cell_t * hash_get_nth_cell ( hash_table_t *  table,
size_t  n 
)
inlinestatic

Gets the nth cell in a hash table.

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

◆ hash_get_nth_lock()

static rw_lock_t * hash_get_nth_lock ( hash_table_t *  table,
size_t  i 
)
inlinestatic

Gets the nth rw_lock in a hash table.

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

◆ hash_get_sync_obj_index()

static uint64_t hash_get_sync_obj_index ( hash_table_t *  table,
uint64_t  hash_value 
)
inlinestatic

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

Parameters
[in]tablehash table
[in]hash_valuehash value
Returns
index

◆ hash_lock_has_all_x()

bool hash_lock_has_all_x ( const hash_table_t *  table)

Verifies that the current thread holds X-latch on all shards.

Assumes type==HASH_TABLE_SYNC_RW_LOCK.

Parameters
[in]tablethe table in question
Returns
true iff the current thread holds X-latch on all shards

◆ hash_lock_s_confirm()

static rw_lock_t * hash_lock_s_confirm ( rw_lock_t *  hash_lock,
hash_table_t *  table,
uint64_t  hash_value 
)
inlinestatic

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

Parameters
[in]hash_locklatched rw_lock to be confirmed
[in]tablehash table
[in]hash_valuehash 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

Parameters
tablein: hash table

◆ hash_lock_x_confirm()

static rw_lock_t * hash_lock_x_confirm ( rw_lock_t *  hash_lock,
hash_table_t *  table,
uint64_t  hash_value 
)
inlinestatic

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

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

◆ hash_table_clear()

static void hash_table_clear ( hash_table_t *  table)
inlinestatic

Clears a hash table so that all the cells become empty.

in/out: 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

Parameters
tablein: 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,.

Parameters
[in]tableHash table
[in]keep_lockLock to keep
Parameters
tablein: hash table
keep_lockin: lock to keep