Path-compressed prefix tries. More...

#include <freeradius-devel/util/dict.h>
#include <freeradius-devel/util/misc.h>
#include <freeradius-devel/util/syserror.h>
#include <freeradius-devel/util/trie.h>

Include dependency graph for trie.c:

Go to the source code of this file.

Data Structures
struct	fr_trie_callback_s

struct	fr_trie_ctx_t

struct	fr_trie_node_t

struct	fr_trie_path_t

struct	fr_trie_s

struct	fr_trie_user_t

Macros
#define	BITSOF(_x) ((_x) * 8)

#define	BYTEOF(_x) ((_x) >> 3)

#define	BYTES(_x) (((_x) + 0x07) >> 3)

#define	FR_TRIE_MAX (FR_TRIE_NODE + 1)

#define	MAX_KEY_BITS (MAX_KEY_BYTES * 8)

#define	MAX_KEY_BYTES (256)

#define	MAX_NODE_BITS (4)

#define	MPRINT(...)
	Internal sanity checks for debugging. More...

#define	MPRINT2(...)

#define	MPRINT3(...)

#define	trie_check(_trie, _key, _start_bit, _end_bit, _data, _lineno)

#define	TRIE_HEADER uint8_t type; uint8_t bits

#define	trie_sprint(_trie, _key, _start_bit, _lineno)

#define	TRIE_TYPE_CHECK(_x, _r)

#define	VERIFY(_x)

#define	WITH_PATH_COMPRESSION
	Enable path compression (or not) More...

Typedefs
typedef struct fr_trie_callback_s	fr_trie_callback_t

typedef int(*	fr_trie_key_walk_t) (fr_trie_t trie, fr_trie_callback_t cb, int depth, bool more)

typedef enum fr_trie_type_t	fr_trie_type_t

typedef int(*	trie_key_insert_t) (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit, void *data)

typedef void (	trie_key_match_t) (fr_trie_t trie, uint8_t const key, int start_bit, int end_bit, bool exact)

typedef void (	trie_key_remove_t) (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit)

Enumerations
enum	fr_trie_type_t { FR_TRIE_INVALID = 0 , FR_TRIE_USER , FR_TRIE_PATH , FR_TRIE_NODE }

Functions
static int	_trie_user_cb (fr_trie_t trie, fr_trie_callback_t cb, int keylen, UNUSED bool more)
	Implement the user-visible side of the walk callback. More...

	CC_NO_UBSAN (function)
	Find an element in the trie, returning the data. More...

fr_trie_t *	fr_trie_alloc (TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_data)
	Allocate a trie. More...

int	fr_trie_insert_by_key (fr_trie_t ft, void const key, size_t keylen, void const *data)
	Insert a key and user ctx into a trie. More...

static int	fr_trie_key_lcp (uint8_t const key1, int keylen1, uint8_t const key2, int keylen2, int start_bit)
	Get the longest prefix of the two keys. More...

void *	fr_trie_lookup_by_key (fr_trie_t const ft, void const key, size_t keylen)
	Lookup a key in a trie and return user ctx, if any. More...

void *	fr_trie_match_by_key (fr_trie_t const ft, void const key, size_t keylen)
	Match a key and length in a trie and return user ctx, if any. More...

static fr_trie_path_t *	fr_trie_path_alloc (TALLOC_CTX ctx, uint8_t const key, int start_bit, int end_bit)

void *	fr_trie_remove_by_key (fr_trie_t ft, void const key, size_t keylen)
	Remove a key and return the associated user ctx. More...

static fr_trie_user_t *	fr_trie_user_alloc (TALLOC_CTX ctx, void const data)

int	fr_trie_walk (fr_trie_t ft, void ctx, fr_trie_walk_t callback)

static uint16_t	get_chunk (uint8_t const *key, uint32_t start_bit, uint32_t num_bits)
	Return a chunk of a key (in the low bits) for use in 2^N node de-indexing. More...

