hash.c File Reference

Resizable hash tables. More...

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

Include dependency graph for hash.c:

Go to the source code of this file.

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)
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.
uint32_t	fr_hash_string (char const *p)
bool	fr_hash_table_delete (fr_hash_table_t *ht, void const *data)
	Remove and free data (if a free function was specified)
void	fr_hash_table_fill (fr_hash_table_t *ht)
	Ensure all buckets are filled.
void *	fr_hash_table_find (fr_hash_table_t *ht, void const *data)
	Find data in a hash table.
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.
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.
static void	fr_hash_table_grow (fr_hash_table_t *ht)
bool	fr_hash_table_insert (fr_hash_table_t *ht, void const *data)
	Insert data into a hash table.
void *	fr_hash_table_iter_init (fr_hash_table_t *ht, fr_hash_iter_t *iter)
	Initialise an iterator.
void *	fr_hash_table_iter_next (fr_hash_table_t *ht, fr_hash_iter_t *iter)
	Iterate over entries in a hash table.
uint32_t	fr_hash_table_num_elements (fr_hash_table_t *ht)
void *	fr_hash_table_remove (fr_hash_table_t *ht, void const *data)
	Remove an entry from the hash table, without freeing the data.
int	fr_hash_table_replace (void **old, fr_hash_table_t *ht, void const *data)
	Replace old data with new data, OR insert if there is no old.
void	fr_hash_table_verify (fr_hash_table_t *ht)
	Check hash table is sane.
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:

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_delete()

bool fr_hash_table_delete	(	fr_hash_table_t *	ht,
		void const *	data
	)

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

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 594 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()

void * fr_hash_table_find	(	fr_hash_table_t *	ht,
		void const *	data
	)

Find data in 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.

Definition at line 429 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.

Here is the caller graph for this function:

fr_hash_table_insert()

bool fr_hash_table_insert	(	fr_hash_table_t *	ht,
		void const *	data
	)

Insert data into a hash table.

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.

Definition at line 468 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

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_num_elements()

uint32_t fr_hash_table_num_elements

(

fr_hash_table_t *

ht

)

Definition at line 610 of file hash.c.

Here is the caller graph for this function:

fr_hash_table_remove()

void * fr_hash_table_remove	(	fr_hash_table_t *	ht,
		void const *	data
	)

Remove an entry from the hash table, without freeing the 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.

Definition at line 559 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_hash_table_replace()

int fr_hash_table_replace	(	void **	old,
		fr_hash_table_t *	ht,
		void const *	data
	)

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

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

Definition at line 528 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.

Here is the caller graph for this function:

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.

Here is the caller graph for this function:

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.