1 /* 2 * Imported: Id: patricia.h 18598 2005-03-04 17:45:53Z androsyn 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_C 16 #define EXTERN extern 17 #else /* PATRICIA_C */ 18 #define EXTERN 19 #endif /* PATRICIA_C */ 20 21 #ifndef _PATRICIA_H 22 #define _PATRICIA_H 23 24 #include <stdlib.h> 25 #include <string.h> 26 #include <sys/types.h> 27 #include <netinet/in.h> 28 #include <arpa/inet.h> 29 #include <assert.h> 30 31 #ifndef FALSE 32 #define FALSE 0 33 #endif 34 #ifndef TRUE 35 #define TRUE !(FALSE) 36 #endif 37 #ifndef INET6_ADDRSTRLEN 38 #define INET6_ADDRSTRLEN 46 39 #endif 40 41 /* typedef unsigned int u_int; */ 42 typedef void (*void_fn_t) (); 43 #define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) 44 #define MAXLINE 1024 45 #define BIT_TEST(f, b) ((f) & (b)) 46 47 #include <netinet/in.h> 48 #include <sys/socket.h> 49 50 typedef struct _prefix_t 51 { 52 u_short family; /* AF_INET | AF_INET6 */ 53 u_short bitlen; /* same as mask? */ 54 int ref_count; /* reference count */ 55 union 56 { 57 struct in_addr sin; 58 #ifdef INET6 59 struct in6_addr sin6; 60 #endif /* IPV6 */ 61 } 62 add; 63 } 64 prefix_t; 65 66 67 typedef struct _patricia_node_t 68 { 69 u_int bit; /* flag if this node used */ 70 prefix_t *prefix; /* who we are in patricia tree */ 71 struct _patricia_node_t *l, *r; /* left and right children */ 72 struct _patricia_node_t *parent; /* may be used */ 73 void *data; 74 } 75 patricia_node_t; 76 77 typedef struct _patricia_tree_t 78 { 79 patricia_node_t *head; 80 u_int maxbits; /* for IP, 32 bit addresses */ 81 int num_active_node; /* for debug purpose */ 82 } 83 patricia_tree_t; 84 85 86 EXTERN patricia_node_t *patricia_match_ip(patricia_tree_t *, struct IN_ADDR *); 87 patricia_node_t *patricia_match_string(patricia_tree_t *, const char *); 88 patricia_node_t *patricia_match_exact_string(patricia_tree_t *, const char *); 89 patricia_node_t *patricia_search_exact(patricia_tree_t *, prefix_t *); 90 patricia_node_t *patricia_search_best(patricia_tree_t *, prefix_t *); 91 patricia_node_t *patricia_search_best2(patricia_tree_t *, prefix_t *, int); 92 patricia_node_t *patricia_lookup(patricia_tree_t *, prefix_t *); 93 94 EXTERN void patricia_remove(patricia_tree_t *, patricia_node_t *); 95 EXTERN patricia_tree_t *patricia_new(int); 96 void patricia_clear(patricia_tree_t *, void_fn_t); 97 EXTERN void patricia_destroy(patricia_tree_t *, void_fn_t); 98 void patricia_process(patricia_tree_t *, void_fn_t); 99 void patricia_init(void); 100 101 102 #if 0 103 prefix_t *ascii2prefix(int family, char *string); 104 #endif 105 patricia_node_t *patricia_make_and_lookup(patricia_tree_t *, const char *); 106 EXTERN patricia_node_t *patricia_make_and_lookup_ip(patricia_tree_t *, struct IN_ADDR *, int); 107 108 109 #define PATRICIA_MAXBITS 128 110 #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f)) 111 #define PATRICIA_NBYTE(x) ((x) >> 3) 112 113 #define PATRICIA_DATA_GET(node, type) (type *)((node)->data) 114 #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value)) 115 116 #define PATRICIA_WALK(Xhead, Xnode) \ 117 do { \ 118 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ 119 patricia_node_t **Xsp = Xstack; \ 120 patricia_node_t *Xrn = (Xhead); \ 121 while ((Xnode = Xrn)) { \ 122 if (Xnode->prefix) 123 124 #define PATRICIA_WALK_ALL(Xhead, Xnode) \ 125 do { \ 126 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ 127 patricia_node_t **Xsp = Xstack; \ 128 patricia_node_t *Xrn = (Xhead); \ 129 while ((Xnode = Xrn)) { \ 130 if (1) 131 132 #define PATRICIA_WALK_BREAK { \ 133 if (Xsp != Xstack) { \ 134 Xrn = *(--Xsp); \ 135 } else { \ 136 Xrn = (patricia_node_t *) 0; \ 137 } \ 138 continue; } 139 140 #define PATRICIA_WALK_END \ 141 if (Xrn->l) { \ 142 if (Xrn->r) { \ 143 *Xsp++ = Xrn->r; \ 144 } \ 145 Xrn = Xrn->l; \ 146 } else if (Xrn->r) { \ 147 Xrn = Xrn->r; \ 148 } else if (Xsp != Xstack) { \ 149 Xrn = *(--Xsp); \ 150 } else { \ 151 Xrn = (patricia_node_t *) 0; \ 152 } \ 153 } \ 154 } while (0) 155 156 #endif /* _PATRICIA_H */ 157