static int	trie_add_edge (fr_trie_t trie, uint16_t chunk, fr_trie_t child)
	Add an edge to a node. More...

static void	trie_free (fr_trie_t *trie)
	Free a fr_trie_t. More...

static fr_trie_t *	trie_key_alloc (TALLOC_CTX ctx, uint8_t const key, int start_bit, int end_bit, void *data)

static int	trie_key_insert (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit, void *data)
	Insert a binary key into the trie. More...

static void *	trie_key_match (fr_trie_t trie, uint8_t const key, int start_bit, int end_bit, bool exact)
	Match a key in a trie and return user ctx, if any. More...

static void *	trie_key_remove (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit)
	Remove a key from a trie, and return the user data. More...

static int	trie_key_walk (fr_trie_t trie, fr_trie_callback_t cb, int depth, bool more)

static fr_trie_node_t *	trie_node_alloc (TALLOC_CTX *ctx, int bits)

static int	trie_node_insert (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit, void *data)

static void *	trie_node_match (fr_trie_t trie, uint8_t const key, int start_bit, int end_bit, bool exact)

static void *	trie_node_remove (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit)

static fr_trie_node_t *	trie_node_split (TALLOC_CTX ctx, fr_trie_node_t node, int bits)
	Split a node at bits. More...

static int	trie_node_walk (fr_trie_t trie, fr_trie_callback_t cb, int depth, bool more)

static int	trie_path_insert (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit, void *data)

static void *	trie_path_match (fr_trie_t trie, uint8_t const key, int start_bit, int end_bit, bool exact)

static void *	trie_path_remove (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit)

static fr_trie_path_t *	trie_path_split (TALLOC_CTX ctx, fr_trie_path_t path, int start_bit, int lcp)

static int	trie_path_walk (fr_trie_t trie, fr_trie_callback_t cb, int depth, bool more)

static int	trie_user_insert (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit, void *data)

static void *	trie_user_match (fr_trie_t trie, uint8_t const key, int start_bit, int end_bit, bool exact)

static void *	trie_user_remove (TALLOC_CTX ctx, fr_trie_t trie_p, uint8_t const key, int start_bit, int end_bit)

static int	trie_user_walk (fr_trie_t trie, fr_trie_callback_t cb, int depth, bool more)

static void	write_chunk (uint8_t *out, int start_bit, int num_bits, uint16_t chunk)
	Write a chunk to an output buffer. More...

Variables
static uint8_t	start_bit_mask [8]

static trie_key_insert_t	trie_insert_table [FR_TRIE_MAX]

static trie_key_match_t	trie_match_table [FR_TRIE_MAX]

static trie_key_remove_t	trie_remove_table [FR_TRIE_MAX]

static fr_trie_key_walk_t	trie_walk_table [FR_TRIE_MAX]

static uint8_t	used_bit_mask [8]

static uint8_t	xor2lcp [256]

Detailed Description

Path-compressed prefix tries.

Copyright: 2017 Alan DeKok (aland.nosp@m.@fre.nosp@m.eradi.nosp@m.us.o.nosp@m.rg)

Definition in file trie.c.

Data Structure Documentation

◆ fr_trie_callback_s

struct fr_trie_callback_s

Definition at line 2178 of file trie.c.

Collaboration diagram for fr_trie_callback_s:

Data Fields
fr_trie_key_walk_t	callback
void *	ctx
uint8_t const *	end
uint8_t *	start
fr_trie_walk_t	user_callback

◆ fr_trie_ctx_t

struct fr_trie_ctx_t

Definition at line 726 of file trie.c.

Data Fields
uint8_t	buffer[16]
fr_free_t	free_data
fr_trie_key_t	get_key

◆ fr_trie_node_t

struct fr_trie_node_t

Definition at line 490 of file trie.c.

Collaboration diagram for fr_trie_node_t:

Data Fields
fr_trie_t *	trie[]
	TRIE_HEADER
int	used

◆ fr_trie_path_t

struct fr_trie_path_t

Definition at line 505 of file trie.c.

