The FreeRADIUS server
$Id: 15bac2a4c627c01d1aa2047687b3418955ac7f00 $
|
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>
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) (fr_htrie_t *ht, void const *data) |
typedef void *(* | fr_htrie_find_t) (fr_htrie_t *ht, void const *data) |
typedef bool(* | fr_htrie_insert_t) (fr_htrie_t *ht, void const *data) |
typedef uint32_t(* | fr_htrie_num_elements_t) (fr_htrie_t *ht) |
typedef void *(* | fr_htrie_remove_t) (fr_htrie_t *ht, void const *data) |
typedef int(* | fr_htrie_replace_t) (void **old, fr_htrie_t *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 |
Structures and prototypes for hash / rbtree / patricia trie structures.
Definition in file htrie.h.
struct fr_htrie_funcs_t |
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. |
struct 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 bool(* fr_htrie_delete_t) (fr_htrie_t *ht, void const *data) |
typedef void*(* fr_htrie_find_t) (fr_htrie_t *ht, void const *data) |
typedef bool(* fr_htrie_insert_t) (fr_htrie_t *ht, void const *data) |
typedef uint32_t(* fr_htrie_num_elements_t) (fr_htrie_t *ht) |
typedef void*(* fr_htrie_remove_t) (fr_htrie_t *ht, void const *data) |
typedef int(* fr_htrie_replace_t) (void **old, fr_htrie_t *ht, void const *data) |
typedef struct fr_htrie_s fr_htrie_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. |
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.
[in] | ctx | to bind the htrie's lifetime to. |
[in] | type | One of:
|
[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. |
Definition at line 92 of file htrie.c.
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
extern |