htrie.h File Reference

Structures and prototypes for hash / rbtree / patricia trie structures. More...

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

Include dependency graph for htrie.h:

Go to the source code of this file.

Data Structures
struct	fr_htrie_funcs_t
	Which functions are used for the different operations. More...
struct	fr_htrie_iter_t
union	fr_htrie_iter_t.__unnamed136__
struct	fr_htrie_s
	A hash/rb/prefix trie abstraction. More...

Typedefs
typedef bool(*	fr_htrie_delete_t) (void *ht, void const *data)
typedef void *(*	fr_htrie_find_t) (void *ht, void const *data)
typedef bool(*	fr_htrie_insert_t) (void *ht, void const *data)
typedef void *(*	fr_htrie_iter_func_t) (void *ht, void *iter)
typedef uint32_t(*	fr_htrie_num_elements_t) (void *ht)
typedef void *(*	fr_htrie_remove_t) (void *ht, void const *data)
typedef int(*	fr_htrie_replace_t) (void **old, void *ht, void const *data)
typedef struct fr_htrie_s	fr_htrie_t

Enumerations
enum	fr_htrie_type_t {   FR_HTRIE_INVALID = 0 ,   FR_HTRIE_HASH ,   FR_HTRIE_RB ,   FR_HTRIE_TRIE ,   FR_HTRIE_AUTO }

Functions
fr_htrie_t *	fr_htrie_alloc (TALLOC_CTX *ctx, fr_htrie_type_t type, fr_hash_t hash_data, fr_cmp_t cmp_data, fr_trie_key_t get_key, fr_free_t free_data)
	An abstraction over our internal hashes, rb trees, and prefix tries.
static bool	fr_htrie_delete (fr_htrie_t *ht, void const *data)
	Delete data from a htrie, freeing it if free_data cb was passed to fr_htrie_alloc.
static void *	fr_htrie_find (fr_htrie_t *ht, void const *data)
	Find data in a htrie.
static fr_htrie_type_t	fr_htrie_hint (fr_type_t type)
static bool	fr_htrie_insert (fr_htrie_t *ht, void const *data)
	Insert data into a htrie.
static void *	fr_htrie_iter_init (fr_htrie_t *ht, fr_htrie_iter_t *iter)
	Initialize an iterator.
static void *	fr_htrie_iter_next (fr_htrie_t *ht, fr_htrie_iter_t *iter)
	Return the next element of an iterator.
static void *	fr_htrie_match (fr_htrie_t *ht, void const *data)
	Match data in a htrie.
static int	fr_htrie_num_elements (fr_htrie_t *ht)
	Return the number of elements in the htrie.
static void *	fr_htrie_remove (fr_htrie_t *ht, void const *data)
	Remove data from a htrie without freeing it.
static int	fr_htrie_replace (void **old, fr_htrie_t *ht, void const *data)
	Replace data in a htrie, freeing previous data if free_data cb was passed to fr_htrie_alloc.
static char const *	fr_htrie_type_to_str (fr_htrie_type_t type)
	Return a static string containing the type name.

Variables
fr_table_num_sorted_t const	fr_htrie_type_table []
size_t	fr_htrie_type_table_len

Detailed Description

Structures and prototypes for hash / rbtree / patricia trie structures.

Copyright

2021 The FreeRADIUS server project

Definition in file htrie.h.

---

Data Structure Documentation

fr_htrie_funcs_t

struct fr_htrie_funcs_t

Which functions are used for the different operations.

Definition at line 76 of file htrie.h.

Data Fields
fr_htrie_delete_t	delete	Remove (and possibly free) and item from the store.
fr_htrie_find_t	find	Absolute or prefix match.
fr_htrie_insert_t	insert	Insert a new item into the store.
fr_htrie_iter_func_t	iter_init	Initialize an iterator.
fr_htrie_iter_func_t	iter_next	go to the next element in an iterator
fr_htrie_find_t	match	exact prefix match
fr_htrie_num_elements_t	num_elements	Number of elements currently in the store.
fr_htrie_remove_t	remove	Remove an item from the store.
fr_htrie_replace_t	replace	Replace an existing item in store.

fr_htrie_iter_t

struct fr_htrie_iter_t

Definition at line 49 of file htrie.h.

Data Fields
union fr_htrie_iter_t.__unnamed136__	__unnamed__

fr_htrie_iter_t.__unnamed136__

union fr_htrie_iter_t.__unnamed136__

Definition at line 50 of file htrie.h.

Data Fields
fr_hash_iter_t	hash	effectively random
fr_rb_iter_inorder_t	rb	only in order

fr_htrie_s

struct fr_htrie_s

A hash/rb/prefix trie abstraction.

Definition at line 91 of file htrie.h.

Collaboration diagram for fr_htrie_s:

Data Fields
fr_htrie_funcs_t	funcs	Function pointers for the various operations.
void *	store	What we're using to store node data.
fr_htrie_type_t	type	type of the htrie

Typedef Documentation

fr_htrie_delete_t

typedef bool(* fr_htrie_delete_t) (void *ht, void const *data)

Definition at line 45 of file htrie.h.

fr_htrie_find_t

typedef void *(* fr_htrie_find_t) (void *ht, void const *data)

Definition at line 37 of file htrie.h.

fr_htrie_insert_t

typedef bool(* fr_htrie_insert_t) (void *ht, void const *data)

Definition at line 39 of file htrie.h.

fr_htrie_iter_func_t