Collaboration diagram for fr_trie_path_t:

Data Fields
uint16_t	chunk
uint8_t	key[2]
fr_trie_t *	trie
	TRIE_HEADER

◆ fr_trie_s

struct fr_trie_s

Definition at line 484 of file trie.c.

Collaboration diagram for fr_trie_s:

Data Fields
fr_trie_t *	trie
	TRIE_HEADER

◆ fr_trie_user_t

struct fr_trie_user_t

Definition at line 497 of file trie.c.

Collaboration diagram for fr_trie_user_t:

Data Fields
void *	data
fr_trie_t *	trie
	TRIE_HEADER

Macro Definition Documentation

◆ BITSOF

#define BITSOF ( _x ) ((_x) * 8)

Definition at line 136 of file trie.c.

◆ BYTEOF

#define BYTEOF ( _x ) ((_x) >> 3)

Definition at line 137 of file trie.c.

◆ BYTES

#define BYTES ( _x ) (((_x) + 0x07) >> 3)

Definition at line 138 of file trie.c.

◆ FR_TRIE_MAX

#define FR_TRIE_MAX (FR_TRIE_NODE + 1)

Definition at line 466 of file trie.c.

◆ MAX_KEY_BITS

#define MAX_KEY_BITS (MAX_KEY_BYTES * 8)

Definition at line 95 of file trie.c.

◆ MAX_KEY_BYTES

#define MAX_KEY_BYTES (256)

Definition at line 94 of file trie.c.

◆ MAX_NODE_BITS

#define MAX_NODE_BITS (4)

Definition at line 98 of file trie.c.

◆ MPRINT

#define MPRINT ( ... )

Internal sanity checks for debugging.

Tries are complex. So we have verification routines for every type of node. These routines are called from within the trie manipulation functions. If the trie manipulation has a bug, the verification routines are likely to catch some of the more egregious issues.

Definition at line 119 of file trie.c.

◆ MPRINT2

#define MPRINT2 ( ... )

Definition at line 120 of file trie.c.

◆ MPRINT3

#define MPRINT3 ( ... )

Definition at line 121 of file trie.c.

◆ trie_check

#define trie_check	(	_trie,
		_key,
		_start_bit,
		_end_bit,
		_data,
		_lineno
	)

Definition at line 1327 of file trie.c.

◆ TRIE_HEADER

#define TRIE_HEADER uint8_t type; uint8_t bits

Definition at line 480 of file trie.c.

◆ trie_sprint

#define trie_sprint	(	_trie,
		_key,
		_start_bit,
		_lineno
	)

Definition at line 122 of file trie.c.

◆ TRIE_TYPE_CHECK

#define TRIE_TYPE_CHECK	(	_x,
		_r
	)

Definition at line 481 of file trie.c.

◆ VERIFY

#define VERIFY ( _x )

Definition at line 130 of file trie.c.

◆ WITH_PATH_COMPRESSION

#define WITH_PATH_COMPRESSION

Enable path compression (or not)

With path compression, long sequences of bits are stored as a path, e.g. "abcdef". Without path compression, we would have to create a large number of intermediate 2^N-way nodes, all of which would have only one edge.

Definition at line 74 of file trie.c.

Typedef Documentation

◆ fr_trie_callback_t

typedef struct fr_trie_callback_s fr_trie_callback_t

Definition at line 2154 of file trie.c.

◆ fr_trie_key_walk_t

typedef int(* fr_trie_key_walk_t) (fr_trie_t *trie, fr_trie_callback_t *cb, int depth, bool more)

Definition at line 2174 of file trie.c.

◆ fr_trie_type_t

typedef enum fr_trie_type_t fr_trie_type_t

◆ trie_key_insert_t

typedef int(* trie_key_insert_t) (TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit, void *data)

Definition at line 1332 of file trie.c.

◆ trie_key_match_t

typedef void*(* trie_key_match_t) (fr_trie_t *trie, uint8_t const *key, int start_bit, int end_bit, bool exact)

