contrib/bind9/lib/dns/rbt.c

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