BIND9 Internals: lib/dns/include/dns/rbt.h File Reference

#define DNS_RBT_H 1

Definition at line 21 of file rbt.h.

#define DNS_RBT_USEHASH 1

Definition at line 34 of file rbt.h.

#define DNS_RBTFIND_NOOPTIONS 0x00

Option values for dns_rbt_findnode() and dns_rbt_findname(). These are used to form a bitmask.

Definition at line 41 of file rbt.h.

Referenced by delete(), dns_keytable_delete(), dns_keytable_deletekeynode(), dns_keytable_find(), dns_keytable_issecuredomain(), dns_ntatable_covered(), dns_rbt_deletename(), and previous_closest_nsec().

#define DNS_RBTFIND_EMPTYDATA 0x01

Option values for dns_rbt_findnode() and dns_rbt_findname(). These are used to form a bitmask.

Definition at line 42 of file rbt.h.

Referenced by ATF_TC_BODY(), cache_find(), cache_findzonecut(), dbiterator_seek(), delete_node(), dns_rbt_findname(), dns_rbt_findnode(), dns_rpz_find_name(), find_wildcard(), findnodeintree(), and zone_find().

#define DNS_RBTFIND_NOEXACT 0x02

Option values for dns_rbt_findnode() and dns_rbt_findname(). These are used to form a bitmask.

Definition at line 43 of file rbt.h.

Referenced by cache_findzonecut(), dns_dbtable_find(), dns_rbt_findnode(), and dns_zt_find().

#define DNS_RBTFIND_NOPREDECESSOR 0x04

Option values for dns_rbt_findnode() and dns_rbt_findname(). These are used to form a bitmask.

Definition at line 44 of file rbt.h.

Referenced by dns_rbt_findnode().

#define DNS_RBT_USEMAGIC 1

Definition at line 53 of file rbt.h.

#define DNS_RBT_LOCKLENGTH 10

Definition at line 58 of file rbt.h.

Referenced by dns_rbtdb_create().

#define DNS_RBT_REFLENGTH 20

Definition at line 59 of file rbt.h.

#define DNS_RBTNODE_MAGIC ISC_MAGIC('R','B','N','O')

Definition at line 61 of file rbt.h.

Referenced by create_node().

#define DNS_RBTNODE_VALID ( n ) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC)

Definition at line 63 of file rbt.h.

Referenced by addonlevel(), dns_rbt_deletenode(), dns_rbt_findnode(), dns_rbt_formatnodename(), dns_rbt_fullnamefromnode(), dns_rbt_namefromnode(), rotate_left(), rotate_right(), and treefix().

#define DNS_RBT_LEVELBLOCK 254

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.

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.

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.

Definition at line 218 of file rbt.h.

#define dns_rbtnode_refinit	(	node,
		n		)	((node)->references = (n))

Definition at line 1052 of file rbt.h.

Referenced by create_node().

#define dns_rbtnode_refdestroy ( node ) REQUIRE((node)->references == 0)

Definition at line 1053 of file rbt.h.

Referenced by dns_rbt_deletenode().

#define dns_rbtnode_refcurrent ( node ) ((node)->references)

Definition at line 1054 of file rbt.h.

Referenced by cache_find(), cache_findzonecut(), cache_zonecut_callback(), cleanup_dead_nodes(), expire_header(), find_coveringnsec(), find_deepest_zonecut(), and printnode().

#define dns_rbtnode_refincrement0	(	node,
		refs		)

Value:

do {                                                    \
                unsigned int *_tmp = (unsigned int *)(refs);    \
                (node)->references++;                           \
                if ((_tmp) != NULL)                             \
                        (*_tmp) = (node)->references;           \
        } while (0)

Definition at line 1080 of file rbt.h.

Referenced by new_reference().

#define dns_rbtnode_refincrement	(	node,
		refs		)

Value:

do {                                                    \
                REQUIRE((node)->references > 0);                \
                (node)->references++;                           \
                if ((refs) != NULL)                             \
                        (*refs) = (node)->references;           \
        } while (0)

Definition at line 1087 of file rbt.h.

Referenced by add_changed(), allrdatasets(), attachnode(), and dbiterator_current().

#define dns_rbtnode_refdecrement	(	node,
		refs		)

Value:

do {                                                    \
                REQUIRE((node)->references > 0);                \
                (node)->references--;                           \
                if ((refs) != NULL)                             \
                        (*refs) = (node)->references;           \
        } while (0)

Definition at line 1094 of file rbt.h.

Referenced by decrement_reference().

typedef struct dns_rbtnode dns_rbtnode_t

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.

Definition at line 74 of file rbt.h.

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

Definition at line 151 of file rbt.h.

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

Definition at line 155 of file rbt.h.

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

Definition at line 160 of file rbt.h.

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

Definition at line 164 of file rbt.h.

typedef struct dns_rbtnodechain dns_rbtnodechain_t

anonymous enum

Enumerator:

DNS_RBT_NSEC_NORMAL
DNS_RBT_NSEC_HAS_NSEC
DNS_RBT_NSEC_NSEC
DNS_RBT_NSEC_NSEC3

Definition at line 75 of file rbt.h.

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:

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:

mctx is a pointer to a valid memory context.
rbtp != NULL && *rbtp == NULL
arg == NULL iff deleter == NULL

Ensures:

If result is ISC_R_SUCCESS: *rbtp points to a valid red-black tree manager

If result is failure: *rbtp does not point to a valid red-black tree manager.

Returns:

ISC_R_SUCCESS Success
ISC_R_NOMEMORY Resource limit: Out of Memory

Definition at line 921 of file rbt.c.

References dns_rbt::data_deleter, dns_rbt::deleter_arg, dns_rbt::hashsize, dns_rbt::hashtable, isc_mem_attach(), isc_mem_get, isc_mem_putanddetach, ISC_R_NOMEMORY, ISC_R_SUCCESS, dns_rbt::magic, dns_rbt::mctx, dns_rbt::mmap_location, dns_rbt::nodecount, RBT_MAGIC, REQUIRE, and dns_rbt::root.

Referenced by ATF_TC_BODY(), configure_view_nametable(), dns_dbtable_create(), dns_fwdtable_create(), dns_keytable_create(), dns_ntatable_create(), dns_rbt_deserialize_tree(), dns_rbtdb_create(), dns_resolver_disable_algorithm(), dns_resolver_disable_ds_digest(), dns_resolver_setmustbesecure(), dns_rpz_new_zones(), dns_tsigkeyring_create(), dns_zt_create(), and test_context_setup().

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:

'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:

rbt is a valid rbt manager.
dns_name_isabsolute(name) == TRUE

Ensures:

'name' is not altered in any way.

Any external references to nodes in the tree are unaffected by node splits that are necessary to insert the new name.

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'.

If result is ISC_R_EXISTS or ISC_R_NOSPACE: The tree of trees is unaltered.

If result is ISC_R_NOMEMORY: No guarantees.

Returns:

ISC_R_SUCCESS Success
ISC_R_EXISTS The name already exists with associated data.
ISC_R_NOSPACE The name had more logical labels than are allowed.
ISC_R_NOMEMORY Resource Limit: Out of Memory

Definition at line 1349 of file rbt.c.

References DATA, dns_name_isabsolute(), dns_rbt_addnode(), ISC_R_EXISTS, ISC_R_SUCCESS, REQUIRE, and VALID_RBT.

Referenced by add_test_data(), ATF_TC_BODY(), configure_view_nametable(), dns_dbtable_add(), dns_fwdtable_add(), dns_fwdtable_addfwd(), dns_resolver_setmustbesecure(), dns_zt_mount(), insert_nodes(), keyring_add(), and test_context_setup().

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:

rbt is a valid rbt structure.
dns_name_isabsolute(name) == TRUE
nodep != NULL && *nodep == NULL

Ensures:

'name' is not altered in any way.

Any external references to nodes in the tree are unaffected by node splits that are necessary to insert the new name.

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'.

If result is ISC_R_EXISTS: The tree of trees is unaltered. *nodep is the existing node for 'name'.

If result is ISC_R_NOMEMORY: No guarantees.

Returns:

ISC_R_SUCCESS Success
ISC_R_EXISTS The name already exists, possibly without data.
ISC_R_NOMEMORY Resource Limit: Out of Memory

Definition at line 1068 of file rbt.c.

References ADD_LEVEL, add_name(), addonlevel(), ATTRS, COLOR, create_node(), dns_fixedname_init, dns_fixedname_name, dns_name_clone(), dns_name_countlabels(), dns_name_fullcompare(), dns_name_getlabelsequence(), dns_name_init(), dns_name_isabsolute(), dns_name_split(), DNS_NAMEATTR_ABSOLUTE, dns_namereln_commonancestor, dns_namereln_contains, dns_namereln_equal, dns_namereln_none, dns_namereln_subdomain, DNS_RBT_NSEC_HAS_NSEC, DNS_RBT_NSEC_NORMAL, dns_rbtnodechain_init(), DOWN, hash_node, INSIST, IS_ROOT, dns_rbtnode::is_root, ISC_R_EXISTS, ISC_R_NOSPACE, ISC_R_SUCCESS, dns_name::labels, LEFT, dns_name::length, dns_rbtnodechain::level_count, dns_rbtnodechain::levels, MAKE_BLACK, dns_rbt::mctx, NAMELEN, dns_rbt::nodecount, NODENAME, dns_rbtnode::nsec, OFFSETLEN, PARENT, REQUIRE, RIGHT, dns_rbt::root, root, and VALID_RBT.

Referenced by add_empty_wildcards(), add_nm(), add_wildcard_magic(), addrdataset(), dns_ntatable_add(), dns_rbt_addname(), dns_rbtdb_create(), dns_resolver_disable_algorithm(), dns_resolver_disable_ds_digest(), findnodeintree(), insert(), insert_helper(), loading_addrdataset(), and loadnode().

isc_result_t dns_rbt_findname	(	dns_rbt_t *	rbt,
		dns_name_t *	name,
		unsigned int	options,
		dns_name_t *	foundname,
		void **	data
	)

Get the data pointer associated with 'name'.

Notes:

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.

A node that has no data is considered not to exist for this function, unless the DNS_RBTFIND_EMPTYDATA option is set.

Requires:

rbt is a valid rbt manager.
dns_name_isabsolute(name) == TRUE
data != NULL && *data == NULL

Ensures:

'name' and the tree are not altered in any way.

If result is ISC_R_SUCCESS: *data is the data associated with 'name'.

If result is DNS_R_PARTIALMATCH: *data is the data associated with the deepest superdomain of 'name' which has data.

If result is ISC_R_NOTFOUND: Neither the name nor a superdomain was found with data.

Returns:

ISC_R_SUCCESS Success
DNS_R_PARTIALMATCH Superdomain found with data
ISC_R_NOTFOUND No match
ISC_R_NOSPACE Concatenating nodes to form foundname failed

Definition at line 1916 of file rbt.c.

References DATA, dns_rbt_findnode(), DNS_RBTFIND_EMPTYDATA, ISC_R_NOTFOUND, and REQUIRE.

Referenced by check_test_data(), dns_dbtable_find(), dns_dbtable_remove(), dns_fwdtable_find2(), dns_keytable_finddeepestmatch(), dns_keytable_findkeynode(), dns_resolver_algorithm_supported(), dns_resolver_ds_digest_supported(), dns_resolver_getmustbesecure(), dns_tsigkey_find(), and dns_zt_find().

isc_result_t dns_rbt_findnode	(	dns_rbt_t *	rbt,
		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:

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.

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.)

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.

Within the chain structure, the 'levels' member of the structure holds the root node of each level except the first.

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[].

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.

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:

rbt is a valid rbt manager.
dns_name_isabsolute(name) == TRUE.
node != NULL && *node == NULL.
DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually exclusive.

Ensures:

'name' and the tree are not altered in any way.

If result is ISC_R_SUCCESS:

 *              *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.
 *

If result is DNS_R_PARTIALMATCH:

 *              *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'.
 *

If result is ISC_R_NOTFOUND:

 *              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.
 *

Returns:

ISC_R_SUCCESS Success
DNS_R_PARTIALMATCH Superdomain found with data
ISC_R_NOTFOUND No match, or superdomain with no data
ISC_R_NOSPACE Concatenating nodes to form foundname failed

Definition at line 1379 of file rbt.c.

References ADD_LEVEL, chain_name(), DATA, dns_fixedname_init, dns_fixedname_name, dns_name_clone(), dns_name_countlabels(), dns_name_equal(), dns_name_fullcompare(), dns_name_fullhash(), dns_name_getlabelsequence(), dns_name_init(), dns_name_isabsolute(), dns_name_split(), dns_namereln_commonancestor, dns_namereln_contains, dns_namereln_equal, dns_namereln_none, dns_namereln_subdomain, DNS_R_CONTINUE, DNS_R_NEWORIGIN, DNS_R_PARTIALMATCH, DNS_RBTFIND_EMPTYDATA, DNS_RBTFIND_NOEXACT, DNS_RBTFIND_NOPREDECESSOR, DNS_RBTNODE_VALID, dns_rbtnodechain_init(), dns_rbtnodechain_prev(), dns_rbtnodechain_reset(), DOWN, dns_rbtnodechain::end, ENSURE, FINDCALLBACK, get_upper_node(), hash, dns_rbtnode::hashnext, dns_rbt::hashsize, dns_rbt::hashtable, HASHVAL, INSIST, ISC_FALSE, ISC_R_NOMORE, ISC_R_NOTFOUND, ISC_R_SUCCESS, ISC_TRUE, LEFT, dns_rbtnodechain::level_count, dns_rbtnodechain::level_matches, dns_rbtnodechain::levels, dns_rbt::mctx, move_chain_to_last(), NODENAME, PARENT, POST, REQUIRE, RIGHT, dns_rbt::root, and VALID_RBT.