Definition at line 1106 of file trie.c.

◆ trie_key_remove_t

typedef void*(* trie_key_remove_t) (TALLOC_CTX *ctx, fr_trie_t **trie_p, uint8_t const *key, int start_bit, int end_bit)

Definition at line 1910 of file trie.c.

Enumeration Type Documentation

◆ fr_trie_type_t

enum fr_trie_type_t

Enumerator
FR_TRIE_INVALID
FR_TRIE_USER
FR_TRIE_PATH
FR_TRIE_NODE

Definition at line 454 of file trie.c.

Function Documentation

◆ _trie_user_cb()

static int _trie_user_cb	(	fr_trie_t *	trie,
		fr_trie_callback_t *	cb,
		int	keylen,
		UNUSED bool	more
	)

static

Implement the user-visible side of the walk callback.

Definition at line 2589 of file trie.c.

Here is the caller graph for this function:

◆ CC_NO_UBSAN()

CC_NO_UBSAN ( function )

Find an element in the trie, returning the data.

Return how many nodes there are in a trie.

Remove node and free data (if a free function was specified)

Remove an entry, without freeing the data.

Replace old data with new data, OR insert if there is no old.

Insert data into a trie.

Match an element exactly in the trie, returning the data.

Parameters

[in]	ft	to search in.
[in]	data	to find.

Returns

User data matching the data passed in.
NULL if nothing matched passed data.

Parameters

[in]	ft	to insert data into.
[in]	data	to insert.

Returns

true if data was inserted.
false if data already existed and was not inserted.

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]	ft	to insert data into.
[in]	data	to replace.

Returns

1 if data was replaced.
0 if data was inserted.
-1 if we failed to replace data

Parameters

[in]	ft	to remove data from.
[in]	data	to remove.

Returns

The user data we removed.
NULL if we couldn't find any matching data.

Parameters

[in]	ft	to remove data from.
[in]	data	to remove/free.

Returns

true if we removed data.
false if we couldn't find any matching data.

Parameters

[in] ft to return node count for.

Definition at line 2641 of file trie.c.

Here is the call graph for this function:

◆ fr_trie_alloc()

fr_trie_t* fr_trie_alloc	(	TALLOC_CTX *	ctx,
		fr_trie_key_t	get_key,
		fr_free_t	free_data
	)

Allocate a trie.

Parameters

ctx	The talloc ctx.
get_key	The "get key from object" function.
free_data	Callback to free data.

Returns

NULL on error
fr_trie_node_t on success

Definition at line 741 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_insert_by_key()

int fr_trie_insert_by_key	(	fr_trie_t *	ft,
		void const *	key,
		size_t	keylen,
		void const *	data
	)

Insert a key and user ctx into a trie.

Parameters

ft	the trie
key	the key
keylen	key length in bits
data	user ctx information to associated with the key

Returns

<0 on error
0 on success

Definition at line 1875 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_key_lcp()

static int fr_trie_key_lcp	(	uint8_t const *	key1,
		int	keylen1,
		uint8_t const *	key2,
		int	keylen2,
		int	start_bit
	)

static

Get the longest prefix of the two keys.

Definition at line 227 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_lookup_by_key()

void* fr_trie_lookup_by_key	(	fr_trie_t const *	ft,
		void const *	key,
		size_t	keylen
	)

Lookup a key in a trie and return user ctx, if any.

The key may be LONGER than entries in the trie. In which case the closest match is returned.

Parameters

ft	the trie
key	the key bytes
keylen	length in bits of the key

Returns

NULL on not found
void* user ctx on found

Definition at line 1262 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_match_by_key()

void* fr_trie_match_by_key	(	fr_trie_t const *	ft,
		void const *	key,
		size_t	keylen
	)

Match a key and length in a trie and return user ctx, if any.

Only the exact match is returned.

Parameters

ft	the trie
key	the key bytes
keylen	length in bits of the key

Returns

NULL on not found
void* user ctx on found

