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_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 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. More...

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. More...

static void *	fr_htrie_find (fr_htrie_t ht, void const data)
	Find data in a htrie. More...

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. More...

static void *	fr_htrie_match (fr_htrie_t ht, void const data)
	Match data in a htrie. More...

static int	fr_htrie_num_elements (fr_htrie_t *ht)
	Return the number of elements in the htrie. More...

static void *	fr_htrie_remove (fr_htrie_t ht, void const data)
	Remove data from a htrie without freeing it. More...

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. More...

static char const *	fr_htrie_type_to_str (fr_htrie_type_t type)
	Return a static string containing the type name. More...

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 67 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_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_s

struct fr_htrie_s

A hash/rb/prefix trie abstraction.

Definition at line 80 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_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 1 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 49 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 92 of file htrie.c.

Here is the call graph for this function: