#$@%#$%!

Ngiler SH3LL 360
: / proc / thread-self / root / usr / include / bind9 / dns /

Information Server
MySQL : OFF Perl : OFF CURL : ON WGET : OFF PKEXEC : OFF

Directive	Local Value
IP Address	162.0.209.101
System	Linux premium169.web-hosting.com 4.18.0-553.50.1.lve.el8.x86_64 #1 SMP Thu Apr 17 19:10:24 UTC 2025 x86_64
User	luxeelil
PHP Version	8.0.30
Software	LiteSpeed
Doc root	Writable

Edit File : rbt.h \| Size : 39.67 KB
/* * Copyright (C) Internet Systems Consortium, Inc. ("ISC") * * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, you can obtain one at https://mozilla.org/MPL/2.0/. * * See the COPYRIGHT file distributed with this work for additional * information regarding copyright ownership. / #ifndef DNS_RBT_H #define DNS_RBT_H 1 /! \file dns/rbt.h / #include <inttypes.h> #include <stdbool.h> #include <isc/assertions.h> #include <isc/crc64.h> #include <isc/lang.h> #include <isc/magic.h> #include <isc/refcount.h> #include <dns/types.h> ISC_LANG_BEGINDECLS #define DNS_RBT_USEHASH 1 /@{/ /% * Option values for dns_rbt_findnode() and dns_rbt_findname(). * These are used to form a bitmask. / #define DNS_RBTFIND_NOOPTIONS 0x00 #define DNS_RBTFIND_EMPTYDATA 0x01 #define DNS_RBTFIND_NOEXACT 0x02 #define DNS_RBTFIND_NOPREDECESSOR 0x04 /@}/ #ifndef DNS_RBT_USEISCREFCOUNT #ifdef ISC_REFCOUNT_HAVEATOMIC #define DNS_RBT_USEISCREFCOUNT 1 #endif #endif #define DNS_RBT_USEMAGIC 1 / * These should add up to 30. / #define DNS_RBT_LOCKLENGTH 10 #define DNS_RBT_REFLENGTH 20 #define DNS_RBTNODE_MAGIC ISC_MAGIC('R','B','N','O') #if DNS_RBT_USEMAGIC #define DNS_RBTNODE_VALID(n) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC) #else #define DNS_RBTNODE_VALID(n) true #endif /% * This is the structure that is used for each node in the red/black * tree of trees. NOTE WELL: the implementation manages this as a variable * length structure, with the actual wire-format name and other data * appended to this structure. Allocating a contiguous block of memory for * multiple dns_rbtnode structures will not work. / typedef struct dns_rbtnode dns_rbtnode_t; enum { DNS_RBT_NSEC_NORMAL=0, / in main tree / DNS_RBT_NSEC_HAS_NSEC=1, / also has node in nsec tree / DNS_RBT_NSEC_NSEC=2, / in nsec tree / DNS_RBT_NSEC_NSEC3=3 / in nsec3 tree / }; struct dns_rbtnode { #if DNS_RBT_USEMAGIC unsigned int magic; #endif /@{/ /! * The following bitfields add up to a total bitwidth of 32. * The range of values necessary for each item is indicated, * but in the case of "attributes" the field is wider to accommodate * possible future expansion. * * In each case below the "range" indicated is what's _necessary_ for * the bitfield to hold, not what it actually _can_ hold. * * Note: Tree lock must be held before modifying these * bit-fields. * * Note: The two "unsigned int :0;" unnamed bitfields on either * side of the bitfields below are scaffolding that border the * set of bitfields which are accessed after acquiring the tree * lock. Please don't insert any other bitfield members between * the unnamed bitfields unless they should also be accessed * after acquiring the tree lock. / unsigned int :0; / start of bitfields c/o tree lock / unsigned int is_root : 1; /%< range is 0..1 / unsigned int color : 1; /%< range is 0..1 / unsigned int find_callback : 1; /%< range is 0..1 / unsigned int attributes : 3; /%< range is 0..2 / unsigned int nsec : 2; /%< range is 0..3 / unsigned int namelen : 8; /%< range is 1..255 / unsigned int offsetlen : 8; /%< range is 1..128 / unsigned int oldnamelen : 8; /%< range is 1..255 / /@}/ / flags needed for serialization to file/ unsigned int is_mmapped : 1; unsigned int parent_is_relative : 1; unsigned int left_is_relative : 1; unsigned int right_is_relative : 1; unsigned int down_is_relative : 1; unsigned int data_is_relative : 1; / node needs to be cleaned from rpz / unsigned int rpz : 1; unsigned int :0; / end of bitfields c/o tree lock / #ifdef DNS_RBT_USEHASH unsigned int hashval; dns_rbtnode_t uppernode; dns_rbtnode_t hashnext; #endif dns_rbtnode_t parent; dns_rbtnode_t left; dns_rbtnode_t right; dns_rbtnode_t down; /% * Used for LRU cache. This linked list is used to mark nodes which * have no data any longer, but we cannot unlink at that exact moment * because we did not or could not obtain a write lock on the tree. / ISC_LINK(dns_rbtnode_t) deadlink; /@{/ /! * These values are used in the RBT DB implementation. The appropriate * node lock must be held before accessing them. * * Note: The two "unsigned int :0;" unnamed bitfields on either * side of the bitfields below are scaffolding that border the * set of bitfields which are accessed after acquiring the node * lock. Please don't insert any other bitfield members between * the unnamed bitfields unless they should also be accessed * after acquiring the node lock. * * NOTE: Do not merge these fields into bitfields above, as * they'll all be put in the same qword that could be accessed * without the node lock as it shares the qword with other * members. Leave these members here so that they occupy a * separate region of memory. / void data; unsigned int locknum; unsigned int :0; /* start of bitfields c/o node lock / unsigned int dirty:1; unsigned int wild:1; #ifndef DNS_RBT_USEISCREFCOUNT unsigned int references:DNS_RBT_REFLENGTH; #endif unsigned int :0; / end of bitfields c/o node lock / #ifdef DNS_RBT_USEISCREFCOUNT isc_refcount_t references; / note that this is not in the bitfield / #endif /@}/ }; typedef isc_result_t (dns_rbtfindcallback_t)(dns_rbtnode_t node, dns_name_t name, void callback_arg); typedef isc_result_t (dns_rbtdatawriter_t)(FILE file, unsigned char data, void arg, uint64_t crc); typedef isc_result_t (dns_rbtdatafixer_t)(dns_rbtnode_t rbtnode, void base, size_t offset, void arg, uint64_t crc); typedef void (dns_rbtdeleter_t)(void , void ); /*** * Chain Info **/ /! * A chain is used to keep track of the sequence of nodes to reach any given * node from the root of the tree. Originally nodes did not have parent * pointers in them (for memory usage reasons) so there was no way to find * the path back to the root from any given node. Now that nodes have parent * pointers, chains might be going away in a future release, though the * movement functionality would remain. * * Chains may be used to iterate over a tree of trees. After setting up the * chain's structure using dns_rbtnodechain_init(), it needs to be initialized * to point to the lexically first or lexically last node in the tree of trees * using dns_rbtnodechain_first() or dns_rbtnodechain_last(), respectively. * Calling dns_rbtnodechain_next() or dns_rbtnodechain_prev() then moves the * chain over to the next or previous node, respectively. * * In any event, parent information, whether via parent pointers or chains, is * necessary information for iterating through the tree or for basic internal * tree maintenance issues (ie, the rotations that are done to rebalance the * tree when a node is added). The obvious implication of this is that for a * chain to remain valid, the tree has to be locked down against writes for the * duration of the useful life of the chain, because additions or removals can * change the path from the root to the node the chain has targeted. * * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take * dns_name_t parameters for the name and the origin, which can be NULL. If * non-NULL, 'name' will end up pointing to the name data and offsets that are * stored at the node (and thus it will be read-only), so it should be a * regular dns_name_t that has been initialized with dns_name_init. When * 'origin' is non-NULL, it will get the name of the origin stored in it, so it * needs to have its own buffer space and offsets, which is most easily * accomplished with a dns_fixedname_t. It is _not_ necessary to reinitialize * either 'name' or 'origin' between calls to the chain functions. * * NOTE WELL: even though the name data at the root of the tree of trees will * be absolute (typically just "."), it will will be made into a relative name * with an origin of "." -- an empty name when the node is ".". This is * because a common on operation on 'name' and 'origin' is to use * dns_name_concatenate() on them to generate the complete name. An empty name * can be detected when dns_name_countlabels == 0, and is printed by * dns_name_totext()/dns_name_format() as "@", consistent with RFC1035's * definition of "@" as the current origin. * * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next * functions but additionally can provide the node to which the chain points. / /% * The number of level blocks to allocate at a time. Currently the maximum * number of levels is allocated directly in the structure, but future * revisions of this code might have a static initial block with dynamic * growth. Allocating space for 256 levels when the tree is almost never that * deep is wasteful, but it's not clear that it matters, since the waste is * only 2MB for 1000 concurrently active chains on a system with 64-bit * pointers. / #define DNS_RBT_LEVELBLOCK 254 typedef struct dns_rbtnodechain { unsigned int magic; isc_mem_t mctx; /% The terminal node of the chain. It is not in levels[]. * This is ostensibly private ... but in a pinch it could be * used tell that the chain points nowhere without needing to * call dns_rbtnodechain_current(). / dns_rbtnode_t end; /% The maximum number of labels in a name is 128; bitstrings mean * a conceptually very large number (which I have not bothered to * compute) of logical levels because splitting can potentially occur * at each bit. However, DNSSEC restricts the number of "logical" * labels in a name to 255, meaning only 254 pointers are needed * in the worst case. / dns_rbtnode_t levels[DNS_RBT_LEVELBLOCK]; /% level_count indicates how deep the chain points into the * tree of trees, and is the index into the levels[] array. * Thus, levels[level_count - 1] is the last level node stored. * A chain that points to the top level of the tree of trees has * a level_count of 0, the first level has a level_count of 1, and * so on. / unsigned int level_count; /% * level_matches tells how many levels matched above the node * returned by dns_rbt_findnode(). A match (partial or exact) found * in the first level thus results in level_matches being set to 1. * This is used by the rbtdb to set the start point for a recursive * search of superdomains until the RR it is looking for is found. / unsigned int level_matches; } dns_rbtnodechain_t; /** * Public interfaces. **/ isc_result_t dns_rbt_create(isc_mem_t mctx, dns_rbtdeleter_t deleter, void deleter_arg, dns_rbt_t rbtp); /%< * Initialize a red-black tree of trees. * * Notes: \li The deleter argument, if non-null, points to a function that is responsible for cleaning up any memory associated with the data * pointer of a node when the node is deleted. It is passed the * deleted node's data pointer as its first argument and deleter_arg * as its second argument. * * Requires: * \li mctx is a pointer to a valid memory context. \li rbtp != NULL && rbtp == NULL \li arg == NULL iff deleter == NULL * Ensures: \li If result is ISC_R_SUCCESS: rbtp points to a valid red-black tree manager \li If result is failure: rbtp does not point to a valid red-black tree manager. * Returns: \li #ISC_R_SUCCESS Success \li #ISC_R_NOMEMORY Resource limit: Out of Memory / isc_result_t dns_rbt_addname(dns_rbt_t rbt, dns_name_t name, void data); /%< Add 'name' to the tree of trees, associated with 'data'. * * Notes: \li 'data' is never required to be non-NULL, but specifying it when the name is added is faster than searching for 'name' * again and then setting the data pointer. The lack of a data pointer * for a node also has other ramifications regarding whether * dns_rbt_findname considers a node to exist, or dns_rbt_deletename * joins nodes. * * Requires: \li rbt is a valid rbt manager. \li dns_name_isabsolute(name) == TRUE * * Ensures: \li 'name' is not altered in any way. \li Any external references to nodes in the tree are unaffected by node splits that are necessary to insert the new name. * \li If result is #ISC_R_SUCCESS: 'name' is findable in the red/black tree of trees in O(log N). * The data pointer of the node for 'name' is set to 'data'. * \li If result is #ISC_R_EXISTS or #ISC_R_NOSPACE: The tree of trees is unaltered. * \li If result is #ISC_R_NOMEMORY: No guarantees. * * Returns: \li #ISC_R_SUCCESS Success \li #ISC_R_EXISTS The name already exists with associated data. \li #ISC_R_NOSPACE The name had more logical labels than are allowed. \li #ISC_R_NOMEMORY Resource Limit: Out of Memory / isc_result_t dns_rbt_addnode(dns_rbt_t rbt, dns_name_t name, dns_rbtnode_t nodep); /%< * Just like dns_rbt_addname, but returns the address of the node. * * Requires: \li rbt is a valid rbt structure. \li dns_name_isabsolute(name) == TRUE \li nodep != NULL && nodep == NULL * * Ensures: \li 'name' is not altered in any way. \li Any external references to nodes in the tree are unaffected by node splits that are necessary to insert the new name. * \li If result is ISC_R_SUCCESS: 'name' is findable in the red/black tree of trees in O(log N). * nodep is the node that was added for 'name'. \li If result is ISC_R_EXISTS: The tree of trees is unaltered. * nodep is the existing node for 'name'. \li If result is ISC_R_NOMEMORY: No guarantees. * * Returns: \li #ISC_R_SUCCESS Success \li #ISC_R_EXISTS The name already exists, possibly without data. \li #ISC_R_NOMEMORY Resource Limit: Out of Memory / isc_result_t dns_rbt_findname(dns_rbt_t rbt, const dns_name_t name, unsigned int options, dns_name_t foundname, void data); /%< * Get the data pointer associated with 'name'. * * Notes: \li When #DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is returned (also subject to #DNS_RBTFIND_EMPTYDATA), even when there is * an exact match in the tree. * \li A node that has no data is considered not to exist for this function, unless the #DNS_RBTFIND_EMPTYDATA option is set. * * Requires: \li rbt is a valid rbt manager. \li dns_name_isabsolute(name) == TRUE \li data != NULL && data == NULL * * Ensures: \li 'name' and the tree are not altered in any way. \li If result is ISC_R_SUCCESS: data is the data associated with 'name'. \li If result is DNS_R_PARTIALMATCH: data is the data associated with the deepest superdomain of 'name' which has data. * \li If result is ISC_R_NOTFOUND: Neither the name nor a superdomain was found with data. * * Returns: \li #ISC_R_SUCCESS Success \li #DNS_R_PARTIALMATCH Superdomain found with data \li #ISC_R_NOTFOUND No match \li #ISC_R_NOSPACE Concatenating nodes to form foundname failed / isc_result_t dns_rbt_findnode(dns_rbt_t rbt, const dns_name_t name, dns_name_t foundname, dns_rbtnode_t *node, dns_rbtnodechain_t chain, unsigned int options, dns_rbtfindcallback_t callback, void callback_arg); /%< * Find the node for 'name'. * * Notes: \li A node that has no data is considered not to exist for this function, unless the DNS_RBTFIND_EMPTYDATA option is set. This applies to both * exact matches and partial matches. * \li If the chain parameter is non-NULL, then the path through the tree to the DNSSEC predecessor of the searched for name is maintained, * unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option * is used. (For more details on those options, see below.) * \li If there is no predecessor, then the chain will point to nowhere, as indicated by chain->end being NULL or dns_rbtnodechain_current * returning ISC_R_NOTFOUND. Note that in a normal Internet DNS RBT * there will always be a predecessor for all names except the root * name, because '.' will exist and '.' is the predecessor of * everything. But you can certainly construct a trivial tree and a * search for it that has no predecessor. * \li Within the chain structure, the 'levels' member of the structure holds the root node of each level except the first. * \li The 'level_count' of the chain indicates how deep the chain to the predecessor name is, as an index into the 'levels[]' array. It does * not count name elements, per se, but only levels of the tree of trees, * the distinction arising because multiple labels from a name can be * stored on only one level. It is also does not include the level * that has the node, since that level is not stored in levels[]. * \li The chain's 'level_matches' is not directly related to the predecessor. It is the number of levels above the level of the found 'node', * regardless of whether it was a partial match or exact match. When * the node is found in the top level tree, or no node is found at all, * level_matches is 0. * \li When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is returned (also subject to DNS_RBTFIND_EMPTYDATA), even when * there is an exact match in the tree. In this case, the chain * will not point to the DNSSEC predecessor, but will instead point * to the exact match, if there was any. Thus the preceding paragraphs * should have "exact match" substituted for "predecessor" to describe * how the various elements of the chain are set. This was done to * ensure that the chain's state was sane, and to prevent problems that * occurred when running the predecessor location code under conditions * it was not designed for. It is not clear where the chain should * point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain * with this option because you want a particular node, let us know * where you want the chain pointed, so this can be made more firm. * * Requires: \li rbt is a valid rbt manager. \li dns_name_isabsolute(name) == TRUE. \li node != NULL && node == NULL. \li #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually exclusive. * * Ensures: \li 'name' and the tree are not altered in any way. \li If result is ISC_R_SUCCESS: \verbatim * node is the terminal node for 'name'. 'foundname' and 'name' represent the same name (though not * the same memory). * 'chain' points to the DNSSEC predecessor, if any, of 'name'. * * chain->level_matches and chain->level_count are equal. \endverbatim * If result is DNS_R_PARTIALMATCH: \verbatim node is the data associated with the deepest superdomain of 'name' which has data. * * 'foundname' is the name of deepest superdomain (which has * data, unless the DNS_RBTFIND_EMPTYDATA option is set). * * 'chain' points to the DNSSEC predecessor, if any, of 'name'. \endverbatim \li If result is ISC_R_NOTFOUND: \verbatim * Neither the name nor a superdomain was found. node is NULL. * 'chain' points to the DNSSEC predecessor, if any, of 'name'. * * chain->level_matches is 0. \endverbatim * Returns: \li #ISC_R_SUCCESS Success \li #DNS_R_PARTIALMATCH Superdomain found with data \li #ISC_R_NOTFOUND No match, or superdomain with no data \li #ISC_R_NOSPACE Concatenating nodes to form foundname failed / isc_result_t dns_rbt_deletename(dns_rbt_t rbt, dns_name_t name, bool recurse); /%< * Delete 'name' from the tree of trees. * * Notes: \li When 'name' is removed, if recurse is true then all of its subnames are removed too. * * Requires: \li rbt is a valid rbt manager. \li dns_name_isabsolute(name) == TRUE * * Ensures: \li 'name' is not altered in any way. \li Does NOT ensure that any external references to nodes in the tree are unaffected by node joins. * \li If result is ISC_R_SUCCESS: 'name' does not appear in the tree with data; however, * the node for the name might still exist which can be * found with dns_rbt_findnode (but not dns_rbt_findname). * \li If result is ISC_R_NOTFOUND: 'name' does not appear in the tree with data, because * it did not appear in the tree before the function was called. * \li If result is something else: See result codes for dns_rbt_findnode (if it fails, the * node is not deleted) or dns_rbt_deletenode (if it fails, * the node is deleted, but the tree is not optimized when * it could have been). * * Returns: \li #ISC_R_SUCCESS Success \li #ISC_R_NOTFOUND No match \li something_else Any return code from dns_rbt_findnode except DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND * to be returned instead), and any code from * dns_rbt_deletenode. / isc_result_t dns_rbt_deletenode(dns_rbt_t rbt, dns_rbtnode_t node, bool recurse); /%< * Delete 'node' from the tree of trees. * * Notes: \li When 'node' is removed, if recurse is true then all nodes in levels down from it are removed too. * * Requires: \li rbt is a valid rbt manager. \li node != NULL. * * Ensures: \li Does NOT ensure that any external references to nodes in the tree are unaffected by node joins. * \li If result is ISC_R_SUCCESS: 'node' does not appear in the tree with data; however, * the node might still exist if it serves as a pointer to * a lower tree level as long as 'recurse' was false, hence * the node could can be found with dns_rbt_findnode when * that function's empty_data_ok parameter is true. * \li If result is ISC_R_NOMEMORY or ISC_R_NOSPACE: The node was deleted, but the tree structure was not * optimized. * * Returns: \li #ISC_R_SUCCESS Success \li #ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes. \li #ISC_R_NOSPACE dns_name_concatenate failed when joining nodes. / void dns_rbt_namefromnode(dns_rbtnode_t node, dns_name_t name); /%< Convert the sequence of labels stored at 'node' into a 'name'. * * Notes: \li This function does not return the full name, from the root, but just the labels at the indicated node. * \li The name data pointed to by 'name' is the information stored in the node, not a copy. Altering the data at this pointer * will likely cause grief. * * Requires: * \li name->offsets == NULL * * Ensures: * \li 'name' is DNS_NAMEATTR_READONLY. * * \li 'name' will point directly to the labels stored after the * dns_rbtnode_t struct. * * \li 'name' will have offsets that also point to the information stored * as part of the node. / isc_result_t dns_rbt_fullnamefromnode(dns_rbtnode_t node, dns_name_t name); /%< * Like dns_rbt_namefromnode, but returns the full name from the root. * * Notes: * \li Unlike dns_rbt_namefromnode, the name will not point directly * to node data. Rather, dns_name_concatenate will be used to copy * the name data from each node into the 'name' argument. * * Requires: * \li name != NULL * \li name has a dedicated buffer. * * Returns: * \li ISC_R_SUCCESS * \li ISC_R_NOSPACE (possible via dns_name_concatenate) * \li DNS_R_NAMETOOLONG (possible via dns_name_concatenate) / char dns_rbt_formatnodename(dns_rbtnode_t node, char printname, unsigned int size); /%< Format the full name of a node for printing, using dns_name_format(). * * Notes: * \li 'size' is the length of the printname buffer. This should be * DNS_NAME_FORMATSIZE or larger. * * Requires: * \li node and printname are not NULL. * * Returns: * \li The 'printname' pointer. / unsigned int dns_rbt_nodecount(dns_rbt_t rbt); /%< Obtain the number of nodes in the tree of trees. * * Requires: * \li rbt is a valid rbt manager. / size_t dns_rbt_hashsize(dns_rbt_t rbt); /%< Obtain the current number of buckets in the 'rbt' hash table. * * Requires: * \li rbt is a valid rbt manager. / void dns_rbt_destroy(dns_rbt_t rbtp); isc_result_t dns_rbt_destroy2(dns_rbt_t rbtp, unsigned int quantum); /%< * Stop working with a red-black tree of trees. * If 'quantum' is zero then the entire tree will be destroyed. * If 'quantum' is non zero then up to 'quantum' nodes will be destroyed * allowing the rbt to be incrementally destroyed by repeated calls to * dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other * operations than dns_rbt_destroy()/dns_rbt_destroy2() should be * performed on the tree of trees. * * Requires: * \li rbt is a valid rbt manager. * Ensures on ISC_R_SUCCESS: * \li All space allocated by the RBT library has been returned. * * \li rbt is invalidated as an rbt manager. * Returns: * \li ISC_R_SUCCESS * \li ISC_R_QUOTA if 'quantum' nodes have been destroyed. / off_t dns_rbt_serialize_align(off_t target); /%< * Align the provided integer to a pointer-size boundary. * This should be used if, during serialization of data to a will-be * mmap()ed file, a pointer alignment is needed for some data. / isc_result_t dns_rbt_serialize_tree(FILE file, dns_rbt_t rbt, dns_rbtdatawriter_t datawriter, void writer_arg, off_t offset); /%< * Write out the RBT structure and its data to a file. * * Notes: * \li The file must be an actual file which allows seek() calls, so it cannot * be a stream. Returns ISC_R_INVALIDFILE if not. / isc_result_t dns_rbt_deserialize_tree(void base_address, size_t filesize, off_t header_offset, isc_mem_t mctx, dns_rbtdeleter_t deleter, void deleter_arg, dns_rbtdatafixer_t datafixer, void fixer_arg, dns_rbtnode_t originp, dns_rbt_t rbtp); /%< * Read a RBT structure and its data from a file. * * If 'originp' is not NULL, then it is pointed to the root node of the RBT. * * Notes: * \li The file must be an actual file which allows seek() calls, so it cannot * be a stream. This condition is not checked in the code. / void dns_rbt_printtext(dns_rbt_t rbt, void (data_printer)(FILE , void ), FILE f); /%< Print an ASCII representation of the internal structure of the red-black * tree of trees to the passed stream. * * data_printer is a callback function that is called to print the data * in a node. It should print it to the passed FILE stream. * * Notes: * \li The name stored at each node, along with the node's color, is printed. * Then the down pointer, left and right pointers are displayed * recursively in turn. NULL down pointers are silently omitted; * NULL left and right pointers are printed. / void dns_rbt_printdot(dns_rbt_t rbt, bool show_pointers, FILE f); /%< * Print a GraphViz dot representation of the internal structure of the * red-black tree of trees to the passed stream. * * If show_pointers is TRUE, pointers are also included in the generated * graph. * * Notes: * \li The name stored at each node, along with the node's color is displayed. * Then the down pointer, left and right pointers are displayed * recursively in turn. NULL left, right and down pointers are * silently omitted. / void dns_rbt_printnodeinfo(dns_rbtnode_t n, FILE f); /%< * Print out various information about a node * * Requires: \li 'n' is a valid pointer. \li 'f' points to a valid open FILE structure that allows writing. / size_t dns__rbt_getheight(dns_rbt_t rbt); /%< * Return the maximum height of sub-root nodes found in the red-black * forest. * * The height of a node is defined as the number of nodes in the longest * path from the node to a leaf. For each subtree in the forest, this * function determines the height of its root node. Then it returns the * maximum such height in the forest. * * Note: This function exists for testing purposes. Non-test code must * not use it. * * Requires: * \li rbt is a valid rbt manager. / bool dns__rbt_checkproperties(dns_rbt_t rbt); /%< Check red-black properties of the forest. * * Note: This function exists for testing purposes. Non-test code must * not use it. * * Requires: * \li rbt is a valid rbt manager. / size_t dns__rbtnode_getdistance(dns_rbtnode_t node); /%< Return the distance (in nodes) from the node to its upper node of its * subtree. The root node has a distance of 1. A child of the root node * has a distance of 2. / /** * Chain Functions **/ void dns_rbtnodechain_init(dns_rbtnodechain_t chain, isc_mem_t mctx); /%< * Initialize 'chain'. * * Requires: \li 'chain' is a valid pointer. \li 'mctx' is a valid memory context. * Ensures: \li 'chain' is suitable for use. / void dns_rbtnodechain_reset(dns_rbtnodechain_t chain); /%< * Free any dynamic storage associated with 'chain', and then reinitialize * 'chain'. * * Requires: \li 'chain' is a valid pointer. * Ensures: \li 'chain' is suitable for use, and uses no dynamic storage. / void dns_rbtnodechain_invalidate(dns_rbtnodechain_t chain); /%< * Free any dynamic storage associated with 'chain', and then invalidates it. * * Notes: \li Future calls to any dns_rbtnodechain_ function will need to call dns_rbtnodechain_init on the chain first (except, of course, * dns_rbtnodechain_init itself). * * Requires: \li 'chain' is a valid chain. * Ensures: \li 'chain' is no longer suitable for use, and uses no dynamic storage. / isc_result_t dns_rbtnodechain_current(dns_rbtnodechain_t chain, dns_name_t name, dns_name_t origin, dns_rbtnode_t node); /%< * Provide the name, origin and node to which the chain is currently pointed. * * Notes: \li The tree need not have be locked against additions for the chain to remain valid, however there are no guarantees if any deletion * has been made since the chain was established. * * Requires: \li 'chain' is a valid chain. * Ensures: \li 'node', if non-NULL, is the node to which the chain was pointed by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last. * If none were called for the chain since it was initialized or reset, * or if the was no predecessor to the name searched for with * dns_rbt_findnode, then 'node' is NULL and ISC_R_NOTFOUND is returned. \li 'name', if non-NULL, is the name stored at the terminal level of the chain. This is typically a single label, like the "www" of * "www.isc.org", but need not be so. At the root of the tree of trees, * if the node is "." then 'name' is ".", otherwise it is relative to ".". * (Minimalist and atypical case: if the tree has just the name * "isc.org." then the root node's stored name is "isc.org." but 'name' * will be "isc.org".) * \li 'origin', if non-NULL, is the sequence of labels in the levels above the terminal level, such as "isc.org." in the above example. * 'origin' is always "." for the root node. * * * Returns: \li #ISC_R_SUCCESS name, origin & node were successfully set. \li #ISC_R_NOTFOUND The chain does not point to any node. \li <something_else> Any error return from dns_name_concatenate. / isc_result_t dns_rbtnodechain_first(dns_rbtnodechain_t chain, dns_rbt_t rbt, dns_name_t name, dns_name_t origin); /%< Set the chain to the lexically first node in the tree of trees. * * Notes: \li By the definition of ordering for DNS names, the root of the tree of trees is the very first node, since everything else in the megatree * uses it as a common suffix. * * Requires: \li 'chain' is a valid chain. \li 'rbt' is a valid rbt manager. * * Ensures: \li The chain points to the very first node of the tree. \li 'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current. Thus 'origin' will always be ".". * * Returns: \li #DNS_R_NEWORIGIN The name & origin were successfully set. \li <something_else> Any error result from dns_rbtnodechain_current. / isc_result_t dns_rbtnodechain_last(dns_rbtnodechain_t chain, dns_rbt_t rbt, dns_name_t name, dns_name_t origin); /%< * Set the chain to the lexically last node in the tree of trees. * * Requires: \li 'chain' is a valid chain. \li 'rbt' is a valid rbt manager. * * Ensures: \li The chain points to the very last node of the tree. \li 'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current. * * Returns: \li #DNS_R_NEWORIGIN The name & origin were successfully set. \li #ISC_R_NOMEMORY Resource Limit: Out of Memory building chain. \li <something_else> Any error result from dns_name_concatenate. / isc_result_t dns_rbtnodechain_prev(dns_rbtnodechain_t chain, dns_name_t name, dns_name_t origin); /%< * Adjusts chain to point the DNSSEC predecessor of the name to which it * is currently pointed. * * Requires: \li 'chain' is a valid chain. \li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that * dns_rbt_findnode is not guaranteed to point the chain somewhere, * since there may have been no predecessor to the searched for name. * * Ensures: \li The chain is pointed to the predecessor of its current target. \li 'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current. * \li 'origin' is only if a new origin was found. * Returns: \li #ISC_R_SUCCESS The predecessor was found and 'name' was set. \li #DNS_R_NEWORIGIN The predecessor was found with a different * origin and 'name' and 'origin' were set. \li #ISC_R_NOMORE There was no predecessor. \li <something_else> Any error result from dns_rbtnodechain_current. / isc_result_t dns_rbtnodechain_next(dns_rbtnodechain_t chain, dns_name_t name, dns_name_t origin); /%< Adjusts chain to point the DNSSEC successor of the name to which it * is currently pointed. * * Requires: \li 'chain' is a valid chain. \li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that * dns_rbt_findnode is not guaranteed to point the chain somewhere, * since there may have been no predecessor to the searched for name. * * Ensures: \li The chain is pointed to the successor of its current target. \li 'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current. * \li 'origin' is only if a new origin was found. * Returns: \li #ISC_R_SUCCESS The successor was found and 'name' was set. \li #DNS_R_NEWORIGIN The successor was found with a different * origin and 'name' and 'origin' were set. \li #ISC_R_NOMORE There was no successor. \li <something_else> Any error result from dns_name_concatenate. / isc_result_t dns_rbtnodechain_down(dns_rbtnodechain_t chain, dns_name_t name, dns_name_t origin); /%< Descend down if possible. / isc_result_t dns_rbtnodechain_nextflat(dns_rbtnodechain_t chain, dns_name_t name); /%< * Find the next node at the current depth in DNSSEC order. / / * Wrapper macros for manipulating the rbtnode reference counter: * Since we selectively use isc_refcount_t for the reference counter of * a rbtnode, operations on the counter depend on the actual type of it. * The following macros provide a common interface to these operations, * hiding the back-end. The usage is the same as that of isc_refcount_xxx(). / #ifdef DNS_RBT_USEISCREFCOUNT #define dns_rbtnode_refinit(node, n) \ do { \ isc_refcount_init(&(node)->references, (n)); \ } while (0) #define dns_rbtnode_refdestroy(node) \ do { \ isc_refcount_destroy(&(node)->references); \ } while (0) #define dns_rbtnode_refcurrent(node) \ isc_refcount_current(&(node)->references) #define dns_rbtnode_refincrement0(node, refs) \ do { \ isc_refcount_increment0(&(node)->references, (refs)); \ } while (0) #define dns_rbtnode_refincrement(node, refs) \ do { \ isc_refcount_increment(&(node)->references, (refs)); \ } while (0) #define dns_rbtnode_refdecrement(node, refs) \ do { \ isc_refcount_decrement(&(node)->references, (refs)); \ } while (0) #else / DNS_RBT_USEISCREFCOUNT / #define dns_rbtnode_refinit(node, n) ((node)->references = (n)) #define dns_rbtnode_refdestroy(node) ISC_REQUIRE((node)->references == 0) #define dns_rbtnode_refcurrent(node) ((node)->references) #if (__STDC_VERSION__ + 0) >= 199901L \|\| defined __GNUC__ static inline void dns_rbtnode_refincrement0(dns_rbtnode_t node, unsigned int refs) { node->references++; if (refs != NULL) refs = node->references; } static inline void dns_rbtnode_refincrement(dns_rbtnode_t node, unsigned int refs) { ISC_REQUIRE(node->references > 0); node->references++; if (refs != NULL) refs = node->references; } static inline void dns_rbtnode_refdecrement(dns_rbtnode_t node, unsigned int refs) { ISC_REQUIRE(node->references > 0); node->references--; if (refs != NULL) refs = node->references; } #else #define dns_rbtnode_refincrement0(node, refs) \ do { \ unsigned int _tmp = (unsigned int )(refs); \ (node)->references++; \ if ((_tmp) != NULL) \ (_tmp) = (node)->references; \ } while (0) #define dns_rbtnode_refincrement(node, refs) \ do { \ ISC_REQUIRE((node)->references > 0); \ (node)->references++; \ if ((refs) != NULL) \ (refs) = (node)->references; \ } while (0) #define dns_rbtnode_refdecrement(node, refs) \ do { \ ISC_REQUIRE((node)->references > 0); \ (node)->references--; \ if ((refs) != NULL) \ (refs) = (node)->references; \ } while (0) #endif #endif / DNS_RBT_USEISCREFCOUNT / void dns_rbtnode_nodename(dns_rbtnode_t node, dns_name_t name); dns_rbtnode_t dns_rbt_root(dns_rbt_t rbt); ISC_LANG_ENDDECLS #endif / DNS_RBT_H */ Back

Edit File : rbt.h | Size : 39.67 KB

/*
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
 */

#ifndef DNS_RBT_H
#define DNS_RBT_H 1

/*! \file dns/rbt.h */

#include <inttypes.h>
#include <stdbool.h>

#include <isc/assertions.h>
#include <isc/crc64.h>
#include <isc/lang.h>
#include <isc/magic.h>
#include <isc/refcount.h>

#include <dns/types.h>

ISC_LANG_BEGINDECLS

#define DNS_RBT_USEHASH 1

/*@{*/
/*%
 * Option values for dns_rbt_findnode() and dns_rbt_findname().
 * These are used to form a bitmask.
 */
#define DNS_RBTFIND_NOOPTIONS                   0x00
#define DNS_RBTFIND_EMPTYDATA                   0x01
#define DNS_RBTFIND_NOEXACT                     0x02
#define DNS_RBTFIND_NOPREDECESSOR               0x04
/*@}*/

#ifndef DNS_RBT_USEISCREFCOUNT
#ifdef ISC_REFCOUNT_HAVEATOMIC
#define DNS_RBT_USEISCREFCOUNT 1
#endif
#endif

#define DNS_RBT_USEMAGIC 1

/*
 * These should add up to 30.
 */
#define DNS_RBT_LOCKLENGTH                      10
#define DNS_RBT_REFLENGTH                       20

