trie.h File Reference

Path-compressed prefix tries. More...

#include <freeradius-devel/build.h>
#include <freeradius-devel/missing.h>
#include <freeradius-devel/util/talloc.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

Include dependency graph for trie.h:

Go to the source code of this file.

Typedefs
typedef int(*	fr_trie_key_t) (uint8_t **out, size_t *outlen, void const *data)
typedef struct fr_trie_s	fr_trie_t
typedef int(*	fr_trie_walk_t) (uint8_t const *key, size_t keylen, void *data, void *uctx)
	Walk over a trie. More...

Functions
fr_trie_t *	fr_trie_alloc (TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_node)
	Allocate a trie. More...
bool	fr_trie_delete (fr_trie_t *ft, void const *data)
void *	fr_trie_find (fr_trie_t *ft, void const *data)
bool	fr_trie_insert (fr_trie_t *ft, void const *data)
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...
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)
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 (fr_trie_t *ft)
void *	fr_trie_remove (fr_trie_t *ft, void const *data)
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))
int	fr_trie_walk (fr_trie_t *ft, void *ctx, fr_trie_walk_t callback))

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

Typedef Documentation

fr_trie_key_t

typedef int(* fr_trie_key_t) (uint8_t **out, size_t *outlen, void const *data)

Definition at line 56 of file trie.h.

fr_trie_t

typedef struct fr_trie_s fr_trie_t

Definition at line 1 of file trie.h.

fr_trie_walk_t

typedef int(* fr_trie_walk_t) (uint8_t const *key, size_t keylen, void *data, void *uctx)

Walk over a trie.

Definition at line 43 of file trie.h.

Function Documentation

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

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

fr_trie_find()

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

fr_trie_insert()

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

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

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

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

unsigned int fr_trie_num_elements

(

fr_trie_t *

ft

)

fr_trie_remove()

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

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

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

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: