extensible hash More...

#include <assert.h>
#include <stddef.h>
#include <string.h>
#include <sys/types.h>
#include <atomic>
#include <bit>
#include <cstdint>
#include "lf.h"
#include "my_atomic.h"
#include "my_compiler.h"
#include "my_inttypes.h"
#include "my_sys.h"
#include "mysql/service_mysql_alloc.h"
#include "mysql/strings/m_ctype.h"
#include "mysys/mysys_priv.h"
#include "template_utils.h"

Classes
struct	LF_SLIST

struct	CURSOR

Macros
#define	MAX_LOAD 1.0 /* average number of elements in a bucket */

Functions
template<class T >
static T *	PTR (T *ptr)

template<class T >
static bool	DELETED (T *ptr)

template<class T >
static T *	SET_DELETED (T *ptr)

static uint32_t	reverse_bits (uint32_t key)

static int	my_lfind (std::atomic< LF_SLIST * > head, lf_cmp_func cmp_func, CHARSET_INFO cs, uint32 hashnr, const uchar key, size_t keylen, CURSOR cursor, LF_PINS pins)

static int	my_lfind_match (std::atomic< LF_SLIST * > head, uint32 first_hashnr, uint32 last_hashnr, lf_hash_match_func match, CURSOR cursor, LF_PINS pins, void *match_arg)
	Search for list element satisfying condition specified by match function and position cursor on it. More...

static LF_SLIST *	linsert (std::atomic< LF_SLIST * > head, lf_cmp_func cmp_func, CHARSET_INFO cs, LF_SLIST node, LF_PINS *pins, uint flags)

static int	ldelete (std::atomic< LF_SLIST * > head, lf_cmp_func cmp_func, CHARSET_INFO cs, uint32 hashnr, const uchar key, uint keylen, LF_PINS *pins)

static LF_SLIST *	my_lsearch (std::atomic< LF_SLIST * > head, lf_cmp_func cmp_func, CHARSET_INFO cs, uint32 hashnr, const uchar key, uint keylen, LF_PINS *pins)

static const uchar *	hash_key (const LF_HASH hash, const uchar record, size_t *length)

static uint	calc_hash (LF_HASH hash, const uchar key, size_t keylen)

static int	initialize_bucket (LF_HASH , std::atomic< LF_SLIST > , uint, LF_PINS )

static uint	cset_hash_sort_adapter (const LF_HASH hash, const uchar key, size_t length)
	Adaptor function which allows to use hash function from character set with LF_HASH. More...

void	lf_hash_init_impl (LF_HASH hash, uint element_size, uint flags, uint key_offset, uint key_length, hash_get_key_function get_key, CHARSET_INFO charset, lf_hash_func hash_function, lf_cmp_func cmp_function, lf_allocator_func ctor, lf_allocator_func dtor, lf_hash_init_func *init)

void	lf_hash_init2 (LF_HASH hash, uint element_size, uint flags, uint key_offset, uint key_length, hash_get_key_function get_key, CHARSET_INFO charset, lf_hash_func hash_function, lf_allocator_func ctor, lf_allocator_func dtor, lf_hash_init_func init)

void	lf_hash_init3 (LF_HASH hash, uint element_size, uint flags, hash_get_key_function get_key, lf_hash_func hash_function, lf_cmp_func cmp_function, lf_allocator_func ctor, lf_allocator_func dtor, lf_hash_init_func init)

void	lf_hash_destroy (LF_HASH *hash)

int	lf_hash_insert (LF_HASH hash, LF_PINS pins, const void *data)

int	lf_hash_delete (LF_HASH hash, LF_PINS pins, const void *key, uint keylen)

void *	lf_hash_search (LF_HASH hash, LF_PINS pins, const void *key, uint keylen)
	Find hash element corresponding to the key. More...

void *	lf_hash_random_match (LF_HASH hash, LF_PINS pins, lf_hash_match_func match, uint rand_val, void match_arg)
	Find random hash element which satisfies condition specified by match function. More...

Variables
const int	LF_HASH_OVERHEAD = sizeof(LF_SLIST)

static constexpr unsigned char	reverse_bits_table [256]

static const uchar *	dummy_key = pointer_cast<const uchar *>("")

Detailed Description

extensible hash

Macro Definition Documentation

◆ MAX_LOAD

