trie.h File Reference

Path-compressed prefix tries. More...

#include <freeradius-devel/build.h>
#include <freeradius-devel/missing.h>
#include <freeradius-devel/util/misc.h>
#include <freeradius-devel/util/talloc.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.

Functions
fr_trie_t *	fr_trie_alloc (TALLOC_CTX *ctx, fr_trie_key_t get_key, fr_free_t free_node)
	Allocate a trie.
int	fr_trie_delete (fr_trie_t *ft, void const *data)
	Remove node and free data (if a free function was specified)
int	fr_trie_find (void **found, fr_trie_t *ft, void const *data)
	Find an element in the trie, returning the data.
int	fr_trie_insert (fr_trie_t *ft, void const *data)
	Insert data into a trie.
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.
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.
int	fr_trie_match (void **found, fr_trie_t *ft, void const *data)
	Match an element exactly in the trie, returning the 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.
unsigned int	fr_trie_num_elements (fr_trie_t *ft)
int	fr_trie_remove (void **removed, fr_trie_t *ft, void const *data))
	Remove an entry, without freeing the 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.
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.
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 55 of file trie.h.

fr_trie_t

typedef struct fr_trie_s fr_trie_t

Definition at line 37 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 42 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()

int 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

• 0 if we removed data.
• 1 if we couldn't find any matching data.

Definition at line 2814 of file trie.c.

Here is the call graph for this function:

fr_trie_find()

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

Find an element in the trie, returning the data.

Parameters

[out]	found	the matching element, or NULL if no element matched.
[in]	ft	to search in.
[in]	data	to find.

Returns

• 0 always, tries never run a comparator. Check found for the result.

Definition at line 2645 of file trie.c.

Here is the call graph for this function:

fr_trie_insert()

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

Insert data into a trie.

Note

Unlike the other containers, inserting a duplicate reports -1, not 1, as the trie key path doesn't distinguish duplicates from other insertion failures.

Parameters

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

Returns

• 0 if data was inserted.
• -1 if data was not inserted, retrieve the error with fr_strerror.

Definition at line 2707 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 1878 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 1265 of file trie.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_trie_match()

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

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

Parameters

[out]	found	the matching element, or NULL if no element matched.
[in]	ft	to search in.
[in]	data	to find.

Returns

• 0 always, tries never run a comparator. Check found for the result.

Definition at line 2674 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 1289 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()

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

Remove an entry, without freeing the data.

Parameters

[out]	removed	the data we removed, if any. May be NULL.
[in]	ft	to remove data from.
[in]	data	to remove.

Returns

• 0 if we removed data, removed is populated.
• 1 if we couldn't find any matching data.

Definition at line 2781 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 2157 of file trie.c.

Here is the call graph for this function:

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

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

Here is the call graph for this function:

Here is the caller graph for this function: