#include "config.h"
#include "util/storage/dnstree.h"
#include "util/data/dname.h"
#include "util/net_help.h"
int name_tree_compare(const void* k1, const void* k2)
{
struct name_tree_node* x = (struct name_tree_node*)k1;
struct name_tree_node* y = (struct name_tree_node*)k2;
int m;
if(x->dclass != y->dclass) {
if(x->dclass < y->dclass)
return -1;
return 1;
}
return dname_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
}
int addr_tree_compare(const void* k1, const void* k2)
{
struct addr_tree_node* n1 = (struct addr_tree_node*)k1;
struct addr_tree_node* n2 = (struct addr_tree_node*)k2;
int r = sockaddr_cmp_addr(&n1->addr, n1->addrlen, &n2->addr,
n2->addrlen);
if(r != 0) return r;
if(n1->net < n2->net)
return -1;
if(n1->net > n2->net)
return 1;
return 0;
}
void name_tree_init(rbtree_t* tree)
{
rbtree_init(tree, &name_tree_compare);
}
void addr_tree_init(rbtree_t* tree)
{
rbtree_init(tree, &addr_tree_compare);
}
int name_tree_insert(rbtree_t* tree, struct name_tree_node* node,
uint8_t* name, size_t len, int labs, uint16_t dclass)
{
node->node.key = node;
node->name = name;
node->len = len;
node->labs = labs;
node->dclass = dclass;
node->parent = NULL;
return rbtree_insert(tree, &node->node) != NULL;
}
int addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node,
struct sockaddr_storage* addr, socklen_t addrlen, int net)
{
node->node.key = node;
memcpy(&node->addr, addr, addrlen);
node->addrlen = addrlen;
node->net = net;
node->parent = NULL;
return rbtree_insert(tree, &node->node) != NULL;
}
void addr_tree_init_parents(rbtree_t* tree)
{
struct addr_tree_node* node, *prev = NULL, *p;
int m;
RBTREE_FOR(node, struct addr_tree_node*, tree) {
node->parent = NULL;
if(!prev || prev->addrlen != node->addrlen) {
prev = node;
continue;
}
m = addr_in_common(&prev->addr, prev->net, &node->addr,
node->net, node->addrlen);
for(p = prev; p; p = p->parent)
if(p->net <= m) {
node->parent = p;
break;
}
prev = node;
}
}
void name_tree_init_parents(rbtree_t* tree)
{
struct name_tree_node* node, *prev = NULL, *p;
int m;
RBTREE_FOR(node, struct name_tree_node*, tree) {
node->parent = NULL;
if(!prev || prev->dclass != node->dclass) {
prev = node;
continue;
}
(void)dname_lab_cmp(prev->name, prev->labs, node->name,
node->labs, &m);
for(p = prev; p; p = p->parent)
if(p->labs <= m) {
node->parent = p;
break;
}
prev = node;
}
}
struct name_tree_node* name_tree_find(rbtree_t* tree, uint8_t* name,
size_t len, int labs, uint16_t dclass)
{
struct name_tree_node key;
key.node.key = &key;
key.name = name;
key.len = len;
key.labs = labs;
key.dclass = dclass;
return (struct name_tree_node*)rbtree_search(tree, &key);
}
struct name_tree_node* name_tree_lookup(rbtree_t* tree, uint8_t* name,
size_t len, int labs, uint16_t dclass)
{
rbnode_t* res = NULL;
struct name_tree_node *result;
struct name_tree_node key;
key.node.key = &key;
key.name = name;
key.len = len;
key.labs = labs;
key.dclass = dclass;
if(rbtree_find_less_equal(tree, &key, &res)) {
result = (struct name_tree_node*)res;
} else {
int m;
result = (struct name_tree_node*)res;
if(!result || result->dclass != dclass)
return NULL;
(void)dname_lab_cmp(result->name, result->labs, key.name,
key.labs, &m);
while(result) {
if(result->labs <= m)
break;
result = result->parent;
}
}
return result;
}
struct addr_tree_node* addr_tree_lookup(rbtree_t* tree,
struct sockaddr_storage* addr, socklen_t addrlen)
{
rbnode_t* res = NULL;
struct addr_tree_node* result;
struct addr_tree_node key;
key.node.key = &key;
memcpy(&key.addr, addr, addrlen);
key.addrlen = addrlen;
key.net = (addr_is_ip6(addr, addrlen)?128:32);
if(rbtree_find_less_equal(tree, &key, &res)) {
return (struct addr_tree_node*)res;
} else {
int m;
result = (struct addr_tree_node*)res;
if(!result || result->addrlen != addrlen)
return 0;
m = addr_in_common(&result->addr, result->net, addr,
key.net, addrlen);
while(result) {
if(result->net <= m)
break;
result = result->parent;
}
}
return result;
}
int
name_tree_next_root(rbtree_t* tree, uint16_t* dclass)
{
struct name_tree_node key;
rbnode_t* n;
struct name_tree_node* p;
if(*dclass == 0) {
n = rbtree_first(tree);
if(n == RBTREE_NULL)
return 0;
p = (struct name_tree_node*)n;
if(dname_is_root(p->name)) {
*dclass = p->dclass;
return 1;
}
*dclass = p->dclass + 1;
return name_tree_next_root(tree, dclass);
}
key.node.key = &key;
key.name = (uint8_t*)"\000";
key.len = 1;
key.labs = 0;
key.dclass = *dclass;
n = NULL;
if(rbtree_find_less_equal(tree, &key, &n)) {
return 1;
} else {
if(!n || n == RBTREE_NULL)
return 0;
n = rbtree_next(n);
if(n == RBTREE_NULL)
return 0;
p = (struct name_tree_node*)n;
if(dname_is_root(p->name)) {
*dclass = p->dclass;
return 1;
}
*dclass = p->dclass+1;
return name_tree_next_root(tree, dclass);
}
}