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)
	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...
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 (fr_trie_t *ft)
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...
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 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_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

(

fr_trie_t *

ft

)

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_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: