rbt.c

bind 9.3结合mysql数据库

/*
 * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
 * Copyright (C) 1999-2003  Internet Software Consortium.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

/* $Id: rbt.c,v 1.115.2.2.2.9 2004/03/08 21:06:27 marka Exp $ */

/* Principal Authors: DCL */

#include <config.h>

#include <isc/mem.h>
#include <isc/platform.h>
#include <isc/print.h>
#include <isc/string.h>
#include <isc/util.h>

/*
 * This define is so dns/name.h (included by dns/fixedname.h) uses more
 * efficient macro calls instead of functions for a few operations.
 */
#define DNS_NAME_USEINLINE 1

#include <dns/fixedname.h>
#include <dns/rbt.h>
#include <dns/result.h>

#define RBT_MAGIC		ISC_MAGIC('R', 'B', 'T', '+')
#define VALID_RBT(rbt)		ISC_MAGIC_VALID(rbt, RBT_MAGIC)

/*
 * XXXDCL Since parent pointers were added in again, I could remove all of the
 * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
 * _lastnode.  This would involve pretty major change to the API.
 */
#define CHAIN_MAGIC		ISC_MAGIC('0', '-', '0', '-')
#define VALID_CHAIN(chain)	ISC_MAGIC_VALID(chain, CHAIN_MAGIC)

#define RBT_HASH_SIZE		64

#ifdef RBT_MEM_TEST
#undef RBT_HASH_SIZE
#define RBT_HASH_SIZE 2	/* To give the reallocation code a workout. */
#endif

struct dns_rbt {
	unsigned int		magic;
	isc_mem_t *		mctx;
	dns_rbtnode_t *		root;
	void			(*data_deleter)(void *, void *);
	void *			deleter_arg;
	unsigned int		nodecount;
	unsigned int		hashsize;
	dns_rbtnode_t **	hashtable;
	unsigned int		quantum;
};

#define RED 0
#define BLACK 1

/*
 * Elements of the rbtnode structure.
 */
#define PARENT(node)		((node)->parent)
#define LEFT(node)	 	((node)->left)
#define RIGHT(node)		((node)->right)
#define DOWN(node)		((node)->down)
#define DATA(node)		((node)->data)
#define HASHNEXT(node)		((node)->hashnext)
#define HASHVAL(node)		((node)->hashval)
#define COLOR(node) 		((node)->color)
#define NAMELEN(node)		((node)->namelen)
#define OFFSETLEN(node)		((node)->offsetlen)
#define ATTRS(node)		((node)->attributes)
#define PADBYTES(node)		((node)->padbytes)
#define IS_ROOT(node)		ISC_TF((node)->is_root == 1)
#define FINDCALLBACK(node)	ISC_TF((node)->find_callback == 1)

/*
 * Structure elements from the rbtdb.c, not
 * used as part of the rbt.c algorithms.
 */
#define DIRTY(node)	((node)->dirty)
#define WILD(node)	((node)->wild)
#define LOCKNUM(node)	((node)->locknum)
#define REFS(node)	((node)->references)

/*
 * The variable length stuff stored after the node.
 */
#define NAME(node)	((unsigned char *)((node) + 1))
#define OFFSETS(node)	(NAME(node) + NAMELEN(node))

#define NODE_SIZE(node)	(sizeof(*node) + \
			 NAMELEN(node) + OFFSETLEN(node) + PADBYTES(node))

/*
 * Color management.
 */
#define IS_RED(node)		((node) != NULL && (node)->color == RED)
#define IS_BLACK(node)		((node) == NULL || (node)->color == BLACK)
#define MAKE_RED(node)		((node)->color = RED)
#define MAKE_BLACK(node)	((node)->color = BLACK)

/*
 * Chain management.
 *
 * The "ancestors" member of chains were removed, with their job now
 * being wholy handled by parent pointers (which didn't exist, because
 * of memory concerns, when chains were first implemented).
 */
#define ADD_LEVEL(chain, node) \
			(chain)->levels[(chain)->level_count++] = (node)

/*
 * The following macros directly access normally private name variables.
 * These macros are used to avoid a lot of function calls in the critical
 * path of the tree traversal code.
 */

#define NODENAME(node, name) \
do { \
	(name)->length = NAMELEN(node); \
	(name)->labels = OFFSETLEN(node); \
	(name)->ndata = NAME(node); \
	(name)->offsets = OFFSETS(node); \
	(name)->attributes = ATTRS(node); \
	(name)->attributes |= DNS_NAMEATTR_READONLY; \
} while (0)

#ifdef DNS_RBT_USEHASH
static isc_result_t
inithash(dns_rbt_t *rbt);
#endif

