1193141Sdougb/* 2262706Serwin * Copyright (C) 2007, 2008, 2013, 2014 Internet Systems Consortium, Inc. ("ISC") 3193141Sdougb * 4193141Sdougb * Permission to use, copy, modify, and/or distribute this software for any 5193141Sdougb * purpose with or without fee is hereby granted, provided that the above 6193141Sdougb * copyright notice and this permission notice appear in all copies. 7193141Sdougb * 8193141Sdougb * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9193141Sdougb * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10193141Sdougb * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11193141Sdougb * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12193141Sdougb * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13193141Sdougb * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14193141Sdougb * PERFORMANCE OF THIS SOFTWARE. 15193141Sdougb */ 16193141Sdougb 17234010Sdougb/* $Id: radix.h,v 1.13 2008/12/01 23:47:45 tbox Exp $ */ 18193141Sdougb 19193141Sdougb/* 20193141Sdougb * This source was adapted from MRT's RCS Ids: 21193141Sdougb * Id: radix.h,v 1.6 1999/08/03 03:32:53 masaki Exp 22193141Sdougb * Id: mrt.h,v 1.57.2.6 1999/12/28 23:41:27 labovit Exp 23193141Sdougb * Id: defs.h,v 1.5.2.2 2000/01/15 14:19:16 masaki Exp 24193141Sdougb */ 25193141Sdougb 26193141Sdougb#include <isc/magic.h> 27193141Sdougb#include <isc/types.h> 28193141Sdougb#include <isc/mutex.h> 29193141Sdougb#include <isc/net.h> 30193141Sdougb#include <isc/refcount.h> 31193141Sdougb 32193141Sdougb#include <string.h> 33193141Sdougb 34193141Sdougb#ifndef _RADIX_H 35193141Sdougb#define _RADIX_H 36193141Sdougb 37193141Sdougb#define NETADDR_TO_PREFIX_T(na,pt,bits) \ 38193141Sdougb do { \ 39193141Sdougb memset(&(pt), 0, sizeof(pt)); \ 40193141Sdougb if((na) != NULL) { \ 41193141Sdougb (pt).family = (na)->family; \ 42193141Sdougb (pt).bitlen = (bits); \ 43193141Sdougb if ((pt).family == AF_INET6) { \ 44262706Serwin memmove(&(pt).add.sin6, &(na)->type.in6, \ 45193141Sdougb ((bits)+7)/8); \ 46193141Sdougb } else \ 47262706Serwin memmove(&(pt).add.sin, &(na)->type.in, \ 48193141Sdougb ((bits)+7)/8); \ 49193141Sdougb } else { \ 50193141Sdougb (pt).family = AF_UNSPEC; \ 51193141Sdougb (pt).bitlen = 0; \ 52193141Sdougb } \ 53193141Sdougb isc_refcount_init(&(pt).refcount, 0); \ 54193141Sdougb } while(0) 55193141Sdougb 56193141Sdougbtypedef struct isc_prefix { 57254897Serwin isc_mem_t *mctx; 58254897Serwin unsigned int family; /* AF_INET | AF_INET6, or AF_UNSPEC for "any" */ 59254897Serwin unsigned int bitlen; /* 0 for "any" */ 60254897Serwin isc_refcount_t refcount; 61254897Serwin union { 62193141Sdougb struct in_addr sin; 63193141Sdougb struct in6_addr sin6; 64254897Serwin } add; 65193141Sdougb} isc_prefix_t; 66193141Sdougb 67193141Sdougbtypedef void (*isc_radix_destroyfunc_t)(void *); 68193141Sdougbtypedef void (*isc_radix_processfunc_t)(isc_prefix_t *, void **); 69193141Sdougb 70193141Sdougb#define isc_prefix_tochar(prefix) ((char *)&(prefix)->add.sin) 71193141Sdougb#define isc_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) 72193141Sdougb 73193141Sdougb#define BIT_TEST(f, b) ((f) & (b)) 74193141Sdougb 75193141Sdougb/* 76193141Sdougb * We need "first match" when we search the radix tree to preserve 77193141Sdougb * compatibility with the existing ACL implementation. Radix trees 78193141Sdougb * naturally lend themselves to "best match". In order to get "first match" 79193141Sdougb * behavior, we keep track of the order in which entries are added to the 80193141Sdougb * tree--and when a search is made, we find all matching entries, and 81193141Sdougb * return the one that was added first. 82193141Sdougb * 83193141Sdougb * An IPv4 prefix and an IPv6 prefix may share a radix tree node if they 84193141Sdougb * have the same length and bit pattern (e.g., 127/8 and 7f::/8). To 85193141Sdougb * disambiguate between them, node_num and data are two-element arrays; 86193141Sdougb * node_num[0] and data[0] are used for IPv4 addresses, node_num[1] 87193141Sdougb * and data[1] for IPv6 addresses. The only exception is a prefix of 88193141Sdougb * 0/0 (aka "any" or "none"), which is always stored as IPv4 but matches 89193141Sdougb * IPv6 addresses too. 90193141Sdougb */ 91193141Sdougb 92193141Sdougb#define ISC_IS6(family) ((family) == AF_INET6 ? 1 : 0) 93193141Sdougbtypedef struct isc_radix_node { 94254897Serwin isc_mem_t *mctx; 95254897Serwin isc_uint32_t bit; /* bit length of the prefix */ 96254897Serwin isc_prefix_t *prefix; /* who we are in radix tree */ 97254897Serwin struct isc_radix_node *l, *r; /* left and right children */ 98254897Serwin struct isc_radix_node *parent; /* may be used */ 99254897Serwin void *data[2]; /* pointers to IPv4 and IPV6 data */ 100254897Serwin int node_num[2]; /* which node this was in the tree, 101193141Sdougb or -1 for glue nodes */ 102193141Sdougb} isc_radix_node_t; 103193141Sdougb 104193141Sdougb#define RADIX_TREE_MAGIC ISC_MAGIC('R','d','x','T'); 105193141Sdougb#define RADIX_TREE_VALID(a) ISC_MAGIC_VALID(a, RADIX_TREE_MAGIC); 106193141Sdougb 107193141Sdougbtypedef struct isc_radix_tree { 108254897Serwin unsigned int magic; 109254897Serwin isc_mem_t *mctx; 110254897Serwin isc_radix_node_t *head; 111254897Serwin isc_uint32_t maxbits; /* for IP, 32 bit addresses */ 112254897Serwin int num_active_node; /* for debugging purposes */ 113254897Serwin int num_added_node; /* total number of nodes */ 114193141Sdougb} isc_radix_tree_t; 115193141Sdougb 116193141Sdougbisc_result_t 117193141Sdougbisc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, 118193141Sdougb isc_prefix_t *prefix); 119193141Sdougb/*%< 120193141Sdougb * Search 'radix' for the best match to 'prefix'. 121193141Sdougb * Return the node found in '*target'. 122193141Sdougb * 123193141Sdougb * Requires: 124193141Sdougb * \li 'radix' to be valid. 125193141Sdougb * \li 'target' is not NULL and "*target" is NULL. 126193141Sdougb * \li 'prefix' to be valid. 127193141Sdougb * 128193141Sdougb * Returns: 129193141Sdougb * \li ISC_R_NOTFOUND 130193141Sdougb * \li ISC_R_SUCCESS 131193141Sdougb */ 132193141Sdougb 133193141Sdougbisc_result_t 134193141Sdougbisc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, 135193141Sdougb isc_radix_node_t *source, isc_prefix_t *prefix); 136193141Sdougb/*%< 137193141Sdougb * Insert 'source' or 'prefix' into the radix tree 'radix'. 138193141Sdougb * Return the node added in 'target'. 139193141Sdougb * 140193141Sdougb * Requires: 141193141Sdougb * \li 'radix' to be valid. 142193141Sdougb * \li 'target' is not NULL and "*target" is NULL. 143193141Sdougb * \li 'prefix' to be valid or 'source' to be non NULL and contain 144193141Sdougb * a valid prefix. 145193141Sdougb * 146193141Sdougb * Returns: 147193141Sdougb * \li ISC_R_NOMEMORY 148193141Sdougb * \li ISC_R_SUCCESS 149193141Sdougb */ 150193141Sdougb 151193141Sdougbvoid 152193141Sdougbisc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node); 153193141Sdougb/*%< 154193141Sdougb * Remove the node 'node' from the radix tree 'radix'. 155193141Sdougb * 156193141Sdougb * Requires: 157193141Sdougb * \li 'radix' to be valid. 158193141Sdougb * \li 'node' to be valid. 159193141Sdougb */ 160193141Sdougb 161193141Sdougbisc_result_t 162193141Sdougbisc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits); 163193141Sdougb/*%< 164193141Sdougb * Create a radix tree with a maximum depth of 'maxbits'; 165193141Sdougb * 166193141Sdougb * Requires: 167193141Sdougb * \li 'mctx' to be valid. 168193141Sdougb * \li 'target' to be non NULL and '*target' to be NULL. 169193141Sdougb * \li 'maxbits' to be less than or equal to RADIX_MAXBITS. 170193141Sdougb * 171193141Sdougb * Returns: 172193141Sdougb * \li ISC_R_NOMEMORY 173193141Sdougb * \li ISC_R_SUCCESS 174193141Sdougb */ 175193141Sdougb 176193141Sdougbvoid 177193141Sdougbisc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func); 178193141Sdougb/*%< 179193141Sdougb * Destroy a radix tree optionally calling 'func' to clean up node data. 180193141Sdougb * 181193141Sdougb * Requires: 182193141Sdougb * \li 'radix' to be valid. 183193141Sdougb */ 184193141Sdougb 185193141Sdougbvoid 186193141Sdougbisc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func); 187193141Sdougb/*%< 188193141Sdougb * Walk a radix tree calling 'func' to process node data. 189193141Sdougb * 190193141Sdougb * Requires: 191193141Sdougb * \li 'radix' to be valid. 192193141Sdougb * \li 'func' to point to a function. 193193141Sdougb */ 194193141Sdougb 195193141Sdougb#define RADIX_MAXBITS 128 196193141Sdougb#define RADIX_NBIT(x) (0x80 >> ((x) & 0x7f)) 197193141Sdougb#define RADIX_NBYTE(x) ((x) >> 3) 198193141Sdougb 199193141Sdougb#define RADIX_DATA_GET(node, type) (type *)((node)->data) 200193141Sdougb#define RADIX_DATA_SET(node, value) ((node)->data = (void *)(value)) 201193141Sdougb 202193141Sdougb#define RADIX_WALK(Xhead, Xnode) \ 203193141Sdougb do { \ 204193141Sdougb isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; \ 205193141Sdougb isc_radix_node_t **Xsp = Xstack; \ 206193141Sdougb isc_radix_node_t *Xrn = (Xhead); \ 207193141Sdougb while ((Xnode = Xrn)) { \ 208193141Sdougb if (Xnode->prefix) 209193141Sdougb 210193141Sdougb#define RADIX_WALK_ALL(Xhead, Xnode) \ 211193141Sdougbdo { \ 212193141Sdougb isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; \ 213193141Sdougb isc_radix_node_t **Xsp = Xstack; \ 214193141Sdougb isc_radix_node_t *Xrn = (Xhead); \ 215193141Sdougb while ((Xnode = Xrn)) { \ 216193141Sdougb if (1) 217193141Sdougb 218193141Sdougb#define RADIX_WALK_BREAK { \ 219193141Sdougb if (Xsp != Xstack) { \ 220193141Sdougb Xrn = *(--Xsp); \ 221193141Sdougb } else { \ 222193141Sdougb Xrn = (radix_node_t *) 0; \ 223193141Sdougb } \ 224193141Sdougb continue; } 225193141Sdougb 226193141Sdougb#define RADIX_WALK_END \ 227193141Sdougb if (Xrn->l) { \ 228193141Sdougb if (Xrn->r) { \ 229193141Sdougb *Xsp++ = Xrn->r; \ 230193141Sdougb } \ 231193141Sdougb Xrn = Xrn->l; \ 232193141Sdougb } else if (Xrn->r) { \ 233193141Sdougb Xrn = Xrn->r; \ 234193141Sdougb } else if (Xsp != Xstack) { \ 235193141Sdougb Xrn = *(--Xsp); \ 236193141Sdougb } else { \ 237193141Sdougb Xrn = (isc_radix_node_t *) 0; \ 238193141Sdougb } \ 239193141Sdougb } \ 240193141Sdougb } while (0) 241193141Sdougb 242193141Sdougb#endif /* _RADIX_H */ 243