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