#include "univ.i"
#include "mem0mem.h"
#include "sync0sync.h"
#include "sync0rw.h"
#include "hash0hash.ic"

Include dependency graph for hash0hash.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	hash_cell_t
struct	hash_table_t

Macros
#define	hash_create hash0_create
#define	hash_create_sync_obj(t, s, n, level) hash_create_sync_obj_func(t, s, level, n)
#define	HASH_ASSERT_OWN(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)
#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
UNIV_INTERN hash_table_t *	hash_create (ulint n)
UNIV_INTERN void	hash_create_sync_obj_func (hash_table_t *table, enum hash_table_sync_t type, ulint sync_level, ulint n_sync_obj)
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_sync_obj_index (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 ib_mutex_t *	hash_get_nth_mutex (hash_table_t *table, ulint i)
UNIV_INLINE rw_lock_t *	hash_get_nth_lock (hash_table_t *table, ulint i)
UNIV_INLINE ib_mutex_t *	hash_get_mutex (hash_table_t *table, ulint fold)
UNIV_INLINE rw_lock_t *	hash_get_lock (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)
UNIV_INTERN void	hash_mutex_exit_all_but (hash_table_t table, ib_mutex_t keep_mutex)
UNIV_INTERN void	hash_lock_s (hash_table_t *table, ulint fold)
UNIV_INTERN void	hash_lock_x (hash_table_t *table, ulint fold)
UNIV_INTERN void	hash_unlock_s (hash_table_t *table, ulint fold)
UNIV_INTERN void	hash_unlock_x (hash_table_t *table, ulint fold)
UNIV_INTERN void	hash_lock_x_all (hash_table_t *table)
UNIV_INTERN void	hash_unlock_x_all (hash_table_t *table)
UNIV_INTERN void	hash_unlock_x_all_but (hash_table_t table, rw_lock_t keep_lock)

Detailed Description

The simple hash table utility

Created 5/20/1997 Heikki Tuuri

Macro Definition Documentation

#define HASH_ASSERT_OWN	(	TABLE,
		FOLD
	)

Value:

ut_ad((TABLE)->type != HASH_TABLE_SYNC_MUTEX \

|| (mutex_own(hash_get_mutex((TABLE), FOLD))));

Assert that the mutex for the table is held

#define HASH_DELETE	(	TYPE,
		NAME,
		TABLE,
		FOLD,
		DATA
	)

Value:

do {\
	hash_cell_t*   cell3333;\
        TYPE*           struct3333;\
\
	HASH_ASSERT_OWN(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)

Deletes a struct from a hash table.

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

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

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

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

#define HASH_INSERT	(	TYPE,
		NAME,
		TABLE,
		FOLD,
		DATA
	)

Value:

do {\
	hash_cell_t*   cell3333;\
        TYPE*           struct3333;\
\
	HASH_ASSERT_OWN(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.

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

Move all hash table entries from OLD_TABLE to NEW_TABLE.

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

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

Enumeration Type Documentation

enum 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

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

Calculates the hash value from a folded value.

Returns: hashed value

Parameters

fold	in: folded value
table	in: hash table

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

UNIV_INTERN void hash_create_sync_obj_func	(	hash_table_t *	table,
		enum hash_table_sync_t	type,
		ulint	sync_level,
		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. in: number of sync objects, must be a power of 2

Parameters

table	in: hash table
type	in: HASH_TABLE_SYNC_MUTEX or HASH_TABLE_SYNC_RW_LOCK
sync_level	in: latching order level of the mutexes: used in the debug version

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

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

Returns: mem heap

Parameters

table	in: hash table
fold	in: fold

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.

Returns: rw_lock in: fold

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

Returns: rw_lock

Parameters

table	in: hash table
fold	in: fold

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.

Returns: mutex in: fold

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

Returns: mutex

Parameters

table	in: hash table
fold	in: fold

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

Returns the number of cells in a hash table.

Returns: number of cells

Parameters

table in: table

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

Gets the nth cell in a hash table.

Returns: pointer to cell

Parameters

table	in: hash table
n	in: cell index

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

Gets the nth heap in a hash table.

Returns: mem heap

Parameters

table	in: hash table
i	in: index of the heap

UNIV_INLINE rw_lock_t* hash_get_nth_lock	(	hash_table_t *	table,
		ulint	i
	)

Gets the nth rw_lock in a hash table.

Returns: rw_lock in: index of the rw_lock

Gets the nth rw_lock in a hash table.

Returns: rw_lock

Parameters

table	in: hash table
i	in: index of the rw_lock

UNIV_INLINE ib_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

Gets the nth mutex in a hash table.

Returns: mutex

Parameters

table	in: hash table
i	in: index of the mutex

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.

Returns: index in: fold

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

Returns: index

Parameters

table	in: hash table
fold	in: fold

UNIV_INTERN void hash_lock_s	(	hash_table_t *	table,
		ulint	fold
	)

s-lock a lock for a fold value in a hash table. in: fold

Parameters

table in: hash table

UNIV_INTERN void hash_lock_x	(	hash_table_t *	table,
		ulint	fold
	)

x-lock a lock for a fold value in a hash table. in: fold

Parameters

table in: hash table

UNIV_INTERN void hash_lock_x_all ( hash_table_t * table )

Reserves all the locks of a hash table, in an ascending order. in: 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

Parameters

table in: hash table

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

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

Parameters

table in: hash table

UNIV_INTERN void hash_mutex_exit_all ( hash_table_t * table )

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

UNIV_INTERN void hash_mutex_exit_all_but	(	hash_table_t *	table,
		ib_mutex_t *	keep_mutex
	)

Releases all but the passed in mutex of a hash table. in: mutex to keep

Parameters

table in: hash table

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

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

Parameters

table in/out: hash table

UNIV_INTERN void hash_table_free ( hash_table_t * table )

Frees a hash table. in, own: hash table

UNIV_INTERN void hash_unlock_s	(	hash_table_t *	table,
		ulint	fold
	)

unlock an s-lock for a fold value in a hash table. in: fold

Parameters

table in: hash table

UNIV_INTERN void hash_unlock_x	(	hash_table_t *	table,
		ulint	fold
	)

unlock x-lock for a fold value in a hash table. in: fold

Parameters

table in: hash table

UNIV_INTERN void hash_unlock_x_all ( hash_table_t * table )

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

UNIV_INTERN 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

table in: hash table

Data Structures

Macros

Typedefs

Enumerations

Functions

Detailed Description

Macro Definition Documentation

Enumeration Type Documentation

Function Documentation