2 * Copyright (C) 2004-2009, 2014-2016 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2002 Internet Software Consortium.
5 * Permission to use, copy, modify, and/or distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15 * PERFORMANCE OF THIS SOFTWARE.
18 /* $Id: rbt.h,v 1.77 2009/11/04 01:18:19 marka Exp $ */
23 /*! \file dns/rbt.h */
26 #include <isc/magic.h>
27 #include <isc/refcount.h>
29 #include <dns/types.h>
33 #define DNS_RBT_USEHASH 1
37 * Option values for dns_rbt_findnode() and dns_rbt_findname().
38 * These are used to form a bitmask.
40 #define DNS_RBTFIND_NOOPTIONS 0x00
41 #define DNS_RBTFIND_EMPTYDATA 0x01
42 #define DNS_RBTFIND_NOEXACT 0x02
43 #define DNS_RBTFIND_NOPREDECESSOR 0x04
46 #ifndef DNS_RBT_USEISCREFCOUNT
47 #ifdef ISC_REFCOUNT_HAVEATOMIC
48 #define DNS_RBT_USEISCREFCOUNT 1
53 * These should add up to 30.
55 #define DNS_RBT_LOCKLENGTH 10
56 #define DNS_RBT_REFLENGTH 20
58 #define DNS_RBTNODE_MAGIC ISC_MAGIC('R','B','N','O')
60 #define DNS_RBTNODE_VALID(n) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC)
62 #define DNS_RBTNODE_VALID(n) ISC_TRUE
66 * This is the structure that is used for each node in the red/black
67 * tree of trees. NOTE WELL: the implementation manages this as a variable
68 * length structure, with the actual wire-format name and other data
69 * appended to this structure. Allocating a contiguous block of memory for
70 * multiple dns_rbtnode structures will not work.
72 typedef struct dns_rbtnode dns_rbtnode_t;
74 DNS_RBT_NSEC_NORMAL=0, /* in main tree */
75 DNS_RBT_NSEC_HAS_NSEC=1, /* also has node in nsec tree */
76 DNS_RBT_NSEC_NSEC=2, /* in nsec tree */
77 DNS_RBT_NSEC_NSEC3=3 /* in nsec3 tree */
85 * The following bitfields add up to a total bitwidth of 32.
86 * The range of values necessary for each item is indicated,
87 * but in the case of "attributes" the field is wider to accommodate
88 * possible future expansion.
90 * In each case below the "range" indicated is what's _necessary_ for
91 * the bitfield to hold, not what it actually _can_ hold.
93 * Note: Tree lock must be held before modifying these
96 * Note: The two "unsigned int :0;" unnamed bitfields on either
97 * side of the bitfields below are scaffolding that border the
98 * set of bitfields which are accessed after acquiring the tree
99 * lock. Please don't insert any other bitfield members between
100 * the unnamed bitfields unless they should also be accessed
101 * after acquiring the tree lock.
103 unsigned int :0; /* start of bitfields c/o tree lock */
104 unsigned int is_root : 1; /*%< range is 0..1 */
105 unsigned int color : 1; /*%< range is 0..1 */
106 unsigned int find_callback : 1; /*%< range is 0..1 */
107 unsigned int attributes : 3; /*%< range is 0..2 */
108 unsigned int nsec : 2; /*%< range is 0..3 */
109 unsigned int namelen : 8; /*%< range is 1..255 */
110 unsigned int offsetlen : 8; /*%< range is 1..128 */
111 unsigned int oldnamelen : 8; /*%< range is 1..255 */
114 /* node needs to be cleaned from rpz */
115 unsigned int rpz : 1;
116 unsigned int :0; /* end of bitfields c/o tree lock */
118 #ifdef DNS_RBT_USEHASH
119 unsigned int hashval;
120 dns_rbtnode_t *uppernode;
121 dns_rbtnode_t *hashnext;
123 dns_rbtnode_t *parent;
125 dns_rbtnode_t *right;
129 * Used for LRU cache. This linked list is used to mark nodes which
130 * have no data any longer, but we cannot unlink at that exact moment
131 * because we did not or could not obtain a write lock on the tree.
133 ISC_LINK(dns_rbtnode_t) deadlink;
137 * These values are used in the RBT DB implementation. The appropriate
138 * node lock must be held before accessing them.
140 * Note: The two "unsigned int :0;" unnamed bitfields on either
141 * side of the bitfields below are scaffolding that border the
142 * set of bitfields which are accessed after acquiring the node
143 * lock. Please don't insert any other bitfield members between
144 * the unnamed bitfields unless they should also be accessed
145 * after acquiring the node lock.
147 * NOTE: Do not merge these fields into bitfields above, as
148 * they'll all be put in the same qword that could be accessed
149 * without the node lock as it shares the qword with other
150 * members. Leave these members here so that they occupy a
151 * separate region of memory.
154 unsigned int :0; /* start of bitfields c/o node lock */
155 unsigned int dirty:1;
157 unsigned int locknum:DNS_RBT_LOCKLENGTH;
158 #ifndef DNS_RBT_USEISCREFCOUNT
159 unsigned int references:DNS_RBT_REFLENGTH;
161 unsigned int :0; /* end of bitfields c/o node lock */
162 #ifdef DNS_RBT_USEISCREFCOUNT
163 isc_refcount_t references; /* note that this is not in the bitfield */
168 typedef isc_result_t (*dns_rbtfindcallback_t)(dns_rbtnode_t *node,
177 * A chain is used to keep track of the sequence of nodes to reach any given
178 * node from the root of the tree. Originally nodes did not have parent
179 * pointers in them (for memory usage reasons) so there was no way to find
180 * the path back to the root from any given node. Now that nodes have parent
181 * pointers, chains might be going away in a future release, though the
182 * movement functionality would remain.
184 * In any event, parent information, whether via parent pointers or chains, is
185 * necessary information for iterating through the tree or for basic internal
186 * tree maintenance issues (ie, the rotations that are done to rebalance the
187 * tree when a node is added). The obvious implication of this is that for a
188 * chain to remain valid, the tree has to be locked down against writes for the
189 * duration of the useful life of the chain, because additions or removals can
190 * change the path from the root to the node the chain has targeted.
192 * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take
193 * dns_name_t parameters for the name and the origin, which can be NULL. If
194 * non-NULL, 'name' will end up pointing to the name data and offsets that are
195 * stored at the node (and thus it will be read-only), so it should be a
196 * regular dns_name_t that has been initialized with dns_name_init. When
197 * 'origin' is non-NULL, it will get the name of the origin stored in it, so it
198 * needs to have its own buffer space and offsets, which is most easily
199 * accomplished with a dns_fixedname_t. It is _not_ necessary to reinitialize
200 * either 'name' or 'origin' between calls to the chain functions.
202 * NOTE WELL: even though the name data at the root of the tree of trees will
203 * be absolute (typically just "."), it will will be made into a relative name
204 * with an origin of "." -- an empty name when the node is ".". This is
205 * because a common on operation on 'name' and 'origin' is to use
206 * dns_name_concatenate() on them to generate the complete name. An empty name
207 * can be detected when dns_name_countlabels == 0, and is printed by
208 * dns_name_totext()/dns_name_format() as "@", consistent with RFC1035's
209 * definition of "@" as the current origin.
211 * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next
212 * functions but additionally can provide the node to which the chain points.
216 * The number of level blocks to allocate at a time. Currently the maximum
217 * number of levels is allocated directly in the structure, but future
218 * revisions of this code might have a static initial block with dynamic
219 * growth. Allocating space for 256 levels when the tree is almost never that
220 * deep is wasteful, but it's not clear that it matters, since the waste is
221 * only 2MB for 1000 concurrently active chains on a system with 64-bit
224 #define DNS_RBT_LEVELBLOCK 254
226 typedef struct dns_rbtnodechain {
230 * The terminal node of the chain. It is not in levels[].
231 * This is ostensibly private ... but in a pinch it could be
232 * used tell that the chain points nowhere without needing to
233 * call dns_rbtnodechain_current().
237 * The maximum number of labels in a name is 128; bitstrings mean
238 * a conceptually very large number (which I have not bothered to
239 * compute) of logical levels because splitting can potentially occur
240 * at each bit. However, DNSSEC restricts the number of "logical"
241 * labels in a name to 255, meaning only 254 pointers are needed
244 dns_rbtnode_t * levels[DNS_RBT_LEVELBLOCK];
246 * level_count indicates how deep the chain points into the
247 * tree of trees, and is the index into the levels[] array.
248 * Thus, levels[level_count - 1] is the last level node stored.
249 * A chain that points to the top level of the tree of trees has
250 * a level_count of 0, the first level has a level_count of 1, and
253 unsigned int level_count;
255 * level_matches tells how many levels matched above the node
256 * returned by dns_rbt_findnode(). A match (partial or exact) found
257 * in the first level thus results in level_matches being set to 1.
258 * This is used by the rbtdb to set the start point for a recursive
259 * search of superdomains until the RR it is looking for is found.
261 unsigned int level_matches;
262 } dns_rbtnodechain_t;
265 ***** Public interfaces.
268 dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
269 void *deleter_arg, dns_rbt_t **rbtp);
271 * Initialize a red-black tree of trees.
274 *\li The deleter argument, if non-null, points to a function that is
275 * responsible for cleaning up any memory associated with the data
276 * pointer of a node when the node is deleted. It is passed the
277 * deleted node's data pointer as its first argument and deleter_arg
278 * as its second argument.
281 * \li mctx is a pointer to a valid memory context.
282 *\li rbtp != NULL && *rbtp == NULL
283 *\li arg == NULL iff deleter == NULL
286 *\li If result is ISC_R_SUCCESS:
287 * *rbtp points to a valid red-black tree manager
289 *\li If result is failure:
290 * *rbtp does not point to a valid red-black tree manager.
293 *\li #ISC_R_SUCCESS Success
294 *\li #ISC_R_NOMEMORY Resource limit: Out of Memory
298 dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data);
300 * Add 'name' to the tree of trees, associated with 'data'.
303 *\li 'data' is never required to be non-NULL, but specifying it
304 * when the name is added is faster than searching for 'name'
305 * again and then setting the data pointer. The lack of a data pointer
306 * for a node also has other ramifications regarding whether
307 * dns_rbt_findname considers a node to exist, or dns_rbt_deletename
311 *\li rbt is a valid rbt manager.
312 *\li dns_name_isabsolute(name) == TRUE
315 *\li 'name' is not altered in any way.
317 *\li Any external references to nodes in the tree are unaffected by
318 * node splits that are necessary to insert the new name.
320 *\li If result is #ISC_R_SUCCESS:
321 * 'name' is findable in the red/black tree of trees in O(log N).
322 * The data pointer of the node for 'name' is set to 'data'.
324 *\li If result is #ISC_R_EXISTS or #ISC_R_NOSPACE:
325 * The tree of trees is unaltered.
327 *\li If result is #ISC_R_NOMEMORY:
331 *\li #ISC_R_SUCCESS Success
332 *\li #ISC_R_EXISTS The name already exists with associated data.
333 *\li #ISC_R_NOSPACE The name had more logical labels than are allowed.
334 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory
338 dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep);
341 * Just like dns_rbt_addname, but returns the address of the node.
344 *\li rbt is a valid rbt structure.
345 *\li dns_name_isabsolute(name) == TRUE
346 *\li nodep != NULL && *nodep == NULL
349 *\li 'name' is not altered in any way.
351 *\li Any external references to nodes in the tree are unaffected by
352 * node splits that are necessary to insert the new name.
354 *\li If result is ISC_R_SUCCESS:
355 * 'name' is findable in the red/black tree of trees in O(log N).
356 * *nodep is the node that was added for 'name'.
358 *\li If result is ISC_R_EXISTS:
359 * The tree of trees is unaltered.
360 * *nodep is the existing node for 'name'.
362 *\li If result is ISC_R_NOMEMORY:
366 *\li #ISC_R_SUCCESS Success
367 *\li #ISC_R_EXISTS The name already exists, possibly without data.
368 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory
372 dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
373 dns_name_t *foundname, void **data);
375 * Get the data pointer associated with 'name'.
378 *\li When #DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is
379 * returned (also subject to #DNS_RBTFIND_EMPTYDATA), even when there is
380 * an exact match in the tree.
382 *\li A node that has no data is considered not to exist for this function,
383 * unless the #DNS_RBTFIND_EMPTYDATA option is set.
386 *\li rbt is a valid rbt manager.
387 *\li dns_name_isabsolute(name) == TRUE
388 *\li data != NULL && *data == NULL
391 *\li 'name' and the tree are not altered in any way.
393 *\li If result is ISC_R_SUCCESS:
394 * *data is the data associated with 'name'.
396 *\li If result is DNS_R_PARTIALMATCH:
397 * *data is the data associated with the deepest superdomain
398 * of 'name' which has data.
400 *\li If result is ISC_R_NOTFOUND:
401 * Neither the name nor a superdomain was found with data.
404 *\li #ISC_R_SUCCESS Success
405 *\li #DNS_R_PARTIALMATCH Superdomain found with data
406 *\li #ISC_R_NOTFOUND No match
407 *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed
411 dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
412 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
413 unsigned int options, dns_rbtfindcallback_t callback,
416 * Find the node for 'name'.
419 *\li A node that has no data is considered not to exist for this function,
420 * unless the DNS_RBTFIND_EMPTYDATA option is set. This applies to both
421 * exact matches and partial matches.
423 *\li If the chain parameter is non-NULL, then the path through the tree
424 * to the DNSSEC predecessor of the searched for name is maintained,
425 * unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option
426 * is used. (For more details on those options, see below.)
428 *\li If there is no predecessor, then the chain will point to nowhere, as
429 * indicated by chain->end being NULL or dns_rbtnodechain_current
430 * returning ISC_R_NOTFOUND. Note that in a normal Internet DNS RBT
431 * there will always be a predecessor for all names except the root
432 * name, because '.' will exist and '.' is the predecessor of
433 * everything. But you can certainly construct a trivial tree and a
434 * search for it that has no predecessor.
436 *\li Within the chain structure, the 'levels' member of the structure holds
437 * the root node of each level except the first.
439 *\li The 'level_count' of the chain indicates how deep the chain to the
440 * predecessor name is, as an index into the 'levels[]' array. It does
441 * not count name elements, per se, but only levels of the tree of trees,
442 * the distinction arising because multiple labels from a name can be
443 * stored on only one level. It is also does not include the level
444 * that has the node, since that level is not stored in levels[].
446 *\li The chain's 'level_matches' is not directly related to the predecessor.
447 * It is the number of levels above the level of the found 'node',
448 * regardless of whether it was a partial match or exact match. When
449 * the node is found in the top level tree, or no node is found at all,
450 * level_matches is 0.
452 *\li When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is
453 * returned (also subject to DNS_RBTFIND_EMPTYDATA), even when
454 * there is an exact match in the tree. In this case, the chain
455 * will not point to the DNSSEC predecessor, but will instead point
456 * to the exact match, if there was any. Thus the preceding paragraphs
457 * should have "exact match" substituted for "predecessor" to describe
458 * how the various elements of the chain are set. This was done to
459 * ensure that the chain's state was sane, and to prevent problems that
460 * occurred when running the predecessor location code under conditions
461 * it was not designed for. It is not clear *where* the chain should
462 * point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain
463 * with this option because you want a particular node, let us know
464 * where you want the chain pointed, so this can be made more firm.
467 *\li rbt is a valid rbt manager.
468 *\li dns_name_isabsolute(name) == TRUE.
469 *\li node != NULL && *node == NULL.
470 *\li #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually
474 *\li 'name' and the tree are not altered in any way.
476 *\li If result is ISC_R_SUCCESS:
478 * *node is the terminal node for 'name'.
480 * 'foundname' and 'name' represent the same name (though not
483 * 'chain' points to the DNSSEC predecessor, if any, of 'name'.
485 * chain->level_matches and chain->level_count are equal.
488 * If result is DNS_R_PARTIALMATCH:
490 * *node is the data associated with the deepest superdomain
491 * of 'name' which has data.
493 * 'foundname' is the name of deepest superdomain (which has
494 * data, unless the DNS_RBTFIND_EMPTYDATA option is set).
496 * 'chain' points to the DNSSEC predecessor, if any, of 'name'.
499 *\li If result is ISC_R_NOTFOUND:
501 * Neither the name nor a superdomain was found. *node is NULL.
503 * 'chain' points to the DNSSEC predecessor, if any, of 'name'.
505 * chain->level_matches is 0.
509 *\li #ISC_R_SUCCESS Success
510 *\li #DNS_R_PARTIALMATCH Superdomain found with data
511 *\li #ISC_R_NOTFOUND No match, or superdomain with no data
512 *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed
516 dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse);
518 * Delete 'name' from the tree of trees.
521 *\li When 'name' is removed, if recurse is ISC_TRUE then all of its
522 * subnames are removed too.
525 *\li rbt is a valid rbt manager.
526 *\li dns_name_isabsolute(name) == TRUE
529 *\li 'name' is not altered in any way.
531 *\li Does NOT ensure that any external references to nodes in the tree
532 * are unaffected by node joins.
534 *\li If result is ISC_R_SUCCESS:
535 * 'name' does not appear in the tree with data; however,
536 * the node for the name might still exist which can be
537 * found with dns_rbt_findnode (but not dns_rbt_findname).
539 *\li If result is ISC_R_NOTFOUND:
540 * 'name' does not appear in the tree with data, because
541 * it did not appear in the tree before the function was called.
543 *\li If result is something else:
544 * See result codes for dns_rbt_findnode (if it fails, the
545 * node is not deleted) or dns_rbt_deletenode (if it fails,
546 * the node is deleted, but the tree is not optimized when
547 * it could have been).
550 *\li #ISC_R_SUCCESS Success
551 *\li #ISC_R_NOTFOUND No match
552 *\li something_else Any return code from dns_rbt_findnode except
553 * DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND
554 * to be returned instead), and any code from
555 * dns_rbt_deletenode.
559 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse);
561 * Delete 'node' from the tree of trees.
564 *\li When 'node' is removed, if recurse is ISC_TRUE then all nodes
565 * in levels down from it are removed too.
568 *\li rbt is a valid rbt manager.
572 *\li Does NOT ensure that any external references to nodes in the tree
573 * are unaffected by node joins.
575 *\li If result is ISC_R_SUCCESS:
576 * 'node' does not appear in the tree with data; however,
577 * the node might still exist if it serves as a pointer to
578 * a lower tree level as long as 'recurse' was false, hence
579 * the node could can be found with dns_rbt_findnode when
580 * that function's empty_data_ok parameter is true.
582 *\li If result is ISC_R_NOMEMORY or ISC_R_NOSPACE:
583 * The node was deleted, but the tree structure was not
587 *\li #ISC_R_SUCCESS Success
588 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes.
589 *\li #ISC_R_NOSPACE dns_name_concatenate failed when joining nodes.
593 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name);
595 * Convert the sequence of labels stored at 'node' into a 'name'.
598 *\li This function does not return the full name, from the root, but
599 * just the labels at the indicated node.
601 *\li The name data pointed to by 'name' is the information stored
602 * in the node, not a copy. Altering the data at this pointer
603 * will likely cause grief.
606 * \li name->offsets == NULL
609 * \li 'name' is DNS_NAMEATTR_READONLY.
611 * \li 'name' will point directly to the labels stored after the
612 * dns_rbtnode_t struct.
614 * \li 'name' will have offsets that also point to the information stored
615 * as part of the node.
619 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name);
621 * Like dns_rbt_namefromnode, but returns the full name from the root.
624 * \li Unlike dns_rbt_namefromnode, the name will not point directly
625 * to node data. Rather, dns_name_concatenate will be used to copy
626 * the name data from each node into the 'name' argument.
630 * \li name has a dedicated buffer.
634 * \li ISC_R_NOSPACE (possible via dns_name_concatenate)
635 * \li DNS_R_NAMETOOLONG (possible via dns_name_concatenate)
639 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname,
642 * Format the full name of a node for printing, using dns_name_format().
645 * \li 'size' is the length of the printname buffer. This should be
646 * DNS_NAME_FORMATSIZE or larger.
649 * \li node and printname are not NULL.
652 * \li The 'printname' pointer.
656 dns_rbt_nodecount(dns_rbt_t *rbt);
658 * Obtain the number of nodes in the tree of trees.
661 * \li rbt is a valid rbt manager.
665 dns_rbt_destroy(dns_rbt_t **rbtp);
667 dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum);
669 * Stop working with a red-black tree of trees.
670 * If 'quantum' is zero then the entire tree will be destroyed.
671 * If 'quantum' is non zero then up to 'quantum' nodes will be destroyed
672 * allowing the rbt to be incrementally destroyed by repeated calls to
673 * dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other
674 * operations than dns_rbt_destroy()/dns_rbt_destroy2() should be
675 * performed on the tree of trees.
678 * \li *rbt is a valid rbt manager.
680 * Ensures on ISC_R_SUCCESS:
681 * \li All space allocated by the RBT library has been returned.
683 * \li *rbt is invalidated as an rbt manager.
687 * \li ISC_R_QUOTA if 'quantum' nodes have been destroyed.
691 dns_rbt_printall(dns_rbt_t *rbt);
693 * Print an ASCII representation of the internal structure of the red-black
697 * \li The name stored at each node, along with the node's color, is printed.
698 * Then the down pointer, left and right pointers are displayed
699 * recursively in turn. NULL down pointers are silently omitted;
700 * NULL left and right pointers are printed.
704 ***** Chain Functions
708 dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx);
710 * Initialize 'chain'.
713 *\li 'chain' is a valid pointer.
715 *\li 'mctx' is a valid memory context.
718 *\li 'chain' is suitable for use.
722 dns_rbtnodechain_reset(dns_rbtnodechain_t *chain);
724 * Free any dynamic storage associated with 'chain', and then reinitialize
728 *\li 'chain' is a valid pointer.
731 *\li 'chain' is suitable for use, and uses no dynamic storage.
735 dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain);
737 * Free any dynamic storage associated with 'chain', and then invalidates it.
740 *\li Future calls to any dns_rbtnodechain_ function will need to call
741 * dns_rbtnodechain_init on the chain first (except, of course,
742 * dns_rbtnodechain_init itself).
745 *\li 'chain' is a valid chain.
748 *\li 'chain' is no longer suitable for use, and uses no dynamic storage.
752 dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
753 dns_name_t *origin, dns_rbtnode_t **node);
755 * Provide the name, origin and node to which the chain is currently pointed.
758 *\li The tree need not have be locked against additions for the chain
759 * to remain valid, however there are no guarantees if any deletion
760 * has been made since the chain was established.
763 *\li 'chain' is a valid chain.
766 *\li 'node', if non-NULL, is the node to which the chain was pointed
767 * by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last.
768 * If none were called for the chain since it was initialized or reset,
769 * or if the was no predecessor to the name searched for with
770 * dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned.
772 *\li 'name', if non-NULL, is the name stored at the terminal level of
773 * the chain. This is typically a single label, like the "www" of
774 * "www.isc.org", but need not be so. At the root of the tree of trees,
775 * if the node is "." then 'name' is ".", otherwise it is relative to ".".
776 * (Minimalist and atypical case: if the tree has just the name
777 * "isc.org." then the root node's stored name is "isc.org." but 'name'
778 * will be "isc.org".)
780 *\li 'origin', if non-NULL, is the sequence of labels in the levels
781 * above the terminal level, such as "isc.org." in the above example.
782 * 'origin' is always "." for the root node.
786 *\li #ISC_R_SUCCESS name, origin & node were successfully set.
787 *\li #ISC_R_NOTFOUND The chain does not point to any node.
788 *\li <something_else> Any error return from dns_name_concatenate.
792 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
793 dns_name_t *name, dns_name_t *origin);
795 * Set the chain to the lexically first node in the tree of trees.
798 *\li By the definition of ordering for DNS names, the root of the tree of
799 * trees is the very first node, since everything else in the megatree
800 * uses it as a common suffix.
803 *\li 'chain' is a valid chain.
804 *\li 'rbt' is a valid rbt manager.
807 *\li The chain points to the very first node of the tree.
809 *\li 'name' and 'origin', if non-NULL, are set as described for
810 * dns_rbtnodechain_current. Thus 'origin' will always be ".".
813 *\li #DNS_R_NEWORIGIN The name & origin were successfully set.
814 *\li <something_else> Any error result from dns_rbtnodechain_current.
818 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
819 dns_name_t *name, dns_name_t *origin);
821 * Set the chain to the lexically last node in the tree of trees.
824 *\li 'chain' is a valid chain.
825 *\li 'rbt' is a valid rbt manager.
828 *\li The chain points to the very last node of the tree.
830 *\li 'name' and 'origin', if non-NULL, are set as described for
831 * dns_rbtnodechain_current.
834 *\li #DNS_R_NEWORIGIN The name & origin were successfully set.
835 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory building chain.
836 *\li <something_else> Any error result from dns_name_concatenate.
840 dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
843 * Adjusts chain to point the DNSSEC predecessor of the name to which it
844 * is currently pointed.
847 *\li 'chain' is a valid chain.
848 *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode,
849 * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that
850 * dns_rbt_findnode is not guaranteed to point the chain somewhere,
851 * since there may have been no predecessor to the searched for name.
854 *\li The chain is pointed to the predecessor of its current target.
856 *\li 'name' and 'origin', if non-NULL, are set as described for
857 * dns_rbtnodechain_current.
859 *\li 'origin' is only if a new origin was found.
862 *\li #ISC_R_SUCCESS The predecessor was found and 'name' was set.
863 *\li #DNS_R_NEWORIGIN The predecessor was found with a different
864 * origin and 'name' and 'origin' were set.
865 *\li #ISC_R_NOMORE There was no predecessor.
866 *\li <something_else> Any error result from dns_rbtnodechain_current.
870 dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
873 * Adjusts chain to point the DNSSEC successor of the name to which it
874 * is currently pointed.
877 *\li 'chain' is a valid chain.
878 *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode,
879 * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that
880 * dns_rbt_findnode is not guaranteed to point the chain somewhere,
881 * since there may have been no predecessor to the searched for name.
884 *\li The chain is pointed to the successor of its current target.
886 *\li 'name' and 'origin', if non-NULL, are set as described for
887 * dns_rbtnodechain_current.
889 *\li 'origin' is only if a new origin was found.
892 *\li #ISC_R_SUCCESS The successor was found and 'name' was set.
893 *\li #DNS_R_NEWORIGIN The successor was found with a different
894 * origin and 'name' and 'origin' were set.
895 *\li #ISC_R_NOMORE There was no successor.
896 *\li <something_else> Any error result from dns_name_concatenate.
900 dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
903 * Descend down if possible.
907 dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name);
909 * Find the next node at the current depth in DNSSEC order.
913 * Wrapper macros for manipulating the rbtnode reference counter:
914 * Since we selectively use isc_refcount_t for the reference counter of
915 * a rbtnode, operations on the counter depend on the actual type of it.
916 * The following macros provide a common interface to these operations,
917 * hiding the back-end. The usage is the same as that of isc_refcount_xxx().
919 #ifdef DNS_RBT_USEISCREFCOUNT
920 #define dns_rbtnode_refinit(node, n) \
922 isc_refcount_init(&(node)->references, (n)); \
924 #define dns_rbtnode_refdestroy(node) \
926 isc_refcount_destroy(&(node)->references); \
928 #define dns_rbtnode_refcurrent(node) \
929 isc_refcount_current(&(node)->references)
930 #define dns_rbtnode_refincrement0(node, refs) \
932 isc_refcount_increment0(&(node)->references, (refs)); \
934 #define dns_rbtnode_refincrement(node, refs) \
936 isc_refcount_increment(&(node)->references, (refs)); \
938 #define dns_rbtnode_refdecrement(node, refs) \
940 isc_refcount_decrement(&(node)->references, (refs)); \
942 #else /* DNS_RBT_USEISCREFCOUNT */
943 #define dns_rbtnode_refinit(node, n) ((node)->references = (n))
944 #define dns_rbtnode_refdestroy(node) REQUIRE((node)->references == 0)
945 #define dns_rbtnode_refcurrent(node) ((node)->references)
947 #if (__STDC_VERSION__ + 0) >= 199901L || defined __GNUC__
949 dns_rbtnode_refincrement0(dns_rbtnode_t *node, unsigned int *refs) {
952 *refs = node->references;
956 dns_rbtnode_refincrement(dns_rbtnode_t *node, unsigned int *refs) {
957 REQUIRE(node->references > 0);
960 *refs = node->references;
964 dns_rbtnode_refdecrement(dns_rbtnode_t *node, unsigned int *refs) {
965 REQUIRE(node->references > 0);
968 *refs = node->references;
971 #define dns_rbtnode_refincrement0(node, refs) \
973 unsigned int *_tmp = (unsigned int *)(refs); \
974 (node)->references++; \
975 if ((_tmp) != NULL) \
976 (*_tmp) = (node)->references; \
978 #define dns_rbtnode_refincrement(node, refs) \
980 REQUIRE((node)->references > 0); \
981 (node)->references++; \
982 if ((refs) != NULL) \
983 (*refs) = (node)->references; \
985 #define dns_rbtnode_refdecrement(node, refs) \
987 REQUIRE((node)->references > 0); \
988 (node)->references--; \
989 if ((refs) != NULL) \
990 (*refs) = (node)->references; \
993 #endif /* DNS_RBT_USEISCREFCOUNT */
997 #endif /* DNS_RBT_H */