The hash table with external chains. More...

#include "univ.i"
#include "buf0types.h"
#include "hash0hash.h"
#include "page0types.h"
#include "rem0types.h"
#include "ha0ha.ic"

Classes
struct	ha_node_t
	The hash table external chain node. More...

Functions
static const rec_t *	ha_search_and_get_data (hash_table_t *table, uint64_t hash_value)
	Looks for an element in a hash table. More...

bool	ha_search_and_update_if_found_func (hash_table_t table, uint64_t hash_value, const rec_t data, buf_block_t new_block, const rec_t new_data)
	Looks for an element when we know the pointer to the data and updates the pointer to data if found. More...

static bool	ha_search_and_update_if_found (hash_table_t table, uint64_t hash_value, const rec_t data, buf_block_t new_block, const rec_t new_data)
	Looks for an element when we know the pointer to the data and updates the pointer to data if found. More...

hash_table_t *	ib_create (size_t n, latch_id_t id, size_t n_sync_obj, uint32_t type)
	Creates a hash table with at least n array cells. More...

void	ha_clear (hash_table_t *table)
	Empties a hash table and frees the memory heaps. More...

bool	ha_insert_for_hash_func (hash_table_t table, uint64_t hash_value, buf_block_t block, const rec_t *data)
	Inserts an entry into a hash table. More...

static void	ha_insert_for_hash (hash_table_t t, uint64_t f, buf_block_t b, const rec_t *d)
	Inserts an entry into a hash table. More...

static bool	ha_search_and_delete_if_found (hash_table_t table, uint64_t hash_value, const rec_t data)
	Looks for an element when we know the pointer to the data and deletes it from the hash table if found. More...

void	ha_remove_a_node_to_page (hash_table_t table, uint64_t hash_value, const page_t page)
	Removes from the chain determined by hash value a single node whose data pointer points to the page given. More...

bool	ha_validate (hash_table_t *table, uint64_t start_index, uint64_t end_index)
	Validates a given range of the cells in hash table. More...

void	ha_print_info (FILE file, hash_table_t table)
	Prints info of a hash table. More...

Detailed Description

The hash table with external chains.

Created 8/18/1994 Heikki Tuuri

Function Documentation

◆ ha_clear()

void ha_clear ( hash_table_t * table )

Empties a hash table and frees the memory heaps.

in, own: hash table

Parameters

table in, own: hash table

◆ ha_insert_for_hash()

static void ha_insert_for_hash	(	hash_table_t *	t,
		uint64_t	f,
		buf_block_t *	b,
		const rec_t *	d
	)

inlinestatic

Inserts an entry into a hash table.

If an entry with the same hash number is found, its node is updated to point to the new data, and no new node is inserted.

Parameters

[in]	t	hash table
[in]	f	hashed value of data
[in]	b	buffer block containing the data
[in]	d	data, must not be NULL

◆ ha_insert_for_hash_func()

bool ha_insert_for_hash_func	(	hash_table_t *	table,
		uint64_t	hash_value,
		buf_block_t *	block,
		const rec_t *	data
	)

Inserts an entry into a hash table.

If an entry with the same hash number is found, its node is updated to point to the new data, and no new node is inserted. If btr_search_enabled is set to false, we will only allow updating existing nodes, but no new node is allowed to be added.

Parameters

[in]	table	hash table
[in]	hash_value	hashed value of data; if a node with the same hash value already exists, it is updated to point to the same data, and no new node is created!
[in]	block	buffer block containing the data
[in]	data	data, must not be NULL

Returns: true if succeeded, false if no more memory could be allocated

◆ ha_print_info()

void ha_print_info	(	FILE *	file,
		hash_table_t *	table
	)

Prints info of a hash table.

Parameters

[in]	file	File where to print
[in]	table	Hash table

◆ ha_remove_a_node_to_page()

void ha_remove_a_node_to_page	(	hash_table_t *	table,
		uint64_t	hash_value,
		const page_t *	page
	)

Removes from the chain determined by hash value a single node whose data pointer points to the page given.

Note that the node deleted can have a different hash value.

Parameters

[in]	table	Hash table
[in]	hash_value	Hash value
[in]	page	Buffer page

◆ ha_search_and_delete_if_found()

static bool ha_search_and_delete_if_found	(	hash_table_t *	table,
		uint64_t	hash_value,
		const rec_t *	data
	)

inlinestatic

Looks for an element when we know the pointer to the data and deletes it from the hash table if found.

Parameters

[in]	table	hash table
[in]	hash_value	hashed value of the searched data
[in]	data	pointer to the data

Returns: true if found

◆ ha_search_and_get_data()

static const rec_t * ha_search_and_get_data	(	hash_table_t *	table,
		uint64_t	hash_value
	)

inlinestatic

Looks for an element in a hash table.

Parameters

[in]	table	hash table
[in]	hash_value	hashed value of the searched data

Returns: pointer to the data of the first hash table node in chain having the hash number, NULL if not found

◆ ha_search_and_update_if_found()

static bool ha_search_and_update_if_found	(	hash_table_t *	table,
		uint64_t	hash_value,
		const rec_t *	data,
		buf_block_t *	new_block,
		const rec_t *	new_data
	)

inlinestatic

Looks for an element when we know the pointer to the data and updates the pointer to data if found.

Parameters

table	in/out: hash table
hash_value	in: hashed value of the searched data
data	in: pointer to the data
new_block	in: block containing new_data
new_data	in: new pointer to the data

◆ ha_search_and_update_if_found_func()

bool ha_search_and_update_if_found_func	(	hash_table_t *	table,
		uint64_t	hash_value,
		const rec_t *	data,
		buf_block_t *	new_block,
		const rec_t *	new_data
	)

Looks for an element when we know the pointer to the data and updates the pointer to data if found.

Parameters

[in,out]	table	hash table
[in]	hash_value	hashed value of the searched data
[in]	data	pointer to the data
[in]	new_block	block containing new data
[in]	new_data	new pointer to the data

Returns: true if found

◆ ha_validate()

bool ha_validate	(	hash_table_t *	table,
		uint64_t	start_index,
		uint64_t	end_index
	)

Validates a given range of the cells in hash table.

Parameters

[in]	table	Hash table
[in]	start_index	Start index
[in]	end_index	End index

Returns: true if ok

◆ ib_create()

hash_table_t * ib_create	(	size_t	n,
		latch_id_t	id,
		size_t	n_sync_obj,
		uint32_t	type
	)

Creates a hash table with at least n array cells.

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

Parameters

[in]	n	number of array cells
[in]	id	latch ID
[in]	n_sync_obj	Number of sync objects protecting the hash table. Must be a power of 2, or 0.
[in]	type	type of datastructure for which the memory heap is going to be used: MEM_HEAP_FOR_BTR_SEARCH or MEM_HEAP_FOR_PAGE_HASH

Returns: own: created table

Classes

Functions

Detailed Description

Function Documentation

◆ ha_clear()

◆ ha_insert_for_hash()

◆ ha_insert_for_hash_func()

◆ ha_print_info()

◆ ha_remove_a_node_to_page()

◆ ha_search_and_delete_if_found()

◆ ha_search_and_get_data()

◆ ha_search_and_update_if_found()

◆ ha_search_and_update_if_found_func()

◆ ha_validate()

◆ ib_create()