Definition at line 1286 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_path_alloc()

static fr_trie_path_t* fr_trie_path_alloc	(	TALLOC_CTX *	ctx,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit
	)

static

Definition at line 634 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_remove_by_key()

void* fr_trie_remove_by_key	(	fr_trie_t *	ft,
		void const *	key,
		size_t	keylen
	)

Remove a key and return the associated user ctx.

The key must match EXACTLY. This is not a prefix match.

Parameters

ft	the trie
key	the key
keylen	key length in bits

Returns

NULL on not found
user ctx data on success

Definition at line 2154 of file trie.c.

Here is the caller graph for this function:

◆ fr_trie_user_alloc()

static fr_trie_user_t* fr_trie_user_alloc	(	TALLOC_CTX *	ctx,
		void const *	data
	)

static

Definition at line 613 of file trie.c.

Here is the caller graph for this function:

◆ fr_trie_walk()

int fr_trie_walk	(	fr_trie_t *	ft,
		void *	ctx,
		fr_trie_walk_t	callback
	)

Definition at line 2607 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_chunk()

static uint16_t get_chunk	(	uint8_t const *	key,
		uint32_t	start_bit,
		uint32_t	num_bits
	)

static

Return a chunk of a key (in the low bits) for use in 2^N node de-indexing.

Definition at line 337 of file trie.c.

Here is the caller graph for this function:

◆ trie_add_edge()

static int trie_add_edge	(	fr_trie_t *	trie,
		uint16_t	chunk,
		fr_trie_t *	child
	)

static

Add an edge to a node.

This function is so that we can abstract 2^N-way nodes, or compressed edge nodes.

Definition at line 1046 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ trie_free()

static void trie_free ( fr_trie_t * trie )

static

Free a fr_trie_t.

We can't use talloc_free(), because we can't talloc_parent the nodes from each other, as talloc_steal() is O(N). So, we just recurse manually.

Definition at line 562 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ trie_key_alloc()

static fr_trie_t* trie_key_alloc	(	TALLOC_CTX *	ctx,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		void *	data
	)

static

Definition at line 887 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ trie_key_insert()

static int trie_key_insert	(	TALLOC_CTX *	ctx,
		fr_trie_t **	trie_p,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		void *	data
	)

static

Insert a binary key into the trie.

The key must have at least ((start_bit + keylen) >> 3) bytes

Parameters

	ctx	the talloc ctx
[in,out]	trie_p	the trie where things are inserted
	key	the binary key
	start_bit	the start bit
	end_bit	the end bit
	data	user data to insert

Returns

<0 on error
0 on success

Definition at line 1810 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ trie_key_match()

static void * trie_key_match	(	fr_trie_t *	trie,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		bool	exact
	)

static

Match a key in a trie and return user ctx, if any.

The key may be LONGER than entries in the trie. In which case the closest match is returned.

Parameters

trie	the trie
key	the key
start_bit	the start bit
end_bit	the end bit
exact	do we return an exact match, or the shortest one.

Returns

NULL on not found
void* user ctx on found

Definition at line 1226 of file trie.c.

Here is the caller graph for this function:

◆ trie_key_remove()

static void * trie_key_remove	(	TALLOC_CTX *	ctx,
		fr_trie_t **	trie_p,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit
	)

static

Remove a key from a trie, and return the user data.

Definition at line 2126 of file trie.c.

Here is the caller graph for this function:

◆ trie_key_walk()

static int trie_key_walk	(	fr_trie_t *	trie,
		fr_trie_callback_t *	cb,
		int	depth,
		bool	more
	)

static

Definition at line 2264 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ trie_node_alloc()

static fr_trie_node_t* trie_node_alloc	(	TALLOC_CTX *	ctx,
		int	bits
	)

static

Definition at line 528 of file trie.c.

Here is the caller graph for this function:

◆ trie_node_insert()

static int trie_node_insert	(	TALLOC_CTX *	ctx,
		fr_trie_t **	trie_p,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		void *	data
	)

static

