1 /* 2 * $Id: patricia.h,v 1.1.1.1 2003/11/23 21:27:48 lexa Exp $ 3 * Dave Plonka <plonka@doit.wisc.edu> 4 * 5 * This product includes software developed by the University of Michigan, 6 * Merit Network, Inc., and their contributors. 7 * 8 * This file had been called "radix.h" in the MRT sources. 9 * 10 * I renamed it to "patricia.h" since it's not an implementation of a general 11 * radix trie. Also, pulled in various requirements from "mrt.h" and added 12 * some other things it could be used as a standalone API. 13 */ 14 15 #ifndef _PATRICIA_H 16 #define _PATRICIA_H 17 #define HAVE_IPV6 18 /* typedef unsigned int u_int; */ 19 typedef void (*void_fn_t)(); 20 /* { from defs.h */ 21 #define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) 22 #define MAXLINE 1024 23 #define BIT_TEST(f, b) ((f) & (b)) 24 /* } */ 25 26 #define addroute make_and_lookup 27 28 #include <netinet/in.h> /* for struct in_addr */ 29 30 #include <sys/socket.h> /* for AF_INET */ 31 32 /* { from mrt.h */ 33 34 typedef struct _prefix4_t { 35 u_short family; /* AF_INET | AF_INET6 */ 36 u_short bitlen; /* same as mask? */ 37 int ref_count; /* reference count */ 38 struct in_addr sin; 39 } prefix4_t; 40 41 typedef struct _prefix6_t { 42 u_short family; /* AF_INET | AF_INET6 */ 43 u_short bitlen; /* same as mask? */ 44 int ref_count; /* reference count */ 45 struct in6_addr sin6; 46 } prefix6_t; 47 48 typedef struct _prefix_t { 49 u_short family; /* AF_INET | AF_INET6 */ 50 u_short bitlen; /* same as mask? */ 51 int ref_count; /* reference count */ 52 union { 53 struct in_addr sin; 54 #ifdef HAVE_IPV6 55 struct in6_addr sin6; 56 #endif /* IPV6 */ 57 } add; 58 } prefix_t; 59 60 /* } */ 61 62 typedef struct _patricia_node_t { 63 u_int bit; /* flag if this node used */ 64 prefix_t *prefix; /* who we are in patricia tree */ 65 struct _patricia_node_t *l, *r; /* left and right children */ 66 struct _patricia_node_t *parent;/* may be used */ 67 void *data; /* pointer to data */ 68 void *user1; /* pointer to usr data (ex. route flap info) */ 69 void *user2; /* pointer to usr data (ex. route flap info) */ 70 } patricia_node_t; 71 72 typedef struct _patricia_tree_t { 73 patricia_node_t *head; 74 u_int maxbits; /* for IP, 32 bit addresses */ 75 int num_active_node; /* for debug purpose */ 76 } patricia_tree_t; 77 78 79 patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix); 80 patricia_node_t *patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix); 81 patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, 82 int inclusive); 83 patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix); 84 void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node); 85 patricia_tree_t *New_Patricia (int maxbits); 86 void Clear_Patricia (patricia_tree_t *patricia, void_fn_t func); 87 void Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func); 88 void patricia_process (patricia_tree_t *patricia, void_fn_t func); 89 90 /* { from demo.c */ 91 92 prefix_t * 93 ascii2prefix (int family, char *string); 94 95 patricia_node_t * 96 make_and_lookup (patricia_tree_t *tree, char *string); 97 98 /* } */ 99 100 #define PATRICIA_MAXBITS 128 101 #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f)) 102 #define PATRICIA_NBYTE(x) ((x) >> 3) 103 104 #define PATRICIA_DATA_GET(node, type) (type *)((node)->data) 105 #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value)) 106 107 #define PATRICIA_WALK(Xhead, Xnode) \ 108 do { \ 109 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ 110 patricia_node_t **Xsp = Xstack; \ 111 patricia_node_t *Xrn = (Xhead); \ 112 while ((Xnode = Xrn)) { \ 113 if (Xnode->prefix) 114 115 #define PATRICIA_WALK_ALL(Xhead, Xnode) \ 116 do { \ 117 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ 118 patricia_node_t **Xsp = Xstack; \ 119 patricia_node_t *Xrn = (Xhead); \ 120 while ((Xnode = Xrn)) { \ 121 if (1) 122 123 #define PATRICIA_WALK_BREAK { \ 124 if (Xsp != Xstack) { \ 125 Xrn = *(--Xsp); \ 126 } else { \ 127 Xrn = (patricia_node_t *) 0; \ 128 } \ 129 continue; } 130 131 #define PATRICIA_WALK_END \ 132 if (Xrn->l) { \ 133 if (Xrn->r) { \ 134 *Xsp++ = Xrn->r; \ 135 } \ 136 Xrn = Xrn->l; \ 137 } else if (Xrn->r) { \ 138 Xrn = Xrn->r; \ 139 } else if (Xsp != Xstack) { \ 140 Xrn = *(--Xsp); \ 141 } else { \ 142 Xrn = (patricia_node_t *) 0; \ 143 } \ 144 } \ 145 } while (0) 146 147 #endif /* _PATRICIA_H */ 148