rbt.h

非常好的dns解析软件

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

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

void
dns_rbt_printall(dns_rbt_t *rbt);
/*%<
 * Print an ASCII representation of the internal structure of the red-black
 * tree of trees.
 *
 * 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.
 */

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

/*
 * 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)	(REQUIRE((node)->references == 0))
#define dns_rbtnode_refcurrent(node)	((node)->references)
#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 {							\
		REQUIRE((node)->references > 0);		\
		(node)->references++;				\
		if ((refs) != NULL)				\
			(*refs) = (node)->references;		\
	} while (0) 
#define dns_rbtnode_refdecrement(node, refs)			\
	do {							\
		REQUIRE((node)->references > 0);		\
		(node)->references--;				\
		if ((refs) != NULL)				\
			(*refs) = (node)->references;		\
	} while (0) 
#endif /* DNS_RBT_USEISCREFCOUNT */

ISC_LANG_ENDDECLS

#endif /* DNS_RBT_H */