#include "univ.i"
#include "mem0mem.h"
#include "sync0sync.h"

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_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

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

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(), dict_table_rename_in_cache(), and thr_local_free().

#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 dict_close(), fil_validate(), recv_apply_hashed_log_recs(), and thr_local_close().

#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 dict_close(), fil_validate(), recv_apply_hashed_log_recs(), and thr_local_close().

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

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(), ha_storage_put_memlim(), and thr_local_create().

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

Definition at line 308 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);\
    }\
  }\
}

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(), get_share(), and thr_local_free().

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

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:

fold	in: 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:

n	in: 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().

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:

table	in: hash table
n_mutexes	in: 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:

table in: 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:

table in: 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:

table in: 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 dict_close(), fil_validate(), ha_clear(), ha_print_info(), recv_apply_hashed_log_recs(), and thr_local_close().

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:

table in: 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:

table in: 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:

table 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

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

Parameters:

table	in: hash table
fold	in: 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:

table in: 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:

table	in: hash table
fold	in: 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:

table in: 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:

table in, 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().

Drizzled Public API Documentation

Classes

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Function Documentation