#define DNS_RBTNODE_MAGIC               ISC_MAGIC('R','B','N','O')
#if DNS_RBT_USEMAGIC
#define DNS_RBTNODE_VALID(n)            ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC)
#else
#define DNS_RBTNODE_VALID(n)            true
#endif

/*%
 * This is the structure that is used for each node in the red/black
 * tree of trees.  NOTE WELL:  the implementation manages this as a variable
 * length structure, with the actual wire-format name and other data
 * appended to this structure.  Allocating a contiguous block of memory for
 * multiple dns_rbtnode structures will not work.
 */
typedef struct dns_rbtnode dns_rbtnode_t;
enum {
	DNS_RBT_NSEC_NORMAL=0,      /* in main tree */
	DNS_RBT_NSEC_HAS_NSEC=1,    /* also has node in nsec tree */
	DNS_RBT_NSEC_NSEC=2,        /* in nsec tree */
	DNS_RBT_NSEC_NSEC3=3        /* in nsec3 tree */
};
struct dns_rbtnode {
#if DNS_RBT_USEMAGIC
	unsigned int magic;
#endif
	/*@{*/
	/*!
	 * The following bitfields add up to a total bitwidth of 32.
	 * The range of values necessary for each item is indicated,
	 * but in the case of "attributes" the field is wider to accommodate
	 * possible future expansion.
	 *
	 * In each case below the "range" indicated is what's _necessary_ for
	 * the bitfield to hold, not what it actually _can_ hold.
	 *
	 * Note: Tree lock must be held before modifying these
	 * bit-fields.
	 *
	 * Note: The two "unsigned int :0;" unnamed bitfields on either
	 * side of the bitfields below are scaffolding that border the
	 * set of bitfields which are accessed after acquiring the tree
	 * lock. Please don't insert any other bitfield members between
	 * the unnamed bitfields unless they should also be accessed
	 * after acquiring the tree lock.
	 */
	unsigned int :0;                /* start of bitfields c/o tree lock */
	unsigned int is_root : 1;       /*%< range is 0..1 */
	unsigned int color : 1;         /*%< range is 0..1 */
	unsigned int find_callback : 1; /*%< range is 0..1 */
	unsigned int attributes : 3;    /*%< range is 0..2 */
	unsigned int nsec : 2;          /*%< range is 0..3 */
	unsigned int namelen : 8;       /*%< range is 1..255 */
	unsigned int offsetlen : 8;     /*%< range is 1..128 */
	unsigned int oldnamelen : 8;    /*%< range is 1..255 */
	/*@}*/

/* flags needed for serialization to file*/
	unsigned int is_mmapped : 1;
	unsigned int parent_is_relative : 1;
	unsigned int left_is_relative : 1;
	unsigned int right_is_relative : 1;
	unsigned int down_is_relative : 1;
	unsigned int data_is_relative : 1;

/* node needs to be cleaned from rpz */
	unsigned int rpz : 1;
	unsigned int :0;                /* end of bitfields c/o tree lock */

#ifdef DNS_RBT_USEHASH
	unsigned int hashval;
	dns_rbtnode_t *uppernode;
	dns_rbtnode_t *hashnext;
#endif
	dns_rbtnode_t *parent;
	dns_rbtnode_t *left;
	dns_rbtnode_t *right;
	dns_rbtnode_t *down;

/*%
	 * Used for LRU cache.  This linked list is used to mark nodes which
	 * have no data any longer, but we cannot unlink at that exact moment
	 * because we did not or could not obtain a write lock on the tree.
	 */
	ISC_LINK(dns_rbtnode_t) deadlink;

/*@{*/
	/*!
	 * These values are used in the RBT DB implementation.  The appropriate
	 * node lock must be held before accessing them.
	 *
	 * Note: The two "unsigned int :0;" unnamed bitfields on either
	 * side of the bitfields below are scaffolding that border the
	 * set of bitfields which are accessed after acquiring the node
	 * lock. Please don't insert any other bitfield members between
	 * the unnamed bitfields unless they should also be accessed
	 * after acquiring the node lock.
	 *
	 * NOTE: Do not merge these fields into bitfields above, as
	 * they'll all be put in the same qword that could be accessed
	 * without the node lock as it shares the qword with other
	 * members. Leave these members here so that they occupy a
	 * separate region of memory.
	 */
	void *data;
	unsigned int locknum;
	unsigned int :0;                /* start of bitfields c/o node lock */
	unsigned int dirty:1;
	unsigned int wild:1;
#ifndef DNS_RBT_USEISCREFCOUNT
	unsigned int references:DNS_RBT_REFLENGTH;
#endif
	unsigned int :0;                /* end of bitfields c/o node lock */
#ifdef DNS_RBT_USEISCREFCOUNT
	isc_refcount_t references; /* note that this is not in the bitfield */
#endif
	/*@}*/
};

typedef isc_result_t (*dns_rbtfindcallback_t)(dns_rbtnode_t *node,
					      dns_name_t *name,
					      void *callback_arg);

typedef isc_result_t (*dns_rbtdatawriter_t)(FILE *file,
					    unsigned char *data,
					    void *arg,
					    uint64_t *crc);

typedef isc_result_t (*dns_rbtdatafixer_t)(dns_rbtnode_t *rbtnode,
					   void *base, size_t offset,
					   void *arg, uint64_t *crc);

typedef void (*dns_rbtdeleter_t)(void *, void *);

/*****
 *****  Chain Info
 *****/

/*!
 * A chain is used to keep track of the sequence of nodes to reach any given
 * node from the root of the tree.  Originally nodes did not have parent
 * pointers in them (for memory usage reasons) so there was no way to find
 * the path back to the root from any given node.  Now that nodes have parent
 * pointers, chains might be going away in a future release, though the
 * movement functionality would remain.
 *
 * Chains may be used to iterate over a tree of trees.  After setting up the
 * chain's structure using dns_rbtnodechain_init(), it needs to be initialized
 * to point to the lexically first or lexically last node in the tree of trees
 * using dns_rbtnodechain_first() or dns_rbtnodechain_last(), respectively.
 * Calling dns_rbtnodechain_next() or dns_rbtnodechain_prev() then moves the
 * chain over to the next or previous node, respectively.
 *
 * In any event, parent information, whether via parent pointers or chains, is
 * necessary information for iterating through the tree or for basic internal
 * tree maintenance issues (ie, the rotations that are done to rebalance the
 * tree when a node is added).  The obvious implication of this is that for a
 * chain to remain valid, the tree has to be locked down against writes for the
 * duration of the useful life of the chain, because additions or removals can
 * change the path from the root to the node the chain has targeted.
 *
 * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take
 * dns_name_t parameters for the name and the origin, which can be NULL.  If
 * non-NULL, 'name' will end up pointing to the name data and offsets that are
 * stored at the node (and thus it will be read-only), so it should be a
 * regular dns_name_t that has been initialized with dns_name_init.  When
 * 'origin' is non-NULL, it will get the name of the origin stored in it, so it
 * needs to have its own buffer space and offsets, which is most easily
 * accomplished with a dns_fixedname_t.  It is _not_ necessary to reinitialize
 * either 'name' or 'origin' between calls to the chain functions.
 *
 * NOTE WELL: even though the name data at the root of the tree of trees will
 * be absolute (typically just "."), it will will be made into a relative name
 * with an origin of "." -- an empty name when the node is ".".  This is
 * because a common on operation on 'name' and 'origin' is to use
 * dns_name_concatenate() on them to generate the complete name.  An empty name
 * can be detected when dns_name_countlabels == 0, and is printed by
 * dns_name_totext()/dns_name_format() as "@", consistent with RFC1035's
 * definition of "@" as the current origin.
 *
 * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next
 * functions but additionally can provide the node to which the chain points.
 */

/*%
 * The number of level blocks to allocate at a time.  Currently the maximum
 * number of levels is allocated directly in the structure, but future
 * revisions of this code might have a static initial block with dynamic
 * growth.  Allocating space for 256 levels when the tree is almost never that
 * deep is wasteful, but it's not clear that it matters, since the waste is
 * only 2MB for 1000 concurrently active chains on a system with 64-bit
 * pointers.
 */
#define DNS_RBT_LEVELBLOCK 254

typedef struct dns_rbtnodechain {
	unsigned int            magic;
	isc_mem_t *             mctx;
	/*%
	 * The terminal node of the chain.  It is not in levels[].
	 * This is ostensibly private ... but in a pinch it could be
	 * used tell that the chain points nowhere without needing to
	 * call dns_rbtnodechain_current().
	 */
	dns_rbtnode_t *         end;
	/*%
	 * The maximum number of labels in a name is 128; bitstrings mean
	 * a conceptually very large number (which I have not bothered to
	 * compute) of logical levels because splitting can potentially occur
	 * at each bit.  However, DNSSEC restricts the number of "logical"
	 * labels in a name to 255, meaning only 254 pointers are needed
	 * in the worst case.
	 */
	dns_rbtnode_t *         levels[DNS_RBT_LEVELBLOCK];
	/*%
	 * level_count indicates how deep the chain points into the
	 * tree of trees, and is the index into the levels[] array.
	 * Thus, levels[level_count - 1] is the last level node stored.
	 * A chain that points to the top level of the tree of trees has
	 * a level_count of 0, the first level has a level_count of 1, and
	 * so on.
	 */
	unsigned int            level_count;
	/*%
	 * level_matches tells how many levels matched above the node
	 * returned by dns_rbt_findnode().  A match (partial or exact) found
	 * in the first level thus results in level_matches being set to 1.
	 * This is used by the rbtdb to set the start point for a recursive
	 * search of superdomains until the RR it is looking for is found.
	 */
	unsigned int            level_matches;
} dns_rbtnodechain_t;

/*****
 ***** Public interfaces.
 *****/
