/**

* @ingroup util_h[{

* Converts the passed IPv6 address first_bit network byte order to host byte order.

* @param[in] src Pointer to a uint32_t array storing a ipv6 address in network byte order.

* @param[out] dest Pointer a uint32_t array that will be used to store the ipv6 addr in host byte order.

* }

*/

void lrtr_ipv6_addr_to_host_byte_order(const uint32_t *src, uint32_t *dest);

/* @} */

/*

* 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/

*/

/**

* @defgroup mod_lpfst_pfx_h Longest prefix first search tree

* @ingroup mod_pfx_h

* @brief An implementation of a \ref mod_pfx_h "pfx_table" data structure

* using longest prefix first trees (lpfst) for storing @ref pfx_record "pfx_records".

* @details This implementation uses two separate lpfs-trees, one for IPv4

* validation records and one for IPv6 records.\n

* See \ref mod_pfx_h "pfx_table" for a list of supported operations of

* this data structure.\n

* For general details about the data structure see: <a

* href="http://dx.doi.org/10.1016/j.comnet.2007.01.023">Wuu et al. "A

* longest prefix first search tree for IP lookup", Computer Networks,

* 51(12), pp. 3354-3367, 2007</a>.

*

* @{

*/

/*

* 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/

*/

/**

* @brief lpfst_node

* @param prefix

* @param rchild

* @param lchild

* @param parent

* @param data

* @param len number of elements in data array

*/

struct lpfst_node {

struct lrtr_ip_addr prefix;

struct lpfst_node *rchild;

struct lpfst_node *lchild;

struct lpfst_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 lpfst_insert(struct lpfst_node *root, struct lpfst_node *new_node,

const unsigned int level);

/**

* @brief Searches for the node with the longest prefix, matching the passed ip

* 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.

* @returns The lpfst_node with the longest 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 lpfst_node *lpfst_lookup(const struct lpfst_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 lpfst_node *lpfst_lookup_exact(struct lpfst_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 could'nt be found in the tree.

*/

struct lpfst_node *lpfst_remove(struct lpfst_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 lpfst_is_leaf(const struct lpfst_node *node);

int lpfst_get_children(const struct lpfst_node *root_node,

struct lpfst_node ***array, unsigned int *len);

struct lpfst_node *ipv4;

struct lpfst_node *ipv6;

pfx_update_fp update_fp;

/* @} */

/*

* 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/

*/