Structures and prototypes for resizable hash tables. More...

#include <freeradius-devel/util/misc.h>
#include <stddef.h>
#include <stdint.h>

Include dependency graph for hash.h:

Data Structures
struct	fr_hash_iter_s
	Stores the state of the current iteration operation. More...

Macros
#define	fr_hash_table_alloc(_ctx, _hash_node, _cmp_node, _free_node) _fr_hash_table_alloc(_ctx, NULL, _hash_node, _cmp_node, _free_node)

#define	fr_hash_table_talloc_alloc(_ctx, _type, _hash_node, _cmp_node, _free_node) _fr_hash_table_alloc(_ctx, #_type, _hash_node, _cmp_node, _free_node)

Typedefs
typedef struct fr_hash_entry_s	fr_hash_entry_t

typedef struct fr_hash_iter_s	fr_hash_iter_t
	Stores the state of the current iteration operation.

typedef uint32_t(*	fr_hash_t) (void const *)

typedef struct fr_hash_table_s	fr_hash_table_t

typedef int(*	fr_hash_table_walk_t) (void data, void uctx)

Functions
fr_hash_table_t *	_fr_hash_table_alloc (TALLOC_CTX ctx, char const type, fr_hash_t hash_node, fr_cmp_t cmp_node, fr_free_t free_node))

uint32_t	fr_hash (void const *, size_t)

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.

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.

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)

Detailed Description

Structures and prototypes for resizable hash tables.

Copyright: 2005,2006 The FreeRADIUS server project

Definition in file hash.h.

Data Structure Documentation

◆ fr_hash_iter_s

struct fr_hash_iter_s

Stores the state of the current iteration operation.

Definition at line 41 of file hash.h.

Collaboration diagram for fr_hash_iter_s:

Data Fields
uint32_t	bucket
fr_hash_entry_t *	node

Macro Definition Documentation

◆ fr_hash_table_alloc

#define fr_hash_table_alloc	(	_ctx,
		_hash_node,
		_cmp_node,
		_free_node
	)	_fr_hash_table_alloc(_ctx, NULL, _hash_node, _cmp_node, _free_node)

Definition at line 58 of file hash.h.

◆ fr_hash_table_talloc_alloc

#define fr_hash_table_talloc_alloc	(	_ctx,
		_type,
		_hash_node,
		_cmp_node,
		_free_node
	)	_fr_hash_table_alloc(_ctx, #_type, _hash_node, _cmp_node, _free_node)

Definition at line 61 of file hash.h.

Typedef Documentation

◆ fr_hash_entry_t

typedef struct fr_hash_entry_s fr_hash_entry_t

Definition at line 35 of file hash.h.

◆ fr_hash_iter_t

typedef struct fr_hash_iter_s fr_hash_iter_t

Stores the state of the current iteration operation.

◆ fr_hash_t

typedef uint32_t(* fr_hash_t) (void const *)

Definition at line 36 of file hash.h.

◆ fr_hash_table_t

typedef struct fr_hash_table_s fr_hash_table_t

Definition at line 55 of file hash.h.

◆ fr_hash_table_walk_t

typedef int(* fr_hash_table_walk_t) (void *data, void *uctx)

Definition at line 56 of file hash.h.

Function Documentation

◆ _fr_hash_table_alloc()

fr_hash_table_t * _fr_hash_table_alloc	(	TALLOC_CTX *	ctx,
		char const *	type,
		fr_hash_t	hash_node,
		fr_cmp_t	cmp_node,
		fr_free_t	free_node
	)

Definition at line 280 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_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_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_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:

Data Structures

Macros

Typedefs

Functions

Detailed Description

Data Structure Documentation

◆ fr_hash_iter_s

Macro Definition Documentation

◆ fr_hash_table_alloc

◆ fr_hash_table_talloc_alloc

Typedef Documentation

◆ fr_hash_entry_t

◆ fr_hash_iter_t

◆ fr_hash_t

◆ fr_hash_table_t

◆ fr_hash_table_walk_t

Function Documentation

◆ _fr_hash_table_alloc()

◆ fr_hash()

◆ fr_hash_case_string()

◆ fr_hash_string()

◆ fr_hash_table_delete()

◆ fr_hash_table_fill()

◆ fr_hash_table_find()

◆ fr_hash_table_find_by_key()

◆ fr_hash_table_flatten()

◆ fr_hash_table_insert()

◆ fr_hash_table_iter_init()

◆ fr_hash_table_iter_next()

◆ fr_hash_table_num_elements()

◆ fr_hash_table_remove()

◆ fr_hash_table_replace()

◆ fr_hash_table_verify()

◆ fr_hash_update()