contrib/bind9/lib/dns/rbt.c

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