isc_result_t
dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,
	       void *deleter_arg, dns_rbt_t **rbtp);
/*%<
 * Initialize a red-black tree of trees.
 *
 * Notes:
 *\li   The deleter argument, if non-null, points to a function that is
 *      responsible for cleaning up any memory associated with the data
 *      pointer of a node when the node is deleted.  It is passed the
 *      deleted node's data pointer as its first argument and deleter_arg
 *      as its second argument.
 *
 * Requires:
 * \li  mctx is a pointer to a valid memory context.
 *\li   rbtp != NULL && *rbtp == NULL
 *\li   arg == NULL iff deleter == NULL
 *
 * Ensures:
 *\li   If result is ISC_R_SUCCESS:
 *              *rbtp points to a valid red-black tree manager
 *
 *\li   If result is failure:
 *              *rbtp does not point to a valid red-black tree manager.
 *
 * Returns:
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_NOMEMORY Resource limit: Out of Memory
 */

isc_result_t
dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data);
/*%<
 * Add 'name' to the tree of trees, associated with 'data'.
 *
 * Notes:
 *\li   'data' is never required to be non-NULL, but specifying it
 *      when the name is added is faster than searching for 'name'
 *      again and then setting the data pointer.  The lack of a data pointer
 *      for a node also has other ramifications regarding whether
 *      dns_rbt_findname considers a node to exist, or dns_rbt_deletename
 *      joins nodes.
 *
 * Requires:
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE
 *
 * Ensures:
 *\li   'name' is not altered in any way.
 *
 *\li   Any external references to nodes in the tree are unaffected by
 *      node splits that are necessary to insert the new name.
 *
 *\li   If result is #ISC_R_SUCCESS:
 *              'name' is findable in the red/black tree of trees in O(log N).
 *              The data pointer of the node for 'name' is set to 'data'.
 *
 *\li   If result is #ISC_R_EXISTS or #ISC_R_NOSPACE:
 *              The tree of trees is unaltered.
 *
 *\li   If result is #ISC_R_NOMEMORY:
 *              No guarantees.
 *
 * Returns:
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_EXISTS   The name already exists with associated data.
 *\li   #ISC_R_NOSPACE  The name had more logical labels than are allowed.
 *\li   #ISC_R_NOMEMORY Resource Limit: Out of Memory
 */

isc_result_t
dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep);

/*%<
 * Just like dns_rbt_addname, but returns the address of the node.
 *
 * Requires:
 *\li   rbt is a valid rbt structure.
 *\li   dns_name_isabsolute(name) == TRUE
 *\li   nodep != NULL && *nodep == NULL
 *
 * Ensures:
 *\li   'name' is not altered in any way.
 *
 *\li   Any external references to nodes in the tree are unaffected by
 *      node splits that are necessary to insert the new name.
 *
 *\li   If result is ISC_R_SUCCESS:
 *              'name' is findable in the red/black tree of trees in O(log N).
 *              *nodep is the node that was added for 'name'.
 *
 *\li   If result is ISC_R_EXISTS:
 *              The tree of trees is unaltered.
 *              *nodep is the existing node for 'name'.
 *
 *\li   If result is ISC_R_NOMEMORY:
 *              No guarantees.
 *
 * Returns:
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_EXISTS   The name already exists, possibly without data.
 *\li   #ISC_R_NOMEMORY Resource Limit: Out of Memory
 */

isc_result_t
dns_rbt_findname(dns_rbt_t *rbt, const dns_name_t *name, unsigned int options,
		 dns_name_t *foundname, void **data);
/*%<
 * Get the data pointer associated with 'name'.
 *
 * Notes:
 *\li   When #DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is
 *      returned (also subject to #DNS_RBTFIND_EMPTYDATA), even when there is
 *      an exact match in the tree.
 *
 *\li   A node that has no data is considered not to exist for this function,
 *      unless the #DNS_RBTFIND_EMPTYDATA option is set.
 *
 * Requires:
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE
 *\li   data != NULL && *data == NULL
 *
 * Ensures:
 *\li   'name' and the tree are not altered in any way.
 *
 *\li   If result is ISC_R_SUCCESS:
 *              *data is the data associated with 'name'.
 *
 *\li   If result is DNS_R_PARTIALMATCH:
 *              *data is the data associated with the deepest superdomain
 *              of 'name' which has data.
 *
 *\li   If result is ISC_R_NOTFOUND:
 *              Neither the name nor a superdomain was found with data.
 *
 * Returns:
 *\li   #ISC_R_SUCCESS          Success
 *\li   #DNS_R_PARTIALMATCH     Superdomain found with data
 *\li   #ISC_R_NOTFOUND         No match
 *\li   #ISC_R_NOSPACE          Concatenating nodes to form foundname failed
 */

isc_result_t
dns_rbt_findnode(dns_rbt_t *rbt, const dns_name_t *name, dns_name_t *foundname,
		 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
		 unsigned int options, dns_rbtfindcallback_t callback,
		 void *callback_arg);
/*%<
 * Find the node for 'name'.
 *
 * Notes:
 *\li   A node that has no data is considered not to exist for this function,
 *      unless the DNS_RBTFIND_EMPTYDATA option is set.  This applies to both
 *      exact matches and partial matches.
 *
 *\li   If the chain parameter is non-NULL, then the path through the tree
 *      to the DNSSEC predecessor of the searched for name is maintained,
 *      unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option
 *      is used. (For more details on those options, see below.)
 *
 *\li   If there is no predecessor, then the chain will point to nowhere, as
 *      indicated by chain->end being NULL or dns_rbtnodechain_current
 *      returning ISC_R_NOTFOUND.  Note that in a normal Internet DNS RBT
 *      there will always be a predecessor for all names except the root
 *      name, because '.' will exist and '.' is the predecessor of
 *      everything.  But you can certainly construct a trivial tree and a
 *      search for it that has no predecessor.
 *
 *\li   Within the chain structure, the 'levels' member of the structure holds
 *      the root node of each level except the first.
 *
 *\li   The 'level_count' of the chain indicates how deep the chain to the
 *      predecessor name is, as an index into the 'levels[]' array.  It does
 *      not count name elements, per se, but only levels of the tree of trees,
 *      the distinction arising because multiple labels from a name can be
 *      stored on only one level.  It is also does not include the level
 *      that has the node, since that level is not stored in levels[].
 *
 *\li   The chain's 'level_matches' is not directly related to the predecessor.
 *      It is the number of levels above the level of the found 'node',
 *      regardless of whether it was a partial match or exact match.  When
 *      the node is found in the top level tree, or no node is found at all,
 *      level_matches is 0.
 *
 *\li   When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is
 *      returned (also subject to DNS_RBTFIND_EMPTYDATA), even when
 *      there is an exact match in the tree.  In this case, the chain
 *      will not point to the DNSSEC predecessor, but will instead point
 *      to the exact match, if there was any.  Thus the preceding paragraphs
 *      should have "exact match" substituted for "predecessor" to describe
 *      how the various elements of the chain are set.  This was done to
 *      ensure that the chain's state was sane, and to prevent problems that
 *      occurred when running the predecessor location code under conditions
 *      it was not designed for.  It is not clear *where* the chain should
 *      point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain
 *      with this option because you want a particular node, let us know
 *      where you want the chain pointed, so this can be made more firm.
 *
 * Requires:
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE.
 *\li   node != NULL && *node == NULL.
 *\li   #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually
 *              exclusive.
 *
 * Ensures:
 *\li   'name' and the tree are not altered in any way.
 *
 *\li   If result is ISC_R_SUCCESS:
 *\verbatim
 *              *node is the terminal node for 'name'.

*              'foundname' and 'name' represent the same name (though not
 *              the same memory).

*              'chain' points to the DNSSEC predecessor, if any, of 'name'.
 *
 *              chain->level_matches and chain->level_count are equal.
 *\endverbatim
 *
 *      If result is DNS_R_PARTIALMATCH:
 *\verbatim
 *              *node is the data associated with the deepest superdomain
 *              of 'name' which has data.
 *
 *              'foundname' is the name of deepest superdomain (which has
 *              data, unless the DNS_RBTFIND_EMPTYDATA option is set).
 *
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
 *\endverbatim
 *
 *\li   If result is ISC_R_NOTFOUND:
 *\verbatim
 *              Neither the name nor a superdomain was found.  *node is NULL.
 *
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
 *
 *              chain->level_matches is 0.
 *\endverbatim
 *
 * Returns:
 *\li   #ISC_R_SUCCESS          Success
 *\li   #DNS_R_PARTIALMATCH     Superdomain found with data
 *\li   #ISC_R_NOTFOUND         No match, or superdomain with no data
 *\li   #ISC_R_NOSPACE Concatenating nodes to form foundname failed
 */

