2 * util/storage/dnstree.h - 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 #ifndef UTIL_STORAGE_DNSTREE_H
44 #define UTIL_STORAGE_DNSTREE_H
45 #include "util/rbtree.h"
48 * Tree of domain names. Sorted first by class then by name.
49 * This is not sorted canonically, but fast.
50 * This can be looked up to obtain a closest encloser parent name.
52 * The tree itself is a rbtree_t.
53 * This is the element node put as first entry in the client structure.
55 struct name_tree_node {
56 /** rbtree node, key is this struct : dclass and name */
59 struct name_tree_node* parent;
60 /** name in uncompressed wireformat */
66 /** the class of the name (host order) */
71 * Tree of IP addresses. Sorted first by protocol, then by bits.
72 * This can be looked up to obtain the enclosing subnet.
74 * The tree itself is a rbtree_t.
75 * This is the element node put as first entry in the client structure.
77 struct addr_tree_node {
78 /** rbtree node, key is this struct : proto and subnet */
81 struct addr_tree_node* parent;
83 struct sockaddr_storage addr;
91 * Init a name tree to be empty
92 * @param tree: to init.
94 void name_tree_init(rbtree_t* tree);
97 * insert element into name tree.
98 * @param tree: name tree
99 * @param node: node element (at start of a structure that caller
101 * @param name: name to insert (wireformat)
102 * this node has been allocated by the caller and it itself inserted.
103 * @param len: length of name
104 * @param labs: labels in name
105 * @param dclass: class of name
106 * @return false on error (duplicate element).
108 int name_tree_insert(rbtree_t* tree, struct name_tree_node* node,
109 uint8_t* name, size_t len, int labs, uint16_t dclass);
112 * Initialize parent pointers in name tree.
113 * Should be performed after insertions are done, before lookups
114 * @param tree: name tree
116 void name_tree_init_parents(rbtree_t* tree);
119 * Lookup exact match in name tree
120 * @param tree: name tree
121 * @param name: wireformat name
122 * @param len: length of name
123 * @param labs: labels in name
124 * @param dclass: class of name
125 * @return node or NULL if not found.
127 struct name_tree_node* name_tree_find(rbtree_t* tree, uint8_t* name,
128 size_t len, int labs, uint16_t dclass);
131 * Lookup closest encloser in name tree.
132 * @param tree: name tree
133 * @param name: wireformat name
134 * @param len: length of name
135 * @param labs: labels in name
136 * @param dclass: class of name
137 * @return closest enclosing node (could be equal) or NULL if not found.
139 struct name_tree_node* name_tree_lookup(rbtree_t* tree, uint8_t* name,
140 size_t len, int labs, uint16_t dclass);
143 * Find next root item in name tree.
144 * @param tree: the nametree.
145 * @param dclass: the class to look for next (or higher).
146 * @return false if no classes found, true means class put into c.
148 int name_tree_next_root(rbtree_t* tree, uint16_t* dclass);
151 * Init addr tree to be empty.
152 * @param tree: to init.
154 void addr_tree_init(rbtree_t* tree);
157 * insert element into addr tree.
158 * @param tree: addr tree
159 * @param node: node element (at start of a structure that caller
161 * @param addr: to insert (copied).
162 * @param addrlen: length of addr
163 * @param net: size of subnet.
164 * @return false on error (duplicate element).
166 int addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node,
167 struct sockaddr_storage* addr, socklen_t addrlen, int net);
170 * Initialize parent pointers in addr tree.
171 * Should be performed after insertions are done, before lookups
172 * @param tree: addr tree
174 void addr_tree_init_parents(rbtree_t* tree);
177 * Lookup closest encloser in addr tree.
178 * @param tree: addr tree
179 * @param addr: to lookup.
180 * @param addrlen: length of addr
181 * @return closest enclosing node (could be equal) or NULL if not found.
183 struct addr_tree_node* addr_tree_lookup(rbtree_t* tree,
184 struct sockaddr_storage* addr, socklen_t addrlen);
186 /** compare name tree nodes */
187 int name_tree_compare(const void* k1, const void* k2);
189 /** compare addr tree nodes */
190 int addr_tree_compare(const void* k1, const void* k2);
192 #endif /* UTIL_STORAGE_DNSTREE_H */