Referenced by ATF_TC_BODY(), cache_find(), cache_findzonecut(), dbiterator_seek(), del_name(), delete(), delete_node(), dns_keytable_delete(), dns_keytable_deletekeynode(), dns_keytable_find(), dns_keytable_issecuredomain(), dns_ntatable_covered(), dns_rbt_deletename(), dns_rbt_findname(), dns_rpz_find_name(), find_wildcard(), findnodeintree(), is_answeraddress_allowed(), is_answertarget_allowed(), previous_closest_nsec(), and zone_find().

isc_result_t dns_rbt_deletename	(	dns_rbt_t *	rbt,
		dns_name_t *	name,
		isc_boolean_t	recurse
	)

Delete 'name' from the tree of trees.

Notes:

When 'name' is removed, if recurse is ISC_TRUE then all of its subnames are removed too.

Requires:

rbt is a valid rbt manager.
dns_name_isabsolute(name) == TRUE

Ensures:

'name' is not altered in any way.

Does NOT ensure that any external references to nodes in the tree are unaffected by node joins.

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).

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.

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:

ISC_R_SUCCESS Success
ISC_R_NOTFOUND No match
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.

Definition at line 1939 of file rbt.c.

References DATA, dns_name_isabsolute(), DNS_R_PARTIALMATCH, dns_rbt_deletenode(), dns_rbt_findnode(), DNS_RBTFIND_NOOPTIONS, ISC_R_NOTFOUND, ISC_R_SUCCESS, REQUIRE, and VALID_RBT.

Referenced by ATF_TC_BODY(), delete_keynames(), dns_dbtable_remove(), dns_fwdtable_delete(), dns_zt_unmount(), remove_fromring(), and remove_nodes().

isc_result_t dns_rbt_deletenode	(	dns_rbt_t *	rbt,
		dns_rbtnode_t *	node,
		isc_boolean_t	recurse
	)

Delete 'node' from the tree of trees.

Notes:

When 'node' is removed, if recurse is ISC_TRUE then all nodes in levels down from it are removed too.

Requires:

rbt is a valid rbt manager.
node != NULL.

Ensures:

Does NOT ensure that any external references to nodes in the tree are unaffected by node joins.

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.

If result is ISC_R_NOMEMORY or ISC_R_NOSPACE: The node was deleted, but the tree structure was not optimized.

Returns:

ISC_R_SUCCESS Success
ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes.
ISC_R_NOSPACE dns_name_concatenate failed when joining nodes.

Definition at line 2012 of file rbt.c.

References DATA, dns_rbt::data_deleter, deletefromlevel(), dns_rbt::deleter_arg, deletetree(), dns_rbtnode_refdestroy, DNS_RBTNODE_VALID, DOWN, freenode(), get_upper_node(), INSIST, ISC_R_SUCCESS, dns_rbtnode::magic, dns_rbt::nodecount, REQUIRE, dns_rbt::root, RUNTIME_CHECK, unhash_node, and VALID_RBT.

Referenced by ATF_TC_BODY(), del_name(), delete(), delete_node(), dns_keytable_delete(), dns_keytable_deletekeynode(), dns_rbt_deletename(), and loadnode().

void dns_rbt_namefromnode	(	dns_rbtnode_t *	node,
		dns_name_t *	name
	)

Convert the sequence of labels stored at 'node' into a 'name'.

Notes:

This function does not return the full name, from the root, but just the labels at the indicated node.

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:

name->offsets == NULL

Ensures:

'name' is DNS_NAMEATTR_READONLY.

'name' will point directly to the labels stored after the dns_rbtnode_t struct.

'name' will have offsets that also point to the information stored as part of the node.

Definition at line 2096 of file rbt.c.

References DNS_RBTNODE_VALID, NODENAME, dns_name::offsets, and REQUIRE.

Referenced by compare_labelsequences(), dns_rbtdb_create(), find_deepest_zonecut(), find_wildcard(), findnodeintree(), and loading_addrdataset().

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:

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:

name != NULL
name has a dedicated buffer.

Returns:

ISC_R_SUCCESS
ISC_R_NOSPACE (possible via dns_name_concatenate)
DNS_R_NAMETOOLONG (possible via dns_name_concatenate)

Definition at line 2106 of file rbt.c.

References dns_name::buffer, dns_name_concatenate(), dns_name_init(), dns_name_isabsolute(), dns_name_reset(), DNS_RBTNODE_VALID, get_upper_node(), INSIST, ISC_R_SUCCESS, NODENAME, and REQUIRE.

Referenced by addrdataset(), delete_node(), dns_ntatable_save(), dns_ntatable_totext(), dns_rbt_formatnodename(), findnodeintree(), and getsigningtime().

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:

'size' is the length of the printname buffer. This should be DNS_NAME_FORMATSIZE or larger.

