1*ef8d499eSDavid van Moolenbroek #ifndef MINIX_NET_LWIP_RTTREE_H 2*ef8d499eSDavid van Moolenbroek #define MINIX_NET_LWIP_RTTREE_H 3*ef8d499eSDavid van Moolenbroek 4*ef8d499eSDavid van Moolenbroek /* Routing table node structure. */ 5*ef8d499eSDavid van Moolenbroek struct rttree_node { 6*ef8d499eSDavid van Moolenbroek struct rttree_node *rtn_child[2]; /* left child node */ 7*ef8d499eSDavid van Moolenbroek struct rttree_node *rtn_parent; /* parent node */ 8*ef8d499eSDavid van Moolenbroek uint8_t rtn_type; /* node type (RNT_) */ 9*ef8d499eSDavid van Moolenbroek uint8_t rtn_bits; /* prefix bit count */ 10*ef8d499eSDavid van Moolenbroek uint8_t rtn_byte; /* bits-derived byte index */ 11*ef8d499eSDavid van Moolenbroek uint8_t rtn_shift; /* bits-derived shift count */ 12*ef8d499eSDavid van Moolenbroek }; 13*ef8d499eSDavid van Moolenbroek 14*ef8d499eSDavid van Moolenbroek #define RTNT_DATA 0 /* data node (entry) */ 15*ef8d499eSDavid van Moolenbroek #define RTNT_LINK 1 /* link node, in use */ 16*ef8d499eSDavid van Moolenbroek #define RTNT_FREE 2 /* link node, free */ 17*ef8d499eSDavid van Moolenbroek 18*ef8d499eSDavid van Moolenbroek /* Routing table entry structure. */ 19*ef8d499eSDavid van Moolenbroek struct rttree_entry { 20*ef8d499eSDavid van Moolenbroek struct rttree_node rte_data; /* data node - MUST be first */ 21*ef8d499eSDavid van Moolenbroek struct rttree_node rte_link; /* link node */ 22*ef8d499eSDavid van Moolenbroek const void *rte_addr; /* pointer to address */ 23*ef8d499eSDavid van Moolenbroek const void *rte_mask; /* pointer to mask */ 24*ef8d499eSDavid van Moolenbroek }; 25*ef8d499eSDavid van Moolenbroek 26*ef8d499eSDavid van Moolenbroek /* Routing table structure. */ 27*ef8d499eSDavid van Moolenbroek struct rttree { 28*ef8d499eSDavid van Moolenbroek struct rttree_node *rtt_root; /* root of the route tree */ 29*ef8d499eSDavid van Moolenbroek struct rttree_node *rtt_free; /* free internal nodes list */ 30*ef8d499eSDavid van Moolenbroek uint8_t rtt_bits; /* number of bits in address */ 31*ef8d499eSDavid van Moolenbroek }; 32*ef8d499eSDavid van Moolenbroek 33*ef8d499eSDavid van Moolenbroek #define rttree_get_addr(entry) ((entry)->rte_addr) 34*ef8d499eSDavid van Moolenbroek #define rttree_get_mask(entry) ((entry)->rte_mask) 35*ef8d499eSDavid van Moolenbroek #define rttree_get_prefix(entry) ((entry)->rte_data.rtn_bits) 36*ef8d499eSDavid van Moolenbroek 37*ef8d499eSDavid van Moolenbroek void rttree_init(struct rttree * tree, unsigned int bits); 38*ef8d499eSDavid van Moolenbroek struct rttree_entry *rttree_lookup_match(struct rttree * tree, 39*ef8d499eSDavid van Moolenbroek const void * addr); 40*ef8d499eSDavid van Moolenbroek struct rttree_entry *rttree_lookup_host(struct rttree * tree, 41*ef8d499eSDavid van Moolenbroek const void * addr); 42*ef8d499eSDavid van Moolenbroek struct rttree_entry *rttree_lookup_exact(struct rttree * tree, 43*ef8d499eSDavid van Moolenbroek const void * addr, unsigned int prefix); 44*ef8d499eSDavid van Moolenbroek struct rttree_entry *rttree_enum(struct rttree * tree, 45*ef8d499eSDavid van Moolenbroek struct rttree_entry * entry); 46*ef8d499eSDavid van Moolenbroek int rttree_add(struct rttree * tree, struct rttree_entry * entry, 47*ef8d499eSDavid van Moolenbroek const void * addr, const void * mask, unsigned int prefix); 48*ef8d499eSDavid van Moolenbroek void rttree_delete(struct rttree * tree, struct rttree_entry * entry); 49*ef8d499eSDavid van Moolenbroek 50*ef8d499eSDavid van Moolenbroek #endif /* !MINIX_NET_LWIP_RTTREE_H */ 51