htrie.c File Reference

hash / rb / patricia trees More...

#include <freeradius-devel/util/debug.h>
#include <freeradius-devel/util/htrie.h>
#include <freeradius-devel/util/table.h>

Include dependency graph for htrie.c:

Go to the source code of this file.

Macros
#define	FUNC(_prefix, _op)   ._op = (fr_htrie_ ##_op ## _t) fr_##_prefix##_## _op

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

Variables
static fr_htrie_funcs_t const	default_funcs []
fr_table_num_sorted_t const	fr_htrie_type_table []
size_t	fr_htrie_type_table_len = NUM_ELEMENTS(fr_htrie_type_table)

Detailed Description

hash / rb / patricia trees

Copyright

2021 Network RADIUS SAS (legal.nosp@m.@net.nosp@m.workr.nosp@m.adiu.nosp@m.s.com)

Definition in file htrie.c.

Macro Definition Documentation

FUNC

#define FUNC	(		_prefix,
			_op
	)		._op = (fr_htrie_ ##_op ## _t) fr_##_prefix##_## _op

Definition at line 29 of file htrie.c.

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:

Here is the caller graph for this function:

Variable Documentation

default_funcs

fr_htrie_funcs_t const default_funcs[]

static

Initial value:

= {
        [FR_HTRIE_HASH] = {
                .match = (fr_htrie_find_t) fr_hash_table_find,
                FUNC(hash_table, find),
                FUNC(hash_table, insert),
                FUNC(hash_table, replace),
                FUNC(hash_table, remove),
                FUNC(hash_table, delete),
 
        },
        [FR_HTRIE_RB] = {
                .match = (fr_htrie_find_t) fr_rb_find,
                FUNC(rb, find),
                FUNC(rb, insert),
                FUNC(rb, replace),
                FUNC(rb, remove),
                FUNC(rb, delete),
 
        },
        [FR_HTRIE_TRIE] = {
                .match = (fr_htrie_find_t) fr_trie_match,
                FUNC(trie, find),
                FUNC(trie, insert),
                FUNC(trie, replace),
                FUNC(trie, remove),
                FUNC(trie, delete),
 
        }
}

Definition at line 39 of file htrie.c.

fr_htrie_type_table

fr_table_num_sorted_t const fr_htrie_type_table[]

Initial value:

= {
        { L("auto"),            FR_HTRIE_AUTO },
        { L("hash"),            FR_HTRIE_HASH },
        { L("rb"),              FR_HTRIE_RB },
        { L("trie"),            FR_HTRIE_TRIE },
}

Definition at line 31 of file htrie.c.

fr_htrie_type_table_len

size_t fr_htrie_type_table_len = NUM_ELEMENTS(fr_htrie_type_table)

Definition at line 37 of file htrie.c.