Resizable hash tables. More...

#include <freeradius-devel/util/hash.h>

Include dependency graph for hash.c:

Data Structures
struct	fr_hash_entry_s

struct	fr_hash_table_s

Macros
#define	FNV_MAGIC_INIT (0x811c9dc5)

#define	FNV_MAGIC_PRIME (0x01000193)

#define	FR_HASH_NUM_BUCKETS (64)

#define	GROW_FACTOR (2)

Functions
fr_hash_table_t *	_fr_hash_table_alloc (TALLOC_CTX ctx, char const type, fr_hash_t hash_func, fr_cmp_t cmp_func, fr_free_t free_func)

static int	_fr_hash_table_free (fr_hash_table_t *ht)

	CC_NO_UBSAN (function)
	Find data in a hash table. More...

uint32_t	fr_hash (void const *data, size_t size)

uint32_t	fr_hash_case_string (char const *p)
	Hash a C string, converting all chars to lowercase. More...

uint32_t	fr_hash_string (char const *p)

void	fr_hash_table_fill (fr_hash_table_t *ht)
	Ensure all buckets are filled. More...

void *	fr_hash_table_find_by_key (fr_hash_table_t ht, uint32_t key, void const data)
	Hash table lookup with pre-computed key. More...

static void	fr_hash_table_fixup (fr_hash_table_t *ht, uint32_t entry)

int	fr_hash_table_flatten (TALLOC_CTX ctx, void out[], fr_hash_table_t ht)
	Copy all entries out of a hash table into an array. More...

static void	fr_hash_table_grow (fr_hash_table_t *ht)

void *	fr_hash_table_iter_init (fr_hash_table_t ht, fr_hash_iter_t iter)
	Initialise an iterator. More...

void *	fr_hash_table_iter_next (fr_hash_table_t ht, fr_hash_iter_t iter)
	Iterate over entries in a hash table. More...

void	fr_hash_table_verify (fr_hash_table_t *ht)
	Check hash table is sane. More...

uint32_t	fr_hash_update (void const *data, size_t size, uint32_t hash)

static fr_hash_entry_t *	hash_table_find (fr_hash_table_t ht, uint32_t key, void const data)

static void	list_delete (fr_hash_table_t ht, fr_hash_entry_t head, fr_hash_entry_t node)

static fr_hash_entry_t *	list_find (fr_hash_table_t ht, fr_hash_entry_t head, uint32_t reversed, void const *data)

static bool	list_insert (fr_hash_table_t ht, fr_hash_entry_t head, fr_hash_entry_t node)

static uint32_t	parent_of (uint32_t key)

static uint32_t	reverse (uint32_t key)

Variables
static uint8_t	parent_byte [256]

static const uint8_t	reversed_byte [256]

Detailed Description

Resizable hash tables.

The weird "reverse" function is based on an idea from "Split-Ordered Lists - Lock-free Resizable Hash Tables", with modifications so that they're not lock-free. :(

However, the split-order idea allows a fast & easy splitting of the hash bucket chain when the hash table is resized. Without it, we'd have to check & update the pointers for every node in the buck chain, rather than being able to move 1/2 of the entries in the chain with one update.

Copyright: 2005,2006 The FreeRADIUS server project

Definition in file hash.c.

Data Structure Documentation

◆ fr_hash_entry_s

struct fr_hash_entry_s

Definition at line 43 of file hash.c.

Collaboration diagram for fr_hash_entry_s:

Data Fields
void *	data
uint32_t	key
fr_hash_entry_t *	next
uint32_t	reversed

◆ fr_hash_table_s

struct fr_hash_table_s

Definition at line 50 of file hash.c.

Collaboration diagram for fr_hash_table_s:

Data Fields
fr_hash_entry_t **	buckets	Array of hash buckets.
fr_cmp_t	cmp	Comparison function.
fr_free_t	free	Data free function.
fr_hash_t	hash	Hashing function.
uint32_t	mask
uint32_t	next_grow
fr_hash_entry_t	null
uint32_t	num_buckets	Number of buckets (how long the array is) - power of 2 *‍/.
uint32_t	num_elements	Number of elements in the hash table.
char const *	type	Talloc type to check elements against.

