1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
/*
* This file is part of RTRlib.
*
* This file is subject to the terms and conditions of the MIT license.
* See the file LICENSE in the top level directory for more details.
*
* Website: http://rtrlib.realmv6.org/
*/
#ifndef RTR_TRIE_PRIVATE
#define RTR_TRIE_PRIVATE
#include "rtrlib/lib/ip_private.h"
#include <inttypes.h>
/**
* @brief trie_node
* @param prefix
* @param rchild
* @param lchild
* @param parent
* @param data
* @param len number of elements in data array
*/
struct trie_node {
struct lrtr_ip_addr prefix;
struct trie_node *rchild;
struct trie_node *lchild;
struct trie_node *parent;
void *data;
uint8_t len;
};
/**
* @brief Inserts new_node in the tree.
* @param[in] root Root node of the tree for the inserting process.
* @param[in] new_node Node that will be inserted.
* @param[in] level Level of the the root node in the tree.
*/
void trie_insert(struct trie_node *root, struct trie_node *new_node, const unsigned int level);
/**
* @brief 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.
* @param[in] root_node Node were the lookup process starts.
* @param[in] lrtr_ip_addr IP-Prefix.
* @param[in] mask_len Length of the network mask of the prefix.
* @param[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.
* @returns NULL if no node that matches the passed prefix and prefix length
* could be found.
*/
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);
/**
* @brief Search for a node with the same prefix and prefix length.
* @param[in] root_node Node were the lookup process starts.
* @param[in] lrtr_ip_addr IP-Prefix.
* @param[in] mask_len Length of the network mask of the prefix.
* @param[in,out] level of the the node root in the tree. Is set to the level of
* the node that is returned.
* @param[in] found Is true if a node which matches could be found else found is
* set to false.
* @return A node which matches the passed parameter (found==true).
* @return The parent of the node where the lookup operation
* stopped (found==false).
* @return NULL if root_node is NULL.
*/
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);
/**
* @brief Removes the node with the passed IP prefix and mask_len from the tree.
* @param[in] root Node were the inserting process starts.
* @param[in] prefix Prefix that will removed from the tree.
* @param[in] mask_len Length of the network mask of the prefix.
* @param[in] level Level of the root node in the tree.
* @returns Node that was removed from the tree. The caller has to free it.
* @returns NULL If the Prefix couldn't be found in the tree.
*/
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);
/**
* @brief Detects if a node is a leaf in the tree.
* @param[in] node
* @returns true if node is a leaf.
* @returns false if node isn't a leaf.
*/
bool trie_is_leaf(const struct trie_node *node);
int trie_get_children(const struct trie_node *root_node, struct trie_node ***array, unsigned int *len);
#endif
|