Definition at line 1348 of file trie.c.

Here is the call graph for this function:

◆ trie_node_match()

static void* trie_node_match	(	fr_trie_t *	trie,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		bool	exact
	)

static

Definition at line 1145 of file trie.c.

Here is the call graph for this function:

◆ trie_node_remove()

static void* trie_node_remove	(	TALLOC_CTX *	ctx,
		fr_trie_t **	trie_p,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit
	)

static

Definition at line 1934 of file trie.c.

Here is the call graph for this function:

◆ trie_node_split()

static fr_trie_node_t* trie_node_split	(	TALLOC_CTX *	ctx,
		fr_trie_node_t *	node,
		int	bits
	)

static

Split a node at bits.

Definition at line 773 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ trie_node_walk()

static int trie_node_walk	(	fr_trie_t *	trie,
		fr_trie_callback_t *	cb,
		int	depth,
		bool	more
	)

static

Definition at line 2197 of file trie.c.

Here is the call graph for this function:

◆ trie_path_insert()

static int trie_path_insert	(	TALLOC_CTX *	ctx,
		fr_trie_t **	trie_p,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		void *	data
	)

static

Definition at line 1422 of file trie.c.

Here is the call graph for this function:

◆ trie_path_match()

static void* trie_path_match	(	fr_trie_t *	trie,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		bool	exact
	)

static

Definition at line 1160 of file trie.c.

Here is the call graph for this function:

◆ trie_path_remove()

static void* trie_path_remove	(	TALLOC_CTX *	ctx,
		fr_trie_t **	trie_p,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit
	)

static

Definition at line 1974 of file trie.c.

Here is the call graph for this function:

◆ trie_path_split()

static fr_trie_path_t* trie_path_split	(	TALLOC_CTX *	ctx,
		fr_trie_path_t *	path,
		int	start_bit,
		int	lcp
	)

static

Definition at line 831 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ trie_path_walk()

static int trie_path_walk	(	fr_trie_t *	trie,
		fr_trie_callback_t *	cb,
		int	depth,
		bool	more
	)

static

Definition at line 2219 of file trie.c.

Here is the call graph for this function:

◆ trie_user_insert()

static int trie_user_insert	(	TALLOC_CTX *	ctx,
		fr_trie_t **	trie_p,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		void *	data
	)

static

Definition at line 1334 of file trie.c.

Here is the call graph for this function:

◆ trie_user_match()

static void* trie_user_match	(	fr_trie_t *	trie,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit,
		bool	exact
	)

static

Definition at line 1110 of file trie.c.

Here is the call graph for this function:

◆ trie_user_remove()

static void* trie_user_remove	(	TALLOC_CTX *	ctx,
		fr_trie_t **	trie_p,
		uint8_t const *	key,
		int	start_bit,
		int	end_bit
	)

static

Definition at line 1912 of file trie.c.

Here is the call graph for this function:

◆ trie_user_walk()

static int trie_user_walk	(	fr_trie_t *	trie,
		fr_trie_callback_t *	cb,
		int	depth,
		bool	more
	)

static

Definition at line 2188 of file trie.c.

Here is the call graph for this function:

◆ write_chunk()

static void write_chunk	(	uint8_t *	out,
		int	start_bit,
		int	num_bits,
		uint16_t	chunk
	)

static

Write a chunk to an output buffer.

Definition at line 409 of file trie.c.

Here is the caller graph for this function:

Variable Documentation

◆ start_bit_mask

uint8_t start_bit_mask[8]

static

Initial value:

= {
        0xff, 0x7f, 0x3f, 0x1f,
        0x0f, 0x07, 0x03, 0x01
}

Definition at line 150 of file trie.c.

◆ trie_insert_table

trie_key_insert_t trie_insert_table[FR_TRIE_MAX]

static

Initial value:

= {
        [ FR_TRIE_USER ] = trie_user_insert,
        [ FR_TRIE_NODE ] = trie_node_insert,
 
        [ FR_TRIE_PATH ] = trie_path_insert,
 
}

