rbt.h

非常好的dns解析软件

 *\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, 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, 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 arrising 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 mutally
 *		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, isc_boolean_t recurse);
/*%<
 * Delete 'name' from the tree of trees.
 *
 * Notes:
 *\li	When 'name' is removed, if recurse is ISC_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, isc_boolean_t recurse);
/*%<
 * Delete 'node' from the tree of trees.
 *
 * Notes:
 *\li	When 'node' is removed, if recurse is ISC_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 whem
 *		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.
 */