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 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. 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 49extern "C" { 50#endif 51 52typedef uint16_t radix_strlen_t; 53typedef struct ldns_radix_array_t ldns_radix_array_t; 54typedef struct ldns_radix_node_t ldns_radix_node_t; 55typedef struct ldns_radix_t ldns_radix_t; 56 57/** Radix node select edge array */ 58struct 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 */ 68struct 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 */ 90struct 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 */ 102ldns_radix_t* ldns_radix_create(void); 103 104/** 105 * Initialize radix tree. 106 * @param tree: uninitialized radix tree. 107 * 108 */ 109void ldns_radix_init(ldns_radix_t* tree); 110 111/** 112 * Free the radix tree. 113 * @param tree: radix tree. 114 * 115 */ 116void 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 */ 127ldns_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 */ 138void* ldns_radix_delete(ldns_radix_t* tree, 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 */ 148ldns_radix_node_t* ldns_radix_search(ldns_radix_t* tree, 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 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 */ 162int ldns_radix_find_less_equal(ldns_radix_t* tree, 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 */ 171ldns_radix_node_t* ldns_radix_first(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 */ 179ldns_radix_node_t* ldns_radix_last(ldns_radix_t* tree); 180 181/** 182 * Next element. 183 * @param node: node. 184 * @return: node with next element. 185 * 186 */ 187ldns_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 */ 195ldns_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 tree2: another tree. 202 * @return: status. 203 * 204 */ 205ldns_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 */ 215ldns_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 */ 225void 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 */ 234void ldns_radix_printf(FILE* fd, ldns_radix_t* tree); 235 236#ifdef __cplusplus 237} 238#endif 239 240#endif /* LDNS_RADIX_H_ */ 241