1 /* 2 * rbtree.h -- generic red-black tree 3 * 4 * Copyright (c) 2001-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 /** 38 * \file 39 * Red black tree. Implementation taken from NSD 3.0.5, adjusted for use 40 * in unbound (memory allocation, logging and so on). 41 */ 42 43 #ifndef LDNS_RBTREE_H_ 44 #define LDNS_RBTREE_H_ 45 46 #ifdef __cplusplus 47 extern "C" { 48 #endif 49 50 /** 51 * This structure must be the first member of the data structure in 52 * the rbtree. This allows easy casting between an rbnode_t and the 53 * user data (poor man's inheritance). 54 * Or you can use the data pointer member to get to your data item. 55 */ 56 typedef struct ldns_rbnode_t ldns_rbnode_t; 57 /** 58 * The rbnode_t struct definition. 59 */ 60 struct ldns_rbnode_t { 61 /** parent in rbtree, RBTREE_NULL for root */ 62 ldns_rbnode_t *parent; 63 /** left node (smaller items) */ 64 ldns_rbnode_t *left; 65 /** right node (larger items) */ 66 ldns_rbnode_t *right; 67 /** pointer to sorting key */ 68 const void *key; 69 /** pointer to data */ 70 const void *data; 71 /** colour of this node */ 72 uint8_t color; 73 }; 74 75 /** The nullpointer, points to empty node */ 76 #define LDNS_RBTREE_NULL &ldns_rbtree_null_node 77 /** the global empty node */ 78 extern ldns_rbnode_t ldns_rbtree_null_node; 79 80 /** An entire red black tree */ 81 typedef struct ldns_rbtree_t ldns_rbtree_t; 82 /** definition for tree struct */ 83 struct ldns_rbtree_t { 84 /** The root of the red-black tree */ 85 ldns_rbnode_t *root; 86 87 /** The number of the nodes in the tree */ 88 size_t count; 89 90 /** 91 * Key compare function. <0,0,>0 like strcmp. 92 * Return 0 on two NULL ptrs. 93 */ 94 int (*cmp) (const void *, const void *); 95 }; 96 97 /** 98 * Create new tree (malloced) with given key compare function. 99 * @param cmpf: compare function (like strcmp) takes pointers to two keys. 100 * @return: new tree, empty. 101 */ 102 ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *)); 103 104 /** 105 * Free the complete tree (but not its keys) 106 * @param rbtree The tree to free 107 */ 108 void ldns_rbtree_free(ldns_rbtree_t *rbtree); 109 110 /** 111 * Init a new tree (malloced by caller) with given key compare function. 112 * @param rbtree: uninitialised memory for new tree, returned empty. 113 * @param cmpf: compare function (like strcmp) takes pointers to two keys. 114 */ 115 void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *)); 116 117 /** 118 * Insert data into the tree. 119 * @param rbtree: tree to insert to. 120 * @param data: element to insert. 121 * @return: data ptr or NULL if key already present. 122 */ 123 ldns_rbnode_t *ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data); 124 125 /** 126 * Insert data into the tree (reversed arguments, for use as callback) 127 * \param[in] data element to insert 128 * \param[out] rbtree tree to insert in to 129 * \return data ptr or NULL if key is already present 130 */ 131 void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree); 132 133 /** 134 * Delete element from tree. 135 * @param rbtree: tree to delete from. 136 * @param key: key of item to delete. 137 * @return: node that is now unlinked from the tree. User to delete it. 138 * returns 0 if node not present 139 */ 140 ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key); 141 142 /** 143 * Find key in tree. Returns NULL if not found. 144 * @param rbtree: tree to find in. 145 * @param key: key that must match. 146 * @return: node that fits or NULL. 147 */ 148 ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key); 149 150 /** 151 * Find, but match does not have to be exact. 152 * @param rbtree: tree to find in. 153 * @param key: key to find position of. 154 * @param[out] result: set to the exact node if present, otherwise to element that 155 * precedes the position of key in the tree. NULL if no smaller element. 156 * @return: true if exact match in result. Else result points to <= element, 157 * or NULL if key is smaller than the smallest key. 158 */ 159 int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, 160 ldns_rbnode_t **result); 161 162 /** 163 * Returns first (smallest) node in the tree 164 * @param rbtree: tree 165 * @return: smallest element or NULL if tree empty. 166 */ 167 ldns_rbnode_t *ldns_rbtree_first(const ldns_rbtree_t *rbtree); 168 169 /** 170 * Returns last (largest) node in the tree 171 * @param rbtree: tree 172 * @return: largest element or NULL if tree empty. 173 */ 174 ldns_rbnode_t *ldns_rbtree_last(const ldns_rbtree_t *rbtree); 175 176 /** 177 * Returns next larger node in the tree 178 * @param rbtree: tree 179 * @return: next larger element or NULL if no larger in tree. 180 */ 181 ldns_rbnode_t *ldns_rbtree_next(ldns_rbnode_t *rbtree); 182 183 /** 184 * Returns previous smaller node in the tree 185 * @param rbtree: tree 186 * @return: previous smaller element or NULL if no previous in tree. 187 */ 188 ldns_rbnode_t *ldns_rbtree_previous(ldns_rbnode_t *rbtree); 189 190 /** 191 * split off 'elements' number of elements from the start 192 * of the name tree and return a new tree containing those 193 * elements 194 */ 195 ldns_rbtree_t *ldns_rbtree_split(ldns_rbtree_t *tree, size_t elements); 196 197 /** 198 * add all node from the second tree to the first (removing them from the 199 * second), and fix up nsec(3)s if present 200 */ 201 void ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2); 202 203 /** 204 * Call with node=variable of struct* with rbnode_t as first element. 205 * with type is the type of a pointer to that struct. 206 */ 207 #define LDNS_RBTREE_FOR(node, type, rbtree) \ 208 for(node=(type)ldns_rbtree_first(rbtree); \ 209 (ldns_rbnode_t*)node != LDNS_RBTREE_NULL; \ 210 node = (type)ldns_rbtree_next((ldns_rbnode_t*)node)) 211 212 /** 213 * Call function for all elements in the redblack tree, such that 214 * leaf elements are called before parent elements. So that all 215 * elements can be safely free()d. 216 * Note that your function must not remove the nodes from the tree. 217 * Since that may trigger rebalances of the rbtree. 218 * @param tree: the tree 219 * @param func: function called with element and user arg. 220 * The function must not alter the rbtree. 221 * @param arg: user argument. 222 */ 223 void ldns_traverse_postorder(ldns_rbtree_t* tree, 224 void (*func)(ldns_rbnode_t*, void*), void* arg); 225 226 #ifdef __cplusplus 227 } 228 #endif 229 230 #endif /* UTIL_RBTREE_H_ */ 231