#define MAX_LOAD 1.0 /* average number of elements in a bucket */

Function Documentation

◆ calc_hash()

static uint calc_hash	(	LF_HASH *	hash,
		const uchar *	key,
		size_t	keylen
	)

inlinestatic

◆ cset_hash_sort_adapter()

static uint cset_hash_sort_adapter	(	const LF_HASH *	hash,
		const uchar *	key,
		size_t	length
	)

static

Adaptor function which allows to use hash function from character set with LF_HASH.

◆ DELETED()

template<class T >

static bool DELETED ( T * ptr )

inlinestatic

◆ hash_key()

static const uchar * hash_key	(	const LF_HASH *	hash,
		const uchar *	record,
		size_t *	length
	)

inlinestatic

◆ initialize_bucket()

static int initialize_bucket	(	LF_HASH *	hash,
		std::atomic< LF_SLIST * > *	node,
		uint	bucket,
		LF_PINS *	pins
	)

static

◆ ldelete()

static int ldelete	(	std::atomic< LF_SLIST * > *	head,
		lf_cmp_func *	cmp_func,
		CHARSET_INFO *	cs,
		uint32	hashnr,
		const uchar *	key,
		uint	keylen,
		LF_PINS *	pins
	)

static

◆ lf_hash_delete()

int lf_hash_delete	(	LF_HASH *	hash,
		LF_PINS *	pins,
		const void *	key,
		uint	keylen
	)

◆ lf_hash_destroy()

void lf_hash_destroy ( LF_HASH * hash )

◆ lf_hash_init2()

void lf_hash_init2	(	LF_HASH *	hash,
		uint	element_size,
		uint	flags,
		uint	key_offset,
		uint	key_length,
		hash_get_key_function	get_key,
		CHARSET_INFO *	charset,
		lf_hash_func *	hash_function,
		lf_allocator_func *	ctor,
		lf_allocator_func *	dtor,
		lf_hash_init_func *	init
	)

◆ lf_hash_init3()

void lf_hash_init3	(	LF_HASH *	hash,
		uint	element_size,
		uint	flags,
		hash_get_key_function	get_key,
		lf_hash_func *	hash_function,
		lf_cmp_func *	cmp_function,
		lf_allocator_func *	ctor,
		lf_allocator_func *	dtor,
		lf_hash_init_func *	init
	)

◆ lf_hash_init_impl()

void lf_hash_init_impl	(	LF_HASH *	hash,
		uint	element_size,
		uint	flags,
		uint	key_offset,
		uint	key_length,
		hash_get_key_function	get_key,
		CHARSET_INFO *	charset,
		lf_hash_func *	hash_function,
		lf_cmp_func *	cmp_function,
		lf_allocator_func *	ctor,
		lf_allocator_func *	dtor,
		lf_hash_init_func *	init
	)

◆ lf_hash_insert()

int lf_hash_insert	(	LF_HASH *	hash,
		LF_PINS *	pins,
		const void *	data
	)

◆ lf_hash_random_match()

void * lf_hash_random_match	(	LF_HASH *	hash,
		LF_PINS *	pins,
		lf_hash_match_func *	match,
		uint	rand_val,
		void *	match_arg
	)

Find random hash element which satisfies condition specified by match function.

Parameters

hash	Hash to search element in.
pins	Pins for calling thread to be used during search and for pinning its result.
match	Pointer to match function. This function takes pointer to object stored in hash as parameter and returns 0 if object doesn't satisfy its condition (and non-0 value if it does).
rand_val	Random value to be used for selecting hash bucket from which search in sort-ordered list needs to be started.
match_arg	Argument passed to match function.

Return values

A	pointer to a random element matching condition.
NULL	- if nothing is found
MY_LF_ERRPTR	- OOM.

Note: This function follows the same pinning protocol as lf_hash_search(), i.e. uses pins[0..2]. On return pins[0..1] are removed and pins[2] is used to pin object found. It is also not removed in case when object is not found/error occurs but its value is undefined in this case. So calling lf_hash_unpin() is mandatory after call to this function in case of both success and failure.

◆ lf_hash_search()

void * lf_hash_search	(	LF_HASH *	hash,
		LF_PINS *	pins,
		const void *	key,
		uint	keylen
	)

Find hash element corresponding to the key.

Parameters

hash	The hash to search element in.
pins	Pins for the calling thread which were earlier obtained from this hash using lf_hash_get_pins().
key	Key
keylen	Key length

