2 * util/storage/dnstree.c - support for rbtree types suitable for DNS code.
4 * Copyright (c) 2008, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
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.
39 * This file contains structures combining types and functions to
40 * manipulate those structures that help building DNS lookup trees.
43 #include "util/storage/dnstree.h"
44 #include "util/data/dname.h"
45 #include "util/net_help.h"
47 int name_tree_compare(const void* k1, const void* k2)
49 struct name_tree_node* x = (struct name_tree_node*)k1;
50 struct name_tree_node* y = (struct name_tree_node*)k2;
52 if(x->dclass != y->dclass) {
53 if(x->dclass < y->dclass)
57 return dname_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
60 int addr_tree_compare(const void* k1, const void* k2)
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,
74 void name_tree_init(rbtree_type* tree)
76 rbtree_init(tree, &name_tree_compare);
79 void addr_tree_init(rbtree_type* tree)
81 rbtree_init(tree, &addr_tree_compare);
84 int name_tree_insert(rbtree_type* tree, struct name_tree_node* node,
85 uint8_t* name, size_t len, int labs, uint16_t dclass)
87 node->node.key = node;
91 node->dclass = dclass;
93 return rbtree_insert(tree, &node->node) != NULL;
96 int addr_tree_insert(rbtree_type* tree, struct addr_tree_node* node,
97 struct sockaddr_storage* addr, socklen_t addrlen, int net)
99 node->node.key = node;
100 memcpy(&node->addr, addr, addrlen);
101 node->addrlen = addrlen;
104 return rbtree_insert(tree, &node->node) != NULL;
107 void addr_tree_init_parents_node(struct addr_tree_node* node)
109 struct addr_tree_node* prev = NULL, *p;
111 for(; (rbnode_type*)node != RBTREE_NULL;
112 node = (struct addr_tree_node*)rbtree_next((rbnode_type*)node)) {
114 if(!prev || prev->addrlen != node->addrlen) {
118 m = addr_in_common(&prev->addr, prev->net, &node->addr,
119 node->net, node->addrlen);
120 /* sort order like: ::/0, 1::/2, 1::/4, ... 2::/2 */
121 /* find the previous, or parent-parent-parent */
122 for(p = prev; p; p = p->parent)
124 /* ==: since prev matched m, this is closest*/
125 /* <: prev matches more, but is not a parent,
126 * this one is a (grand)parent */
134 void addr_tree_init_parents(rbtree_type* tree)
136 addr_tree_init_parents_node(
137 (struct addr_tree_node*)rbtree_first(tree));
140 void name_tree_init_parents(rbtree_type* tree)
142 struct name_tree_node* node, *prev = NULL, *p;
144 RBTREE_FOR(node, struct name_tree_node*, tree) {
146 if(!prev || prev->dclass != node->dclass) {
150 (void)dname_lab_cmp(prev->name, prev->labs, node->name,
151 node->labs, &m); /* we know prev is smaller */
152 /* sort order like: . com. bla.com. zwb.com. net. */
153 /* find the previous, or parent-parent-parent */
154 for(p = prev; p; p = p->parent)
156 /* ==: since prev matched m, this is closest*/
157 /* <: prev matches more, but is not a parent,
158 * this one is a (grand)parent */
166 struct name_tree_node* name_tree_find(rbtree_type* tree, uint8_t* name,
167 size_t len, int labs, uint16_t dclass)
169 struct name_tree_node key;
175 return (struct name_tree_node*)rbtree_search(tree, &key);
178 struct name_tree_node* name_tree_lookup(rbtree_type* tree, uint8_t* name,
179 size_t len, int labs, uint16_t dclass)
181 rbnode_type* res = NULL;
182 struct name_tree_node *result;
183 struct name_tree_node key;
189 if(rbtree_find_less_equal(tree, &key, &res)) {
191 result = (struct name_tree_node*)res;
193 /* smaller element (or no element) */
195 result = (struct name_tree_node*)res;
196 if(!result || result->dclass != dclass)
198 /* count number of labels matched */
199 (void)dname_lab_cmp(result->name, result->labs, key.name,
201 while(result) { /* go up until qname is subdomain of stub */
202 if(result->labs <= m)
204 result = result->parent;
210 struct addr_tree_node* addr_tree_lookup(rbtree_type* tree,
211 struct sockaddr_storage* addr, socklen_t addrlen)
213 rbnode_type* res = NULL;
214 struct addr_tree_node* result;
215 struct addr_tree_node key;
217 memcpy(&key.addr, addr, addrlen);
218 key.addrlen = addrlen;
219 key.net = (addr_is_ip6(addr, addrlen)?128:32);
220 if(rbtree_find_less_equal(tree, &key, &res)) {
222 return (struct addr_tree_node*)res;
224 /* smaller element (or no element) */
226 result = (struct addr_tree_node*)res;
227 if(!result || result->addrlen != addrlen)
229 /* count number of bits matched */
230 m = addr_in_common(&result->addr, result->net, addr,
232 while(result) { /* go up until addr is inside netblock */
235 result = result->parent;
241 struct addr_tree_node* addr_tree_find(rbtree_type* tree,
242 struct sockaddr_storage* addr, socklen_t addrlen, int net)
244 rbnode_type* res = NULL;
245 struct addr_tree_node key;
247 memcpy(&key.addr, addr, addrlen);
248 key.addrlen = addrlen;
250 res = rbtree_search(tree, &key);
251 return (struct addr_tree_node*)res;
255 name_tree_next_root(rbtree_type* tree, uint16_t* dclass)
257 struct name_tree_node key;
259 struct name_tree_node* p;
261 /* first root item is first item in tree */
262 n = rbtree_first(tree);
265 p = (struct name_tree_node*)n;
266 if(dname_is_root(p->name)) {
270 /* root not first item? search for higher items */
271 *dclass = p->dclass + 1;
272 return name_tree_next_root(tree, dclass);
274 /* find class n in tree, we may get a direct hit, or if we don't
275 * this is the last item of the previous class so rbtree_next() takes
276 * us to the next root (if any) */
278 key.name = (uint8_t*)"\000";
281 key.dclass = *dclass;
283 if(rbtree_find_less_equal(tree, &key, &n)) {
287 /* smaller element */
288 if(!n || n == RBTREE_NULL)
289 return 0; /* nothing found */
292 return 0; /* no higher */
293 p = (struct name_tree_node*)n;
294 if(dname_is_root(p->name)) {
298 /* not a root node, return next higher item */
299 *dclass = p->dclass+1;
300 return name_tree_next_root(tree, dclass);