typedef void *(* fr_htrie_iter_func_t) (void *ht, void *iter)

Definition at line 56 of file htrie.h.

fr_htrie_num_elements_t

typedef uint32_t(* fr_htrie_num_elements_t) (void *ht)

Definition at line 47 of file htrie.h.

fr_htrie_remove_t

typedef void *(* fr_htrie_remove_t) (void *ht, void const *data)

Definition at line 43 of file htrie.h.

fr_htrie_replace_t

typedef int(* fr_htrie_replace_t) (void **old, void *ht, void const *data)

Definition at line 41 of file htrie.h.

fr_htrie_t

typedef struct fr_htrie_s fr_htrie_t

Definition at line 35 of file htrie.h.

Enumeration Type Documentation

fr_htrie_type_t

enum fr_htrie_type_t

Enumerator
FR_HTRIE_INVALID
FR_HTRIE_HASH	Data is stored in a hash.
FR_HTRIE_RB	Data is stored in a rb tree.
FR_HTRIE_TRIE	Data is stored in a prefix trie.
FR_HTRIE_AUTO	Automatically choose the best type. Must be not be passed to fr_htrie_alloc(). If the user selects this, you must call fr_htrie_hint() to determine the best type.

Definition at line 58 of file htrie.h.

Function Documentation

fr_htrie_alloc()

fr_htrie_t * fr_htrie_alloc	(	TALLOC_CTX *	ctx,
		fr_htrie_type_t	type,
		fr_hash_t	hash_data,
		fr_cmp_t	cmp_data,
		fr_trie_key_t	get_key,
		fr_free_t	free_data
	)

An abstraction over our internal hashes, rb trees, and prefix tries.

This is useful where the data type being inserted into the tree is user controlled, and so we need to pick the most efficient structure for a given data type dynamically at runtime.

Parameters

[in]	ctx	to bind the htrie's lifetime to.
[in]	type	One of: FR_HTRIE_HASH FR_HTRIE_RB FR_HTRIE_TRIE
[in]	hash_data	Used by FR_HTRIE_HASH to convert the data into a 32bit integer used for binning.
[in]	cmp_data	Used to determine exact matched.
[in]	get_key	Used by the prefix trie to extract a key from the data.
[in]	free_data	The callback used to free the data if it is deleted or replaced. May be NULL in which case data will not be freed for these operations.

Returns

• A new htrie on success.
• NULL on failure, either missing functions or a memory allocation error.

Definition at line 95 of file htrie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_htrie_delete()

static bool fr_htrie_delete ( fr_htrie_t *  ht, void const *  data  )

inlinestatic

Delete data from a htrie, freeing it if free_data cb was passed to fr_htrie_alloc.

Definition at line 147 of file htrie.h.

Here is the caller graph for this function:

fr_htrie_find()

static void * fr_htrie_find ( fr_htrie_t *  ht, void const *  data  )

inlinestatic

Find data in a htrie.

Definition at line 115 of file htrie.h.

Here is the caller graph for this function:

fr_htrie_hint()

static fr_htrie_type_t fr_htrie_hint ( fr_type_t  type )

inlinestatic

Definition at line 180 of file htrie.h.

Here is the caller graph for this function:

fr_htrie_insert()

static bool fr_htrie_insert ( fr_htrie_t *  ht, void const *  data  )

inlinestatic

Insert data into a htrie.

Definition at line 123 of file htrie.h.

Here is the caller graph for this function:

fr_htrie_iter_init()

static void * fr_htrie_iter_init ( fr_htrie_t *  ht, fr_htrie_iter_t *  iter  )

inlinestatic

Initialize an iterator.

Definition at line 163 of file htrie.h.

fr_htrie_iter_next()

static void * fr_htrie_iter_next ( fr_htrie_t *  ht, fr_htrie_iter_t *  iter  )

inlinestatic

Return the next element of an iterator.

Definition at line 173 of file htrie.h.

fr_htrie_match()

static void * fr_htrie_match ( fr_htrie_t *  ht, void const *  data  )

inlinestatic

Match data in a htrie.

Definition at line 107 of file htrie.h.

Here is the caller graph for this function:

fr_htrie_num_elements()

static int fr_htrie_num_elements ( fr_htrie_t *  ht )

inlinestatic

Return the number of elements in the htrie.

Definition at line 155 of file htrie.h.

Here is the caller graph for this function:

fr_htrie_remove()

static void * fr_htrie_remove ( fr_htrie_t *  ht, void const *  data  )

inlinestatic

Remove data from a htrie without freeing it.

Definition at line 139 of file htrie.h.

Here is the caller graph for this function:

fr_htrie_replace()

static int fr_htrie_replace ( void **  old, fr_htrie_t *  ht, void const *  data  )

inlinestatic

Replace data in a htrie, freeing previous data if free_data cb was passed to fr_htrie_alloc.

Definition at line 131 of file htrie.h.

Here is the caller graph for this function:

fr_htrie_type_to_str()

static char const * fr_htrie_type_to_str ( fr_htrie_type_t  type )

inlinestatic

Return a static string containing the type name.

Parameters

[in]

type

to return name for.

Returns

name of the type

Definition at line 213 of file htrie.h.

Variable Documentation

fr_htrie_type_table

fr_table_num_sorted_t const fr_htrie_type_table[]

extern

Definition at line 30 of file htrie.c.

fr_htrie_type_table_len

size_t fr_htrie_type_table_len

extern

Definition at line 36 of file htrie.c.