1 files changed, 98 insertions, 0 deletions
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 <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