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