contrib/bind-9.2.4rc7/lib/dns/rbt.c

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