#include <config.h>
#include <isc/mem.h>
#include <isc/platform.h>
#include <isc/print.h>
#include <isc/refcount.h>
#include <isc/string.h>
#include <isc/util.h>
#define DNS_NAME_USEINLINE 1
#include <dns/fixedname.h>
#include <dns/log.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)
#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
#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;
};
#define RED 0
#define BLACK 1
#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 OLDNAMELEN(node) ((node)->oldnamelen)
#define OFFSETLEN(node) ((node)->offsetlen)
#define ATTRS(node) ((node)->attributes)
#define IS_ROOT(node) ISC_TF((node)->is_root == 1)
#define FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)
#define DIRTY(node) ((node)->dirty)
#define WILD(node) ((node)->wild)
#define LOCKNUM(node) ((node)->locknum)
#define NAME(node) ((unsigned char *)((node) + 1))
#define OFFSETS(node) (NAME(node) + OLDNAMELEN(node) + 1)
#define OLDOFFSETLEN(node) (OFFSETS(node)[-1])
#define NODE_SIZE(node) (sizeof(*node) + \
OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)
#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)
#define ADD_LEVEL(chain, node) \
(chain)->levels[(chain)->level_count++] = (node)
#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
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;
for (root = node; ! IS_ROOT(root); root = PARENT(root))
;
return (PARENT(root));
}
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, dns_name_t *name);
static inline void
unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
#else
#define hash_node(rbt, node, name) (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, unsigned int quantum,
dns_rbtnode_t **nodep);
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->magic = RBT_MAGIC;
*rbtp = rbt;
return (ISC_R_SUCCESS);
}
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;
dns_rbt_deletetreeflat(rbt, quantum, &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 {
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);
}
isc_result_t
dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
dns_rbtnode_t **root, *parent, *child, *current, *new_current;
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));
REQUIRE(dns_name_isabsolute(name));
REQUIRE(nodep != NULL && *nodep == NULL);
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, name);
}
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(¤t_name, current_offsets);
dns_fixedname_init(&fnewname);
new_name = dns_fixedname_name(&fnewname);
nlabels = dns_name_countlabels(name);
hlabels = 0;
do {
current = child;
NODENAME(current, ¤t_name);
compared = dns_name_fullcompare(add_name, ¤t_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 {
hlabels += common_labels;
if (compared == dns_namereln_subdomain) {
dns_name_split(add_name, common_labels,
add_name, NULL);
root = &DOWN(current);
INSIST(*root == NULL ||
(IS_ROOT(*root) &&
PARENT(*root) == current));
parent = NULL;
child = DOWN(current);
ADD_LEVEL(&chain, current);
} else {
INSIST(compared == dns_namereln_commonancestor
|| compared == dns_namereln_contains);
if (chain.level_count ==
(sizeof(chain.levels) /
sizeof(*chain.levels))) {
result = ISC_R_NOSPACE;
break;
}
dns_name_split(¤t_name, common_labels,
prefix, suffix);
result = create_node(rbt->mctx, suffix,
&new_current);
if (result != ISC_R_SUCCESS)
break;
new_current->is_root = current->is_root;
if (current->nsec == DNS_RBT_NSEC_HAS_NSEC)
new_current->nsec = DNS_RBT_NSEC_NORMAL;
else
new_current->nsec = current->nsec;
PARENT(new_current) = PARENT(current);
LEFT(new_current) = LEFT(current);
RIGHT(new_current) = RIGHT(current);
COLOR(new_current) = COLOR(current);
if (parent != NULL) {
if (LEFT(parent) == current)
LEFT(parent) = new_current;
else
RIGHT(parent) = new_current;
}
if (LEFT(new_current) != NULL)
PARENT(LEFT(new_current)) =
new_current;
if (RIGHT(new_current) != NULL)
PARENT(RIGHT(new_current)) =
new_current;
if (*root == current)
*root = new_current;
NAMELEN(current) = prefix->length;
OFFSETLEN(current) = prefix->labels;
current->is_root = 1;
PARENT(current) = new_current;
DOWN(new_current) = current;
root = &DOWN(new_current);
ADD_LEVEL(&chain, new_current);
LEFT(current) = NULL;
RIGHT(current) = NULL;
MAKE_BLACK(current);
ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
rbt->nodecount++;
dns_name_getlabelsequence(name,
nlabels - hlabels,
hlabels, new_name);
hash_node(rbt, new_current, new_name);
if (common_labels ==
dns_name_countlabels(add_name)) {
*nodep = new_current;
return (ISC_R_SUCCESS);
} else {
dns_name_split(add_name, common_labels,
add_name, NULL);
break;
}
}
}
} while (child != NULL);
if (result == ISC_R_SUCCESS)
result = create_node(rbt->mctx, add_name, &new_current);
if (result == ISC_R_SUCCESS) {
dns_rbt_addonlevel(new_current, current, order, root);
rbt->nodecount++;
*nodep = new_current;
hash_node(rbt, new_current, name);
}
return (result);
}
isc_result_t
dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
isc_result_t result;
dns_rbtnode_t *node;
REQUIRE(VALID_RBT(rbt));
REQUIRE(dns_name_isabsolute(name));
node = NULL;
result = dns_rbt_addnode(rbt, name, &node);
if (result == ISC_R_SUCCESS ||
(result == ISC_R_EXISTS && DATA(node) == NULL)) {
DATA(node) = data;
result = ISC_R_SUCCESS;
}
return (result);
}
isc_result_t
dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
unsigned int options, dns_rbtfindcallback_t callback,
void *callback_arg)
{
dns_rbtnode_t *current, *last_compared, *current_root;
dns_rbtnodechain_t localchain;
dns_name_t *search_name, current_name, *callback_name;
dns_fixedname_t fixedcallbackname, fixedsearchname;
dns_namereln_t compared;
isc_result_t result, saved_result;
unsigned int common_labels;
unsigned int hlabels = 0;
int order;
REQUIRE(VALID_RBT(rbt));
REQUIRE(dns_name_isabsolute(name));
REQUIRE(node != NULL && *node == NULL);
REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
!= (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
if (chain == NULL) {
options |= DNS_RBTFIND_NOPREDECESSOR;
chain = &localchain;
dns_rbtnodechain_init(chain, rbt->mctx);
} else
dns_rbtnodechain_reset(chain);
if (rbt->root == NULL)
return (ISC_R_NOTFOUND);
else {
compared = dns_namereln_none;
last_compared = NULL;
order = 0;
}
dns_fixedname_init(&fixedcallbackname);
callback_name = dns_fixedname_name(&fixedcallbackname);
dns_fixedname_init(&fixedsearchname);
search_name = dns_fixedname_name(&fixedsearchname);
dns_name_clone(name, search_name);
dns_name_init(¤t_name, NULL);
saved_result = ISC_R_SUCCESS;
current = rbt->root;
current_root = rbt->root;
while (current != NULL) {
NODENAME(current, ¤t_name);
compared = dns_name_fullcompare(search_name, ¤t_name,
&order, &common_labels);
last_compared = current;
if (compared == dns_namereln_equal)
break;
if (compared == dns_namereln_none) {
#ifdef DNS_RBT_USEHASH
dns_name_t hash_name;
dns_rbtnode_t *hnode;
dns_rbtnode_t *up_current;
unsigned int nlabels;
unsigned int tlabels = 1;
unsigned int hash;
if (rbt->hashtable == NULL)
goto nohash;
INSIST(current == current_root);
nlabels = dns_name_countlabels(search_name);
up_current = PARENT(current_root);
dns_name_init(&hash_name, NULL);
hashagain:
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);
for (hnode = rbt->hashtable[hash % rbt->hashsize];
hnode != NULL;
hnode = hnode->hashnext)
{
dns_name_t hnode_name;
if (hash != HASHVAL(hnode))
continue;
if (find_up(hnode) != up_current)
continue;
dns_name_init(&hnode_name, NULL);
NODENAME(hnode, &hnode_name);
if (dns_name_equal(&hnode_name, &hash_name))
break;
}
if (hnode != NULL) {
current = hnode;
if (tlabels == nlabels) {
compared = dns_namereln_equal;
break;
} else {
common_labels = tlabels;
compared = dns_namereln_subdomain;
goto subdomain;
}
}
if (tlabels++ < nlabels)
goto hashagain;
current = NULL;
continue;
nohash:
#endif
if (order < 0)
current = LEFT(current);
else
current = RIGHT(current);
} else {
if (compared == dns_namereln_subdomain) {
subdomain:
dns_name_split(search_name, common_labels,
search_name, NULL);
hlabels += common_labels;
if (DATA(current) != NULL ||
(options & DNS_RBTFIND_EMPTYDATA) != 0)
*node = current;
ADD_LEVEL(chain, current);
if (callback != NULL &&
FINDCALLBACK(current)) {
result = chain_name(chain,
callback_name,
ISC_FALSE);
if (result != ISC_R_SUCCESS) {
dns_rbtnodechain_reset(chain);
return (result);
}
result = (callback)(current,
callback_name,
callback_arg);
if (result != DNS_R_CONTINUE) {
saved_result = result;
current = NULL;
break;
}
}
current = DOWN(current);
current_root = current;
} else {
INSIST(compared == dns_namereln_commonancestor
|| compared == dns_namereln_contains);
current = NULL;
}
}
}
if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
(DATA(current) != NULL ||
(options & DNS_RBTFIND_EMPTYDATA) != 0)) {
chain->end = current;
chain->level_matches = chain->level_count;
if (foundname != NULL)
result = chain_name(chain, foundname, ISC_TRUE);
else
result = ISC_R_SUCCESS;
if (result == ISC_R_SUCCESS) {
*node = current;
result = saved_result;
} else
*node = NULL;
} else {
if (*node != NULL) {
chain->level_matches = chain->level_count - 1;
while (chain->levels[chain->level_matches] != *node) {
INSIST(chain->level_matches > 0);
chain->level_matches--;
}
if (foundname != NULL) {
unsigned int saved_count = chain->level_count;
chain->level_count = chain->level_matches + 1;
result = chain_name(chain, foundname,
ISC_FALSE);
chain->level_count = saved_count;
} else
result = ISC_R_SUCCESS;
if (result == ISC_R_SUCCESS)
result = DNS_R_PARTIALMATCH;
} else
result = ISC_R_NOTFOUND;
if (current != NULL) {
INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
DATA(current) == NULL));
chain->end = current;
} else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
chain->end = NULL;
} else {
if (compared == dns_namereln_subdomain) {
INSIST(chain->level_count > 0);
INSIST(chain->level_matches <
chain->level_count);
chain->end =
chain->levels[--chain->level_count];
} else {
isc_result_t result2;
if (compared == dns_namereln_none)
current = last_compared;
else
current = NULL;
while (current != NULL) {
NODENAME(current, ¤t_name);
compared = dns_name_fullcompare(
search_name,
¤t_name,
&order,
&common_labels);
POST(compared);
last_compared = current;
if (order < 0)
current = LEFT(current);
else
current = RIGHT(current);
}
current = last_compared;
if (order > 0) {
if (DOWN(current) != NULL) {
ADD_LEVEL(chain, current);
result2 =
move_chain_to_last(chain,
DOWN(current));
if (result2 != ISC_R_SUCCESS)
result = result2;
} else
chain->end = current;
} else {
INSIST(order < 0);
chain->end = current;
result2 = dns_rbtnodechain_prev(chain,
NULL,
NULL);
if (result2 == ISC_R_SUCCESS ||
result2 == DNS_R_NEWORIGIN)
;
else if (result2 == ISC_R_NOMORE)
dns_rbtnodechain_reset(chain);
else
result = result2;
}
}
}
}
ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
return (result);
}
isc_result_t
dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
dns_name_t *foundname, void **data) {
dns_rbtnode_t *node = NULL;
isc_result_t result;
REQUIRE(data != NULL && *data == NULL);
result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
options, NULL, NULL);
if (node != NULL &&
(DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
*data = DATA(node);
else
result = ISC_R_NOTFOUND;
return (result);
}
isc_result_t
dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse) {
dns_rbtnode_t *node = NULL;
isc_result_t result;
REQUIRE(VALID_RBT(rbt));
REQUIRE(dns_name_isabsolute(name));
result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
DNS_RBTFIND_NOOPTIONS, NULL, NULL);
if (result == ISC_R_SUCCESS) {
if (DATA(node) != NULL)
result = dns_rbt_deletenode(rbt, node, recurse);
else
result = ISC_R_NOTFOUND;
} else if (result == DNS_R_PARTIALMATCH)
result = ISC_R_NOTFOUND;
return (result);
}
isc_result_t
dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
{
dns_rbtnode_t *parent;
REQUIRE(VALID_RBT(rbt));
REQUIRE(DNS_RBTNODE_VALID(node));
if (DOWN(node) != NULL) {
if (recurse)
RUNTIME_CHECK(dns_rbt_deletetree(rbt, DOWN(node))
== ISC_R_SUCCESS);
else {
if (DATA(node) != NULL && rbt->data_deleter != NULL)
rbt->data_deleter(DATA(node), rbt->deleter_arg);
DATA(node) = NULL;
return (ISC_R_SUCCESS);
}
}
parent = find_up(node);
dns_rbt_deletefromlevel(node, parent == NULL ? &rbt->root :
&DOWN(parent));
if (DATA(node) != NULL && rbt->data_deleter != NULL)
rbt->data_deleter(DATA(node), rbt->deleter_arg);
unhash_node(rbt, node);
#if DNS_RBT_USEMAGIC
node->magic = 0;
#endif
dns_rbtnode_refdestroy(node);
isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
rbt->nodecount--;
return (ISC_R_SUCCESS);
}
void
dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
REQUIRE(DNS_RBTNODE_VALID(node));
REQUIRE(name != NULL);
REQUIRE(name->offsets == NULL);
NODENAME(node, name);
}
isc_result_t
dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
dns_name_t current;
isc_result_t result;
REQUIRE(DNS_RBTNODE_VALID(node));
REQUIRE(name != NULL);
REQUIRE(name->buffer != NULL);
dns_name_init(¤t, NULL);
dns_name_reset(name);
do {
INSIST(node != NULL);
NODENAME(node, ¤t);
result = dns_name_concatenate(name, ¤t, name, NULL);
if (result != ISC_R_SUCCESS)
break;
node = find_up(node);
} while (! dns_name_isabsolute(name));
return (result);
}
char *
dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
{
dns_fixedname_t fixedname;
dns_name_t *name;
isc_result_t result;
REQUIRE(DNS_RBTNODE_VALID(node));
REQUIRE(printname != NULL);
dns_fixedname_init(&fixedname);
name = dns_fixedname_name(&fixedname);
result = dns_rbt_fullnamefromnode(node, name);
if (result == ISC_R_SUCCESS)
dns_name_format(name, printname, size);
else
snprintf(printname, size, "<error building name: %s>",
dns_result_totext(result));
return (printname);
}
static isc_result_t
create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep) {
dns_rbtnode_t *node;
isc_region_t region;
unsigned int labels;
REQUIRE(name->offsets != NULL);
dns_name_toregion(name, ®ion);
labels = dns_name_countlabels(name);
ENSURE(labels > 0);
node = (dns_rbtnode_t *)isc_mem_get(mctx, sizeof(*node) +
region.length + labels + 1);
if (node == NULL)
return (ISC_R_NOMEMORY);
node->is_root = 0;
PARENT(node) = NULL;
RIGHT(node) = NULL;
LEFT(node) = NULL;
DOWN(node) = NULL;
DATA(node) = NULL;
#ifdef DNS_RBT_USEHASH
HASHNEXT(node) = NULL;
HASHVAL(node) = 0;
#endif
ISC_LINK_INIT(node, deadlink);
LOCKNUM(node) = 0;
WILD(node) = 0;
DIRTY(node) = 0;
dns_rbtnode_refinit(node, 0);
node->find_callback = 0;
node->nsec = DNS_RBT_NSEC_NORMAL;
MAKE_BLACK(node);
OLDNAMELEN(node) = NAMELEN(node) = region.length;
OLDOFFSETLEN(node) = OFFSETLEN(node) = labels;
ATTRS(node) = name->attributes;
memcpy(NAME(node), region.base, region.length);
memcpy(OFFSETS(node), name->offsets, labels);
#if DNS_RBT_USEMAGIC
node->magic = DNS_RBTNODE_MAGIC;
#endif
*nodep = node;
return (ISC_R_SUCCESS);
}
#ifdef DNS_RBT_USEHASH
static inline void
hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
unsigned int hash;
HASHVAL(node) = dns_name_fullhash(name, ISC_FALSE);
hash = HASHVAL(node) % rbt->hashsize;
HASHNEXT(node) = rbt->hashtable[hash];
rbt->hashtable[hash] = node;
}
static isc_result_t
inithash(dns_rbt_t *rbt) {
unsigned int bytes;
rbt->hashsize = RBT_HASH_SIZE;
bytes = rbt->hashsize * sizeof(dns_rbtnode_t *);
rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
if (rbt->hashtable == NULL)
return (ISC_R_NOMEMORY);
memset(rbt->hashtable, 0, bytes);
return (ISC_R_SUCCESS);
}
static void
rehash(dns_rbt_t *rbt) {
unsigned int oldsize;
dns_rbtnode_t **oldtable;
dns_rbtnode_t *node;
unsigned int hash;
unsigned int i;
oldsize = rbt->hashsize;
oldtable = rbt->hashtable;
rbt->hashsize = rbt->hashsize * 2 + 1;
rbt->hashtable = isc_mem_get(rbt->mctx,
rbt->hashsize * sizeof(dns_rbtnode_t *));
if (rbt->hashtable == NULL) {
rbt->hashtable = oldtable;
rbt->hashsize = oldsize;
return;
}
for (i = 0; i < rbt->hashsize; i++)
rbt->hashtable[i] = NULL;
for (i = 0; i < oldsize; i++) {
node = oldtable[i];
while (node != NULL) {
hash = HASHVAL(node) % rbt->hashsize;
oldtable[i] = HASHNEXT(node);
HASHNEXT(node) = rbt->hashtable[hash];
rbt->hashtable[hash] = node;
node = oldtable[i];
}
}
isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
}
static inline void
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, name);
}
static inline void
unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
unsigned int bucket;
dns_rbtnode_t *bucket_node;
REQUIRE(DNS_RBTNODE_VALID(node));
if (rbt->hashtable != NULL) {
bucket = HASHVAL(node) % rbt->hashsize;
bucket_node = rbt->hashtable[bucket];
if (bucket_node == node)
rbt->hashtable[bucket] = HASHNEXT(node);
else {
while (HASHNEXT(bucket_node) != node) {
INSIST(HASHNEXT(bucket_node) != NULL);
bucket_node = HASHNEXT(bucket_node);
}
HASHNEXT(bucket_node) = HASHNEXT(node);
}
}
}
#endif
static inline void
rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
dns_rbtnode_t *child;
REQUIRE(DNS_RBTNODE_VALID(node));
REQUIRE(rootp != NULL);
child = RIGHT(node);
INSIST(child != NULL);
RIGHT(node) = LEFT(child);
if (LEFT(child) != NULL)
PARENT(LEFT(child)) = node;
LEFT(child) = node;
if (child != NULL)
PARENT(child) = PARENT(node);
if (IS_ROOT(node)) {
*rootp = child;
child->is_root = 1;
node->is_root = 0;
} else {
if (LEFT(PARENT(node)) == node)
LEFT(PARENT(node)) = child;
else
RIGHT(PARENT(node)) = child;
}
PARENT(node) = child;
}
static inline void
rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
dns_rbtnode_t *child;
REQUIRE(DNS_RBTNODE_VALID(node));
REQUIRE(rootp != NULL);
child = LEFT(node);
INSIST(child != NULL);
LEFT(node) = RIGHT(child);
if (RIGHT(child) != NULL)
PARENT(RIGHT(child)) = node;
RIGHT(child) = node;
if (child != NULL)
PARENT(child) = PARENT(node);
if (IS_ROOT(node)) {
*rootp = child;
child->is_root = 1;
node->is_root = 0;
} else {
if (LEFT(PARENT(node)) == node)
LEFT(PARENT(node)) = child;
else
RIGHT(PARENT(node)) = child;
}
PARENT(node) = child;
}
static void
dns_rbt_addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
dns_rbtnode_t **rootp)
{
dns_rbtnode_t *child, *root, *parent, *grandparent;
dns_name_t add_name, current_name;
dns_offsets_t add_offsets, current_offsets;
REQUIRE(rootp != NULL);
REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
RIGHT(node) == NULL);
REQUIRE(current != NULL);
root = *rootp;
if (root == NULL) {
MAKE_BLACK(node);
node->is_root = 1;
PARENT(node) = current;
*rootp = node;
return;
}
child = root;
POST(child);
dns_name_init(&add_name, add_offsets);
NODENAME(node, &add_name);
dns_name_init(¤t_name, current_offsets);
NODENAME(current, ¤t_name);
if (order < 0) {
INSIST(LEFT(current) == NULL);
LEFT(current) = node;
} else {
INSIST(RIGHT(current) == NULL);
RIGHT(current) = node;
}
INSIST(PARENT(node) == NULL);
PARENT(node) = current;
MAKE_RED(node);
while (node != root && IS_RED(PARENT(node))) {
parent = PARENT(node);
grandparent = PARENT(parent);
if (parent == LEFT(grandparent)) {
child = RIGHT(grandparent);
if (child != NULL && IS_RED(child)) {
MAKE_BLACK(parent);
MAKE_BLACK(child);
MAKE_RED(grandparent);
node = grandparent;
} else {
if (node == RIGHT(parent)) {
rotate_left(parent, &root);
node = parent;
parent = PARENT(node);
grandparent = PARENT(parent);
}
MAKE_BLACK(parent);
MAKE_RED(grandparent);
rotate_right(grandparent, &root);
}
} else {
child = LEFT(grandparent);
if (child != NULL && IS_RED(child)) {
MAKE_BLACK(parent);
MAKE_BLACK(child);
MAKE_RED(grandparent);
node = grandparent;
} else {
if (node == LEFT(parent)) {
rotate_right(parent, &root);
node = parent;
parent = PARENT(node);
grandparent = PARENT(parent);
}
MAKE_BLACK(parent);
MAKE_RED(grandparent);
rotate_left(grandparent, &root);
}
}
}
MAKE_BLACK(root);
ENSURE(IS_ROOT(root));
*rootp = root;
return;
}
static void
dns_rbt_deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp) {
dns_rbtnode_t *child, *sibling, *parent;
dns_rbtnode_t *successor;
REQUIRE(delete != NULL);
INSIST((IS_ROOT(delete) && *rootp == delete) ||
(! IS_ROOT(delete) &&
(LEFT(PARENT(delete)) == delete ||
RIGHT(PARENT(delete)) == delete)));
child = NULL;
if (LEFT(delete) == NULL) {
if (RIGHT(delete) == NULL) {
if (IS_ROOT(delete)) {
*rootp = NULL;
return;
}
} else
child = RIGHT(delete);
} else if (RIGHT(delete) == NULL)
child = LEFT(delete);
else {
dns_rbtnode_t holder, *tmp = &holder;
successor = RIGHT(delete);
while (LEFT(successor) != NULL)
successor = LEFT(successor);
if (RIGHT(successor) != NULL)
child = RIGHT(successor);
memcpy(tmp, successor, sizeof(dns_rbtnode_t));
if (IS_ROOT(delete)) {
*rootp = successor;
successor->is_root = ISC_TRUE;
delete->is_root = ISC_FALSE;
} else
if (LEFT(PARENT(delete)) == delete)
LEFT(PARENT(delete)) = successor;
else
RIGHT(PARENT(delete)) = successor;
PARENT(successor) = PARENT(delete);
LEFT(successor) = LEFT(delete);
RIGHT(successor) = RIGHT(delete);
COLOR(successor) = COLOR(delete);
if (LEFT(successor) != NULL)
PARENT(LEFT(successor)) = successor;
if (RIGHT(successor) != successor)
PARENT(RIGHT(successor)) = successor;
INSIST(! IS_ROOT(delete));
if (PARENT(tmp) == delete) {
RIGHT(successor) = delete;
PARENT(delete) = successor;
} else {
LEFT(PARENT(tmp)) = delete;
PARENT(delete) = PARENT(tmp);
}
LEFT(delete) = NULL;
RIGHT(delete) = RIGHT(tmp);
COLOR(delete) = COLOR(tmp);
}
if (! IS_ROOT(delete)) {
if (LEFT(PARENT(delete)) == delete)
LEFT(PARENT(delete)) = child;
else
RIGHT(PARENT(delete)) = child;
if (child != NULL)
PARENT(child) = PARENT(delete);
} else {
*rootp = child;
child->is_root = 1;
PARENT(child) = PARENT(delete);
}
if (IS_BLACK(delete)) {
parent = PARENT(delete);
while (child != *rootp && IS_BLACK(child)) {
INSIST(child == NULL || ! IS_ROOT(child));
if (LEFT(parent) == child) {
sibling = RIGHT(parent);
if (IS_RED(sibling)) {
MAKE_BLACK(sibling);
MAKE_RED(parent);
rotate_left(parent, rootp);
sibling = RIGHT(parent);
}
if (IS_BLACK(LEFT(sibling)) &&
IS_BLACK(RIGHT(sibling))) {
MAKE_RED(sibling);
child = parent;
} else {
if (IS_BLACK(RIGHT(sibling))) {
MAKE_BLACK(LEFT(sibling));
MAKE_RED(sibling);
rotate_right(sibling, rootp);
sibling = RIGHT(parent);
}
COLOR(sibling) = COLOR(parent);
MAKE_BLACK(parent);
MAKE_BLACK(RIGHT(sibling));
rotate_left(parent, rootp);
child = *rootp;
}
} else {
sibling = LEFT(parent);
if (IS_RED(sibling)) {
MAKE_BLACK(sibling);
MAKE_RED(parent);
rotate_right(parent, rootp);
sibling = LEFT(parent);
}
if (IS_BLACK(LEFT(sibling)) &&
IS_BLACK(RIGHT(sibling))) {
MAKE_RED(sibling);
child = parent;
} else {
if (IS_BLACK(LEFT(sibling))) {
MAKE_BLACK(RIGHT(sibling));
MAKE_RED(sibling);
rotate_left(sibling, rootp);
sibling = LEFT(parent);
}
COLOR(sibling) = COLOR(parent);
MAKE_BLACK(parent);
MAKE_BLACK(LEFT(sibling));
rotate_right(parent, rootp);
child = *rootp;
}
}
parent = PARENT(child);
}
if (IS_RED(child))
MAKE_BLACK(child);
}
}
static isc_result_t
dns_rbt_deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) {
isc_result_t result = ISC_R_SUCCESS;
REQUIRE(VALID_RBT(rbt));
if (node == NULL)
return (result);
if (LEFT(node) != NULL) {
result = dns_rbt_deletetree(rbt, LEFT(node));
if (result != ISC_R_SUCCESS)
goto done;
LEFT(node) = NULL;
}
if (RIGHT(node) != NULL) {
result = dns_rbt_deletetree(rbt, RIGHT(node));
if (result != ISC_R_SUCCESS)
goto done;
RIGHT(node) = NULL;
}
if (DOWN(node) != NULL) {
result = dns_rbt_deletetree(rbt, DOWN(node));
if (result != ISC_R_SUCCESS)
goto done;
DOWN(node) = NULL;
}
done:
if (result != ISC_R_SUCCESS)
return (result);
if (DATA(node) != NULL && rbt->data_deleter != NULL)
rbt->data_deleter(DATA(node), rbt->deleter_arg);
unhash_node(rbt, node);
#if DNS_RBT_USEMAGIC
node->magic = 0;
#endif
isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
rbt->nodecount--;
return (result);
}
static void
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));
again:
if (node == NULL) {
*nodep = NULL;
return;
}
traverse:
if (LEFT(node) != NULL) {
node = LEFT(node);
goto traverse;
}
if (DOWN(node) != NULL) {
node = DOWN(node);
goto traverse;
}
if (DATA(node) != NULL && rbt->data_deleter != NULL)
rbt->data_deleter(DATA(node), rbt->deleter_arg);
#if DNS_RBT_USEMAGIC
node->magic = 0;
#endif
parent = PARENT(node);
if (RIGHT(node) != NULL)
PARENT(RIGHT(node)) = parent;
if (parent != NULL) {
if (LEFT(parent) == node)
LEFT(parent) = RIGHT(node);
else if (DOWN(parent) == node)
DOWN(parent) = RIGHT(node);
} else
parent = RIGHT(node);
isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
rbt->nodecount--;
node = parent;
if (quantum != 0 && --quantum == 0) {
*nodep = node;
return;
}
goto again;
}
static void
dns_rbt_indent(int depth) {
int i;
for (i = 0; i < depth; i++)
putchar('\t');
}
static void
dns_rbt_printnodename(dns_rbtnode_t *node) {
isc_region_t r;
dns_name_t name;
char buffer[DNS_NAME_FORMATSIZE];
dns_offsets_t offsets;
r.length = NAMELEN(node);
r.base = NAME(node);
dns_name_init(&name, offsets);
dns_name_fromregion(&name, &r);
dns_name_format(&name, buffer, sizeof(buffer));
printf("%s", buffer);
}
static void
dns_rbt_printtree(dns_rbtnode_t *root, dns_rbtnode_t *parent, int depth) {
dns_rbt_indent(depth);
if (root != NULL) {
dns_rbt_printnodename(root);
printf(" (%s", IS_RED(root) ? "RED" : "black");
if (parent) {
printf(" from ");
dns_rbt_printnodename(parent);
}
if ((! IS_ROOT(root) && PARENT(root) != parent) ||
( IS_ROOT(root) && depth > 0 &&
DOWN(PARENT(root)) != root)) {
printf(" (BAD parent pointer! -> ");
if (PARENT(root) != NULL)
dns_rbt_printnodename(PARENT(root));
else
printf("NULL");
printf(")");
}
printf(")\n");
depth++;
if (DOWN(root)) {
dns_rbt_indent(depth);
printf("++ BEG down from ");
dns_rbt_printnodename(root);
printf("\n");
dns_rbt_printtree(DOWN(root), NULL, depth);
dns_rbt_indent(depth);
printf("-- END down from ");
dns_rbt_printnodename(root);
printf("\n");
}
if (IS_RED(root) && IS_RED(LEFT(root)))
printf("** Red/Red color violation on left\n");
dns_rbt_printtree(LEFT(root), root, depth);
if (IS_RED(root) && IS_RED(RIGHT(root)))
printf("** Red/Red color violation on right\n");
dns_rbt_printtree(RIGHT(root), root, depth);
} else
printf("NULL\n");
}
void
dns_rbt_printall(dns_rbt_t *rbt) {
REQUIRE(VALID_RBT(rbt));
dns_rbt_printtree(rbt->root, NULL, 0);
}
void
dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
REQUIRE(chain != NULL);
chain->mctx = mctx;
chain->end = NULL;
chain->level_count = 0;
chain->level_matches = 0;
memset(chain->levels, 0, sizeof(chain->levels));
chain->magic = CHAIN_MAGIC;
}
isc_result_t
dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
dns_name_t *origin, dns_rbtnode_t **node)
{
isc_result_t result = ISC_R_SUCCESS;
REQUIRE(VALID_CHAIN(chain));
if (node != NULL)
*node = chain->end;
if (chain->end == NULL)
return (ISC_R_NOTFOUND);
if (name != NULL) {
NODENAME(chain->end, name);
if (chain->level_count == 0) {
INSIST(dns_name_isabsolute(name));
name->labels--;
name->length--;
name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
}
}
if (origin != NULL) {
if (chain->level_count > 0)
result = chain_name(chain, origin, ISC_FALSE);
else
result = dns_name_copy(dns_rootname, origin, NULL);
}
return (result);
}
isc_result_t
dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
dns_name_t *origin)
{
dns_rbtnode_t *current, *previous, *predecessor;
isc_result_t result = ISC_R_SUCCESS;
isc_boolean_t new_origin = ISC_FALSE;
REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
predecessor = NULL;
current = chain->end;
if (LEFT(current) != NULL) {
current = LEFT(current);
while (RIGHT(current) != NULL)
current = RIGHT(current);
predecessor = current;
} else {
while (! IS_ROOT(current)) {
previous = current;
current = PARENT(current);
if (RIGHT(current) == previous) {
predecessor = current;
break;
}
}
}
if (predecessor != NULL) {
if (DOWN(predecessor) != NULL) {
do {
ADD_LEVEL(chain, predecessor);
predecessor = DOWN(predecessor);
while (RIGHT(predecessor) != NULL)
predecessor = RIGHT(predecessor);
} while (DOWN(predecessor) != NULL);
if (origin != NULL)
new_origin = ISC_TRUE;
}
} else if (chain->level_count > 0) {
INSIST(chain->level_count > 0 && IS_ROOT(current));
predecessor = chain->levels[--chain->level_count];
if (origin != NULL &&
(chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
new_origin = ISC_TRUE;
}
if (predecessor != NULL) {
chain->end = predecessor;
if (new_origin) {
result = dns_rbtnodechain_current(chain, name, origin,
NULL);
if (result == ISC_R_SUCCESS)
result = DNS_R_NEWORIGIN;
} else
result = dns_rbtnodechain_current(chain, name, NULL,
NULL);
} else
result = ISC_R_NOMORE;
return (result);
}
isc_result_t
dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
dns_name_t *origin)
{
dns_rbtnode_t *current, *successor;
isc_result_t result = ISC_R_SUCCESS;
isc_boolean_t new_origin = ISC_FALSE;
REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
successor = NULL;
current = chain->end;
if (DOWN(current) != NULL) {
if (chain->level_count > 0 ||
OFFSETLEN(current) > 1)
new_origin = ISC_TRUE;
ADD_LEVEL(chain, current);
current = DOWN(current);
while (LEFT(current) != NULL)
current = LEFT(current);
successor = current;
}
if (successor != NULL) {
chain->end = successor;
if (name != NULL)
NODENAME(chain->end, name);
if (new_origin) {
if (origin != NULL)
result = chain_name(chain, origin, ISC_FALSE);
if (result == ISC_R_SUCCESS)
result = DNS_R_NEWORIGIN;
} else
result = ISC_R_SUCCESS;
} else
result = ISC_R_NOMORE;
return (result);
}
isc_result_t
dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name) {
dns_rbtnode_t *current, *previous, *successor;
isc_result_t result = ISC_R_SUCCESS;
REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
successor = NULL;
current = chain->end;
if (RIGHT(current) == NULL) {
while (! IS_ROOT(current)) {
previous = current;
current = PARENT(current);
if (LEFT(current) == previous) {
successor = current;
break;
}
}
} else {
current = RIGHT(current);
while (LEFT(current) != NULL)
current = LEFT(current);
successor = current;
}
if (successor != NULL) {
chain->end = successor;
if (name != NULL)
NODENAME(chain->end, name);
result = ISC_R_SUCCESS;
} else
result = ISC_R_NOMORE;
return (result);
}
isc_result_t
dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
dns_name_t *origin)
{
dns_rbtnode_t *current, *previous, *successor;
isc_result_t result = ISC_R_SUCCESS;
isc_boolean_t new_origin = ISC_FALSE;
REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
successor = NULL;
current = chain->end;
if (DOWN(current) != NULL) {
if (chain->level_count > 0 ||
OFFSETLEN(current) > 1)
new_origin = ISC_TRUE;
ADD_LEVEL(chain, current);
current = DOWN(current);
while (LEFT(current) != NULL)
current = LEFT(current);
successor = current;
} else if (RIGHT(current) == NULL) {
do {
while (! IS_ROOT(current)) {
previous = current;
current = PARENT(current);
if (LEFT(current) == previous) {
successor = current;
break;
}
}
if (successor == NULL) {
if (chain->level_count == 0)
break;
current = chain->levels[--chain->level_count];
new_origin = ISC_TRUE;
if (RIGHT(current) != NULL)
break;
}
} while (successor == NULL);
}
if (successor == NULL && RIGHT(current) != NULL) {
current = RIGHT(current);
while (LEFT(current) != NULL)
current = LEFT(current);
successor = current;
}
if (successor != NULL) {
chain->end = successor;
if (name != NULL)
NODENAME(chain->end, name);
if (new_origin) {
if (origin != NULL)
result = chain_name(chain, origin, ISC_FALSE);
if (result == ISC_R_SUCCESS)
result = DNS_R_NEWORIGIN;
} else
result = ISC_R_SUCCESS;
} else
result = ISC_R_NOMORE;
return (result);
}
isc_result_t
dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
dns_name_t *name, dns_name_t *origin)
{
isc_result_t result;
REQUIRE(VALID_RBT(rbt));
REQUIRE(VALID_CHAIN(chain));
dns_rbtnodechain_reset(chain);
chain->end = rbt->root;
result = dns_rbtnodechain_current(chain, name, origin, NULL);
if (result == ISC_R_SUCCESS)
result = DNS_R_NEWORIGIN;
return (result);
}
isc_result_t
dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
dns_name_t *name, dns_name_t *origin)
{
isc_result_t result;
REQUIRE(VALID_RBT(rbt));
REQUIRE(VALID_CHAIN(chain));
dns_rbtnodechain_reset(chain);
result = move_chain_to_last(chain, rbt->root);
if (result != ISC_R_SUCCESS)
return (result);
result = dns_rbtnodechain_current(chain, name, origin, NULL);
if (result == ISC_R_SUCCESS)
result = DNS_R_NEWORIGIN;
return (result);
}
void
dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
REQUIRE(VALID_CHAIN(chain));
chain->end = NULL;
chain->level_count = 0;
chain->level_matches = 0;
}
void
dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
dns_rbtnodechain_reset(chain);
chain->magic = 0;
}