Macro Definition Documentation

◆ FNV_MAGIC_INIT

#define FNV_MAGIC_INIT (0x811c9dc5)

Definition at line 801 of file hash.c.

◆ FNV_MAGIC_PRIME

#define FNV_MAGIC_PRIME (0x01000193)

Definition at line 802 of file hash.c.

◆ FR_HASH_NUM_BUCKETS

#define FR_HASH_NUM_BUCKETS (64)

Definition at line 41 of file hash.c.

◆ GROW_FACTOR

#define GROW_FACTOR (2)

Definition at line 377 of file hash.c.

Function Documentation

◆ _fr_hash_table_alloc()

fr_hash_table_t* _fr_hash_table_alloc	(	TALLOC_CTX *	ctx,
		char const *	type,
		fr_hash_t	hash_func,
		fr_cmp_t	cmp_func,
		fr_free_t	free_func
	)

Definition at line 280 of file hash.c.

Here is the call graph for this function:

◆ _fr_hash_table_free()

static int _fr_hash_table_free ( fr_hash_table_t * ht )

static

Definition at line 254 of file hash.c.

Here is the caller graph for this function:

◆ CC_NO_UBSAN()

CC_NO_UBSAN ( function )

Find data in a hash table.

Remove and free data (if a free function was specified)

Remove an entry from the hash table, without freeing the data.

Replace old data with new data, OR insert if there is no old.

Insert data into a hash table.

Parameters

[in]	ht	to find data in.
[in]	data	to find. Will be passed to the hashing function.

Returns

The user data we found.
NULL if we couldn't find any matching data.

Parameters

[in]	ht	to insert data into.
[in]	data	to insert. Will be passed to the hashing function.

Returns

true if data was inserted.
false if data already existed and was not inserted.

Parameters

[out]	old	data that was replaced. If this argument is not NULL, then the old data will not be freed, even if a free function is configured.
[in]	ht	to insert data into.
[in]	data	to replace. Will be passed to the hashing function.

Returns

1 if data was replaced.
0 if data was inserted.
-1 if we failed to replace data

Parameters

[in]	ht	to remove data from.
[in]	data	to remove. Will be passed to the hashing function.

Returns

The user data we removed.
NULL if we couldn't find any matching data.

Parameters

[in]	ht	to remove data from.
[in]	data	to remove/free.

Returns

true if we removed data.
false if we couldn't find any matching data.

Definition at line 428 of file hash.c.

Here is the call graph for this function:

◆ fr_hash()

uint32_t fr_hash	(	void const *	data,
		size_t	size
	)

Definition at line 812 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_hash_case_string()

uint32_t fr_hash_case_string ( char const * p )

Hash a C string, converting all chars to lowercase.

Definition at line 881 of file hash.c.

Here is the call graph for this function:

◆ fr_hash_string()

uint32_t fr_hash_string ( char const * p )

Definition at line 865 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_hash_table_fill()

void fr_hash_table_fill ( fr_hash_table_t * ht )

Ensure all buckets are filled.

This must be called if the table will be read by multiple threads without synchronisation. Synchronisation is still required for updates.

Parameters

[in] ht to fill.

Definition at line 719 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_hash_table_find_by_key()

void* fr_hash_table_find_by_key	(	fr_hash_table_t *	ht,
		uint32_t	key,
		void const *	data
	)

Hash table lookup with pre-computed key.

Parameters

[in]	ht	to find data in.
[in]	key	the precomputed key.
[in]	data	for list matching.

Returns

The user data we found.
NULL if we couldn't find any matching data.

Definition at line 448 of file hash.c.

Here is the call graph for this function:

◆ fr_hash_table_fixup()

static void fr_hash_table_fixup	(	fr_hash_table_t *	ht,
		uint32_t	entry
	)

static

Definition at line 332 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_hash_table_flatten()

int fr_hash_table_flatten	(	TALLOC_CTX *	ctx,
		void **	out[],
		fr_hash_table_t *	ht
	)

Copy all entries out of a hash table into an array.

