contrib/bind9/lib/dns/rbt.c

   1 /*
   2  * Copyright (C) 2004, 2005, 2008  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and/or distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: rbt.c,v 1.128.18.10 2008/03/31 13:32:59 fdupont Exp $ */
  19
  20 /*! \file */
  21
  22 /* Principal Authors: DCL */
  23
  24 #include <config.h>
  25
  26 #include <isc/mem.h>
  27 #include <isc/platform.h>
  28 #include <isc/print.h>
  29 #include <isc/refcount.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/rbt.h>
  41 #include <dns/result.h>
  42
  43 #define RBT_MAGIC               ISC_MAGIC('R', 'B', 'T', '+')
  44 #define VALID_RBT(rbt)          ISC_MAGIC_VALID(rbt, RBT_MAGIC)
  45
  46 /*
  47  * XXXDCL Since parent pointers were added in again, I could remove all of the
  48  * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
  49  * _lastnode.  This would involve pretty major change to the API.
  50  */
  51 #define CHAIN_MAGIC             ISC_MAGIC('0', '-', '0', '-')
  52 #define VALID_CHAIN(chain)      ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
  53
  54 #define RBT_HASH_SIZE           64
  55
  56 #ifdef RBT_MEM_TEST
  57 #undef RBT_HASH_SIZE
  58 #define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
  59 #endif
  60
  61 struct dns_rbt {
  62         unsigned int            magic;
  63         isc_mem_t *             mctx;
  64         dns_rbtnode_t *         root;
  65         void                    (*data_deleter)(void *, void *);
  66         void *                  deleter_arg;
  67         unsigned int            nodecount;
  68         unsigned int            hashsize;
  69         dns_rbtnode_t **        hashtable;
  70 };
  71
  72 #define RED 0
  73 #define BLACK 1
  74
  75 /*%
  76  * Elements of the rbtnode structure.
  77  */
  78 #define PARENT(node)            ((node)->parent)
  79 #define LEFT(node)              ((node)->left)
  80 #define RIGHT(node)             ((node)->right)
  81 #define DOWN(node)              ((node)->down)
  82 #define DATA(node)              ((node)->data)
  83 #define HASHNEXT(node)          ((node)->hashnext)
  84 #define HASHVAL(node)           ((node)->hashval)
  85 #define COLOR(node)             ((node)->color)
  86 #define NAMELEN(node)           ((node)->namelen)
  87 #define OFFSETLEN(node)         ((node)->offsetlen)
  88 #define ATTRS(node)             ((node)->attributes)
  89 #define PADBYTES(node)          ((node)->padbytes)
  90 #define IS_ROOT(node)           ISC_TF((node)->is_root == 1)
  91 #define FINDCALLBACK(node)      ISC_TF((node)->find_callback == 1)
  92
  93 /*%
  94  * Structure elements from the rbtdb.c, not
  95  * used as part of the rbt.c algorithms.
  96  */
  97 #define DIRTY(node)     ((node)->dirty)
  98 #define WILD(node)      ((node)->wild)
  99 #define LOCKNUM(node)   ((node)->locknum)
 100
 101 /*%
 102  * The variable length stuff stored after the node.
 103  */
 104 #define NAME(node)      ((unsigned char *)((node) + 1))
 105 #define OFFSETS(node)   (NAME(node) + NAMELEN(node))
 106
 107 #define NODE_SIZE(node) (sizeof(*node) + \
 108                          NAMELEN(node) + OFFSETLEN(node) + PADBYTES(node))
 109
 110 /*%
 111  * Color management.
 112  */
 113 #define IS_RED(node)            ((node) != NULL && (node)->color == RED)
 114 #define IS_BLACK(node)          ((node) == NULL || (node)->color == BLACK)
 115 #define MAKE_RED(node)          ((node)->color = RED)
 116 #define MAKE_BLACK(node)        ((node)->color = BLACK)
 117
 118 /*%
 119  * Chain management.
 120  *
 121  * The "ancestors" member of chains were removed, with their job now
 122  * being wholy handled by parent pointers (which didn't exist, because
 123  * of memory concerns, when chains were first implemented).
 124  */
 125 #define ADD_LEVEL(chain, node) \
 126                         (chain)->levels[(chain)->level_count++] = (node)
 127
 128 /*%
 129  * The following macros directly access normally private name variables.
 130  * These macros are used to avoid a lot of function calls in the critical
 131  * path of the tree traversal code.
 132  */
 133
 134 #define NODENAME(node, name) \
 135 do { \
 136         (name)->length = NAMELEN(node); \
 137         (name)->labels = OFFSETLEN(node); \
 138         (name)->ndata = NAME(node); \
 139         (name)->offsets = OFFSETS(node); \
 140         (name)->attributes = ATTRS(node); \
 141         (name)->attributes |= DNS_NAMEATTR_READONLY; \
 142 } while (0)
 143
 144 #ifdef DNS_RBT_USEHASH
 145 static isc_result_t
 146 inithash(dns_rbt_t *rbt);
 147 #endif
 148
 149 #ifdef DEBUG
 150 #define inline
 151 /*
 152  * A little something to help out in GDB.
 153  */
 154 dns_name_t Name(dns_rbtnode_t *node);
 155 dns_name_t
 156 Name(dns_rbtnode_t *node) {
 157         dns_name_t name;
 158
 159         dns_name_init(&name, NULL);
 160         if (node != NULL)
 161                 NODENAME(node, &name);
 162
 163         return (name);
 164 }
 165
 166 static void dns_rbt_printnodename(dns_rbtnode_t *node);
 167 #endif
 168
 169 static inline dns_rbtnode_t *
 170 find_up(dns_rbtnode_t *node) {
 171         dns_rbtnode_t *root;
 172
 173         /*
 174          * Return the node in the level above the argument node that points
 175          * to the level the argument node is in.  If the argument node is in
 176          * the top level, the return value is NULL.
 177          */
 178         for (root = node; ! IS_ROOT(root); root = PARENT(root))
 179                 ; /* Nothing. */
 180
 181         return (PARENT(root));
 182 }
 183
 184 /*
 185  * Forward declarations.
 186  */
 187 static isc_result_t
 188 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
 189
 190 #ifdef DNS_RBT_USEHASH
 191 static inline void
 192 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
 193 static inline void
 194 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
 195 #else
 196 #define hash_node(rbt, node, name) (ISC_R_SUCCESS)
 197 #define unhash_node(rbt, node)
 198 #endif
 199
 200 static inline void
 201 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
 202 static inline void
 203 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
 204
 205 static void
 206 dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
 207                    dns_rbtnode_t **rootp);
 208
 209 static void
 210 dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);
 211
 212 static isc_result_t
 213 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);
 214
 215 static void
 216 dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum,
 217                        dns_rbtnode_t **nodep);
 218
 219 /*
 220  * Initialize a red/black tree of trees.
 221  */
 222 isc_result_t
 223 dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
 224                void *deleter_arg, dns_rbt_t **rbtp)
 225 {
 226 #ifdef DNS_RBT_USEHASH
 227         isc_result_t result;
 228 #endif
 229         dns_rbt_t *rbt;
 230
 231
 232         REQUIRE(mctx != NULL);
 233         REQUIRE(rbtp != NULL && *rbtp == NULL);
 234         REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
 235
 236         rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
 237         if (rbt == NULL)
 238                 return (ISC_R_NOMEMORY);
 239
 240         rbt->mctx = mctx;
 241         rbt->data_deleter = deleter;
 242         rbt->deleter_arg = deleter_arg;
 243         rbt->root = NULL;
 244         rbt->nodecount = 0;
 245         rbt->hashtable = NULL;
 246         rbt->hashsize = 0;
 247 #ifdef DNS_RBT_USEHASH
 248         result = inithash(rbt);
 249         if (result != ISC_R_SUCCESS) {
 250                 isc_mem_put(mctx, rbt, sizeof(*rbt));
 251                 return (result);
 252         }
 253 #endif
 254         rbt->magic = RBT_MAGIC;
 255
 256         *rbtp = rbt;
 257
 258         return (ISC_R_SUCCESS);
 259 }
 260
 261 /*
 262  * Deallocate a red/black tree of trees.
 263  */
 264 void
 265 dns_rbt_destroy(dns_rbt_t **rbtp) {
 266         RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
 267 }
 268
 269 isc_result_t
 270 dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
 271         dns_rbt_t *rbt;
 272
 273         REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
 274
 275         rbt = *rbtp;
 276
 277         dns_rbt_deletetreeflat(rbt, quantum, &rbt->root);
 278         if (rbt->root != NULL)
 279                 return (ISC_R_QUOTA);
 280
 281         INSIST(rbt->nodecount == 0);
 282
 283         if (rbt->hashtable != NULL)
 284                 isc_mem_put(rbt->mctx, rbt->hashtable,
 285                             rbt->hashsize * sizeof(dns_rbtnode_t *));
 286
 287         rbt->magic = 0;
 288
 289         isc_mem_put(rbt->mctx, rbt, sizeof(*rbt));
 290         *rbtp = NULL;
 291         return (ISC_R_SUCCESS);
 292 }
 293
 294 unsigned int
 295 dns_rbt_nodecount(dns_rbt_t *rbt) {
 296         REQUIRE(VALID_RBT(rbt));
 297         return (rbt->nodecount);
 298 }
 299
 300 static inline isc_result_t
 301 chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
 302            isc_boolean_t include_chain_end)
 303 {
 304         dns_name_t nodename;
 305         isc_result_t result = ISC_R_SUCCESS;
 306         int i;
 307
 308         dns_name_init(&nodename, NULL);
 309
 310         if (include_chain_end && chain->end != NULL) {
 311                 NODENAME(chain->end, &nodename);
 312                 result = dns_name_copy(&nodename, name, NULL);
 313                 if (result != ISC_R_SUCCESS)
 314                         return (result);
 315         } else
 316                 dns_name_reset(name);
 317
 318         for (i = (int)chain->level_count - 1; i >= 0; i--) {
 319                 NODENAME(chain->levels[i], &nodename);
 320                 result = dns_name_concatenate(name, &nodename, name, NULL);
 321
 322                 if (result != ISC_R_SUCCESS)
 323                         return (result);
 324         }
 325         return (result);
 326 }
 327
 328 static inline isc_result_t
 329 move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
 330         do {
 331                 /*
 332                  * Go as far right and then down as much as possible,
 333                  * as long as the rightmost node has a down pointer.
 334                  */
 335                 while (RIGHT(node) != NULL)
 336                         node = RIGHT(node);
 337
 338                 if (DOWN(node) == NULL)
 339                         break;
 340
 341                 ADD_LEVEL(chain, node);
 342                 node = DOWN(node);
 343         } while (1);
 344
 345         chain->end = node;
 346
 347         return (ISC_R_SUCCESS);
 348 }
 349
 350 /*
 351  * Add 'name' to tree, initializing its data pointer with 'data'.
 352  */
 353
 354 isc_result_t
 355 dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
 356         /*
 357          * Does this thing have too many variables or what?
 358          */
 359         dns_rbtnode_t **root, *parent, *child, *current, *new_current;
 360         dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
 361         dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
 362         dns_offsets_t current_offsets;
 363         dns_namereln_t compared;
 364         isc_result_t result = ISC_R_SUCCESS;
 365         dns_rbtnodechain_t chain;
 366         unsigned int common_labels;
 367         unsigned int nlabels, hlabels;
 368         int order;
 369
 370         REQUIRE(VALID_RBT(rbt));
 371         REQUIRE(dns_name_isabsolute(name));
 372         REQUIRE(nodep != NULL && *nodep == NULL);
 373
 374         /*
 375          * Create a copy of the name so the original name structure is
 376          * not modified.
 377          */
 378         dns_fixedname_init(&fixedcopy);
 379         add_name = dns_fixedname_name(&fixedcopy);
 380         dns_name_clone(name, add_name);
 381
 382         if (rbt->root == NULL) {
 383                 result = create_node(rbt->mctx, add_name, &new_current);
 384                 if (result == ISC_R_SUCCESS) {
 385                         rbt->nodecount++;
 386                         new_current->is_root = 1;
 387                         rbt->root = new_current;
 388                         *nodep = new_current;
 389                         hash_node(rbt, new_current, name);
 390                 }
 391                 return (result);
 392         }
 393
 394         dns_rbtnodechain_init(&chain, rbt->mctx);
 395
 396         dns_fixedname_init(&fixedprefix);
 397         dns_fixedname_init(&fixedsuffix);
 398         prefix = dns_fixedname_name(&fixedprefix);
 399         suffix = dns_fixedname_name(&fixedsuffix);
 400
 401         root = &rbt->root;
 402         INSIST(IS_ROOT(*root));
 403         parent = NULL;
 404         current = NULL;
 405         child = *root;
 406         dns_name_init(&current_name, current_offsets);
 407         dns_fixedname_init(&fnewname);
 408         new_name = dns_fixedname_name(&fnewname);
 409         nlabels = dns_name_countlabels(name);
 410         hlabels = 0;
 411
 412         do {
 413                 current = child;
 414
 415                 NODENAME(current, &current_name);
 416                 compared = dns_name_fullcompare(add_name, &current_name,
 417                                                 &order, &common_labels);
 418
 419                 if (compared == dns_namereln_equal) {
 420                         *nodep = current;
 421                         result = ISC_R_EXISTS;
 422                         break;
 423
 424                 }
 425
 426                 if (compared == dns_namereln_none) {
 427
 428                         if (order < 0) {
 429                                 parent = current;
 430                                 child = LEFT(current);
 431
 432                         } else if (order > 0) {
 433                                 parent = current;
 434                                 child = RIGHT(current);
 435
 436                         }
 437
 438                 } else {
 439                         /*
 440                          * This name has some suffix in common with the
 441                          * name at the current node.  If the name at
 442                          * the current node is shorter, that means the
 443                          * new name should be in a subtree.  If the
 444                          * name at the current node is longer, that means
 445                          * the down pointer to this tree should point
 446                          * to a new tree that has the common suffix, and
 447                          * the non-common parts of these two names should
 448                          * start a new tree.
 449                          */
 450                         hlabels += common_labels;
 451                         if (compared == dns_namereln_subdomain) {
 452                                 /*
 453                                  * All of the existing labels are in common,
 454                                  * so the new name is in a subtree.
 455                                  * Whack off the common labels for the
 456                                  * not-in-common part to be searched for
 457                                  * in the next level.
 458                                  */
 459                                 dns_name_split(add_name, common_labels,
 460                                                add_name, NULL);
 461
 462                                 /*
 463                                  * Follow the down pointer (possibly NULL).
 464                                  */
 465                                 root = &DOWN(current);
 466
 467                                 INSIST(*root == NULL ||
 468                                        (IS_ROOT(*root) &&
 469                                         PARENT(*root) == current));
 470
 471                                 parent = NULL;
 472                                 child = DOWN(current);
 473                                 ADD_LEVEL(&chain, current);
 474
 475                         } else {
 476                                 /*
 477                                  * The number of labels in common is fewer
 478                                  * than the number of labels at the current
 479                                  * node, so the current node must be adjusted
 480                                  * to have just the common suffix, and a down
 481                                  * pointer made to a new tree.
 482                                  */
 483
 484                                 INSIST(compared == dns_namereln_commonancestor
 485                                        || compared == dns_namereln_contains);
 486
 487                                 /*
 488                                  * Ensure the number of levels in the tree
 489                                  * does not exceed the number of logical
 490                                  * levels allowed by DNSSEC.
 491                                  *
 492                                  * XXXDCL need a better error result?
 493                                  *
 494                                  * XXXDCL Since chain ancestors were removed,
 495                                  * no longer used by dns_rbt_addonlevel(),
 496                                  * this is the only real use of chains in the
 497                                  * function.  It could be done instead with
 498                                  * a simple integer variable, but I am pressed
 499                                  * for time.
 500                                  */
 501                                 if (chain.level_count ==
 502                                     (sizeof(chain.levels) /
 503                                      sizeof(*chain.levels))) {
 504                                         result = ISC_R_NOSPACE;
 505                                         break;
 506                                 }
 507
 508                                 /*
 509                                  * Split the name into two parts, a prefix
 510                                  * which is the not-in-common parts of the
 511                                  * two names and a suffix that is the common
 512                                  * parts of them.
 513                                  */
 514                                 dns_name_split(&current_name, common_labels,
 515                                                prefix, suffix);
 516                                 result = create_node(rbt->mctx, suffix,
 517                                                      &new_current);
 518
 519                                 if (result != ISC_R_SUCCESS)
 520                                         break;
 521
 522                                 /*
 523                                  * Reproduce the tree attributes of the
 524                                  * current node.
 525                                  */
 526                                 new_current->is_root = current->is_root;
 527                                 PARENT(new_current)  = PARENT(current);
 528                                 LEFT(new_current)    = LEFT(current);
 529                                 RIGHT(new_current)   = RIGHT(current);
 530                                 COLOR(new_current)   = COLOR(current);
 531
 532                                 /*
 533                                  * Fix pointers that were to the current node.
 534                                  */
 535                                 if (parent != NULL) {
 536                                         if (LEFT(parent) == current)
 537                                                 LEFT(parent) = new_current;
 538                                         else
 539                                                 RIGHT(parent) = new_current;
 540                                 }
 541                                 if (LEFT(new_current) != NULL)
 542                                         PARENT(LEFT(new_current)) =
 543                                                 new_current;
 544                                 if (RIGHT(new_current) != NULL)
 545                                         PARENT(RIGHT(new_current)) =
 546                                                 new_current;
 547                                 if (*root == current)
 548                                         *root = new_current;
 549
 550                                 NAMELEN(current) = prefix->length;
 551                                 OFFSETLEN(current) = prefix->labels;
 552                                 memcpy(OFFSETS(current), prefix->offsets,
 553                                        prefix->labels);
 554                                 PADBYTES(current) +=
 555                                        (current_name.length - prefix->length) +
 556                                        (current_name.labels - prefix->labels);
 557
 558                                 /*
 559                                  * Set up the new root of the next level.
 560                                  * By definition it will not be the top
 561                                  * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
 562                                  */
 563                                 current->is_root = 1;
 564                                 PARENT(current) = new_current;
 565                                 DOWN(new_current) = current;
 566                                 root = &DOWN(new_current);
 567
 568                                 ADD_LEVEL(&chain, new_current);
 569
 570                                 LEFT(current) = NULL;
 571                                 RIGHT(current) = NULL;
 572
 573                                 MAKE_BLACK(current);
 574                                 ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
 575
 576                                 rbt->nodecount++;
 577                                 dns_name_getlabelsequence(name,
 578                                                           nlabels - hlabels,
 579                                                           hlabels, new_name);
 580                                 hash_node(rbt, new_current, new_name);
 581
 582                                 if (common_labels ==
 583                                     dns_name_countlabels(add_name)) {
 584                                         /*
 585                                          * The name has been added by pushing
 586                                          * the not-in-common parts down to
 587                                          * a new level.
 588                                          */
 589                                         *nodep = new_current;
 590                                         return (ISC_R_SUCCESS);
 591
 592                                 } else {
 593                                         /*
 594                                          * The current node has no data,
 595                                          * because it is just a placeholder.
 596                                          * Its data pointer is already NULL
 597                                          * from create_node()), so there's
 598                                          * nothing more to do to it.
 599                                          */
 600
 601                                         /*
 602                                          * The not-in-common parts of the new
 603                                          * name will be inserted into the new
 604                                          * level following this loop (unless
 605                                          * result != ISC_R_SUCCESS, which
 606                                          * is tested after the loop ends).
 607                                          */
 608                                         dns_name_split(add_name, common_labels,
 609                                                        add_name, NULL);
 610
 611                                         break;
 612                                 }
 613
 614                         }
 615
 616                 }
 617
 618         } while (child != NULL);
 619
 620         if (result == ISC_R_SUCCESS)
 621                 result = create_node(rbt->mctx, add_name, &new_current);
 622
 623         if (result == ISC_R_SUCCESS) {
 624                 dns_rbt_addonlevel(new_current, current, order, root);
 625                 rbt->nodecount++;
 626                 *nodep = new_current;
 627                 hash_node(rbt, new_current, name);
 628         }
 629
 630         return (result);
 631 }
 632
 633 /*
 634  * Add a name to the tree of trees, associating it with some data.
 635  */
 636 isc_result_t
 637 dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
 638         isc_result_t result;
 639         dns_rbtnode_t *node;
 640
 641         REQUIRE(VALID_RBT(rbt));
 642         REQUIRE(dns_name_isabsolute(name));
 643
 644         node = NULL;
 645
 646         result = dns_rbt_addnode(rbt, name, &node);
 647
 648         /*
 649          * dns_rbt_addnode will report the node exists even when
 650          * it does not have data associated with it, but the
 651          * dns_rbt_*name functions all behave depending on whether
 652          * there is data associated with a node.
 653          */
 654         if (result == ISC_R_SUCCESS ||
 655             (result == ISC_R_EXISTS && DATA(node) == NULL)) {
 656                 DATA(node) = data;
 657                 result = ISC_R_SUCCESS;
 658         }
 659
 660         return (result);
 661 }
 662
 663 /*
 664  * Find the node for "name" in the tree of trees.
 665  */
 666 isc_result_t
 667 dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
 668                  dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
 669                  unsigned int options, dns_rbtfindcallback_t callback,
 670                  void *callback_arg)
 671 {
 672         dns_rbtnode_t *current, *last_compared, *current_root;
 673         dns_rbtnodechain_t localchain;
 674         dns_name_t *search_name, current_name, *callback_name;
 675         dns_fixedname_t fixedcallbackname, fixedsearchname;
 676         dns_namereln_t compared;
 677         isc_result_t result, saved_result;
 678         unsigned int common_labels;
 679         unsigned int hlabels = 0;
 680         int order;
 681
 682         REQUIRE(VALID_RBT(rbt));
 683         REQUIRE(dns_name_isabsolute(name));
 684         REQUIRE(node != NULL && *node == NULL);
 685         REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
 686                 !=         (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
 687
 688         /*
 689          * If there is a chain it needs to appear to be in a sane state,
 690          * otherwise a chain is still needed to generate foundname and
 691          * callback_name.
 692          */
 693         if (chain == NULL) {
 694                 options |= DNS_RBTFIND_NOPREDECESSOR;
 695                 chain = &localchain;
 696                 dns_rbtnodechain_init(chain, rbt->mctx);
 697         } else
 698                 dns_rbtnodechain_reset(chain);
 699
 700         if (rbt->root == NULL)
 701                 return (ISC_R_NOTFOUND);
 702         else {
 703                 /*
 704                  * Appease GCC about variables it incorrectly thinks are
 705                  * possibly used uninitialized.
 706                  */
 707                 compared = dns_namereln_none;
 708                 last_compared = NULL;
 709         }
 710
 711         dns_fixedname_init(&fixedcallbackname);
 712         callback_name = dns_fixedname_name(&fixedcallbackname);
 713
 714         /*
 715          * search_name is the name segment being sought in each tree level.
 716          * By using a fixedname, the search_name will definitely have offsets
 717          * for use by any splitting.
 718          * By using dns_name_clone, no name data should be copied thanks to
 719          * the lack of bitstring labels.
 720          */
 721         dns_fixedname_init(&fixedsearchname);
 722         search_name = dns_fixedname_name(&fixedsearchname);
 723         dns_name_clone(name, search_name);
 724
 725         dns_name_init(&current_name, NULL);
 726
 727         saved_result = ISC_R_SUCCESS;
 728         current = rbt->root;
 729         current_root = rbt->root;
 730
 731         while (current != NULL) {
 732                 NODENAME(current, &current_name);
 733                 compared = dns_name_fullcompare(search_name, &current_name,
 734                                                 &order, &common_labels);
 735                 last_compared = current;
 736
 737                 if (compared == dns_namereln_equal)
 738                         break;
 739
 740                 if (compared == dns_namereln_none) {
 741 #ifdef DNS_RBT_USEHASH
 742                         dns_name_t hash_name;
 743                         dns_rbtnode_t *hnode;
 744                         dns_rbtnode_t *up_current;
 745                         unsigned int nlabels;
 746                         unsigned int tlabels = 1;
 747                         unsigned int hash;
 748
 749                         /*
 750                          * If there is no hash table, hashing can't be done.
 751                          */
 752                         if (rbt->hashtable == NULL)
 753                                 goto nohash;
 754
 755                         /*
 756                          * The case of current != current_root, that
 757                          * means a left or right pointer was followed,
 758                          * only happens when the algorithm fell through to
 759                          * the traditional binary search because of a
 760                          * bitstring label.  Since we dropped the bitstring
 761                          * support, this should not happen.
 762                          */
 763                         INSIST(current == current_root);
 764
 765                         nlabels = dns_name_countlabels(search_name);
 766
 767                         /*
 768                          * current_root is the root of the current level, so
 769                          * it's parent is the same as it's "up" pointer.
 770                          */
 771                         up_current = PARENT(current_root);
 772                         dns_name_init(&hash_name, NULL);
 773
 774                 hashagain:
 775                         /*
 776                          * Hash includes tail.
 777                          */
 778                         dns_name_getlabelsequence(name,
 779                                                   nlabels - tlabels,
 780                                                   hlabels + tlabels,
 781                                                   &hash_name);
 782                         hash = dns_name_fullhash(&hash_name, ISC_FALSE);
 783                         dns_name_getlabelsequence(search_name,
 784                                                   nlabels - tlabels,
 785                                                   tlabels, &hash_name);
 786
 787                         for (hnode = rbt->hashtable[hash % rbt->hashsize];
 788                              hnode != NULL;
 789                              hnode = hnode->hashnext)
 790                         {
 791                                 dns_name_t hnode_name;
 792
 793                                 if (hash != HASHVAL(hnode))
 794                                         continue;
 795                                 if (find_up(hnode) != up_current)
 796                                         continue;
 797                                 dns_name_init(&hnode_name, NULL);
 798                                 NODENAME(hnode, &hnode_name);
 799                                 if (dns_name_equal(&hnode_name, &hash_name))
 800                                         break;
 801                         }
 802
 803                         if (hnode != NULL) {
 804                                 current = hnode;
 805                                 /*
 806                                  * This is an optimization.  If hashing found
 807                                  * the right node, the next call to
 808                                  * dns_name_fullcompare() would obviously
 809                                  * return _equal or _subdomain.  Determine
 810                                  * which of those would be the case by
 811                                  * checking if the full name was hashed.  Then
 812                                  * make it look like dns_name_fullcompare
 813                                  * was called and jump to the right place.
 814                                  */
 815                                 if (tlabels == nlabels) {
 816                                         compared = dns_namereln_equal;
 817                                         break;
 818                                 } else {
 819                                         common_labels = tlabels;
 820                                         compared = dns_namereln_subdomain;
 821                                         goto subdomain;
 822                                 }
 823                         }
 824
 825                         if (tlabels++ < nlabels)
 826                                 goto hashagain;
 827
 828                         /*
 829                          * All of the labels have been tried against the hash
 830                          * table.  Since we dropped the support of bitstring
 831                          * labels, the name isn't in the table.
 832                          */
 833                         current = NULL;
 834                         continue;
 835
 836                 nohash:
 837 #endif /* DNS_RBT_USEHASH */
 838                         /*
 839                          * Standard binary search tree movement.
 840                          */
 841                         if (order < 0)
 842                                 current = LEFT(current);
 843                         else
 844                                 current = RIGHT(current);
 845
 846                 } else {
 847                         /*
 848                          * The names have some common suffix labels.
 849                          *
 850                          * If the number in common are equal in length to
 851                          * the current node's name length, then follow the
 852                          * down pointer and search in the new tree.
 853                          */
 854                         if (compared == dns_namereln_subdomain) {
 855                 subdomain:
 856                                 /*
 857                                  * Whack off the current node's common parts
 858                                  * for the name to search in the next level.
 859                                  */
 860                                 dns_name_split(search_name, common_labels,
 861                                                search_name, NULL);
 862                                 hlabels += common_labels;
 863                                 /*
 864                                  * This might be the closest enclosing name.
 865                                  */
 866                                 if (DATA(current) != NULL ||
 867                                     (options & DNS_RBTFIND_EMPTYDATA) != 0)
 868                                         *node = current;
 869
 870                                 /*
 871                                  * Point the chain to the next level.   This
 872                                  * needs to be done before 'current' is pointed
 873                                  * there because the callback in the next
 874                                  * block of code needs the current 'current',
 875                                  * but in the event the callback requests that
 876                                  * the search be stopped then the
 877                                  * DNS_R_PARTIALMATCH code at the end of this
 878                                  * function needs the chain pointed to the
 879                                  * next level.
 880                                  */
 881                                 ADD_LEVEL(chain, current);
 882
 883                                 /*
 884                                  * The caller may want to interrupt the
 885                                  * downward search when certain special nodes
 886                                  * are traversed.  If this is a special node,
 887                                  * the callback is used to learn what the
 888                                  * caller wants to do.
 889                                  */
 890                                 if (callback != NULL &&
 891                                     FINDCALLBACK(current)) {
 892                                         result = chain_name(chain,
 893                                                             callback_name,
 894                                                             ISC_FALSE);
 895                                         if (result != ISC_R_SUCCESS) {
 896                                                 dns_rbtnodechain_reset(chain);
 897                                                 return (result);
 898                                         }
 899
 900                                         result = (callback)(current,
 901                                                             callback_name,
 902                                                             callback_arg);
 903                                         if (result != DNS_R_CONTINUE) {
 904                                                 saved_result = result;
 905                                                 /*
 906                                                  * Treat this node as if it
 907                                                  * had no down pointer.
 908                                                  */
 909                                                 current = NULL;
 910                                                 break;
 911                                         }
 912                                 }
 913
 914                                 /*
 915                                  * Finally, head to the next tree level.
 916                                  */
 917                                 current = DOWN(current);
 918                                 current_root = current;
 919
 920                         } else {
 921                                 /*
 922                                  * Though there are labels in common, the
 923                                  * entire name at this node is not common
 924                                  * with the search name so the search
 925                                  * name does not exist in the tree.
 926                                  */
 927                                 INSIST(compared == dns_namereln_commonancestor
 928                                        || compared == dns_namereln_contains);
 929
 930                                 current = NULL;
 931                         }
 932                 }
 933         }
 934
 935         /*
 936          * If current is not NULL, NOEXACT is not disallowing exact matches,
 937          * and either the node has data or an empty node is ok, return
 938          * ISC_R_SUCCESS to indicate an exact match.
 939          */
 940         if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
 941             (DATA(current) != NULL ||
 942              (options & DNS_RBTFIND_EMPTYDATA) != 0)) {
 943                 /*
 944                  * Found an exact match.
 945                  */
 946                 chain->end = current;
 947                 chain->level_matches = chain->level_count;
 948
 949                 if (foundname != NULL)
 950                         result = chain_name(chain, foundname, ISC_TRUE);
 951                 else
 952                         result = ISC_R_SUCCESS;
 953
 954                 if (result == ISC_R_SUCCESS) {
 955                         *node = current;
 956                         result = saved_result;
 957                 } else
 958                         *node = NULL;
 959         } else {
 960                 /*
 961                  * Did not find an exact match (or did not want one).
 962                  */
 963                 if (*node != NULL) {
 964                         /*
 965                          * ... but found a partially matching superdomain.
 966                          * Unwind the chain to the partial match node
 967                          * to set level_matches to the level above the node,
 968                          * and then to derive the name.
 969                          *
 970                          * chain->level_count is guaranteed to be at least 1
 971                          * here because by definition of finding a superdomain,
 972                          * the chain is pointed to at least the first subtree.
 973                          */
 974                         chain->level_matches = chain->level_count - 1;
 975
 976                         while (chain->levels[chain->level_matches] != *node) {
 977                                 INSIST(chain->level_matches > 0);
 978                                 chain->level_matches--;
 979                         }
 980
 981                         if (foundname != NULL) {
 982                                 unsigned int saved_count = chain->level_count;
 983
 984                                 chain->level_count = chain->level_matches + 1;
 985
 986                                 result = chain_name(chain, foundname,
 987                                                     ISC_FALSE);
 988
 989                                 chain->level_count = saved_count;
 990                         } else
 991                                 result = ISC_R_SUCCESS;
 992
 993                         if (result == ISC_R_SUCCESS)
 994                                 result = DNS_R_PARTIALMATCH;
 995
 996                 } else
 997                         result = ISC_R_NOTFOUND;
 998
 999                 if (current != NULL) {
1000                         /*
1001                          * There was an exact match but either
1002                          * DNS_RBTFIND_NOEXACT was set, or
1003                          * DNS_RBTFIND_EMPTYDATA was set and the node had no
1004                          * data.  A policy decision was made to set the
1005                          * chain to the exact match, but this is subject
1006                          * to change if it becomes apparent that something
1007                          * else would be more useful.  It is important that
1008                          * this case is handled here, because the predecessor
1009                          * setting code below assumes the match was not exact.
1010                          */
1011                         INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
1012                                ((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
1013                                 DATA(current) == NULL));
1014                         chain->end = current;
1015
1016                 } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
1017                         /*
1018                          * Ensure the chain points nowhere.
1019                          */
1020                         chain->end = NULL;
1021
1022                 } else {
1023                         /*
1024                          * Since there was no exact match, the chain argument
1025                          * needs to be pointed at the DNSSEC predecessor of
1026                          * the search name.
1027                          */
1028                         if (compared == dns_namereln_subdomain) {
1029                                 /*
1030                                  * Attempted to follow a down pointer that was
1031                                  * NULL, which means the searched for name was
1032                                  * a subdomain of a terminal name in the tree.
1033                                  * Since there are no existing subdomains to
1034                                  * order against, the terminal name is the
1035                                  * predecessor.
1036                                  */
1037                                 INSIST(chain->level_count > 0);
1038                                 INSIST(chain->level_matches <
1039                                        chain->level_count);
1040                                 chain->end =
1041                                         chain->levels[--chain->level_count];
1042
1043                         } else {
1044                                 isc_result_t result2;
1045
1046                                 /*
1047                                  * Point current to the node that stopped
1048                                  * the search.
1049                                  *
1050                                  * With the hashing modification that has been
1051                                  * added to the algorithm, the stop node of a
1052                                  * standard binary search is not known.  So it
1053                                  * has to be found.  There is probably a more
1054                                  * clever way of doing this.
1055                                  *
1056                                  * The assignment of current to NULL when
1057                                  * the relationship is *not* dns_namereln_none,
1058                                  * even though it later gets set to the same
1059                                  * last_compared anyway, is simply to not push
1060                                  * the while loop in one more level of
1061                                  * indentation.
1062                                  */
1063                                 if (compared == dns_namereln_none)
1064                                         current = last_compared;
1065                                 else
1066                                         current = NULL;
1067
1068                                 while (current != NULL) {
1069                                         NODENAME(current, &current_name);
1070                                         compared = dns_name_fullcompare(
1071                                                                 search_name,
1072                                                                 &current_name,
1073                                                                 &order,
1074                                                                 &common_labels);
1075
1076                                         last_compared = current;
1077
1078                                         /*
1079                                          * Standard binary search movement.
1080                                          */
1081                                         if (order < 0)
1082                                                 current = LEFT(current);
1083                                         else
1084                                                 current = RIGHT(current);
1085
1086                                 }
1087
1088                                 current = last_compared;
1089
1090                                 /*
1091                                  * Reached a point within a level tree that
1092                                  * positively indicates the name is not
1093                                  * present, but the stop node could be either
1094                                  * less than the desired name (order > 0) or
1095                                  * greater than the desired name (order < 0).
1096                                  *
1097                                  * If the stop node is less, it is not
1098                                  * necessarily the predecessor.  If the stop
1099                                  * node has a down pointer, then the real
1100                                  * predecessor is at the end of a level below
1101                                  * (not necessarily the next level).
1102                                  * Move down levels until the rightmost node
1103                                  * does not have a down pointer.
1104                                  *
1105                                  * When the stop node is greater, it is
1106                                  * the successor.  All the logic for finding
1107                                  * the predecessor is handily encapsulated
1108                                  * in dns_rbtnodechain_prev.  In the event
1109                                  * that the search name is less than anything
1110                                  * else in the tree, the chain is reset.
1111                                  * XXX DCL What is the best way for the caller
1112                                  *         to know that the search name has
1113                                  *         no predecessor?
1114                                  */
1115
1116
1117                                 if (order > 0) {
1118                                         if (DOWN(current) != NULL) {
1119                                                 ADD_LEVEL(chain, current);
1120
1121                                                 result2 =
1122                                                       move_chain_to_last(chain,
1123                                                                 DOWN(current));
1124
1125                                                 if (result2 != ISC_R_SUCCESS)
1126                                                         result = result2;
1127                                         } else
1128                                                 /*
1129                                                  * Ah, the pure and simple
1130                                                  * case.  The stop node is the
1131                                                  * predecessor.
1132                                                  */
1133                                                 chain->end = current;
1134
1135                                 } else {
1136                                         INSIST(order < 0);
1137
1138                                         chain->end = current;
1139
1140                                         result2 = dns_rbtnodechain_prev(chain,
1141                                                                         NULL,
1142                                                                         NULL);
1143                                         if (result2 == ISC_R_SUCCESS ||
1144                                             result2 == DNS_R_NEWORIGIN)
1145                                                 ;       /* Nothing. */
1146                                         else if (result2 == ISC_R_NOMORE)
1147                                                 /*
1148                                                  * There is no predecessor.
1149                                                  */
1150                                                 dns_rbtnodechain_reset(chain);
1151                                         else
1152                                                 result = result2;
1153                                 }
1154
1155                         }
1156                 }
1157         }
1158
1159         ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
1160
1161         return (result);
1162 }
1163
1164 /*
1165  * Get the data pointer associated with 'name'.
1166  */
1167 isc_result_t
1168 dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
1169                  dns_name_t *foundname, void **data) {
1170         dns_rbtnode_t *node = NULL;
1171         isc_result_t result;
1172
1173         REQUIRE(data != NULL && *data == NULL);
1174
1175         result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
1176                                   options, NULL, NULL);
1177
1178         if (node != NULL &&
1179             (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
1180                 *data = DATA(node);
1181         else
1182                 result = ISC_R_NOTFOUND;
1183
1184         return (result);
1185 }
1186
1187 /*
1188  * Delete a name from the tree of trees.
1189  */
1190 isc_result_t
1191 dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse) {
1192         dns_rbtnode_t *node = NULL;
1193         isc_result_t result;
1194
1195         REQUIRE(VALID_RBT(rbt));
1196         REQUIRE(dns_name_isabsolute(name));
1197
1198         /*
1199          * First, find the node.
1200          *
1201          * When searching, the name might not have an exact match:
1202          * consider a.b.a.com, b.b.a.com and c.b.a.com as the only
1203          * elements of a tree, which would make layer 1 a single
1204          * node tree of "b.a.com" and layer 2 a three node tree of
1205          * a, b, and c.  Deleting a.com would find only a partial depth
1206          * match in the first layer.  Should it be a requirement that
1207          * that the name to be deleted have data?  For now, it is.
1208          *
1209          * ->dirty, ->locknum and ->references are ignored; they are
1210          * solely the province of rbtdb.c.
1211          */
1212         result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
1213                                   DNS_RBTFIND_NOOPTIONS, NULL, NULL);
1214
1215         if (result == ISC_R_SUCCESS) {
1216                 if (DATA(node) != NULL)
1217                         result = dns_rbt_deletenode(rbt, node, recurse);
1218                 else
1219                         result = ISC_R_NOTFOUND;
1220
1221         } else if (result == DNS_R_PARTIALMATCH)
1222                 result = ISC_R_NOTFOUND;
1223
1224         return (result);
1225 }
1226
1227 /*
1228  * Remove a node from the tree of trees.
1229  *
1230  * NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
1231  * a sequence of additions to be deletions will not generally get the
1232  * tree back to the state it started in.  For example, if the addition
1233  * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
1234  * then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
1235  * restoring "a.b.c".  The RBT *used* to do this kind of rejoining, but it
1236  * turned out to be a bad idea because it could corrupt an active nodechain
1237  * that had "b.c" as one of its levels -- and the RBT has no idea what
1238  * nodechains are in use by callers, so it can't even *try* to helpfully
1239  * fix them up (which would probably be doomed to failure anyway).
1240  *
1241  * Similarly, it is possible to leave the tree in a state where a supposedly
1242  * deleted node still exists.  The first case of this is obvious; take
1243  * the tree which has "b.c" on one level, pointing to "a".  Now deleted "b.c".
1244  * It was just established in the previous paragraph why we can't pull "a"
1245  * back up to its parent level.  But what happens when "a" then gets deleted?
1246  * "b.c" is left hanging around without data or children.  This condition
1247  * is actually pretty easy to detect, but ... should it really be removed?
1248  * Is a chain pointing to it?  An iterator?  Who knows!  (Note that the
1249  * references structure member cannot be looked at because it is private to
1250  * rbtdb.)  This is ugly and makes me unhappy, but after hours of trying to
1251  * make it more aesthetically proper and getting nowhere, this is the way it
1252  * is going to stay until such time as it proves to be a *real* problem.
1253  *
1254  * Finally, for reference, note that the original routine that did node
1255  * joining was called join_nodes().  It has been excised, living now only
1256  * in the CVS history, but comments have been left behind that point to it just
1257  * in case someone wants to muck with this some more.
1258  *
1259  * The one positive aspect of all of this is that joining used to have a
1260  * case where it might fail.  Without trying to join, now this function always
1261  * succeeds. It still returns isc_result_t, though, so the API wouldn't change.
1262  */
1263 isc_result_t
1264 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
1265 {
1266         dns_rbtnode_t *parent;
1267
1268         REQUIRE(VALID_RBT(rbt));
1269         REQUIRE(DNS_RBTNODE_VALID(node));
1270
1271         if (DOWN(node) != NULL) {
1272                 if (recurse)
1273                         RUNTIME_CHECK(dns_rbt_deletetree(rbt, DOWN(node))
1274                                       == ISC_R_SUCCESS);
1275                 else {
1276                         if (DATA(node) != NULL && rbt->data_deleter != NULL)
1277                                 rbt->data_deleter(DATA(node),
1278                                                   rbt->deleter_arg);
1279                         DATA(node) = NULL;
1280
1281                         /*
1282                          * Since there is at least one node below this one and
1283                          * no recursion was requested, the deletion is
1284                          * complete.  The down node from this node might be all
1285                          * by itself on a single level, so join_nodes() could
1286                          * be used to collapse the tree (with all the caveats
1287                          * of the comment at the start of this function).
1288                          */
1289                         return (ISC_R_SUCCESS);
1290                 }
1291         }
1292
1293         /*
1294          * Note the node that points to the level of the node that is being
1295          * deleted.  If the deleted node is the top level, parent will be set
1296          * to NULL.
1297          */
1298         parent = find_up(node);
1299
1300         /*
1301          * This node now has no down pointer (either because it didn't
1302          * have one to start, or because it was recursively removed).
1303          * So now the node needs to be removed from this level.
1304          */
1305         dns_rbt_deletefromlevel(node, parent == NULL ? &rbt->root :
1306                                                        &DOWN(parent));
1307
1308         if (DATA(node) != NULL && rbt->data_deleter != NULL)
1309                 rbt->data_deleter(DATA(node), rbt->deleter_arg);
1310
1311         unhash_node(rbt, node);
1312 #if DNS_RBT_USEMAGIC
1313         node->magic = 0;
1314 #endif
1315         dns_rbtnode_refdestroy(node);
1316         isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
1317         rbt->nodecount--;
1318
1319         /*
1320          * There are now two special cases that can exist that would
1321          * not have existed if the tree had been created using only
1322          * the names that now exist in it.  (This is all related to
1323          * join_nodes() as described in this function's introductory comment.)
1324          * Both cases exist when the deleted node's parent (the node
1325          * that pointed to the deleted node's level) is not null but
1326          * it has no data:  parent != NULL && DATA(parent) == NULL.
1327          *
1328          * The first case is that the deleted node was the last on its level:
1329          * DOWN(parent) == NULL.  This case can only exist if the parent was
1330          * previously deleted -- and so now, apparently, the parent should go
1331          * away.  That can't be done though because there might be external
1332          * references to it, such as through a nodechain.
1333          *
1334          * The other case also involves a parent with no data, but with the
1335          * deleted node being the next-to-last node instead of the last:
1336          * LEFT(DOWN(parent)) == NULL && RIGHT(DOWN(parent)) == NULL.
1337          * Presumably now the remaining node on the level should be joined
1338          * with the parent, but it's already been described why that can't be
1339          * done.
1340          */
1341
1342         /*
1343          * This function never fails.
1344          */
1345         return (ISC_R_SUCCESS);
1346 }
1347
1348 void
1349 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1350
1351         REQUIRE(DNS_RBTNODE_VALID(node));
1352         REQUIRE(name != NULL);
1353         REQUIRE(name->offsets == NULL);
1354
1355         NODENAME(node, name);
1356 }
1357
1358 isc_result_t
1359 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1360         dns_name_t current;
1361         isc_result_t result;
1362
1363         REQUIRE(DNS_RBTNODE_VALID(node));
1364         REQUIRE(name != NULL);
1365         REQUIRE(name->buffer != NULL);
1366
1367         dns_name_init(&current, NULL);
1368         dns_name_reset(name);
1369
1370         do {
1371                 INSIST(node != NULL);
1372
1373                 NODENAME(node, &current);
1374
1375                 result = dns_name_concatenate(name, &current, name, NULL);
1376                 if (result != ISC_R_SUCCESS)
1377                         break;
1378
1379                 node = find_up(node);
1380         } while (! dns_name_isabsolute(name));
1381
1382         return (result);
1383 }
1384
1385 char *
1386 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
1387 {
1388         dns_fixedname_t fixedname;
1389         dns_name_t *name;
1390         isc_result_t result;
1391
1392         REQUIRE(DNS_RBTNODE_VALID(node));
1393         REQUIRE(printname != NULL);
1394
1395         dns_fixedname_init(&fixedname);
1396         name = dns_fixedname_name(&fixedname);
1397         result = dns_rbt_fullnamefromnode(node, name);
1398         if (result == ISC_R_SUCCESS)
1399                 dns_name_format(name, printname, size);
1400         else
1401                 snprintf(printname, size, "<error building name: %s>",
1402                          dns_result_totext(result));
1403
1404         return (printname);
1405 }
1406
1407 static isc_result_t
1408 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep) {
1409         dns_rbtnode_t *node;
1410         isc_region_t region;
1411         unsigned int labels;
1412
1413         REQUIRE(name->offsets != NULL);
1414
1415         dns_name_toregion(name, &region);
1416         labels = dns_name_countlabels(name);
1417         ENSURE(labels > 0);
1418
1419         /*
1420          * Allocate space for the node structure, the name, and the offsets.
1421          */
1422         node = (dns_rbtnode_t *)isc_mem_get(mctx, sizeof(*node) +
1423                                             region.length + labels);
1424
1425         if (node == NULL)
1426                 return (ISC_R_NOMEMORY);
1427
1428         node->is_root = 0;
1429         PARENT(node) = NULL;
1430         RIGHT(node) = NULL;
1431         LEFT(node) = NULL;
1432         DOWN(node) = NULL;
1433         DATA(node) = NULL;
1434 #ifdef DNS_RBT_USEHASH
1435         HASHNEXT(node) = NULL;
1436         HASHVAL(node) = 0;
1437 #endif
1438
1439         LOCKNUM(node) = 0;
1440         WILD(node) = 0;
1441         DIRTY(node) = 0;
1442         dns_rbtnode_refinit(node, 0);
1443         node->find_callback = 0;
1444
1445         MAKE_BLACK(node);
1446
1447         /*
1448          * The following is stored to make reconstructing a name from the
1449          * stored value in the node easy:  the length of the name, the number
1450          * of labels, whether the name is absolute or not, the name itself,
1451          * and the name's offsets table.
1452          *
1453          * XXX RTH
1454          *      The offsets table could be made smaller by eliminating the
1455          *      first offset, which is always 0.  This requires changes to
1456          *      lib/dns/name.c.
1457          */
1458         NAMELEN(node) = region.length;
1459         PADBYTES(node) = 0;
1460         OFFSETLEN(node) = labels;
1461         ATTRS(node) = name->attributes;
1462
1463         memcpy(NAME(node), region.base, region.length);
1464         memcpy(OFFSETS(node), name->offsets, labels);
1465
1466 #if DNS_RBT_USEMAGIC
1467         node->magic = DNS_RBTNODE_MAGIC;
1468 #endif
1469         *nodep = node;
1470
1471         return (ISC_R_SUCCESS);
1472 }
1473
1474 #ifdef DNS_RBT_USEHASH
1475 static inline void
1476 hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
1477         unsigned int hash;
1478
1479         HASHVAL(node) = dns_name_fullhash(name, ISC_FALSE);
1480
1481         hash = HASHVAL(node) % rbt->hashsize;
1482         HASHNEXT(node) = rbt->hashtable[hash];
1483
1484         rbt->hashtable[hash] = node;
1485 }
1486
1487 static isc_result_t
1488 inithash(dns_rbt_t *rbt) {
1489         unsigned int bytes;
1490
1491         rbt->hashsize = RBT_HASH_SIZE;
1492         bytes = rbt->hashsize * sizeof(dns_rbtnode_t *);
1493         rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
1494
1495         if (rbt->hashtable == NULL)
1496                 return (ISC_R_NOMEMORY);
1497
1498         memset(rbt->hashtable, 0, bytes);
1499
1500         return (ISC_R_SUCCESS);
1501 }
1502
1503 static void
1504 rehash(dns_rbt_t *rbt) {
1505         unsigned int oldsize;
1506         dns_rbtnode_t **oldtable;
1507         dns_rbtnode_t *node;
1508         unsigned int hash;
1509         unsigned int i;
1510
1511         oldsize = rbt->hashsize;
1512         oldtable = rbt->hashtable;
1513         rbt->hashsize *= 2 + 1;
1514         rbt->hashtable = isc_mem_get(rbt->mctx,
1515                                      rbt->hashsize * sizeof(dns_rbtnode_t *));
1516         if (rbt->hashtable == NULL) {
1517                 rbt->hashtable = oldtable;
1518                 rbt->hashsize = oldsize;
1519                 return;
1520         }
1521
1522         for (i = 0; i < rbt->hashsize; i++)
1523                 rbt->hashtable[i] = NULL;
1524
1525         for (i = 0; i < oldsize; i++) {
1526                 node = oldtable[i];
1527                 while (node != NULL) {
1528                         hash = HASHVAL(node) % rbt->hashsize;
1529                         oldtable[i] = HASHNEXT(node);
1530                         HASHNEXT(node) = rbt->hashtable[hash];
1531                         rbt->hashtable[hash] = node;
1532                         node = oldtable[i];
1533                 }
1534         }
1535
1536         isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
1537 }
1538
1539 static inline void
1540 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
1541
1542         REQUIRE(DNS_RBTNODE_VALID(node));
1543
1544         if (rbt->nodecount >= (rbt->hashsize *3))
1545                 rehash(rbt);
1546
1547         hash_add_node(rbt, node, name);
1548 }
1549
1550 static inline void
1551 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1552         unsigned int bucket;
1553         dns_rbtnode_t *bucket_node;
1554
1555         REQUIRE(DNS_RBTNODE_VALID(node));
1556
1557         if (rbt->hashtable != NULL) {
1558                 bucket = HASHVAL(node) % rbt->hashsize;
1559                 bucket_node = rbt->hashtable[bucket];
1560
1561                 if (bucket_node == node)
1562                         rbt->hashtable[bucket] = HASHNEXT(node);
1563                 else {
1564                         while (HASHNEXT(bucket_node) != node) {
1565                                 INSIST(HASHNEXT(bucket_node) != NULL);
1566                                 bucket_node = HASHNEXT(bucket_node);
1567                         }
1568                         HASHNEXT(bucket_node) = HASHNEXT(node);
1569                 }
1570         }
1571 }
1572 #endif /* DNS_RBT_USEHASH */
1573
1574 static inline void
1575 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1576         dns_rbtnode_t *child;
1577
1578         REQUIRE(DNS_RBTNODE_VALID(node));
1579         REQUIRE(rootp != NULL);
1580
1581         child = RIGHT(node);
1582         INSIST(child != NULL);
1583
1584         RIGHT(node) = LEFT(child);
1585         if (LEFT(child) != NULL)
1586                 PARENT(LEFT(child)) = node;
1587         LEFT(child) = node;
1588
1589         if (child != NULL)
1590                 PARENT(child) = PARENT(node);
1591
1592         if (IS_ROOT(node)) {
1593                 *rootp = child;
1594                 child->is_root = 1;
1595                 node->is_root = 0;
1596
1597         } else {
1598                 if (LEFT(PARENT(node)) == node)
1599                         LEFT(PARENT(node)) = child;
1600                 else
1601                         RIGHT(PARENT(node)) = child;
1602         }
1603
1604         PARENT(node) = child;
1605 }
1606
1607 static inline void
1608 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1609         dns_rbtnode_t *child;
1610
1611         REQUIRE(DNS_RBTNODE_VALID(node));
1612         REQUIRE(rootp != NULL);
1613
1614         child = LEFT(node);
1615         INSIST(child != NULL);
1616
1617         LEFT(node) = RIGHT(child);
1618         if (RIGHT(child) != NULL)
1619                 PARENT(RIGHT(child)) = node;
1620         RIGHT(child) = node;
1621
1622         if (child != NULL)
1623                 PARENT(child) = PARENT(node);
1624
1625         if (IS_ROOT(node)) {
1626                 *rootp = child;
1627                 child->is_root = 1;
1628                 node->is_root = 0;
1629
1630         } else {
1631                 if (LEFT(PARENT(node)) == node)
1632                         LEFT(PARENT(node)) = child;
1633                 else
1634                         RIGHT(PARENT(node)) = child;
1635         }
1636
1637         PARENT(node) = child;
1638 }
1639
1640 /*
1641  * This is the real workhorse of the insertion code, because it does the
1642  * true red/black tree on a single level.
1643  */
1644 static void
1645 dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
1646                    dns_rbtnode_t **rootp)
1647 {
1648         dns_rbtnode_t *child, *root, *parent, *grandparent;
1649         dns_name_t add_name, current_name;
1650         dns_offsets_t add_offsets, current_offsets;
1651
1652         REQUIRE(rootp != NULL);
1653         REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
1654                 RIGHT(node) == NULL);
1655         REQUIRE(current != NULL);
1656
1657         root = *rootp;
1658         if (root == NULL) {
1659                 /*
1660                  * First node of a level.
1661                  */
1662                 MAKE_BLACK(node);
1663                 node->is_root = 1;
1664                 PARENT(node) = current;
1665                 *rootp = node;
1666                 return;
1667         }
1668
1669         child = root;
1670
1671         dns_name_init(&add_name, add_offsets);
1672         NODENAME(node, &add_name);
1673
1674         dns_name_init(&current_name, current_offsets);
1675         NODENAME(current, &current_name);
1676
1677         if (order < 0) {
1678                 INSIST(LEFT(current) == NULL);
1679                 LEFT(current) = node;
1680         } else {
1681                 INSIST(RIGHT(current) == NULL);
1682                 RIGHT(current) = node;
1683         }
1684
1685         INSIST(PARENT(node) == NULL);
1686         PARENT(node) = current;
1687
1688         MAKE_RED(node);
1689
1690         while (node != root && IS_RED(PARENT(node))) {
1691                 /*
1692                  * XXXDCL could do away with separate parent and grandparent
1693                  * variables.  They are vestiges of the days before parent
1694                  * pointers.  However, they make the code a little clearer.
1695                  */
1696
1697                 parent = PARENT(node);
1698                 grandparent = PARENT(parent);
1699
1700                 if (parent == LEFT(grandparent)) {
1701                         child = RIGHT(grandparent);
1702                         if (child != NULL && IS_RED(child)) {
1703                                 MAKE_BLACK(parent);
1704                                 MAKE_BLACK(child);
1705                                 MAKE_RED(grandparent);
1706                                 node = grandparent;
1707                         } else {
1708                                 if (node == RIGHT(parent)) {
1709                                         rotate_left(parent, &root);
1710                                         node = parent;
1711                                         parent = PARENT(node);
1712                                         grandparent = PARENT(parent);
1713                                 }
1714                                 MAKE_BLACK(parent);
1715                                 MAKE_RED(grandparent);
1716                                 rotate_right(grandparent, &root);
1717                         }
1718                 } else {
1719                         child = LEFT(grandparent);
1720                         if (child != NULL && IS_RED(child)) {
1721                                 MAKE_BLACK(parent);
1722                                 MAKE_BLACK(child);
1723                                 MAKE_RED(grandparent);
1724                                 node = grandparent;
1725                         } else {
1726                                 if (node == LEFT(parent)) {
1727                                         rotate_right(parent, &root);
1728                                         node = parent;
1729                                         parent = PARENT(node);
1730                                         grandparent = PARENT(parent);
1731                                 }
1732                                 MAKE_BLACK(parent);
1733                                 MAKE_RED(grandparent);
1734                                 rotate_left(grandparent, &root);
1735                         }
1736                 }
1737         }
1738
1739         MAKE_BLACK(root);
1740         ENSURE(IS_ROOT(root));
1741         *rootp = root;
1742
1743         return;
1744 }
1745
1746 /*
1747  * This is the real workhorse of the deletion code, because it does the
1748  * true red/black tree on a single level.
1749  */
1750 static void
1751 dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp) {
1752         dns_rbtnode_t *child, *sibling, *parent;
1753         dns_rbtnode_t *successor;
1754
1755         REQUIRE(delete != NULL);
1756
1757         /*
1758          * Verify that the parent history is (apparently) correct.
1759          */
1760         INSIST((IS_ROOT(delete) && *rootp == delete) ||
1761                (! IS_ROOT(delete) &&
1762                 (LEFT(PARENT(delete)) == delete ||
1763                  RIGHT(PARENT(delete)) == delete)));
1764
1765         child = NULL;
1766
1767         if (LEFT(delete) == NULL) {
1768                 if (RIGHT(delete) == NULL) {
1769                         if (IS_ROOT(delete)) {
1770                                 /*
1771                                  * This is the only item in the tree.
1772                                  */
1773                                 *rootp = NULL;
1774                                 return;
1775                         }
1776                 } else
1777                         /*
1778                          * This node has one child, on the right.
1779                          */
1780                         child = RIGHT(delete);
1781
1782         } else if (RIGHT(delete) == NULL)
1783                 /*
1784                  * This node has one child, on the left.
1785                  */
1786                 child = LEFT(delete);
1787         else {
1788                 dns_rbtnode_t holder, *tmp = &holder;
1789
1790                 /*
1791                  * This node has two children, so it cannot be directly
1792                  * deleted.  Find its immediate in-order successor and
1793                  * move it to this location, then do the deletion at the
1794                  * old site of the successor.
1795                  */
1796                 successor = RIGHT(delete);
1797                 while (LEFT(successor) != NULL)
1798                         successor = LEFT(successor);
1799
1800                 /*
1801                  * The successor cannot possibly have a left child;
1802                  * if there is any child, it is on the right.
1803                  */
1804                 if (RIGHT(successor) != NULL)
1805                         child = RIGHT(successor);
1806
1807                 /*
1808                  * Swap the two nodes; it would be simpler to just replace
1809                  * the value being deleted with that of the successor,
1810                  * but this rigamarole is done so the caller has complete
1811                  * control over the pointers (and memory allocation) of
1812                  * all of nodes.  If just the key value were removed from
1813                  * the tree, the pointer to the node would be unchanged.
1814                  */
1815
1816                 /*
1817                  * First, put the successor in the tree location of the
1818                  * node to be deleted.  Save its existing tree pointer
1819                  * information, which will be needed when linking up
1820                  * delete to the successor's old location.
1821                  */
1822                 memcpy(tmp, successor, sizeof(dns_rbtnode_t));
1823
1824                 if (IS_ROOT(delete)) {
1825                         *rootp = successor;
1826                         successor->is_root = ISC_TRUE;
1827                         delete->is_root = ISC_FALSE;
1828
1829                 } else
1830                         if (LEFT(PARENT(delete)) == delete)
1831                                 LEFT(PARENT(delete)) = successor;
1832                         else
1833                                 RIGHT(PARENT(delete)) = successor;
1834
1835                 PARENT(successor) = PARENT(delete);
1836                 LEFT(successor)   = LEFT(delete);
1837                 RIGHT(successor)  = RIGHT(delete);
1838                 COLOR(successor)  = COLOR(delete);
1839
1840                 if (LEFT(successor) != NULL)
1841                         PARENT(LEFT(successor)) = successor;
1842                 if (RIGHT(successor) != successor)
1843                         PARENT(RIGHT(successor)) = successor;
1844
1845                 /*
1846                  * Now relink the node to be deleted into the
1847                  * successor's previous tree location.  PARENT(tmp)
1848                  * is the successor's original parent.
1849                  */
1850                 INSIST(! IS_ROOT(delete));
1851
1852                 if (PARENT(tmp) == delete) {
1853                         /*
1854                          * Node being deleted was successor's parent.
1855                          */
1856                         RIGHT(successor) = delete;
1857                         PARENT(delete) = successor;
1858
1859                 } else {
1860                         LEFT(PARENT(tmp)) = delete;
1861                         PARENT(delete) = PARENT(tmp);
1862                 }
1863
1864                 /*
1865                  * Original location of successor node has no left.
1866                  */
1867                 LEFT(delete)   = NULL;
1868                 RIGHT(delete)  = RIGHT(tmp);
1869                 COLOR(delete)  = COLOR(tmp);
1870         }
1871
1872         /*
1873          * Remove the node by removing the links from its parent.
1874          */
1875         if (! IS_ROOT(delete)) {
1876                 if (LEFT(PARENT(delete)) == delete)
1877                         LEFT(PARENT(delete)) = child;
1878                 else
1879                         RIGHT(PARENT(delete)) = child;
1880
1881                 if (child != NULL)
1882                         PARENT(child) = PARENT(delete);
1883
1884         } else {
1885                 /*
1886                  * This is the root being deleted, and at this point
1887                  * it is known to have just one child.
1888                  */
1889                 *rootp = child;
1890                 child->is_root = 1;
1891                 PARENT(child) = PARENT(delete);
1892         }
1893
1894         /*
1895          * Fix color violations.
1896          */
1897         if (IS_BLACK(delete)) {
1898                 parent = PARENT(delete);
1899
1900                 while (child != *rootp && IS_BLACK(child)) {
1901                         INSIST(child == NULL || ! IS_ROOT(child));
1902
1903                         if (LEFT(parent) == child) {
1904                                 sibling = RIGHT(parent);
1905
1906                                 if (IS_RED(sibling)) {
1907                                         MAKE_BLACK(sibling);
1908                                         MAKE_RED(parent);
1909                                         rotate_left(parent, rootp);
1910                                         sibling = RIGHT(parent);
1911                                 }
1912
1913                                 if (IS_BLACK(LEFT(sibling)) &&
1914                                     IS_BLACK(RIGHT(sibling))) {
1915                                         MAKE_RED(sibling);
1916                                         child = parent;
1917
1918                                 } else {
1919
1920                                         if (IS_BLACK(RIGHT(sibling))) {
1921                                                 MAKE_BLACK(LEFT(sibling));
1922                                                 MAKE_RED(sibling);
1923                                                 rotate_right(sibling, rootp);
1924                                                 sibling = RIGHT(parent);
1925                                         }
1926
1927                                         COLOR(sibling) = COLOR(parent);
1928                                         MAKE_BLACK(parent);
1929                                         MAKE_BLACK(RIGHT(sibling));
1930                                         rotate_left(parent, rootp);
1931                                         child = *rootp;
1932                                 }
1933
1934                         } else {
1935                                 /*
1936                                  * Child is parent's right child.
1937                                  * Everything is doen the same as above,
1938                                  * except mirrored.
1939                                  */
1940                                 sibling = LEFT(parent);
1941
1942                                 if (IS_RED(sibling)) {
1943                                         MAKE_BLACK(sibling);
1944                                         MAKE_RED(parent);
1945                                         rotate_right(parent, rootp);
1946                                         sibling = LEFT(parent);
1947                                 }
1948
1949                                 if (IS_BLACK(LEFT(sibling)) &&
1950                                     IS_BLACK(RIGHT(sibling))) {
1951                                         MAKE_RED(sibling);
1952                                         child = parent;
1953
1954                                 } else {
1955                                         if (IS_BLACK(LEFT(sibling))) {
1956                                                 MAKE_BLACK(RIGHT(sibling));
1957                                                 MAKE_RED(sibling);
1958                                                 rotate_left(sibling, rootp);
1959                                                 sibling = LEFT(parent);
1960                                         }
1961
1962                                         COLOR(sibling) = COLOR(parent);
1963                                         MAKE_BLACK(parent);
1964                                         MAKE_BLACK(LEFT(sibling));
1965                                         rotate_right(parent, rootp);
1966                                         child = *rootp;
1967                                 }
1968                         }
1969
1970                         parent = PARENT(child);
1971                 }
1972
1973                 if (IS_RED(child))
1974                         MAKE_BLACK(child);
1975         }
1976 }
1977
1978 /*
1979  * This should only be used on the root of a tree, because no color fixup
1980  * is done at all.
1981  *
1982  * NOTE: No root pointer maintenance is done, because the function is only
1983  * used for two cases:
1984  * + deleting everything DOWN from a node that is itself being deleted, and
1985  * + deleting the entire tree of trees from dns_rbt_destroy.
1986  * In each case, the root pointer is no longer relevant, so there
1987  * is no need for a root parameter to this function.
1988  *
1989  * If the function is ever intended to be used to delete something where
1990  * a pointer needs to be told that this tree no longer exists,
1991  * this function would need to adjusted accordingly.
1992  */
1993 static isc_result_t
1994 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1995         isc_result_t result = ISC_R_SUCCESS;
1996         REQUIRE(VALID_RBT(rbt));
1997
1998         if (node == NULL)
1999                 return (result);
2000
2001         if (LEFT(node) != NULL) {
2002                 result = dns_rbt_deletetree(rbt, LEFT(node));
2003                 if (result != ISC_R_SUCCESS)
2004                         goto done;
2005                 LEFT(node) = NULL;
2006         }
2007         if (RIGHT(node) != NULL) {
2008                 result = dns_rbt_deletetree(rbt, RIGHT(node));
2009                 if (result != ISC_R_SUCCESS)
2010                         goto done;
2011                 RIGHT(node) = NULL;
2012         }
2013         if (DOWN(node) != NULL) {
2014                 result = dns_rbt_deletetree(rbt, DOWN(node));
2015                 if (result != ISC_R_SUCCESS)
2016                         goto done;
2017                 DOWN(node) = NULL;
2018         }
2019  done:
2020         if (result != ISC_R_SUCCESS)
2021                 return (result);
2022
2023         if (DATA(node) != NULL && rbt->data_deleter != NULL)
2024                 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2025
2026         unhash_node(rbt, node);
2027 #if DNS_RBT_USEMAGIC
2028         node->magic = 0;
2029 #endif
2030         isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2031         rbt->nodecount--;
2032         return (result);
2033 }
2034
2035 static void
2036 dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum,
2037                        dns_rbtnode_t **nodep)
2038 {
2039         dns_rbtnode_t *parent;
2040         dns_rbtnode_t *node = *nodep;
2041         REQUIRE(VALID_RBT(rbt));
2042
2043  again:
2044         if (node == NULL) {
2045                 *nodep = NULL;
2046                 return;
2047         }
2048
2049  traverse:
2050         if (LEFT(node) != NULL) {
2051                 node = LEFT(node);
2052                 goto traverse;
2053         }
2054         if (DOWN(node) != NULL) {
2055                 node = DOWN(node);
2056                 goto traverse;
2057         }
2058
2059         if (DATA(node) != NULL && rbt->data_deleter != NULL)
2060                 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2061
2062         /*
2063          * Note: we don't call unhash_node() here as we are destroying
2064          * the complete rbt tree.
2065          */
2066 #if DNS_RBT_USEMAGIC
2067         node->magic = 0;
2068 #endif
2069         parent = PARENT(node);
2070         if (RIGHT(node) != NULL)
2071                 PARENT(RIGHT(node)) = parent;
2072         if (parent != NULL) {
2073                 if (LEFT(parent) == node)
2074                         LEFT(parent) = RIGHT(node);
2075                 else if (DOWN(parent) == node)
2076                         DOWN(parent) = RIGHT(node);
2077         } else
2078                 parent = RIGHT(node);
2079         isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2080         rbt->nodecount--;
2081         node = parent;
2082         if (quantum != 0 && --quantum == 0) {
2083                 *nodep = node;
2084                 return;
2085         }
2086         goto again;
2087 }
2088
2089 static void
2090 dns_rbt_indent(int depth) {
2091         int i;
2092
2093         for (i = 0; i < depth; i++)
2094                 putchar('\t');
2095 }
2096
2097 static void
2098 dns_rbt_printnodename(dns_rbtnode_t *node) {
2099         isc_region_t r;
2100         dns_name_t name;
2101         char buffer[DNS_NAME_FORMATSIZE];
2102         dns_offsets_t offsets;
2103
2104         r.length = NAMELEN(node);
2105         r.base = NAME(node);
2106
2107         dns_name_init(&name, offsets);
2108         dns_name_fromregion(&name, &r);
2109
2110         dns_name_format(&name, buffer, sizeof(buffer));
2111
2112         printf("%s", buffer);
2113 }
2114
2115 static void
2116 dns_rbt_printtree(dns_rbtnode_t *root, dns_rbtnode_t *parent, int depth) {
2117         dns_rbt_indent(depth);
2118
2119         if (root != NULL) {
2120                 dns_rbt_printnodename(root);
2121                 printf(" (%s", IS_RED(root) ? "RED" : "black");
2122                 if (parent) {
2123                         printf(" from ");
2124                         dns_rbt_printnodename(parent);
2125                 }
2126
2127                 if ((! IS_ROOT(root) && PARENT(root) != parent) ||
2128                     (  IS_ROOT(root) && depth > 0 &&
2129                        DOWN(PARENT(root)) != root)) {
2130
2131                         printf(" (BAD parent pointer! -> ");
2132                         if (PARENT(root) != NULL)
2133                                 dns_rbt_printnodename(PARENT(root));
2134                         else
2135                                 printf("NULL");
2136                         printf(")");
2137                 }
2138
2139                 printf(")\n");
2140
2141
2142                 depth++;
2143
2144                 if (DOWN(root)) {
2145                         dns_rbt_indent(depth);
2146                         printf("++ BEG down from ");
2147                         dns_rbt_printnodename(root);
2148                         printf("\n");
2149                         dns_rbt_printtree(DOWN(root), NULL, depth);
2150                         dns_rbt_indent(depth);
2151                         printf("-- END down from ");
2152                         dns_rbt_printnodename(root);
2153                         printf("\n");
2154                 }
2155
2156                 if (IS_RED(root) && IS_RED(LEFT(root)))
2157                     printf("** Red/Red color violation on left\n");
2158                 dns_rbt_printtree(LEFT(root), root, depth);
2159
2160                 if (IS_RED(root) && IS_RED(RIGHT(root)))
2161                     printf("** Red/Red color violation on right\n");
2162                 dns_rbt_printtree(RIGHT(root), root, depth);
2163
2164         } else
2165                 printf("NULL\n");
2166 }
2167
2168 void
2169 dns_rbt_printall(dns_rbt_t *rbt) {
2170         REQUIRE(VALID_RBT(rbt));
2171
2172         dns_rbt_printtree(rbt->root, NULL, 0);
2173 }
2174
2175 /*
2176  * Chain Functions
2177  */
2178
2179 void
2180 dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
2181         /*
2182          * Initialize 'chain'.
2183          */
2184
2185         REQUIRE(chain != NULL);
2186
2187         chain->mctx = mctx;
2188         chain->end = NULL;
2189         chain->level_count = 0;
2190         chain->level_matches = 0;
2191         memset(chain->levels, 0, sizeof(chain->levels));
2192
2193         chain->magic = CHAIN_MAGIC;
2194 }
2195
2196 isc_result_t
2197 dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
2198                          dns_name_t *origin, dns_rbtnode_t **node)
2199 {
2200         isc_result_t result = ISC_R_SUCCESS;
2201
2202         REQUIRE(VALID_CHAIN(chain));
2203
2204         if (node != NULL)
2205                 *node = chain->end;
2206
2207         if (chain->end == NULL)
2208                 return (ISC_R_NOTFOUND);
2209
2210         if (name != NULL) {
2211                 NODENAME(chain->end, name);
2212
2213                 if (chain->level_count == 0) {
2214                         /*
2215                          * Names in the top level tree are all absolute.
2216                          * Always make 'name' relative.
2217                          */
2218                         INSIST(dns_name_isabsolute(name));
2219
2220                         /*
2221                          * This is cheaper than dns_name_getlabelsequence().
2222                          */
2223                         name->labels--;
2224                         name->length--;
2225                         name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
2226                 }
2227         }
2228
2229         if (origin != NULL) {
2230                 if (chain->level_count > 0)
2231                         result = chain_name(chain, origin, ISC_FALSE);
2232                 else
2233                         result = dns_name_copy(dns_rootname, origin, NULL);
2234         }
2235
2236         return (result);
2237 }
2238
2239 isc_result_t
2240 dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
2241                       dns_name_t *origin)
2242 {
2243         dns_rbtnode_t *current, *previous, *predecessor;
2244         isc_result_t result = ISC_R_SUCCESS;
2245         isc_boolean_t new_origin = ISC_FALSE;
2246
2247         REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2248
2249         predecessor = NULL;
2250
2251         current = chain->end;
2252
2253         if (LEFT(current) != NULL) {
2254                 /*
2255                  * Moving left one then right as far as possible is the
2256                  * previous node, at least for this level.
2257                  */
2258                 current = LEFT(current);
2259
2260                 while (RIGHT(current) != NULL)
2261                         current = RIGHT(current);
2262
2263                 predecessor = current;
2264
2265         } else {
2266                 /*
2267                  * No left links, so move toward the root.  If at any point on
2268                  * the way there the link from parent to child is a right
2269                  * link, then the parent is the previous node, at least
2270                  * for this level.
2271                  */
2272                 while (! IS_ROOT(current)) {
2273                         previous = current;
2274                         current = PARENT(current);
2275
2276                         if (RIGHT(current) == previous) {
2277                                 predecessor = current;
2278                                 break;
2279                         }
2280                 }
2281         }
2282
2283         if (predecessor != NULL) {
2284                 /*
2285                  * Found a predecessor node in this level.  It might not
2286                  * really be the predecessor, however.
2287                  */
2288                 if (DOWN(predecessor) != NULL) {
2289                         /*
2290                          * The predecessor is really down at least one level.
2291                          * Go down and as far right as possible, and repeat
2292                          * as long as the rightmost node has a down pointer.
2293                          */
2294                         do {
2295                                 /*
2296                                  * XXX DCL Need to do something about origins
2297                                  * here. See whether to go down, and if so
2298                                  * whether it is truly what Bob calls a
2299                                  * new origin.
2300                                  */
2301                                 ADD_LEVEL(chain, predecessor);
2302                                 predecessor = DOWN(predecessor);
2303
2304                                 /* XXX DCL duplicated from above; clever
2305                                  * way to unduplicate? */
2306
2307                                 while (RIGHT(predecessor) != NULL)
2308                                         predecessor = RIGHT(predecessor);
2309                         } while (DOWN(predecessor) != NULL);
2310
2311                         /* XXX DCL probably needs work on the concept */
2312                         if (origin != NULL)
2313                                 new_origin = ISC_TRUE;
2314                 }
2315
2316         } else if (chain->level_count > 0) {
2317                 /*
2318                  * Dang, didn't find a predecessor in this level.
2319                  * Got to the root of this level without having traversed
2320                  * any right links.  Ascend the tree one level; the
2321                  * node that points to this tree is the predecessor.
2322                  */
2323                 INSIST(chain->level_count > 0 && IS_ROOT(current));
2324                 predecessor = chain->levels[--chain->level_count];
2325
2326                 /* XXX DCL probably needs work on the concept */
2327                 /*
2328                  * Don't declare an origin change when the new origin is "."
2329                  * at the top level tree, because "." is declared as the origin
2330                  * for the second level tree.
2331                  */
2332                 if (origin != NULL &&
2333                     (chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
2334                         new_origin = ISC_TRUE;
2335         }
2336
2337         if (predecessor != NULL) {
2338                 chain->end = predecessor;
2339
2340                 if (new_origin) {
2341                         result = dns_rbtnodechain_current(chain, name, origin,
2342                                                           NULL);
2343                         if (result == ISC_R_SUCCESS)
2344                                 result = DNS_R_NEWORIGIN;
2345
2346                 } else
2347                         result = dns_rbtnodechain_current(chain, name, NULL,
2348                                                           NULL);
2349
2350         } else
2351                 result = ISC_R_NOMORE;
2352
2353         return (result);
2354 }
2355
2356 isc_result_t
2357 dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
2358                       dns_name_t *origin)
2359 {
2360         dns_rbtnode_t *current, *previous, *successor;
2361         isc_result_t result = ISC_R_SUCCESS;
2362         isc_boolean_t new_origin = ISC_FALSE;
2363
2364         REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2365
2366         successor = NULL;
2367
2368         current = chain->end;
2369
2370         /*
2371          * If there is a level below this node, the next node is the leftmost
2372          * node of the next level.
2373          */
2374         if (DOWN(current) != NULL) {
2375                 /*
2376                  * Don't declare an origin change when the new origin is "."
2377                  * at the second level tree, because "." is already declared
2378                  * as the origin for the top level tree.
2379                  */
2380                 if (chain->level_count > 0 ||
2381                     OFFSETLEN(current) > 1)
2382                         new_origin = ISC_TRUE;
2383
2384                 ADD_LEVEL(chain, current);
2385                 current = DOWN(current);
2386
2387                 while (LEFT(current) != NULL)
2388                         current = LEFT(current);
2389
2390                 successor = current;
2391
2392         } else if (RIGHT(current) == NULL) {
2393                 /*
2394                  * The successor is up, either in this level or a previous one.
2395                  * Head back toward the root of the tree, looking for any path
2396                  * that was via a left link; the successor is the node that has
2397                  * that left link.  In the event the root of the level is
2398                  * reached without having traversed any left links, ascend one
2399                  * level and look for either a right link off the point of
2400                  * ascent, or search for a left link upward again, repeating
2401                  * ascents until either case is true.
2402                  */
2403                 do {
2404                         while (! IS_ROOT(current)) {
2405                                 previous = current;
2406                                 current = PARENT(current);
2407
2408                                 if (LEFT(current) == previous) {
2409                                         successor = current;
2410                                         break;
2411                                 }
2412                         }
2413
2414                         if (successor == NULL) {
2415                                 /*
2416                                  * Reached the root without having traversed
2417                                  * any left pointers, so this level is done.
2418                                  */
2419                                 if (chain->level_count == 0)
2420                                         break;
2421
2422                                 current = chain->levels[--chain->level_count];
2423                                 new_origin = ISC_TRUE;
2424
2425                                 if (RIGHT(current) != NULL)
2426                                         break;
2427                         }
2428                 } while (successor == NULL);
2429         }
2430
2431         if (successor == NULL && RIGHT(current) != NULL) {
2432                 current = RIGHT(current);
2433
2434                 while (LEFT(current) != NULL)
2435                         current = LEFT(current);
2436
2437                 successor = current;
2438         }
2439
2440         if (successor != NULL) {
2441                 chain->end = successor;
2442
2443                 /*
2444                  * It is not necessary to use dns_rbtnodechain_current like
2445                  * the other functions because this function will never
2446                  * find a node in the topmost level.  This is because the
2447                  * root level will never be more than one name, and everything
2448                  * in the megatree is a successor to that node, down at
2449                  * the second level or below.
2450                  */
2451
2452                 if (name != NULL)
2453                         NODENAME(chain->end, name);
2454
2455                 if (new_origin) {
2456                         if (origin != NULL)
2457                                 result = chain_name(chain, origin, ISC_FALSE);
2458
2459                         if (result == ISC_R_SUCCESS)
2460                                 result = DNS_R_NEWORIGIN;
2461
2462                 } else
2463                         result = ISC_R_SUCCESS;
2464
2465         } else
2466                 result = ISC_R_NOMORE;
2467
2468         return (result);
2469 }
2470
2471 isc_result_t
2472 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2473                        dns_name_t *name, dns_name_t *origin)
2474
2475 {
2476         isc_result_t result;
2477
2478         REQUIRE(VALID_RBT(rbt));
2479         REQUIRE(VALID_CHAIN(chain));
2480
2481         dns_rbtnodechain_reset(chain);
2482
2483         chain->end = rbt->root;
2484
2485         result = dns_rbtnodechain_current(chain, name, origin, NULL);
2486
2487         if (result == ISC_R_SUCCESS)
2488                 result = DNS_R_NEWORIGIN;
2489
2490         return (result);
2491 }
2492
2493 isc_result_t
2494 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2495                        dns_name_t *name, dns_name_t *origin)
2496
2497 {
2498         isc_result_t result;
2499
2500         REQUIRE(VALID_RBT(rbt));
2501         REQUIRE(VALID_CHAIN(chain));
2502
2503         dns_rbtnodechain_reset(chain);
2504
2505         result = move_chain_to_last(chain, rbt->root);
2506         if (result != ISC_R_SUCCESS)
2507                 return (result);
2508
2509         result = dns_rbtnodechain_current(chain, name, origin, NULL);
2510
2511         if (result == ISC_R_SUCCESS)
2512                 result = DNS_R_NEWORIGIN;
2513
2514         return (result);
2515 }
2516
2517
2518 void
2519 dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
2520         /*
2521          * Free any dynamic storage associated with 'chain', and then
2522          * reinitialize 'chain'.
2523          */
2524
2525         REQUIRE(VALID_CHAIN(chain));
2526
2527         chain->end = NULL;
2528         chain->level_count = 0;
2529         chain->level_matches = 0;
2530 }
2531
2532 void
2533 dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
2534         /*
2535          * Free any dynamic storage associated with 'chain', and then
2536          * invalidate 'chain'.
2537          */
2538
2539         dns_rbtnodechain_reset(chain);
2540
2541         chain->magic = 0;
2542 }