hash.h File Reference

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:

Go to the source code of this file.

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. More...
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. More...
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) More...
void	fr_hash_table_fill (fr_hash_table_t *ht)
	Ensure all buckets are filled. More...
void *	fr_hash_table_find (fr_hash_table_t *ht, void const *data)
	Find data in a hash table. 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...
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...
bool	fr_hash_table_insert (fr_hash_table_t *ht, void const *data)
	Insert data into a hash table. More...
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...
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. More...
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. 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)

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 1 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 53 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 806 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 874 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 859 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 589 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 713 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 428 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 447 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 689 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 466 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 672 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 620 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 604 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 555 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 525 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 889 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 840 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function: