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