drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
hash0hash.h File Reference
#include "univ.i"
#include "mem0mem.h"
#include "sync0sync.h"
Include dependency graph for hash0hash.h:
This graph shows which files directly or indirectly include this file:

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)
#define HASH_ASSERT_OWNED(TABLE, FOLD)
#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)
#define HASH_ASSERT_VALID(DATA)
#define HASH_INVALIDATE(DATA, NAME)
#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)
#define HASH_GET_FIRST(TABLE, HASH_VAL)
#define HASH_GET_NEXT(NAME, DATA)
#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_t * hash_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_t * hash_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_t * hash_get_nth_heap (hash_table_t *table, ulint i)
UNIV_INLINE mem_heap_t * hash_get_heap (hash_table_t *table, ulint fold)
UNIV_INLINE mutex_t * hash_get_nth_mutex (hash_table_t *table, ulint i)
UNIV_INLINE mutex_t * hash_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

◆ hash0hash_h

#define hash0hash_h

Definition at line 28 of file hash0hash.h.

◆ HASH_ASSERT_OWNED

#define HASH_ASSERT_OWNED ( TABLE,
FOLD )
Value:
ut_ad(!(TABLE)->mutexes || mutex_own(hash_get_mutex(TABLE, FOLD)));
UNIV_INLINE mutex_t * hash_get_mutex(hash_table_t *table, ulint fold)
#define ut_ad(EXPR)
Definition ut0dbg.h:127

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

Definition at line 92 of file hash0hash.h.

◆ HASH_ASSERT_VALID

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

Definition at line 130 of file hash0hash.h.

◆ hash_create

#define hash_create   hash0_create

Definition at line 42 of file hash0hash.h.

◆ hash_create_mutexes

#define hash_create_mutexes ( t,
n,
level )
Value:
hash_create_mutexes_func(t,n)

Definition at line 69 of file hash0hash.h.

◆ HASH_DELETE

#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)
UNIV_INLINE hash_cell_t * hash_get_nth_cell(hash_table_t *table, ulint n)
UNIV_INLINE ulint hash_calc_hash(ulint fold, hash_table_t *table)

Deletes a struct from a hash table.

Definition at line 137 of file hash0hash.h.

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

Definition at line 252 of file hash0hash.h.

◆ HASH_GET_FIRST

#define HASH_GET_FIRST ( TABLE,
HASH_VAL )
Value:
(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.

◆ HASH_GET_NEXT

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

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

Definition at line 172 of file hash0hash.h.

◆ HASH_INSERT

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

Inserts a struct to a hash table.

Definition at line 101 of file hash0hash.h.

◆ HASH_INVALIDATE

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

Definition at line 131 of file hash0hash.h.

◆ 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)
UNIV_INLINE ulint hash_get_n_cells(hash_table_t *table)
#define HASH_GET_FIRST(TABLE, HASH_VAL)
Definition hash0hash.h:166

Move all hash table entries from OLD_TABLE to NEW_TABLE.

Definition at line 308 of file hash0hash.h.

◆ HASH_SEARCH

#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_GET_NEXT(NAME, DATA)
Definition hash0hash.h:172

Looks for a struct in a hash table.

Definition at line 176 of file hash0hash.h.

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

Definition at line 197 of file hash0hash.h.

Typedef Documentation

◆ hash_cell_t

typedef struct hash_cell_struct hash_cell_t

Definition at line 37 of file hash0hash.h.

◆ hash_node_t

typedef void* hash_node_t

Definition at line 39 of file hash0hash.h.

◆ hash_table_t

typedef struct hash_table_struct hash_table_t

Definition at line 36 of file hash0hash.h.

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.

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

◆ hash_create()

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.

◆ hash_create_mutexes_func()

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.

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

Returns
mem heap in: fold
Parameters
tablein: hash table

◆ hash_get_mutex()

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

◆ hash_get_mutex_no()

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

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

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

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

Returns
mem heap in: index of the heap
Parameters
tablein: hash table

◆ hash_get_nth_mutex()

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

◆ hash_mutex_enter()

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.

◆ hash_mutex_enter_all()

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.

◆ hash_mutex_exit()

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.

◆ hash_mutex_exit_all()

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.

◆ 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()

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.