"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.16.7/lib/isc/include/isc/radix.h" (4 Sep 2020, 7030 Bytes) of package /linux/misc/dns/bind9/9.16.7/bind-9.16.7.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "radix.h" see the Fossies "Dox" file reference documentation.

    1 /*
    2  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
    3  *
    4  * This Source Code Form is subject to the terms of the Mozilla Public
    5  * License, v. 2.0. If a copy of the MPL was not distributed with this
    6  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
    7  *
    8  * See the COPYRIGHT file distributed with this work for additional
    9  * information regarding copyright ownership.
   10  */
   11 
   12 #ifndef _RADIX_H
   13 #define _RADIX_H
   14 
   15 #include <inttypes.h>
   16 #include <string.h>
   17 
   18 #include <isc/magic.h>
   19 #include <isc/mutex.h>
   20 #include <isc/net.h>
   21 #include <isc/refcount.h>
   22 #include <isc/types.h>
   23 
   24 #define NETADDR_TO_PREFIX_T(na, pt, bits)                                \
   25     do {                                                             \
   26         const void *p = na;                                      \
   27         memset(&(pt), 0, sizeof(pt));                            \
   28         if (p != NULL) {                                         \
   29             (pt).family = (na)->family;                      \
   30             (pt).bitlen = (bits);                            \
   31             if ((pt).family == AF_INET6) {                   \
   32                 memmove(&(pt).add.sin6, &(na)->type.in6, \
   33                     ((bits) + 7) / 8);               \
   34             } else                                           \
   35                 memmove(&(pt).add.sin, &(na)->type.in,   \
   36                     ((bits) + 7) / 8);               \
   37         } else {                                                 \
   38             (pt).family = AF_UNSPEC;                         \
   39             (pt).bitlen = 0;                                 \
   40         }                                                        \
   41         isc_refcount_init(&(pt).refcount, 0);                    \
   42     } while (0)
   43 
   44 typedef struct isc_prefix {
   45     isc_mem_t *  mctx;
   46     unsigned int family;   /* AF_INET | AF_INET6, or AF_UNSPEC for
   47                 * "any" */
   48     unsigned int   bitlen; /* 0 for "any" */
   49     isc_refcount_t refcount;
   50     union {
   51         struct in_addr  sin;
   52         struct in6_addr sin6;
   53     } add;
   54 } isc_prefix_t;
   55 
   56 typedef void (*isc_radix_destroyfunc_t)(void *);
   57 typedef void (*isc_radix_processfunc_t)(isc_prefix_t *, void **);
   58 
   59 #define isc_prefix_tochar(prefix)  ((char *)&(prefix)->add.sin)
   60 #define isc_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
   61 
   62 /*
   63  * We need "first match" when we search the radix tree to preserve
   64  * compatibility with the existing ACL implementation. Radix trees
   65  * naturally lend themselves to "best match". In order to get "first match"
   66  * behavior, we keep track of the order in which entries are added to the
   67  * tree--and when a search is made, we find all matching entries, and
   68  * return the one that was added first.
   69  *
   70  * An IPv4 prefix and an IPv6 prefix may share a radix tree node if they
   71  * have the same length and bit pattern (e.g., 127/8 and 7f::/8).  To
   72  * disambiguate between them, node_num and data are two-element arrays:
   73  *
   74  *   - node_num[0] and data[0] are used for IPv4 client addresses
   75  *   - node_num[1] and data[1] are used for IPv6 client addresses
   76  *
   77  * A prefix of 0/0 (aka "any" or "none"), is always stored as IPv4,
   78  * but matches all IPv6 addresses too.
   79  */
   80 
   81 #define RADIX_V4       0
   82 #define RADIX_V6       1
   83 #define RADIX_FAMILIES 2
   84 
   85 #define ISC_RADIX_FAMILY(p) (((p)->family == AF_INET6) ? RADIX_V6 : RADIX_V4)
   86 
   87 typedef struct isc_radix_node {
   88     isc_mem_t *        mctx;
   89     uint32_t           bit;    /* bit length of the prefix */
   90     isc_prefix_t *         prefix; /* who we are in radix tree */
   91     struct isc_radix_node *l, *r;  /* left and right children */
   92     struct isc_radix_node *parent; /* may be used */
   93     void *             data[RADIX_FAMILIES]; /* pointers to IPv4
   94                               * and IPV6 data */
   95     int node_num[RADIX_FAMILIES];            /* which node
   96                               * this was in
   97                               * the tree,
   98                               * or -1 for glue
   99                               * nodes */
  100 } isc_radix_node_t;
  101 
  102 #define RADIX_TREE_MAGIC    ISC_MAGIC('R', 'd', 'x', 'T');
  103 #define RADIX_TREE_VALID(a) ISC_MAGIC_VALID(a, RADIX_TREE_MAGIC);
  104 
  105 typedef struct isc_radix_tree {
  106     unsigned int      magic;
  107     isc_mem_t *   mctx;
  108     isc_radix_node_t *head;
  109     uint32_t      maxbits;     /* for IP, 32 bit addresses */
  110     int       num_active_node; /* for debugging purposes */
  111     int       num_added_node;  /* total number of nodes */
  112 } isc_radix_tree_t;
  113 
  114 isc_result_t
  115 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
  116          isc_prefix_t *prefix);
  117 /*%<
  118  * Search 'radix' for the best match to 'prefix'.
  119  * Return the node found in '*target'.
  120  *
  121  * Requires:
  122  * \li  'radix' to be valid.
  123  * \li  'target' is not NULL and "*target" is NULL.
  124  * \li  'prefix' to be valid.
  125  *
  126  * Returns:
  127  * \li  ISC_R_NOTFOUND
  128  * \li  ISC_R_SUCCESS
  129  */
  130 
  131 isc_result_t
  132 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
  133          isc_radix_node_t *source, isc_prefix_t *prefix);
  134 /*%<
  135  * Insert 'source' or 'prefix' into the radix tree 'radix'.
  136  * Return the node added in 'target'.
  137  *
  138  * Requires:
  139  * \li  'radix' to be valid.
  140  * \li  'target' is not NULL and "*target" is NULL.
  141  * \li  'prefix' to be valid or 'source' to be non NULL and contain
  142  *  a valid prefix.
  143  *
  144  * Returns:
  145  * \li  ISC_R_NOMEMORY
  146  * \li  ISC_R_SUCCESS
  147  */
  148 
  149 void
  150 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node);
  151 /*%<
  152  * Remove the node 'node' from the radix tree 'radix'.
  153  *
  154  * Requires:
  155  * \li  'radix' to be valid.
  156  * \li  'node' to be valid.
  157  */
  158 
  159 isc_result_t
  160 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits);
  161 /*%<
  162  * Create a radix tree with a maximum depth of 'maxbits';
  163  *
  164  * Requires:
  165  * \li  'mctx' to be valid.
  166  * \li  'target' to be non NULL and '*target' to be NULL.
  167  * \li  'maxbits' to be less than or equal to RADIX_MAXBITS.
  168  *
  169  * Returns:
  170  * \li  ISC_R_NOMEMORY
  171  * \li  ISC_R_SUCCESS
  172  */
  173 
  174 void
  175 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
  176 /*%<
  177  * Destroy a radix tree optionally calling 'func' to clean up node data.
  178  *
  179  * Requires:
  180  * \li  'radix' to be valid.
  181  */
  182 
  183 void
  184 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func);
  185 /*%<
  186  * Walk a radix tree calling 'func' to process node data.
  187  *
  188  * Requires:
  189  * \li  'radix' to be valid.
  190  * \li  'func' to point to a function.
  191  */
  192 
  193 #define RADIX_MAXBITS  128
  194 #define RADIX_NBIT(x)  (0x80 >> ((x)&0x7f))
  195 #define RADIX_NBYTE(x) ((x) >> 3)
  196 
  197 #define RADIX_WALK(Xhead, Xnode)                              \
  198     do {                                                  \
  199         isc_radix_node_t * Xstack[RADIX_MAXBITS + 1]; \
  200         isc_radix_node_t **Xsp = Xstack;              \
  201         isc_radix_node_t * Xrn = (Xhead);             \
  202         while ((Xnode = Xrn)) {                       \
  203             if (Xnode->prefix)
  204 
  205 #define RADIX_WALK_END                       \
  206     if (Xrn->l) {                        \
  207         if (Xrn->r) {                \
  208             *Xsp++ = Xrn->r;     \
  209         }                            \
  210         Xrn = Xrn->l;                \
  211     } else if (Xrn->r) {                 \
  212         Xrn = Xrn->r;                \
  213     } else if (Xsp != Xstack) {          \
  214         Xrn = *(--Xsp);              \
  215     } else {                             \
  216         Xrn = (isc_radix_node_t *)0; \
  217     }                                    \
  218     }                                    \
  219     }                                    \
  220     while (0)
  221 
  222 #endif /* _RADIX_H */