contrib/bind-9.3/lib/dns/rbt.c

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