Requires:

node and printname are not NULL.

Returns:

The 'printname' pointer.

Definition at line 2133 of file rbt.c.

References dns_fixedname_init, dns_fixedname_name, dns_name_format(), dns_rbt_fullnamefromnode(), DNS_RBTNODE_VALID, dns_result_totext(), ISC_R_SUCCESS, and REQUIRE.

Referenced by decrement_reference(), and expirenode().

unsigned int dns_rbt_nodecount ( dns_rbt_t * rbt )

Obtain the number of nodes in the tree of trees.

Requires:

rbt is a valid rbt manager.

Definition at line 998 of file rbt.c.

References dns_rbt::nodecount, REQUIRE, and VALID_RBT.

Referenced by ATF_TC_BODY(), check_tree(), flush_deletions(), and nodecount().

unsigned int dns_rbt_hashsize ( dns_rbt_t * rbt )

Obtain the current number of buckets in the 'rbt' hash table.

Requires:

rbt is a valid rbt manager.

Definition at line 1006 of file rbt.c.

References dns_rbt::hashsize, REQUIRE, and VALID_RBT.

Referenced by hashsize().

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:

*rbt is a valid rbt manager.

Ensures on ISC_R_SUCCESS:

All space allocated by the RBT library has been returned.

*rbt is invalidated as an rbt manager.

Returns:

ISC_R_SUCCESS
ISC_R_QUOTA if 'quantum' nodes have been destroyed.

Definition at line 971 of file rbt.c.

References deletetreeflat(), dns_rbt::hashsize, dns_rbt::hashtable, INSIST, isc_mem_put, isc_mem_putanddetach, ISC_R_QUOTA, ISC_R_SUCCESS, dns_rbt::magic, dns_rbt::mctx, dns_rbt::mmap_location, dns_rbt::nodecount, REQUIRE, dns_rbt::root, and VALID_RBT.

Referenced by dns_rbt_destroy(), and free_rbtdb().

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.

Definition at line 653 of file rbt.c.

Referenced by ATF_TC_BODY(), dns_rbt_serialize_tree(), rbt_datafixer(), rbt_datawriter(), serialize_node(), serialize_nodes(), and write_header().

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:

The file must be an actual file which allows seek() calls, so it cannot be a stream. Returns ISC_R_INVALIDFILE if not.

Definition at line 663 of file rbt.c.

References CHECK, cleanup(), dns_rbt_serialize_align(), dns_rbt_zero_header(), HEADER_LENGTH, isc_crc64_final(), isc_crc64_init(), isc_file_isplainfilefd(), ISC_R_SUCCESS, isc_stdio_seek(), isc_stdio_tell(), REQUIRE, dns_rbt::root, serialize_nodes(), and write_header().

Referenced by ATF_TC_BODY(), and serialize().

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:

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.

Definition at line 832 of file rbt.c.

References file_header::bigendian, CHECK, cleanup(), file_header::crc, dns_rbt_create(), dns_rbt_destroy(), dns_rootname, file_header::first_node_offset, header, isc_crc64_final(), isc_crc64_init(), ISC_R_INVALIDFILE, ISC_R_SUCCESS, dns_rbt::mmap_location, dns_rbt::nodecount, file_header::nodecount, file_header::ptrsize, file_header::rdataset_fixed, rehash, REQUIRE, dns_rbt::root, and treefix().

Referenced by ATF_TC_BODY(), and deserialize32().

