Lines Matching defs:rbt
41 #include <dns/rbt.h>
45 #define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
96 * used as part of the rbt.c algorithms.
157 inithash(dns_rbt_t *rbt);
203 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
205 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
207 #define hash_node(rbt, node, name) (ISC_R_SUCCESS)
208 #define unhash_node(rbt, node)
224 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);
227 dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum,
240 dns_rbt_t *rbt;
247 rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
248 if (rbt == NULL)
251 rbt->mctx = mctx;
252 rbt->data_deleter = deleter;
253 rbt->deleter_arg = deleter_arg;
254 rbt->root = NULL;
255 rbt->nodecount = 0;
256 rbt->hashtable = NULL;
257 rbt->hashsize = 0;
260 result = inithash(rbt);
262 isc_mem_put(mctx, rbt, sizeof(*rbt));
267 rbt->magic = RBT_MAGIC;
269 *rbtp = rbt;
284 dns_rbt_t *rbt;
288 rbt = *rbtp;
290 dns_rbt_deletetreeflat(rbt, quantum, &rbt->root);
291 if (rbt->root != NULL)
294 INSIST(rbt->nodecount == 0);
296 if (rbt->hashtable != NULL)
297 isc_mem_put(rbt->mctx, rbt->hashtable,
298 rbt->hashsize * sizeof(dns_rbtnode_t *));
300 rbt->magic = 0;
302 isc_mem_put(rbt->mctx, rbt, sizeof(*rbt));
308 dns_rbt_nodecount(dns_rbt_t *rbt) {
309 REQUIRE(VALID_RBT(rbt));
310 return (rbt->nodecount);
368 dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
383 REQUIRE(VALID_RBT(rbt));
395 if (rbt->root == NULL) {
396 result = create_node(rbt->mctx, add_name, &new_current);
398 rbt->nodecount++;
400 rbt->root = new_current;
402 hash_node(rbt, new_current, name);
407 dns_rbtnodechain_init(&chain, rbt->mctx);
414 root = &rbt->root;
529 result = create_node(rbt->mctx, suffix,
585 rbt->nodecount++;
589 hash_node(rbt, new_current, new_name);
630 result = create_node(rbt->mctx, add_name, &new_current);
634 rbt->nodecount++;
636 hash_node(rbt, new_current, name);
646 dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
650 REQUIRE(VALID_RBT(rbt));
655 result = dns_rbt_addnode(rbt, name, &node);
676 dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
691 REQUIRE(VALID_RBT(rbt));
705 dns_rbtnodechain_init(chain, rbt->mctx);
709 if (rbt->root == NULL)
738 current = rbt->root;
739 current_root = rbt->root;
762 if (rbt->hashtable == NULL)
797 for (hnode = rbt->hashtable[hash % rbt->hashsize];
1179 dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
1186 result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
1202 dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse) {
1206 REQUIRE(VALID_RBT(rbt));
1223 result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
1228 result = dns_rbt_deletenode(rbt, node, recurse);
1275 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
1279 REQUIRE(VALID_RBT(rbt));
1284 RUNTIME_CHECK(dns_rbt_deletetree(rbt, DOWN(node))
1287 if (DATA(node) != NULL && rbt->data_deleter != NULL)
1288 rbt->data_deleter(DATA(node), rbt->deleter_arg);
1315 dns_rbt_deletefromlevel(node, parent == NULL ? &rbt->root :
1318 if (DATA(node) != NULL && rbt->data_deleter != NULL)
1319 rbt->data_deleter(DATA(node), rbt->deleter_arg);
1321 unhash_node(rbt, node);
1326 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
1327 rbt->nodecount--;
1491 hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
1496 hash = HASHVAL(node) % rbt->hashsize;
1497 HASHNEXT(node) = rbt->hashtable[hash];
1499 rbt->hashtable[hash] = node;
1503 inithash(dns_rbt_t *rbt) {
1506 rbt->hashsize = RBT_HASH_SIZE;
1507 bytes = rbt->hashsize * sizeof(dns_rbtnode_t *);
1508 rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
1510 if (rbt->hashtable == NULL)
1513 memset(rbt->hashtable, 0, bytes);
1519 rehash(dns_rbt_t *rbt) {
1526 oldsize = rbt->hashsize;
1527 oldtable = rbt->hashtable;
1528 rbt->hashsize = rbt->hashsize * 2 + 1;
1529 rbt->hashtable = isc_mem_get(rbt->mctx,
1530 rbt->hashsize * sizeof(dns_rbtnode_t *));
1531 if (rbt->hashtable == NULL) {
1532 rbt->hashtable = oldtable;
1533 rbt->hashsize = oldsize;
1537 INSIST(rbt->hashsize > 0);
1539 for (i = 0; i < rbt->hashsize; i++)
1540 rbt->hashtable[i] = NULL;
1545 hash = HASHVAL(node) % rbt->hashsize;
1547 HASHNEXT(node) = rbt->hashtable[hash];
1548 rbt->hashtable[hash] = node;
1553 isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
1557 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
1561 if (rbt->nodecount >= (rbt->hashsize *3))
1562 rehash(rbt);
1564 hash_add_node(rbt, node, name);
1568 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
1574 if (rbt->hashtable != NULL) {
1575 bucket = HASHVAL(node) % rbt->hashsize;
1576 bucket_node = rbt->hashtable[bucket];
1579 rbt->hashtable[bucket] = HASHNEXT(node);
2018 dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) {
2020 REQUIRE(VALID_RBT(rbt));
2026 result = dns_rbt_deletetree(rbt, LEFT(node));
2032 result = dns_rbt_deletetree(rbt, RIGHT(node));
2038 result = dns_rbt_deletetree(rbt, DOWN(node));
2047 if (DATA(node) != NULL && rbt->data_deleter != NULL)
2048 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2050 unhash_node(rbt, node);
2055 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2056 rbt->nodecount--;
2061 dns_rbt_deletetreeflat(dns_rbt_t *rbt, unsigned int quantum,
2066 REQUIRE(VALID_RBT(rbt));
2084 if (DATA(node) != NULL && rbt->data_deleter != NULL)
2085 rbt->data_deleter(DATA(node), rbt->deleter_arg);
2089 * the complete rbt tree.
2105 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2106 rbt->nodecount--;
2195 dns_rbt_printall(dns_rbt_t *rbt) {
2196 REQUIRE(VALID_RBT(rbt));
2198 dns_rbt_printtree(rbt->root, NULL, 0);
2605 dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2611 REQUIRE(VALID_RBT(rbt));
2616 chain->end = rbt->root;
2627 dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
2633 REQUIRE(VALID_RBT(rbt));
2638 result = move_chain_to_last(chain, rbt->root);