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

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

bool	fr_trie_delete (fr_trie_t ft, void const data)
	Remove node and free data (if a free function was specified) More...

void *	fr_trie_find (fr_trie_t ft, void const data)
	Find an element in the trie, returning the data. More...

bool	fr_trie_insert (fr_trie_t ft, void const data)
	Insert data into 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 (fr_trie_t ft, void const data)
	Match an element exactly in the trie, returning the data. 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...

unsigned int	fr_trie_num_elements (UNUSED fr_trie_t *ft)
	Return how many nodes there are in a trie. 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 (fr_trie_t ft, void const data)
	Remove an entry, without freeing the data. More...

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

int	fr_trie_replace (void *old, fr_trie_t ft, void const *data)
	Replace old data with new data, OR insert if there is no old. 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, int start_bit, int 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 2180 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 728 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 492 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 507 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 486 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 499 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 468 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 1329 of file trie.c.

◆ TRIE_HEADER

#define TRIE_HEADER uint8_t type; uint8_t bits

Definition at line 482 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 483 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 2156 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 2176 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 1334 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 1108 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 1912 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 456 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 2591 of file trie.c.

Here is the caller 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 743 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_delete()

bool fr_trie_delete	(	fr_trie_t *	ft,
		void const *	data
	)

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

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.

Definition at line 2789 of file trie.c.

Here is the call graph for this function:

◆ fr_trie_find()

void* fr_trie_find	(	fr_trie_t *	ft,
		void const *	data
	)

Find an element 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.

Definition at line 2643 of file trie.c.

Here is the call graph for this function:

◆ fr_trie_insert()

bool fr_trie_insert	(	fr_trie_t *	ft,
		void const *	data
	)

Insert data into a trie.

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.

Definition at line 2693 of file trie.c.

Here is the call 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 1877 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 1264 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_match()

void* fr_trie_match	(	fr_trie_t *	ft,
		void const *	data
	)

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.

Definition at line 2668 of file trie.c.

Here is the call 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 1288 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_num_elements()

unsigned int fr_trie_num_elements ( UNUSED fr_trie_t * ft )

Return how many nodes there are in a trie.

Parameters

[in] ft to return node count for.

Definition at line 2817 of file trie.c.

◆ 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 636 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_trie_remove()

void* fr_trie_remove	(	fr_trie_t *	ft,
		void const *	data
	)

Remove an entry, without freeing the 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.

Definition at line 2764 of file trie.c.

Here is the call 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 2156 of file trie.c.

Here is the caller graph for this function:

◆ fr_trie_replace()

int fr_trie_replace	(	void **	old,
		fr_trie_t *	ft,
		void const *	data
	)

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

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

Definition at line 2725 of file trie.c.

Here is the call 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 615 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 2609 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,
		int	start_bit,
		int	num_bits
	)

static

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

Definition at line 339 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 1048 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 564 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 889 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 1812 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 1228 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 2128 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 2266 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 530 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 1350 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 1147 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 1936 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 775 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 2199 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 1424 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 1162 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 1976 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 833 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 2221 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 1336 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 1112 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 1914 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 2190 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 411 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 1787 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 1202 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 2114 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 2255 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()

◆ fr_trie_alloc()

◆ fr_trie_delete()

◆ fr_trie_find()

◆ fr_trie_insert()

◆ fr_trie_insert_by_key()

◆ fr_trie_key_lcp()

◆ fr_trie_lookup_by_key()

◆ fr_trie_match()

◆ fr_trie_match_by_key()

◆ fr_trie_num_elements()

◆ fr_trie_path_alloc()

◆ fr_trie_remove()

◆ fr_trie_remove_by_key()

◆ fr_trie_replace()

◆ 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()