trie.h

/*
 * 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
#define RTR_trie
#include <inttypes.h>
#include "rtrlib/lib/ip.h"

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;
};

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

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);

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);

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);

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