1 /* 2 * radix.h -- generic radix tree 3 * 4 * Copyright (c) 2012, 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 /** 38 * \file 39 * Radix tree. Implementation taken from NSD 4, adjusted for use in ldns. 40 * 41 */ 42 43 #ifndef LDNS_RADIX_H_ 44 #define LDNS_RADIX_H_ 45 46 #include <ldns/error.h> 47 48 #ifdef __cplusplus 49 extern "C" { 50 #endif 51 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; 56 57 /** Radix node select edge array */ 58 struct ldns_radix_array_t { 59 /** Additional string after the selection byte for this edge. */ 60 uint8_t* str; 61 /** Length of additional string for this edge. */ 62 radix_strlen_t len; 63 /** Node that deals with byte+str. */ 64 ldns_radix_node_t* edge; 65 }; 66 67 /** A node in a radix tree */ 68 struct ldns_radix_node_t { 69 /** Key corresponding to this node. */ 70 uint8_t* key; 71 /** Key length corresponding to this node. */ 72 radix_strlen_t klen; 73 /** Data corresponding to this node. */ 74 void* data; 75 /** Parent node. */ 76 ldns_radix_node_t* parent; 77 /** Index in the the parent node select edge array. */ 78 uint8_t parent_index; 79 /** Length of the array. */ 80 uint16_t len; 81 /** Offset of the array. */ 82 uint16_t offset; 83 /** Capacity of the array. */ 84 uint16_t capacity; 85 /** Select edge array. */ 86 ldns_radix_array_t* array; 87 }; 88 89 /** An entire radix tree */ 90 struct ldns_radix_t { 91 /** Root. */ 92 ldns_radix_node_t* root; 93 /** Number of nodes in tree. */ 94 size_t count; 95 }; 96 97 /** 98 * Create a new radix tree. 99 * @return: new radix tree. 100 * 101 */ 102 ldns_radix_t* ldns_radix_create(void); 103 104 /** 105 * Initialize radix tree. 106 * @param tree: uninitialized radix tree. 107 * 108 */ 109 void ldns_radix_init(ldns_radix_t* tree); 110 111 /** 112 * Free the radix tree. 113 * @param tree: radix tree. 114 * 115 */ 116 void ldns_radix_free(ldns_radix_t* tree); 117 118 /** 119 * Insert data into the tree. 120 * @param tree: tree to insert to. 121 * @param key: key. 122 * @param len: length of key. 123 * @param data: data. 124 * @return: status. 125 * 126 */ 127 ldns_status ldns_radix_insert(ldns_radix_t* tree, uint8_t* key, 128 radix_strlen_t len, void* data); 129 130 /** 131 * Delete data from the tree. 132 * @param tree: tree to insert to. 133 * @param key: key. 134 * @param len: length of key. 135 * @return: unlinked data or NULL if not present. 136 * 137 */ 138 void* ldns_radix_delete(ldns_radix_t* tree, const uint8_t* key, radix_strlen_t len); 139 140 /** 141 * Search data in the tree. 142 * @param tree: tree to insert to. 143 * @param key: key. 144 * @param len: length of key. 145 * @return: the radix node or NULL if not found. 146 * 147 */ 148 ldns_radix_node_t* ldns_radix_search(ldns_radix_t* tree, const uint8_t* key, 149 radix_strlen_t len); 150 151 /** 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. 155 * @param key: key. 156 * @param len: length of key. 157 * @param[out] 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. 160 * 161 */ 162 int ldns_radix_find_less_equal(ldns_radix_t* tree, const uint8_t* key, 163 radix_strlen_t len, ldns_radix_node_t** result); 164 165 /** 166 * Get the first element in the tree. 167 * @param tree: tree. 168 * @return: the radix node with the first element. 169 * 170 */ 171 ldns_radix_node_t* ldns_radix_first(const ldns_radix_t* tree); 172 173 /** 174 * Get the last element in the tree. 175 * @param tree: tree. 176 * @return: the radix node with the last element. 177 * 178 */ 179 ldns_radix_node_t* ldns_radix_last(const ldns_radix_t* tree); 180 181 /** 182 * Next element. 183 * @param node: node. 184 * @return: node with next element. 185 * 186 */ 187 ldns_radix_node_t* ldns_radix_next(ldns_radix_node_t* node); 188 189 /** 190 * Previous element. 191 * @param node: node. 192 * @return: node with previous element. 193 * 194 */ 195 ldns_radix_node_t* ldns_radix_prev(ldns_radix_node_t* node); 196 197 /** 198 * Split radix tree intwo. 199 * @param tree1: one tree. 200 * @param num: number of elements to split off. 201 * @param[out] tree2: another tree. 202 * @return: status. 203 * 204 */ 205 ldns_status ldns_radix_split(ldns_radix_t* tree1, size_t num, 206 ldns_radix_t** tree2); 207 208 /** 209 * Join two radix trees. 210 * @param tree1: one tree. 211 * @param tree2: another tree. 212 * @return: status. 213 * 214 */ 215 ldns_status ldns_radix_join(ldns_radix_t* tree1, ldns_radix_t* tree2); 216 217 /** 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. 223 * 224 */ 225 void ldns_radix_traverse_postorder(ldns_radix_node_t* node, 226 void (*func)(ldns_radix_node_t*, void*), void* arg); 227 228 /** 229 * Print radix tree (for debugging purposes). 230 * @param fd: file descriptor. 231 * @param tree: tree. 232 * 233 */ 234 void ldns_radix_printf(FILE* fd, const ldns_radix_t* tree); 235 236 #ifdef __cplusplus 237 } 238 #endif 239 240 #endif /* LDNS_RADIX_H_ */ 241