From cd7b005519ade8ab6c97fcb21590b71b7d1be6e3 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:54:46 +0200 Subject: Adding upstream version 0.8.0. Signed-off-by: Daniel Baumann --- rtrlib/pfx/trie/trie_private.h | 98 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 98 insertions(+) create mode 100644 rtrlib/pfx/trie/trie_private.h (limited to 'rtrlib/pfx/trie/trie_private.h') diff --git a/rtrlib/pfx/trie/trie_private.h b/rtrlib/pfx/trie/trie_private.h new file mode 100644 index 0000000..8003ced --- /dev/null +++ b/rtrlib/pfx/trie/trie_private.h @@ -0,0 +1,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 + +/** + * @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 -- cgit v1.2.3