Parameters

[in]	ctx	to allocate array in.
[in]	out	array of hash table entries.
[in]	ht	to flatter.

Returns

0 on success.
-1 on failure.

Definition at line 695 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_hash_table_grow()

static void fr_hash_table_grow ( fr_hash_table_t * ht )

static

Definition at line 382 of file hash.c.

◆ fr_hash_table_iter_init()

void* fr_hash_table_iter_init	(	fr_hash_table_t *	ht,
		fr_hash_iter_t *	iter
	)

Initialise an iterator.

Note: If the hash table is modified the iterator should be considered invalidated.

Parameters

[in]	ht	to iterate over.
[out]	iter	to initialise.

Returns

The first entry in the hash table.
NULL if the hash table is empty.

Definition at line 678 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_hash_table_iter_next()

void* fr_hash_table_iter_next	(	fr_hash_table_t *	ht,
		fr_hash_iter_t *	iter
	)

Iterate over entries in a hash table.

Note: If the hash table is modified the iterator should be considered invalidated.

Parameters

[in]	ht	to iterate over.
[in]	iter	Pointer to an iterator struct, used to maintain state between calls.

Returns

User data.
NULL if at the end of the list.

Definition at line 626 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_hash_table_verify()

void fr_hash_table_verify ( fr_hash_table_t * ht )

Check hash table is sane.

Definition at line 897 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_hash_update()

uint32_t fr_hash_update	(	void const *	data,
		size_t	size,
		uint32_t	hash
	)

Definition at line 846 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hash_table_find()

static fr_hash_entry_t* hash_table_find	(	fr_hash_table_t *	ht,
		uint32_t	key,
		void const *	data
	)

inlinestatic

Definition at line 405 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ list_delete()

static void list_delete	(	fr_hash_table_t *	ht,
		fr_hash_entry_t **	head,
		fr_hash_entry_t *	node
	)

static

Definition at line 239 of file hash.c.

◆ list_find()

static fr_hash_entry_t* list_find	(	fr_hash_table_t *	ht,
		fr_hash_entry_t *	head,
		uint32_t	reversed,
		void const *	data
	)

static

Definition at line 184 of file hash.c.

Here is the caller graph for this function:

◆ list_insert()

static bool list_insert	(	fr_hash_table_t *	ht,
		fr_hash_entry_t **	head,
		fr_hash_entry_t *	node
	)

static

Definition at line 208 of file hash.c.

◆ parent_of()

static uint32_t parent_of ( uint32_t key )

static

Definition at line 169 of file hash.c.

Here is the caller graph for this function:

◆ reverse()

static uint32_t reverse ( uint32_t key )

static

Definition at line 151 of file hash.c.

Here is the caller graph for this function:

Variable Documentation

◆ parent_byte

uint8_t parent_byte[256]

static

Definition at line 112 of file hash.c.

◆ reversed_byte

const uint8_t reversed_byte[256]

static

Definition at line 73 of file hash.c.

Data Structures

Macros

Functions

Variables

Detailed Description

Data Structure Documentation

◆ fr_hash_entry_s

◆ fr_hash_table_s

Macro Definition Documentation

◆ FNV_MAGIC_INIT

◆ FNV_MAGIC_PRIME

◆ FR_HASH_NUM_BUCKETS

◆ GROW_FACTOR

Function Documentation

◆ _fr_hash_table_alloc()

◆ _fr_hash_table_free()

◆ CC_NO_UBSAN()

◆ fr_hash()

◆ fr_hash_case_string()

◆ fr_hash_string()

◆ fr_hash_table_fill()

◆ fr_hash_table_find_by_key()

◆ fr_hash_table_fixup()

◆ fr_hash_table_flatten()

◆ fr_hash_table_grow()

◆ fr_hash_table_iter_init()

◆ fr_hash_table_iter_next()

◆ fr_hash_table_verify()

◆ fr_hash_update()

◆ hash_table_find()

◆ list_delete()

◆ list_find()

◆ list_insert()

◆ parent_of()

◆ reverse()

Variable Documentation

◆ parent_byte

◆ reversed_byte