Return values

A	pointer to an element with the given key (if a hash is not unique and there're many elements with this key - the "first" matching element).
NULL	- if nothing is found
MY_LF_ERRPTR	- if OOM

Note: Uses pins[0..2]. On return pins[0..1] are removed and pins[2] is used to pin object found. It is also not removed in case when object is not found/error occurs but pin value is undefined in this case. So calling lf_hash_unpin() is mandatory after call to this function in case of both success and failure.

See also: my_lsearch().

◆ linsert()

static LF_SLIST * linsert	(	std::atomic< LF_SLIST * > *	head,
		lf_cmp_func *	cmp_func,
		CHARSET_INFO *	cs,
		LF_SLIST *	node,
		LF_PINS *	pins,
		uint	flags
	)

static

◆ my_lfind()

static int my_lfind	(	std::atomic< LF_SLIST * > *	head,
		lf_cmp_func *	cmp_func,
		CHARSET_INFO *	cs,
		uint32	hashnr,
		const uchar *	key,
		size_t	keylen,
		CURSOR *	cursor,
		LF_PINS *	pins
	)

static

◆ my_lfind_match()

static int my_lfind_match	(	std::atomic< LF_SLIST * > *	head,
		uint32	first_hashnr,
		uint32	last_hashnr,
		lf_hash_match_func *	match,
		CURSOR *	cursor,
		LF_PINS *	pins,
		void *	match_arg
	)

static

Search for list element satisfying condition specified by match function and position cursor on it.

Parameters

head	Head of the list to search in.
first_hashnr	Hash value to start search from.
last_hashnr	Hash value to stop search after.
match	Match function.
cursor	Cursor to be position.
pins	LF_PINS for the calling thread to be used during search for pinning result.
match_arg	Argument passed to match function.

Return values

0	- not found
1	- found

◆ my_lsearch()

static LF_SLIST * my_lsearch	(	std::atomic< LF_SLIST * > *	head,
		lf_cmp_func *	cmp_func,
		CHARSET_INFO *	cs,
		uint32	hashnr,
		const uchar *	key,
		uint	keylen,
		LF_PINS *	pins
	)

static

◆ PTR()

template<class T >

static T * PTR ( T * ptr )

inlinestatic

◆ reverse_bits()

static uint32_t reverse_bits ( uint32_t key )

static

◆ SET_DELETED()

template<class T >

static T * SET_DELETED ( T * ptr )

inlinestatic

Variable Documentation

◆ dummy_key

const uchar* dummy_key = pointer_cast<const uchar *>("")

static

◆ LF_HASH_OVERHEAD

const int LF_HASH_OVERHEAD = sizeof(LF_SLIST)

◆ reverse_bits_table

constexpr unsigned char reverse_bits_table[256]

staticconstexpr

Initial value:

= {
    0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0,
    0x30, 0xB0, 0x70, 0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
    0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 0x04, 0x84, 0x44, 0xC4,
    0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
    0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC,
    0x3C, 0xBC, 0x7C, 0xFC, 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,
    0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA,
    0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
    0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6,
    0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
    0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 0x01, 0x81, 0x41, 0xC1,
    0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
    0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9,
    0x39, 0xB9, 0x79, 0xF9, 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,
    0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD,
    0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
    0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3,
    0x33, 0xB3, 0x73, 0xF3, 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
    0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 0x07, 0x87, 0x47, 0xC7,
    0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
    0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF,
    0x3F, 0xBF, 0x7F, 0xFF}

Classes

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ MAX_LOAD

Function Documentation

◆ calc_hash()

◆ cset_hash_sort_adapter()

◆ DELETED()

◆ hash_key()

◆ initialize_bucket()

◆ ldelete()

◆ lf_hash_delete()

◆ lf_hash_destroy()

◆ lf_hash_init2()

◆ lf_hash_init3()

◆ lf_hash_init_impl()

◆ lf_hash_insert()

◆ lf_hash_random_match()

◆ lf_hash_search()

◆ linsert()

◆ my_lfind()

◆ my_lfind_match()

◆ my_lsearch()

◆ PTR()

◆ reverse_bits()

◆ SET_DELETED()

Variable Documentation

◆ dummy_key

◆ LF_HASH_OVERHEAD

◆ reverse_bits_table