Definition at line 1785 of file trie.c.

◆ trie_match_table

trie_key_match_t trie_match_table[FR_TRIE_MAX]

static

Initial value:

= {
        [ FR_TRIE_USER ] = trie_user_match,
        [ FR_TRIE_NODE ] = trie_node_match,
 
        [ FR_TRIE_PATH ] = trie_path_match,
 
}

Definition at line 1200 of file trie.c.

◆ trie_remove_table

trie_key_remove_t trie_remove_table[FR_TRIE_MAX]

static

Initial value:

= {
        [ FR_TRIE_USER ] = trie_user_remove,
        [ FR_TRIE_NODE ] = trie_node_remove,
 
        [ FR_TRIE_PATH ] = trie_path_remove,
 
}

Definition at line 2112 of file trie.c.

◆ trie_walk_table

fr_trie_key_walk_t trie_walk_table[FR_TRIE_MAX]

static

Initial value:

= {
        [ FR_TRIE_USER ] = trie_user_walk,
        [ FR_TRIE_NODE ] = trie_node_walk,
 
        [ FR_TRIE_PATH ] = trie_path_walk,
 
}

Definition at line 2253 of file trie.c.

◆ used_bit_mask

uint8_t used_bit_mask[8]

static

Initial value:

= {
        0x80, 0xc0, 0xe0, 0xf0,
        0xf8, 0xfc, 0xfe, 0xff,
}

Definition at line 155 of file trie.c.

◆ xor2lcp

uint8_t xor2lcp[256]

static

Definition at line 172 of file trie.c.

Data Structures

Macros

Typedefs

Enumerations

Functions

Variables

Detailed Description

Data Structure Documentation

◆ fr_trie_callback_s

◆ fr_trie_ctx_t

◆ fr_trie_node_t

◆ fr_trie_path_t

◆ fr_trie_s

◆ fr_trie_user_t

Macro Definition Documentation

◆ BITSOF

◆ BYTEOF

◆ BYTES

◆ FR_TRIE_MAX

◆ MAX_KEY_BITS

◆ MAX_KEY_BYTES

◆ MAX_NODE_BITS

◆ MPRINT

◆ MPRINT2

◆ MPRINT3

◆ trie_check

◆ TRIE_HEADER

◆ trie_sprint

◆ TRIE_TYPE_CHECK

◆ VERIFY

◆ WITH_PATH_COMPRESSION

Typedef Documentation

◆ fr_trie_callback_t

◆ fr_trie_key_walk_t

◆ fr_trie_type_t

◆ trie_key_insert_t

◆ trie_key_match_t

◆ trie_key_remove_t

Enumeration Type Documentation

◆ fr_trie_type_t

Function Documentation

◆ _trie_user_cb()

◆ CC_NO_UBSAN()

◆ fr_trie_alloc()

◆ fr_trie_insert_by_key()

◆ fr_trie_key_lcp()

◆ fr_trie_lookup_by_key()

◆ fr_trie_match_by_key()

◆ fr_trie_path_alloc()

◆ fr_trie_remove_by_key()

◆ fr_trie_user_alloc()

◆ fr_trie_walk()

◆ get_chunk()

◆ trie_add_edge()

◆ trie_free()

◆ trie_key_alloc()

◆ trie_key_insert()

◆ trie_key_match()

◆ trie_key_remove()

◆ trie_key_walk()

◆ trie_node_alloc()

◆ trie_node_insert()

◆ trie_node_match()

◆ trie_node_remove()

◆ trie_node_split()

◆ trie_node_walk()

◆ trie_path_insert()

◆ trie_path_match()

◆ trie_path_remove()

◆ trie_path_split()

◆ trie_path_walk()

◆ trie_user_insert()

◆ trie_user_match()

◆ trie_user_remove()

◆ trie_user_walk()

◆ write_chunk()

Variable Documentation

◆ start_bit_mask

◆ trie_insert_table

◆ trie_match_table