2 * radix.h -- generic radix tree
4 * Copyright (c) 2012, 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 LIMITED
25 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
39 * Radix tree. Implementation taken from NSD 4, adjusted for use in ldns.
46 #include <ldns/error.h>
52 typedef uint16_t radix_strlen_t;
53 typedef struct ldns_radix_array_t ldns_radix_array_t;
54 typedef struct ldns_radix_node_t ldns_radix_node_t;
55 typedef struct ldns_radix_t ldns_radix_t;
57 /** Radix node select edge array */
58 struct ldns_radix_array_t {
59 /** Additional string after the selection byte for this edge. */
61 /** Length of additional string for this edge. */
63 /** Node that deals with byte+str. */
64 ldns_radix_node_t* edge;
67 /** A node in a radix tree */
68 struct ldns_radix_node_t {
69 /** Key corresponding to this node. */
71 /** Key length corresponding to this node. */
73 /** Data corresponding to this node. */
76 ldns_radix_node_t* parent;
77 /** Index in the the parent node select edge array. */
79 /** Length of the array. */
81 /** Offset of the array. */
83 /** Capacity of the array. */
85 /** Select edge array. */
86 ldns_radix_array_t* array;
89 /** An entire radix tree */
92 ldns_radix_node_t* root;
93 /** Number of nodes in tree. */
98 * Create a new radix tree.
99 * @return: new radix tree.
102 ldns_radix_t* ldns_radix_create(void);
105 * Initialize radix tree.
106 * @param tree: uninitialized radix tree.
109 void ldns_radix_init(ldns_radix_t* tree);
112 * Free the radix tree.
113 * @param tree: radix tree.
116 void ldns_radix_free(ldns_radix_t* tree);
119 * Insert data into the tree.
120 * @param tree: tree to insert to.
122 * @param len: length of key.
127 ldns_status ldns_radix_insert(ldns_radix_t* tree, uint8_t* key,
128 radix_strlen_t len, void* data);
131 * Delete data from the tree.
132 * @param tree: tree to insert to.
134 * @param len: length of key.
135 * @return: unlinked data or NULL if not present.
138 void* ldns_radix_delete(ldns_radix_t* tree, uint8_t* key, radix_strlen_t len);
141 * Search data in the tree.
142 * @param tree: tree to insert to.
144 * @param len: length of key.
145 * @return: the radix node or NULL if not found.
148 ldns_radix_node_t* ldns_radix_search(ldns_radix_t* tree, uint8_t* key,
152 * Search data in the tree, and if not found, find the closest smaller
153 * element in the tree.
154 * @param tree: tree to insert to.
156 * @param len: length of key.
157 * @param result: the radix node with the exact or closest match. NULL if
158 * the key is smaller than the smallest key in the tree.
159 * @return 1 if exact match, 0 otherwise.
162 int ldns_radix_find_less_equal(ldns_radix_t* tree, uint8_t* key,
163 radix_strlen_t len, ldns_radix_node_t** result);
166 * Get the first element in the tree.
168 * @return: the radix node with the first element.
171 ldns_radix_node_t* ldns_radix_first(ldns_radix_t* tree);
174 * Get the last element in the tree.
176 * @return: the radix node with the last element.
179 ldns_radix_node_t* ldns_radix_last(ldns_radix_t* tree);
184 * @return: node with next element.
187 ldns_radix_node_t* ldns_radix_next(ldns_radix_node_t* node);
192 * @return: node with previous element.
195 ldns_radix_node_t* ldns_radix_prev(ldns_radix_node_t* node);
198 * Split radix tree intwo.
199 * @param tree1: one tree.
200 * @param num: number of elements to split off.
201 * @param tree2: another tree.
205 ldns_status ldns_radix_split(ldns_radix_t* tree1, size_t num,
206 ldns_radix_t** tree2);
209 * Join two radix trees.
210 * @param tree1: one tree.
211 * @param tree2: another tree.
215 ldns_status ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2);
218 * Call function for all nodes in the tree, such that leaf nodes are
219 * called before parent nodes.
220 * @param node: start node.
221 * @param func: function.
222 * @param arg: user argument.
225 void ldns_radix_traverse_postorder(ldns_radix_node_t* node,
226 void (*func)(ldns_radix_node_t*, void*), void* arg);
229 * Print radix tree (for debugging purposes).
230 * @param fd: file descriptor.
234 void ldns_radix_printf(FILE* fd, ldns_radix_t* tree);
240 #endif /* LDNS_RADIX_H_ */