summaryrefslogtreecommitdiffstats
path: root/contrib/bind9/lib/dns/rbt.c
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/bind9/lib/dns/rbt.c')
-rw-r--r--contrib/bind9/lib/dns/rbt.c81
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(&current_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;
}
OpenPOWER on IntegriCloud