[apple/network_cmds.git] / unbound / util / storage / dnstree.c

/*
 * util/storage/dnstree.c - support for rbtree types suitable for DNS code.
 *
 * Copyright (c) 2008, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 *
 * This file contains structures combining types and functions to
 * manipulate those structures that help building DNS lookup trees.
 */
#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);
                /* sort order like: ::/0, 1::/2, 1::/4, ... 2::/2 */
                /* find the previous, or parent-parent-parent */
                for(p = prev; p; p = p->parent)
                        if(p->net <= m) {
                                /* ==: since prev matched m, this is closest*/
                                /* <: prev matches more, but is not a parent,
				 * this one is a (grand)parent */
                                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); /* we know prev is smaller */
		/* sort order like: . com. bla.com. zwb.com. net. */
                /* find the previous, or parent-parent-parent */
                for(p = prev; p; p = p->parent)
                        if(p->labs <= m) {
                                /* ==: since prev matched m, this is closest*/
                                /* <: prev matches more, but is not a parent,
				 * this one is a (grand)parent */
                                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)) {
                /* exact */
                result = (struct name_tree_node*)res;
        } else {
                /* smaller element (or no element) */
                int m;
                result = (struct name_tree_node*)res;
                if(!result || result->dclass != dclass)
                        return NULL;
                /* count number of labels matched */
                (void)dname_lab_cmp(result->name, result->labs, key.name,
                        key.labs, &m);
                while(result) { /* go up until qname is subdomain of stub */
                        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)) {
                /* exact */
                return (struct addr_tree_node*)res;
        } else {
                /* smaller element (or no element) */
                int m;
                result = (struct addr_tree_node*)res;
                if(!result || result->addrlen != addrlen)
                        return 0;
                /* count number of bits matched */
                m = addr_in_common(&result->addr, result->net, addr,
                        key.net, addrlen);
                while(result) { /* go up until addr is inside netblock */
                        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) {
		/* first root item is first item in tree */
		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;
		}
		/* root not first item? search for higher items */
		*dclass = p->dclass + 1;
		return name_tree_next_root(tree, dclass);
	}
	/* find class n in tree, we may get a direct hit, or if we don't
	 * this is the last item of the previous class so rbtree_next() takes
	 * us to the next root (if any) */
	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)) {
		/* exact */
		return 1;
	} else {
		/* smaller element */
		if(!n || n == RBTREE_NULL)
			return 0; /* nothing found */
		n = rbtree_next(n);
		if(n == RBTREE_NULL)
			return 0; /* no higher */
		p = (struct name_tree_node*)n;
		if(dname_is_root(p->name)) {
			*dclass = p->dclass;
			return 1;
		}
		/* not a root node, return next higher item */
		*dclass = p->dclass+1;
		return name_tree_next_root(tree, dclass);
	}
}
Commit	Line	Data
89c4ed63 A	1	/*
	2	* util/storage/dnstree.c - support for rbtree types suitable for DNS code.
	3	*
	4	* Copyright (c) 2008, NLnet Labs. All rights reserved.
	5	*
	6	* This software is open source.
	7	*
	8	* Redistribution and use in source and binary forms, with or without
	9	* modification, are permitted provided that the following conditions
	10	* are met:
	11	*
	12	* Redistributions of source code must retain the above copyright notice,
	13	* this list of conditions and the following disclaimer.
	14	*
	15	* Redistributions in binary form must reproduce the above copyright notice,
	16	* this list of conditions and the following disclaimer in the documentation
	17	* and/or other materials provided with the distribution.
	18	*
	19	* Neither the name of the NLNET LABS nor the names of its contributors may
	20	* be used to endorse or promote products derived from this software without
	21	* specific prior written permission.
	22	*
	23	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	24	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	25	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	26	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	27	* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	28	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
	29	* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	30	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
	31	* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
	32	* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
	33	* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	34	*/
	35
	36	/**
	37	* \file
	38	*
	39	* This file contains structures combining types and functions to
	40	* manipulate those structures that help building DNS lookup trees.
	41	*/
	42	#include "config.h"
	43	#include "util/storage/dnstree.h"
	44	#include "util/data/dname.h"
	45	#include "util/net_help.h"
	46
	47	int name_tree_compare(const void* k1, const void* k2)
	48	{
	49	struct name_tree_node* x = (struct name_tree_node*)k1;
	50	struct name_tree_node* y = (struct name_tree_node*)k2;
	51	int m;
	52	if(x->dclass != y->dclass) {
	53	if(x->dclass < y->dclass)
	54	return -1;
	55	return 1;
	56	}
	57	return dname_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
	58	}
	59
	60	int addr_tree_compare(const void* k1, const void* k2)
	61	{
	62	struct addr_tree_node* n1 = (struct addr_tree_node*)k1;
	63	struct addr_tree_node* n2 = (struct addr_tree_node*)k2;
	64	int r = sockaddr_cmp_addr(&n1->addr, n1->addrlen, &n2->addr,
65	n2->addrlen);
66	if(r != 0) return r;
67	if(n1->net < n2->net)
68	return -1;
69	if(n1->net > n2->net)
70	return 1;
71	return 0;
72	}
73
74	void name_tree_init(rbtree_t* tree)
75	{
76	rbtree_init(tree, &name_tree_compare);
77	}
78
79	void addr_tree_init(rbtree_t* tree)
80	{
81	rbtree_init(tree, &addr_tree_compare);
82	}
83
84	int name_tree_insert(rbtree_t* tree, struct name_tree_node* node,
85	uint8_t* name, size_t len, int labs, uint16_t dclass)
86	{
87	node->node.key = node;
88	node->name = name;
89	node->len = len;
90	node->labs = labs;
91	node->dclass = dclass;
92	node->parent = NULL;
93	return rbtree_insert(tree, &node->node) != NULL;
94	}
95
96	int addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node,
97	struct sockaddr_storage* addr, socklen_t addrlen, int net)
98	{
99	node->node.key = node;
100	memcpy(&node->addr, addr, addrlen);
101	node->addrlen = addrlen;
102	node->net = net;
103	node->parent = NULL;
104	return rbtree_insert(tree, &node->node) != NULL;
105	}
106
107	void addr_tree_init_parents(rbtree_t* tree)
108	{
109	struct addr_tree_node* node, prev = NULL, p;
110	int m;
111	RBTREE_FOR(node, struct addr_tree_node*, tree) {
112	node->parent = NULL;
113	if(!prev \|\| prev->addrlen != node->addrlen) {
114	prev = node;
115	continue;
116	}
117	m = addr_in_common(&prev->addr, prev->net, &node->addr,
118	node->net, node->addrlen);
119	/* sort order like: ::/0, 1::/2, 1::/4, ... 2::/2 */
120	/* find the previous, or parent-parent-parent */
121	for(p = prev; p; p = p->parent)
122	if(p->net <= m) {
123	/* ==: since prev matched m, this is closest*/
124	/* <: prev matches more, but is not a parent,
125	* this one is a (grand)parent */
126	node->parent = p;
127	break;
128	}
129	prev = node;
130	}
131	}
132
133	void name_tree_init_parents(rbtree_t* tree)
134	{
135	struct name_tree_node* node, prev = NULL, p;
136	int m;
137	RBTREE_FOR(node, struct name_tree_node*, tree) {
138	node->parent = NULL;
139	if(!prev \|\| prev->dclass != node->dclass) {
140	prev = node;
141	continue;
142	}
143	(void)dname_lab_cmp(prev->name, prev->labs, node->name,
144	node->labs, &m); /* we know prev is smaller */
145	/* sort order like: . com. bla.com. zwb.com. net. */
146	/* find the previous, or parent-parent-parent */
147	for(p = prev; p; p = p->parent)
148	if(p->labs <= m) {
149	/* ==: since prev matched m, this is closest*/
150	/* <: prev matches more, but is not a parent,
151	* this one is a (grand)parent */
152	node->parent = p;
153	break;
154	}
155	prev = node;
156	}
157	}
158
159	struct name_tree_node* name_tree_find(rbtree_t* tree, uint8_t* name,
160	size_t len, int labs, uint16_t dclass)
161	{
162	struct name_tree_node key;
163	key.node.key = &key;
164	key.name = name;
165	key.len = len;
166	key.labs = labs;
167	key.dclass = dclass;
168	return (struct name_tree_node*)rbtree_search(tree, &key);
169	}
170
171	struct name_tree_node* name_tree_lookup(rbtree_t* tree, uint8_t* name,
172	size_t len, int labs, uint16_t dclass)
173	{
174	rbnode_t* res = NULL;
175	struct name_tree_node *result;
176	struct name_tree_node key;
177	key.node.key = &key;
178	key.name = name;
179	key.len = len;
180	key.labs = labs;
181	key.dclass = dclass;
182	if(rbtree_find_less_equal(tree, &key, &res)) {
183	/* exact */
184	result = (struct name_tree_node*)res;
185	} else {
186	/* smaller element (or no element) */
187	int m;
188	result = (struct name_tree_node*)res;
189	if(!result \|\| result->dclass != dclass)
190	return NULL;
191	/* count number of labels matched */
192	(void)dname_lab_cmp(result->name, result->labs, key.name,
193	key.labs, &m);
194	while(result) { /* go up until qname is subdomain of stub */
195	if(result->labs <= m)
196	break;
197	result = result->parent;
198	}
199	}
200	return result;
201	}
202
203	struct addr_tree_node* addr_tree_lookup(rbtree_t* tree,
204	struct sockaddr_storage* addr, socklen_t addrlen)
205	{
206	rbnode_t* res = NULL;
207	struct addr_tree_node* result;
208	struct addr_tree_node key;
209	key.node.key = &key;
210	memcpy(&key.addr, addr, addrlen);
211	key.addrlen = addrlen;
212	key.net = (addr_is_ip6(addr, addrlen)?128:32);
213	if(rbtree_find_less_equal(tree, &key, &res)) {
214	/* exact */
215	return (struct addr_tree_node*)res;
216	} else {
217	/* smaller element (or no element) */
218	int m;
219	result = (struct addr_tree_node*)res;
220	if(!result \|\| result->addrlen != addrlen)
221	return 0;
222	/* count number of bits matched */
223	m = addr_in_common(&result->addr, result->net, addr,
224	key.net, addrlen);
225	while(result) { /* go up until addr is inside netblock */
226	if(result->net <= m)
227	break;
228	result = result->parent;
229	}
230	}
231	return result;
232	}
233
234	int
235	name_tree_next_root(rbtree_t* tree, uint16_t* dclass)
236	{
237	struct name_tree_node key;
238	rbnode_t* n;
239	struct name_tree_node* p;
240	if(*dclass == 0) {
241	/* first root item is first item in tree */
242	n = rbtree_first(tree);
243	if(n == RBTREE_NULL)
244	return 0;
245	p = (struct name_tree_node*)n;
246	if(dname_is_root(p->name)) {
247	*dclass = p->dclass;
248	return 1;
249	}
250	/* root not first item? search for higher items */
251	*dclass = p->dclass + 1;
252	return name_tree_next_root(tree, dclass);
253	}
254	/* find class n in tree, we may get a direct hit, or if we don't
255	* this is the last item of the previous class so rbtree_next() takes
256	* us to the next root (if any) */
257	key.node.key = &key;
258	key.name = (uint8_t*)"\000";
259	key.len = 1;
260	key.labs = 0;
261	key.dclass = *dclass;
262	n = NULL;
263	if(rbtree_find_less_equal(tree, &key, &n)) {
264	/* exact */
265	return 1;
266	} else {
267	/* smaller element */
268	if(!n \|\| n == RBTREE_NULL)
269	return 0; /* nothing found */
270	n = rbtree_next(n);
271	if(n == RBTREE_NULL)
272	return 0; /* no higher */
273	p = (struct name_tree_node*)n;
274	if(dname_is_root(p->name)) {
275	*dclass = p->dclass;
276	return 1;
277	}
278	/* not a root node, return next higher item */
279	*dclass = p->dclass+1;
280	return name_tree_next_root(tree, dclass);
281	}
282	}