contrib/bind9/lib/dns/rbt.c

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