2 * Copyright (C) 2004, 2005, 2007-2009 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2003 Internet Software Consortium.
5 * Permission to use, copy, modify, and/or distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
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.142.50.3 2009/10/20 05:06:04 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>
42 #include <dns/result.h>
44 #define RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')
45 #define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
48 * XXXDCL Since parent pointers were added in again, I could remove all of the
49 * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
50 * _lastnode. This would involve pretty major change to the API.
52 #define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')
53 #define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
55 #define RBT_HASH_SIZE 64
59 #define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
66 void (*data_deleter)(void *, void *);
68 unsigned int nodecount;
69 unsigned int hashsize;
70 dns_rbtnode_t ** hashtable;
77 * Elements of the rbtnode structure.
79 #define PARENT(node) ((node)->parent)
80 #define LEFT(node) ((node)->left)
81 #define RIGHT(node) ((node)->right)
82 #define DOWN(node) ((node)->down)
83 #define DATA(node) ((node)->data)
84 #define HASHNEXT(node) ((node)->hashnext)
85 #define HASHVAL(node) ((node)->hashval)
86 #define COLOR(node) ((node)->color)
87 #define NAMELEN(node) ((node)->namelen)
88 #define OLDNAMELEN(node) ((node)->oldnamelen)
89 #define OFFSETLEN(node) ((node)->offsetlen)
90 #define ATTRS(node) ((node)->attributes)
91 #define IS_ROOT(node) ISC_TF((node)->is_root == 1)
92 #define FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)
95 * Structure elements from the rbtdb.c, not
96 * used as part of the rbt.c algorithms.
98 #define DIRTY(node) ((node)->dirty)
99 #define WILD(node) ((node)->wild)
100 #define LOCKNUM(node) ((node)->locknum)
103 * The variable length stuff stored after the node has the following
106 * <name_data>{1..255}<oldoffsetlen>{1}<offsets>{1..128}
108 * <name_data> contains the name of the node when it was created.
109 * <oldoffsetlen> contains the length of <offsets> when the node was created.
110 * <offsets> contains the offets into name for each label when the node was
114 #define NAME(node) ((unsigned char *)((node) + 1))
115 #define OFFSETS(node) (NAME(node) + OLDNAMELEN(node) + 1)
116 #define OLDOFFSETLEN(node) (OFFSETS(node)[-1])
118 #define NODE_SIZE(node) (sizeof(*node) + \
119 OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)
124 #define IS_RED(node) ((node) != NULL && (node)->color == RED)
125 #define IS_BLACK(node) ((node) == NULL || (node)->color == BLACK)
126 #define MAKE_RED(node) ((node)->color = RED)
127 #define MAKE_BLACK(node) ((node)->color = BLACK)
132 * The "ancestors" member of chains were removed, with their job now
133 * being wholly handled by parent pointers (which didn't exist, because
134 * of memory concerns, when chains were first implemented).
136 #define ADD_LEVEL(chain, node) \
137 (chain)->levels[(chain)->level_count++] = (node)
140 * The following macros directly access normally private name variables.
141 * These macros are used to avoid a lot of function calls in the critical
142 * path of the tree traversal code.
145 #define NODENAME(node, name) \
147 (name)->length = NAMELEN(node); \
148 (name)->labels = OFFSETLEN(node); \
149 (name)->ndata = NAME(node); \
150 (name)->offsets = OFFSETS(node); \
151 (name)->attributes = ATTRS(node); \
152 (name)->attributes |= DNS_NAMEATTR_READONLY; \
155 #ifdef DNS_RBT_USEHASH
157 inithash(dns_rbt_t *rbt);
163 * A little something to help out in GDB.
165 dns_name_t Name(dns_rbtnode_t *node);
167 Name(dns_rbtnode_t *node) {
170 dns_name_init(&name, NULL);
172 NODENAME(node, &name);
177 static void dns_rbt_printnodename(dns_rbtnode_t *node);
180 static inline dns_rbtnode_t *
181 find_up(dns_rbtnode_t *node) {
185 * Return the node in the level above the argument node that points
186 * to the level the argument node is in. If the argument node is in
187 * the top level, the return value is NULL.
189 for (root = node; ! IS_ROOT(root); root = PARENT(root))
192 return (PARENT(root));
196 * Forward declarations.
199 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
201 #ifdef DNS_RBT_USEHASH
203 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
205 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
207 #define hash_node(rbt, node, name) (ISC_R_SUCCESS)
208 #define unhash_node(rbt, node)
212 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
214 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
217 dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
218 dns_rbtnode_t **rootp);
221 dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);
224 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);
227 dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum,
228 dns_rbtnode_t **nodep);
231 * Initialize a red/black tree of trees.
234 dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
235 void *deleter_arg, dns_rbt_t **rbtp)
237 #ifdef DNS_RBT_USEHASH
243 REQUIRE(mctx != NULL);
244 REQUIRE(rbtp != NULL && *rbtp == NULL);
245 REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
247 rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
249 return (ISC_R_NOMEMORY);
252 rbt->data_deleter = deleter;
253 rbt->deleter_arg = deleter_arg;
256 rbt->hashtable = NULL;
259 #ifdef DNS_RBT_USEHASH
260 result = inithash(rbt);
261 if (result != ISC_R_SUCCESS) {
262 isc_mem_put(mctx, rbt, sizeof(*rbt));
267 rbt->magic = RBT_MAGIC;
271 return (ISC_R_SUCCESS);
275 * Deallocate a red/black tree of trees.
278 dns_rbt_destroy(dns_rbt_t **rbtp) {
279 RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
283 dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
286 REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
290 dns_rbt_deletetreeflat(rbt, quantum, &rbt->root);
291 if (rbt->root != NULL)
292 return (ISC_R_QUOTA);
294 INSIST(rbt->nodecount == 0);
296 if (rbt->hashtable != NULL)
297 isc_mem_put(rbt->mctx, rbt->hashtable,
298 rbt->hashsize * sizeof(dns_rbtnode_t *));
302 isc_mem_put(rbt->mctx, rbt, sizeof(*rbt));
304 return (ISC_R_SUCCESS);
308 dns_rbt_nodecount(dns_rbt_t *rbt) {
309 REQUIRE(VALID_RBT(rbt));
310 return (rbt->nodecount);
313 static inline isc_result_t
314 chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
315 isc_boolean_t include_chain_end)
318 isc_result_t result = ISC_R_SUCCESS;
321 dns_name_init(&nodename, NULL);
323 if (include_chain_end && chain->end != NULL) {
324 NODENAME(chain->end, &nodename);
325 result = dns_name_copy(&nodename, name, NULL);
326 if (result != ISC_R_SUCCESS)
329 dns_name_reset(name);
331 for (i = (int)chain->level_count - 1; i >= 0; i--) {
332 NODENAME(chain->levels[i], &nodename);
333 result = dns_name_concatenate(name, &nodename, name, NULL);
335 if (result != ISC_R_SUCCESS)
341 static inline isc_result_t
342 move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
345 * Go as far right and then down as much as possible,
346 * as long as the rightmost node has a down pointer.
348 while (RIGHT(node) != NULL)
351 if (DOWN(node) == NULL)
354 ADD_LEVEL(chain, node);
360 return (ISC_R_SUCCESS);
364 * Add 'name' to tree, initializing its data pointer with 'data'.
368 dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
370 * Does this thing have too many variables or what?
372 dns_rbtnode_t **root, *parent, *child, *current, *new_current;
373 dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
374 dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
375 dns_offsets_t current_offsets;
376 dns_namereln_t compared;
377 isc_result_t result = ISC_R_SUCCESS;
378 dns_rbtnodechain_t chain;
379 unsigned int common_labels;
380 unsigned int nlabels, hlabels;
383 REQUIRE(VALID_RBT(rbt));
384 REQUIRE(dns_name_isabsolute(name));
385 REQUIRE(nodep != NULL && *nodep == NULL);
388 * Create a copy of the name so the original name structure is
391 dns_fixedname_init(&fixedcopy);
392 add_name = dns_fixedname_name(&fixedcopy);
393 dns_name_clone(name, add_name);
395 if (rbt->root == NULL) {
396 result = create_node(rbt->mctx, add_name, &new_current);
397 if (result == ISC_R_SUCCESS) {
399 new_current->is_root = 1;
400 rbt->root = new_current;
401 *nodep = new_current;
402 hash_node(rbt, new_current, name);
407 dns_rbtnodechain_init(&chain, rbt->mctx);
409 dns_fixedname_init(&fixedprefix);
410 dns_fixedname_init(&fixedsuffix);
411 prefix = dns_fixedname_name(&fixedprefix);
412 suffix = dns_fixedname_name(&fixedsuffix);
415 INSIST(IS_ROOT(*root));
419 dns_name_init(¤t_name, current_offsets);
420 dns_fixedname_init(&fnewname);
421 new_name = dns_fixedname_name(&fnewname);
422 nlabels = dns_name_countlabels(name);
428 NODENAME(current, ¤t_name);
429 compared = dns_name_fullcompare(add_name, ¤t_name,
430 &order, &common_labels);
432 if (compared == dns_namereln_equal) {
434 result = ISC_R_EXISTS;
439 if (compared == dns_namereln_none) {
443 child = LEFT(current);
445 } else if (order > 0) {
447 child = RIGHT(current);
453 * This name has some suffix in common with the
454 * name at the current node. If the name at
455 * the current node is shorter, that means the
456 * new name should be in a subtree. If the
457 * name at the current node is longer, that means
458 * the down pointer to this tree should point
459 * to a new tree that has the common suffix, and
460 * the non-common parts of these two names should
463 hlabels += common_labels;
464 if (compared == dns_namereln_subdomain) {
466 * All of the existing labels are in common,
467 * so the new name is in a subtree.
468 * Whack off the common labels for the
469 * not-in-common part to be searched for
472 dns_name_split(add_name, common_labels,
476 * Follow the down pointer (possibly NULL).
478 root = &DOWN(current);
480 INSIST(*root == NULL ||
482 PARENT(*root) == current));
485 child = DOWN(current);
486 ADD_LEVEL(&chain, current);
490 * The number of labels in common is fewer
491 * than the number of labels at the current
492 * node, so the current node must be adjusted
493 * to have just the common suffix, and a down
494 * pointer made to a new tree.
497 INSIST(compared == dns_namereln_commonancestor
498 || compared == dns_namereln_contains);
501 * Ensure the number of levels in the tree
502 * does not exceed the number of logical
503 * levels allowed by DNSSEC.
505 * XXXDCL need a better error result?
507 * XXXDCL Since chain ancestors were removed,
508 * no longer used by dns_rbt_addonlevel(),
509 * this is the only real use of chains in the
510 * function. It could be done instead with
511 * a simple integer variable, but I am pressed
514 if (chain.level_count ==
515 (sizeof(chain.levels) /
516 sizeof(*chain.levels))) {
517 result = ISC_R_NOSPACE;
522 * Split the name into two parts, a prefix
523 * which is the not-in-common parts of the
524 * two names and a suffix that is the common
527 dns_name_split(¤t_name, common_labels,
529 result = create_node(rbt->mctx, suffix,
532 if (result != ISC_R_SUCCESS)
536 * Reproduce the tree attributes of the
539 new_current->is_root = current->is_root;
540 new_current->nsec3 = current->nsec3;
541 PARENT(new_current) = PARENT(current);
542 LEFT(new_current) = LEFT(current);
543 RIGHT(new_current) = RIGHT(current);
544 COLOR(new_current) = COLOR(current);
547 * Fix pointers that were to the current node.
549 if (parent != NULL) {
550 if (LEFT(parent) == current)
551 LEFT(parent) = new_current;
553 RIGHT(parent) = new_current;
555 if (LEFT(new_current) != NULL)
556 PARENT(LEFT(new_current)) =
558 if (RIGHT(new_current) != NULL)
559 PARENT(RIGHT(new_current)) =
561 if (*root == current)
564 NAMELEN(current) = prefix->length;
565 OFFSETLEN(current) = prefix->labels;
568 * Set up the new root of the next level.
569 * By definition it will not be the top
570 * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
572 current->is_root = 1;
573 PARENT(current) = new_current;
574 DOWN(new_current) = current;
575 root = &DOWN(new_current);
577 ADD_LEVEL(&chain, new_current);
579 LEFT(current) = NULL;
580 RIGHT(current) = NULL;
583 ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
586 dns_name_getlabelsequence(name,
589 hash_node(rbt, new_current, new_name);
592 dns_name_countlabels(add_name)) {
594 * The name has been added by pushing
595 * the not-in-common parts down to
598 *nodep = new_current;
599 return (ISC_R_SUCCESS);
603 * The current node has no data,
604 * because it is just a placeholder.
605 * Its data pointer is already NULL
606 * from create_node()), so there's
607 * nothing more to do to it.
611 * The not-in-common parts of the new
612 * name will be inserted into the new
613 * level following this loop (unless
614 * result != ISC_R_SUCCESS, which
615 * is tested after the loop ends).
617 dns_name_split(add_name, common_labels,
627 } while (child != NULL);
629 if (result == ISC_R_SUCCESS)
630 result = create_node(rbt->mctx, add_name, &new_current);
632 if (result == ISC_R_SUCCESS) {
633 dns_rbt_addonlevel(new_current, current, order, root);
635 *nodep = new_current;
636 hash_node(rbt, new_current, name);
643 * Add a name to the tree of trees, associating it with some data.
646 dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
650 REQUIRE(VALID_RBT(rbt));
651 REQUIRE(dns_name_isabsolute(name));
655 result = dns_rbt_addnode(rbt, name, &node);
658 * dns_rbt_addnode will report the node exists even when
659 * it does not have data associated with it, but the
660 * dns_rbt_*name functions all behave depending on whether
661 * there is data associated with a node.
663 if (result == ISC_R_SUCCESS ||
664 (result == ISC_R_EXISTS && DATA(node) == NULL)) {
666 result = ISC_R_SUCCESS;
673 * Find the node for "name" in the tree of trees.
676 dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
677 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
678 unsigned int options, dns_rbtfindcallback_t callback,
681 dns_rbtnode_t *current, *last_compared, *current_root;
682 dns_rbtnodechain_t localchain;
683 dns_name_t *search_name, current_name, *callback_name;
684 dns_fixedname_t fixedcallbackname, fixedsearchname;
685 dns_namereln_t compared;
686 isc_result_t result, saved_result;
687 unsigned int common_labels;
688 unsigned int hlabels = 0;
691 REQUIRE(VALID_RBT(rbt));
692 REQUIRE(dns_name_isabsolute(name));
693 REQUIRE(node != NULL && *node == NULL);
694 REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
695 != (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
698 * If there is a chain it needs to appear to be in a sane state,
699 * otherwise a chain is still needed to generate foundname and
703 options |= DNS_RBTFIND_NOPREDECESSOR;
705 dns_rbtnodechain_init(chain, rbt->mctx);
707 dns_rbtnodechain_reset(chain);
709 if (rbt->root == NULL)
710 return (ISC_R_NOTFOUND);
713 * Appease GCC about variables it incorrectly thinks are
714 * possibly used uninitialized.
716 compared = dns_namereln_none;
717 last_compared = NULL;
720 dns_fixedname_init(&fixedcallbackname);
721 callback_name = dns_fixedname_name(&fixedcallbackname);
724 * search_name is the name segment being sought in each tree level.
725 * By using a fixedname, the search_name will definitely have offsets
726 * for use by any splitting.
727 * By using dns_name_clone, no name data should be copied thanks to
728 * the lack of bitstring labels.
730 dns_fixedname_init(&fixedsearchname);
731 search_name = dns_fixedname_name(&fixedsearchname);
732 dns_name_clone(name, search_name);
734 dns_name_init(¤t_name, NULL);
736 saved_result = ISC_R_SUCCESS;
738 current_root = rbt->root;
740 while (current != NULL) {
741 NODENAME(current, ¤t_name);
742 compared = dns_name_fullcompare(search_name, ¤t_name,
743 &order, &common_labels);
744 last_compared = current;
746 if (compared == dns_namereln_equal)
749 if (compared == dns_namereln_none) {
750 #ifdef DNS_RBT_USEHASH
751 dns_name_t hash_name;
752 dns_rbtnode_t *hnode;
753 dns_rbtnode_t *up_current;
754 unsigned int nlabels;
755 unsigned int tlabels = 1;
759 * If there is no hash table, hashing can't be done.
761 if (rbt->hashtable == NULL)
765 * The case of current != current_root, that
766 * means a left or right pointer was followed,
767 * only happens when the algorithm fell through to
768 * the traditional binary search because of a
769 * bitstring label. Since we dropped the bitstring
770 * support, this should not happen.
772 INSIST(current == current_root);
774 nlabels = dns_name_countlabels(search_name);
777 * current_root is the root of the current level, so
778 * it's parent is the same as it's "up" pointer.
780 up_current = PARENT(current_root);
781 dns_name_init(&hash_name, NULL);
785 * Hash includes tail.
787 dns_name_getlabelsequence(name,
791 hash = dns_name_fullhash(&hash_name, ISC_FALSE);
792 dns_name_getlabelsequence(search_name,
794 tlabels, &hash_name);
796 for (hnode = rbt->hashtable[hash % rbt->hashsize];
798 hnode = hnode->hashnext)
800 dns_name_t hnode_name;
802 if (hash != HASHVAL(hnode))
804 if (find_up(hnode) != up_current)
806 dns_name_init(&hnode_name, NULL);
807 NODENAME(hnode, &hnode_name);
808 if (dns_name_equal(&hnode_name, &hash_name))
815 * This is an optimization. If hashing found
816 * the right node, the next call to
817 * dns_name_fullcompare() would obviously
818 * return _equal or _subdomain. Determine
819 * which of those would be the case by
820 * checking if the full name was hashed. Then
821 * make it look like dns_name_fullcompare
822 * was called and jump to the right place.
824 if (tlabels == nlabels) {
825 compared = dns_namereln_equal;
828 common_labels = tlabels;
829 compared = dns_namereln_subdomain;
834 if (tlabels++ < nlabels)
838 * All of the labels have been tried against the hash
839 * table. Since we dropped the support of bitstring
840 * labels, the name isn't in the table.
846 #endif /* DNS_RBT_USEHASH */
848 * Standard binary search tree movement.
851 current = LEFT(current);
853 current = RIGHT(current);
857 * The names have some common suffix labels.
859 * If the number in common are equal in length to
860 * the current node's name length, then follow the
861 * down pointer and search in the new tree.
863 if (compared == dns_namereln_subdomain) {
866 * Whack off the current node's common parts
867 * for the name to search in the next level.
869 dns_name_split(search_name, common_labels,
871 hlabels += common_labels;
873 * This might be the closest enclosing name.
875 if (DATA(current) != NULL ||
876 (options & DNS_RBTFIND_EMPTYDATA) != 0)
880 * Point the chain to the next level. This
881 * needs to be done before 'current' is pointed
882 * there because the callback in the next
883 * block of code needs the current 'current',
884 * but in the event the callback requests that
885 * the search be stopped then the
886 * DNS_R_PARTIALMATCH code at the end of this
887 * function needs the chain pointed to the
890 ADD_LEVEL(chain, current);
893 * The caller may want to interrupt the
894 * downward search when certain special nodes
895 * are traversed. If this is a special node,
896 * the callback is used to learn what the
897 * caller wants to do.
899 if (callback != NULL &&
900 FINDCALLBACK(current)) {
901 result = chain_name(chain,
904 if (result != ISC_R_SUCCESS) {
905 dns_rbtnodechain_reset(chain);
909 result = (callback)(current,
912 if (result != DNS_R_CONTINUE) {
913 saved_result = result;
915 * Treat this node as if it
916 * had no down pointer.
924 * Finally, head to the next tree level.
926 current = DOWN(current);
927 current_root = current;
931 * Though there are labels in common, the
932 * entire name at this node is not common
933 * with the search name so the search
934 * name does not exist in the tree.
936 INSIST(compared == dns_namereln_commonancestor
937 || compared == dns_namereln_contains);
945 * If current is not NULL, NOEXACT is not disallowing exact matches,
946 * and either the node has data or an empty node is ok, return
947 * ISC_R_SUCCESS to indicate an exact match.
949 if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
950 (DATA(current) != NULL ||
951 (options & DNS_RBTFIND_EMPTYDATA) != 0)) {
953 * Found an exact match.
955 chain->end = current;
956 chain->level_matches = chain->level_count;
958 if (foundname != NULL)
959 result = chain_name(chain, foundname, ISC_TRUE);
961 result = ISC_R_SUCCESS;
963 if (result == ISC_R_SUCCESS) {
965 result = saved_result;
970 * Did not find an exact match (or did not want one).
974 * ... but found a partially matching superdomain.
975 * Unwind the chain to the partial match node
976 * to set level_matches to the level above the node,
977 * and then to derive the name.
979 * chain->level_count is guaranteed to be at least 1
980 * here because by definition of finding a superdomain,
981 * the chain is pointed to at least the first subtree.
983 chain->level_matches = chain->level_count - 1;
985 while (chain->levels[chain->level_matches] != *node) {
986 INSIST(chain->level_matches > 0);
987 chain->level_matches--;
990 if (foundname != NULL) {
991 unsigned int saved_count = chain->level_count;
993 chain->level_count = chain->level_matches + 1;
995 result = chain_name(chain, foundname,
998 chain->level_count = saved_count;
1000 result = ISC_R_SUCCESS;
1002 if (result == ISC_R_SUCCESS)
1003 result = DNS_R_PARTIALMATCH;
1006 result = ISC_R_NOTFOUND;
1008 if (current != NULL) {
1010 * There was an exact match but either
1011 * DNS_RBTFIND_NOEXACT was set, or
1012 * DNS_RBTFIND_EMPTYDATA was set and the node had no
1013 * data. A policy decision was made to set the
1014 * chain to the exact match, but this is subject
1015 * to change if it becomes apparent that something
1016 * else would be more useful. It is important that
1017 * this case is handled here, because the predecessor
1018 * setting code below assumes the match was not exact.
1020 INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
1021 ((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
1022 DATA(current) == NULL));
1023 chain->end = current;
1025 } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
1027 * Ensure the chain points nowhere.
1033 * Since there was no exact match, the chain argument
1034 * needs to be pointed at the DNSSEC predecessor of
1037 if (compared == dns_namereln_subdomain) {
1039 * Attempted to follow a down pointer that was
1040 * NULL, which means the searched for name was
1041 * a subdomain of a terminal name in the tree.
1042 * Since there are no existing subdomains to
1043 * order against, the terminal name is the
1046 INSIST(chain->level_count > 0);
1047 INSIST(chain->level_matches <
1048 chain->level_count);
1050 chain->levels[--chain->level_count];
1053 isc_result_t result2;
1056 * Point current to the node that stopped
1059 * With the hashing modification that has been
1060 * added to the algorithm, the stop node of a
1061 * standard binary search is not known. So it
1062 * has to be found. There is probably a more
1063 * clever way of doing this.
1065 * The assignment of current to NULL when
1066 * the relationship is *not* dns_namereln_none,
1067 * even though it later gets set to the same
1068 * last_compared anyway, is simply to not push
1069 * the while loop in one more level of
1072 if (compared == dns_namereln_none)
1073 current = last_compared;
1077 while (current != NULL) {
1078 NODENAME(current, ¤t_name);
1079 compared = dns_name_fullcompare(
1085 last_compared = current;
1088 * Standard binary search movement.
1091 current = LEFT(current);
1093 current = RIGHT(current);
1097 current = last_compared;
1100 * Reached a point within a level tree that
1101 * positively indicates the name is not
1102 * present, but the stop node could be either
1103 * less than the desired name (order > 0) or
1104 * greater than the desired name (order < 0).
1106 * If the stop node is less, it is not
1107 * necessarily the predecessor. If the stop
1108 * node has a down pointer, then the real
1109 * predecessor is at the end of a level below
1110 * (not necessarily the next level).
1111 * Move down levels until the rightmost node
1112 * does not have a down pointer.
1114 * When the stop node is greater, it is
1115 * the successor. All the logic for finding
1116 * the predecessor is handily encapsulated
1117 * in dns_rbtnodechain_prev. In the event
1118 * that the search name is less than anything
1119 * else in the tree, the chain is reset.
1120 * XXX DCL What is the best way for the caller
1121 * to know that the search name has
1127 if (DOWN(current) != NULL) {
1128 ADD_LEVEL(chain, current);
1131 move_chain_to_last(chain,
1134 if (result2 != ISC_R_SUCCESS)
1138 * Ah, the pure and simple
1139 * case. The stop node is the
1142 chain->end = current;
1147 chain->end = current;
1149 result2 = dns_rbtnodechain_prev(chain,
1152 if (result2 == ISC_R_SUCCESS ||
1153 result2 == DNS_R_NEWORIGIN)
1155 else if (result2 == ISC_R_NOMORE)
1157 * There is no predecessor.
1159 dns_rbtnodechain_reset(chain);
1168 ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
1174 * Get the data pointer associated with 'name'.
1177 dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
1178 dns_name_t *foundname, void **data) {
1179 dns_rbtnode_t *node = NULL;
1180 isc_result_t result;
1182 REQUIRE(data != NULL && *data == NULL);
1184 result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
1185 options, NULL, NULL);
1188 (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
1191 result = ISC_R_NOTFOUND;
1197 * Delete a name from the tree of trees.
1200 dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse) {
1201 dns_rbtnode_t *node = NULL;
1202 isc_result_t result;
1204 REQUIRE(VALID_RBT(rbt));
1205 REQUIRE(dns_name_isabsolute(name));
1208 * First, find the node.
1210 * When searching, the name might not have an exact match:
1211 * consider a.b.a.com, b.b.a.com and c.b.a.com as the only
1212 * elements of a tree, which would make layer 1 a single
1213 * node tree of "b.a.com" and layer 2 a three node tree of
1214 * a, b, and c. Deleting a.com would find only a partial depth
1215 * match in the first layer. Should it be a requirement that
1216 * that the name to be deleted have data? For now, it is.
1218 * ->dirty, ->locknum and ->references are ignored; they are
1219 * solely the province of rbtdb.c.
1221 result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
1222 DNS_RBTFIND_NOOPTIONS, NULL, NULL);
1224 if (result == ISC_R_SUCCESS) {
1225 if (DATA(node) != NULL)
1226 result = dns_rbt_deletenode(rbt, node, recurse);
1228 result = ISC_R_NOTFOUND;
1230 } else if (result == DNS_R_PARTIALMATCH)
1231 result = ISC_R_NOTFOUND;
1237 * Remove a node from the tree of trees.
1239 * NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
1240 * a sequence of additions to be deletions will not generally get the
1241 * tree back to the state it started in. For example, if the addition
1242 * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
1243 * then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
1244 * restoring "a.b.c". The RBT *used* to do this kind of rejoining, but it
1245 * turned out to be a bad idea because it could corrupt an active nodechain
1246 * that had "b.c" as one of its levels -- and the RBT has no idea what
1247 * nodechains are in use by callers, so it can't even *try* to helpfully
1248 * fix them up (which would probably be doomed to failure anyway).
1250 * Similarly, it is possible to leave the tree in a state where a supposedly
1251 * deleted node still exists. The first case of this is obvious; take
1252 * the tree which has "b.c" on one level, pointing to "a". Now deleted "b.c".
1253 * It was just established in the previous paragraph why we can't pull "a"
1254 * back up to its parent level. But what happens when "a" then gets deleted?
1255 * "b.c" is left hanging around without data or children. This condition
1256 * is actually pretty easy to detect, but ... should it really be removed?
1257 * Is a chain pointing to it? An iterator? Who knows! (Note that the
1258 * references structure member cannot be looked at because it is private to
1259 * rbtdb.) This is ugly and makes me unhappy, but after hours of trying to
1260 * make it more aesthetically proper and getting nowhere, this is the way it
1261 * is going to stay until such time as it proves to be a *real* problem.
1263 * Finally, for reference, note that the original routine that did node
1264 * joining was called join_nodes(). It has been excised, living now only
1265 * in the CVS history, but comments have been left behind that point to it just
1266 * in case someone wants to muck with this some more.
1268 * The one positive aspect of all of this is that joining used to have a
1269 * case where it might fail. Without trying to join, now this function always
1270 * succeeds. It still returns isc_result_t, though, so the API wouldn't change.
1273 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
1275 dns_rbtnode_t *parent;
1277 REQUIRE(VALID_RBT(rbt));
1278 REQUIRE(DNS_RBTNODE_VALID(node));
1280 if (DOWN(node) != NULL) {
1282 RUNTIME_CHECK(dns_rbt_deletetree(rbt, DOWN(node))
1285 if (DATA(node) != NULL && rbt->data_deleter != NULL)
1286 rbt->data_deleter(DATA(node), rbt->deleter_arg);
1290 * Since there is at least one node below this one and
1291 * no recursion was requested, the deletion is
1292 * complete. The down node from this node might be all
1293 * by itself on a single level, so join_nodes() could
1294 * be used to collapse the tree (with all the caveats
1295 * of the comment at the start of this function).
1297 return (ISC_R_SUCCESS);
1302 * Note the node that points to the level of the node that is being
1303 * deleted. If the deleted node is the top level, parent will be set
1306 parent = find_up(node);
1309 * This node now has no down pointer (either because it didn't
1310 * have one to start, or because it was recursively removed).
1311 * So now the node needs to be removed from this level.
1313 dns_rbt_deletefromlevel(node, parent == NULL ? &rbt->root :
1316 if (DATA(node) != NULL && rbt->data_deleter != NULL)
1317 rbt->data_deleter(DATA(node), rbt->deleter_arg);
1319 unhash_node(rbt, node);
1320 #if DNS_RBT_USEMAGIC
1323 dns_rbtnode_refdestroy(node);
1324 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
1328 * There are now two special cases that can exist that would
1329 * not have existed if the tree had been created using only
1330 * the names that now exist in it. (This is all related to
1331 * join_nodes() as described in this function's introductory comment.)
1332 * Both cases exist when the deleted node's parent (the node
1333 * that pointed to the deleted node's level) is not null but
1334 * it has no data: parent != NULL && DATA(parent) == NULL.
1336 * The first case is that the deleted node was the last on its level:
1337 * DOWN(parent) == NULL. This case can only exist if the parent was
1338 * previously deleted -- and so now, apparently, the parent should go
1339 * away. That can't be done though because there might be external
1340 * references to it, such as through a nodechain.
1342 * The other case also involves a parent with no data, but with the
1343 * deleted node being the next-to-last node instead of the last:
1344 * LEFT(DOWN(parent)) == NULL && RIGHT(DOWN(parent)) == NULL.
1345 * Presumably now the remaining node on the level should be joined
1346 * with the parent, but it's already been described why that can't be
1351 * This function never fails.
1353 return (ISC_R_SUCCESS);
1357 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1359 REQUIRE(DNS_RBTNODE_VALID(node));
1360 REQUIRE(name != NULL);
1361 REQUIRE(name->offsets == NULL);
1363 NODENAME(node, name);
1367 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1369 isc_result_t result;
1371 REQUIRE(DNS_RBTNODE_VALID(node));
1372 REQUIRE(name != NULL);
1373 REQUIRE(name->buffer != NULL);
1375 dns_name_init(¤t, NULL);
1376 dns_name_reset(name);
1379 INSIST(node != NULL);
1381 NODENAME(node, ¤t);
1383 result = dns_name_concatenate(name, ¤t, name, NULL);
1384 if (result != ISC_R_SUCCESS)
1387 node = find_up(node);
1388 } while (! dns_name_isabsolute(name));
1394 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
1396 dns_fixedname_t fixedname;
1398 isc_result_t result;
1400 REQUIRE(DNS_RBTNODE_VALID(node));
1401 REQUIRE(printname != NULL);
1403 dns_fixedname_init(&fixedname);
1404 name = dns_fixedname_name(&fixedname);
1405 result = dns_rbt_fullnamefromnode(node, name);
1406 if (result == ISC_R_SUCCESS)
1407 dns_name_format(name, printname, size);
1409 snprintf(printname, size, "<error building name: %s>",
1410 dns_result_totext(result));
1416 create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep) {
1417 dns_rbtnode_t *node;
1418 isc_region_t region;
1419 unsigned int labels;
1421 REQUIRE(name->offsets != NULL);
1423 dns_name_toregion(name, ®ion);
1424 labels = dns_name_countlabels(name);
1428 * Allocate space for the node structure, the name, and the offsets.
1430 node = (dns_rbtnode_t *)isc_mem_get(mctx, sizeof(*node) +
1431 region.length + labels + 1);
1434 return (ISC_R_NOMEMORY);
1437 PARENT(node) = NULL;
1442 #ifdef DNS_RBT_USEHASH
1443 HASHNEXT(node) = NULL;
1447 ISC_LINK_INIT(node, deadlink);
1452 dns_rbtnode_refinit(node, 0);
1453 node->find_callback = 0;
1459 * The following is stored to make reconstructing a name from the
1460 * stored value in the node easy: the length of the name, the number
1461 * of labels, whether the name is absolute or not, the name itself,
1462 * and the name's offsets table.
1465 * The offsets table could be made smaller by eliminating the
1466 * first offset, which is always 0. This requires changes to
1469 * Note: OLDOFFSETLEN *must* be assigned *after* OLDNAMELEN is assigned
1470 * as it uses OLDNAMELEN.
1472 OLDNAMELEN(node) = NAMELEN(node) = region.length;
1473 OLDOFFSETLEN(node) = OFFSETLEN(node) = labels;
1474 ATTRS(node) = name->attributes;
1476 memcpy(NAME(node), region.base, region.length);
1477 memcpy(OFFSETS(node), name->offsets, labels);
1479 #if DNS_RBT_USEMAGIC
1480 node->magic = DNS_RBTNODE_MAGIC;
1484 return (ISC_R_SUCCESS);
1487 #ifdef DNS_RBT_USEHASH
1489 hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
1492 HASHVAL(node) = dns_name_fullhash(name, ISC_FALSE);
1494 hash = HASHVAL(node) % rbt->hashsize;
1495 HASHNEXT(node) = rbt->hashtable[hash];
1497 rbt->hashtable[hash] = node;
1501 inithash(dns_rbt_t *rbt) {
1504 rbt->hashsize = RBT_HASH_SIZE;
1505 bytes = rbt->hashsize * sizeof(dns_rbtnode_t *);
1506 rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
1508 if (rbt->hashtable == NULL)
1509 return (ISC_R_NOMEMORY);
1511 memset(rbt->hashtable, 0, bytes);
1513 return (ISC_R_SUCCESS);
1517 rehash(dns_rbt_t *rbt) {
1518 unsigned int oldsize;
1519 dns_rbtnode_t **oldtable;
1520 dns_rbtnode_t *node;
1524 oldsize = rbt->hashsize;
1525 oldtable = rbt->hashtable;
1526 rbt->hashsize *= 2 + 1;
1527 rbt->hashtable = isc_mem_get(rbt->mctx,
1528 rbt->hashsize * sizeof(dns_rbtnode_t *));
1529 if (rbt->hashtable == NULL) {
1530 rbt->hashtable = oldtable;
1531 rbt->hashsize = oldsize;
1535 for (i = 0; i < rbt->hashsize; i++)
1536 rbt->hashtable[i] = NULL;
1538 for (i = 0; i < oldsize; i++) {
1540 while (node != NULL) {
1541 hash = HASHVAL(node) % rbt->hashsize;
1542 oldtable[i] = HASHNEXT(node);
1543 HASHNEXT(node) = rbt->hashtable[hash];
1544 rbt->hashtable[hash] = node;
1549 isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
1553 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
1555 REQUIRE(DNS_RBTNODE_VALID(node));
1557 if (rbt->nodecount >= (rbt->hashsize *3))
1560 hash_add_node(rbt, node, name);
1564 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1565 unsigned int bucket;
1566 dns_rbtnode_t *bucket_node;
1568 REQUIRE(DNS_RBTNODE_VALID(node));
1570 if (rbt->hashtable != NULL) {
1571 bucket = HASHVAL(node) % rbt->hashsize;
1572 bucket_node = rbt->hashtable[bucket];
1574 if (bucket_node == node)
1575 rbt->hashtable[bucket] = HASHNEXT(node);
1577 while (HASHNEXT(bucket_node) != node) {
1578 INSIST(HASHNEXT(bucket_node) != NULL);
1579 bucket_node = HASHNEXT(bucket_node);
1581 HASHNEXT(bucket_node) = HASHNEXT(node);
1585 #endif /* DNS_RBT_USEHASH */
1588 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1589 dns_rbtnode_t *child;
1591 REQUIRE(DNS_RBTNODE_VALID(node));
1592 REQUIRE(rootp != NULL);
1594 child = RIGHT(node);
1595 INSIST(child != NULL);
1597 RIGHT(node) = LEFT(child);
1598 if (LEFT(child) != NULL)
1599 PARENT(LEFT(child)) = node;
1603 PARENT(child) = PARENT(node);
1605 if (IS_ROOT(node)) {
1611 if (LEFT(PARENT(node)) == node)
1612 LEFT(PARENT(node)) = child;
1614 RIGHT(PARENT(node)) = child;
1617 PARENT(node) = child;
1621 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1622 dns_rbtnode_t *child;
1624 REQUIRE(DNS_RBTNODE_VALID(node));
1625 REQUIRE(rootp != NULL);
1628 INSIST(child != NULL);
1630 LEFT(node) = RIGHT(child);
1631 if (RIGHT(child) != NULL)
1632 PARENT(RIGHT(child)) = node;
1633 RIGHT(child) = node;
1636 PARENT(child) = PARENT(node);
1638 if (IS_ROOT(node)) {
1644 if (LEFT(PARENT(node)) == node)
1645 LEFT(PARENT(node)) = child;
1647 RIGHT(PARENT(node)) = child;
1650 PARENT(node) = child;
1654 * This is the real workhorse of the insertion code, because it does the
1655 * true red/black tree on a single level.
1658 dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
1659 dns_rbtnode_t **rootp)
1661 dns_rbtnode_t *child, *root, *parent, *grandparent;
1662 dns_name_t add_name, current_name;
1663 dns_offsets_t add_offsets, current_offsets;
1665 REQUIRE(rootp != NULL);
1666 REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
1667 RIGHT(node) == NULL);
1668 REQUIRE(current != NULL);
1673 * First node of a level.
1677 PARENT(node) = current;
1684 dns_name_init(&add_name, add_offsets);
1685 NODENAME(node, &add_name);
1687 dns_name_init(¤t_name, current_offsets);
1688 NODENAME(current, ¤t_name);
1691 INSIST(LEFT(current) == NULL);
1692 LEFT(current) = node;
1694 INSIST(RIGHT(current) == NULL);
1695 RIGHT(current) = node;
1698 INSIST(PARENT(node) == NULL);
1699 PARENT(node) = current;
1703 while (node != root && IS_RED(PARENT(node))) {
1705 * XXXDCL could do away with separate parent and grandparent
1706 * variables. They are vestiges of the days before parent
1707 * pointers. However, they make the code a little clearer.
1710 parent = PARENT(node);
1711 grandparent = PARENT(parent);
1713 if (parent == LEFT(grandparent)) {
1714 child = RIGHT(grandparent);
1715 if (child != NULL && IS_RED(child)) {
1718 MAKE_RED(grandparent);
1721 if (node == RIGHT(parent)) {
1722 rotate_left(parent, &root);
1724 parent = PARENT(node);
1725 grandparent = PARENT(parent);
1728 MAKE_RED(grandparent);
1729 rotate_right(grandparent, &root);
1732 child = LEFT(grandparent);
1733 if (child != NULL && IS_RED(child)) {
1736 MAKE_RED(grandparent);
1739 if (node == LEFT(parent)) {
1740 rotate_right(parent, &root);
1742 parent = PARENT(node);
1743 grandparent = PARENT(parent);
1746 MAKE_RED(grandparent);
1747 rotate_left(grandparent, &root);
1753 ENSURE(IS_ROOT(root));
1760 * This is the real workhorse of the deletion code, because it does the
1761 * true red/black tree on a single level.
1764 dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp) {
1765 dns_rbtnode_t *child, *sibling, *parent;
1766 dns_rbtnode_t *successor;
1768 REQUIRE(delete != NULL);
1771 * Verify that the parent history is (apparently) correct.
1773 INSIST((IS_ROOT(delete) && *rootp == delete) ||
1774 (! IS_ROOT(delete) &&
1775 (LEFT(PARENT(delete)) == delete ||
1776 RIGHT(PARENT(delete)) == delete)));
1780 if (LEFT(delete) == NULL) {
1781 if (RIGHT(delete) == NULL) {
1782 if (IS_ROOT(delete)) {
1784 * This is the only item in the tree.
1791 * This node has one child, on the right.
1793 child = RIGHT(delete);
1795 } else if (RIGHT(delete) == NULL)
1797 * This node has one child, on the left.
1799 child = LEFT(delete);
1801 dns_rbtnode_t holder, *tmp = &holder;
1804 * This node has two children, so it cannot be directly
1805 * deleted. Find its immediate in-order successor and
1806 * move it to this location, then do the deletion at the
1807 * old site of the successor.
1809 successor = RIGHT(delete);
1810 while (LEFT(successor) != NULL)
1811 successor = LEFT(successor);
1814 * The successor cannot possibly have a left child;
1815 * if there is any child, it is on the right.
1817 if (RIGHT(successor) != NULL)
1818 child = RIGHT(successor);
1821 * Swap the two nodes; it would be simpler to just replace
1822 * the value being deleted with that of the successor,
1823 * but this rigamarole is done so the caller has complete
1824 * control over the pointers (and memory allocation) of
1825 * all of nodes. If just the key value were removed from
1826 * the tree, the pointer to the node would be unchanged.
1830 * First, put the successor in the tree location of the
1831 * node to be deleted. Save its existing tree pointer
1832 * information, which will be needed when linking up
1833 * delete to the successor's old location.
1835 memcpy(tmp, successor, sizeof(dns_rbtnode_t));
1837 if (IS_ROOT(delete)) {
1839 successor->is_root = ISC_TRUE;
1840 delete->is_root = ISC_FALSE;
1843 if (LEFT(PARENT(delete)) == delete)
1844 LEFT(PARENT(delete)) = successor;
1846 RIGHT(PARENT(delete)) = successor;
1848 PARENT(successor) = PARENT(delete);
1849 LEFT(successor) = LEFT(delete);
1850 RIGHT(successor) = RIGHT(delete);
1851 COLOR(successor) = COLOR(delete);
1853 if (LEFT(successor) != NULL)
1854 PARENT(LEFT(successor)) = successor;
1855 if (RIGHT(successor) != successor)
1856 PARENT(RIGHT(successor)) = successor;
1859 * Now relink the node to be deleted into the
1860 * successor's previous tree location. PARENT(tmp)
1861 * is the successor's original parent.
1863 INSIST(! IS_ROOT(delete));
1865 if (PARENT(tmp) == delete) {
1867 * Node being deleted was successor's parent.
1869 RIGHT(successor) = delete;
1870 PARENT(delete) = successor;
1873 LEFT(PARENT(tmp)) = delete;
1874 PARENT(delete) = PARENT(tmp);
1878 * Original location of successor node has no left.
1880 LEFT(delete) = NULL;
1881 RIGHT(delete) = RIGHT(tmp);
1882 COLOR(delete) = COLOR(tmp);
1886 * Remove the node by removing the links from its parent.
1888 if (! IS_ROOT(delete)) {
1889 if (LEFT(PARENT(delete)) == delete)
1890 LEFT(PARENT(delete)) = child;
1892 RIGHT(PARENT(delete)) = child;
1895 PARENT(child) = PARENT(delete);
1899 * This is the root being deleted, and at this point
1900 * it is known to have just one child.
1904 PARENT(child) = PARENT(delete);
1908 * Fix color violations.
1910 if (IS_BLACK(delete)) {
1911 parent = PARENT(delete);
1913 while (child != *rootp && IS_BLACK(child)) {
1914 INSIST(child == NULL || ! IS_ROOT(child));
1916 if (LEFT(parent) == child) {
1917 sibling = RIGHT(parent);
1919 if (IS_RED(sibling)) {
1920 MAKE_BLACK(sibling);
1922 rotate_left(parent, rootp);
1923 sibling = RIGHT(parent);
1926 if (IS_BLACK(LEFT(sibling)) &&
1927 IS_BLACK(RIGHT(sibling))) {
1933 if (IS_BLACK(RIGHT(sibling))) {
1934 MAKE_BLACK(LEFT(sibling));
1936 rotate_right(sibling, rootp);
1937 sibling = RIGHT(parent);
1940 COLOR(sibling) = COLOR(parent);
1942 MAKE_BLACK(RIGHT(sibling));
1943 rotate_left(parent, rootp);
1949 * Child is parent's right child.
1950 * Everything is done the same as above,
1953 sibling = LEFT(parent);
1955 if (IS_RED(sibling)) {
1956 MAKE_BLACK(sibling);
1958 rotate_right(parent, rootp);
1959 sibling = LEFT(parent);
1962 if (IS_BLACK(LEFT(sibling)) &&
1963 IS_BLACK(RIGHT(sibling))) {
1968 if (IS_BLACK(LEFT(sibling))) {
1969 MAKE_BLACK(RIGHT(sibling));
1971 rotate_left(sibling, rootp);
1972 sibling = LEFT(parent);
1975 COLOR(sibling) = COLOR(parent);
1977 MAKE_BLACK(LEFT(sibling));
1978 rotate_right(parent, rootp);
1983 parent = PARENT(child);
1992 * This should only be used on the root of a tree, because no color fixup
1995 * NOTE: No root pointer maintenance is done, because the function is only
1996 * used for two cases:
1997 * + deleting everything DOWN from a node that is itself being deleted, and
1998 * + deleting the entire tree of trees from dns_rbt_destroy.
1999 * In each case, the root pointer is no longer relevant, so there
2000 * is no need for a root parameter to this function.
2002 * If the function is ever intended to be used to delete something where
2003 * a pointer needs to be told that this tree no longer exists,
2004 * this function would need to adjusted accordingly.
2007 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) {
2008 isc_result_t result = ISC_R_SUCCESS;
2009 REQUIRE(VALID_RBT(rbt));
2014 if (LEFT(node) != NULL) {
2015 result = dns_rbt_deletetree(rbt, LEFT(node));
2016 if (result != ISC_R_SUCCESS)
2020 if (RIGHT(node) != NULL) {
2021 result = dns_rbt_deletetree(rbt, RIGHT(node));
2022 if (result != ISC_R_SUCCESS)
2026 if (DOWN(node) != NULL) {
2027 result = dns_rbt_deletetree(rbt, DOWN(node));
2028 if (result != ISC_R_SUCCESS)
2033 if (result != ISC_R_SUCCESS)
2036 if (DATA(node) != NULL && rbt->data_deleter != NULL)
2037 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2039 unhash_node(rbt, node);
2040 #if DNS_RBT_USEMAGIC
2044 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2050 dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum,
2051 dns_rbtnode_t **nodep)
2053 dns_rbtnode_t *parent;
2054 dns_rbtnode_t *node = *nodep;
2055 REQUIRE(VALID_RBT(rbt));
2064 if (LEFT(node) != NULL) {
2068 if (DOWN(node) != NULL) {
2073 if (DATA(node) != NULL && rbt->data_deleter != NULL)
2074 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2077 * Note: we don't call unhash_node() here as we are destroying
2078 * the complete rbt tree.
2080 #if DNS_RBT_USEMAGIC
2083 parent = PARENT(node);
2084 if (RIGHT(node) != NULL)
2085 PARENT(RIGHT(node)) = parent;
2086 if (parent != NULL) {
2087 if (LEFT(parent) == node)
2088 LEFT(parent) = RIGHT(node);
2089 else if (DOWN(parent) == node)
2090 DOWN(parent) = RIGHT(node);
2092 parent = RIGHT(node);
2094 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2097 if (quantum != 0 && --quantum == 0) {
2105 dns_rbt_indent(int depth) {
2108 for (i = 0; i < depth; i++)
2113 dns_rbt_printnodename(dns_rbtnode_t *node) {
2116 char buffer[DNS_NAME_FORMATSIZE];
2117 dns_offsets_t offsets;
2119 r.length = NAMELEN(node);
2120 r.base = NAME(node);
2122 dns_name_init(&name, offsets);
2123 dns_name_fromregion(&name, &r);
2125 dns_name_format(&name, buffer, sizeof(buffer));
2127 printf("%s", buffer);
2131 dns_rbt_printtree(dns_rbtnode_t *root, dns_rbtnode_t *parent, int depth) {
2132 dns_rbt_indent(depth);
2135 dns_rbt_printnodename(root);
2136 printf(" (%s", IS_RED(root) ? "RED" : "black");
2139 dns_rbt_printnodename(parent);
2142 if ((! IS_ROOT(root) && PARENT(root) != parent) ||
2143 ( IS_ROOT(root) && depth > 0 &&
2144 DOWN(PARENT(root)) != root)) {
2146 printf(" (BAD parent pointer! -> ");
2147 if (PARENT(root) != NULL)
2148 dns_rbt_printnodename(PARENT(root));
2160 dns_rbt_indent(depth);
2161 printf("++ BEG down from ");
2162 dns_rbt_printnodename(root);
2164 dns_rbt_printtree(DOWN(root), NULL, depth);
2165 dns_rbt_indent(depth);
2166 printf("-- END down from ");
2167 dns_rbt_printnodename(root);
2171 if (IS_RED(root) && IS_RED(LEFT(root)))
2172 printf("** Red/Red color violation on left\n");
2173 dns_rbt_printtree(LEFT(root), root, depth);
2175 if (IS_RED(root) && IS_RED(RIGHT(root)))
2176 printf("** Red/Red color violation on right\n");
2177 dns_rbt_printtree(RIGHT(root), root, depth);
2184 dns_rbt_printall(dns_rbt_t *rbt) {
2185 REQUIRE(VALID_RBT(rbt));
2187 dns_rbt_printtree(rbt->root, NULL, 0);
2195 dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
2197 * Initialize 'chain'.
2200 REQUIRE(chain != NULL);
2204 chain->level_count = 0;
2205 chain->level_matches = 0;
2206 memset(chain->levels, 0, sizeof(chain->levels));
2208 chain->magic = CHAIN_MAGIC;
2212 dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
2213 dns_name_t *origin, dns_rbtnode_t **node)
2215 isc_result_t result = ISC_R_SUCCESS;
2217 REQUIRE(VALID_CHAIN(chain));
2222 if (chain->end == NULL)
2223 return (ISC_R_NOTFOUND);
2226 NODENAME(chain->end, name);
2228 if (chain->level_count == 0) {
2230 * Names in the top level tree are all absolute.
2231 * Always make 'name' relative.
2233 INSIST(dns_name_isabsolute(name));
2236 * This is cheaper than dns_name_getlabelsequence().
2240 name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
2244 if (origin != NULL) {
2245 if (chain->level_count > 0)
2246 result = chain_name(chain, origin, ISC_FALSE);
2248 result = dns_name_copy(dns_rootname, origin, NULL);
2255 dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
2258 dns_rbtnode_t *current, *previous, *predecessor;
2259 isc_result_t result = ISC_R_SUCCESS;
2260 isc_boolean_t new_origin = ISC_FALSE;
2262 REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2266 current = chain->end;
2268 if (LEFT(current) != NULL) {
2270 * Moving left one then right as far as possible is the
2271 * previous node, at least for this level.
2273 current = LEFT(current);
2275 while (RIGHT(current) != NULL)
2276 current = RIGHT(current);
2278 predecessor = current;
2282 * No left links, so move toward the root. If at any point on
2283 * the way there the link from parent to child is a right
2284 * link, then the parent is the previous node, at least
2287 while (! IS_ROOT(current)) {
2289 current = PARENT(current);
2291 if (RIGHT(current) == previous) {
2292 predecessor = current;
2298 if (predecessor != NULL) {
2300 * Found a predecessor node in this level. It might not
2301 * really be the predecessor, however.
2303 if (DOWN(predecessor) != NULL) {
2305 * The predecessor is really down at least one level.
2306 * Go down and as far right as possible, and repeat
2307 * as long as the rightmost node has a down pointer.
2311 * XXX DCL Need to do something about origins
2312 * here. See whether to go down, and if so
2313 * whether it is truly what Bob calls a
2316 ADD_LEVEL(chain, predecessor);
2317 predecessor = DOWN(predecessor);
2319 /* XXX DCL duplicated from above; clever
2320 * way to unduplicate? */
2322 while (RIGHT(predecessor) != NULL)
2323 predecessor = RIGHT(predecessor);
2324 } while (DOWN(predecessor) != NULL);
2326 /* XXX DCL probably needs work on the concept */
2328 new_origin = ISC_TRUE;
2331 } else if (chain->level_count > 0) {
2333 * Dang, didn't find a predecessor in this level.
2334 * Got to the root of this level without having traversed
2335 * any right links. Ascend the tree one level; the
2336 * node that points to this tree is the predecessor.
2338 INSIST(chain->level_count > 0 && IS_ROOT(current));
2339 predecessor = chain->levels[--chain->level_count];
2341 /* XXX DCL probably needs work on the concept */
2343 * Don't declare an origin change when the new origin is "."
2344 * at the top level tree, because "." is declared as the origin
2345 * for the second level tree.
2347 if (origin != NULL &&
2348 (chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
2349 new_origin = ISC_TRUE;
2352 if (predecessor != NULL) {
2353 chain->end = predecessor;
2356 result = dns_rbtnodechain_current(chain, name, origin,
2358 if (result == ISC_R_SUCCESS)
2359 result = DNS_R_NEWORIGIN;
2362 result = dns_rbtnodechain_current(chain, name, NULL,
2366 result = ISC_R_NOMORE;
2372 dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
2375 dns_rbtnode_t *current, *successor;
2376 isc_result_t result = ISC_R_SUCCESS;
2377 isc_boolean_t new_origin = ISC_FALSE;
2379 REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2383 current = chain->end;
2385 if (DOWN(current) != NULL) {
2387 * Don't declare an origin change when the new origin is "."
2388 * at the second level tree, because "." is already declared
2389 * as the origin for the top level tree.
2391 if (chain->level_count > 0 ||
2392 OFFSETLEN(current) > 1)
2393 new_origin = ISC_TRUE;
2395 ADD_LEVEL(chain, current);
2396 current = DOWN(current);
2398 while (LEFT(current) != NULL)
2399 current = LEFT(current);
2401 successor = current;
2404 if (successor != NULL) {
2405 chain->end = successor;
2408 * It is not necessary to use dns_rbtnodechain_current like
2409 * the other functions because this function will never
2410 * find a node in the topmost level. This is because the
2411 * root level will never be more than one name, and everything
2412 * in the megatree is a successor to that node, down at
2413 * the second level or below.
2417 NODENAME(chain->end, name);
2421 result = chain_name(chain, origin, ISC_FALSE);
2423 if (result == ISC_R_SUCCESS)
2424 result = DNS_R_NEWORIGIN;
2427 result = ISC_R_SUCCESS;
2430 result = ISC_R_NOMORE;
2436 dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name) {
2437 dns_rbtnode_t *current, *previous, *successor;
2438 isc_result_t result = ISC_R_SUCCESS;
2440 REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2444 current = chain->end;
2446 if (RIGHT(current) == NULL) {
2447 while (! IS_ROOT(current)) {
2449 current = PARENT(current);
2451 if (LEFT(current) == previous) {
2452 successor = current;
2457 current = RIGHT(current);
2459 while (LEFT(current) != NULL)
2460 current = LEFT(current);
2462 successor = current;
2465 if (successor != NULL) {
2466 chain->end = successor;
2469 NODENAME(chain->end, name);
2471 result = ISC_R_SUCCESS;
2473 result = ISC_R_NOMORE;
2479 dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
2482 dns_rbtnode_t *current, *previous, *successor;
2483 isc_result_t result = ISC_R_SUCCESS;
2484 isc_boolean_t new_origin = ISC_FALSE;
2486 REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
2490 current = chain->end;
2493 * If there is a level below this node, the next node is the leftmost
2494 * node of the next level.
2496 if (DOWN(current) != NULL) {
2498 * Don't declare an origin change when the new origin is "."
2499 * at the second level tree, because "." is already declared
2500 * as the origin for the top level tree.
2502 if (chain->level_count > 0 ||
2503 OFFSETLEN(current) > 1)
2504 new_origin = ISC_TRUE;
2506 ADD_LEVEL(chain, current);
2507 current = DOWN(current);
2509 while (LEFT(current) != NULL)
2510 current = LEFT(current);
2512 successor = current;
2514 } else if (RIGHT(current) == NULL) {
2516 * The successor is up, either in this level or a previous one.
2517 * Head back toward the root of the tree, looking for any path
2518 * that was via a left link; the successor is the node that has
2519 * that left link. In the event the root of the level is
2520 * reached without having traversed any left links, ascend one
2521 * level and look for either a right link off the point of
2522 * ascent, or search for a left link upward again, repeating
2523 * ascends until either case is true.
2526 while (! IS_ROOT(current)) {
2528 current = PARENT(current);
2530 if (LEFT(current) == previous) {
2531 successor = current;
2536 if (successor == NULL) {
2538 * Reached the root without having traversed
2539 * any left pointers, so this level is done.
2541 if (chain->level_count == 0)
2544 current = chain->levels[--chain->level_count];
2545 new_origin = ISC_TRUE;
2547 if (RIGHT(current) != NULL)
2550 } while (successor == NULL);
2553 if (successor == NULL && RIGHT(current) != NULL) {
2554 current = RIGHT(current);
2556 while (LEFT(current) != NULL)
2557 current = LEFT(current);
2559 successor = current;
2562 if (successor != NULL) {
2563 chain->end = successor;
2566 * It is not necessary to use dns_rbtnodechain_current like
2567 * the other functions because this function will never
2568 * find a node in the topmost level. This is because the
2569 * root level will never be more than one name, and everything
2570 * in the megatree is a successor to that node, down at
2571 * the second level or below.
2575 NODENAME(chain->end, name);
2579 result = chain_name(chain, origin, ISC_FALSE);
2581 if (result == ISC_R_SUCCESS)
2582 result = DNS_R_NEWORIGIN;
2585 result = ISC_R_SUCCESS;
2588 result = ISC_R_NOMORE;
2594 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2595 dns_name_t *name, dns_name_t *origin)
2598 isc_result_t result;
2600 REQUIRE(VALID_RBT(rbt));
2601 REQUIRE(VALID_CHAIN(chain));
2603 dns_rbtnodechain_reset(chain);
2605 chain->end = rbt->root;
2607 result = dns_rbtnodechain_current(chain, name, origin, NULL);
2609 if (result == ISC_R_SUCCESS)
2610 result = DNS_R_NEWORIGIN;
2616 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2617 dns_name_t *name, dns_name_t *origin)
2620 isc_result_t result;
2622 REQUIRE(VALID_RBT(rbt));
2623 REQUIRE(VALID_CHAIN(chain));
2625 dns_rbtnodechain_reset(chain);
2627 result = move_chain_to_last(chain, rbt->root);
2628 if (result != ISC_R_SUCCESS)
2631 result = dns_rbtnodechain_current(chain, name, origin, NULL);
2633 if (result == ISC_R_SUCCESS)
2634 result = DNS_R_NEWORIGIN;
2641 dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
2643 * Free any dynamic storage associated with 'chain', and then
2644 * reinitialize 'chain'.
2647 REQUIRE(VALID_CHAIN(chain));
2650 chain->level_count = 0;
2651 chain->level_matches = 0;
2655 dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
2657 * Free any dynamic storage associated with 'chain', and then
2658 * invalidate 'chain'.
2661 dns_rbtnodechain_reset(chain);