isc_result_t
dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, bool recurse);
/*%<
 * Delete 'name' from the tree of trees.
 *
 * Notes:
 *\li   When 'name' is removed, if recurse is true then all of its
 *      subnames are removed too.
 *
 * Requires:
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE
 *
 * Ensures:
 *\li   'name' is not altered in any way.
 *
 *\li   Does NOT ensure that any external references to nodes in the tree
 *      are unaffected by node joins.
 *
 *\li   If result is ISC_R_SUCCESS:
 *              'name' does not appear in the tree with data; however,
 *              the node for the name might still exist which can be
 *              found with dns_rbt_findnode (but not dns_rbt_findname).
 *
 *\li   If result is ISC_R_NOTFOUND:
 *              'name' does not appear in the tree with data, because
 *              it did not appear in the tree before the function was called.
 *
 *\li   If result is something else:
 *              See result codes for dns_rbt_findnode (if it fails, the
 *              node is not deleted) or dns_rbt_deletenode (if it fails,
 *              the node is deleted, but the tree is not optimized when
 *              it could have been).
 *
 * Returns:
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_NOTFOUND No match
 *\li   something_else  Any return code from dns_rbt_findnode except
 *                      DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND
 *                      to be returned instead), and any code from
 *                      dns_rbt_deletenode.
 */

isc_result_t
dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, bool recurse);
/*%<
 * Delete 'node' from the tree of trees.
 *
 * Notes:
 *\li   When 'node' is removed, if recurse is true then all nodes
 *      in levels down from it are removed too.
 *
 * Requires:
 *\li   rbt is a valid rbt manager.
 *\li   node != NULL.
 *
 * Ensures:
 *\li   Does NOT ensure that any external references to nodes in the tree
 *      are unaffected by node joins.
 *
 *\li   If result is ISC_R_SUCCESS:
 *              'node' does not appear in the tree with data; however,
 *              the node might still exist if it serves as a pointer to
 *              a lower tree level as long as 'recurse' was false, hence
 *              the node could can be found with dns_rbt_findnode when
 *              that function's empty_data_ok parameter is true.
 *
 *\li   If result is ISC_R_NOMEMORY or ISC_R_NOSPACE:
 *              The node was deleted, but the tree structure was not
 *              optimized.
 *
 * Returns:
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes.
 *\li   #ISC_R_NOSPACE  dns_name_concatenate failed when joining nodes.
 */

void
dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name);
/*%<
 * Convert the sequence of labels stored at 'node' into a 'name'.
 *
 * Notes:
 *\li   This function does not return the full name, from the root, but
 *      just the labels at the indicated node.
 *
 *\li   The name data pointed to by 'name' is the information stored
 *      in the node, not a copy.  Altering the data at this pointer
 *      will likely cause grief.
 *
 * Requires:
 * \li  name->offsets == NULL
 *
 * Ensures:
 * \li  'name' is DNS_NAMEATTR_READONLY.
 *
 * \li  'name' will point directly to the labels stored after the
 *      dns_rbtnode_t struct.
 *
 * \li  'name' will have offsets that also point to the information stored
 *      as part of the node.
 */

isc_result_t
dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name);
/*%<
 * Like dns_rbt_namefromnode, but returns the full name from the root.
 *
 * Notes:
 * \li  Unlike dns_rbt_namefromnode, the name will not point directly
 *      to node data.  Rather, dns_name_concatenate will be used to copy
 *      the name data from each node into the 'name' argument.
 *
 * Requires:
 * \li  name != NULL
 * \li  name has a dedicated buffer.
 *
 * Returns:
 * \li  ISC_R_SUCCESS
 * \li  ISC_R_NOSPACE           (possible via dns_name_concatenate)
 * \li  DNS_R_NAMETOOLONG       (possible via dns_name_concatenate)
 */

char *
dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname,
		       unsigned int size);
/*%<
 * Format the full name of a node for printing, using dns_name_format().
 *
 * Notes:
 * \li  'size' is the length of the printname buffer.  This should be
 *      DNS_NAME_FORMATSIZE or larger.
 *
 * Requires:
 * \li  node and printname are not NULL.
 *
 * Returns:
 * \li  The 'printname' pointer.
 */

unsigned int
dns_rbt_nodecount(dns_rbt_t *rbt);
/*%<
 * Obtain the number of nodes in the tree of trees.
 *
 * Requires:
 * \li  rbt is a valid rbt manager.
 */

size_t
dns_rbt_hashsize(dns_rbt_t *rbt);
/*%<
 * Obtain the current number of buckets in the 'rbt' hash table.
 *
 * Requires:
 * \li  rbt is a valid rbt manager.
 */

void
dns_rbt_destroy(dns_rbt_t **rbtp);
isc_result_t
dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum);
/*%<
 * Stop working with a red-black tree of trees.
 * If 'quantum' is zero then the entire tree will be destroyed.
 * If 'quantum' is non zero then up to 'quantum' nodes will be destroyed
 * allowing the rbt to be incrementally destroyed by repeated calls to
 * dns_rbt_destroy2().  Once dns_rbt_destroy2() has been called no other
 * operations than dns_rbt_destroy()/dns_rbt_destroy2() should be
 * performed on the tree of trees.
 *
 * Requires:
 * \li  *rbt is a valid rbt manager.
 *
 * Ensures on ISC_R_SUCCESS:
 * \li  All space allocated by the RBT library has been returned.
 *
 * \li  *rbt is invalidated as an rbt manager.
 *
 * Returns:
 * \li  ISC_R_SUCCESS
 * \li  ISC_R_QUOTA if 'quantum' nodes have been destroyed.
 */

off_t
dns_rbt_serialize_align(off_t target);
/*%<
 * Align the provided integer to a pointer-size boundary.
 * This should be used if, during serialization of data to a will-be
 * mmap()ed file, a pointer alignment is needed for some data.
 */

isc_result_t
dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
		       dns_rbtdatawriter_t datawriter,
		       void *writer_arg, off_t *offset);
/*%<
 * Write out the RBT structure and its data to a file.
 *
 * Notes:
 * \li  The file must be an actual file which allows seek() calls, so it cannot
 *      be a stream.  Returns ISC_R_INVALIDFILE if not.
 */

isc_result_t
dns_rbt_deserialize_tree(void *base_address, size_t filesize,
			 off_t header_offset, isc_mem_t *mctx,
			 dns_rbtdeleter_t deleter, void *deleter_arg,
			 dns_rbtdatafixer_t datafixer, void *fixer_arg,
			 dns_rbtnode_t **originp, dns_rbt_t **rbtp);
/*%<
 * Read a RBT structure and its data from a file.
 *
 * If 'originp' is not NULL, then it is pointed to the root node of the RBT.
 *
 * Notes:
 * \li  The file must be an actual file which allows seek() calls, so it cannot
 *      be a stream.  This condition is not checked in the code.
 */

void
dns_rbt_printtext(dns_rbt_t *rbt,
		  void (*data_printer)(FILE *, void *), FILE *f);
/*%<
 * Print an ASCII representation of the internal structure of the red-black
 * tree of trees to the passed stream.
 *
 * data_printer is a callback function that is called to print the data
 * in a node. It should print it to the passed FILE stream.
 *
 * Notes:
 * \li  The name stored at each node, along with the node's color, is printed.
 *      Then the down pointer, left and right pointers are displayed
 *      recursively in turn.  NULL down pointers are silently omitted;
 *      NULL left and right pointers are printed.
 */

void
dns_rbt_printdot(dns_rbt_t *rbt, bool show_pointers, FILE *f);
/*%<
 * Print a GraphViz dot representation of the internal structure of the
 * red-black tree of trees to the passed stream.
 *
 * If show_pointers is TRUE, pointers are also included in the generated
 * graph.
 *
 * Notes:
 * \li	The name stored at each node, along with the node's color is displayed.
 *	Then the down pointer, left and right pointers are displayed
 *	recursively in turn.  NULL left, right and down pointers are
 *	silently omitted.
 */

void
dns_rbt_printnodeinfo(dns_rbtnode_t *n, FILE *f);
/*%<
 * Print out various information about a node
 *
 * Requires:
 *\li	'n' is a valid pointer.
 *
 *\li	'f' points to a valid open FILE structure that allows writing.
 */

size_t
dns__rbt_getheight(dns_rbt_t *rbt);
/*%<
 * Return the maximum height of sub-root nodes found in the red-black
 * forest.
 *
 * The height of a node is defined as the number of nodes in the longest
 * path from the node to a leaf. For each subtree in the forest, this
 * function determines the height of its root node. Then it returns the
 * maximum such height in the forest.
 *
 * Note: This function exists for testing purposes. Non-test code must
 * not use it.
 *
 * Requires:
 * \li  rbt is a valid rbt manager.
 */

bool
dns__rbt_checkproperties(dns_rbt_t *rbt);
/*%<
 * Check red-black properties of the forest.
 *
 * Note: This function exists for testing purposes. Non-test code must
 * not use it.
 *
 * Requires:
 * \li  rbt is a valid rbt manager.
 */

size_t
dns__rbtnode_getdistance(dns_rbtnode_t *node);
/*%<
 * Return the distance (in nodes) from the node to its upper node of its
 * subtree. The root node has a distance of 1. A child of the root node
 * has a distance of 2.
 */

/*****
 ***** Chain Functions
 *****/

void
dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx);
/*%<
 * Initialize 'chain'.
 *
 * Requires:
 *\li   'chain' is a valid pointer.
 *
 *\li   'mctx' is a valid memory context.
 *
 * Ensures:
 *\li   'chain' is suitable for use.
 */

void
dns_rbtnodechain_reset(dns_rbtnodechain_t *chain);
/*%<
 * Free any dynamic storage associated with 'chain', and then reinitialize
 * 'chain'.
 *
 * Requires:
 *\li   'chain' is a valid pointer.
 *
 * Ensures:
 *\li   'chain' is suitable for use, and uses no dynamic storage.
 */

