contrib/bind9/lib/dns/rbt.c

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