"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.11.23/lib/dns/rbt.c" (7 Sep 2020, 93377 Bytes) of package /linux/misc/dns/bind9/9.11.23/bind-9.11.23.tar.gz:


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 "rbt.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 9.17.4_vs_9.17.5.

    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 /*! \file */
   13 
   14 #include <config.h>
   15 
   16 #include <sys/stat.h>
   17 #include <inttypes.h> /* uintptr_t */
   18 #include <stdbool.h>
   19 
   20 #include <isc/crc64.h>
   21 #include <isc/file.h>
   22 #include <isc/hex.h>
   23 #include <isc/mem.h>
   24 #include <isc/once.h>
   25 #include <isc/platform.h>
   26 #include <isc/print.h>
   27 #include <isc/refcount.h>
   28 #include <isc/socket.h>
   29 #include <isc/stdio.h>
   30 #include <isc/string.h>
   31 #include <isc/util.h>
   32 
   33 /*%
   34  * This define is so dns/name.h (included by dns/fixedname.h) uses more
   35  * efficient macro calls instead of functions for a few operations.
   36  */
   37 #define DNS_NAME_USEINLINE 1
   38 
   39 #include <dns/fixedname.h>
   40 #include <dns/log.h>
   41 #include <dns/rbt.h>
   42 #include <dns/result.h>
   43 #include <dns/version.h>
   44 
   45 #include <unistd.h>
   46 
   47 #define CHECK(x) \
   48     do { \
   49         result = (x); \
   50         if (result != ISC_R_SUCCESS) \
   51             goto cleanup; \
   52     } while (0)
   53 
   54 #define RBT_MAGIC               ISC_MAGIC('R', 'B', 'T', '+')
   55 #define VALID_RBT(rbt)          ISC_MAGIC_VALID(rbt, RBT_MAGIC)
   56 
   57 /*
   58  * XXXDCL Since parent pointers were added in again, I could remove all of the
   59  * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
   60  * _lastnode.  This would involve pretty major change to the API.
   61  */
   62 #define CHAIN_MAGIC             ISC_MAGIC('0', '-', '0', '-')
   63 #define VALID_CHAIN(chain)      ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
   64 
   65 #define RBT_HASH_SIZE           64
   66 
   67 #ifdef RBT_MEM_TEST
   68 #undef RBT_HASH_SIZE
   69 #define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
   70 #endif
   71 
   72 struct dns_rbt {
   73     unsigned int        magic;
   74     isc_mem_t *     mctx;
   75     dns_rbtnode_t *     root;
   76     void            (*data_deleter)(void *, void *);
   77     void *          deleter_arg;
   78     unsigned int        nodecount;
   79     size_t          hashsize;
   80     dns_rbtnode_t **    hashtable;
   81     void *          mmap_location;
   82 };
   83 
   84 #define RED 0
   85 #define BLACK 1
   86 
   87 /*
   88  * This is the header for map-format RBT images.  It is populated,
   89  * and then written, as the LAST thing done to the file before returning.
   90  * Writing this last (with zeros in the header area initially) will ensure
   91  * that the header is only valid when the RBT image is also valid.
   92  */
   93 typedef struct file_header file_header_t;
   94 
   95 /* Pad to 32 bytes */
   96 static char FILE_VERSION[32] = "\0";
   97 
   98 /* Header length, always the same size regardless of structure size */
   99 #define HEADER_LENGTH       1024
  100 
  101 struct file_header {
  102     char version1[32];
  103     uint64_t first_node_offset; /* usually 1024 */
  104     /*
  105      * information about the system on which the map file was generated
  106      * will be used to tell if we can load the map file or not
  107      */
  108     uint32_t ptrsize;
  109     unsigned int bigendian:1;   /* big or little endian system */
  110     unsigned int rdataset_fixed:1;  /* compiled with --enable-rrset-fixed */
  111     unsigned int nodecount;     /* shadow from rbt structure */
  112     uint64_t crc;
  113     char version2[32];          /* repeated; must match version1 */
  114 };
  115 
  116 /*
  117  * The following declarations are for the serialization of an RBT:
  118  *
  119  * step one: write out a zeroed header of 1024 bytes
  120  * step two: walk the tree in a depth-first, left-right-down order, writing
  121  * out the nodes, reserving space as we go, correcting addresses to point
  122  * at the proper offset in the file, and setting a flag for each pointer to
  123  * indicate that it is a reference to a location in the file, rather than in
  124  * memory.
  125  * step three: write out the header, adding the information that will be
  126  * needed to re-create the tree object itself.
  127  *
  128  * The RBTDB object will do this three times, once for each of the three
  129  * RBT objects it contains.
  130  *
  131  * Note: 'file' must point an actual open file that can be mmapped
  132  * and fseeked, not to a pipe or stream
  133  */
  134 
  135 static isc_result_t
  136 dns_rbt_zero_header(FILE *file);
  137 
  138 static isc_result_t
  139 write_header(FILE *file, dns_rbt_t *rbt, uint64_t first_node_offset,
  140          uint64_t crc);
  141 
  142 static bool
  143 match_header_version(file_header_t *header);
  144 
  145 static isc_result_t
  146 serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
  147            uintptr_t right, uintptr_t down, uintptr_t parent,
  148            uintptr_t data, uint64_t *crc);
  149 
  150 static isc_result_t
  151 serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
  152         dns_rbtdatawriter_t datawriter, void *writer_arg,
  153         uintptr_t *where, uint64_t *crc);
  154 /*
  155  * The following functions allow you to get the actual address of a pointer
  156  * without having to use an if statement to check to see if that address is
  157  * relative or not
  158  */
  159 static inline dns_rbtnode_t *
  160 getparent(dns_rbtnode_t *node, file_header_t *header) {
  161     char *adjusted_address = (char *)(node->parent);
  162     adjusted_address += node->parent_is_relative * (uintptr_t)header;
  163 
  164     return ((dns_rbtnode_t *)adjusted_address);
  165 }
  166 
  167 static inline dns_rbtnode_t *
  168 getleft(dns_rbtnode_t *node, file_header_t *header) {
  169     char *adjusted_address = (char *)(node->left);
  170     adjusted_address += node->left_is_relative * (uintptr_t)header;
  171 
  172     return ((dns_rbtnode_t *)adjusted_address);
  173 }
  174 
  175 static inline dns_rbtnode_t *
  176 getright(dns_rbtnode_t *node, file_header_t *header) {
  177     char *adjusted_address = (char *)(node->right);
  178     adjusted_address += node->right_is_relative * (uintptr_t)header;
  179 
  180     return ((dns_rbtnode_t *)adjusted_address);
  181 }
  182 
  183 static inline dns_rbtnode_t *
  184 getdown(dns_rbtnode_t *node, file_header_t *header) {
  185     char *adjusted_address = (char *)(node->down);
  186     adjusted_address += node->down_is_relative * (uintptr_t)header;
  187 
  188     return ((dns_rbtnode_t *)adjusted_address);
  189 }
  190 
  191 static inline dns_rbtnode_t *
  192 getdata(dns_rbtnode_t *node, file_header_t *header) {
  193     char *adjusted_address = (char *)(node->data);
  194     adjusted_address += node->data_is_relative * (uintptr_t)header;
  195 
  196     return ((dns_rbtnode_t *)adjusted_address);
  197 }
  198 
  199 /*%
  200  * Elements of the rbtnode structure.
  201  */
  202 #define PARENT(node)            ((node)->parent)
  203 #define LEFT(node)              ((node)->left)
  204 #define RIGHT(node)             ((node)->right)
  205 #define DOWN(node)              ((node)->down)
  206 #ifdef DNS_RBT_USEHASH
  207 #define UPPERNODE(node)         ((node)->uppernode)
  208 #endif /* DNS_RBT_USEHASH */
  209 #define DATA(node)              ((node)->data)
  210 #define IS_EMPTY(node)          ((node)->data == NULL)
  211 #define HASHNEXT(node)          ((node)->hashnext)
  212 #define HASHVAL(node)           ((node)->hashval)
  213 #define COLOR(node)             ((node)->color)
  214 #define NAMELEN(node)           ((node)->namelen)
  215 #define OLDNAMELEN(node)        ((node)->oldnamelen)
  216 #define OFFSETLEN(node)         ((node)->offsetlen)
  217 #define ATTRS(node)             ((node)->attributes)
  218 #define IS_ROOT(node)           ((node)->is_root == 1)
  219 #define FINDCALLBACK(node)      ((node)->find_callback == 1)
  220 
  221 /*%
  222  * Structure elements from the rbtdb.c, not
  223  * used as part of the rbt.c algorithms.
  224  */
  225 #define DIRTY(node)     ((node)->dirty)
  226 #define WILD(node)      ((node)->wild)
  227 #define LOCKNUM(node)   ((node)->locknum)
  228 
  229 /*%
  230  * The variable length stuff stored after the node has the following
  231  * structure.
  232  *
  233  *  &lt;name_data&gt;{1..255}&lt;oldoffsetlen&gt;{1}&lt;offsets&gt;{1..128}
  234  *
  235  * &lt;name_data&gt; contains the name of the node when it was created.
  236  * &lt;oldoffsetlen&gt; contains the length of &lt;offsets&gt; when the node was created.
  237  * &lt;offsets&gt; contains the offsets into name for each label when the node was
  238  * created.
  239  */
  240 
  241 #define NAME(node)      ((unsigned char *)((node) + 1))
  242 #define OFFSETS(node)   (NAME(node) + OLDNAMELEN(node) + 1)
  243 #define OLDOFFSETLEN(node) (OFFSETS(node)[-1])
  244 
  245 #define NODE_SIZE(node) (sizeof(*node) + \
  246              OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)
  247 
  248 /*%
  249  * Color management.
  250  */
  251 #define IS_RED(node)            ((node) != NULL && (node)->color == RED)
  252 #define IS_BLACK(node)          ((node) == NULL || (node)->color == BLACK)
  253 #define MAKE_RED(node)          ((node)->color = RED)
  254 #define MAKE_BLACK(node)        ((node)->color = BLACK)
  255 
  256 /*%
  257  * Chain management.
  258  *
  259  * The "ancestors" member of chains were removed, with their job now
  260  * being wholly handled by parent pointers (which didn't exist, because
  261  * of memory concerns, when chains were first implemented).
  262  */
  263 #define ADD_LEVEL(chain, node) \
  264     do { \
  265         INSIST((chain)->level_count < DNS_RBT_LEVELBLOCK); \
  266         (chain)->levels[(chain)->level_count++] = (node); \
  267     } while (0)
  268 
  269 /*%
  270  * The following macros directly access normally private name variables.
  271  * These macros are used to avoid a lot of function calls in the critical
  272  * path of the tree traversal code.
  273  */
  274 
  275 static inline void
  276 NODENAME(dns_rbtnode_t *node, dns_name_t *name) {
  277     name->length = NAMELEN(node);
  278     name->labels = OFFSETLEN(node);
  279     name->ndata = NAME(node);
  280     name->offsets = OFFSETS(node);
  281     name->attributes = ATTRS(node);
  282     name->attributes |= DNS_NAMEATTR_READONLY;
  283 }
  284 
  285 void
  286 dns_rbtnode_nodename(dns_rbtnode_t *node, dns_name_t *name) {
  287     name->length = NAMELEN(node);
  288     name->labels = OFFSETLEN(node);
  289     name->ndata = NAME(node);
  290     name->offsets = OFFSETS(node);
  291     name->attributes = ATTRS(node);
  292     name->attributes |= DNS_NAMEATTR_READONLY;
  293 }
  294 
  295 dns_rbtnode_t *
  296 dns_rbt_root(dns_rbt_t *rbt) {
  297   return rbt->root;
  298 }
  299 
  300 #ifdef DNS_RBT_USEHASH
  301 static isc_result_t
  302 inithash(dns_rbt_t *rbt);
  303 #endif
  304 
  305 #ifdef DEBUG
  306 #define inline
  307 /*
  308  * A little something to help out in GDB.
  309  */
  310 dns_name_t Name(dns_rbtnode_t *node);
  311 dns_name_t
  312 Name(dns_rbtnode_t *node) {
  313     dns_name_t name;
  314 
  315     dns_name_init(&name, NULL);
  316     if (node != NULL)
  317         NODENAME(node, &name);
  318 
  319     return (name);
  320 }
  321 
  322 static void
  323 hexdump(const char *desc, unsigned char *data, size_t size) {
  324     char hexdump[BUFSIZ * 2 + 1];
  325     isc_buffer_t b;
  326     isc_region_t r;
  327     isc_result_t result;
  328     size_t bytes;
  329 
  330     fprintf(stderr, "%s: ", desc);
  331     do {
  332         isc_buffer_init(&b, hexdump, sizeof(hexdump));
  333         r.base = data;
  334         r.length = bytes = (size > BUFSIZ) ? BUFSIZ : size;
  335         result = isc_hex_totext(&r, 0, "", &b);
  336         RUNTIME_CHECK(result == ISC_R_SUCCESS);
  337         isc_buffer_putuint8(&b, 0);
  338         fprintf(stderr, "%s", hexdump);
  339         data += bytes;
  340         size -= bytes;
  341     } while (size > 0);
  342     fprintf(stderr, "\n");
  343 }
  344 #endif /* DEBUG */
  345 
  346 #ifdef DNS_RBT_USEHASH
  347 
  348 /*
  349  * Upper node is the parent of the root of the passed node's
  350  * subtree. The passed node must not be NULL.
  351  */
  352 static inline dns_rbtnode_t *
  353 get_upper_node(dns_rbtnode_t *node) {
  354     return (UPPERNODE(node));
  355 }
  356 
  357 static void
  358 fixup_uppernodes_helper(dns_rbtnode_t *node, dns_rbtnode_t *uppernode) {
  359     if (node == NULL)
  360         return;
  361 
  362     UPPERNODE(node) = uppernode;
  363 
  364     fixup_uppernodes_helper(LEFT(node), uppernode);
  365     fixup_uppernodes_helper(RIGHT(node), uppernode);
  366     fixup_uppernodes_helper(DOWN(node), node);
  367 }
  368 
  369 /*
  370  * This function is used to fixup uppernode members of all dns_rbtnodes
  371  * after deserialization.
  372  */
  373 static void
  374 fixup_uppernodes(dns_rbt_t *rbt) {
  375     fixup_uppernodes_helper(rbt->root, NULL);
  376 }
  377 
  378 #else
  379 
  380 /* The passed node must not be NULL. */
  381 static inline dns_rbtnode_t *
  382 get_subtree_root(dns_rbtnode_t *node) {
  383     while (!IS_ROOT(node)) {
  384         node = PARENT(node);
  385     }
  386 
  387     return (node);
  388 }
  389 
  390 /* Upper node is the parent of the root of the passed node's
  391  * subtree. The passed node must not be NULL.
  392  */
  393 static inline dns_rbtnode_t *
  394 get_upper_node(dns_rbtnode_t *node) {
  395     dns_rbtnode_t *root = get_subtree_root(node);
  396 
  397     /*
  398      * Return the node in the level above the argument node that points
  399      * to the level the argument node is in.  If the argument node is in
  400      * the top level, the return value is NULL.
  401      */
  402     return (PARENT(root));
  403 }
  404 
  405 #endif /* DNS_RBT_USEHASH */
  406 
  407 size_t
  408 dns__rbtnode_getdistance(dns_rbtnode_t *node) {
  409     size_t nodes = 1;
  410 
  411     while (node != NULL) {
  412         if (IS_ROOT(node))
  413             break;
  414         nodes++;
  415         node = PARENT(node);
  416     }
  417 
  418     return (nodes);
  419 }
  420 
  421 /*
  422  * Forward declarations.
  423  */
  424 static isc_result_t
  425 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
  426 
  427 #ifdef DNS_RBT_USEHASH
  428 static inline void
  429 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
  430 static inline void
  431 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
  432 static void
  433 rehash(dns_rbt_t *rbt, unsigned int newcount);
  434 #else
  435 #define hash_node(rbt, node, name)
  436 #define unhash_node(rbt, node)
  437 #define rehash(rbt, newcount)
  438 #endif
  439 
  440 static inline void
  441 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
  442 static inline void
  443 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
  444 
  445 static void
  446 addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
  447        dns_rbtnode_t **rootp);
  448 
  449 static void
  450 deletefromlevel(dns_rbtnode_t *item, dns_rbtnode_t **rootp);
  451 
  452 static isc_result_t
  453 treefix(dns_rbt_t *rbt, void *base, size_t size,
  454     dns_rbtnode_t *n, dns_name_t *name,
  455     dns_rbtdatafixer_t datafixer, void *fixer_arg,
  456     uint64_t *crc);
  457 
  458 static void
  459 deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, bool unhash,
  460            dns_rbtnode_t **nodep);
  461 
  462 static void
  463 printnodename(dns_rbtnode_t *node, bool quoted, FILE *f);
  464 
  465 static void
  466 freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep);
  467 
  468 static isc_result_t
  469 dns_rbt_zero_header(FILE *file) {
  470     /*
  471      * Write out a zeroed header as a placeholder.  Doing this ensures
  472      * that the file will not read while it is partially written, should
  473      * writing fail or be interrupted.
  474      */
  475     char buffer[HEADER_LENGTH];
  476     isc_result_t result;
  477 
  478     memset(buffer, 0, HEADER_LENGTH);
  479     result = isc_stdio_write(buffer, 1, HEADER_LENGTH, file, NULL);
  480     if (result != ISC_R_SUCCESS)
  481         return (result);
  482 
  483     result = fflush(file);
  484     if (result != ISC_R_SUCCESS)
  485         return (result);
  486 
  487     return (ISC_R_SUCCESS);
  488 }
  489 
  490 static isc_once_t once = ISC_ONCE_INIT;
  491 
  492 static void
  493 init_file_version(void) {
  494     int n;
  495 
  496     memset(FILE_VERSION, 0, sizeof(FILE_VERSION));
  497     n = snprintf(FILE_VERSION, sizeof(FILE_VERSION),
  498          "RBT Image %s %s", dns_major, dns_mapapi);
  499     INSIST(n > 0 && (unsigned int)n < sizeof(FILE_VERSION));
  500 }
  501 
  502 /*
  503  * Write out the real header, including NodeDump version information
  504  * and the offset of the first node.
  505  *
  506  * Any information stored in the rbt object itself should be stored
  507  * here.
  508  */
  509 static isc_result_t
  510 write_header(FILE *file, dns_rbt_t *rbt, uint64_t first_node_offset,
  511          uint64_t crc)
  512 {
  513     file_header_t header;
  514     isc_result_t result;
  515     off_t location;
  516 
  517     RUNTIME_CHECK(isc_once_do(&once, init_file_version) == ISC_R_SUCCESS);
  518 
  519     memset(&header, 0, sizeof(file_header_t));
  520     memmove(header.version1, FILE_VERSION, sizeof(header.version1));
  521     memmove(header.version2, FILE_VERSION, sizeof(header.version2));
  522     header.first_node_offset = first_node_offset;
  523     header.ptrsize = (uint32_t) sizeof(void *);
  524     header.bigendian = (1 == htonl(1)) ? 1 : 0;
  525 
  526 #ifdef DNS_RDATASET_FIXED
  527     header.rdataset_fixed = 1;
  528 #else
  529     header.rdataset_fixed = 0;
  530 #endif
  531 
  532     header.nodecount = rbt->nodecount;
  533 
  534     header.crc = crc;
  535 
  536     CHECK(isc_stdio_tell(file, &location));
  537     location = dns_rbt_serialize_align(location);
  538     CHECK(isc_stdio_seek(file, location, SEEK_SET));
  539     CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));
  540     CHECK(fflush(file));
  541 
  542     /* Ensure we are always at the end of the file. */
  543     CHECK(isc_stdio_seek(file, 0, SEEK_END));
  544 
  545  cleanup:
  546     return (result);
  547 }
  548 
  549 static bool
  550 match_header_version(file_header_t *header) {
  551     RUNTIME_CHECK(isc_once_do(&once, init_file_version) == ISC_R_SUCCESS);
  552 
  553     if (memcmp(header->version1, FILE_VERSION,
  554            sizeof(header->version1)) != 0 ||
  555         memcmp(header->version2, FILE_VERSION,
  556            sizeof(header->version1)) != 0)
  557     {
  558         return (false);
  559     }
  560 
  561     return (true);
  562 }
  563 
  564 static isc_result_t
  565 serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
  566            uintptr_t right, uintptr_t down, uintptr_t parent,
  567            uintptr_t data, uint64_t *crc)
  568 {
  569     dns_rbtnode_t temp_node;
  570     off_t file_position;
  571     unsigned char *node_data;
  572     size_t datasize;
  573     isc_result_t result;
  574 #ifdef DEBUG
  575     dns_name_t nodename;
  576 #endif
  577 
  578     INSIST(node != NULL);
  579 
  580     CHECK(isc_stdio_tell(file, &file_position));
  581     file_position = dns_rbt_serialize_align(file_position);
  582     CHECK(isc_stdio_seek(file, file_position, SEEK_SET));
  583 
  584     temp_node = *node;
  585     temp_node.down_is_relative = 0;
  586     temp_node.left_is_relative = 0;
  587     temp_node.right_is_relative = 0;
  588     temp_node.parent_is_relative = 0;
  589     temp_node.data_is_relative = 0;
  590     temp_node.is_mmapped = 1;
  591 
  592     /*
  593      * If the next node is not NULL, calculate the next node's location
  594      * in the file.  Note that this will have to change when the data
  595      * structure changes, and it also assumes that we always write the
  596      * nodes out in list order (which we currently do.)
  597     */
  598     if (temp_node.parent != NULL) {
  599         temp_node.parent = (dns_rbtnode_t *)(parent);
  600         temp_node.parent_is_relative = 1;
  601     }
  602     if (temp_node.left != NULL) {
  603         temp_node.left = (dns_rbtnode_t *)(left);
  604         temp_node.left_is_relative = 1;
  605     }
  606     if (temp_node.right != NULL) {
  607         temp_node.right = (dns_rbtnode_t *)(right);
  608         temp_node.right_is_relative = 1;
  609     }
  610     if (temp_node.down != NULL) {
  611         temp_node.down = (dns_rbtnode_t *)(down);
  612         temp_node.down_is_relative = 1;
  613     }
  614     if (temp_node.data != NULL) {
  615         temp_node.data = (dns_rbtnode_t *)(data);
  616         temp_node.data_is_relative = 1;
  617     }
  618 
  619     node_data = (unsigned char *) node + sizeof(dns_rbtnode_t);
  620     datasize = NODE_SIZE(node) - sizeof(dns_rbtnode_t);
  621 
  622     CHECK(isc_stdio_write(&temp_node, 1, sizeof(dns_rbtnode_t),
  623                   file, NULL));
  624     CHECK(isc_stdio_write(node_data, 1, datasize, file, NULL));
  625 
  626 #ifdef DEBUG
  627     dns_name_init(&nodename, NULL);
  628     NODENAME(node, &nodename);
  629     fprintf(stderr, "serialize ");
  630     dns_name_print(&nodename, stderr);
  631     fprintf(stderr, "\n");
  632     hexdump("node header", (unsigned char*) &temp_node,
  633         sizeof(dns_rbtnode_t));
  634     hexdump("node data", node_data, datasize);
  635 #endif
  636 
  637     isc_crc64_update(crc, (const uint8_t *) &temp_node,
  638              sizeof(dns_rbtnode_t));
  639     isc_crc64_update(crc, (const uint8_t *) node_data, datasize);
  640 
  641  cleanup:
  642     return (result);
  643 }
  644 
  645 static isc_result_t
  646 serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
  647         dns_rbtdatawriter_t datawriter, void *writer_arg,
  648         uintptr_t *where, uint64_t *crc)
  649 {
  650     uintptr_t left = 0, right = 0, down = 0, data = 0;
  651     off_t location = 0, offset_adjust;
  652     isc_result_t result;
  653 
  654     if (node == NULL) {
  655         if (where != NULL)
  656             *where = 0;
  657         return (ISC_R_SUCCESS);
  658     }
  659 
  660     /* Reserve space for current node. */
  661     CHECK(isc_stdio_tell(file, &location));
  662     location = dns_rbt_serialize_align(location);
  663     CHECK(isc_stdio_seek(file, location, SEEK_SET));
  664 
  665     offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));
  666     CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));
  667 
  668     /*
  669      * Serialize the rest of the tree.
  670      *
  671      * WARNING: A change in the order (from left, right, down)
  672      * will break the way the crc hash is computed.
  673      */
  674     CHECK(serialize_nodes(file, getleft(node, NULL), location,
  675                   datawriter, writer_arg, &left, crc));
  676     CHECK(serialize_nodes(file, getright(node, NULL), location,
  677                   datawriter, writer_arg, &right, crc));
  678     CHECK(serialize_nodes(file, getdown(node, NULL), location,
  679                   datawriter, writer_arg, &down, crc));
  680 
  681     if (node->data != NULL) {
  682         off_t ret;
  683 
  684         CHECK(isc_stdio_tell(file, &ret));
  685         ret = dns_rbt_serialize_align(ret);
  686         CHECK(isc_stdio_seek(file, ret, SEEK_SET));
  687         data = ret;
  688 
  689         datawriter(file, node->data, writer_arg, crc);
  690     }
  691 
  692     /* Seek back to reserved space. */
  693     CHECK(isc_stdio_seek(file, location, SEEK_SET));
  694 
  695     /* Serialize the current node. */
  696     CHECK(serialize_node(file, node, left, right, down, parent, data, crc));
  697 
  698     /* Ensure we are always at the end of the file. */
  699     CHECK(isc_stdio_seek(file, 0, SEEK_END));
  700 
  701     if (where != NULL)
  702         *where = (uintptr_t) location;
  703 
  704  cleanup:
  705     return (result);
  706 }
  707 
  708 off_t
  709 dns_rbt_serialize_align(off_t target) {
  710     off_t offset = target % 8;
  711 
  712     if (offset == 0)
  713         return (target);
  714     else
  715         return (target + 8 - offset);
  716 }
  717 
  718 isc_result_t
  719 dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
  720                dns_rbtdatawriter_t datawriter,
  721                void *writer_arg, off_t *offset)
  722 {
  723     isc_result_t result;
  724     off_t header_position, node_position, end_position;
  725     uint64_t crc;
  726 
  727     REQUIRE(file != NULL);
  728 
  729     CHECK(isc_file_isplainfilefd(fileno(file)));
  730 
  731     isc_crc64_init(&crc);
  732 
  733     CHECK(isc_stdio_tell(file, &header_position));
  734 
  735     /* Write dummy header */
  736     CHECK(dns_rbt_zero_header(file));
  737 
  738     /* Serialize nodes */
  739     CHECK(isc_stdio_tell(file, &node_position));
  740     CHECK(serialize_nodes(file, rbt->root, 0, datawriter,
  741                   writer_arg, NULL, &crc));
  742 
  743     CHECK(isc_stdio_tell(file, &end_position));
  744     if (node_position == end_position) {
  745         CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
  746         *offset = 0;
  747         return (ISC_R_SUCCESS);
  748     }
  749 
  750     isc_crc64_final(&crc);
  751 #ifdef DEBUG
  752     hexdump("serializing CRC", (unsigned char *)&crc, sizeof(crc));
  753 #endif
  754 
  755     /* Serialize header */
  756     CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
  757     CHECK(write_header(file, rbt, HEADER_LENGTH, crc));
  758 
  759     /* Ensure we are always at the end of the file. */
  760     CHECK(isc_stdio_seek(file, 0, SEEK_END));
  761     *offset = dns_rbt_serialize_align(header_position);
  762 
  763  cleanup:
  764     return (result);
  765 }
  766 
  767 #define CONFIRM(a) do { \
  768     if (! (a)) { \
  769         result = ISC_R_INVALIDFILE; \
  770         goto cleanup; \
  771     } \
  772 } while(0);
  773 
  774 static isc_result_t
  775 treefix(dns_rbt_t *rbt, void *base, size_t filesize, dns_rbtnode_t *n,
  776     dns_name_t *name, dns_rbtdatafixer_t datafixer,
  777     void *fixer_arg, uint64_t *crc)
  778 {
  779     isc_result_t result = ISC_R_SUCCESS;
  780     dns_fixedname_t fixed;
  781     dns_name_t nodename, *fullname;
  782     unsigned char *node_data;
  783     dns_rbtnode_t header;
  784     size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);
  785 
  786     if (n == NULL)
  787         return (ISC_R_SUCCESS);
  788 
  789     CONFIRM((void *) n >= base);
  790     CONFIRM((char *) n - (char *) base <= (int) nodemax);
  791     CONFIRM(DNS_RBTNODE_VALID(n));
  792 
  793     dns_name_init(&nodename, NULL);
  794     NODENAME(n, &nodename);
  795 
  796     fullname = &nodename;
  797     CONFIRM(dns_name_isvalid(fullname));
  798 
  799     if (!dns_name_isabsolute(&nodename)) {
  800         fullname = dns_fixedname_initname(&fixed);
  801         CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));
  802     }
  803 
  804     /* memorize header contents prior to fixup */
  805     memmove(&header, n, sizeof(header));
  806 
  807     if (n->left_is_relative) {
  808         CONFIRM(n->left <= (dns_rbtnode_t *) nodemax);
  809         n->left = getleft(n, rbt->mmap_location);
  810         n->left_is_relative = 0;
  811         CONFIRM(DNS_RBTNODE_VALID(n->left));
  812     } else
  813         CONFIRM(n->left == NULL);
  814 
  815     if (n->right_is_relative) {
  816         CONFIRM(n->right <= (dns_rbtnode_t *) nodemax);
  817         n->right = getright(n, rbt->mmap_location);
  818         n->right_is_relative = 0;
  819         CONFIRM(DNS_RBTNODE_VALID(n->right));
  820     } else
  821         CONFIRM(n->right == NULL);
  822 
  823     if (n->down_is_relative) {
  824         CONFIRM(n->down <= (dns_rbtnode_t *) nodemax);
  825         n->down = getdown(n, rbt->mmap_location);
  826         n->down_is_relative = 0;
  827         CONFIRM(n->down > (dns_rbtnode_t *) n);
  828         CONFIRM(DNS_RBTNODE_VALID(n->down));
  829     } else
  830         CONFIRM(n->down == NULL);
  831 
  832     if (n->parent_is_relative) {
  833         CONFIRM(n->parent <= (dns_rbtnode_t *) nodemax);
  834         n->parent = getparent(n, rbt->mmap_location);
  835         n->parent_is_relative = 0;
  836         CONFIRM(n->parent < (dns_rbtnode_t *) n);
  837         CONFIRM(DNS_RBTNODE_VALID(n->parent));
  838     } else
  839         CONFIRM(n->parent == NULL);
  840 
  841     if (n->data_is_relative) {
  842         CONFIRM(n->data <= (void *) filesize);
  843         n->data = getdata(n, rbt->mmap_location);
  844         n->data_is_relative = 0;
  845         CONFIRM(n->data > (void *) n);
  846     } else
  847         CONFIRM(n->data == NULL);
  848 
  849     hash_node(rbt, n, fullname);
  850 
  851     /* a change in the order (from left, right, down) will break hashing*/
  852     if (n->left != NULL)
  853         CHECK(treefix(rbt, base, filesize, n->left, name,
  854                   datafixer, fixer_arg, crc));
  855     if (n->right != NULL)
  856         CHECK(treefix(rbt, base, filesize, n->right, name,
  857                   datafixer, fixer_arg, crc));
  858     if (n->down != NULL)
  859         CHECK(treefix(rbt, base, filesize, n->down, fullname,
  860                   datafixer, fixer_arg, crc));
  861 
  862     if (datafixer != NULL && n->data != NULL)
  863         CHECK(datafixer(n, base, filesize, fixer_arg, crc));
  864 
  865     rbt->nodecount++;
  866     node_data = (unsigned char *) n + sizeof(dns_rbtnode_t);
  867     datasize = NODE_SIZE(n) - sizeof(dns_rbtnode_t);
  868 
  869 #ifdef DEBUG
  870     fprintf(stderr, "deserialize ");
  871     dns_name_print(&nodename, stderr);
  872     fprintf(stderr, "\n");
  873     hexdump("node header", (unsigned char *) &header,
  874         sizeof(dns_rbtnode_t));
  875     hexdump("node data", node_data, datasize);
  876 #endif
  877     isc_crc64_update(crc, (const uint8_t *) &header,
  878             sizeof(dns_rbtnode_t));
  879     isc_crc64_update(crc, (const uint8_t *) node_data,
  880             datasize);
  881 
  882  cleanup:
  883     return (result);
  884 }
  885 
  886 isc_result_t
  887 dns_rbt_deserialize_tree(void *base_address, size_t filesize,
  888              off_t header_offset, isc_mem_t *mctx,
  889              dns_rbtdeleter_t deleter, void *deleter_arg,
  890              dns_rbtdatafixer_t datafixer, void *fixer_arg,
  891              dns_rbtnode_t **originp, dns_rbt_t **rbtp)
  892 {
  893     isc_result_t result = ISC_R_SUCCESS;
  894     file_header_t *header;
  895     dns_rbt_t *rbt = NULL;
  896     uint64_t crc;
  897     unsigned int host_big_endian;
  898 
  899     REQUIRE(originp == NULL || *originp == NULL);
  900     REQUIRE(rbtp != NULL && *rbtp == NULL);
  901 
  902     isc_crc64_init(&crc);
  903 
  904     CHECK(dns_rbt_create(mctx, deleter, deleter_arg, &rbt));
  905 
  906     rbt->mmap_location = base_address;
  907 
  908     header = (file_header_t *)((char *)base_address + header_offset);
  909     if (!match_header_version(header)) {
  910         result = ISC_R_INVALIDFILE;
  911         goto cleanup;
  912     }
  913 
  914 #ifdef DNS_RDATASET_FIXED
  915     if (header->rdataset_fixed != 1) {
  916         result = ISC_R_INVALIDFILE;
  917         goto cleanup;
  918     }
  919 
  920 #else
  921     if (header->rdataset_fixed != 0) {
  922         result = ISC_R_INVALIDFILE;
  923         goto cleanup;
  924     }
  925 #endif
  926 
  927     if (header->ptrsize != (uint32_t) sizeof(void *)) {
  928         result = ISC_R_INVALIDFILE;
  929         goto cleanup;
  930     }
  931 
  932     host_big_endian = (1 == htonl(1));
  933     if (header->bigendian != host_big_endian) {
  934         result = ISC_R_INVALIDFILE;
  935         goto cleanup;
  936     }
  937 
  938     /* Copy other data items from the header into our rbt. */
  939     rbt->root = (dns_rbtnode_t *)((char *)base_address +
  940                 header_offset + header->first_node_offset);
  941 
  942     if ((header->nodecount * sizeof(dns_rbtnode_t)) > filesize) {
  943         result = ISC_R_INVALIDFILE;
  944         goto cleanup;
  945     }
  946     rehash(rbt, header->nodecount);
  947 
  948     CHECK(treefix(rbt, base_address, filesize, rbt->root,
  949               dns_rootname, datafixer, fixer_arg, &crc));
  950 
  951     isc_crc64_final(&crc);
  952 #ifdef DEBUG
  953     hexdump("deserializing CRC", (unsigned char *)&crc, sizeof(crc));
  954 #endif
  955 
  956     /* Check file hash */
  957     if (header->crc != crc) {
  958         result = ISC_R_INVALIDFILE;
  959         goto cleanup;
  960     }
  961 
  962     if (header->nodecount != rbt->nodecount) {
  963         result = ISC_R_INVALIDFILE;
  964         goto cleanup;
  965     }
  966 
  967 #ifdef DNS_RBT_USEHASH
  968     fixup_uppernodes(rbt);
  969 #endif /* DNS_RBT_USEHASH */
  970 
  971     *rbtp = rbt;
  972     if (originp != NULL)
  973         *originp = rbt->root;
  974 
  975  cleanup:
  976     if (result != ISC_R_SUCCESS && rbt != NULL) {
  977         rbt->root = NULL;
  978         rbt->nodecount = 0;
  979         dns_rbt_destroy(&rbt);
  980     }
  981 
  982     return (result);
  983 }
  984 
  985 /*
  986  * Initialize a red/black tree of trees.
  987  */
  988 isc_result_t
  989 dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,
  990            void *deleter_arg, dns_rbt_t **rbtp)
  991 {
  992 #ifdef DNS_RBT_USEHASH
  993     isc_result_t result;
  994 #endif
  995     dns_rbt_t *rbt;
  996 
  997     REQUIRE(mctx != NULL);
  998     REQUIRE(rbtp != NULL && *rbtp == NULL);
  999     REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
 1000 
 1001     rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
 1002     if (rbt == NULL)
 1003         return (ISC_R_NOMEMORY);
 1004 
 1005     rbt->mctx = NULL;
 1006     isc_mem_attach(mctx, &rbt->mctx);
 1007     rbt->data_deleter = deleter;
 1008     rbt->deleter_arg = deleter_arg;
 1009     rbt->root = NULL;
 1010     rbt->nodecount = 0;
 1011     rbt->hashtable = NULL;
 1012     rbt->hashsize = 0;
 1013     rbt->mmap_location = NULL;
 1014 
 1015 #ifdef DNS_RBT_USEHASH
 1016     result = inithash(rbt);
 1017     if (result != ISC_R_SUCCESS) {
 1018         isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
 1019         return (result);
 1020     }
 1021 #endif
 1022 
 1023     rbt->magic = RBT_MAGIC;
 1024 
 1025     *rbtp = rbt;
 1026 
 1027     return (ISC_R_SUCCESS);
 1028 }
 1029 
 1030 /*
 1031  * Deallocate a red/black tree of trees.
 1032  */
 1033 void
 1034 dns_rbt_destroy(dns_rbt_t **rbtp) {
 1035     RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
 1036 }
 1037 
 1038 isc_result_t
 1039 dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
 1040     dns_rbt_t *rbt;
 1041 
 1042     REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
 1043 
 1044     rbt = *rbtp;
 1045 
 1046     deletetreeflat(rbt, quantum, false, &rbt->root);
 1047     if (rbt->root != NULL)
 1048         return (ISC_R_QUOTA);
 1049 
 1050     INSIST(rbt->nodecount == 0);
 1051 
 1052     rbt->mmap_location = NULL;
 1053 
 1054     if (rbt->hashtable != NULL)
 1055         isc_mem_put(rbt->mctx, rbt->hashtable,
 1056                 rbt->hashsize * sizeof(dns_rbtnode_t *));
 1057 
 1058     rbt->magic = 0;
 1059 
 1060     isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
 1061     *rbtp = NULL;
 1062     return (ISC_R_SUCCESS);
 1063 }
 1064 
 1065 unsigned int
 1066 dns_rbt_nodecount(dns_rbt_t *rbt) {
 1067 
 1068     REQUIRE(VALID_RBT(rbt));
 1069 
 1070     return (rbt->nodecount);
 1071 }
 1072 
 1073 size_t
 1074 dns_rbt_hashsize(dns_rbt_t *rbt) {
 1075 
 1076     REQUIRE(VALID_RBT(rbt));
 1077 
 1078     return (rbt->hashsize);
 1079 }
 1080 
 1081 static inline isc_result_t
 1082 chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
 1083        bool include_chain_end)
 1084 {
 1085     dns_name_t nodename;
 1086     isc_result_t result = ISC_R_SUCCESS;
 1087     int i;
 1088 
 1089     dns_name_init(&nodename, NULL);
 1090 
 1091     if (include_chain_end && chain->end != NULL) {
 1092         NODENAME(chain->end, &nodename);
 1093         result = dns_name_copy(&nodename, name, NULL);
 1094         if (result != ISC_R_SUCCESS)
 1095             return (result);
 1096     } else
 1097         dns_name_reset(name);
 1098 
 1099     for (i = (int)chain->level_count - 1; i >= 0; i--) {
 1100         NODENAME(chain->levels[i], &nodename);
 1101         result = dns_name_concatenate(name, &nodename, name, NULL);
 1102 
 1103         if (result != ISC_R_SUCCESS)
 1104             return (result);
 1105     }
 1106     return (result);
 1107 }
 1108 
 1109 static inline isc_result_t
 1110 move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
 1111     do {
 1112         /*
 1113          * Go as far right and then down as much as possible,
 1114          * as long as the rightmost node has a down pointer.
 1115          */
 1116         while (RIGHT(node) != NULL)
 1117             node = RIGHT(node);
 1118 
 1119         if (DOWN(node) == NULL)
 1120             break;
 1121 
 1122         ADD_LEVEL(chain, node);
 1123         node = DOWN(node);
 1124     } while (1);
 1125 
 1126     chain->end = node;
 1127 
 1128     return (ISC_R_SUCCESS);
 1129 }
 1130 
 1131 /*
 1132  * Add 'name' to tree, initializing its data pointer with 'data'.
 1133  */
 1134 
 1135 isc_result_t
 1136 dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
 1137     /*
 1138      * Does this thing have too many variables or what?
 1139      */
 1140     dns_rbtnode_t **root, *parent, *child, *current, *new_current;
 1141     dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
 1142     dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
 1143     dns_offsets_t current_offsets;
 1144     dns_namereln_t compared;
 1145     isc_result_t result = ISC_R_SUCCESS;
 1146     unsigned int level_count;
 1147     unsigned int common_labels;
 1148     unsigned int nlabels, hlabels;
 1149     int order;
 1150 
 1151     REQUIRE(VALID_RBT(rbt));
 1152     REQUIRE(dns_name_isabsolute(name));
 1153     REQUIRE(nodep != NULL && *nodep == NULL);
 1154 
 1155     /*
 1156      * Dear future BIND developer,
 1157      *
 1158      * After you have tried attempting to optimize this routine by
 1159      * using the hashtable and have realized your folly, please
 1160      * append another cross ("X") below as a warning to the next
 1161      * future BIND developer:
 1162      *
 1163      * Number of victim developers: X
 1164      *
 1165      * I wish the past developer had included such a notice.
 1166      *
 1167      * Long form: Unlike dns_rbt_findnode(), this function does not
 1168      * lend itself to be optimized using the hashtable:
 1169      *
 1170      * 1. In the subtree where the insertion occurs, this function
 1171      * needs to have the insertion point and the order where the
 1172      * lookup terminated (i.e., at the insertion point where left or
 1173      * right child is NULL). This cannot be determined from the
 1174      * hashtable, so at least in that subtree, a BST O(log N) lookup
 1175      * is necessary.
 1176      *
 1177      * 2. Our RBT nodes contain not only single labels but label
 1178      * sequences to optimize space usage. So at every level, we have
 1179      * to look for a match in the hashtable for all superdomains in
 1180      * the rest of the name we're searching. This is an O(N)
 1181      * operation at least, here N being the label size of name, each
 1182      * of which is a hashtable lookup involving dns_name_equal()
 1183      * comparisons.
 1184      */
 1185 
 1186     /*
 1187      * Create a copy of the name so the original name structure is
 1188      * not modified.
 1189      */
 1190     add_name = dns_fixedname_initname(&fixedcopy);
 1191     dns_name_clone(name, add_name);
 1192 
 1193     if (ISC_UNLIKELY(rbt->root == NULL)) {
 1194         result = create_node(rbt->mctx, add_name, &new_current);
 1195         if (result == ISC_R_SUCCESS) {
 1196             rbt->nodecount++;
 1197             new_current->is_root = 1;
 1198 #ifdef DNS_RBT_USEHASH
 1199             UPPERNODE(new_current) = NULL;
 1200 #endif /* DNS_RBT_USEHASH */
 1201             rbt->root = new_current;
 1202             *nodep = new_current;
 1203             hash_node(rbt, new_current, name);
 1204         }
 1205         return (result);
 1206     }
 1207 
 1208     level_count = 0;
 1209 
 1210     prefix = dns_fixedname_initname(&fixedprefix);
 1211     suffix = dns_fixedname_initname(&fixedsuffix);
 1212 
 1213     root = &rbt->root;
 1214     INSIST(IS_ROOT(*root));
 1215     parent = NULL;
 1216     current = NULL;
 1217     child = *root;
 1218     dns_name_init(&current_name, current_offsets);
 1219     new_name = dns_fixedname_initname(&fnewname);
 1220     nlabels = dns_name_countlabels(name);
 1221     hlabels = 0;
 1222 
 1223     do {
 1224         current = child;
 1225 
 1226         NODENAME(current, &current_name);
 1227         compared = dns_name_fullcompare(add_name, &current_name,
 1228                         &order, &common_labels);
 1229 
 1230         if (compared == dns_namereln_equal) {
 1231             *nodep = current;
 1232             result = ISC_R_EXISTS;
 1233             break;
 1234 
 1235         }
 1236 
 1237         if (compared == dns_namereln_none) {
 1238 
 1239             if (order < 0) {
 1240                 parent = current;
 1241                 child = LEFT(current);
 1242 
 1243             } else if (order > 0) {
 1244                 parent = current;
 1245                 child = RIGHT(current);
 1246 
 1247             }
 1248 
 1249         } else {
 1250             /*
 1251              * This name has some suffix in common with the
 1252              * name at the current node.  If the name at
 1253              * the current node is shorter, that means the
 1254              * new name should be in a subtree.  If the
 1255              * name at the current node is longer, that means
 1256              * the down pointer to this tree should point
 1257              * to a new tree that has the common suffix, and
 1258              * the non-common parts of these two names should
 1259              * start a new tree.
 1260              */
 1261             hlabels += common_labels;
 1262             if (compared == dns_namereln_subdomain) {
 1263                 /*
 1264                  * All of the existing labels are in common,
 1265                  * so the new name is in a subtree.
 1266                  * Whack off the common labels for the
 1267                  * not-in-common part to be searched for
 1268                  * in the next level.
 1269                  */
 1270                 dns_name_split(add_name, common_labels,
 1271                            add_name, NULL);
 1272 
 1273                 /*
 1274                  * Follow the down pointer (possibly NULL).
 1275                  */
 1276                 root = &DOWN(current);
 1277 
 1278                 INSIST(*root == NULL ||
 1279                        (IS_ROOT(*root) &&
 1280                     PARENT(*root) == current));
 1281 
 1282                 parent = NULL;
 1283                 child = DOWN(current);
 1284 
 1285                 INSIST(level_count < DNS_RBT_LEVELBLOCK);
 1286                 level_count++;
 1287             } else {
 1288                 /*
 1289                  * The number of labels in common is fewer
 1290                  * than the number of labels at the current
 1291                  * node, so the current node must be adjusted
 1292                  * to have just the common suffix, and a down
 1293                  * pointer made to a new tree.
 1294                  */
 1295 
 1296                 INSIST(compared == dns_namereln_commonancestor
 1297                        || compared == dns_namereln_contains);
 1298 
 1299                 /*
 1300                  * Ensure the number of levels in the tree
 1301                  * does not exceed the number of logical
 1302                  * levels allowed by DNSSEC.
 1303                  *
 1304                  * XXXDCL need a better error result?
 1305                  */
 1306                 if (level_count >= DNS_RBT_LEVELBLOCK) {
 1307                     result = ISC_R_NOSPACE;
 1308                     break;
 1309                 }
 1310 
 1311                 /*
 1312                  * Split the name into two parts, a prefix
 1313                  * which is the not-in-common parts of the
 1314                  * two names and a suffix that is the common
 1315                  * parts of them.
 1316                  */
 1317                 dns_name_split(&current_name, common_labels,
 1318                            prefix, suffix);
 1319                 result = create_node(rbt->mctx, suffix,
 1320                              &new_current);
 1321 
 1322                 if (result != ISC_R_SUCCESS)
 1323                     break;
 1324 
 1325                 /*
 1326                  * Reproduce the tree attributes of the
 1327                  * current node.
 1328                  */
 1329                 new_current->is_root = current->is_root;
 1330                 if (current->nsec == DNS_RBT_NSEC_HAS_NSEC)
 1331                     new_current->nsec = DNS_RBT_NSEC_NORMAL;
 1332                 else
 1333                     new_current->nsec = current->nsec;
 1334                 PARENT(new_current)  = PARENT(current);
 1335                 LEFT(new_current)    = LEFT(current);
 1336                 RIGHT(new_current)   = RIGHT(current);
 1337                 COLOR(new_current)   = COLOR(current);
 1338 
 1339                 /*
 1340                  * Fix pointers that were to the current node.
 1341                  */
 1342                 if (parent != NULL) {
 1343                     if (LEFT(parent) == current)
 1344                         LEFT(parent) = new_current;
 1345                     else
 1346                         RIGHT(parent) = new_current;
 1347                 }
 1348                 if (LEFT(new_current) != NULL)
 1349                     PARENT(LEFT(new_current)) =
 1350                         new_current;
 1351                 if (RIGHT(new_current) != NULL)
 1352                     PARENT(RIGHT(new_current)) =
 1353                         new_current;
 1354                 if (*root == current)
 1355                     *root = new_current;
 1356 
 1357                 NAMELEN(current) = prefix->length;
 1358                 OFFSETLEN(current) = prefix->labels;
 1359 
 1360                 /*
 1361                  * Set up the new root of the next level.
 1362                  * By definition it will not be the top
 1363                  * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
 1364                  */
 1365                 current->is_root = 1;
 1366                 PARENT(current) = new_current;
 1367                 DOWN(new_current) = current;
 1368                 root = &DOWN(new_current);
 1369 #ifdef DNS_RBT_USEHASH
 1370                 UPPERNODE(new_current) = UPPERNODE(current);
 1371                 UPPERNODE(current) = new_current;
 1372 #endif /* DNS_RBT_USEHASH */
 1373 
 1374                 INSIST(level_count < DNS_RBT_LEVELBLOCK);
 1375                 level_count++;
 1376 
 1377                 LEFT(current) = NULL;
 1378                 RIGHT(current) = NULL;
 1379 
 1380                 MAKE_BLACK(current);
 1381                 ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
 1382 
 1383                 rbt->nodecount++;
 1384                 dns_name_getlabelsequence(name,
 1385                               nlabels - hlabels,
 1386                               hlabels, new_name);
 1387                 hash_node(rbt, new_current, new_name);
 1388 
 1389                 if (common_labels ==
 1390                     dns_name_countlabels(add_name)) {
 1391                     /*
 1392                      * The name has been added by pushing
 1393                      * the not-in-common parts down to
 1394                      * a new level.
 1395                      */
 1396                     *nodep = new_current;
 1397                     return (ISC_R_SUCCESS);
 1398 
 1399                 } else {
 1400                     /*
 1401                      * The current node has no data,
 1402                      * because it is just a placeholder.
 1403                      * Its data pointer is already NULL
 1404                      * from create_node()), so there's
 1405                      * nothing more to do to it.
 1406                      */
 1407 
 1408                     /*
 1409                      * The not-in-common parts of the new
 1410                      * name will be inserted into the new
 1411                      * level following this loop (unless
 1412                      * result != ISC_R_SUCCESS, which
 1413                      * is tested after the loop ends).
 1414                      */
 1415                     dns_name_split(add_name, common_labels,
 1416                                add_name, NULL);
 1417 
 1418                     break;
 1419                 }
 1420 
 1421             }
 1422 
 1423         }
 1424 
 1425     } while (ISC_LIKELY(child != NULL));
 1426 
 1427     if (ISC_LIKELY(result == ISC_R_SUCCESS))
 1428         result = create_node(rbt->mctx, add_name, &new_current);
 1429 
 1430     if (ISC_LIKELY(result == ISC_R_SUCCESS)) {
 1431 #ifdef DNS_RBT_USEHASH
 1432         if (*root == NULL)
 1433             UPPERNODE(new_current) = current;
 1434         else
 1435             UPPERNODE(new_current) = PARENT(*root);
 1436 #endif /* DNS_RBT_USEHASH */
 1437         addonlevel(new_current, current, order, root);
 1438         rbt->nodecount++;
 1439         *nodep = new_current;
 1440         hash_node(rbt, new_current, name);
 1441     }
 1442 
 1443     return (result);
 1444 }
 1445 
 1446 /*
 1447  * Add a name to the tree of trees, associating it with some data.
 1448  */
 1449 isc_result_t
 1450 dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
 1451     isc_result_t result;
 1452     dns_rbtnode_t *node;
 1453 
 1454     REQUIRE(VALID_RBT(rbt));
 1455     REQUIRE(dns_name_isabsolute(name));
 1456 
 1457     node = NULL;
 1458 
 1459     result = dns_rbt_addnode(rbt, name, &node);
 1460 
 1461     /*
 1462      * dns_rbt_addnode will report the node exists even when
 1463      * it does not have data associated with it, but the
 1464      * dns_rbt_*name functions all behave depending on whether
 1465      * there is data associated with a node.
 1466      */
 1467     if (result == ISC_R_SUCCESS ||
 1468         (result == ISC_R_EXISTS && DATA(node) == NULL)) {
 1469         DATA(node) = data;
 1470         result = ISC_R_SUCCESS;
 1471     }
 1472 
 1473     return (result);
 1474 }
 1475 
 1476 /*
 1477  * Find the node for "name" in the tree of trees.
 1478  */
 1479 isc_result_t
 1480 dns_rbt_findnode(dns_rbt_t *rbt, const dns_name_t *name, dns_name_t *foundname,
 1481          dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
 1482          unsigned int options, dns_rbtfindcallback_t callback,
 1483          void *callback_arg)
 1484 {
 1485     dns_rbtnode_t *current, *last_compared;
 1486     dns_rbtnodechain_t localchain;
 1487     dns_name_t *search_name, current_name, *callback_name;
 1488     dns_fixedname_t fixedcallbackname, fixedsearchname;
 1489     dns_namereln_t compared;
 1490     isc_result_t result, saved_result;
 1491     unsigned int common_labels;
 1492     unsigned int hlabels = 0;
 1493     int order;
 1494 
 1495     REQUIRE(VALID_RBT(rbt));
 1496     REQUIRE(dns_name_isabsolute(name));
 1497     REQUIRE(node != NULL && *node == NULL);
 1498     REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
 1499         !=         (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
 1500 
 1501     /*
 1502      * If there is a chain it needs to appear to be in a sane state,
 1503      * otherwise a chain is still needed to generate foundname and
 1504      * callback_name.
 1505      */
 1506     if (chain == NULL) {
 1507         options |= DNS_RBTFIND_NOPREDECESSOR;
 1508         chain = &localchain;
 1509         dns_rbtnodechain_init(chain, rbt->mctx);
 1510     } else
 1511         dns_rbtnodechain_reset(chain);
 1512 
 1513     if (ISC_UNLIKELY(rbt->root == NULL))
 1514         return (ISC_R_NOTFOUND);
 1515 
 1516     /*
 1517      * Appease GCC about variables it incorrectly thinks are
 1518      * possibly used uninitialized.
 1519      */
 1520     compared = dns_namereln_none;
 1521     last_compared = NULL;
 1522     order = 0;
 1523 
 1524     callback_name = dns_fixedname_initname(&fixedcallbackname);
 1525 
 1526     /*
 1527      * search_name is the name segment being sought in each tree level.
 1528      * By using a fixedname, the search_name will definitely have offsets
 1529      * for use by any splitting.
 1530      * By using dns_name_clone, no name data should be copied thanks to
 1531      * the lack of bitstring labels.
 1532      */
 1533     search_name = dns_fixedname_initname(&fixedsearchname);
 1534     dns_name_clone(name, search_name);
 1535 
 1536     dns_name_init(&current_name, NULL);
 1537 
 1538     saved_result = ISC_R_SUCCESS;
 1539     current = rbt->root;
 1540 
 1541     while (ISC_LIKELY(current != NULL)) {
 1542         NODENAME(current, &current_name);
 1543         compared = dns_name_fullcompare(search_name, &current_name,
 1544                         &order, &common_labels);
 1545         /*
 1546          * last_compared is used as a shortcut to start (or
 1547          * continue rather) finding the stop-node of the search
 1548          * when hashing was used (see much below in this
 1549          * function).
 1550          */
 1551         last_compared = current;
 1552 
 1553         if (compared == dns_namereln_equal)
 1554             break;
 1555 
 1556         if (compared == dns_namereln_none) {
 1557 #ifdef DNS_RBT_USEHASH
 1558             /*
 1559              * Here, current is pointing at a subtree root
 1560              * node. We try to find a matching node using
 1561              * the hashtable. We can get one of 3 results
 1562              * here: (a) we locate the matching node, (b) we
 1563              * find a node to which the current node has a
 1564              * subdomain relation, (c) we fail to find (a)
 1565              * or (b).
 1566              */
 1567 
 1568             dns_name_t hash_name;
 1569             dns_rbtnode_t *hnode;
 1570             dns_rbtnode_t *up_current;
 1571             unsigned int nlabels;
 1572             unsigned int tlabels = 1;
 1573             unsigned int hash;
 1574 
 1575             /*
 1576              * The case of current not being a subtree root,
 1577              * that means a left or right pointer was
 1578              * followed, only happens when the algorithm
 1579              * fell through to the traditional binary search
 1580              * because of a bitstring label.  Since we
 1581              * dropped the bitstring support, this should
 1582              * not happen.
 1583              */
 1584             INSIST(IS_ROOT(current));
 1585 
 1586             nlabels = dns_name_countlabels(search_name);
 1587 
 1588             /*
 1589              * current is the root of the current level, so
 1590              * its parent is the same as its "up" pointer.
 1591              */
 1592             up_current = PARENT(current);
 1593             dns_name_init(&hash_name, NULL);
 1594 
 1595         hashagain:
 1596             /*
 1597              * Compute the hash over the full absolute
 1598              * name. Look for the smallest suffix match at
 1599              * this tree level (hlevel), and then at every
 1600              * iteration, look for the next smallest suffix
 1601              * match (add another subdomain label to the
 1602              * absolute name being hashed).
 1603              */
 1604             dns_name_getlabelsequence(name,
 1605                           nlabels - tlabels,
 1606                           hlabels + tlabels,
 1607                           &hash_name);
 1608             hash = dns_name_fullhash(&hash_name, false);
 1609             dns_name_getlabelsequence(search_name,
 1610                           nlabels - tlabels,
 1611                           tlabels, &hash_name);
 1612 
 1613             /*
 1614              * Walk all the nodes in the hash bucket pointed
 1615              * by the computed hash value.
 1616              */
 1617             for (hnode = rbt->hashtable[hash % rbt->hashsize];
 1618                  hnode != NULL;
 1619                  hnode = hnode->hashnext)
 1620             {
 1621                 dns_name_t hnode_name;
 1622 
 1623                 if (ISC_LIKELY(hash != HASHVAL(hnode)))
 1624                     continue;
 1625                 /*
 1626                  * This checks that the hashed label
 1627                  * sequence being looked up is at the
 1628                  * same tree level, so that we don't
 1629                  * match a labelsequence from some other
 1630                  * subdomain.
 1631                  */
 1632                 if (ISC_LIKELY(get_upper_node(hnode) != up_current))
 1633                     continue;
 1634 
 1635                 dns_name_init(&hnode_name, NULL);
 1636                 NODENAME(hnode, &hnode_name);
 1637                 if (ISC_LIKELY(dns_name_equal(&hnode_name, &hash_name)))
 1638                     break;
 1639             }
 1640 
 1641             if (hnode != NULL) {
 1642                 current = hnode;
 1643                 /*
 1644                  * This is an optimization.  If hashing found
 1645                  * the right node, the next call to
 1646                  * dns_name_fullcompare() would obviously
 1647                  * return _equal or _subdomain.  Determine
 1648                  * which of those would be the case by
 1649                  * checking if the full name was hashed.  Then
 1650                  * make it look like dns_name_fullcompare
 1651                  * was called and jump to the right place.
 1652                  */
 1653                 if (tlabels == nlabels) {
 1654                     compared = dns_namereln_equal;
 1655                     break;
 1656                 } else {
 1657                     common_labels = tlabels;
 1658                     compared = dns_namereln_subdomain;
 1659                     goto subdomain;
 1660                 }
 1661             }
 1662 
 1663             if (tlabels++ < nlabels)
 1664                 goto hashagain;
 1665 
 1666             /*
 1667              * All of the labels have been tried against the hash
 1668              * table.  Since we dropped the support of bitstring
 1669              * labels, the name isn't in the table.
 1670              */
 1671             current = NULL;
 1672             continue;
 1673 
 1674 #else /* DNS_RBT_USEHASH */
 1675 
 1676             /*
 1677              * Standard binary search tree movement.
 1678              */
 1679             if (order < 0)
 1680                 current = LEFT(current);
 1681             else
 1682                 current = RIGHT(current);
 1683 
 1684 #endif /* DNS_RBT_USEHASH */
 1685 
 1686         } else {
 1687             /*
 1688              * The names have some common suffix labels.
 1689              *
 1690              * If the number in common are equal in length to
 1691              * the current node's name length, then follow the
 1692              * down pointer and search in the new tree.
 1693              */
 1694             if (compared == dns_namereln_subdomain) {
 1695 #ifdef DNS_RBT_USEHASH
 1696         subdomain:
 1697 #endif
 1698                 /*
 1699                  * Whack off the current node's common parts
 1700                  * for the name to search in the next level.
 1701                  */
 1702                 dns_name_split(search_name, common_labels,
 1703                            search_name, NULL);
 1704                 hlabels += common_labels;
 1705                 /*
 1706                  * This might be the closest enclosing name.
 1707                  */
 1708                 if (DATA(current) != NULL ||
 1709                     (options & DNS_RBTFIND_EMPTYDATA) != 0)
 1710                     *node = current;
 1711 
 1712                 /*
 1713                  * Point the chain to the next level.   This
 1714                  * needs to be done before 'current' is pointed
 1715                  * there because the callback in the next
 1716                  * block of code needs the current 'current',
 1717                  * but in the event the callback requests that
 1718                  * the search be stopped then the
 1719                  * DNS_R_PARTIALMATCH code at the end of this
 1720                  * function needs the chain pointed to the
 1721                  * next level.
 1722                  */
 1723                 ADD_LEVEL(chain, current);
 1724 
 1725                 /*
 1726                  * The caller may want to interrupt the
 1727                  * downward search when certain special nodes
 1728                  * are traversed.  If this is a special node,
 1729                  * the callback is used to learn what the
 1730                  * caller wants to do.
 1731                  */
 1732                 if (callback != NULL &&
 1733                     FINDCALLBACK(current)) {
 1734                     result = chain_name(chain,
 1735                                 callback_name,
 1736                                 false);
 1737                     if (result != ISC_R_SUCCESS) {
 1738                         dns_rbtnodechain_reset(chain);
 1739                         return (result);
 1740                     }
 1741 
 1742                     result = (callback)(current,
 1743                                 callback_name,
 1744                                 callback_arg);
 1745                     if (result != DNS_R_CONTINUE) {
 1746                         saved_result = result;
 1747                         /*
 1748                          * Treat this node as if it
 1749                          * had no down pointer.
 1750                          */
 1751                         current = NULL;
 1752                         break;
 1753                     }
 1754                 }
 1755 
 1756                 /*
 1757                  * Finally, head to the next tree level.
 1758                  */
 1759                 current = DOWN(current);
 1760             } else {
 1761                 /*
 1762                  * Though there are labels in common, the
 1763                  * entire name at this node is not common
 1764                  * with the search name so the search
 1765                  * name does not exist in the tree.
 1766                  */
 1767                 INSIST(compared == dns_namereln_commonancestor
 1768                        || compared == dns_namereln_contains);
 1769 
 1770                 current = NULL;
 1771             }
 1772         }
 1773     }
 1774 
 1775     /*
 1776      * If current is not NULL, NOEXACT is not disallowing exact matches,
 1777      * and either the node has data or an empty node is ok, return
 1778      * ISC_R_SUCCESS to indicate an exact match.
 1779      */
 1780     if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
 1781         (DATA(current) != NULL ||
 1782          (options & DNS_RBTFIND_EMPTYDATA) != 0)) {
 1783         /*
 1784          * Found an exact match.
 1785          */
 1786         chain->end = current;
 1787         chain->level_matches = chain->level_count;
 1788 
 1789         if (foundname != NULL)
 1790             result = chain_name(chain, foundname, true);
 1791         else
 1792             result = ISC_R_SUCCESS;
 1793 
 1794         if (result == ISC_R_SUCCESS) {
 1795             *node = current;
 1796             result = saved_result;
 1797         } else
 1798             *node = NULL;
 1799     } else {
 1800         /*
 1801          * Did not find an exact match (or did not want one).
 1802          */
 1803         if (*node != NULL) {
 1804             /*
 1805              * ... but found a partially matching superdomain.
 1806              * Unwind the chain to the partial match node
 1807              * to set level_matches to the level above the node,
 1808              * and then to derive the name.
 1809              *
 1810              * chain->level_count is guaranteed to be at least 1
 1811              * here because by definition of finding a superdomain,
 1812              * the chain is pointed to at least the first subtree.
 1813              */
 1814             chain->level_matches = chain->level_count - 1;
 1815 
 1816             while (chain->levels[chain->level_matches] != *node) {
 1817                 INSIST(chain->level_matches > 0);
 1818                 chain->level_matches--;
 1819             }
 1820 
 1821             if (foundname != NULL) {
 1822                 unsigned int saved_count = chain->level_count;
 1823 
 1824                 chain->level_count = chain->level_matches + 1;
 1825 
 1826                 result = chain_name(chain, foundname,
 1827                             false);
 1828 
 1829                 chain->level_count = saved_count;
 1830             } else
 1831                 result = ISC_R_SUCCESS;
 1832 
 1833             if (result == ISC_R_SUCCESS)
 1834                 result = DNS_R_PARTIALMATCH;
 1835 
 1836         } else
 1837             result = ISC_R_NOTFOUND;
 1838 
 1839         if (current != NULL) {
 1840             /*
 1841              * There was an exact match but either
 1842              * DNS_RBTFIND_NOEXACT was set, or
 1843              * DNS_RBTFIND_EMPTYDATA was set and the node had no
 1844              * data.  A policy decision was made to set the
 1845              * chain to the exact match, but this is subject
 1846              * to change if it becomes apparent that something
 1847              * else would be more useful.  It is important that
 1848              * this case is handled here, because the predecessor
 1849              * setting code below assumes the match was not exact.
 1850              */
 1851             INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
 1852                    ((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
 1853                 DATA(current) == NULL));
 1854             chain->end = current;
 1855 
 1856         } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
 1857             /*
 1858              * Ensure the chain points nowhere.
 1859              */
 1860             chain->end = NULL;
 1861 
 1862         } else {
 1863             /*
 1864              * Since there was no exact match, the chain argument
 1865              * needs to be pointed at the DNSSEC predecessor of
 1866              * the search name.
 1867              */
 1868             if (compared == dns_namereln_subdomain) {
 1869                 /*
 1870                  * Attempted to follow a down pointer that was
 1871                  * NULL, which means the searched for name was
 1872                  * a subdomain of a terminal name in the tree.
 1873                  * Since there are no existing subdomains to
 1874                  * order against, the terminal name is the
 1875                  * predecessor.
 1876                  */
 1877                 INSIST(chain->level_count > 0);
 1878                 INSIST(chain->level_matches <
 1879                        chain->level_count);
 1880                 chain->end =
 1881                     chain->levels[--chain->level_count];
 1882 
 1883             } else {
 1884                 isc_result_t result2;
 1885 
 1886                 /*
 1887                  * Point current to the node that stopped
 1888                  * the search.
 1889                  *
 1890                  * With the hashing modification that has been
 1891                  * added to the algorithm, the stop node of a
 1892                  * standard binary search is not known.  So it
 1893                  * has to be found.  There is probably a more
 1894                  * clever way of doing this.
 1895                  *
 1896                  * The assignment of current to NULL when
 1897                  * the relationship is *not* dns_namereln_none,
 1898                  * even though it later gets set to the same
 1899                  * last_compared anyway, is simply to not push
 1900                  * the while loop in one more level of
 1901                  * indentation.
 1902                  */
 1903                 if (compared == dns_namereln_none)
 1904                     current = last_compared;
 1905                 else
 1906                     current = NULL;
 1907 
 1908                 while (current != NULL) {
 1909                     NODENAME(current, &current_name);
 1910                     compared = dns_name_fullcompare(
 1911                                 search_name,
 1912                                 &current_name,
 1913                                 &order,
 1914                                 &common_labels);
 1915                     POST(compared);
 1916 
 1917                     last_compared = current;
 1918 
 1919                     /*
 1920                      * Standard binary search movement.
 1921                      */
 1922                     if (order < 0)
 1923                         current = LEFT(current);
 1924                     else
 1925                         current = RIGHT(current);
 1926 
 1927                 }
 1928 
 1929                 current = last_compared;
 1930 
 1931                 /*
 1932                  * Reached a point within a level tree that
 1933                  * positively indicates the name is not
 1934                  * present, but the stop node could be either
 1935                  * less than the desired name (order > 0) or
 1936                  * greater than the desired name (order < 0).
 1937                  *
 1938                  * If the stop node is less, it is not
 1939                  * necessarily the predecessor.  If the stop
 1940                  * node has a down pointer, then the real
 1941                  * predecessor is at the end of a level below
 1942                  * (not necessarily the next level).
 1943                  * Move down levels until the rightmost node
 1944                  * does not have a down pointer.
 1945                  *
 1946                  * When the stop node is greater, it is
 1947                  * the successor.  All the logic for finding
 1948                  * the predecessor is handily encapsulated
 1949                  * in dns_rbtnodechain_prev.  In the event
 1950                  * that the search name is less than anything
 1951                  * else in the tree, the chain is reset.
 1952                  * XXX DCL What is the best way for the caller
 1953                  *         to know that the search name has
 1954                  *         no predecessor?
 1955                  */
 1956 
 1957 
 1958                 if (order > 0) {
 1959                     if (DOWN(current) != NULL) {
 1960                         ADD_LEVEL(chain, current);
 1961 
 1962                         result2 =
 1963                               move_chain_to_last(chain,
 1964                                 DOWN(current));
 1965 
 1966                         if (result2 != ISC_R_SUCCESS)
 1967                             result = result2;
 1968                     } else
 1969                         /*
 1970                          * Ah, the pure and simple
 1971                          * case.  The stop node is the
 1972                          * predecessor.
 1973                          */
 1974                         chain->end = current;
 1975 
 1976                 } else {
 1977                     INSIST(order < 0);
 1978 
 1979                     chain->end = current;
 1980 
 1981                     result2 = dns_rbtnodechain_prev(chain,
 1982                                     NULL,
 1983                                     NULL);
 1984                     if (result2 == ISC_R_SUCCESS ||
 1985                         result2 == DNS_R_NEWORIGIN)
 1986                         ;       /* Nothing. */
 1987                     else if (result2 == ISC_R_NOMORE)
 1988                         /*
 1989                          * There is no predecessor.
 1990                          */
 1991                         dns_rbtnodechain_reset(chain);
 1992                     else
 1993                         result = result2;
 1994                 }
 1995 
 1996             }
 1997         }
 1998     }
 1999 
 2000     ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
 2001 
 2002     return (result);
 2003 }
 2004 
 2005 /*
 2006  * Get the data pointer associated with 'name'.
 2007  */
 2008 isc_result_t
 2009 dns_rbt_findname(dns_rbt_t *rbt, const dns_name_t *name, unsigned int options,
 2010          dns_name_t *foundname, void **data) {
 2011     dns_rbtnode_t *node = NULL;
 2012     isc_result_t result;
 2013 
 2014     REQUIRE(data != NULL && *data == NULL);
 2015 
 2016     result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
 2017                   options, NULL, NULL);
 2018 
 2019     if (node != NULL &&
 2020         (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
 2021         *data = DATA(node);
 2022     else
 2023         result = ISC_R_NOTFOUND;
 2024 
 2025     return (result);
 2026 }
 2027 
 2028 /*
 2029  * Delete a name from the tree of trees.
 2030  */
 2031 isc_result_t
 2032 dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, bool recurse) {
 2033     dns_rbtnode_t *node = NULL;
 2034     isc_result_t result;
 2035 
 2036     REQUIRE(VALID_RBT(rbt));
 2037     REQUIRE(dns_name_isabsolute(name));
 2038 
 2039     /*
 2040      * First, find the node.
 2041      *
 2042      * When searching, the name might not have an exact match:
 2043      * consider a.b.a.com, b.b.a.com and c.b.a.com as the only
 2044      * elements of a tree, which would make layer 1 a single
 2045      * node tree of "b.a.com" and layer 2 a three node tree of
 2046      * a, b, and c.  Deleting a.com would find only a partial depth
 2047      * match in the first layer.  Should it be a requirement that
 2048      * that the name to be deleted have data?  For now, it is.
 2049      *
 2050      * ->dirty, ->locknum and ->references are ignored; they are
 2051      * solely the province of rbtdb.c.
 2052      */
 2053     result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
 2054                   DNS_RBTFIND_NOOPTIONS, NULL, NULL);
 2055 
 2056     if (result == ISC_R_SUCCESS) {
 2057         if (DATA(node) != NULL)
 2058             result = dns_rbt_deletenode(rbt, node, recurse);
 2059         else
 2060             result = ISC_R_NOTFOUND;
 2061 
 2062     } else if (result == DNS_R_PARTIALMATCH)
 2063         result = ISC_R_NOTFOUND;
 2064 
 2065     return (result);
 2066 }
 2067 
 2068 /*
 2069  * Remove a node from the tree of trees.
 2070  *
 2071  * NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
 2072  * a sequence of additions to be deletions will not generally get the
 2073  * tree back to the state it started in.  For example, if the addition
 2074  * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
 2075  * then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
 2076  * restoring "a.b.c".  The RBT *used* to do this kind of rejoining, but it
 2077  * turned out to be a bad idea because it could corrupt an active nodechain
 2078  * that had "b.c" as one of its levels -- and the RBT has no idea what
 2079  * nodechains are in use by callers, so it can't even *try* to helpfully
 2080  * fix them up (which would probably be doomed to failure anyway).
 2081  *
 2082  * Similarly, it is possible to leave the tree in a state where a supposedly
 2083  * deleted node still exists.  The first case of this is obvious; take
 2084  * the tree which has "b.c" on one level, pointing to "a".  Now deleted "b.c".
 2085  * It was just established in the previous paragraph why we can't pull "a"
 2086  * back up to its parent level.  But what happens when "a" then gets deleted?
 2087  * "b.c" is left hanging around without data or children.  This condition
 2088  * is actually pretty easy to detect, but ... should it really be removed?
 2089  * Is a chain pointing to it?  An iterator?  Who knows!  (Note that the
 2090  * references structure member cannot be looked at because it is private to
 2091  * rbtdb.)  This is ugly and makes me unhappy, but after hours of trying to
 2092  * make it more aesthetically proper and getting nowhere, this is the way it
 2093  * is going to stay until such time as it proves to be a *real* problem.
 2094  *
 2095  * Finally, for reference, note that the original routine that did node
 2096  * joining was called join_nodes().  It has been excised, living now only
 2097  * in the CVS history, but comments have been left behind that point to it just
 2098  * in case someone wants to muck with this some more.
 2099  *
 2100  * The one positive aspect of all of this is that joining used to have a
 2101  * case where it might fail.  Without trying to join, now this function always
 2102  * succeeds. It still returns isc_result_t, though, so the API wouldn't change.
 2103  */
 2104 isc_result_t
 2105 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, bool recurse)
 2106 {
 2107     dns_rbtnode_t *parent;
 2108 
 2109     REQUIRE(VALID_RBT(rbt));
 2110     REQUIRE(DNS_RBTNODE_VALID(node));
 2111     INSIST(rbt->nodecount != 0);
 2112 
 2113     if (DOWN(node) != NULL) {
 2114         if (recurse) {
 2115             PARENT(DOWN(node)) = NULL;
 2116             deletetreeflat(rbt, 0, true, &DOWN(node));
 2117         } else {
 2118             if (DATA(node) != NULL && rbt->data_deleter != NULL)
 2119                 rbt->data_deleter(DATA(node), rbt->deleter_arg);
 2120             DATA(node) = NULL;
 2121 
 2122             /*
 2123              * Since there is at least one node below this one and
 2124              * no recursion was requested, the deletion is
 2125              * complete.  The down node from this node might be all
 2126              * by itself on a single level, so join_nodes() could
 2127              * be used to collapse the tree (with all the caveats
 2128              * of the comment at the start of this function).
 2129              * But join_nodes() function has now been removed.
 2130              */
 2131             return (ISC_R_SUCCESS);
 2132         }
 2133     }
 2134 
 2135     /*
 2136      * Note the node that points to the level of the node
 2137      * that is being deleted.  If the deleted node is the
 2138      * top level, parent will be set to NULL.
 2139      */
 2140     parent = get_upper_node(node);
 2141 
 2142     /*
 2143      * This node now has no down pointer, so now it needs
 2144      * to be removed from this level.
 2145      */
 2146     deletefromlevel(node, parent == NULL ? &rbt->root : &DOWN(parent));
 2147 
 2148     if (DATA(node) != NULL && rbt->data_deleter != NULL)
 2149         rbt->data_deleter(DATA(node), rbt->deleter_arg);
 2150 
 2151     unhash_node(rbt, node);
 2152 #if DNS_RBT_USEMAGIC
 2153     node->magic = 0;
 2154 #endif
 2155     dns_rbtnode_refdestroy(node);
 2156 
 2157     freenode(rbt, &node);
 2158 
 2159     /*
 2160      * This function never fails.
 2161      */
 2162     return (ISC_R_SUCCESS);
 2163 }
 2164 
 2165 void
 2166 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
 2167 
 2168     REQUIRE(DNS_RBTNODE_VALID(node));
 2169     REQUIRE(name != NULL);
 2170     REQUIRE(name->offsets == NULL);
 2171 
 2172     NODENAME(node, name);
 2173 }
 2174 
 2175 isc_result_t
 2176 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
 2177     dns_name_t current;
 2178     isc_result_t result;
 2179 
 2180     REQUIRE(DNS_RBTNODE_VALID(node));
 2181     REQUIRE(name != NULL);
 2182     REQUIRE(name->buffer != NULL);
 2183 
 2184     dns_name_init(&current, NULL);
 2185     dns_name_reset(name);
 2186 
 2187     do {
 2188         INSIST(node != NULL);
 2189 
 2190         NODENAME(node, &current);
 2191 
 2192         result = dns_name_concatenate(name, &current, name, NULL);
 2193         if (result != ISC_R_SUCCESS)
 2194             break;
 2195 
 2196         node = get_upper_node(node);
 2197     } while (! dns_name_isabsolute(name));
 2198 
 2199     return (result);
 2200 }
 2201 
 2202 char *
 2203 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
 2204 {
 2205     dns_fixedname_t fixedname;
 2206     dns_name_t *name;
 2207     isc_result_t result;
 2208 
 2209     REQUIRE(DNS_RBTNODE_VALID(node));
 2210     REQUIRE(printname != NULL);
 2211 
 2212     name = dns_fixedname_initname(&fixedname);
 2213     result = dns_rbt_fullnamefromnode(node, name);
 2214     if (result == ISC_R_SUCCESS)
 2215         dns_name_format(name, printname, size);
 2216     else
 2217         snprintf(printname, size, "<error building name: %s>",
 2218              dns_result_totext(result));
 2219 
 2220     return (printname);
 2221 }
 2222 
 2223 static isc_result_t
 2224 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep) {
 2225     dns_rbtnode_t *node;
 2226     isc_region_t region;
 2227     unsigned int labels;
 2228     size_t nodelen;
 2229 
 2230     REQUIRE(name->offsets != NULL);
 2231 
 2232     dns_name_toregion(name, &region);
 2233     labels = dns_name_countlabels(name);
 2234     ENSURE(labels > 0);
 2235 
 2236     /*
 2237      * Allocate space for the node structure, the name, and the offsets.
 2238      */
 2239     nodelen = sizeof(dns_rbtnode_t) + region.length + labels + 1;
 2240     node = (dns_rbtnode_t *)isc_mem_get(mctx, nodelen);
 2241     if (node == NULL)
 2242         return (ISC_R_NOMEMORY);
 2243     memset(node, 0, nodelen);
 2244 
 2245     node->is_root = 0;
 2246     PARENT(node) = NULL;
 2247     RIGHT(node) = NULL;
 2248     LEFT(node) = NULL;
 2249     DOWN(node) = NULL;
 2250     DATA(node) = NULL;
 2251     node->is_mmapped = 0;
 2252     node->down_is_relative = 0;
 2253     node->left_is_relative = 0;
 2254     node->right_is_relative = 0;
 2255     node->parent_is_relative = 0;
 2256     node->data_is_relative = 0;
 2257     node->rpz = 0;
 2258 
 2259 #ifdef DNS_RBT_USEHASH
 2260     HASHNEXT(node) = NULL;
 2261     HASHVAL(node) = 0;
 2262 #endif
 2263 
 2264     ISC_LINK_INIT(node, deadlink);
 2265 
 2266     LOCKNUM(node) = 0;
 2267     WILD(node) = 0;
 2268     DIRTY(node) = 0;
 2269     dns_rbtnode_refinit(node, 0);
 2270     node->find_callback = 0;
 2271     node->nsec = DNS_RBT_NSEC_NORMAL;
 2272 
 2273     MAKE_BLACK(node);
 2274 
 2275     /*
 2276      * The following is stored to make reconstructing a name from the
 2277      * stored value in the node easy:  the length of the name, the number
 2278      * of labels, whether the name is absolute or not, the name itself,
 2279      * and the name's offsets table.
 2280      *
 2281      * XXX RTH
 2282      *      The offsets table could be made smaller by eliminating the
 2283      *      first offset, which is always 0.  This requires changes to
 2284      *      lib/dns/name.c.
 2285      *
 2286      * Note: OLDOFFSETLEN *must* be assigned *after* OLDNAMELEN is assigned
 2287      *   as it uses OLDNAMELEN.
 2288      */
 2289     OLDNAMELEN(node) = NAMELEN(node) = region.length;
 2290     OLDOFFSETLEN(node) = OFFSETLEN(node) = labels;
 2291     ATTRS(node) = name->attributes;
 2292 
 2293     memmove(NAME(node), region.base, region.length);
 2294     memmove(OFFSETS(node), name->offsets, labels);
 2295 
 2296 #if DNS_RBT_USEMAGIC
 2297     node->magic = DNS_RBTNODE_MAGIC;
 2298 #endif
 2299     *nodep = node;
 2300 
 2301     return (ISC_R_SUCCESS);
 2302 }
 2303 
 2304 #ifdef DNS_RBT_USEHASH
 2305 static inline void
 2306 hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
 2307     unsigned int hash;
 2308 
 2309     REQUIRE(name != NULL);
 2310 
 2311     HASHVAL(node) = dns_name_fullhash(name, false);
 2312 
 2313     hash = HASHVAL(node) % rbt->hashsize;
 2314     HASHNEXT(node) = rbt->hashtable[hash];
 2315 
 2316     rbt->hashtable[hash] = node;
 2317 }
 2318 
 2319 static isc_result_t
 2320 inithash(dns_rbt_t *rbt) {
 2321     unsigned int bytes;
 2322 
 2323     rbt->hashsize = RBT_HASH_SIZE;
 2324     bytes = (unsigned int)rbt->hashsize * sizeof(dns_rbtnode_t *);
 2325     rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
 2326 
 2327     if (rbt->hashtable == NULL)
 2328         return (ISC_R_NOMEMORY);
 2329 
 2330     memset(rbt->hashtable, 0, bytes);
 2331 
 2332     return (ISC_R_SUCCESS);
 2333 }
 2334 
 2335 static void
 2336 rehash(dns_rbt_t *rbt, unsigned int newcount) {
 2337     unsigned int oldsize;
 2338     dns_rbtnode_t **oldtable;
 2339     dns_rbtnode_t *node;
 2340     dns_rbtnode_t *nextnode;
 2341     unsigned int hash;
 2342     unsigned int i;
 2343 
 2344     oldsize = (unsigned int)rbt->hashsize;
 2345     oldtable = rbt->hashtable;
 2346     do {
 2347         INSIST((rbt->hashsize * 2 + 1) > rbt->hashsize);
 2348         rbt->hashsize = rbt->hashsize * 2 + 1;
 2349     } while (newcount >= (rbt->hashsize * 3));
 2350     rbt->hashtable = isc_mem_get(rbt->mctx,
 2351                      rbt->hashsize * sizeof(dns_rbtnode_t *));
 2352     if (rbt->hashtable == NULL) {
 2353         rbt->hashtable = oldtable;
 2354         rbt->hashsize = oldsize;
 2355         return;
 2356     }
 2357 
 2358     for (i = 0; i < rbt->hashsize; i++)
 2359         rbt->hashtable[i] = NULL;
 2360 
 2361     for (i = 0; i < oldsize; i++) {
 2362         for (node = oldtable[i]; node != NULL; node = nextnode) {
 2363             hash = HASHVAL(node) % rbt->hashsize;
 2364             nextnode = HASHNEXT(node);
 2365             HASHNEXT(node) = rbt->hashtable[hash];
 2366             rbt->hashtable[hash] = node;
 2367         }
 2368     }
 2369 
 2370     isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
 2371 }
 2372 
 2373 static inline void
 2374 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
 2375     REQUIRE(DNS_RBTNODE_VALID(node));
 2376 
 2377     if (rbt->nodecount >= (rbt->hashsize * 3))
 2378         rehash(rbt, rbt->nodecount);
 2379 
 2380     hash_add_node(rbt, node, name);
 2381 }
 2382 
 2383 static inline void
 2384 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
 2385     unsigned int bucket;
 2386     dns_rbtnode_t *bucket_node;
 2387 
 2388     REQUIRE(DNS_RBTNODE_VALID(node));
 2389 
 2390     bucket = HASHVAL(node) % rbt->hashsize;
 2391     bucket_node = rbt->hashtable[bucket];
 2392 
 2393     if (bucket_node == node) {
 2394         rbt->hashtable[bucket] = HASHNEXT(node);
 2395     } else {
 2396         while (HASHNEXT(bucket_node) != node) {
 2397             INSIST(HASHNEXT(bucket_node) != NULL);
 2398             bucket_node = HASHNEXT(bucket_node);
 2399         }
 2400         HASHNEXT(bucket_node) = HASHNEXT(node);
 2401     }
 2402 }
 2403 #endif /* DNS_RBT_USEHASH */
 2404 
 2405 static inline void
 2406 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
 2407     dns_rbtnode_t *child;
 2408 
 2409     REQUIRE(DNS_RBTNODE_VALID(node));
 2410     REQUIRE(rootp != NULL);
 2411 
 2412     child = RIGHT(node);
 2413     INSIST(child != NULL);
 2414 
 2415     RIGHT(node) = LEFT(child);
 2416     if (LEFT(child) != NULL)
 2417         PARENT(LEFT(child)) = node;
 2418     LEFT(child) = node;
 2419 
 2420     PARENT(child) = PARENT(node);
 2421 
 2422     if (IS_ROOT(node)) {
 2423         *rootp = child;
 2424         child->is_root = 1;
 2425         node->is_root = 0;
 2426 
 2427     } else {
 2428         if (LEFT(PARENT(node)) == node)
 2429             LEFT(PARENT(node)) = child;
 2430         else
 2431             RIGHT(PARENT(node)) = child;
 2432     }
 2433 
 2434     PARENT(node) = child;
 2435 }
 2436 
 2437 static inline void
 2438 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
 2439     dns_rbtnode_t *child;
 2440 
 2441     REQUIRE(DNS_RBTNODE_VALID(node));
 2442     REQUIRE(rootp != NULL);
 2443 
 2444     child = LEFT(node);
 2445     INSIST(child != NULL);
 2446 
 2447     LEFT(node) = RIGHT(child);
 2448     if (RIGHT(child) != NULL)
 2449         PARENT(RIGHT(child)) = node;
 2450     RIGHT(child) = node;
 2451 
 2452     PARENT(child) = PARENT(node);
 2453 
 2454     if (IS_ROOT(node)) {
 2455         *rootp = child;
 2456         child->is_root = 1;
 2457         node->is_root = 0;
 2458 
 2459     } else {
 2460         if (LEFT(PARENT(node)) == node)
 2461             LEFT(PARENT(node)) = child;
 2462         else
 2463             RIGHT(PARENT(node)) = child;
 2464     }
 2465 
 2466     PARENT(node) = child;
 2467 }
 2468 
 2469 /*
 2470  * This is the real workhorse of the insertion code, because it does the
 2471  * true red/black tree on a single level.
 2472  */
 2473 static void
 2474 addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
 2475        dns_rbtnode_t **rootp)
 2476 {
 2477     dns_rbtnode_t *child, *root, *parent, *grandparent;
 2478     dns_name_t add_name, current_name;
 2479     dns_offsets_t add_offsets, current_offsets;
 2480 
 2481     REQUIRE(rootp != NULL);
 2482     REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
 2483         RIGHT(node) == NULL);
 2484     REQUIRE(current != NULL);
 2485 
 2486     root = *rootp;
 2487     if (root == NULL) {
 2488         /*
 2489          * First node of a level.
 2490          */
 2491         MAKE_BLACK(node);
 2492         node->is_root = 1;
 2493         PARENT(node) = current;
 2494         *rootp = node;
 2495         return;
 2496     }
 2497 
 2498     child = root;
 2499     POST(child);
 2500 
 2501     dns_name_init(&add_name, add_offsets);
 2502     NODENAME(node, &add_name);
 2503 
 2504     dns_name_init(&current_name, current_offsets);
 2505     NODENAME(current, &current_name);
 2506 
 2507     if (order < 0) {
 2508         INSIST(LEFT(current) == NULL);
 2509         LEFT(current) = node;
 2510     } else {
 2511         INSIST(RIGHT(current) == NULL);
 2512         RIGHT(current) = node;
 2513     }
 2514 
 2515     INSIST(PARENT(node) == NULL);
 2516     PARENT(node) = current;
 2517 
 2518     MAKE_RED(node);
 2519 
 2520     while (node != root && IS_RED(PARENT(node))) {
 2521         /*
 2522          * XXXDCL could do away with separate parent and grandparent
 2523          * variables.  They are vestiges of the days before parent
 2524          * pointers.  However, they make the code a little clearer.
 2525          */
 2526 
 2527         parent = PARENT(node);
 2528         grandparent = PARENT(parent);
 2529 
 2530         if (parent == LEFT(grandparent)) {
 2531             child = RIGHT(grandparent);
 2532             if (child != NULL && IS_RED(child)) {
 2533                 MAKE_BLACK(parent);
 2534                 MAKE_BLACK(child);
 2535                 MAKE_RED(grandparent);
 2536                 node = grandparent;
 2537             } else {
 2538                 if (node == RIGHT(parent)) {
 2539                     rotate_left(parent, &root);
 2540                     node = parent;
 2541                     parent = PARENT(node);
 2542                     grandparent = PARENT(parent);
 2543                 }
 2544                 MAKE_BLACK(parent);
 2545                 MAKE_RED(grandparent);
 2546                 rotate_right(grandparent, &root);
 2547             }
 2548         } else {
 2549             child = LEFT(grandparent);
 2550             if (child != NULL && IS_RED(child)) {
 2551                 MAKE_BLACK(parent);
 2552                 MAKE_BLACK(child);
 2553                 MAKE_RED(grandparent);
 2554                 node = grandparent;
 2555             } else {
 2556                 if (node == LEFT(parent)) {
 2557                     rotate_right(parent, &root);
 2558                     node = parent;
 2559                     parent = PARENT(node);
 2560                     grandparent = PARENT(parent);
 2561                 }
 2562                 MAKE_BLACK(parent);
 2563                 MAKE_RED(grandparent);
 2564                 rotate_left(grandparent, &root);
 2565             }
 2566         }
 2567     }
 2568 
 2569     MAKE_BLACK(root);
 2570     ENSURE(IS_ROOT(root));
 2571     *rootp = root;
 2572 
 2573     return;
 2574 }
 2575 
 2576 /*
 2577  * This is the real workhorse of the deletion code, because it does the
 2578  * true red/black tree on a single level.
 2579  */
 2580 static void
 2581 deletefromlevel(dns_rbtnode_t *item, dns_rbtnode_t **rootp) {
 2582     dns_rbtnode_t *child, *sibling, *parent;
 2583     dns_rbtnode_t *successor;
 2584 
 2585     REQUIRE(item != NULL);
 2586 
 2587     /*
 2588      * Verify that the parent history is (apparently) correct.
 2589      */
 2590     INSIST((IS_ROOT(item) && *rootp == item) ||
 2591            (! IS_ROOT(item) &&
 2592         (LEFT(PARENT(item)) == item ||
 2593          RIGHT(PARENT(item)) == item)));
 2594 
 2595     child = NULL;
 2596 
 2597     if (LEFT(item) == NULL) {
 2598         if (RIGHT(item) == NULL) {
 2599             if (IS_ROOT(item)) {
 2600                 /*
 2601                  * This is the only item in the tree.
 2602                  */
 2603                 *rootp = NULL;
 2604                 return;
 2605             }
 2606         } else
 2607             /*
 2608              * This node has one child, on the right.
 2609              */
 2610             child = RIGHT(item);
 2611 
 2612     } else if (RIGHT(item) == NULL)
 2613         /*
 2614          * This node has one child, on the left.
 2615          */
 2616         child = LEFT(item);
 2617     else {
 2618         dns_rbtnode_t holder, *tmp = &holder;
 2619 
 2620         /*
 2621          * This node has two children, so it cannot be directly
 2622          * deleted.  Find its immediate in-order successor and
 2623          * move it to this location, then do the deletion at the
 2624          * old site of the successor.
 2625          */
 2626         successor = RIGHT(item);
 2627         while (LEFT(successor) != NULL)
 2628             successor = LEFT(successor);
 2629 
 2630         /*
 2631          * The successor cannot possibly have a left child;
 2632          * if there is any child, it is on the right.
 2633          */
 2634         if (RIGHT(successor) != NULL)
 2635             child = RIGHT(successor);
 2636 
 2637         /*
 2638          * Swap the two nodes; it would be simpler to just replace
 2639          * the value being deleted with that of the successor,
 2640          * but this rigamarole is done so the caller has complete
 2641          * control over the pointers (and memory allocation) of
 2642          * all of nodes.  If just the key value were removed from
 2643          * the tree, the pointer to the node would be unchanged.
 2644          */
 2645 
 2646         /*
 2647          * First, put the successor in the tree location of the
 2648          * node to be deleted.  Save its existing tree pointer
 2649          * information, which will be needed when linking up
 2650          * delete to the successor's old location.
 2651          */
 2652         memmove(tmp, successor, sizeof(dns_rbtnode_t));
 2653 
 2654         if (IS_ROOT(item)) {
 2655             *rootp = successor;
 2656             successor->is_root = true;
 2657             item->is_root = false;
 2658 
 2659         } else
 2660             if (LEFT(PARENT(item)) == item)
 2661                 LEFT(PARENT(item)) = successor;
 2662             else
 2663                 RIGHT(PARENT(item)) = successor;
 2664 
 2665         PARENT(successor) = PARENT(item);
 2666         LEFT(successor)   = LEFT(item);
 2667         RIGHT(successor)  = RIGHT(item);
 2668         COLOR(successor)  = COLOR(item);
 2669 
 2670         if (LEFT(successor) != NULL)
 2671             PARENT(LEFT(successor)) = successor;
 2672         if (RIGHT(successor) != successor)
 2673             PARENT(RIGHT(successor)) = successor;
 2674 
 2675         /*
 2676          * Now relink the node to be deleted into the
 2677          * successor's previous tree location.  PARENT(tmp)
 2678          * is the successor's original parent.
 2679          */
 2680         INSIST(! IS_ROOT(item));
 2681 
 2682         if (PARENT(tmp) == item) {
 2683             /*
 2684              * Node being deleted was successor's parent.
 2685              */
 2686             RIGHT(successor) = item;
 2687             PARENT(item) = successor;
 2688 
 2689         } else {
 2690             LEFT(PARENT(tmp)) = item;
 2691             PARENT(item) = PARENT(tmp);
 2692         }
 2693 
 2694         /*
 2695          * Original location of successor node has no left.
 2696          */
 2697         LEFT(item)   = NULL;
 2698         RIGHT(item)  = RIGHT(tmp);
 2699         COLOR(item)  = COLOR(tmp);
 2700     }
 2701 
 2702     /*
 2703      * Remove the node by removing the links from its parent.
 2704      */
 2705     if (! IS_ROOT(item)) {
 2706         if (LEFT(PARENT(item)) == item)
 2707             LEFT(PARENT(item)) = child;
 2708         else
 2709             RIGHT(PARENT(item)) = child;
 2710 
 2711         if (child != NULL)
 2712             PARENT(child) = PARENT(item);
 2713 
 2714     } else {
 2715         /*
 2716          * This is the root being deleted, and at this point
 2717          * it is known to have just one child.
 2718          */
 2719         *rootp = child;
 2720         child->is_root = 1;
 2721         PARENT(child) = PARENT(item);
 2722     }
 2723 
 2724     /*
 2725      * Fix color violations.
 2726      */
 2727     if (IS_BLACK(item)) {
 2728         /* cppcheck-suppress nullPointerRedundantCheck symbolName=item */
 2729         parent = PARENT(item);
 2730 
 2731         while (child != *rootp && IS_BLACK(child)) {
 2732             INSIST(child == NULL || ! IS_ROOT(child));
 2733 
 2734             if (LEFT(parent) == child) {
 2735                 sibling = RIGHT(parent);
 2736 
 2737                 if (IS_RED(sibling)) {
 2738                     MAKE_BLACK(sibling);
 2739                     MAKE_RED(parent);
 2740                     rotate_left(parent, rootp);
 2741                     sibling = RIGHT(parent);
 2742                 }
 2743 
 2744                 INSIST(sibling != NULL);
 2745 
 2746                 /* cppcheck-suppress nullPointerRedundantCheck symbolName=sibling */
 2747                 if (IS_BLACK(LEFT(sibling)) &&
 2748                     IS_BLACK(RIGHT(sibling))) {
 2749                     MAKE_RED(sibling);
 2750                     child = parent;
 2751 
 2752                 } else {
 2753 
 2754                     if (IS_BLACK(RIGHT(sibling))) {
 2755                         MAKE_BLACK(LEFT(sibling));
 2756                         MAKE_RED(sibling);
 2757                         rotate_right(sibling, rootp);
 2758                         sibling = RIGHT(parent);
 2759                     }
 2760 
 2761                     COLOR(sibling) = COLOR(parent);
 2762                     MAKE_BLACK(parent);
 2763                     INSIST(RIGHT(sibling) != NULL);
 2764                     MAKE_BLACK(RIGHT(sibling));
 2765                     rotate_left(parent, rootp);
 2766                     child = *rootp;
 2767                 }
 2768 
 2769             } else {
 2770                 /*
 2771                  * Child is parent's right child.
 2772                  * Everything is done the same as above,
 2773                  * except mirrored.
 2774                  */
 2775                 sibling = LEFT(parent);
 2776 
 2777                 if (IS_RED(sibling)) {
 2778                     MAKE_BLACK(sibling);
 2779                     MAKE_RED(parent);
 2780                     rotate_right(parent, rootp);
 2781                     sibling = LEFT(parent);
 2782                 }
 2783 
 2784                 INSIST(sibling != NULL);
 2785 
 2786                 /* cppcheck-suppress nullPointerRedundantCheck symbolName=sibling */
 2787                 if (IS_BLACK(LEFT(sibling)) &&
 2788                     IS_BLACK(RIGHT(sibling))) {
 2789                     MAKE_RED(sibling);
 2790                     child = parent;
 2791 
 2792                 } else {
 2793                     if (IS_BLACK(LEFT(sibling))) {
 2794                         MAKE_BLACK(RIGHT(sibling));
 2795                         MAKE_RED(sibling);
 2796                         rotate_left(sibling, rootp);
 2797                         sibling = LEFT(parent);
 2798                     }
 2799 
 2800                     COLOR(sibling) = COLOR(parent);
 2801                     MAKE_BLACK(parent);
 2802                     INSIST(LEFT(sibling) != NULL);
 2803                     MAKE_BLACK(LEFT(sibling));
 2804                     rotate_right(parent, rootp);
 2805                     child = *rootp;
 2806                 }
 2807             }
 2808 
 2809             parent = PARENT(child);
 2810         }
 2811 
 2812         if (IS_RED(child))
 2813             MAKE_BLACK(child);
 2814     }
 2815 }
 2816 
 2817 static void
 2818 freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep) {
 2819     dns_rbtnode_t *node = *nodep;
 2820 
 2821     if (node->is_mmapped == 0) {
 2822         isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
 2823     }
 2824     *nodep = NULL;
 2825 
 2826     rbt->nodecount--;
 2827 }
 2828 
 2829 static void
 2830 deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, bool unhash,
 2831            dns_rbtnode_t **nodep)
 2832 {
 2833     dns_rbtnode_t *root = *nodep;
 2834 
 2835     while (root != NULL) {
 2836         /*
 2837          * If there is a left, right or down node, walk into it
 2838          * and iterate.
 2839          */
 2840         if (LEFT(root) != NULL) {
 2841             dns_rbtnode_t *node = root;
 2842             root = LEFT(root);
 2843             LEFT(node) = NULL;
 2844         } else if (RIGHT(root) != NULL) {
 2845             dns_rbtnode_t *node = root;
 2846             root = RIGHT(root);
 2847             RIGHT(node) = NULL;
 2848         } else if (DOWN(root) != NULL) {
 2849             dns_rbtnode_t *node = root;
 2850             root = DOWN(root);
 2851             DOWN(node) = NULL;
 2852         } else {
 2853             /*
 2854              * There are no left, right or down nodes, so we
 2855              * can free this one and go back to its parent.
 2856              */
 2857             dns_rbtnode_t *node = root;
 2858             root = PARENT(root);
 2859 
 2860             if (DATA(node) != NULL && rbt->data_deleter != NULL)
 2861                 rbt->data_deleter(DATA(node),
 2862                           rbt->deleter_arg);
 2863             if (unhash)
 2864                 unhash_node(rbt, node);
 2865             /*
 2866              * Note: we don't call unhash_node() here as we
 2867              * are destroying the complete RBT tree.
 2868              */
 2869 #if DNS_RBT_USEMAGIC
 2870             node->magic = 0;
 2871 #endif
 2872             freenode(rbt, &node);
 2873             if (quantum != 0 && --quantum == 0)
 2874                 break;
 2875         }
 2876     }
 2877 
 2878     *nodep = root;
 2879 }
 2880 
 2881 static size_t
 2882 getheight_helper(dns_rbtnode_t *node) {
 2883     size_t dl, dr;
 2884     size_t this_height, down_height;
 2885 
 2886     if (node == NULL)
 2887         return (0);
 2888 
 2889     dl = getheight_helper(LEFT(node));
 2890     dr = getheight_helper(RIGHT(node));
 2891 
 2892     this_height = ISC_MAX(dl + 1, dr + 1);
 2893     down_height = getheight_helper(DOWN(node));
 2894 
 2895     return (ISC_MAX(this_height, down_height));
 2896 }
 2897 
 2898 size_t
 2899 dns__rbt_getheight(dns_rbt_t *rbt) {
 2900     return (getheight_helper(rbt->root));
 2901 }
 2902 
 2903 static bool
 2904 check_properties_helper(dns_rbtnode_t *node) {
 2905     if (node == NULL)
 2906         return (true);
 2907 
 2908     if (IS_RED(node)) {
 2909         /* Root nodes must be BLACK. */
 2910         if (IS_ROOT(node))
 2911             return (false);
 2912 
 2913         /* Both children of RED nodes must be BLACK. */
 2914         if (IS_RED(LEFT(node)) || IS_RED(RIGHT(node)))
 2915             return (false);
 2916     }
 2917 
 2918     /* cppcheck-suppress nullPointerRedundantCheck symbolName=node */
 2919     if ((DOWN(node) != NULL) && (!IS_ROOT(DOWN(node))))
 2920         return (false);
 2921 
 2922     if (IS_ROOT(node)) {
 2923         if ((PARENT(node) != NULL) &&
 2924             (DOWN(PARENT(node)) != node))
 2925             return (false);
 2926 
 2927         if (get_upper_node(node) != PARENT(node))
 2928             return (false);
 2929     }
 2930 
 2931     /* If node is assigned to the down_ pointer of its parent, it is
 2932      * a subtree root and must have the flag set.
 2933      */
 2934     if (((!PARENT(node)) ||
 2935          (DOWN(PARENT(node)) == node)) &&
 2936         (!IS_ROOT(node)))
 2937     {
 2938         return (false);
 2939     }
 2940 
 2941     /* Repeat tests with this node's children. */
 2942     return (check_properties_helper(LEFT(node)) &&
 2943         check_properties_helper(RIGHT(node)) &&
 2944         check_properties_helper(DOWN(node)));
 2945 }
 2946 
 2947 static bool
 2948 check_black_distance_helper(dns_rbtnode_t *node, size_t *distance) {
 2949     size_t dl, dr, dd;
 2950 
 2951     if (node == NULL) {
 2952         *distance = 1;
 2953         return (true);
 2954     }
 2955 
 2956     /* cppcheck-suppress nullPointerRedundantCheck symbolName=node */
 2957     if (!check_black_distance_helper(LEFT(node), &dl))
 2958         return (false);
 2959 
 2960     /* cppcheck-suppress nullPointerRedundantCheck symbolName=node */
 2961     if (!check_black_distance_helper(RIGHT(node), &dr))
 2962         return (false);
 2963 
 2964     /* cppcheck-suppress nullPointerRedundantCheck symbolName=node */
 2965     if (!check_black_distance_helper(DOWN(node), &dd))
 2966         return (false);
 2967 
 2968     /* Left and right side black node counts must match. */
 2969     if (dl != dr)
 2970         return (false);
 2971 
 2972     if (IS_BLACK(node))
 2973         dl++;
 2974 
 2975     *distance = dl;
 2976 
 2977     return (true);
 2978 }
 2979 
 2980 bool
 2981 dns__rbt_checkproperties(dns_rbt_t *rbt) {
 2982     size_t dd;
 2983 
 2984     if (!check_properties_helper(rbt->root))
 2985         return (false);
 2986 
 2987     /* Path from a given node to all its leaves must contain the
 2988      * same number of BLACK child nodes. This is done separately
 2989      * here instead of inside check_properties_helper() as
 2990      * it would take (n log n) complexity otherwise.
 2991      */
 2992     return (check_black_distance_helper(rbt->root, &dd));
 2993 }
 2994 
 2995 static void
 2996 dns_rbt_indent(FILE *f, int depth) {
 2997     int i;
 2998 
 2999     fprintf(f, "%4d ", depth);
 3000 
 3001     for (i = 0; i < depth; i++)
 3002         fprintf(f, "- ");
 3003 }
 3004 
 3005 void
 3006 dns_rbt_printnodeinfo(dns_rbtnode_t *n, FILE *f) {
 3007 
 3008     if (n == NULL) {
 3009         fprintf(f, "Null node\n");
 3010         return;
 3011     }
 3012 
 3013     fprintf(f, "Node info for nodename: ");
 3014     printnodename(n, true, f);
 3015     fprintf(f, "\n");
 3016 
 3017     fprintf(f, "n = %p\n", n);
 3018 
 3019     fprintf(f, "Relative pointers: %s%s%s%s%s\n",
 3020             (n->parent_is_relative == 1 ? " P" : ""),
 3021             (n->right_is_relative == 1 ? " R" : ""),
 3022             (n->left_is_relative == 1 ? " L" : ""),
 3023             (n->down_is_relative == 1 ? " D" : ""),
 3024             (n->data_is_relative == 1 ? " T" : ""));
 3025 
 3026     fprintf(f, "node lock address = %u\n", n->locknum);
 3027 
 3028     fprintf(f, "Parent: %p\n", n->parent);
 3029     fprintf(f, "Right: %p\n", n->right);
 3030     fprintf(f, "Left: %p\n", n->left);
 3031     fprintf(f, "Down: %p\n", n->down);
 3032     fprintf(f, "Data: %p\n", n->data);
 3033 }
 3034 
 3035 static void
 3036 printnodename(dns_rbtnode_t *node, bool quoted, FILE *f) {
 3037     isc_region_t r;
 3038     dns_name_t name;
 3039     char buffer[DNS_NAME_FORMATSIZE];
 3040     dns_offsets_t offsets;
 3041 
 3042     r.length = NAMELEN(node);
 3043     r.base = NAME(node);
 3044 
 3045     dns_name_init(&name, offsets);
 3046     dns_name_fromregion(&name, &r);
 3047 
 3048     dns_name_format(&name, buffer, sizeof(buffer));
 3049 
 3050     if (quoted)
 3051         fprintf(f, "\"%s\"", buffer);
 3052     else
 3053         fprintf(f, "%s", buffer);
 3054 }
 3055 
 3056 static void
 3057 print_text_helper(dns_rbtnode_t *root, dns_rbtnode_t *parent,
 3058           int depth, const char *direction,
 3059           void (*data_printer)(FILE *, void *), FILE *f)
 3060 {
 3061     dns_rbt_indent(f, depth);
 3062 
 3063     if (root != NULL) {
 3064         printnodename(root, true, f);
 3065         /*
 3066          * Don't use IS_RED(root) as it tests for 'root != NULL'
 3067          * and cppcheck produces false positives.
 3068          */
 3069         fprintf(f, " (%s, %s", direction,
 3070             COLOR(root) == RED ? "RED" : "BLACK");
 3071 
 3072         if ((! IS_ROOT(root) && PARENT(root) != parent) ||
 3073             (  IS_ROOT(root) && depth > 0 &&
 3074                DOWN(PARENT(root)) != root)) {
 3075 
 3076             fprintf(f, " (BAD parent pointer! -> ");
 3077             if (PARENT(root) != NULL)
 3078                 printnodename(PARENT(root), true, f);
 3079             else
 3080                 fprintf(f, "NULL");
 3081             fprintf(f, ")");
 3082         }
 3083 
 3084         fprintf(f, ")");
 3085 
 3086         if (root->data != NULL && data_printer != NULL) {
 3087             fprintf(f, " data@%p: ", root->data);
 3088             data_printer(f, root->data);
 3089         }
 3090         fprintf(f, "\n");
 3091 
 3092         depth++;
 3093 
 3094         /*
 3095          * Don't use IS_RED(root) as it tests for 'root != NULL'
 3096          * and cppcheck produces false positives.
 3097          */
 3098         if (COLOR(root) == RED && IS_RED(LEFT(root))) {
 3099             fprintf(f, "** Red/Red color violation on left\n");
 3100         }
 3101         print_text_helper(LEFT(root), root, depth, "left",
 3102                       data_printer, f);
 3103 
 3104         /*
 3105          * Don't use IS_RED(root) as cppcheck produces false positives.
 3106          */
 3107         if (COLOR(root) == RED && IS_RED(RIGHT(root))) {
 3108             fprintf(f, "** Red/Red color violation on right\n");
 3109         }
 3110         print_text_helper(RIGHT(root), root, depth, "right",
 3111                       data_printer, f);
 3112 
 3113         print_text_helper(DOWN(root), NULL, depth, "down",
 3114                       data_printer, f);
 3115     } else {
 3116         fprintf(f, "NULL (%s)\n", direction);
 3117     }
 3118 }
 3119 
 3120 void
 3121 dns_rbt_printtext(dns_rbt_t *rbt,
 3122           void (*data_printer)(FILE *, void *), FILE *f)
 3123 {
 3124     REQUIRE(VALID_RBT(rbt));
 3125 
 3126     print_text_helper(rbt->root, NULL, 0, "root", data_printer, f);
 3127 }
 3128 
 3129 static int
 3130 print_dot_helper(dns_rbtnode_t *node, unsigned int *nodecount,
 3131          bool show_pointers, FILE *f)
 3132 {
 3133     unsigned int l, r, d;
 3134 
 3135     if (node == NULL)
 3136         return (0);
 3137 
 3138     l = print_dot_helper(LEFT(node), nodecount, show_pointers, f);
 3139     r = print_dot_helper(RIGHT(node), nodecount, show_pointers, f);
 3140     d = print_dot_helper(DOWN(node), nodecount, show_pointers, f);
 3141 
 3142     *nodecount += 1;
 3143 
 3144     fprintf(f, "node%u[label = \"<f0> |<f1> ", *nodecount);
 3145     printnodename(node, false, f);
 3146     fprintf(f, "|<f2>");
 3147 
 3148     if (show_pointers)
 3149         fprintf(f, "|<f3> n=%p|<f4> p=%p", node, PARENT(node));
 3150 
 3151     fprintf(f, "\"] [");
 3152 
 3153     if (IS_RED(node))
 3154         fprintf(f, "color=red");
 3155     else
 3156         fprintf(f, "color=black");
 3157 
 3158     /* XXXMUKS: verify that IS_ROOT() indicates subtree root and not
 3159      * forest root.
 3160      */
 3161     if (IS_ROOT(node))
 3162         fprintf(f, ",penwidth=3");
 3163 
 3164     if (IS_EMPTY(node))
 3165         fprintf(f, ",style=filled,fillcolor=lightgrey");
 3166 
 3167     fprintf(f, "];\n");
 3168 
 3169     if (LEFT(node) != NULL)
 3170         fprintf(f, "\"node%u\":f0 -> \"node%u\":f1;\n", *nodecount, l);
 3171 
 3172     if (DOWN(node) != NULL)
 3173         fprintf(f, "\"node%u\":f1 -> \"node%u\":f1 [penwidth=5];\n",
 3174             *nodecount, d);
 3175 
 3176     if (RIGHT(node) != NULL)
 3177         fprintf(f, "\"node%u\":f2 -> \"node%u\":f1;\n", *nodecount, r);
 3178 
 3179     return (*nodecount);
 3180 }
 3181 
 3182 void
 3183 dns_rbt_printdot(dns_rbt_t *rbt, bool show_pointers, FILE *f) {
 3184     unsigned int nodecount = 0;
 3185 
 3186     REQUIRE(VALID_RBT(rbt));
 3187 
 3188     fprintf(f, "digraph g {\n");
 3189     fprintf(f, "node [shape = record,height=.1];\n");
 3190     print_dot_helper(rbt->root, &nodecount, show_pointers, f);
 3191     fprintf(f, "}\n");
 3192 }
 3193 
 3194 /*
 3195  * Chain Functions
 3196  */
 3197 
 3198 void
 3199 dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
 3200 
 3201     REQUIRE(chain != NULL);
 3202 
 3203     /*
 3204      * Initialize 'chain'.
 3205      */
 3206     chain->mctx = mctx;
 3207     chain->end = NULL;
 3208     chain->level_count = 0;
 3209     chain->level_matches = 0;
 3210     memset(chain->levels, 0, sizeof(chain->levels));
 3211 
 3212     chain->magic = CHAIN_MAGIC;
 3213 }
 3214 
 3215 isc_result_t
 3216 dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
 3217              dns_name_t *origin, dns_rbtnode_t **node)
 3218 {
 3219     isc_result_t result = ISC_R_SUCCESS;
 3220 
 3221     REQUIRE(VALID_CHAIN(chain));
 3222 
 3223     if (node != NULL)
 3224         *node = chain->end;
 3225 
 3226     if (chain->end == NULL)
 3227         return (ISC_R_NOTFOUND);
 3228 
 3229     if (name != NULL) {
 3230         NODENAME(chain->end, name);
 3231 
 3232         if (chain->level_count == 0) {
 3233             /*
 3234              * Names in the top level tree are all absolute.
 3235              * Always make 'name' relative.
 3236              */
 3237             INSIST(dns_name_isabsolute(name));
 3238 
 3239             /*
 3240              * This is cheaper than dns_name_getlabelsequence().
 3241              */
 3242             name->labels--;
 3243             name->length--;
 3244             name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
 3245         }
 3246     }
 3247 
 3248     if (origin != NULL) {
 3249         if (chain->level_count > 0)
 3250             result = chain_name(chain, origin, false);
 3251         else
 3252             result = dns_name_copy(dns_rootname, origin, NULL);
 3253     }
 3254 
 3255     return (result);
 3256 }
 3257 
 3258 isc_result_t
 3259 dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
 3260               dns_name_t *origin)
 3261 {
 3262     dns_rbtnode_t *current, *previous, *predecessor;
 3263     isc_result_t result = ISC_R_SUCCESS;
 3264     bool new_origin = false;
 3265 
 3266     REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
 3267 
 3268     predecessor = NULL;
 3269 
 3270     current = chain->end;
 3271 
 3272     if (LEFT(current) != NULL) {
 3273         /*
 3274          * Moving left one then right as far as possible is the
 3275          * previous node, at least for this level.
 3276          */
 3277         current = LEFT(current);
 3278 
 3279         while (RIGHT(current) != NULL)
 3280             current = RIGHT(current);
 3281 
 3282         predecessor = current;
 3283 
 3284     } else {
 3285         /*
 3286          * No left links, so move toward the root.  If at any point on
 3287          * the way there the link from parent to child is a right
 3288          * link, then the parent is the previous node, at least
 3289          * for this level.
 3290          */
 3291         while (! IS_ROOT(current)) {
 3292             previous = current;
 3293             current = PARENT(current);
 3294 
 3295             if (RIGHT(current) == previous) {
 3296                 predecessor = current;
 3297                 break;
 3298             }
 3299         }
 3300     }
 3301 
 3302     if (predecessor != NULL) {
 3303         /*
 3304          * Found a predecessor node in this level.  It might not
 3305          * really be the predecessor, however.
 3306          */
 3307         if (DOWN(predecessor) != NULL) {
 3308             /*
 3309              * The predecessor is really down at least one level.
 3310              * Go down and as far right as possible, and repeat
 3311              * as long as the rightmost node has a down pointer.
 3312              */
 3313             do {
 3314                 /*
 3315                  * XXX DCL Need to do something about origins
 3316                  * here. See whether to go down, and if so
 3317                  * whether it is truly what Bob calls a
 3318                  * new origin.
 3319                  */
 3320                 ADD_LEVEL(chain, predecessor);
 3321                 predecessor = DOWN(predecessor);
 3322 
 3323                 /* XXX DCL duplicated from above; clever
 3324                  * way to unduplicate? */
 3325 
 3326                 while (RIGHT(predecessor) != NULL)
 3327                     predecessor = RIGHT(predecessor);
 3328             } while (DOWN(predecessor) != NULL);
 3329 
 3330             /* XXX DCL probably needs work on the concept */
 3331             if (origin != NULL)
 3332                 new_origin = true;
 3333         }
 3334 
 3335     } else if (chain->level_count > 0) {
 3336         /*
 3337          * Dang, didn't find a predecessor in this level.
 3338          * Got to the root of this level without having traversed
 3339          * any right links.  Ascend the tree one level; the
 3340          * node that points to this tree is the predecessor.
 3341          */
 3342         INSIST(chain->level_count > 0 && IS_ROOT(current));
 3343         predecessor = chain->levels[--chain->level_count];
 3344 
 3345         /* XXX DCL probably needs work on the concept */
 3346         /*
 3347          * Don't declare an origin change when the new origin is "."
 3348          * at the top level tree, because "." is declared as the origin
 3349          * for the second level tree.
 3350          */
 3351         if (origin != NULL &&
 3352             (chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
 3353             new_origin = true;
 3354     }
 3355 
 3356     if (predecessor != NULL) {
 3357         chain->end = predecessor;
 3358 
 3359         if (new_origin) {
 3360             result = dns_rbtnodechain_current(chain, name, origin,
 3361                               NULL);
 3362             if (result == ISC_R_SUCCESS)
 3363                 result = DNS_R_NEWORIGIN;
 3364 
 3365         } else
 3366             result = dns_rbtnodechain_current(chain, name, NULL,
 3367                               NULL);
 3368 
 3369     } else
 3370         result = ISC_R_NOMORE;
 3371 
 3372     return (result);
 3373 }
 3374 
 3375 isc_result_t
 3376 dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
 3377               dns_name_t *origin)
 3378 {
 3379     dns_rbtnode_t *current, *successor;
 3380     isc_result_t result = ISC_R_SUCCESS;
 3381     bool new_origin = false;
 3382 
 3383     REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
 3384 
 3385     successor = NULL;
 3386 
 3387     current = chain->end;
 3388 
 3389     if (DOWN(current) != NULL) {
 3390         /*
 3391          * Don't declare an origin change when the new origin is "."
 3392          * at the second level tree, because "." is already declared
 3393          * as the origin for the top level tree.
 3394          */
 3395         if (chain->level_count > 0 ||
 3396             OFFSETLEN(current) > 1)
 3397             new_origin = true;
 3398 
 3399         ADD_LEVEL(chain, current);
 3400         current = DOWN(current);
 3401 
 3402         while (LEFT(current) != NULL)
 3403             current = LEFT(current);
 3404 
 3405         successor = current;
 3406     }
 3407 
 3408     if (successor != NULL) {
 3409         chain->end = successor;
 3410 
 3411         /*
 3412          * It is not necessary to use dns_rbtnodechain_current like
 3413          * the other functions because this function will never
 3414          * find a node in the topmost level.  This is because the
 3415          * root level will never be more than one name, and everything
 3416          * in the megatree is a successor to that node, down at
 3417          * the second level or below.
 3418          */
 3419 
 3420         if (name != NULL)
 3421             NODENAME(chain->end, name);
 3422 
 3423         if (new_origin) {
 3424             if (origin != NULL)
 3425                 result = chain_name(chain, origin, false);
 3426 
 3427             if (result == ISC_R_SUCCESS)
 3428                 result = DNS_R_NEWORIGIN;
 3429 
 3430         } else
 3431             result = ISC_R_SUCCESS;
 3432 
 3433     } else
 3434         result = ISC_R_NOMORE;
 3435 
 3436     return (result);
 3437 }
 3438 
 3439 isc_result_t
 3440 dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name) {
 3441     dns_rbtnode_t *current, *previous, *successor;
 3442     isc_result_t result = ISC_R_SUCCESS;
 3443 
 3444     REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
 3445 
 3446     successor = NULL;
 3447 
 3448     current = chain->end;
 3449 
 3450     if (RIGHT(current) == NULL) {
 3451         while (! IS_ROOT(current)) {
 3452             previous = current;
 3453             current = PARENT(current);
 3454 
 3455             if (LEFT(current) == previous) {
 3456                 successor = current;
 3457                 break;
 3458             }
 3459         }
 3460     } else {
 3461         current = RIGHT(current);
 3462 
 3463         while (LEFT(current) != NULL)
 3464             current = LEFT(current);
 3465 
 3466         successor = current;
 3467     }
 3468 
 3469     if (successor != NULL) {
 3470         chain->end = successor;
 3471 
 3472         if (name != NULL)
 3473             NODENAME(chain->end, name);
 3474 
 3475         result = ISC_R_SUCCESS;
 3476     } else
 3477         result = ISC_R_NOMORE;
 3478 
 3479     return (result);
 3480 }
 3481 
 3482 isc_result_t
 3483 dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
 3484               dns_name_t *origin)
 3485 {
 3486     dns_rbtnode_t *current, *previous, *successor;
 3487     isc_result_t result = ISC_R_SUCCESS;
 3488     bool new_origin = false;
 3489 
 3490     REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
 3491 
 3492     successor = NULL;
 3493 
 3494     current = chain->end;
 3495 
 3496     /*
 3497      * If there is a level below this node, the next node is the leftmost
 3498      * node of the next level.
 3499      */
 3500     if (DOWN(current) != NULL) {
 3501         /*
 3502          * Don't declare an origin change when the new origin is "."
 3503          * at the second level tree, because "." is already declared
 3504          * as the origin for the top level tree.
 3505          */
 3506         if (chain->level_count > 0 ||
 3507             OFFSETLEN(current) > 1)
 3508             new_origin = true;
 3509 
 3510         ADD_LEVEL(chain, current);
 3511         current = DOWN(current);
 3512 
 3513         while (LEFT(current) != NULL)
 3514             current = LEFT(current);
 3515 
 3516         successor = current;
 3517 
 3518     } else if (RIGHT(current) == NULL) {
 3519         /*
 3520          * The successor is up, either in this level or a previous one.
 3521          * Head back toward the root of the tree, looking for any path
 3522          * that was via a left link; the successor is the node that has
 3523          * that left link.  In the event the root of the level is
 3524          * reached without having traversed any left links, ascend one
 3525          * level and look for either a right link off the point of
 3526          * ascent, or search for a left link upward again, repeating
 3527          * ascends until either case is true.
 3528          */
 3529         do {
 3530             while (! IS_ROOT(current)) {
 3531                 previous = current;
 3532                 current = PARENT(current);
 3533 
 3534                 if (LEFT(current) == previous) {
 3535                     successor = current;
 3536                     break;
 3537                 }
 3538             }
 3539 
 3540             if (successor == NULL) {
 3541                 /*
 3542                  * Reached the root without having traversed
 3543                  * any left pointers, so this level is done.
 3544                  */
 3545                 if (chain->level_count == 0) {
 3546                     /*
 3547                      * If the tree we are iterating over
 3548                      * was modified since this chain was
 3549                      * initialized in a way that caused
 3550                      * node splits to occur, "current" may
 3551                      * now be pointing to a root node which
 3552                      * appears to be at level 0, but still
 3553                      * has a parent.  If that happens,
 3554                      * abort.  Otherwise, we are done
 3555                      * looking for a successor as we really
 3556                      * reached the root node on level 0.
 3557                      */
 3558                     INSIST(PARENT(current) == NULL);
 3559                     break;
 3560                 }
 3561 
 3562                 current = chain->levels[--chain->level_count];
 3563                 new_origin = true;
 3564 
 3565                 if (RIGHT(current) != NULL)
 3566                     break;
 3567             }
 3568         } while (successor == NULL);
 3569     }
 3570 
 3571     if (successor == NULL && RIGHT(current) != NULL) {
 3572         current = RIGHT(current);
 3573 
 3574         while (LEFT(current) != NULL)
 3575             current = LEFT(current);
 3576 
 3577         successor = current;
 3578     }
 3579 
 3580     if (successor != NULL) {
 3581         /*
 3582          * If we determine that the current node is the successor to
 3583          * itself, we will run into an infinite loop, so abort instead.
 3584          */
 3585         INSIST(chain->end != successor);
 3586 
 3587         chain->end = successor;
 3588 
 3589         /*
 3590          * It is not necessary to use dns_rbtnodechain_current like
 3591          * the other functions because this function will never
 3592          * find a node in the topmost level.  This is because the
 3593          * root level will never be more than one name, and everything
 3594          * in the megatree is a successor to that node, down at
 3595          * the second level or below.
 3596          */
 3597 
 3598         if (name != NULL)
 3599             NODENAME(chain->end, name);
 3600 
 3601         if (new_origin) {
 3602             if (origin != NULL)
 3603                 result = chain_name(chain, origin, false);
 3604 
 3605             if (result == ISC_R_SUCCESS)
 3606                 result = DNS_R_NEWORIGIN;
 3607 
 3608         } else
 3609             result = ISC_R_SUCCESS;
 3610 
 3611     } else
 3612         result = ISC_R_NOMORE;
 3613 
 3614     return (result);
 3615 }
 3616 
 3617 isc_result_t
 3618 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
 3619                dns_name_t *name, dns_name_t *origin)
 3620 
 3621 {
 3622     isc_result_t result;
 3623 
 3624     REQUIRE(VALID_RBT(rbt));
 3625     REQUIRE(VALID_CHAIN(chain));
 3626 
 3627     dns_rbtnodechain_reset(chain);
 3628 
 3629     chain->end = rbt->root;
 3630 
 3631     result = dns_rbtnodechain_current(chain, name, origin, NULL);
 3632 
 3633     if (result == ISC_R_SUCCESS)
 3634         result = DNS_R_NEWORIGIN;
 3635 
 3636     return (result);
 3637 }
 3638 
 3639 isc_result_t
 3640 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
 3641                dns_name_t *name, dns_name_t *origin)
 3642 
 3643 {
 3644     isc_result_t result;
 3645 
 3646     REQUIRE(VALID_RBT(rbt));
 3647     REQUIRE(VALID_CHAIN(chain));
 3648 
 3649     dns_rbtnodechain_reset(chain);
 3650 
 3651     result = move_chain_to_last(chain, rbt->root);
 3652     if (result != ISC_R_SUCCESS)
 3653         return (result);
 3654 
 3655     result = dns_rbtnodechain_current(chain, name, origin, NULL);
 3656 
 3657     if (result == ISC_R_SUCCESS)
 3658         result = DNS_R_NEWORIGIN;
 3659 
 3660     return (result);
 3661 }
 3662 
 3663 
 3664 void
 3665 dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
 3666 
 3667     REQUIRE(VALID_CHAIN(chain));
 3668 
 3669     /*
 3670      * Free any dynamic storage associated with 'chain', and then
 3671      * reinitialize 'chain'.
 3672      */
 3673     chain->end = NULL;
 3674     chain->level_count = 0;
 3675     chain->level_matches = 0;
 3676 }
 3677 
 3678 void
 3679 dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
 3680     /*
 3681      * Free any dynamic storage associated with 'chain', and then
 3682      * invalidate 'chain'.
 3683      */
 3684 
 3685     dns_rbtnodechain_reset(chain);
 3686 
 3687     chain->magic = 0;
 3688 }
 3689 
 3690 /* XXXMUKS:
 3691  *
 3692  * - worth removing inline as static functions are inlined automatically
 3693  *   where suitable by modern compilers.
 3694  * - bump the size of dns_rbt.nodecount to size_t.
 3695  * - the dumpfile header also contains a nodecount that is unsigned
 3696  *   int. If large files (> 2^32 nodes) are to be supported, the
 3697  *   allocation for this field should be increased.
 3698  */