contrib/ldns/ldns/radix.h

   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
  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, 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, 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  */
 162 int 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  */
 171 ldns_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  */
 179 ldns_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  */
 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 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, ldns_radix_t* tree);
 235
 236 #ifdef __cplusplus
 237 }
 238 #endif
 239
 240 #endif /* LDNS_RADIX_H_ */