diff options
Diffstat (limited to 'contrib/bind9/lib/dns/rbt.c')
-rw-r--r-- | contrib/bind9/lib/dns/rbt.c | 81 |
1 files changed, 38 insertions, 43 deletions
diff --git a/contrib/bind9/lib/dns/rbt.c b/contrib/bind9/lib/dns/rbt.c index a3608f7..cb43858 100644 --- a/contrib/bind9/lib/dns/rbt.c +++ b/contrib/bind9/lib/dns/rbt.c @@ -15,7 +15,7 @@ * PERFORMANCE OF THIS SOFTWARE. */ -/* $Id: rbt.c,v 1.115.2.2.2.9 2004/03/08 21:06:27 marka Exp $ */ +/* $Id: rbt.c,v 1.115.2.2.2.11 2004/10/25 01:36:07 marka Exp $ */ /* Principal Authors: DCL */ @@ -64,7 +64,6 @@ struct dns_rbt { unsigned int nodecount; unsigned int hashsize; dns_rbtnode_t ** hashtable; - unsigned int quantum; }; #define RED 0 @@ -180,25 +179,6 @@ find_up(dns_rbtnode_t *node) { 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. */ @@ -207,11 +187,11 @@ 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); +hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name); static inline void unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node); #else -#define hash_node(rbt, node) (ISC_R_SUCCESS) +#define hash_node(rbt, node, name) (ISC_R_SUCCESS) #define unhash_node(rbt, node) #endif @@ -231,7 +211,8 @@ 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); +dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, + dns_rbtnode_t **nodep); /* * Initialize a red/black tree of trees. @@ -268,7 +249,6 @@ dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *), return (result); } #endif - rbt->quantum = 0; rbt->magic = RBT_MAGIC; *rbtp = rbt; @@ -292,9 +272,7 @@ dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) { rbt = *rbtp; - rbt->quantum = quantum; - - dns_rbt_deletetreeflat(rbt, &rbt->root); + dns_rbt_deletetreeflat(rbt, quantum, &rbt->root); if (rbt->root != NULL) return (ISC_R_QUOTA); @@ -377,13 +355,14 @@ 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_name_t *add_name, *new_name, current_name, *prefix, *suffix; + dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname; dns_offsets_t current_offsets; dns_namereln_t compared; isc_result_t result = ISC_R_SUCCESS; dns_rbtnodechain_t chain; unsigned int common_labels; + unsigned int nlabels, hlabels; int order; REQUIRE(VALID_RBT(rbt)); @@ -405,7 +384,7 @@ dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) { new_current->is_root = 1; rbt->root = new_current; *nodep = new_current; - hash_node(rbt, new_current); + hash_node(rbt, new_current, name); } return (result); } @@ -423,6 +402,10 @@ dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) { current = NULL; child = *root; dns_name_init(¤t_name, current_offsets); + dns_fixedname_init(&fnewname); + new_name = dns_fixedname_name(&fnewname); + nlabels = dns_name_countlabels(name); + hlabels = 0; do { current = child; @@ -462,6 +445,7 @@ dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) { * the non-common parts of these two names should * start a new tree. */ + hlabels += common_labels; if (compared == dns_namereln_subdomain) { /* * All of the existing labels are in common, @@ -588,7 +572,10 @@ dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) { ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE; rbt->nodecount++; - hash_node(rbt, new_current); + dns_name_getlabelsequence(name, + nlabels - hlabels, + hlabels, new_name); + hash_node(rbt, new_current, new_name); if (common_labels == dns_name_countlabels(add_name)) { @@ -635,7 +622,7 @@ dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) { dns_rbt_addonlevel(new_current, current, order, root); rbt->nodecount++; *nodep = new_current; - hash_node(rbt, new_current); + hash_node(rbt, new_current, name); } return (result); @@ -687,6 +674,7 @@ dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname, dns_namereln_t compared; isc_result_t result, saved_result; unsigned int common_labels; + unsigned int hlabels = 0; int order; REQUIRE(VALID_RBT(rbt)); @@ -782,11 +770,17 @@ dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname, dns_name_init(&hash_name, NULL); hashagain: + /* + * Hash includes tail. + */ + dns_name_getlabelsequence(name, + nlabels - tlabels, + hlabels + tlabels, + &hash_name); + hash = dns_name_fullhash(&hash_name, ISC_FALSE); dns_name_getlabelsequence(search_name, nlabels - tlabels, tlabels, &hash_name); - hash = HASHVAL(up_current) + - dns_name_hashbylabel(&hash_name, ISC_FALSE); for (hnode = rbt->hashtable[hash % rbt->hashsize]; hnode != NULL; @@ -863,6 +857,7 @@ dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname, */ dns_name_split(search_name, common_labels, search_name, NULL); + hlabels += common_labels; /* * This might be the closest enclosing name. */ @@ -1475,10 +1470,10 @@ create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep) { #ifdef DNS_RBT_USEHASH static inline void -hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node) { +hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) { unsigned int hash; - compute_node_hash(node); + HASHVAL(node) = dns_name_fullhash(name, ISC_FALSE); hash = HASHVAL(node) % rbt->hashsize; HASHNEXT(node) = rbt->hashtable[hash]; @@ -1539,14 +1534,14 @@ rehash(dns_rbt_t *rbt) { } static inline void -hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) { +hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) { REQUIRE(DNS_RBTNODE_VALID(node)); if (rbt->nodecount >= (rbt->hashsize *3)) rehash(rbt); - hash_add_node(rbt, node); + hash_add_node(rbt, node, name); } static inline void @@ -2021,8 +2016,6 @@ dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) { done: if (result != ISC_R_SUCCESS) return (result); - if (rbt->quantum != 0 && --rbt->quantum == 0) - return (ISC_R_QUOTA); if (DATA(node) != NULL && rbt->data_deleter != NULL) rbt->data_deleter(DATA(node), rbt->deleter_arg); @@ -2037,7 +2030,9 @@ dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) { } static void -dns_rbt_deletetreeflat(dns_rbt_t *rbt, dns_rbtnode_t **nodep) { +dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, + dns_rbtnode_t **nodep) +{ dns_rbtnode_t *parent; dns_rbtnode_t *node = *nodep; REQUIRE(VALID_RBT(rbt)); @@ -2081,7 +2076,7 @@ dns_rbt_deletetreeflat(dns_rbt_t *rbt, dns_rbtnode_t **nodep) { isc_mem_put(rbt->mctx, node, NODE_SIZE(node)); rbt->nodecount--; node = parent; - if (rbt->quantum != 0 && --rbt->quantum == 0) { + if (quantum != 0 && --quantum == 0) { *nodep = node; return; } |