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