#ifdef DEBUG
#define inline
/*
 * A little something to help out in GDB.
 */
dns_name_t Name(dns_rbtnode_t *node);
dns_name_t
Name(dns_rbtnode_t *node) {
	dns_name_t name;

	dns_name_init(&name, NULL);
	if (node != NULL)
		NODENAME(node, &name);

	return (name);
}

static void dns_rbt_printnodename(dns_rbtnode_t *node);
#endif

static inline dns_rbtnode_t *
find_up(dns_rbtnode_t *node) {
	dns_rbtnode_t *root;

	/*
	 * Return the node in the level above the argument node that points
	 * to the level the argument node is in.  If the argument node is in
	 * the top level, the return value is NULL.
	 */
	for (root = node; ! IS_ROOT(root); root = PARENT(root))
		; /* Nothing. */

	return (PARENT(root));
}

#ifdef DNS_RBT_USEHASH
static inline void
compute_node_hash(dns_rbtnode_t *node) {
	unsigned int hash;
	dns_name_t name;
	dns_rbtnode_t *up_node;

	dns_name_init(&name, NULL);
	NODENAME(node, &name);
	hash = dns_name_hashbylabel(&name, ISC_FALSE);

	up_node = find_up(node);
	if (up_node != NULL)
		hash += HASHVAL(up_node);

	HASHVAL(node) = hash;
}
#endif

/*
 * Forward declarations.
 */
static isc_result_t
create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);

#ifdef DNS_RBT_USEHASH
static inline void
hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
static inline void
unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
#else
#define hash_node(rbt, node) (ISC_R_SUCCESS)
#define unhash_node(rbt, node)
#endif

static inline void
rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
static inline void
rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);

static void
dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order, 
		   dns_rbtnode_t **rootp);

static void
dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);

static isc_result_t
dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);

static void
dns_rbt_deletetreeflat(dns_rbt_t *rbt, dns_rbtnode_t **nodep);

/*
 * Initialize a red/black tree of trees.
 */
isc_result_t
dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
	       void *deleter_arg, dns_rbt_t **rbtp)
{
#ifdef DNS_RBT_USEHASH
	isc_result_t result;
#endif
	dns_rbt_t *rbt;
	

	REQUIRE(mctx != NULL);
	REQUIRE(rbtp != NULL && *rbtp == NULL);
	REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);

	rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
	if (rbt == NULL)
		return (ISC_R_NOMEMORY);

	rbt->mctx = mctx;
	rbt->data_deleter = deleter;
	rbt->deleter_arg = deleter_arg;
	rbt->root = NULL;
	rbt->nodecount = 0;
	rbt->hashtable = NULL;
	rbt->hashsize = 0;
#ifdef DNS_RBT_USEHASH
	result = inithash(rbt);
	if (result != ISC_R_SUCCESS) {
		isc_mem_put(mctx, rbt, sizeof(*rbt));
		return (result);
	}
#endif
	rbt->quantum = 0;
	rbt->magic = RBT_MAGIC;

	*rbtp = rbt;

	return (ISC_R_SUCCESS);
}

/*
 * Deallocate a red/black tree of trees.
 */
void
dns_rbt_destroy(dns_rbt_t **rbtp) {
	RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
}

isc_result_t
dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
	dns_rbt_t *rbt;

	REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));

	rbt = *rbtp;

	rbt->quantum = quantum;

	dns_rbt_deletetreeflat(rbt, &rbt->root);
	if (rbt->root != NULL)
		return (ISC_R_QUOTA);

	INSIST(rbt->nodecount == 0);

	if (rbt->hashtable != NULL)
		isc_mem_put(rbt->mctx, rbt->hashtable,
			    rbt->hashsize * sizeof(dns_rbtnode_t *));

	rbt->magic = 0;

	isc_mem_put(rbt->mctx, rbt, sizeof(*rbt));
	*rbtp = NULL;
	return (ISC_R_SUCCESS);
}

unsigned int
dns_rbt_nodecount(dns_rbt_t *rbt) {
	REQUIRE(VALID_RBT(rbt));
	return (rbt->nodecount);
}

static inline isc_result_t
chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
	   isc_boolean_t include_chain_end)
{
	dns_name_t nodename;
	isc_result_t result = ISC_R_SUCCESS;
	int i;

	dns_name_init(&nodename, NULL);

	if (include_chain_end && chain->end != NULL) {
		NODENAME(chain->end, &nodename);
		result = dns_name_copy(&nodename, name, NULL);
		if (result != ISC_R_SUCCESS)
			return (result);
	} else
		dns_name_reset(name);

	for (i = (int)chain->level_count - 1; i >= 0; i--) {
		NODENAME(chain->levels[i], &nodename);
		result = dns_name_concatenate(name, &nodename, name, NULL);

		if (result != ISC_R_SUCCESS)
			return (result);
	}
	return (result);
}

