#ifndef MINIX_NET_LWIP_RTTREE_H

#define MINIX_NET_LWIP_RTTREE_H

/* Routing table node structure. */

struct rttree_node {

struct rttree_node *rtn_child[2]; /* left child node */

struct rttree_node *rtn_parent; /* parent node */

uint8_t rtn_type; /* node type (RNT_) */

uint8_t rtn_bits; /* prefix bit count */

uint8_t rtn_byte; /* bits-derived byte index */

uint8_t rtn_shift; /* bits-derived shift count */

};

#define RTNT_DATA 0 /* data node (entry) */

#define RTNT_LINK 1 /* link node, in use */

#define RTNT_FREE 2 /* link node, free */

/* Routing table entry structure. */

struct rttree_entry {

struct rttree_node rte_data; /* data node - MUST be first */

struct rttree_node rte_link; /* link node */

const void *rte_addr; /* pointer to address */

const void *rte_mask; /* pointer to mask */

};

/* Routing table structure. */

struct rttree {

struct rttree_node *rtt_root; /* root of the route tree */

struct rttree_node *rtt_free; /* free internal nodes list */

uint8_t rtt_bits; /* number of bits in address */

};

#define rttree_get_addr(entry) ((entry)->rte_addr)

#define rttree_get_mask(entry) ((entry)->rte_mask)

#define rttree_get_prefix(entry) ((entry)->rte_data.rtn_bits)

void rttree_init(struct rttree * tree, unsigned int bits);

struct rttree_entry *rttree_lookup_match(struct rttree * tree,

const void * addr);

struct rttree_entry *rttree_lookup_host(struct rttree * tree,

const void * addr);

struct rttree_entry *rttree_lookup_exact(struct rttree * tree,

const void * addr, unsigned int prefix);

struct rttree_entry *rttree_enum(struct rttree * tree,

struct rttree_entry * entry);

int rttree_add(struct rttree * tree, struct rttree_entry * entry,

const void * addr, const void * mask, unsigned int prefix);

void rttree_delete(struct rttree * tree, struct rttree_entry * entry);

#endif /* !MINIX_NET_LWIP_RTTREE_H */