MySQL 8.3.0
Source Code Documentation
lf_hash.cc File Reference

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_SLISTlinsert (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_SLISTmy_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 ucharhash_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 uchardummy_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
hashHash to search element in.
pinsPins for calling thread to be used during search and for pinning its result.
matchPointer 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_valRandom value to be used for selecting hash bucket from which search in sort-ordered list needs to be started.
match_argArgument passed to match function.
Return values
Apointer 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
hashThe hash to search element in.
pinsPins for the calling thread which were earlier obtained from this hash using lf_hash_get_pins().
keyKey
keylenKey length
Return values
Apointer 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
headHead of the list to search in.
first_hashnrHash value to start search from.
last_hashnrHash value to stop search after.
matchMatch function.
cursorCursor to be position.
pinsLF_PINS for the calling thread to be used during search for pinning result.
match_argArgument 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}