static inline isc_result_t
move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
	do {
		/*
		 * Go as far right and then down as much as possible,
		 * as long as the rightmost node has a down pointer.
		 */
		while (RIGHT(node) != NULL)
			node = RIGHT(node);

		if (DOWN(node) == NULL)
			break;

		ADD_LEVEL(chain, node);
		node = DOWN(node);
	} while (1);

	chain->end = node;

	return (ISC_R_SUCCESS);
}

/*
 * Add 'name' to tree, initializing its data pointer with 'data'.
 */

isc_result_t
dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
	/*
	 * Does this thing have too many variables or what?
	 */
	dns_rbtnode_t **root, *parent, *child, *current, *new_current;
	dns_name_t *add_name, current_name, *prefix, *suffix;
	dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix;
	dns_offsets_t current_offsets;
	dns_namereln_t compared;
	isc_result_t result = ISC_R_SUCCESS;
	dns_rbtnodechain_t chain;
	unsigned int common_labels;
	int order;

	REQUIRE(VALID_RBT(rbt));
	REQUIRE(dns_name_isabsolute(name));
	REQUIRE(nodep != NULL && *nodep == NULL);

	/*
	 * Create a copy of the name so the original name structure is
	 * not modified.
	 */
	dns_fixedname_init(&fixedcopy);
	add_name = dns_fixedname_name(&fixedcopy);
	dns_name_clone(name, add_name);

	if (rbt->root == NULL) {
		result = create_node(rbt->mctx, add_name, &new_current);
		if (result == ISC_R_SUCCESS) {
			rbt->nodecount++;
			new_current->is_root = 1;
			rbt->root = new_current;
			*nodep = new_current;
			hash_node(rbt, new_current);
		}
		return (result);
	}

	dns_rbtnodechain_init(&chain, rbt->mctx);

	dns_fixedname_init(&fixedprefix);
	dns_fixedname_init(&fixedsuffix);
	prefix = dns_fixedname_name(&fixedprefix);
	suffix = dns_fixedname_name(&fixedsuffix);

	root = &rbt->root;
	INSIST(IS_ROOT(*root));
	parent = NULL;
	current = NULL;
	child = *root;
	dns_name_init(&current_name, current_offsets);

	do {
		current = child;

		NODENAME(current, &current_name);
		compared = dns_name_fullcompare(add_name, &current_name,
						&order, &common_labels);

		if (compared == dns_namereln_equal) {
			*nodep = current;
			result = ISC_R_EXISTS;
			break;

		}

		if (compared == dns_namereln_none) {

			if (order < 0) {
				parent = current;
				child = LEFT(current);

			} else if (order > 0) {
				parent = current;
				child = RIGHT(current);

			}

		} else {
			/*
			 * This name has some suffix in common with the
			 * name at the current node.  If the name at
			 * the current node is shorter, that means the
			 * new name should be in a subtree.  If the
			 * name at the current node is longer, that means
			 * the down pointer to this tree should point
			 * to a new tree that has the common suffix, and
			 * the non-common parts of these two names should
			 * start a new tree.
			 */
			if (compared == dns_namereln_subdomain) {
				/*
				 * All of the existing labels are in common,
				 * so the new name is in a subtree.
				 * Whack off the common labels for the
				 * not-in-common part to be searched for
				 * in the next level.
				 */
				dns_name_split(add_name, common_labels,
					       add_name, NULL);

				/*
				 * Follow the down pointer (possibly NULL).
				 */
				root = &DOWN(current);

				INSIST(*root == NULL ||
				       (IS_ROOT(*root) &&
					PARENT(*root) == current));

				parent = NULL;
				child = DOWN(current);
				ADD_LEVEL(&chain, current);

			} else {
				/*
				 * The number of labels in common is fewer
				 * than the number of labels at the current
				 * node, so the current node must be adjusted
				 * to have just the common suffix, and a down
				 * pointer made to a new tree.
				 */

				INSIST(compared == dns_namereln_commonancestor
				       || compared == dns_namereln_contains);

				/*
				 * Ensure the number of levels in the tree
				 * does not exceed the number of logical
				 * levels allowed by DNSSEC.
				 *
				 * XXXDCL need a better error result?
				 *
				 * XXXDCL Since chain ancestors were removed,
				 * no longer used by dns_rbt_addonlevel(),