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