2 * Copyright (C) 2004 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2001, 2003 Internet Software Consortium.
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.
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.
18 /* $Id: rbt.c,v 1.115.2.5 2004/03/09 06:11:04 marka Exp $ */
20 /* Principal Authors: DCL */
25 #include <isc/platform.h>
26 #include <isc/print.h>
27 #include <isc/string.h>
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.
34 #define DNS_NAME_USEINLINE 1
36 #include <dns/fixedname.h>
38 #include <dns/result.h>
40 #define RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')
41 #define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
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.
48 #define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')
49 #define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
51 #define RBT_HASH_SIZE 64
55 #define RBT_HASH_SIZE 2 /* To give the reallocation code a workout. */
62 void (*data_deleter)(void *, void *);
64 unsigned int nodecount;
65 unsigned int hashsize;
66 dns_rbtnode_t ** hashtable;
74 * Elements of the rbtnode structure.
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)
92 * Structure elements from the rbtdb.c, not
93 * used as part of the rbt.c algorithms.
95 #define DIRTY(node) ((node)->dirty)
96 #define WILD(node) ((node)->wild)
97 #define LOCKNUM(node) ((node)->locknum)
98 #define REFS(node) ((node)->references)
101 * The variable length stuff stored after the node.
103 #define NAME(node) ((unsigned char *)((node) + 1))
104 #define OFFSETS(node) (NAME(node) + NAMELEN(node))
106 #define NODE_SIZE(node) (sizeof(*node) + \
107 NAMELEN(node) + OFFSETLEN(node) + PADBYTES(node))
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)
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).
124 #define ADD_LEVEL(chain, node) \
125 (chain)->levels[(chain)->level_count++] = (node)
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.
133 #define NODENAME(node, name) \
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; \
143 #ifdef DNS_RBT_USEHASH
145 inithash(dns_rbt_t *rbt);
151 * A little something to help out in GDB.
153 dns_name_t Name(dns_rbtnode_t *node);
155 Name(dns_rbtnode_t *node) {
158 dns_name_init(&name, NULL);
160 NODENAME(node, &name);
165 static void dns_rbt_printnodename(dns_rbtnode_t *node);
168 static inline dns_rbtnode_t *
169 find_up(dns_rbtnode_t *node) {
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.
177 for (root = node; ! IS_ROOT(root); root = PARENT(root))
180 return(PARENT(root));
183 static inline unsigned int
184 name_hash(dns_name_t *name) {
185 unsigned int nlabels;
189 if (dns_name_countlabels(name) == 1)
190 return (dns_name_hash(name, ISC_FALSE));
192 dns_name_init(&tname, NULL);
193 nlabels = dns_name_countlabels(name);
196 for ( ; nlabels > 0; nlabels--) {
197 dns_name_getlabelsequence(name, nlabels - 1, 1, &tname);
198 hash += dns_name_hash(&tname, ISC_FALSE);
204 #ifdef DNS_RBT_USEHASH
206 compute_node_hash(dns_rbtnode_t *node) {
209 dns_rbtnode_t *up_node;
211 dns_name_init(&name, NULL);
212 NODENAME(node, &name);
213 hash = name_hash(&name);
215 up_node = find_up(node);
217 hash += HASHVAL(up_node);
219 HASHVAL(node) = hash;
224 * Forward declarations.
227 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
229 #ifdef DNS_RBT_USEHASH
231 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
233 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
235 #define hash_node(rbt, node) (ISC_R_SUCCESS)
236 #define unhash_node(rbt, node)
240 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
242 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
245 dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
246 dns_rbtnode_t **rootp);
249 dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);
252 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);
255 dns_rbt_deletetreeflat(dns_rbt_t *rbt, dns_rbtnode_t **nodep);
258 * Initialize a red/black tree of trees.
261 dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
262 void *deleter_arg, dns_rbt_t **rbtp)
264 #ifdef DNS_RBT_USEHASH
270 REQUIRE(mctx != NULL);
271 REQUIRE(rbtp != NULL && *rbtp == NULL);
272 REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
274 rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
276 return (ISC_R_NOMEMORY);
279 rbt->data_deleter = deleter;
280 rbt->deleter_arg = deleter_arg;
283 rbt->hashtable = NULL;
285 #ifdef DNS_RBT_USEHASH
286 result = inithash(rbt);
287 if (result != ISC_R_SUCCESS) {
288 isc_mem_put(mctx, rbt, sizeof(*rbt));
293 rbt->magic = RBT_MAGIC;
297 return (ISC_R_SUCCESS);
301 * Deallocate a red/black tree of trees.
304 dns_rbt_destroy(dns_rbt_t **rbtp) {
305 RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
309 dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
312 REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
316 rbt->quantum = quantum;
318 dns_rbt_deletetreeflat(rbt, &rbt->root);
319 if (rbt->root != NULL)
320 return (ISC_R_QUOTA);
322 INSIST(rbt->nodecount == 0);
324 if (rbt->hashtable != NULL)
325 isc_mem_put(rbt->mctx, rbt->hashtable,
326 rbt->hashsize * sizeof(dns_rbtnode_t *));
330 isc_mem_put(rbt->mctx, rbt, sizeof(*rbt));
332 return (ISC_R_SUCCESS);
336 dns_rbt_nodecount(dns_rbt_t *rbt) {
337 REQUIRE(VALID_RBT(rbt));
338 return (rbt->nodecount);
341 static inline isc_result_t
342 chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
343 isc_boolean_t include_chain_end)
346 isc_result_t result = ISC_R_SUCCESS;
349 dns_name_init(&nodename, NULL);
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)
357 dns_name_reset(name);
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);
363 if (result != ISC_R_SUCCESS)
369 static inline isc_result_t
370 move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
373 * Go as far right and then down as much as possible,
374 * as long as the rightmost node has a down pointer.
376 while (RIGHT(node) != NULL)
379 if (DOWN(node) == NULL)
382 ADD_LEVEL(chain, node);
388 return (ISC_R_SUCCESS);
392 * Add 'name' to tree, initializing its data pointer with 'data'.
396 dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
398 * Does this thing have too many variables or what?
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;
410 REQUIRE(VALID_RBT(rbt));
411 REQUIRE(dns_name_isabsolute(name));
412 REQUIRE(nodep != NULL && *nodep == NULL);
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.
419 dns_fixedname_init(&fixedcopy);
420 add_name = dns_fixedname_name(&fixedcopy);
421 dns_name_clone(name, add_name);
423 if (rbt->root == NULL) {
424 result = create_node(rbt->mctx, add_name, &new_current);
425 if (result == ISC_R_SUCCESS) {
427 new_current->is_root = 1;
428 rbt->root = new_current;
429 *nodep = new_current;
430 hash_node(rbt, new_current);
435 dns_rbtnodechain_init(&chain, rbt->mctx);
437 dns_fixedname_init(&fixedprefix);
438 dns_fixedname_init(&fixedsuffix);
439 prefix = dns_fixedname_name(&fixedprefix);
440 suffix = dns_fixedname_name(&fixedsuffix);
443 INSIST(IS_ROOT(*root));
447 dns_name_init(¤t_name, current_offsets);
452 NODENAME(current, ¤t_name);
453 compared = dns_name_fullcompare(add_name, ¤t_name,
455 &common_labels, &common_bits);
457 if (compared == dns_namereln_equal) {
459 result = ISC_R_EXISTS;
464 if (compared == dns_namereln_none) {
468 child = LEFT(current);
470 } else if (order > 0) {
472 child = RIGHT(current);
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
488 if (compared == dns_namereln_subdomain) {
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
496 result = dns_name_split(add_name,
501 if (result != ISC_R_SUCCESS)
505 * Follow the down pointer (possibly NULL).
507 root = &DOWN(current);
509 INSIST(*root == NULL ||
511 PARENT(*root) == current));
514 child = DOWN(current);
515 ADD_LEVEL(&chain, current);
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.
526 INSIST(compared == dns_namereln_commonancestor
527 || compared == dns_namereln_contains);
530 * Ensure the number of levels in the tree
531 * does not exceed the number of logical
532 * levels allowed by DNSSEC.
534 * XXXDCL need a better error result?
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
543 if (chain.level_count ==
544 (sizeof(chain.levels) /
545 sizeof(*chain.levels))) {
546 result = ISC_R_NOSPACE;
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
556 result = dns_name_split(¤t_name,
561 if (result == ISC_R_SUCCESS)
562 result = create_node(rbt->mctx, suffix,
565 if (result != ISC_R_SUCCESS)
569 * Reproduce the tree attributes of the
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);
579 * Fix pointers that were to the current node.
581 if (parent != NULL) {
582 if (LEFT(parent) == current)
583 LEFT(parent) = new_current;
585 RIGHT(parent) = new_current;
587 if (LEFT(new_current) != NULL)
588 PARENT(LEFT(new_current)) =
590 if (RIGHT(new_current) != NULL)
591 PARENT(RIGHT(new_current)) =
593 if (*root == current)
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.
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.
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.
625 if (common_bits > 0) {
627 unsigned int skip_width;
628 unsigned int start_label =
629 dns_name_countlabels(¤t_name)
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.
647 prefix->offsets[start_label];
649 memcpy(NAME(current) + skip_width,
650 prefix->ndata + skip_width,
651 prefix->length - skip_width);
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.
662 dns_name_countlabels(add_name)
665 p = add_name->ndata +
666 add_name->offsets[start_label];
667 INSIST(*p == DNS_LABELTYPE_BITSTRING);
672 * A bitstring that was split would not
673 * result in a part of maximal length.
675 INSIST(add_bits != 0);
679 NAMELEN(current) = prefix->length;
680 OFFSETLEN(current) = prefix->labels;
681 memcpy(OFFSETS(current), prefix->offsets,
684 (current_name.length - prefix->length) +
685 (current_name.labels - prefix->labels);
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.
692 current->is_root = 1;
693 PARENT(current) = new_current;
694 DOWN(new_current) = current;
695 root = &DOWN(new_current);
697 ADD_LEVEL(&chain, new_current);
699 LEFT(current) = NULL;
700 RIGHT(current) = NULL;
703 ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
706 hash_node(rbt, new_current);
709 dns_name_countlabels(add_name) &&
710 common_bits == add_bits) {
712 * The name has been added by pushing
713 * the not-in-common parts down to
716 *nodep = new_current;
717 return (ISC_R_SUCCESS);
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.
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).
735 result = dns_name_split(add_name,
749 } while (child != NULL);
751 if (result == ISC_R_SUCCESS)
752 result = create_node(rbt->mctx, add_name, &new_current);
754 if (result == ISC_R_SUCCESS) {
755 dns_rbt_addonlevel(new_current, current, order, root);
757 *nodep = new_current;
758 hash_node(rbt, new_current);
765 * Add a name to the tree of trees, associating it with some data.
768 dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
772 REQUIRE(VALID_RBT(rbt));
773 REQUIRE(dns_name_isabsolute(name));
777 result = dns_rbt_addnode(rbt, name, &node);
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.
785 if (result == ISC_R_SUCCESS ||
786 (result == ISC_R_EXISTS && DATA(node) == NULL)) {
788 result = ISC_R_SUCCESS;
795 * Find the node for "name" in the tree of trees.
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,
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;
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));
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
824 options |= DNS_RBTFIND_NOPREDECESSOR;
826 dns_rbtnodechain_init(chain, rbt->mctx);
828 dns_rbtnodechain_reset(chain);
830 if (rbt->root == NULL)
831 return (ISC_R_NOTFOUND);
834 * Appease GCC about variables it incorrectly thinks are
835 * possibly used unitialized.
837 compared = dns_namereln_none;
838 last_compared = NULL;
841 dns_fixedname_init(&fixedcallbackname);
842 callback_name = dns_fixedname_name(&fixedcallbackname);
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.
851 dns_fixedname_init(&fixedsearchname);
852 search_name = dns_fixedname_name(&fixedsearchname);
853 dns_name_clone(name, search_name);
855 dns_name_init(¤t_name, NULL);
857 saved_result = ISC_R_SUCCESS;
859 current_root = rbt->root;
861 while (current != NULL) {
862 NODENAME(current, ¤t_name);
863 compared = dns_name_fullcompare(search_name, ¤t_name,
865 &common_labels, &common_bits);
866 last_compared = current;
868 if (compared == dns_namereln_equal)
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;
879 isc_boolean_t has_bitstring = ISC_FALSE;
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.
890 if (rbt->hashtable == NULL ||
891 current != current_root)
894 nlabels = dns_name_countlabels(search_name);
897 * current_root is the root of the current level, so
898 * it's parent is the same as it's "up" pointer.
900 up_current = PARENT(current_root);
901 dns_name_init(&hash_name, NULL);
904 dns_name_getlabelsequence(search_name,
906 tlabels, &hash_name);
907 hash = HASHVAL(up_current) + name_hash(&hash_name);
909 for (hnode = rbt->hashtable[hash % rbt->hashsize];
911 hnode = hnode->hashnext)
913 dns_name_t hnode_name;
915 if (hash != HASHVAL(hnode))
917 if (find_up(hnode) != up_current)
919 dns_name_init(&hnode_name, NULL);
920 NODENAME(hnode, &hnode_name);
921 if (dns_name_equal(&hnode_name, &hash_name))
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.
937 if (tlabels == nlabels) {
938 compared = dns_namereln_equal;
941 common_labels = tlabels;
943 compared = dns_namereln_subdomain;
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
959 if (has_bitstring == ISC_FALSE &&
960 hash_name.ndata[0] ==
961 DNS_LABELTYPE_BITSTRING)
962 has_bitstring = ISC_TRUE;
964 if (tlabels++ < nlabels)
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.
973 if (! has_bitstring) {
975 * Done with the search.
983 #endif /* DNS_RBT_USEHASH */
985 * Standard binary search tree movement.
988 current = LEFT(current);
990 current = RIGHT(current);
994 * The names have some common suffix labels.
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.
1000 if (compared == dns_namereln_subdomain) {
1003 * Whack off the current node's common parts
1004 * for the name to search in the next level.
1006 result = dns_name_split(search_name,
1010 if (result != ISC_R_SUCCESS) {
1011 dns_rbtnodechain_reset(chain);
1016 * This might be the closest enclosing name.
1018 if (DATA(current) != NULL ||
1019 (options & DNS_RBTFIND_EMPTYDATA) != 0)
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
1033 ADD_LEVEL(chain, current);
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.
1042 if (callback != NULL &&
1043 FINDCALLBACK(current)) {
1044 result = chain_name(chain,
1047 if (result != ISC_R_SUCCESS) {
1048 dns_rbtnodechain_reset(chain);
1052 result = (callback)(current,
1055 if (result != DNS_R_CONTINUE) {
1056 saved_result = result;
1058 * Treat this node as if it
1059 * had no down pointer.
1067 * Finally, head to the next tree level.
1069 current = DOWN(current);
1070 current_root = current;
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.
1079 INSIST(compared == dns_namereln_commonancestor
1080 || compared == dns_namereln_contains);
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.
1092 if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
1093 (DATA(current) != NULL ||
1094 (options & DNS_RBTFIND_EMPTYDATA) != 0)) {
1096 * Found an exact match.
1098 chain->end = current;
1099 chain->level_matches = chain->level_count;
1101 if (foundname != NULL)
1102 result = chain_name(chain, foundname, ISC_TRUE);
1104 result = ISC_R_SUCCESS;
1106 if (result == ISC_R_SUCCESS) {
1108 result = saved_result;
1113 * Did not find an exact match (or did not want one).
1115 if (*node != NULL) {
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.
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.
1126 chain->level_matches = chain->level_count - 1;
1128 while (chain->levels[chain->level_matches] != *node) {
1129 INSIST(chain->level_matches > 0);
1130 chain->level_matches--;
1133 if (foundname != NULL) {
1134 unsigned int saved_count = chain->level_count;
1136 chain->level_count = chain->level_matches + 1;
1138 result = chain_name(chain, foundname,
1141 chain->level_count = saved_count;
1143 result = ISC_R_SUCCESS;
1145 if (result == ISC_R_SUCCESS)
1146 result = DNS_R_PARTIALMATCH;
1149 result = ISC_R_NOTFOUND;
1151 if (current != NULL) {
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.
1163 INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
1164 ((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
1165 DATA(current) == NULL));
1166 chain->end = current;
1168 } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
1170 * Ensure the chain points nowhere.
1176 * Since there was no exact match, the chain argument
1177 * needs to be pointed at the DNSSEC predecessor of
1180 if (compared == dns_namereln_subdomain) {
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
1189 INSIST(chain->level_count > 0);
1190 INSIST(chain->level_matches <
1191 chain->level_count);
1193 chain->levels[--chain->level_count];
1196 isc_result_t result2;
1199 * Point current to the node that stopped
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.
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
1215 if (compared == dns_namereln_none)
1216 current = last_compared;
1220 while (current != NULL) {
1221 NODENAME(current, ¤t_name);
1222 compared = dns_name_fullcompare(
1229 last_compared = current;
1232 * Standard binary search movement.
1235 current = LEFT(current);
1237 current = RIGHT(current);
1241 current = last_compared;
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).
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.
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
1271 if (DOWN(current) != NULL) {
1272 ADD_LEVEL(chain, current);
1275 move_chain_to_last(chain,
1278 if (result2 != ISC_R_SUCCESS)
1282 * Ah, the pure and simple
1283 * case. The stop node is the
1286 chain->end = current;
1291 chain->end = current;
1293 result2 = dns_rbtnodechain_prev(chain,
1296 if (result2 == ISC_R_SUCCESS ||
1297 result2 == DNS_R_NEWORIGIN)
1299 else if (result2 == ISC_R_NOMORE)
1301 * There is no predecessor.
1303 dns_rbtnodechain_reset(chain);
1316 * Get the data pointer associated with 'name'.
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;
1324 REQUIRE(data != NULL && *data == NULL);
1326 result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
1327 options, NULL, NULL);
1330 (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
1333 result = ISC_R_NOTFOUND;
1339 * Delete a name from the tree of trees.
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;
1346 REQUIRE(VALID_RBT(rbt));
1347 REQUIRE(dns_name_isabsolute(name));
1350 * First, find the node.
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.
1360 * ->dirty, ->locknum and ->references are ignored; they are
1361 * solely the province of rbtdb.c.
1363 result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
1364 DNS_RBTFIND_NOOPTIONS, NULL, NULL);
1366 if (result == ISC_R_SUCCESS) {
1367 if (DATA(node) != NULL)
1368 result = dns_rbt_deletenode(rbt, node, recurse);
1370 result = ISC_R_NOTFOUND;
1372 } else if (result == DNS_R_PARTIALMATCH)
1373 result = ISC_R_NOTFOUND;
1379 * Remove a node from the tree of trees.
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).
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.
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.
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. */
1414 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
1416 dns_rbtnode_t *parent;
1418 REQUIRE(VALID_RBT(rbt));
1419 REQUIRE(node != NULL);
1421 if (DOWN(node) != NULL) {
1423 RUNTIME_CHECK(dns_rbt_deletetree(rbt, DOWN(node))
1426 if (DATA(node) != NULL && rbt->data_deleter != NULL)
1427 rbt->data_deleter(DATA(node),
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).
1439 return (ISC_R_SUCCESS);
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
1448 parent = find_up(node);
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.
1455 dns_rbt_deletefromlevel(node, parent == NULL ? &rbt->root :
1458 if (DATA(node) != NULL && rbt->data_deleter != NULL)
1459 rbt->data_deleter(DATA(node), rbt->deleter_arg);
1461 unhash_node(rbt, node);
1462 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
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.
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.
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
1489 * This function never fails.
1491 return (ISC_R_SUCCESS);
1495 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1497 REQUIRE(node != NULL);
1498 REQUIRE(name != NULL);
1499 REQUIRE(name->offsets == NULL);
1501 NODENAME(node, name);
1505 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1507 isc_result_t result;
1509 REQUIRE(node != NULL);
1510 REQUIRE(name != NULL);
1511 REQUIRE(name->buffer != NULL);
1513 dns_name_init(¤t, NULL);
1514 dns_name_reset(name);
1517 INSIST(node != NULL);
1519 NODENAME(node, ¤t);
1521 result = dns_name_concatenate(name, ¤t, name, NULL);
1522 if (result != ISC_R_SUCCESS)
1525 node = find_up(node);
1526 } while (! dns_name_isabsolute(name));
1532 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
1534 dns_fixedname_t fixedname;
1536 isc_result_t result;
1538 REQUIRE(node != NULL);
1539 REQUIRE(printname != NULL);
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);
1547 snprintf(printname, size, "<error building name: %s>",
1548 dns_result_totext(result));
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;
1559 REQUIRE(name->offsets != NULL);
1561 dns_name_toregion(name, ®ion);
1562 labels = dns_name_countlabels(name);
1566 * Allocate space for the node structure, the name, and the offsets.
1568 node = (dns_rbtnode_t *)isc_mem_get(mctx, sizeof(*node) +
1569 region.length + labels);
1572 return (ISC_R_NOMEMORY);
1575 PARENT(node) = NULL;
1580 #ifdef DNS_RBT_USEHASH
1581 HASHNEXT(node) = NULL;
1589 node->find_callback = 0;
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.
1600 * The offsets table could be made smaller by eliminating the
1601 * first offset, which is always 0. This requires changes to
1604 NAMELEN(node) = region.length;
1606 OFFSETLEN(node) = labels;
1607 ATTRS(node) = name->attributes;
1609 memcpy(NAME(node), region.base, region.length);
1610 memcpy(OFFSETS(node), name->offsets, labels);
1614 return (ISC_R_SUCCESS);
1617 #ifdef DNS_RBT_USEHASH
1619 hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1622 compute_node_hash(node);
1624 hash = HASHVAL(node) % rbt->hashsize;
1625 HASHNEXT(node) = rbt->hashtable[hash];
1627 rbt->hashtable[hash] = node;
1631 inithash(dns_rbt_t *rbt) {
1634 rbt->hashsize = RBT_HASH_SIZE;
1635 bytes = rbt->hashsize * sizeof(dns_rbtnode_t *);
1636 rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
1638 if (rbt->hashtable == NULL)
1639 return (ISC_R_NOMEMORY);
1641 memset(rbt->hashtable, 0, bytes);
1643 return (ISC_R_SUCCESS);
1647 rehash(dns_rbt_t *rbt) {
1648 unsigned int oldsize;
1649 dns_rbtnode_t **oldtable;
1650 dns_rbtnode_t *node;
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;
1665 for (i = 0; i < rbt->hashsize; i++)
1666 rbt->hashtable[i] = NULL;
1668 for (i = 0; i < oldsize; 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;
1679 isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
1683 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1685 if (rbt->nodecount >= (rbt->hashsize * 3))
1688 hash_add_node(rbt, node);
1692 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1693 unsigned int bucket;
1694 dns_rbtnode_t *bucket_node;
1696 if (rbt->hashtable != NULL) {
1697 bucket = HASHVAL(node) % rbt->hashsize;
1698 bucket_node = rbt->hashtable[bucket];
1700 if (bucket_node == node)
1701 rbt->hashtable[bucket] = HASHNEXT(node);
1703 while (HASHNEXT(bucket_node) != node) {
1704 INSIST(HASHNEXT(bucket_node) != NULL);
1705 bucket_node = HASHNEXT(bucket_node);
1707 HASHNEXT(bucket_node) = HASHNEXT(node);
1711 #endif /* DNS_RBT_USEHASH */
1714 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1715 dns_rbtnode_t *child;
1717 REQUIRE(node != NULL);
1718 REQUIRE(rootp != NULL);
1720 child = RIGHT(node);
1721 INSIST(child != NULL);
1723 RIGHT(node) = LEFT(child);
1724 if (LEFT(child) != NULL)
1725 PARENT(LEFT(child)) = node;
1729 PARENT(child) = PARENT(node);
1731 if (IS_ROOT(node)) {
1737 if (LEFT(PARENT(node)) == node)
1738 LEFT(PARENT(node)) = child;
1740 RIGHT(PARENT(node)) = child;
1743 PARENT(node) = child;
1747 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1748 dns_rbtnode_t *child;
1750 REQUIRE(node != NULL);
1751 REQUIRE(rootp != NULL);
1754 INSIST(child != NULL);
1756 LEFT(node) = RIGHT(child);
1757 if (RIGHT(child) != NULL)
1758 PARENT(RIGHT(child)) = node;
1759 RIGHT(child) = node;
1762 PARENT(child) = PARENT(node);
1764 if (IS_ROOT(node)) {
1770 if (LEFT(PARENT(node)) == node)
1771 LEFT(PARENT(node)) = child;
1773 RIGHT(PARENT(node)) = child;
1776 PARENT(node) = child;
1780 * This is the real workhorse of the insertion code, because it does the
1781 * true red/black tree on a single level.
1784 dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
1785 dns_rbtnode_t **rootp)
1787 dns_rbtnode_t *child, *root, *parent, *grandparent;
1788 dns_name_t add_name, current_name;
1789 dns_offsets_t add_offsets, current_offsets;
1791 REQUIRE(rootp != NULL);
1792 REQUIRE(node != NULL && LEFT(node) == NULL && RIGHT(node) == NULL);
1793 REQUIRE(current != NULL);
1798 * First node of a level.
1802 PARENT(node) = current;
1809 dns_name_init(&add_name, add_offsets);
1810 NODENAME(node, &add_name);
1812 dns_name_init(¤t_name, current_offsets);
1813 NODENAME(current, ¤t_name);
1816 INSIST(LEFT(current) == NULL);
1817 LEFT(current) = node;
1819 INSIST(RIGHT(current) == NULL);
1820 RIGHT(current) = node;
1823 INSIST(PARENT(node) == NULL);
1824 PARENT(node) = current;
1828 while (node != root && IS_RED(PARENT(node))) {
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.
1835 parent = PARENT(node);
1836 grandparent = PARENT(parent);
1838 if (parent == LEFT(grandparent)) {
1839 child = RIGHT(grandparent);
1840 if (child != NULL && IS_RED(child)) {
1843 MAKE_RED(grandparent);
1846 if (node == RIGHT(parent)) {
1847 rotate_left(parent, &root);
1849 parent = PARENT(node);
1850 grandparent = PARENT(parent);
1853 MAKE_RED(grandparent);
1854 rotate_right(grandparent, &root);
1857 child = LEFT(grandparent);
1858 if (child != NULL && IS_RED(child)) {
1861 MAKE_RED(grandparent);
1864 if (node == LEFT(parent)) {
1865 rotate_right(parent, &root);
1867 parent = PARENT(node);
1868 grandparent = PARENT(parent);
1871 MAKE_RED(grandparent);
1872 rotate_left(grandparent, &root);
1878 ENSURE(IS_ROOT(root));
1885 * This is the real workhorse of the deletion code, because it does the
1886 * true red/black tree on a single level.
1889 dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp) {
1890 dns_rbtnode_t *child, *sibling, *parent;
1891 dns_rbtnode_t *successor;
1893 REQUIRE(delete != NULL);
1896 * Verify that the parent history is (apparently) correct.
1898 INSIST((IS_ROOT(delete) && *rootp == delete) ||
1899 (! IS_ROOT(delete) &&
1900 (LEFT(PARENT(delete)) == delete ||
1901 RIGHT(PARENT(delete)) == delete)));
1905 if (LEFT(delete) == NULL) {
1906 if (RIGHT(delete) == NULL) {
1907 if (IS_ROOT(delete)) {
1909 * This is the only item in the tree.
1916 * This node has one child, on the right.
1918 child = RIGHT(delete);
1920 } else if (RIGHT(delete) == NULL)
1922 * This node has one child, on the left.
1924 child = LEFT(delete);
1927 dns_rbtnode_t holder, *tmp = &holder;
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.
1935 successor = RIGHT(delete);
1936 while (LEFT(successor) != NULL)
1937 successor = LEFT(successor);
1940 * The successor cannot possibly have a left child;
1941 * if there is any child, it is on the right.
1943 if (RIGHT(successor) != NULL)
1944 child = RIGHT(successor);
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.
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.
1960 memcpy(tmp, successor, sizeof(dns_rbtnode_t));
1962 if (IS_ROOT(delete)) {
1964 successor->is_root = ISC_TRUE;
1965 delete->is_root = ISC_FALSE;
1968 if (LEFT(PARENT(delete)) == delete)
1969 LEFT(PARENT(delete)) = successor;
1971 RIGHT(PARENT(delete)) = successor;
1973 PARENT(successor) = PARENT(delete);
1974 LEFT(successor) = LEFT(delete);
1975 RIGHT(successor) = RIGHT(delete);
1976 COLOR(successor) = COLOR(delete);
1978 if (LEFT(successor) != NULL)
1979 PARENT(LEFT(successor)) = successor;
1980 if (RIGHT(successor) != successor)
1981 PARENT(RIGHT(successor)) = successor;
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.
1988 INSIST(! IS_ROOT(delete));
1990 if (PARENT(tmp) == delete) {
1992 * Node being deleted was successor's parent.
1994 RIGHT(successor) = delete;
1995 PARENT(delete) = successor;
1998 LEFT(PARENT(tmp)) = delete;
1999 PARENT(delete) = PARENT(tmp);
2003 * Original location of successor node has no left.
2005 LEFT(delete) = NULL;
2006 RIGHT(delete) = RIGHT(tmp);
2007 COLOR(delete) = COLOR(tmp);
2011 * Remove the node by removing the links from its parent.
2013 if (! IS_ROOT(delete)) {
2014 if (LEFT(PARENT(delete)) == delete)
2015 LEFT(PARENT(delete)) = child;
2017 RIGHT(PARENT(delete)) = child;
2020 PARENT(child) = PARENT(delete);
2024 * This is the root being deleted, and at this point
2025 * it is known to have just one child.
2029 PARENT(child) = PARENT(delete);
2033 * Fix color violations.
2035 if (IS_BLACK(delete)) {
2036 parent = PARENT(delete);
2038 while (child != *rootp && IS_BLACK(child)) {
2039 INSIST(child == NULL || ! IS_ROOT(child));
2041 if (LEFT(parent) == child) {
2042 sibling = RIGHT(parent);
2044 if (IS_RED(sibling)) {
2045 MAKE_BLACK(sibling);
2047 rotate_left(parent, rootp);
2048 sibling = RIGHT(parent);
2051 if (IS_BLACK(LEFT(sibling)) &&
2052 IS_BLACK(RIGHT(sibling))) {
2058 if (IS_BLACK(RIGHT(sibling))) {
2059 MAKE_BLACK(LEFT(sibling));
2061 rotate_right(sibling, rootp);
2062 sibling = RIGHT(parent);
2065 COLOR(sibling) = COLOR(parent);
2067 MAKE_BLACK(RIGHT(sibling));
2068 rotate_left(parent, rootp);
2074 * Child is parent's right child.
2075 * Everything is doen the same as above,
2078 sibling = LEFT(parent);
2080 if (IS_RED(sibling)) {
2081 MAKE_BLACK(sibling);
2083 rotate_right(parent, rootp);
2084 sibling = LEFT(parent);
2087 if (IS_BLACK(LEFT(sibling)) &&
2088 IS_BLACK(RIGHT(sibling))) {
2093 if (IS_BLACK(LEFT(sibling))) {
2094 MAKE_BLACK(RIGHT(sibling));
2096 rotate_left(sibling, rootp);
2097 sibling = LEFT(parent);
2100 COLOR(sibling) = COLOR(parent);
2102 MAKE_BLACK(LEFT(sibling));
2103 rotate_right(parent, rootp);
2108 parent = PARENT(child);
2117 * This should only be used on the root of a tree, because no color fixup
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.
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.
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));
2139 if (LEFT(node) != NULL) {
2140 result = dns_rbt_deletetree(rbt, LEFT(node));
2141 if (result != ISC_R_SUCCESS)
2145 if (RIGHT(node) != NULL) {
2146 result = dns_rbt_deletetree(rbt, RIGHT(node));
2147 if (result != ISC_R_SUCCESS)
2151 if (DOWN(node) != NULL) {
2152 result = dns_rbt_deletetree(rbt, DOWN(node));
2153 if (result != ISC_R_SUCCESS)
2158 if (result != ISC_R_SUCCESS)
2160 if (rbt->quantum != 0 && --rbt->quantum == 0)
2161 return (ISC_R_QUOTA);
2163 if (DATA(node) != NULL && rbt->data_deleter != NULL)
2164 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2166 unhash_node(rbt, node);
2167 #if DNS_RBT_USEMAGIC
2170 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
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));
2188 if (LEFT(node) != NULL) {
2192 if (RIGHT(node) != NULL) {
2196 if (DOWN(node) != NULL) {
2201 if (DATA(node) != NULL && rbt->data_deleter != NULL)
2202 rbt->data_deleter(DATA(node), rbt->deleter_arg);
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;
2214 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2217 if (rbt->quantum != 0 && --rbt->quantum == 0) {
2225 dns_rbt_indent(int depth) {
2228 for (i = 0; i < depth; i++)
2233 dns_rbt_printnodename(dns_rbtnode_t *node) {
2234 isc_buffer_t target;
2238 dns_offsets_t offsets;
2240 r.length = NAMELEN(node);
2241 r.base = NAME(node);
2243 dns_name_init(&name, offsets);
2244 dns_name_fromregion(&name, &r);
2246 isc_buffer_init(&target, buffer, 255);
2249 * ISC_FALSE means absolute names have the final dot added.
2251 dns_name_totext(&name, ISC_FALSE, &target);
2253 printf("%.*s", (int)target.used, (char *)target.base);
2257 dns_rbt_printtree(dns_rbtnode_t *root, dns_rbtnode_t *parent, int depth) {
2258 dns_rbt_indent(depth);
2261 dns_rbt_printnodename(root);
2262 printf(" (%s", IS_RED(root) ? "RED" : "black");
2265 dns_rbt_printnodename(parent);
2268 if ((! IS_ROOT(root) && PARENT(root) != parent) ||
2269 ( IS_ROOT(root) && depth > 0 &&
2270 DOWN(PARENT(root)) != root)) {
2272 printf(" (BAD parent pointer! -> ");
2273 if (PARENT(root) != NULL)
2274 dns_rbt_printnodename(PARENT(root));
2286 dns_rbt_indent(depth);
2287 printf("++ BEG down from ");
2288 dns_rbt_printnodename(root);
2290 dns_rbt_printtree(DOWN(root), NULL, depth);
2291 dns_rbt_indent(depth);
2292 printf("-- END down from ");
2293 dns_rbt_printnodename(root);
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);
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);
2310 dns_rbt_printall(dns_rbt_t *rbt) {
2311 REQUIRE(VALID_RBT(rbt));
2313 dns_rbt_printtree(rbt->root, NULL, 0);
2321 dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
2323 * Initialize 'chain'.
2326 REQUIRE(chain != NULL);
2330 chain->level_count = 0;
2331 chain->level_matches = 0;
2333 chain->magic = CHAIN_MAGIC;
2337 dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
2338 dns_name_t *origin, dns_rbtnode_t **node)
2340 isc_result_t result = ISC_R_SUCCESS;
2342 REQUIRE(VALID_CHAIN(chain));
2347 if (chain->end == NULL)
2348 return (ISC_R_NOTFOUND);
2351 NODENAME(chain->end, name);
2353 if (chain->level_count == 0) {
2355 * Names in the top level tree are all absolute.
2356 * Always make 'name' relative.
2358 INSIST(dns_name_isabsolute(name));
2361 * This is cheaper than dns_name_getlabelsequence().
2365 name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
2369 if (origin != NULL) {
2370 if (chain->level_count > 0)
2371 result = chain_name(chain, origin, ISC_FALSE);
2373 result = dns_name_copy(dns_rootname, origin, NULL);
2380 dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
2383 dns_rbtnode_t *current, *previous, *predecessor;
2384 isc_result_t result = ISC_R_SUCCESS;
2385 isc_boolean_t new_origin = ISC_FALSE;
2387 REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2391 current = chain->end;
2393 if (LEFT(current) != NULL) {
2395 * Moving left one then right as far as possible is the
2396 * previous node, at least for this level.
2398 current = LEFT(current);
2400 while (RIGHT(current) != NULL)
2401 current = RIGHT(current);
2403 predecessor = current;
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
2412 while (! IS_ROOT(current)) {
2414 current = PARENT(current);
2416 if (RIGHT(current) == previous) {
2417 predecessor = current;
2423 if (predecessor != NULL) {
2425 * Found a predecessor node in this level. It might not
2426 * really be the predecessor, however.
2428 if (DOWN(predecessor) != NULL) {
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.
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
2441 ADD_LEVEL(chain, predecessor);
2442 predecessor = DOWN(predecessor);
2444 /* XXX DCL duplicated from above; clever
2445 * way to unduplicate? */
2447 while (RIGHT(predecessor) != NULL)
2448 predecessor = RIGHT(predecessor);
2449 } while (DOWN(predecessor) != NULL);
2451 /* XXX DCL probably needs work on the concept */
2453 new_origin = ISC_TRUE;
2456 } else if (chain->level_count > 0) {
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.
2463 INSIST(chain->level_count > 0 && IS_ROOT(current));
2464 predecessor = chain->levels[--chain->level_count];
2466 /* XXX DCL probably needs work on the concept */
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.
2472 if (origin != NULL &&
2473 (chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
2474 new_origin = ISC_TRUE;
2477 if (predecessor != NULL) {
2478 chain->end = predecessor;
2481 result = dns_rbtnodechain_current(chain, name, origin,
2483 if (result == ISC_R_SUCCESS)
2484 result = DNS_R_NEWORIGIN;
2487 result = dns_rbtnodechain_current(chain, name, NULL,
2491 result = ISC_R_NOMORE;
2497 dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
2500 dns_rbtnode_t *current, *previous, *successor;
2501 isc_result_t result = ISC_R_SUCCESS;
2502 isc_boolean_t new_origin = ISC_FALSE;
2504 REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2508 current = chain->end;
2511 * If there is a level below this node, the next node is the leftmost
2512 * node of the next level.
2514 if (DOWN(current) != NULL) {
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.
2520 if (chain->level_count > 0 ||
2521 OFFSETLEN(current) > 1)
2522 new_origin = ISC_TRUE;
2524 ADD_LEVEL(chain, current);
2525 current = DOWN(current);
2527 while (LEFT(current) != NULL)
2528 current = LEFT(current);
2530 successor = current;
2532 } else if (RIGHT(current) == NULL) {
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.
2544 while (! IS_ROOT(current)) {
2546 current = PARENT(current);
2548 if (LEFT(current) == previous) {
2549 successor = current;
2554 if (successor == NULL) {
2556 * Reached the root without having traversed
2557 * any left pointers, so this level is done.
2559 if (chain->level_count == 0)
2562 current = chain->levels[--chain->level_count];
2563 new_origin = ISC_TRUE;
2565 if (RIGHT(current) != NULL)
2568 } while (successor == NULL);
2571 if (successor == NULL && RIGHT(current) != NULL) {
2572 current = RIGHT(current);
2574 while (LEFT(current) != NULL)
2575 current = LEFT(current);
2577 successor = current;
2580 if (successor != NULL) {
2581 chain->end = successor;
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.
2593 NODENAME(chain->end, name);
2597 result = chain_name(chain, origin, ISC_FALSE);
2599 if (result == ISC_R_SUCCESS)
2600 result = DNS_R_NEWORIGIN;
2603 result = ISC_R_SUCCESS;
2606 result = ISC_R_NOMORE;
2612 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2613 dns_name_t *name, dns_name_t *origin)
2616 isc_result_t result;
2618 REQUIRE(VALID_RBT(rbt));
2619 REQUIRE(VALID_CHAIN(chain));
2621 dns_rbtnodechain_reset(chain);
2623 chain->end = rbt->root;
2625 result = dns_rbtnodechain_current(chain, name, origin, NULL);
2627 if (result == ISC_R_SUCCESS)
2628 result = DNS_R_NEWORIGIN;
2634 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2635 dns_name_t *name, dns_name_t *origin)
2638 isc_result_t result;
2640 REQUIRE(VALID_RBT(rbt));
2641 REQUIRE(VALID_CHAIN(chain));
2643 dns_rbtnodechain_reset(chain);
2645 result = move_chain_to_last(chain, rbt->root);
2646 if (result != ISC_R_SUCCESS)
2649 result = dns_rbtnodechain_current(chain, name, origin, NULL);
2651 if (result == ISC_R_SUCCESS)
2652 result = DNS_R_NEWORIGIN;
2659 dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
2661 * Free any dynamic storage associated with 'chain', and then
2662 * reinitialize 'chain'.
2665 REQUIRE(VALID_CHAIN(chain));
2668 chain->level_count = 0;
2669 chain->level_matches = 0;
2673 dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
2675 * Free any dynamic storage associated with 'chain', and then
2676 * invalidate 'chain'.
2679 dns_rbtnodechain_reset(chain);