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