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#ifdef __cplusplus 47extern "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 */ 56typedef struct ldns_rbnode_t ldns_rbnode_t; 57/** 58 * The rbnode_t struct definition. 59 */ 60struct 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 */ 78extern ldns_rbnode_t ldns_rbtree_null_node; 79 80/** An entire red black tree */ 81typedef struct ldns_rbtree_t ldns_rbtree_t; 82/** definition for tree struct */ 83struct 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 */ 102ldns_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 */ 108void 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 */ 115void 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 */ 123ldns_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 */ 131void 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 */ 140ldns_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 */ 148ldns_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 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 */ 159int 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 */ 167ldns_rbnode_t *ldns_rbtree_first(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 */ 174ldns_rbnode_t *ldns_rbtree_last(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 */ 181ldns_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 */ 188ldns_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 */ 195ldns_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 */ 201void 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 */ 223void 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