xref: /freebsd/contrib/unbound/util/storage/dnstree.h (revision 71625ec9ad2a9bc8c09784fbd23b759830e0ee5f)
1 /*
2  * util/storage/dnstree.h - 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 
43 #ifndef UTIL_STORAGE_DNSTREE_H
44 #define UTIL_STORAGE_DNSTREE_H
45 #include "util/rbtree.h"
46 
47 /**
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.
51  *
52  * The tree itself is a rbtree_type.
53  * This is the element node put as first entry in the client structure.
54  */
55 struct name_tree_node {
56 	/** rbtree node, key is this struct : dclass and name */
57 	rbnode_type node;
58 	/** parent in tree */
59 	struct name_tree_node* parent;
60 	/** name in uncompressed wireformat */
61 	uint8_t* name;
62 	/** length of name */
63 	size_t len;
64 	/** labels in name */
65 	int labs;
66 	/** the class of the name (host order) */
67 	uint16_t dclass;
68 };
69 
70 /**
71  * Tree of IP addresses.  Sorted first by protocol, then by bits.
72  * This can be looked up to obtain the enclosing subnet.
73  *
74  * The tree itself is a rbtree_type.
75  * This is the element node put as first entry in the client structure.
76  */
77 struct addr_tree_node {
78 	/** rbtree node, key is this struct : proto and subnet */
79 	rbnode_type node;
80 	/** parent in tree */
81 	struct addr_tree_node* parent;
82 	/** address */
83 	struct sockaddr_storage addr;
84 	/** length of addr */
85 	socklen_t addrlen;
86 	/** netblock size */
87 	int net;
88 };
89 
90 /**
91  * Init a name tree to be empty
92  * @param tree: to init.
93  */
94 void name_tree_init(rbtree_type* tree);
95 
96 /**
97  * insert element into name tree.
98  * @param tree: name tree
99  * @param node: node element (at start of a structure that caller
100  *	has allocated).
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).
107  */
108 int name_tree_insert(rbtree_type* tree, struct name_tree_node* node,
109 	uint8_t* name, size_t len, int labs, uint16_t dclass);
110 
111 /**
112  * Initialize parent pointers in name tree.
113  * Should be performed after insertions are done, before lookups
114  * @param tree: name tree
115  */
116 void name_tree_init_parents(rbtree_type* tree);
117 
118 /**
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.
126  */
127 struct name_tree_node* name_tree_find(rbtree_type* tree, uint8_t* name,
128 	size_t len, int labs, uint16_t dclass);
129 
130 /**
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.
138  */
139 struct name_tree_node* name_tree_lookup(rbtree_type* tree, uint8_t* name,
140 	size_t len, int labs, uint16_t dclass);
141 
142 /**
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.
147  */
148 int name_tree_next_root(rbtree_type* tree, uint16_t* dclass);
149 
150 /**
151  * Init addr tree to be empty.
152  * @param tree: to init.
153  */
154 void addr_tree_init(rbtree_type* tree);
155 
156 /**
157  * Init addr tree to be empty.
158  * The comparison function to be used is addr_tree_addrport_compare.
159  * @param tree: to init.
160  */
161 void addr_tree_addrport_init(rbtree_type* tree);
162 
163 /**
164  * insert element into addr tree.
165  * @param tree: addr tree
166  * @param node: node element (at start of a structure that caller
167  *	has allocated).
168  * @param addr: to insert (copied).
169  * @param addrlen: length of addr
170  * @param net: size of subnet.
171  * @return false on error (duplicate element).
172  */
173 int addr_tree_insert(rbtree_type* tree, struct addr_tree_node* node,
174 	struct sockaddr_storage* addr, socklen_t addrlen, int net);
175 
176 /**
177  * Initialize parent pointers in addr tree.
178  * Should be performed after insertions are done, before lookups
179  * @param tree: addr tree
180  */
181 void addr_tree_init_parents(rbtree_type* tree);
182 
183 /**
184  * Initialize parent pointers in partial addr tree.
185  * Reinitialize pointer for part of tree, used after node deletion
186  * @param node: node to start parent pointer initialization for.
187  */
188 void addr_tree_init_parents_node(struct addr_tree_node* node);
189 
190 /**
191  * Lookup closest encloser in addr tree.
192  * @param tree: addr tree
193  * @param addr: to lookup.
194  * @param addrlen: length of addr
195  * @return closest enclosing node (could be equal) or NULL if not found.
196  */
197 struct addr_tree_node* addr_tree_lookup(rbtree_type* tree,
198 	struct sockaddr_storage* addr, socklen_t addrlen);
199 
200 /**
201  * Find element in addr tree.  (search a netblock, not a match for an address)
202  * @param tree: addr tree
203  * @param addr: netblock to lookup.
204  * @param addrlen: length of addr
205  * @param net: size of subnet
206  * @return addr tree element, or NULL if not found.
207  */
208 struct addr_tree_node* addr_tree_find(rbtree_type* tree,
209 	struct sockaddr_storage* addr, socklen_t addrlen, int net);
210 
211 /** compare name tree nodes */
212 int name_tree_compare(const void* k1, const void* k2);
213 
214 /** compare addr tree nodes */
215 int addr_tree_compare(const void* k1, const void* k2);
216 
217 /** compare addr tree nodes (address and port only) */
218 int addr_tree_addrport_compare(const void* k1, const void* k2);
219 
220 #endif /* UTIL_STORAGE_DNSTREE_H */
221