void dns_rbt_printtext	(	dns_rbt_t *	rbt,
		void()(FILE , void *)	data_printer,
		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:

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.

Definition at line 3080 of file rbt.c.

References data_printer(), print_text_helper(), REQUIRE, dns_rbt::root, and VALID_RBT.

Referenced by ATF_TC_BODY().

void dns_rbt_printdot	(	dns_rbt_t *	rbt,
		isc_boolean_t	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:

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.

Definition at line 3142 of file rbt.c.

References nodecount(), print_dot_helper(), REQUIRE, dns_rbt::root, and VALID_RBT.

void dns_rbt_printnodeinfo	(	dns_rbtnode_t *	n,
		FILE *	f
	)

Print out various information about a node.

Requires:

'n' is a valid pointer.

'f' points to a valid open FILE structure that allows writing.

Definition at line 2984 of file rbt.c.

References dns_rbtnode::data, dns_rbtnode::data_is_relative, dns_rbtnode::down, dns_rbtnode::down_is_relative, ISC_TRUE, dns_rbtnode::left, dns_rbtnode::left_is_relative, dns_rbtnode::locknum, dns_rbtnode::parent, dns_rbtnode::parent_is_relative, printnodename(), dns_rbtnode::right, and dns_rbtnode::right_is_relative.

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:

rbt is a valid rbt manager.

Definition at line 2893 of file rbt.c.

References getheight_helper(), and dns_rbt::root.

Referenced by ATF_TC_BODY(), and check_tree().

isc_boolean_t 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:

rbt is a valid rbt manager.

Definition at line 2959 of file rbt.c.

References check_black_distance_helper(), check_properties_helper(), ISC_FALSE, and dns_rbt::root.

Referenced by ATF_TC_BODY(), and check_tree().

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.

Definition at line 373 of file rbt.c.

References IS_ROOT, and PARENT.

Referenced by ATF_TC_BODY().

void dns_rbtnodechain_init	(	dns_rbtnodechain_t *	chain,
		isc_mem_t *	mctx
	)

Initialize 'chain'.

Requires:

'chain' is a valid pointer.

'mctx' is a valid memory context.

Ensures:

'chain' is suitable for use.

Definition at line 3158 of file rbt.c.

References CHAIN_MAGIC, dns_rbtnodechain::end, dns_rbtnodechain::level_count, dns_rbtnodechain::level_matches, dns_rbtnodechain::levels, dns_rbtnodechain::magic, dns_rbtnodechain::mctx, and REQUIRE.

Referenced by ATF_TC_BODY(), cache_find(), cache_findzonecut(), cleanup_ring(), createiterator(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_rbt_addnode(), dns_rbt_findnode(), dns_rpz_ready(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), find_wildcard(), list_keynames(), previous_closest_nsec(), sync_keyzone(), and zone_find().

void dns_rbtnodechain_reset ( dns_rbtnodechain_t * chain )

Free any dynamic storage associated with 'chain', and then reinitialize 'chain'.

Requires:

'chain' is a valid pointer.

Ensures:

'chain' is suitable for use, and uses no dynamic storage.

Definition at line 3604 of file rbt.c.

References dns_rbtnodechain::end, dns_rbtnodechain::level_count, dns_rbtnodechain::level_matches, REQUIRE, and VALID_CHAIN.

Referenced by cache_find(), cache_findzonecut(), dbiterator_destroy(), dbiterator_first(), dbiterator_last(), dbiterator_next(), dbiterator_prev(), dbiterator_seek(), dns_rbt_findnode(), dns_rbtnodechain_first(), dns_rbtnodechain_invalidate(), dns_rbtnodechain_last(), and zone_find().

void dns_rbtnodechain_invalidate ( dns_rbtnodechain_t * chain )

Free any dynamic storage associated with 'chain', and then invalidates it.

Notes:

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:

'chain' is a valid chain.

Ensures:

'chain' is no longer suitable for use, and uses no dynamic storage.

Definition at line 3618 of file rbt.c.

References dns_rbtnodechain_reset(), and dns_rbtnodechain::magic.

Referenced by ATF_TC_BODY(), cleanup_ring(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), find_closest_nsec(), and list_keynames().

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:

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:

'chain' is a valid chain.

Ensures:

'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.

'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".)

'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:

ISC_R_SUCCESS name, origin & node were successfully set.
ISC_R_NOTFOUND The chain does not point to any node.
<something_else> Any error return from dns_name_concatenate.

Definition at line 3175 of file rbt.c.

References dns_name::attributes, chain_name(), dns_name_copy(), dns_name_isabsolute(), DNS_NAMEATTR_ABSOLUTE, dns_rootname, dns_rbtnodechain::end, INSIST, ISC_FALSE, ISC_R_NOTFOUND, ISC_R_SUCCESS, dns_name::labels, dns_name::length, dns_rbtnodechain::level_count, NODENAME, REQUIRE, and VALID_CHAIN.

Referenced by activeempty(), activeemtpynode(), ATF_TC_BODY(), cleanup_ring(), dbiterator_first(), dbiterator_last(), dbiterator_next(), dbiterator_prev(), dbiterator_seek(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_rbtnodechain_first(), dns_rbtnodechain_last(), dns_rbtnodechain_prev(), dns_rpz_ready(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), find_closest_nsec(), find_coveringnsec(), list_keynames(), previous_closest_nsec(), and sync_keyzone().

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:

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:

'chain' is a valid chain.
'rbt' is a valid rbt manager.

Ensures:

The chain points to the very first node of the tree.

'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current. Thus 'origin' will always be ".".

Returns:

DNS_R_NEWORIGIN The name & origin were successfully set.
<something_else> Any error result from dns_rbtnodechain_current.

Definition at line 3557 of file rbt.c.

References DNS_R_NEWORIGIN, dns_rbtnodechain_current(), dns_rbtnodechain_reset(), dns_rbtnodechain::end, ISC_R_SUCCESS, REQUIRE, dns_rbt::root, VALID_CHAIN, and VALID_RBT.

Referenced by cleanup_ring(), dbiterator_first(), dbiterator_next(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_rpz_ready(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), list_keynames(), and sync_keyzone().

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:

'chain' is a valid chain.
'rbt' is a valid rbt manager.

Ensures:

The chain points to the very last node of the tree.

'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current.

Returns:

DNS_R_NEWORIGIN The name & origin were successfully set.
ISC_R_NOMEMORY Resource Limit: Out of Memory building chain.
<something_else> Any error result from dns_name_concatenate.

Definition at line 3579 of file rbt.c.

References DNS_R_NEWORIGIN, dns_rbtnodechain_current(), dns_rbtnodechain_reset(), ISC_R_SUCCESS, move_chain_to_last(), REQUIRE, dns_rbt::root, VALID_CHAIN, and VALID_RBT.

Referenced by dbiterator_last(), dbiterator_prev(), and find_closest_nsec().

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:

'chain' is a valid chain.
'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:

The chain is pointed to the predecessor of its current target.

'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current.

'origin' is only if a new origin was found.

Returns:

ISC_R_SUCCESS The predecessor was found and 'name' was set.
DNS_R_NEWORIGIN The predecessor was found with a different origin and 'name' and 'origin' were set.
ISC_R_NOMORE There was no predecessor.
<something_else> Any error result from dns_rbtnodechain_current.

Definition at line 3218 of file rbt.c.

References ADD_LEVEL, DNS_R_NEWORIGIN, dns_rbtnodechain_current(), DOWN, dns_rbtnodechain::end, INSIST, IS_ROOT, ISC_FALSE, ISC_R_NOMORE, ISC_R_SUCCESS, ISC_TRUE, LEFT, dns_rbtnodechain::level_count, dns_rbtnodechain::levels, OFFSETLEN, PARENT, REQUIRE, RIGHT, and VALID_CHAIN.

Referenced by activeemtpynode(), dbiterator_prev(), dns_rbt_findnode(), find_coveringnsec(), and previous_closest_nsec().

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:

'chain' is a valid chain.
'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:

The chain is pointed to the successor of its current target.

'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current.

'origin' is only if a new origin was found.

Returns:

ISC_R_SUCCESS The successor was found and 'name' was set.
DNS_R_NEWORIGIN The successor was found with a different origin and 'name' and 'origin' were set.
ISC_R_NOMORE There was no successor.
<something_else> Any error result from dns_name_concatenate.

Definition at line 3442 of file rbt.c.

References ADD_LEVEL, chain_name(), DNS_R_NEWORIGIN, DOWN, dns_rbtnodechain::end, IS_ROOT, ISC_FALSE, ISC_R_NOMORE, ISC_R_SUCCESS, ISC_TRUE, LEFT, dns_rbtnodechain::level_count, dns_rbtnodechain::levels, NODENAME, OFFSETLEN, PARENT, REQUIRE, RIGHT, and VALID_CHAIN.

Referenced by activeempty(), activeemtpynode(), ATF_TC_BODY(), cleanup_ring(), dbiterator_next(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_rpz_ready(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), list_keynames(), and sync_keyzone().

isc_result_t dns_rbtnodechain_down	(	dns_rbtnodechain_t *	chain,
		dns_name_t *	name,
		dns_name_t *	origin
	)

Descend down if possible.

Definition at line 3335 of file rbt.c.

References ADD_LEVEL, chain_name(), DNS_R_NEWORIGIN, DOWN, dns_rbtnodechain::end, ISC_FALSE, ISC_R_NOMORE, ISC_R_SUCCESS, ISC_TRUE, LEFT, dns_rbtnodechain::level_count, NODENAME, OFFSETLEN, REQUIRE, and VALID_CHAIN.

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.

Definition at line 3399 of file rbt.c.

References dns_rbtnodechain::end, IS_ROOT, ISC_R_NOMORE, ISC_R_SUCCESS, LEFT, NODENAME, PARENT, REQUIRE, RIGHT, and VALID_CHAIN.

void dns_rbtnode_nodename	(	dns_rbtnode_t *	node,
		dns_name_t *	name
	)

Definition at line 288 of file rbt.c.

References dns_name::attributes, ATTRS, DNS_NAMEATTR_READONLY, dns_name::labels, dns_name::length, NAME, NAMELEN, dns_name::ndata, OFFSETLEN, OFFSETS, and dns_name::offsets.

Referenced by checkandaddsoa().

dns_rbtnode_t* dns_rbt_root ( dns_rbt_t * rbt )

Definition at line 298 of file rbt.c.

References dns_rbt::root.

rbt.h File Reference

Data Structures

Defines

Typedefs

Enumerations

Functions

Detailed Description

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation


Data Structures
struct	dns_rbtnode
struct	dns_rbtnodechain
Defines
#define	DNS_RBT_H 1
#define	DNS_RBT_USEHASH 1
#define	DNS_RBT_USEMAGIC 1
#define	DNS_RBT_LOCKLENGTH 10
#define	DNS_RBT_REFLENGTH 20
#define	DNS_RBTNODE_MAGIC ISC_MAGIC('R','B','N','O')
#define	DNS_RBTNODE_VALID(n) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC)
#define	DNS_RBT_LEVELBLOCK 254
	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_rbtnode_refinit(node, n) ((node)->references = (n))
#define	dns_rbtnode_refdestroy(node) REQUIRE((node)->references == 0)
#define	dns_rbtnode_refcurrent(node) ((node)->references)
#define	dns_rbtnode_refincrement0(node, refs)
#define	dns_rbtnode_refincrement(node, refs)
#define	dns_rbtnode_refdecrement(node, refs)

#define	DNS_RBTFIND_NOOPTIONS 0x00
	Option values for dns_rbt_findnode() and dns_rbt_findname(). These are used to form a bitmask.
#define	DNS_RBTFIND_EMPTYDATA 0x01
	Option values for dns_rbt_findnode() and dns_rbt_findname(). These are used to form a bitmask.
#define	DNS_RBTFIND_NOEXACT 0x02
	Option values for dns_rbt_findnode() and dns_rbt_findname(). These are used to form a bitmask.
#define	DNS_RBTFIND_NOPREDECESSOR 0x04
	Option values for dns_rbt_findnode() and dns_rbt_findname(). These are used to form a bitmask.
Typedefs
typedef struct dns_rbtnode	dns_rbtnode_t
	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 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, isc_uint64_t crc)
typedef isc_result_t(*	dns_rbtdatafixer_t )(dns_rbtnode_t rbtnode, void base, size_t offset, void arg, isc_uint64_t crc)
typedef void(*	dns_rbtdeleter_t )(void , void )
typedef struct dns_rbtnodechain	dns_rbtnodechain_t
Enumerations
enum	{ DNS_RBT_NSEC_NORMAL = 0, DNS_RBT_NSEC_HAS_NSEC = 1, DNS_RBT_NSEC_NSEC = 2, DNS_RBT_NSEC_NSEC3 = 3 }
Functions
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.
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'.
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.
isc_result_t	dns_rbt_findname (dns_rbt_t rbt, dns_name_t name, unsigned int options, dns_name_t foundname, void *data)
	Get the data pointer associated with 'name'.
isc_result_t	dns_rbt_findnode (dns_rbt_t rbt, 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'.
isc_result_t	dns_rbt_deletename (dns_rbt_t rbt, dns_name_t name, isc_boolean_t recurse)
	Delete 'name' from the tree of trees.
isc_result_t	dns_rbt_deletenode (dns_rbt_t rbt, dns_rbtnode_t node, isc_boolean_t recurse)
	Delete 'node' from the tree of trees.
void	dns_rbt_namefromnode (dns_rbtnode_t node, dns_name_t name)
	Convert the sequence of labels stored at 'node' into a 'name'.
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.
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().
unsigned int	dns_rbt_nodecount (dns_rbt_t *rbt)
	Obtain the number of nodes in the tree of trees.
unsigned int	dns_rbt_hashsize (dns_rbt_t *rbt)
	Obtain the current number of buckets in the 'rbt' hash table.
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.
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.
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.
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.
void	dns_rbt_printdot (dns_rbt_t rbt, isc_boolean_t show_pointers, FILE f)
	Print a GraphViz dot representation of the internal structure of the red-black tree of trees to the passed stream.
void	dns_rbt_printnodeinfo (dns_rbtnode_t n, FILE f)
	Print out various information about a node.
size_t	dns__rbt_getheight (dns_rbt_t *rbt)
	Return the maximum height of sub-root nodes found in the red-black forest.
isc_boolean_t	dns__rbt_checkproperties (dns_rbt_t *rbt)
	Check red-black properties of the forest.
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.
void	dns_rbtnodechain_init (dns_rbtnodechain_t chain, isc_mem_t mctx)
	Initialize 'chain'.
void	dns_rbtnodechain_reset (dns_rbtnodechain_t *chain)
	Free any dynamic storage associated with 'chain', and then reinitialize 'chain'.
void	dns_rbtnodechain_invalidate (dns_rbtnodechain_t *chain)
	Free any dynamic storage associated with 'chain', and then invalidates it.
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.
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.
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.
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.
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.
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.
void	dns_rbtnode_nodename (dns_rbtnode_t node, dns_name_t name)
dns_rbtnode_t *	dns_rbt_root (dns_rbt_t *rbt)