trie_private.h File Reference

#include "rtrlib/lib/ip_private.h"
#include "rtrlib/lib/log_private.h"
#include <inttypes.h>

Go to the source code of this file.

Data Structures
struct	trie_node
	trie_node More...

Macros
#define	PFX_DBG1(a)   lrtr_dbg("PFX: " a)

Functions
void	trie_insert (struct trie_node *root, struct trie_node *new_node, const unsigned int level)
	Inserts new_node in the tree.
struct trie_node *	trie_lookup (const struct trie_node *root_node, const struct lrtr_ip_addr *prefix, const uint8_t mask_len, unsigned int *level)
	Searches for a matching node matching the passed ip prefix and prefix length.
struct trie_node *	trie_lookup_exact (struct trie_node *root_node, const struct lrtr_ip_addr *prefix, const uint8_t mask_len, unsigned int *level, bool *found)
	Search for a node with the same prefix and prefix length.
struct trie_node *	trie_remove (struct trie_node *root_node, const struct lrtr_ip_addr *prefix, const uint8_t mask_len, const unsigned int level)
	Removes the node with the passed IP prefix and mask_len from the tree.
bool	trie_is_leaf (const struct trie_node *node)
	Detects if a node is a leaf in the tree.
int	trie_get_children (const struct trie_node *root_node, struct trie_node ***array, unsigned int *len)

Macro Definition Documentation

PFX_DBG1

#define PFX_DBG1

(

a

)

lrtr_dbg("PFX: " a)

Function Documentation

trie_get_children()

int trie_get_children	(	const struct trie_node *	root_node,
		struct trie_node ***	array,
		unsigned int *	len
	)

trie_insert()

void trie_insert	(	struct trie_node *	root,
		struct trie_node *	new_node,
		const unsigned int	level
	)

Inserts new_node in the tree.

Parameters

[in]	root	Root node of the tree for the inserting process.
[in]	new_node	Node that will be inserted.
[in]	level	Level of the the root node in the tree.

trie_is_leaf()

bool trie_is_leaf

(

const struct trie_node *

node

)

Detects if a node is a leaf in the tree.

Parameters

[in]

node

Returns

true if node is a leaf.

false if node isn't a leaf.

trie_lookup()

struct trie_node * trie_lookup	(	const struct trie_node *	root_node,
		const struct lrtr_ip_addr *	prefix,
		const uint8_t	mask_len,
		unsigned int *	level
	)

Searches for a matching node matching the passed ip prefix and prefix length.

If multiple matching nodes exist, the one with the shortest prefix is returned.

Parameters

[in]	root_node	Node were the lookup process starts.
[in]	lrtr_ip_addr	IP-Prefix.
[in]	mask_len	Length of the network mask of the prefix.
[in,out]	level	of the the node root in the tree. Is set to the level of the node that is returned.

Returns

The trie_node with the short prefix in the tree matching the passed ip prefix and prefix length.

NULL if no node that matches the passed prefix and prefix length could be found.

trie_lookup_exact()

struct trie_node * trie_lookup_exact	(	struct trie_node *	root_node,
		const struct lrtr_ip_addr *	prefix,
		const uint8_t	mask_len,
		unsigned int *	level,
		bool *	found
	)

Search for a node with the same prefix and prefix length.

Parameters

[in]	root_node	Node were the lookup process starts.
[in]	lrtr_ip_addr	IP-Prefix.
[in]	mask_len	Length of the network mask of the prefix.
[in,out]	level	of the the node root in the tree. Is set to the level of the node that is returned.
[in]	found	Is true if a node which matches could be found else found is set to false.

Returns

A node which matches the passed parameter (found==true).

The parent of the node where the lookup operation stopped (found==false).

NULL if root_node is NULL.

trie_remove()

struct trie_node * trie_remove	(	struct trie_node *	root_node,
		const struct lrtr_ip_addr *	prefix,
		const uint8_t	mask_len,
		const unsigned int	level
	)

Removes the node with the passed IP prefix and mask_len from the tree.

Parameters

[in]	root	Node were the inserting process starts.
[in]	prefix	Prefix that will removed from the tree.
[in]	mask_len	Length of the network mask of the prefix.
[in]	level	Level of the root node in the tree.

Returns

Node that was removed from the tree. The caller has to free it.

NULL If the Prefix couldn't be found in the tree.