1 /* $NetBSD: radix.h,v 1.10 2015/07/08 17:28:59 christos Exp $ */ 2 3 /* 4 * Copyright (C) 2007, 2008, 2013, 2014 Internet Systems Consortium, Inc. ("ISC") 5 * 6 * Permission to use, copy, modify, and/or distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 11 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 12 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 13 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 14 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 15 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 16 * PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 /* Id: radix.h,v 1.13 2008/12/01 23:47:45 tbox Exp */ 20 21 /* 22 * This source was adapted from MRT's RCS Ids: 23 * Id: radix.h,v 1.6 1999/08/03 03:32:53 masaki Exp 24 * Id: mrt.h,v 1.57.2.6 1999/12/28 23:41:27 labovit Exp 25 * Id: defs.h,v 1.5.2.2 2000/01/15 14:19:16 masaki Exp 26 */ 27 28 #include <isc/magic.h> 29 #include <isc/types.h> 30 #include <isc/mutex.h> 31 #include <isc/net.h> 32 #include <isc/refcount.h> 33 34 #include <string.h> 35 36 #ifndef _RADIX_H 37 #define _RADIX_H 38 39 #define NETADDR_TO_PREFIX_T(na,pt,bits) \ 40 do { \ 41 const void *p = na; \ 42 memset(&(pt), 0, sizeof(pt)); \ 43 if (p != NULL) { \ 44 (pt).family = (na)->family; \ 45 (pt).bitlen = (bits); \ 46 if ((pt).family == AF_INET6) { \ 47 memmove(&(pt).add.sin6, &(na)->type.in6, \ 48 ((bits)+7)/8); \ 49 } else \ 50 memmove(&(pt).add.sin, &(na)->type.in, \ 51 ((bits)+7)/8); \ 52 } else { \ 53 (pt).family = AF_UNSPEC; \ 54 (pt).bitlen = 0; \ 55 } \ 56 isc_refcount_init(&(pt).refcount, 0); \ 57 } while(/*CONSTCOND*/0) 58 59 typedef struct isc_prefix { 60 isc_mem_t *mctx; 61 unsigned int family; /* AF_INET | AF_INET6, or AF_UNSPEC for "any" */ 62 unsigned int bitlen; /* 0 for "any" */ 63 isc_refcount_t refcount; 64 union { 65 struct in_addr sin; 66 struct in6_addr sin6; 67 } add; 68 } isc_prefix_t; 69 70 typedef void (*isc_radix_destroyfunc_t)(void *); 71 typedef void (*isc_radix_processfunc_t)(isc_prefix_t *, void **); 72 73 #define isc_prefix_tochar(prefix) ((char *)&(prefix)->add.sin) 74 #define isc_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) 75 76 #define BIT_TEST(f, b) ((f) & (b)) 77 78 /* 79 * We need "first match" when we search the radix tree to preserve 80 * compatibility with the existing ACL implementation. Radix trees 81 * naturally lend themselves to "best match". In order to get "first match" 82 * behavior, we keep track of the order in which entries are added to the 83 * tree--and when a search is made, we find all matching entries, and 84 * return the one that was added first. 85 * 86 * An IPv4 prefix and an IPv6 prefix may share a radix tree node if they 87 * have the same length and bit pattern (e.g., 127/8 and 7f::/8). To 88 * disambiguate between them, node_num and data are two-element arrays; 89 * node_num[0] and data[0] are used for IPv4 addresses, node_num[1] 90 * and data[1] for IPv6 addresses. The only exception is a prefix of 91 * 0/0 (aka "any" or "none"), which is always stored as IPv4 but matches 92 * IPv6 addresses too. 93 */ 94 95 #define ISC_IS6(family) ((family) == AF_INET6 ? 1 : 0) 96 typedef struct isc_radix_node { 97 isc_mem_t *mctx; 98 isc_uint32_t bit; /* bit length of the prefix */ 99 isc_prefix_t *prefix; /* who we are in radix tree */ 100 struct isc_radix_node *l, *r; /* left and right children */ 101 struct isc_radix_node *parent; /* may be used */ 102 void *data[2]; /* pointers to IPv4 and IPV6 data */ 103 int node_num[2]; /* which node this was in the tree, 104 or -1 for glue nodes */ 105 } isc_radix_node_t; 106 107 #define RADIX_TREE_MAGIC ISC_MAGIC('R','d','x','T'); 108 #define RADIX_TREE_VALID(a) ISC_MAGIC_VALID(a, RADIX_TREE_MAGIC); 109 110 typedef struct isc_radix_tree { 111 unsigned int magic; 112 isc_mem_t *mctx; 113 isc_radix_node_t *head; 114 isc_uint32_t maxbits; /* for IP, 32 bit addresses */ 115 int num_active_node; /* for debugging purposes */ 116 int num_added_node; /* total number of nodes */ 117 } isc_radix_tree_t; 118 119 isc_result_t 120 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, 121 isc_prefix_t *prefix); 122 /*%< 123 * Search 'radix' for the best match to 'prefix'. 124 * Return the node found in '*target'. 125 * 126 * Requires: 127 * \li 'radix' to be valid. 128 * \li 'target' is not NULL and "*target" is NULL. 129 * \li 'prefix' to be valid. 130 * 131 * Returns: 132 * \li ISC_R_NOTFOUND 133 * \li ISC_R_SUCCESS 134 */ 135 136 isc_result_t 137 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, 138 isc_radix_node_t *source, isc_prefix_t *prefix); 139 /*%< 140 * Insert 'source' or 'prefix' into the radix tree 'radix'. 141 * Return the node added in 'target'. 142 * 143 * Requires: 144 * \li 'radix' to be valid. 145 * \li 'target' is not NULL and "*target" is NULL. 146 * \li 'prefix' to be valid or 'source' to be non NULL and contain 147 * a valid prefix. 148 * 149 * Returns: 150 * \li ISC_R_NOMEMORY 151 * \li ISC_R_SUCCESS 152 */ 153 154 void 155 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node); 156 /*%< 157 * Remove the node 'node' from the radix tree 'radix'. 158 * 159 * Requires: 160 * \li 'radix' to be valid. 161 * \li 'node' to be valid. 162 */ 163 164 isc_result_t 165 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits); 166 /*%< 167 * Create a radix tree with a maximum depth of 'maxbits'; 168 * 169 * Requires: 170 * \li 'mctx' to be valid. 171 * \li 'target' to be non NULL and '*target' to be NULL. 172 * \li 'maxbits' to be less than or equal to RADIX_MAXBITS. 173 * 174 * Returns: 175 * \li ISC_R_NOMEMORY 176 * \li ISC_R_SUCCESS 177 */ 178 179 void 180 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func); 181 /*%< 182 * Destroy a radix tree optionally calling 'func' to clean up node data. 183 * 184 * Requires: 185 * \li 'radix' to be valid. 186 */ 187 188 void 189 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func); 190 /*%< 191 * Walk a radix tree calling 'func' to process node data. 192 * 193 * Requires: 194 * \li 'radix' to be valid. 195 * \li 'func' to point to a function. 196 */ 197 198 #define RADIX_MAXBITS 128 199 #define RADIX_NBIT(x) (0x80 >> ((x) & 0x7f)) 200 #define RADIX_NBYTE(x) ((x) >> 3) 201 202 #define RADIX_DATA_GET(node, type) (type *)((node)->data) 203 #define RADIX_DATA_SET(node, value) ((node)->data = (void *)(value)) 204 205 #define RADIX_WALK(Xhead, Xnode) \ 206 do { \ 207 isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; \ 208 isc_radix_node_t **Xsp = Xstack; \ 209 isc_radix_node_t *Xrn = (Xhead); \ 210 while ((Xnode = Xrn)) { \ 211 if (Xnode->prefix) 212 213 #define RADIX_WALK_ALL(Xhead, Xnode) \ 214 do { \ 215 isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; \ 216 isc_radix_node_t **Xsp = Xstack; \ 217 isc_radix_node_t *Xrn = (Xhead); \ 218 while ((Xnode = Xrn)) { \ 219 if (1) 220 221 #define RADIX_WALK_BREAK { \ 222 if (Xsp != Xstack) { \ 223 Xrn = *(--Xsp); \ 224 } else { \ 225 Xrn = (radix_node_t *) 0; \ 226 } \ 227 continue; } 228 229 #define RADIX_WALK_END \ 230 if (Xrn->l) { \ 231 if (Xrn->r) { \ 232 *Xsp++ = Xrn->r; \ 233 } \ 234 Xrn = Xrn->l; \ 235 } else if (Xrn->r) { \ 236 Xrn = Xrn->r; \ 237 } else if (Xsp != Xstack) { \ 238 Xrn = *(--Xsp); \ 239 } else { \ 240 Xrn = (isc_radix_node_t *) 0; \ 241 } \ 242 } \ 243 } while (/*CONSTCOND*/0) 244 245 #endif /* _RADIX_H */ 246