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