void
dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain);
/*%<
 * Free any dynamic storage associated with 'chain', and then invalidates it.
 *
 * Notes:
 *\li   Future calls to any dns_rbtnodechain_ function will need to call
 *      dns_rbtnodechain_init on the chain first (except, of course,
 *      dns_rbtnodechain_init itself).
 *
 * Requires:
 *\li   'chain' is a valid chain.
 *
 * Ensures:
 *\li   'chain' is no longer suitable for use, and uses no dynamic storage.
 */

isc_result_t
dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
			 dns_name_t *origin, dns_rbtnode_t **node);
/*%<
 * Provide the name, origin and node to which the chain is currently pointed.
 *
 * Notes:
 *\li   The tree need not have be locked against additions for the chain
 *      to remain valid, however there are no guarantees if any deletion
 *      has been made since the chain was established.
 *
 * Requires:
 *\li   'chain' is a valid chain.
 *
 * Ensures:
 *\li   'node', if non-NULL, is the node to which the chain was pointed
 *      by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last.
 *      If none were called for the chain since it was initialized or reset,
 *      or if the was no predecessor to the name searched for with
 *      dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned.
 *
 *\li   'name', if non-NULL, is the name stored at the terminal level of
 *      the chain.  This is typically a single label, like the "www" of
 *      "www.isc.org", but need not be so.  At the root of the tree of trees,
 *      if the node is "." then 'name' is ".", otherwise it is relative to ".".
 *      (Minimalist and atypical case:  if the tree has just the name
 *      "isc.org." then the root node's stored name is "isc.org." but 'name'
 *      will be "isc.org".)
 *
 *\li   'origin', if non-NULL, is the sequence of labels in the levels
 *      above the terminal level, such as "isc.org." in the above example.
 *      'origin' is always "." for the root node.
 *
 *
 * Returns:
 *\li   #ISC_R_SUCCESS          name, origin & node were successfully set.
 *\li   #ISC_R_NOTFOUND         The chain does not point to any node.
 *\li   &lt;something_else>     Any error return from dns_name_concatenate.
 */

isc_result_t
dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
		       dns_name_t *name, dns_name_t *origin);
/*%<
 * Set the chain to the lexically first node in the tree of trees.
 *
 * Notes:
 *\li   By the definition of ordering for DNS names, the root of the tree of
 *      trees is the very first node, since everything else in the megatree
 *      uses it as a common suffix.
 *
 * Requires:
 *\li   'chain' is a valid chain.
 *\li   'rbt' is a valid rbt manager.
 *
 * Ensures:
 *\li   The chain points to the very first node of the tree.
 *
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.  Thus 'origin' will always be ".".
 *
 * Returns:
 *\li   #DNS_R_NEWORIGIN                The name & origin were successfully set.
 *\li   &lt;something_else>     Any error result from dns_rbtnodechain_current.
 */

isc_result_t
dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
		       dns_name_t *name, dns_name_t *origin);
/*%<
 * Set the chain to the lexically last node in the tree of trees.
 *
 * Requires:
 *\li   'chain' is a valid chain.
 *\li   'rbt' is a valid rbt manager.
 *
 * Ensures:
 *\li   The chain points to the very last node of the tree.
 *
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.
 *
 * Returns:
 *\li   #DNS_R_NEWORIGIN                The name & origin were successfully set.
 *\li   #ISC_R_NOMEMORY         Resource Limit: Out of Memory building chain.
 *\li   &lt;something_else>     Any error result from dns_name_concatenate.
 */

isc_result_t
dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
		      dns_name_t *origin);
/*%<
 * Adjusts chain to point the DNSSEC predecessor of the name to which it
 * is currently pointed.
 *
 * Requires:
 *\li   'chain' is a valid chain.
 *\li   'chain' has been pointed somewhere in the tree with dns_rbt_findnode,
 *      dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that
 *      dns_rbt_findnode is not guaranteed to point the chain somewhere,
 *      since there may have been no predecessor to the searched for name.
 *
 * Ensures:
 *\li   The chain is pointed to the predecessor of its current target.
 *
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.
 *
 *\li   'origin' is only if a new origin was found.
 *
 * Returns:
 *\li   #ISC_R_SUCCESS          The predecessor was found and 'name' was set.
 *\li   #DNS_R_NEWORIGIN                The predecessor was found with a different
 *                              origin and 'name' and 'origin' were set.
 *\li   #ISC_R_NOMORE           There was no predecessor.
 *\li   &lt;something_else>     Any error result from dns_rbtnodechain_current.
 */

isc_result_t
dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
		      dns_name_t *origin);
/*%<
 * Adjusts chain to point the DNSSEC successor of the name to which it
 * is currently pointed.
 *
 * Requires:
 *\li   'chain' is a valid chain.
 *\li   'chain' has been pointed somewhere in the tree with dns_rbt_findnode,
 *      dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that
 *      dns_rbt_findnode is not guaranteed to point the chain somewhere,
 *      since there may have been no predecessor to the searched for name.
 *
 * Ensures:
 *\li   The chain is pointed to the successor of its current target.
 *
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.
 *
 *\li   'origin' is only if a new origin was found.
 *
 * Returns:
 *\li   #ISC_R_SUCCESS          The successor was found and 'name' was set.
 *\li   #DNS_R_NEWORIGIN                The successor was found with a different
 *                              origin and 'name' and 'origin' were set.
 *\li   #ISC_R_NOMORE           There was no successor.
 *\li   &lt;something_else>     Any error result from dns_name_concatenate.
 */

isc_result_t
dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
		      dns_name_t *origin);
/*%<
 * Descend down if possible.
 */

isc_result_t
dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name);
/*%<
 * Find the next node at the current depth in DNSSEC order.
 */

/*
 * Wrapper macros for manipulating the rbtnode reference counter:
 *   Since we selectively use isc_refcount_t for the reference counter of
 *   a rbtnode, operations on the counter depend on the actual type of it.
 *   The following macros provide a common interface to these operations,
 *   hiding the back-end.  The usage is the same as that of isc_refcount_xxx().
 */
#ifdef DNS_RBT_USEISCREFCOUNT
#define dns_rbtnode_refinit(node, n)                            \
	do {                                                    \
		isc_refcount_init(&(node)->references, (n));    \
	} while (0)
#define dns_rbtnode_refdestroy(node)                            \
	do {                                                    \
		isc_refcount_destroy(&(node)->references);      \
	} while (0)
#define dns_rbtnode_refcurrent(node)                            \
	isc_refcount_current(&(node)->references)
#define dns_rbtnode_refincrement0(node, refs)                   \
	do {                                                    \
		isc_refcount_increment0(&(node)->references, (refs)); \
	} while (0)
#define dns_rbtnode_refincrement(node, refs)                    \
	do {                                                    \
		isc_refcount_increment(&(node)->references, (refs)); \
	} while (0)
#define dns_rbtnode_refdecrement(node, refs)                    \
	do {                                                    \
		isc_refcount_decrement(&(node)->references, (refs)); \
	} while (0)
#else  /* DNS_RBT_USEISCREFCOUNT */
#define dns_rbtnode_refinit(node, n)    ((node)->references = (n))
#define dns_rbtnode_refdestroy(node)    ISC_REQUIRE((node)->references == 0)
#define dns_rbtnode_refcurrent(node)    ((node)->references)

#if (__STDC_VERSION__ + 0) >= 199901L || defined __GNUC__
static inline void
dns_rbtnode_refincrement0(dns_rbtnode_t *node, unsigned int *refs) {
	node->references++;
	if (refs != NULL)
		*refs = node->references;
}

static inline void
dns_rbtnode_refincrement(dns_rbtnode_t *node, unsigned int *refs) {
	ISC_REQUIRE(node->references > 0);
	node->references++;
	if (refs != NULL)
		*refs = node->references;
}

static inline void
dns_rbtnode_refdecrement(dns_rbtnode_t *node, unsigned int *refs) {
	ISC_REQUIRE(node->references > 0);
	node->references--;
	if (refs != NULL)
		*refs = node->references;
}
#else
#define dns_rbtnode_refincrement0(node, refs)                   \
	do {                                                    \
		unsigned int *_tmp = (unsigned int *)(refs);    \
		(node)->references++;                           \
		if ((_tmp) != NULL)                             \
			(*_tmp) = (node)->references;           \
	} while (0)
#define dns_rbtnode_refincrement(node, refs)                    \
	do {                                                    \
		ISC_REQUIRE((node)->references > 0);                \
		(node)->references++;                           \
		if ((refs) != NULL)                             \
			(*refs) = (node)->references;           \
	} while (0)
#define dns_rbtnode_refdecrement(node, refs)                    \
	do {                                                    \
		ISC_REQUIRE((node)->references > 0);                \
		(node)->references--;                           \
		if ((refs) != NULL)                             \
			(*refs) = (node)->references;           \
	} while (0)
#endif
#endif /* DNS_RBT_USEISCREFCOUNT */

void
dns_rbtnode_nodename(dns_rbtnode_t *node, dns_name_t *name);

dns_rbtnode_t *
dns_rbt_root(dns_rbt_t *rbt);

ISC_LANG_ENDDECLS

#endif /* DNS_RBT_H */

Back