contrib/bind9/lib/isc/include/isc/radix.h

   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
  56 typedef 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
  67 typedef void (*isc_radix_destroyfunc_t)(void *);
  68 typedef 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)
  93 typedef 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
 107 typedef 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
 116 isc_result_t
 117 isc_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
 133 isc_result_t
 134 isc_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
 151 void
 152 isc_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
 161 isc_result_t
 162 isc_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
 176 void
 177 isc_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
 185 void
 186 isc_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) \
 211 do { \
 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 */