2 * Copyright (C) 2004, 2005 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-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.128.18.7 2005/10/13 01:26:06 marka Exp $ */
22 /* Principal Authors: DCL */
27 #include <isc/platform.h>
28 #include <isc/print.h>
29 #include <isc/refcount.h>
30 #include <isc/string.h>
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.
37 #define DNS_NAME_USEINLINE 1
39 #include <dns/fixedname.h>
41 #include <dns/result.h>
43 #define RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')
44 #define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
47 * XXXDCL Since parent pointers were added in again, I could remove all of the
48 * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
49 * _lastnode. This would involve pretty major change to the API.
51 #define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')
52 #define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
54 #define RBT_HASH_SIZE 64
58 #define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
65 void (*data_deleter)(void *, void *);
67 unsigned int nodecount;
68 unsigned int hashsize;
69 dns_rbtnode_t ** hashtable;
76 * Elements of the rbtnode structure.
78 #define PARENT(node) ((node)->parent)
79 #define LEFT(node) ((node)->left)
80 #define RIGHT(node) ((node)->right)
81 #define DOWN(node) ((node)->down)
82 #define DATA(node) ((node)->data)
83 #define HASHNEXT(node) ((node)->hashnext)
84 #define HASHVAL(node) ((node)->hashval)
85 #define COLOR(node) ((node)->color)
86 #define NAMELEN(node) ((node)->namelen)
87 #define OFFSETLEN(node) ((node)->offsetlen)
88 #define ATTRS(node) ((node)->attributes)
89 #define PADBYTES(node) ((node)->padbytes)
90 #define IS_ROOT(node) ISC_TF((node)->is_root == 1)
91 #define FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)
94 * Structure elements from the rbtdb.c, not
95 * used as part of the rbt.c algorithms.
97 #define DIRTY(node) ((node)->dirty)
98 #define WILD(node) ((node)->wild)
99 #define LOCKNUM(node) ((node)->locknum)
102 * The variable length stuff stored after the node.
104 #define NAME(node) ((unsigned char *)((node) + 1))
105 #define OFFSETS(node) (NAME(node) + NAMELEN(node))
107 #define NODE_SIZE(node) (sizeof(*node) + \
108 NAMELEN(node) + OFFSETLEN(node) + PADBYTES(node))
113 #define IS_RED(node) ((node) != NULL && (node)->color == RED)
114 #define IS_BLACK(node) ((node) == NULL || (node)->color == BLACK)
115 #define MAKE_RED(node) ((node)->color = RED)
116 #define MAKE_BLACK(node) ((node)->color = BLACK)
121 * The "ancestors" member of chains were removed, with their job now
122 * being wholy handled by parent pointers (which didn't exist, because
123 * of memory concerns, when chains were first implemented).
125 #define ADD_LEVEL(chain, node) \
126 (chain)->levels[(chain)->level_count++] = (node)
129 * The following macros directly access normally private name variables.
130 * These macros are used to avoid a lot of function calls in the critical
131 * path of the tree traversal code.
134 #define NODENAME(node, name) \
136 (name)->length = NAMELEN(node); \
137 (name)->labels = OFFSETLEN(node); \
138 (name)->ndata = NAME(node); \
139 (name)->offsets = OFFSETS(node); \
140 (name)->attributes = ATTRS(node); \
141 (name)->attributes |= DNS_NAMEATTR_READONLY; \
144 #ifdef DNS_RBT_USEHASH
146 inithash(dns_rbt_t *rbt);
152 * A little something to help out in GDB.
154 dns_name_t Name(dns_rbtnode_t *node);
156 Name(dns_rbtnode_t *node) {
159 dns_name_init(&name, NULL);
161 NODENAME(node, &name);
166 static void dns_rbt_printnodename(dns_rbtnode_t *node);
169 static inline dns_rbtnode_t *
170 find_up(dns_rbtnode_t *node) {
174 * Return the node in the level above the argument node that points
175 * to the level the argument node is in. If the argument node is in
176 * the top level, the return value is NULL.
178 for (root = node; ! IS_ROOT(root); root = PARENT(root))
181 return (PARENT(root));
185 * Forward declarations.
188 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
190 #ifdef DNS_RBT_USEHASH
192 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
194 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
196 #define hash_node(rbt, node, name) (ISC_R_SUCCESS)
197 #define unhash_node(rbt, node)
201 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
203 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
206 dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
207 dns_rbtnode_t **rootp);
210 dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);
213 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);
216 dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum,
217 dns_rbtnode_t **nodep);
220 * Initialize a red/black tree of trees.
223 dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
224 void *deleter_arg, dns_rbt_t **rbtp)
226 #ifdef DNS_RBT_USEHASH
232 REQUIRE(mctx != NULL);
233 REQUIRE(rbtp != NULL && *rbtp == NULL);
234 REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
236 rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
238 return (ISC_R_NOMEMORY);
241 rbt->data_deleter = deleter;
242 rbt->deleter_arg = deleter_arg;
245 rbt->hashtable = NULL;
247 #ifdef DNS_RBT_USEHASH
248 result = inithash(rbt);
249 if (result != ISC_R_SUCCESS) {
250 isc_mem_put(mctx, rbt, sizeof(*rbt));
254 rbt->magic = RBT_MAGIC;
258 return (ISC_R_SUCCESS);
262 * Deallocate a red/black tree of trees.
265 dns_rbt_destroy(dns_rbt_t **rbtp) {
266 RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
270 dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
273 REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
277 dns_rbt_deletetreeflat(rbt, quantum, &rbt->root);
278 if (rbt->root != NULL)
279 return (ISC_R_QUOTA);
281 INSIST(rbt->nodecount == 0);
283 if (rbt->hashtable != NULL)
284 isc_mem_put(rbt->mctx, rbt->hashtable,
285 rbt->hashsize * sizeof(dns_rbtnode_t *));
289 isc_mem_put(rbt->mctx, rbt, sizeof(*rbt));
291 return (ISC_R_SUCCESS);
295 dns_rbt_nodecount(dns_rbt_t *rbt) {
296 REQUIRE(VALID_RBT(rbt));
297 return (rbt->nodecount);
300 static inline isc_result_t
301 chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
302 isc_boolean_t include_chain_end)
305 isc_result_t result = ISC_R_SUCCESS;
308 dns_name_init(&nodename, NULL);
310 if (include_chain_end && chain->end != NULL) {
311 NODENAME(chain->end, &nodename);
312 result = dns_name_copy(&nodename, name, NULL);
313 if (result != ISC_R_SUCCESS)
316 dns_name_reset(name);
318 for (i = (int)chain->level_count - 1; i >= 0; i--) {
319 NODENAME(chain->levels[i], &nodename);
320 result = dns_name_concatenate(name, &nodename, name, NULL);
322 if (result != ISC_R_SUCCESS)
328 static inline isc_result_t
329 move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
332 * Go as far right and then down as much as possible,
333 * as long as the rightmost node has a down pointer.
335 while (RIGHT(node) != NULL)
338 if (DOWN(node) == NULL)
341 ADD_LEVEL(chain, node);
347 return (ISC_R_SUCCESS);
351 * Add 'name' to tree, initializing its data pointer with 'data'.
355 dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
357 * Does this thing have too many variables or what?
359 dns_rbtnode_t **root, *parent, *child, *current, *new_current;
360 dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
361 dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
362 dns_offsets_t current_offsets;
363 dns_namereln_t compared;
364 isc_result_t result = ISC_R_SUCCESS;
365 dns_rbtnodechain_t chain;
366 unsigned int common_labels;
367 unsigned int nlabels, hlabels;
370 REQUIRE(VALID_RBT(rbt));
371 REQUIRE(dns_name_isabsolute(name));
372 REQUIRE(nodep != NULL && *nodep == NULL);
375 * Create a copy of the name so the original name structure is
378 dns_fixedname_init(&fixedcopy);
379 add_name = dns_fixedname_name(&fixedcopy);
380 dns_name_clone(name, add_name);
382 if (rbt->root == NULL) {
383 result = create_node(rbt->mctx, add_name, &new_current);
384 if (result == ISC_R_SUCCESS) {
386 new_current->is_root = 1;
387 rbt->root = new_current;
388 *nodep = new_current;
389 hash_node(rbt, new_current, name);
394 dns_rbtnodechain_init(&chain, rbt->mctx);
396 dns_fixedname_init(&fixedprefix);
397 dns_fixedname_init(&fixedsuffix);
398 prefix = dns_fixedname_name(&fixedprefix);
399 suffix = dns_fixedname_name(&fixedsuffix);
402 INSIST(IS_ROOT(*root));
406 dns_name_init(¤t_name, current_offsets);
407 dns_fixedname_init(&fnewname);
408 new_name = dns_fixedname_name(&fnewname);
409 nlabels = dns_name_countlabels(name);
415 NODENAME(current, ¤t_name);
416 compared = dns_name_fullcompare(add_name, ¤t_name,
417 &order, &common_labels);
419 if (compared == dns_namereln_equal) {
421 result = ISC_R_EXISTS;
426 if (compared == dns_namereln_none) {
430 child = LEFT(current);
432 } else if (order > 0) {
434 child = RIGHT(current);
440 * This name has some suffix in common with the
441 * name at the current node. If the name at
442 * the current node is shorter, that means the
443 * new name should be in a subtree. If the
444 * name at the current node is longer, that means
445 * the down pointer to this tree should point
446 * to a new tree that has the common suffix, and
447 * the non-common parts of these two names should
450 hlabels += common_labels;
451 if (compared == dns_namereln_subdomain) {
453 * All of the existing labels are in common,
454 * so the new name is in a subtree.
455 * Whack off the common labels for the
456 * not-in-common part to be searched for
459 dns_name_split(add_name, common_labels,
463 * Follow the down pointer (possibly NULL).
465 root = &DOWN(current);
467 INSIST(*root == NULL ||
469 PARENT(*root) == current));
472 child = DOWN(current);
473 ADD_LEVEL(&chain, current);
477 * The number of labels in common is fewer
478 * than the number of labels at the current
479 * node, so the current node must be adjusted
480 * to have just the common suffix, and a down
481 * pointer made to a new tree.
484 INSIST(compared == dns_namereln_commonancestor
485 || compared == dns_namereln_contains);
488 * Ensure the number of levels in the tree
489 * does not exceed the number of logical
490 * levels allowed by DNSSEC.
492 * XXXDCL need a better error result?
494 * XXXDCL Since chain ancestors were removed,
495 * no longer used by dns_rbt_addonlevel(),
496 * this is the only real use of chains in the
497 * function. It could be done instead with
498 * a simple integer variable, but I am pressed
501 if (chain.level_count ==
502 (sizeof(chain.levels) /
503 sizeof(*chain.levels))) {
504 result = ISC_R_NOSPACE;
509 * Split the name into two parts, a prefix
510 * which is the not-in-common parts of the
511 * two names and a suffix that is the common
514 dns_name_split(¤t_name, common_labels,
516 result = create_node(rbt->mctx, suffix,
519 if (result != ISC_R_SUCCESS)
523 * Reproduce the tree attributes of the
526 new_current->is_root = current->is_root;
527 PARENT(new_current) = PARENT(current);
528 LEFT(new_current) = LEFT(current);
529 RIGHT(new_current) = RIGHT(current);
530 COLOR(new_current) = COLOR(current);
533 * Fix pointers that were to the current node.
535 if (parent != NULL) {
536 if (LEFT(parent) == current)
537 LEFT(parent) = new_current;
539 RIGHT(parent) = new_current;
541 if (LEFT(new_current) != NULL)
542 PARENT(LEFT(new_current)) =
544 if (RIGHT(new_current) != NULL)
545 PARENT(RIGHT(new_current)) =
547 if (*root == current)
550 NAMELEN(current) = prefix->length;
551 OFFSETLEN(current) = prefix->labels;
552 memcpy(OFFSETS(current), prefix->offsets,
555 (current_name.length - prefix->length) +
556 (current_name.labels - prefix->labels);
559 * Set up the new root of the next level.
560 * By definition it will not be the top
561 * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
563 current->is_root = 1;
564 PARENT(current) = new_current;
565 DOWN(new_current) = current;
566 root = &DOWN(new_current);
568 ADD_LEVEL(&chain, new_current);
570 LEFT(current) = NULL;
571 RIGHT(current) = NULL;
574 ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
577 dns_name_getlabelsequence(name,
580 hash_node(rbt, new_current, new_name);
583 dns_name_countlabels(add_name)) {
585 * The name has been added by pushing
586 * the not-in-common parts down to
589 *nodep = new_current;
590 return (ISC_R_SUCCESS);
594 * The current node has no data,
595 * because it is just a placeholder.
596 * Its data pointer is already NULL
597 * from create_node()), so there's
598 * nothing more to do to it.
602 * The not-in-common parts of the new
603 * name will be inserted into the new
604 * level following this loop (unless
605 * result != ISC_R_SUCCESS, which
606 * is tested after the loop ends).
608 dns_name_split(add_name, common_labels,
618 } while (child != NULL);
620 if (result == ISC_R_SUCCESS)
621 result = create_node(rbt->mctx, add_name, &new_current);
623 if (result == ISC_R_SUCCESS) {
624 dns_rbt_addonlevel(new_current, current, order, root);
626 *nodep = new_current;
627 hash_node(rbt, new_current, name);
634 * Add a name to the tree of trees, associating it with some data.
637 dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
641 REQUIRE(VALID_RBT(rbt));
642 REQUIRE(dns_name_isabsolute(name));
646 result = dns_rbt_addnode(rbt, name, &node);
649 * dns_rbt_addnode will report the node exists even when
650 * it does not have data associated with it, but the
651 * dns_rbt_*name functions all behave depending on whether
652 * there is data associated with a node.
654 if (result == ISC_R_SUCCESS ||
655 (result == ISC_R_EXISTS && DATA(node) == NULL)) {
657 result = ISC_R_SUCCESS;
664 * Find the node for "name" in the tree of trees.
667 dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
668 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
669 unsigned int options, dns_rbtfindcallback_t callback,
672 dns_rbtnode_t *current, *last_compared, *current_root;
673 dns_rbtnodechain_t localchain;
674 dns_name_t *search_name, current_name, *callback_name;
675 dns_fixedname_t fixedcallbackname, fixedsearchname;
676 dns_namereln_t compared;
677 isc_result_t result, saved_result;
678 unsigned int common_labels;
679 unsigned int hlabels = 0;
682 REQUIRE(VALID_RBT(rbt));
683 REQUIRE(dns_name_isabsolute(name));
684 REQUIRE(node != NULL && *node == NULL);
685 REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
686 != (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
689 * If there is a chain it needs to appear to be in a sane state,
690 * otherwise a chain is still needed to generate foundname and
694 options |= DNS_RBTFIND_NOPREDECESSOR;
696 dns_rbtnodechain_init(chain, rbt->mctx);
698 dns_rbtnodechain_reset(chain);
700 if (rbt->root == NULL)
701 return (ISC_R_NOTFOUND);
704 * Appease GCC about variables it incorrectly thinks are
705 * possibly used uninitialized.
707 compared = dns_namereln_none;
708 last_compared = NULL;
711 dns_fixedname_init(&fixedcallbackname);
712 callback_name = dns_fixedname_name(&fixedcallbackname);
715 * search_name is the name segment being sought in each tree level.
716 * By using a fixedname, the search_name will definitely have offsets
717 * for use by any splitting.
718 * By using dns_name_clone, no name data should be copied thanks to
719 * the lack of bitstring labels.
721 dns_fixedname_init(&fixedsearchname);
722 search_name = dns_fixedname_name(&fixedsearchname);
723 dns_name_clone(name, search_name);
725 dns_name_init(¤t_name, NULL);
727 saved_result = ISC_R_SUCCESS;
729 current_root = rbt->root;
731 while (current != NULL) {
732 NODENAME(current, ¤t_name);
733 compared = dns_name_fullcompare(search_name, ¤t_name,
734 &order, &common_labels);
735 last_compared = current;
737 if (compared == dns_namereln_equal)
740 if (compared == dns_namereln_none) {
741 #ifdef DNS_RBT_USEHASH
742 dns_name_t hash_name;
743 dns_rbtnode_t *hnode;
744 dns_rbtnode_t *up_current;
745 unsigned int nlabels;
746 unsigned int tlabels = 1;
750 * If there is no hash table, hashing can't be done.
752 if (rbt->hashtable == NULL)
756 * The case of current != current_root, that
757 * means a left or right pointer was followed,
758 * only happens when the algorithm fell through to
759 * the traditional binary search because of a
760 * bitstring label. Since we dropped the bitstring
761 * support, this should not happen.
763 INSIST(current == current_root);
765 nlabels = dns_name_countlabels(search_name);
768 * current_root is the root of the current level, so
769 * it's parent is the same as it's "up" pointer.
771 up_current = PARENT(current_root);
772 dns_name_init(&hash_name, NULL);
776 * Hash includes tail.
778 dns_name_getlabelsequence(name,
782 hash = dns_name_fullhash(&hash_name, ISC_FALSE);
783 dns_name_getlabelsequence(search_name,
785 tlabels, &hash_name);
787 for (hnode = rbt->hashtable[hash % rbt->hashsize];
789 hnode = hnode->hashnext)
791 dns_name_t hnode_name;
793 if (hash != HASHVAL(hnode))
795 if (find_up(hnode) != up_current)
797 dns_name_init(&hnode_name, NULL);
798 NODENAME(hnode, &hnode_name);
799 if (dns_name_equal(&hnode_name, &hash_name))
806 * This is an optimization. If hashing found
807 * the right node, the next call to
808 * dns_name_fullcompare() would obviously
809 * return _equal or _subdomain. Determine
810 * which of those would be the case by
811 * checking if the full name was hashed. Then
812 * make it look like dns_name_fullcompare
813 * was called and jump to the right place.
815 if (tlabels == nlabels) {
816 compared = dns_namereln_equal;
819 common_labels = tlabels;
820 compared = dns_namereln_subdomain;
825 if (tlabels++ < nlabels)
829 * All of the labels have been tried against the hash
830 * table. Since we dropped the support of bitstring
831 * labels, the name isn't in the table.
837 #endif /* DNS_RBT_USEHASH */
839 * Standard binary search tree movement.
842 current = LEFT(current);
844 current = RIGHT(current);
848 * The names have some common suffix labels.
850 * If the number in common are equal in length to
851 * the current node's name length, then follow the
852 * down pointer and search in the new tree.
854 if (compared == dns_namereln_subdomain) {
857 * Whack off the current node's common parts
858 * for the name to search in the next level.
860 dns_name_split(search_name, common_labels,
862 hlabels += common_labels;
864 * This might be the closest enclosing name.
866 if (DATA(current) != NULL ||
867 (options & DNS_RBTFIND_EMPTYDATA) != 0)
871 * Point the chain to the next level. This
872 * needs to be done before 'current' is pointed
873 * there because the callback in the next
874 * block of code needs the current 'current',
875 * but in the event the callback requests that
876 * the search be stopped then the
877 * DNS_R_PARTIALMATCH code at the end of this
878 * function needs the chain pointed to the
881 ADD_LEVEL(chain, current);
884 * The caller may want to interrupt the
885 * downward search when certain special nodes
886 * are traversed. If this is a special node,
887 * the callback is used to learn what the
888 * caller wants to do.
890 if (callback != NULL &&
891 FINDCALLBACK(current)) {
892 result = chain_name(chain,
895 if (result != ISC_R_SUCCESS) {
896 dns_rbtnodechain_reset(chain);
900 result = (callback)(current,
903 if (result != DNS_R_CONTINUE) {
904 saved_result = result;
906 * Treat this node as if it
907 * had no down pointer.
915 * Finally, head to the next tree level.
917 current = DOWN(current);
918 current_root = current;
922 * Though there are labels in common, the
923 * entire name at this node is not common
924 * with the search name so the search
925 * name does not exist in the tree.
927 INSIST(compared == dns_namereln_commonancestor
928 || compared == dns_namereln_contains);
936 * If current is not NULL, NOEXACT is not disallowing exact matches,
937 * and either the node has data or an empty node is ok, return
938 * ISC_R_SUCCESS to indicate an exact match.
940 if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
941 (DATA(current) != NULL ||
942 (options & DNS_RBTFIND_EMPTYDATA) != 0)) {
944 * Found an exact match.
946 chain->end = current;
947 chain->level_matches = chain->level_count;
949 if (foundname != NULL)
950 result = chain_name(chain, foundname, ISC_TRUE);
952 result = ISC_R_SUCCESS;
954 if (result == ISC_R_SUCCESS) {
956 result = saved_result;
961 * Did not find an exact match (or did not want one).
965 * ... but found a partially matching superdomain.
966 * Unwind the chain to the partial match node
967 * to set level_matches to the level above the node,
968 * and then to derive the name.
970 * chain->level_count is guaranteed to be at least 1
971 * here because by definition of finding a superdomain,
972 * the chain is pointed to at least the first subtree.
974 chain->level_matches = chain->level_count - 1;
976 while (chain->levels[chain->level_matches] != *node) {
977 INSIST(chain->level_matches > 0);
978 chain->level_matches--;
981 if (foundname != NULL) {
982 unsigned int saved_count = chain->level_count;
984 chain->level_count = chain->level_matches + 1;
986 result = chain_name(chain, foundname,
989 chain->level_count = saved_count;
991 result = ISC_R_SUCCESS;
993 if (result == ISC_R_SUCCESS)
994 result = DNS_R_PARTIALMATCH;
997 result = ISC_R_NOTFOUND;
999 if (current != NULL) {
1001 * There was an exact match but either
1002 * DNS_RBTFIND_NOEXACT was set, or
1003 * DNS_RBTFIND_EMPTYDATA was set and the node had no
1004 * data. A policy decision was made to set the
1005 * chain to the exact match, but this is subject
1006 * to change if it becomes apparent that something
1007 * else would be more useful. It is important that
1008 * this case is handled here, because the predecessor
1009 * setting code below assumes the match was not exact.
1011 INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
1012 ((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
1013 DATA(current) == NULL));
1014 chain->end = current;
1016 } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
1018 * Ensure the chain points nowhere.
1024 * Since there was no exact match, the chain argument
1025 * needs to be pointed at the DNSSEC predecessor of
1028 if (compared == dns_namereln_subdomain) {
1030 * Attempted to follow a down pointer that was
1031 * NULL, which means the searched for name was
1032 * a subdomain of a terminal name in the tree.
1033 * Since there are no existing subdomains to
1034 * order against, the terminal name is the
1037 INSIST(chain->level_count > 0);
1038 INSIST(chain->level_matches <
1039 chain->level_count);
1041 chain->levels[--chain->level_count];
1044 isc_result_t result2;
1047 * Point current to the node that stopped
1050 * With the hashing modification that has been
1051 * added to the algorithm, the stop node of a
1052 * standard binary search is not known. So it
1053 * has to be found. There is probably a more
1054 * clever way of doing this.
1056 * The assignment of current to NULL when
1057 * the relationship is *not* dns_namereln_none,
1058 * even though it later gets set to the same
1059 * last_compared anyway, is simply to not push
1060 * the while loop in one more level of
1063 if (compared == dns_namereln_none)
1064 current = last_compared;
1068 while (current != NULL) {
1069 NODENAME(current, ¤t_name);
1070 compared = dns_name_fullcompare(
1076 last_compared = current;
1079 * Standard binary search movement.
1082 current = LEFT(current);
1084 current = RIGHT(current);
1088 current = last_compared;
1091 * Reached a point within a level tree that
1092 * positively indicates the name is not
1093 * present, but the stop node could be either
1094 * less than the desired name (order > 0) or
1095 * greater than the desired name (order < 0).
1097 * If the stop node is less, it is not
1098 * necessarily the predecessor. If the stop
1099 * node has a down pointer, then the real
1100 * predecessor is at the end of a level below
1101 * (not necessarily the next level).
1102 * Move down levels until the rightmost node
1103 * does not have a down pointer.
1105 * When the stop node is greater, it is
1106 * the successor. All the logic for finding
1107 * the predecessor is handily encapsulated
1108 * in dns_rbtnodechain_prev. In the event
1109 * that the search name is less than anything
1110 * else in the tree, the chain is reset.
1111 * XXX DCL What is the best way for the caller
1112 * to know that the search name has
1118 if (DOWN(current) != NULL) {
1119 ADD_LEVEL(chain, current);
1122 move_chain_to_last(chain,
1125 if (result2 != ISC_R_SUCCESS)
1129 * Ah, the pure and simple
1130 * case. The stop node is the
1133 chain->end = current;
1138 chain->end = current;
1140 result2 = dns_rbtnodechain_prev(chain,
1143 if (result2 == ISC_R_SUCCESS ||
1144 result2 == DNS_R_NEWORIGIN)
1146 else if (result2 == ISC_R_NOMORE)
1148 * There is no predecessor.
1150 dns_rbtnodechain_reset(chain);
1159 ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
1165 * Get the data pointer associated with 'name'.
1168 dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
1169 dns_name_t *foundname, void **data) {
1170 dns_rbtnode_t *node = NULL;
1171 isc_result_t result;
1173 REQUIRE(data != NULL && *data == NULL);
1175 result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
1176 options, NULL, NULL);
1179 (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
1182 result = ISC_R_NOTFOUND;
1188 * Delete a name from the tree of trees.
1191 dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse) {
1192 dns_rbtnode_t *node = NULL;
1193 isc_result_t result;
1195 REQUIRE(VALID_RBT(rbt));
1196 REQUIRE(dns_name_isabsolute(name));
1199 * First, find the node.
1201 * When searching, the name might not have an exact match:
1202 * consider a.b.a.com, b.b.a.com and c.b.a.com as the only
1203 * elements of a tree, which would make layer 1 a single
1204 * node tree of "b.a.com" and layer 2 a three node tree of
1205 * a, b, and c. Deleting a.com would find only a partial depth
1206 * match in the first layer. Should it be a requirement that
1207 * that the name to be deleted have data? For now, it is.
1209 * ->dirty, ->locknum and ->references are ignored; they are
1210 * solely the province of rbtdb.c.
1212 result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
1213 DNS_RBTFIND_NOOPTIONS, NULL, NULL);
1215 if (result == ISC_R_SUCCESS) {
1216 if (DATA(node) != NULL)
1217 result = dns_rbt_deletenode(rbt, node, recurse);
1219 result = ISC_R_NOTFOUND;
1221 } else if (result == DNS_R_PARTIALMATCH)
1222 result = ISC_R_NOTFOUND;
1228 * Remove a node from the tree of trees.
1230 * NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
1231 * a sequence of additions to be deletions will not generally get the
1232 * tree back to the state it started in. For example, if the addition
1233 * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
1234 * then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
1235 * restoring "a.b.c". The RBT *used* to do this kind of rejoining, but it
1236 * turned out to be a bad idea because it could corrupt an active nodechain
1237 * that had "b.c" as one of its levels -- and the RBT has no idea what
1238 * nodechains are in use by callers, so it can't even *try* to helpfully
1239 * fix them up (which would probably be doomed to failure anyway).
1241 * Similarly, it is possible to leave the tree in a state where a supposedly
1242 * deleted node still exists. The first case of this is obvious; take
1243 * the tree which has "b.c" on one level, pointing to "a". Now deleted "b.c".
1244 * It was just established in the previous paragraph why we can't pull "a"
1245 * back up to its parent level. But what happens when "a" then gets deleted?
1246 * "b.c" is left hanging around without data or children. This condition
1247 * is actually pretty easy to detect, but ... should it really be removed?
1248 * Is a chain pointing to it? An iterator? Who knows! (Note that the
1249 * references structure member cannot be looked at because it is private to
1250 * rbtdb.) This is ugly and makes me unhappy, but after hours of trying to
1251 * make it more aesthetically proper and getting nowhere, this is the way it
1252 * is going to stay until such time as it proves to be a *real* problem.
1254 * Finally, for reference, note that the original routine that did node
1255 * joining was called join_nodes(). It has been excised, living now only
1256 * in the CVS history, but comments have been left behind that point to it just
1257 * in case someone wants to muck with this some more.
1259 * The one positive aspect of all of this is that joining used to have a
1260 * case where it might fail. Without trying to join, now this function always
1261 * succeeds. It still returns isc_result_t, though, so the API wouldn't change.
1264 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
1266 dns_rbtnode_t *parent;
1268 REQUIRE(VALID_RBT(rbt));
1269 REQUIRE(DNS_RBTNODE_VALID(node));
1271 if (DOWN(node) != NULL) {
1273 RUNTIME_CHECK(dns_rbt_deletetree(rbt, DOWN(node))
1276 if (DATA(node) != NULL && rbt->data_deleter != NULL)
1277 rbt->data_deleter(DATA(node),
1282 * Since there is at least one node below this one and
1283 * no recursion was requested, the deletion is
1284 * complete. The down node from this node might be all
1285 * by itself on a single level, so join_nodes() could
1286 * be used to collapse the tree (with all the caveats
1287 * of the comment at the start of this function).
1289 return (ISC_R_SUCCESS);
1294 * Note the node that points to the level of the node that is being
1295 * deleted. If the deleted node is the top level, parent will be set
1298 parent = find_up(node);
1301 * This node now has no down pointer (either because it didn't
1302 * have one to start, or because it was recursively removed).
1303 * So now the node needs to be removed from this level.
1305 dns_rbt_deletefromlevel(node, parent == NULL ? &rbt->root :
1308 if (DATA(node) != NULL && rbt->data_deleter != NULL)
1309 rbt->data_deleter(DATA(node), rbt->deleter_arg);
1311 unhash_node(rbt, node);
1312 #if DNS_RBT_USEMAGIC
1315 dns_rbtnode_refdestroy(node);
1316 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
1320 * There are now two special cases that can exist that would
1321 * not have existed if the tree had been created using only
1322 * the names that now exist in it. (This is all related to
1323 * join_nodes() as described in this function's introductory comment.)
1324 * Both cases exist when the deleted node's parent (the node
1325 * that pointed to the deleted node's level) is not null but
1326 * it has no data: parent != NULL && DATA(parent) == NULL.
1328 * The first case is that the deleted node was the last on its level:
1329 * DOWN(parent) == NULL. This case can only exist if the parent was
1330 * previously deleted -- and so now, apparently, the parent should go
1331 * away. That can't be done though because there might be external
1332 * references to it, such as through a nodechain.
1334 * The other case also involves a parent with no data, but with the
1335 * deleted node being the next-to-last node instead of the last:
1336 * LEFT(DOWN(parent)) == NULL && RIGHT(DOWN(parent)) == NULL.
1337 * Presumably now the remaining node on the level should be joined
1338 * with the parent, but it's already been described why that can't be
1343 * This function never fails.
1345 return (ISC_R_SUCCESS);
1349 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1351 REQUIRE(DNS_RBTNODE_VALID(node));
1352 REQUIRE(name != NULL);
1353 REQUIRE(name->offsets == NULL);
1355 NODENAME(node, name);
1359 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1361 isc_result_t result;
1363 REQUIRE(DNS_RBTNODE_VALID(node));
1364 REQUIRE(name != NULL);
1365 REQUIRE(name->buffer != NULL);
1367 dns_name_init(¤t, NULL);
1368 dns_name_reset(name);
1371 INSIST(node != NULL);
1373 NODENAME(node, ¤t);
1375 result = dns_name_concatenate(name, ¤t, name, NULL);
1376 if (result != ISC_R_SUCCESS)
1379 node = find_up(node);
1380 } while (! dns_name_isabsolute(name));
1386 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
1388 dns_fixedname_t fixedname;
1390 isc_result_t result;
1392 REQUIRE(DNS_RBTNODE_VALID(node));
1393 REQUIRE(printname != NULL);
1395 dns_fixedname_init(&fixedname);
1396 name = dns_fixedname_name(&fixedname);
1397 result = dns_rbt_fullnamefromnode(node, name);
1398 if (result == ISC_R_SUCCESS)
1399 dns_name_format(name, printname, size);
1401 snprintf(printname, size, "<error building name: %s>",
1402 dns_result_totext(result));
1408 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep) {
1409 dns_rbtnode_t *node;
1410 isc_region_t region;
1411 unsigned int labels;
1413 REQUIRE(name->offsets != NULL);
1415 dns_name_toregion(name, ®ion);
1416 labels = dns_name_countlabels(name);
1420 * Allocate space for the node structure, the name, and the offsets.
1422 node = (dns_rbtnode_t *)isc_mem_get(mctx, sizeof(*node) +
1423 region.length + labels);
1426 return (ISC_R_NOMEMORY);
1429 PARENT(node) = NULL;
1434 #ifdef DNS_RBT_USEHASH
1435 HASHNEXT(node) = NULL;
1442 dns_rbtnode_refinit(node, 0);
1443 node->find_callback = 0;
1448 * The following is stored to make reconstructing a name from the
1449 * stored value in the node easy: the length of the name, the number
1450 * of labels, whether the name is absolute or not, the name itself,
1451 * and the name's offsets table.
1454 * The offsets table could be made smaller by eliminating the
1455 * first offset, which is always 0. This requires changes to
1458 NAMELEN(node) = region.length;
1460 OFFSETLEN(node) = labels;
1461 ATTRS(node) = name->attributes;
1463 memcpy(NAME(node), region.base, region.length);
1464 memcpy(OFFSETS(node), name->offsets, labels);
1466 #if DNS_RBT_USEMAGIC
1467 node->magic = DNS_RBTNODE_MAGIC;
1471 return (ISC_R_SUCCESS);
1474 #ifdef DNS_RBT_USEHASH
1476 hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
1479 HASHVAL(node) = dns_name_fullhash(name, ISC_FALSE);
1481 hash = HASHVAL(node) % rbt->hashsize;
1482 HASHNEXT(node) = rbt->hashtable[hash];
1484 rbt->hashtable[hash] = node;
1488 inithash(dns_rbt_t *rbt) {
1491 rbt->hashsize = RBT_HASH_SIZE;
1492 bytes = rbt->hashsize * sizeof(dns_rbtnode_t *);
1493 rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
1495 if (rbt->hashtable == NULL)
1496 return (ISC_R_NOMEMORY);
1498 memset(rbt->hashtable, 0, bytes);
1500 return (ISC_R_SUCCESS);
1504 rehash(dns_rbt_t *rbt) {
1505 unsigned int oldsize;
1506 dns_rbtnode_t **oldtable;
1507 dns_rbtnode_t *node;
1511 oldsize = rbt->hashsize;
1512 oldtable = rbt->hashtable;
1513 rbt->hashsize *= 2 + 1;
1514 rbt->hashtable = isc_mem_get(rbt->mctx,
1515 rbt->hashsize * sizeof(dns_rbtnode_t *));
1516 if (rbt->hashtable == NULL) {
1517 rbt->hashtable = oldtable;
1518 rbt->hashsize = oldsize;
1522 for (i = 0; i < rbt->hashsize; i++)
1523 rbt->hashtable[i] = NULL;
1525 for (i = 0; i < oldsize; i++) {
1527 while (node != NULL) {
1528 hash = HASHVAL(node) % rbt->hashsize;
1529 oldtable[i] = HASHNEXT(node);
1530 HASHNEXT(node) = rbt->hashtable[hash];
1531 rbt->hashtable[hash] = node;
1536 isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
1540 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
1542 REQUIRE(DNS_RBTNODE_VALID(node));
1544 if (rbt->nodecount >= (rbt->hashsize *3))
1547 hash_add_node(rbt, node, name);
1551 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1552 unsigned int bucket;
1553 dns_rbtnode_t *bucket_node;
1555 REQUIRE(DNS_RBTNODE_VALID(node));
1557 if (rbt->hashtable != NULL) {
1558 bucket = HASHVAL(node) % rbt->hashsize;
1559 bucket_node = rbt->hashtable[bucket];
1561 if (bucket_node == node)
1562 rbt->hashtable[bucket] = HASHNEXT(node);
1564 while (HASHNEXT(bucket_node) != node) {
1565 INSIST(HASHNEXT(bucket_node) != NULL);
1566 bucket_node = HASHNEXT(bucket_node);
1568 HASHNEXT(bucket_node) = HASHNEXT(node);
1572 #endif /* DNS_RBT_USEHASH */
1575 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1576 dns_rbtnode_t *child;
1578 REQUIRE(DNS_RBTNODE_VALID(node));
1579 REQUIRE(rootp != NULL);
1581 child = RIGHT(node);
1582 INSIST(child != NULL);
1584 RIGHT(node) = LEFT(child);
1585 if (LEFT(child) != NULL)
1586 PARENT(LEFT(child)) = node;
1590 PARENT(child) = PARENT(node);
1592 if (IS_ROOT(node)) {
1598 if (LEFT(PARENT(node)) == node)
1599 LEFT(PARENT(node)) = child;
1601 RIGHT(PARENT(node)) = child;
1604 PARENT(node) = child;
1608 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1609 dns_rbtnode_t *child;
1611 REQUIRE(DNS_RBTNODE_VALID(node));
1612 REQUIRE(rootp != NULL);
1615 INSIST(child != NULL);
1617 LEFT(node) = RIGHT(child);
1618 if (RIGHT(child) != NULL)
1619 PARENT(RIGHT(child)) = node;
1620 RIGHT(child) = node;
1623 PARENT(child) = PARENT(node);
1625 if (IS_ROOT(node)) {
1631 if (LEFT(PARENT(node)) == node)
1632 LEFT(PARENT(node)) = child;
1634 RIGHT(PARENT(node)) = child;
1637 PARENT(node) = child;
1641 * This is the real workhorse of the insertion code, because it does the
1642 * true red/black tree on a single level.
1645 dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
1646 dns_rbtnode_t **rootp)
1648 dns_rbtnode_t *child, *root, *parent, *grandparent;
1649 dns_name_t add_name, current_name;
1650 dns_offsets_t add_offsets, current_offsets;
1652 REQUIRE(rootp != NULL);
1653 REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
1654 RIGHT(node) == NULL);
1655 REQUIRE(current != NULL);
1660 * First node of a level.
1664 PARENT(node) = current;
1671 dns_name_init(&add_name, add_offsets);
1672 NODENAME(node, &add_name);
1674 dns_name_init(¤t_name, current_offsets);
1675 NODENAME(current, ¤t_name);
1678 INSIST(LEFT(current) == NULL);
1679 LEFT(current) = node;
1681 INSIST(RIGHT(current) == NULL);
1682 RIGHT(current) = node;
1685 INSIST(PARENT(node) == NULL);
1686 PARENT(node) = current;
1690 while (node != root && IS_RED(PARENT(node))) {
1692 * XXXDCL could do away with separate parent and grandparent
1693 * variables. They are vestiges of the days before parent
1694 * pointers. However, they make the code a little clearer.
1697 parent = PARENT(node);
1698 grandparent = PARENT(parent);
1700 if (parent == LEFT(grandparent)) {
1701 child = RIGHT(grandparent);
1702 if (child != NULL && IS_RED(child)) {
1705 MAKE_RED(grandparent);
1708 if (node == RIGHT(parent)) {
1709 rotate_left(parent, &root);
1711 parent = PARENT(node);
1712 grandparent = PARENT(parent);
1715 MAKE_RED(grandparent);
1716 rotate_right(grandparent, &root);
1719 child = LEFT(grandparent);
1720 if (child != NULL && IS_RED(child)) {
1723 MAKE_RED(grandparent);
1726 if (node == LEFT(parent)) {
1727 rotate_right(parent, &root);
1729 parent = PARENT(node);
1730 grandparent = PARENT(parent);
1733 MAKE_RED(grandparent);
1734 rotate_left(grandparent, &root);
1740 ENSURE(IS_ROOT(root));
1747 * This is the real workhorse of the deletion code, because it does the
1748 * true red/black tree on a single level.
1751 dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp) {
1752 dns_rbtnode_t *child, *sibling, *parent;
1753 dns_rbtnode_t *successor;
1755 REQUIRE(delete != NULL);
1758 * Verify that the parent history is (apparently) correct.
1760 INSIST((IS_ROOT(delete) && *rootp == delete) ||
1761 (! IS_ROOT(delete) &&
1762 (LEFT(PARENT(delete)) == delete ||
1763 RIGHT(PARENT(delete)) == delete)));
1767 if (LEFT(delete) == NULL) {
1768 if (RIGHT(delete) == NULL) {
1769 if (IS_ROOT(delete)) {
1771 * This is the only item in the tree.
1778 * This node has one child, on the right.
1780 child = RIGHT(delete);
1782 } else if (RIGHT(delete) == NULL)
1784 * This node has one child, on the left.
1786 child = LEFT(delete);
1788 dns_rbtnode_t holder, *tmp = &holder;
1791 * This node has two children, so it cannot be directly
1792 * deleted. Find its immediate in-order successor and
1793 * move it to this location, then do the deletion at the
1794 * old site of the successor.
1796 successor = RIGHT(delete);
1797 while (LEFT(successor) != NULL)
1798 successor = LEFT(successor);
1801 * The successor cannot possibly have a left child;
1802 * if there is any child, it is on the right.
1804 if (RIGHT(successor) != NULL)
1805 child = RIGHT(successor);
1808 * Swap the two nodes; it would be simpler to just replace
1809 * the value being deleted with that of the successor,
1810 * but this rigamarole is done so the caller has complete
1811 * control over the pointers (and memory allocation) of
1812 * all of nodes. If just the key value were removed from
1813 * the tree, the pointer to the node would be unchanged.
1817 * First, put the successor in the tree location of the
1818 * node to be deleted. Save its existing tree pointer
1819 * information, which will be needed when linking up
1820 * delete to the successor's old location.
1822 memcpy(tmp, successor, sizeof(dns_rbtnode_t));
1824 if (IS_ROOT(delete)) {
1826 successor->is_root = ISC_TRUE;
1827 delete->is_root = ISC_FALSE;
1830 if (LEFT(PARENT(delete)) == delete)
1831 LEFT(PARENT(delete)) = successor;
1833 RIGHT(PARENT(delete)) = successor;
1835 PARENT(successor) = PARENT(delete);
1836 LEFT(successor) = LEFT(delete);
1837 RIGHT(successor) = RIGHT(delete);
1838 COLOR(successor) = COLOR(delete);
1840 if (LEFT(successor) != NULL)
1841 PARENT(LEFT(successor)) = successor;
1842 if (RIGHT(successor) != successor)
1843 PARENT(RIGHT(successor)) = successor;
1846 * Now relink the node to be deleted into the
1847 * successor's previous tree location. PARENT(tmp)
1848 * is the successor's original parent.
1850 INSIST(! IS_ROOT(delete));
1852 if (PARENT(tmp) == delete) {
1854 * Node being deleted was successor's parent.
1856 RIGHT(successor) = delete;
1857 PARENT(delete) = successor;
1860 LEFT(PARENT(tmp)) = delete;
1861 PARENT(delete) = PARENT(tmp);
1865 * Original location of successor node has no left.
1867 LEFT(delete) = NULL;
1868 RIGHT(delete) = RIGHT(tmp);
1869 COLOR(delete) = COLOR(tmp);
1873 * Remove the node by removing the links from its parent.
1875 if (! IS_ROOT(delete)) {
1876 if (LEFT(PARENT(delete)) == delete)
1877 LEFT(PARENT(delete)) = child;
1879 RIGHT(PARENT(delete)) = child;
1882 PARENT(child) = PARENT(delete);
1886 * This is the root being deleted, and at this point
1887 * it is known to have just one child.
1891 PARENT(child) = PARENT(delete);
1895 * Fix color violations.
1897 if (IS_BLACK(delete)) {
1898 parent = PARENT(delete);
1900 while (child != *rootp && IS_BLACK(child)) {
1901 INSIST(child == NULL || ! IS_ROOT(child));
1903 if (LEFT(parent) == child) {
1904 sibling = RIGHT(parent);
1906 if (IS_RED(sibling)) {
1907 MAKE_BLACK(sibling);
1909 rotate_left(parent, rootp);
1910 sibling = RIGHT(parent);
1913 if (IS_BLACK(LEFT(sibling)) &&
1914 IS_BLACK(RIGHT(sibling))) {
1920 if (IS_BLACK(RIGHT(sibling))) {
1921 MAKE_BLACK(LEFT(sibling));
1923 rotate_right(sibling, rootp);
1924 sibling = RIGHT(parent);
1927 COLOR(sibling) = COLOR(parent);
1929 MAKE_BLACK(RIGHT(sibling));
1930 rotate_left(parent, rootp);
1936 * Child is parent's right child.
1937 * Everything is doen the same as above,
1940 sibling = LEFT(parent);
1942 if (IS_RED(sibling)) {
1943 MAKE_BLACK(sibling);
1945 rotate_right(parent, rootp);
1946 sibling = LEFT(parent);
1949 if (IS_BLACK(LEFT(sibling)) &&
1950 IS_BLACK(RIGHT(sibling))) {
1955 if (IS_BLACK(LEFT(sibling))) {
1956 MAKE_BLACK(RIGHT(sibling));
1958 rotate_left(sibling, rootp);
1959 sibling = LEFT(parent);
1962 COLOR(sibling) = COLOR(parent);
1964 MAKE_BLACK(LEFT(sibling));
1965 rotate_right(parent, rootp);
1970 parent = PARENT(child);
1979 * This should only be used on the root of a tree, because no color fixup
1982 * NOTE: No root pointer maintenance is done, because the function is only
1983 * used for two cases:
1984 * + deleting everything DOWN from a node that is itself being deleted, and
1985 * + deleting the entire tree of trees from dns_rbt_destroy.
1986 * In each case, the root pointer is no longer relevant, so there
1987 * is no need for a root parameter to this function.
1989 * If the function is ever intended to be used to delete something where
1990 * a pointer needs to be told that this tree no longer exists,
1991 * this function would need to adjusted accordingly.
1994 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1995 isc_result_t result = ISC_R_SUCCESS;
1996 REQUIRE(VALID_RBT(rbt));
2001 if (LEFT(node) != NULL) {
2002 result = dns_rbt_deletetree(rbt, LEFT(node));
2003 if (result != ISC_R_SUCCESS)
2007 if (RIGHT(node) != NULL) {
2008 result = dns_rbt_deletetree(rbt, RIGHT(node));
2009 if (result != ISC_R_SUCCESS)
2013 if (DOWN(node) != NULL) {
2014 result = dns_rbt_deletetree(rbt, DOWN(node));
2015 if (result != ISC_R_SUCCESS)
2020 if (result != ISC_R_SUCCESS)
2023 if (DATA(node) != NULL && rbt->data_deleter != NULL)
2024 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2026 unhash_node(rbt, node);
2027 #if DNS_RBT_USEMAGIC
2030 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2036 dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum,
2037 dns_rbtnode_t **nodep)
2039 dns_rbtnode_t *parent;
2040 dns_rbtnode_t *node = *nodep;
2041 REQUIRE(VALID_RBT(rbt));
2050 if (LEFT(node) != NULL) {
2054 if (RIGHT(node) != NULL) {
2058 if (DOWN(node) != NULL) {
2063 if (DATA(node) != NULL && rbt->data_deleter != NULL)
2064 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2067 * Note: we don't call unhash_node() here as we are destroying
2068 * the complete rbt tree.
2070 #if DNS_RBT_USEMAGIC
2073 parent = PARENT(node);
2074 if (parent != NULL) {
2075 if (LEFT(parent) == node)
2076 LEFT(parent) = NULL;
2077 else if (DOWN(parent) == node)
2078 DOWN(parent) = NULL;
2079 else if (RIGHT(parent) == node)
2080 RIGHT(parent) = NULL;
2082 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2085 if (quantum != 0 && --quantum == 0) {
2093 dns_rbt_indent(int depth) {
2096 for (i = 0; i < depth; i++)
2101 dns_rbt_printnodename(dns_rbtnode_t *node) {
2104 char buffer[DNS_NAME_FORMATSIZE];
2105 dns_offsets_t offsets;
2107 r.length = NAMELEN(node);
2108 r.base = NAME(node);
2110 dns_name_init(&name, offsets);
2111 dns_name_fromregion(&name, &r);
2113 dns_name_format(&name, buffer, sizeof(buffer));
2115 printf("%s", buffer);
2119 dns_rbt_printtree(dns_rbtnode_t *root, dns_rbtnode_t *parent, int depth) {
2120 dns_rbt_indent(depth);
2123 dns_rbt_printnodename(root);
2124 printf(" (%s", IS_RED(root) ? "RED" : "black");
2127 dns_rbt_printnodename(parent);
2130 if ((! IS_ROOT(root) && PARENT(root) != parent) ||
2131 ( IS_ROOT(root) && depth > 0 &&
2132 DOWN(PARENT(root)) != root)) {
2134 printf(" (BAD parent pointer! -> ");
2135 if (PARENT(root) != NULL)
2136 dns_rbt_printnodename(PARENT(root));
2148 dns_rbt_indent(depth);
2149 printf("++ BEG down from ");
2150 dns_rbt_printnodename(root);
2152 dns_rbt_printtree(DOWN(root), NULL, depth);
2153 dns_rbt_indent(depth);
2154 printf("-- END down from ");
2155 dns_rbt_printnodename(root);
2159 if (IS_RED(root) && IS_RED(LEFT(root)))
2160 printf("** Red/Red color violation on left\n");
2161 dns_rbt_printtree(LEFT(root), root, depth);
2163 if (IS_RED(root) && IS_RED(RIGHT(root)))
2164 printf("** Red/Red color violation on right\n");
2165 dns_rbt_printtree(RIGHT(root), root, depth);
2172 dns_rbt_printall(dns_rbt_t *rbt) {
2173 REQUIRE(VALID_RBT(rbt));
2175 dns_rbt_printtree(rbt->root, NULL, 0);
2183 dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
2185 * Initialize 'chain'.
2188 REQUIRE(chain != NULL);
2192 chain->level_count = 0;
2193 chain->level_matches = 0;
2195 chain->magic = CHAIN_MAGIC;
2199 dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
2200 dns_name_t *origin, dns_rbtnode_t **node)
2202 isc_result_t result = ISC_R_SUCCESS;
2204 REQUIRE(VALID_CHAIN(chain));
2209 if (chain->end == NULL)
2210 return (ISC_R_NOTFOUND);
2213 NODENAME(chain->end, name);
2215 if (chain->level_count == 0) {
2217 * Names in the top level tree are all absolute.
2218 * Always make 'name' relative.
2220 INSIST(dns_name_isabsolute(name));
2223 * This is cheaper than dns_name_getlabelsequence().
2227 name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
2231 if (origin != NULL) {
2232 if (chain->level_count > 0)
2233 result = chain_name(chain, origin, ISC_FALSE);
2235 result = dns_name_copy(dns_rootname, origin, NULL);
2242 dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
2245 dns_rbtnode_t *current, *previous, *predecessor;
2246 isc_result_t result = ISC_R_SUCCESS;
2247 isc_boolean_t new_origin = ISC_FALSE;
2249 REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2253 current = chain->end;
2255 if (LEFT(current) != NULL) {
2257 * Moving left one then right as far as possible is the
2258 * previous node, at least for this level.
2260 current = LEFT(current);
2262 while (RIGHT(current) != NULL)
2263 current = RIGHT(current);
2265 predecessor = current;
2269 * No left links, so move toward the root. If at any point on
2270 * the way there the link from parent to child is a right
2271 * link, then the parent is the previous node, at least
2274 while (! IS_ROOT(current)) {
2276 current = PARENT(current);
2278 if (RIGHT(current) == previous) {
2279 predecessor = current;
2285 if (predecessor != NULL) {
2287 * Found a predecessor node in this level. It might not
2288 * really be the predecessor, however.
2290 if (DOWN(predecessor) != NULL) {
2292 * The predecessor is really down at least one level.
2293 * Go down and as far right as possible, and repeat
2294 * as long as the rightmost node has a down pointer.
2298 * XXX DCL Need to do something about origins
2299 * here. See whether to go down, and if so
2300 * whether it is truly what Bob calls a
2303 ADD_LEVEL(chain, predecessor);
2304 predecessor = DOWN(predecessor);
2306 /* XXX DCL duplicated from above; clever
2307 * way to unduplicate? */
2309 while (RIGHT(predecessor) != NULL)
2310 predecessor = RIGHT(predecessor);
2311 } while (DOWN(predecessor) != NULL);
2313 /* XXX DCL probably needs work on the concept */
2315 new_origin = ISC_TRUE;
2318 } else if (chain->level_count > 0) {
2320 * Dang, didn't find a predecessor in this level.
2321 * Got to the root of this level without having traversed
2322 * any right links. Ascend the tree one level; the
2323 * node that points to this tree is the predecessor.
2325 INSIST(chain->level_count > 0 && IS_ROOT(current));
2326 predecessor = chain->levels[--chain->level_count];
2328 /* XXX DCL probably needs work on the concept */
2330 * Don't declare an origin change when the new origin is "."
2331 * at the top level tree, because "." is declared as the origin
2332 * for the second level tree.
2334 if (origin != NULL &&
2335 (chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
2336 new_origin = ISC_TRUE;
2339 if (predecessor != NULL) {
2340 chain->end = predecessor;
2343 result = dns_rbtnodechain_current(chain, name, origin,
2345 if (result == ISC_R_SUCCESS)
2346 result = DNS_R_NEWORIGIN;
2349 result = dns_rbtnodechain_current(chain, name, NULL,
2353 result = ISC_R_NOMORE;
2359 dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
2362 dns_rbtnode_t *current, *previous, *successor;
2363 isc_result_t result = ISC_R_SUCCESS;
2364 isc_boolean_t new_origin = ISC_FALSE;
2366 REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2370 current = chain->end;
2373 * If there is a level below this node, the next node is the leftmost
2374 * node of the next level.
2376 if (DOWN(current) != NULL) {
2378 * Don't declare an origin change when the new origin is "."
2379 * at the second level tree, because "." is already declared
2380 * as the origin for the top level tree.
2382 if (chain->level_count > 0 ||
2383 OFFSETLEN(current) > 1)
2384 new_origin = ISC_TRUE;
2386 ADD_LEVEL(chain, current);
2387 current = DOWN(current);
2389 while (LEFT(current) != NULL)
2390 current = LEFT(current);
2392 successor = current;
2394 } else if (RIGHT(current) == NULL) {
2396 * The successor is up, either in this level or a previous one.
2397 * Head back toward the root of the tree, looking for any path
2398 * that was via a left link; the successor is the node that has
2399 * that left link. In the event the root of the level is
2400 * reached without having traversed any left links, ascend one
2401 * level and look for either a right link off the point of
2402 * ascent, or search for a left link upward again, repeating
2403 * ascents until either case is true.
2406 while (! IS_ROOT(current)) {
2408 current = PARENT(current);
2410 if (LEFT(current) == previous) {
2411 successor = current;
2416 if (successor == NULL) {
2418 * Reached the root without having traversed
2419 * any left pointers, so this level is done.
2421 if (chain->level_count == 0)
2424 current = chain->levels[--chain->level_count];
2425 new_origin = ISC_TRUE;
2427 if (RIGHT(current) != NULL)
2430 } while (successor == NULL);
2433 if (successor == NULL && RIGHT(current) != NULL) {
2434 current = RIGHT(current);
2436 while (LEFT(current) != NULL)
2437 current = LEFT(current);
2439 successor = current;
2442 if (successor != NULL) {
2443 chain->end = successor;
2446 * It is not necessary to use dns_rbtnodechain_current like
2447 * the other functions because this function will never
2448 * find a node in the topmost level. This is because the
2449 * root level will never be more than one name, and everything
2450 * in the megatree is a successor to that node, down at
2451 * the second level or below.
2455 NODENAME(chain->end, name);
2459 result = chain_name(chain, origin, ISC_FALSE);
2461 if (result == ISC_R_SUCCESS)
2462 result = DNS_R_NEWORIGIN;
2465 result = ISC_R_SUCCESS;
2468 result = ISC_R_NOMORE;
2474 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2475 dns_name_t *name, dns_name_t *origin)
2478 isc_result_t result;
2480 REQUIRE(VALID_RBT(rbt));
2481 REQUIRE(VALID_CHAIN(chain));
2483 dns_rbtnodechain_reset(chain);
2485 chain->end = rbt->root;
2487 result = dns_rbtnodechain_current(chain, name, origin, NULL);
2489 if (result == ISC_R_SUCCESS)
2490 result = DNS_R_NEWORIGIN;
2496 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2497 dns_name_t *name, dns_name_t *origin)
2500 isc_result_t result;
2502 REQUIRE(VALID_RBT(rbt));
2503 REQUIRE(VALID_CHAIN(chain));
2505 dns_rbtnodechain_reset(chain);
2507 result = move_chain_to_last(chain, rbt->root);
2508 if (result != ISC_R_SUCCESS)
2511 result = dns_rbtnodechain_current(chain, name, origin, NULL);
2513 if (result == ISC_R_SUCCESS)
2514 result = DNS_R_NEWORIGIN;
2521 dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
2523 * Free any dynamic storage associated with 'chain', and then
2524 * reinitialize 'chain'.
2527 REQUIRE(VALID_CHAIN(chain));
2530 chain->level_count = 0;
2531 chain->level_matches = 0;
2535 dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
2537 * Free any dynamic storage associated with 'chain', and then
2538 * invalidate 'chain'.
2541 dns_rbtnodechain_reset(chain);