1 /* 2 * rbtree.h -- generic red-black tree 3 * 4 * Copyright (c) 2001-2007, 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 UTIL_RBTREE_H_ 44 #define UTIL_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 rbnode_t rbnode_t; 52 /** 53 * The rbnode_t struct definition. 54 */ 55 struct rbnode_t { 56 /** parent in rbtree, RBTREE_NULL for root */ 57 rbnode_t *parent; 58 /** left node (smaller items) */ 59 rbnode_t *left; 60 /** right node (larger items) */ 61 rbnode_t *right; 62 /** pointer to sorting key */ 63 const void *key; 64 /** colour of this node */ 65 uint8_t color; 66 }; 67 68 /** The nullpointer, points to empty node */ 69 #define RBTREE_NULL &rbtree_null_node 70 /** the global empty node */ 71 extern rbnode_t rbtree_null_node; 72 73 /** An entire red black tree */ 74 typedef struct rbtree_t rbtree_t; 75 /** definition for tree struct */ 76 struct rbtree_t { 77 /** The root of the red-black tree */ 78 rbnode_t *root; 79 80 /** The number of the nodes in the tree */ 81 size_t count; 82 83 /** 84 * Key compare function. <0,0,>0 like strcmp. 85 * Return 0 on two NULL ptrs. 86 */ 87 int (*cmp) (const void *, const void *); 88 }; 89 90 /** 91 * Create new tree (malloced) with given key compare function. 92 * @param cmpf: compare function (like strcmp) takes pointers to two keys. 93 * @return: new tree, empty. 94 */ 95 rbtree_t *rbtree_create(int (*cmpf)(const void *, const void *)); 96 97 /** 98 * Init a new tree (malloced by caller) with given key compare function. 99 * @param rbtree: uninitialised memory for new tree, returned empty. 100 * @param cmpf: compare function (like strcmp) takes pointers to two keys. 101 */ 102 void rbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *)); 103 104 /** 105 * Insert data into the tree. 106 * @param rbtree: tree to insert to. 107 * @param data: element to insert. 108 * @return: data ptr or NULL if key already present. 109 */ 110 rbnode_t *rbtree_insert(rbtree_t *rbtree, rbnode_t *data); 111 112 /** 113 * Delete element from tree. 114 * @param rbtree: tree to delete from. 115 * @param key: key of item to delete. 116 * @return: node that is now unlinked from the tree. User to delete it. 117 * returns 0 if node not present 118 */ 119 rbnode_t *rbtree_delete(rbtree_t *rbtree, const void *key); 120 121 /** 122 * Find key in tree. Returns NULL if not found. 123 * @param rbtree: tree to find in. 124 * @param key: key that must match. 125 * @return: node that fits or NULL. 126 */ 127 rbnode_t *rbtree_search(rbtree_t *rbtree, const void *key); 128 129 /** 130 * Find, but match does not have to be exact. 131 * @param rbtree: tree to find in. 132 * @param key: key to find position of. 133 * @param result: set to the exact node if present, otherwise to element that 134 * precedes the position of key in the tree. NULL if no smaller element. 135 * @return: true if exact match in result. Else result points to <= element, 136 * or NULL if key is smaller than the smallest key. 137 */ 138 int rbtree_find_less_equal(rbtree_t *rbtree, const void *key, 139 rbnode_t **result); 140 141 /** 142 * Returns first (smallest) node in the tree 143 * @param rbtree: tree 144 * @return: smallest element or NULL if tree empty. 145 */ 146 rbnode_t *rbtree_first(rbtree_t *rbtree); 147 148 /** 149 * Returns last (largest) node in the tree 150 * @param rbtree: tree 151 * @return: largest element or NULL if tree empty. 152 */ 153 rbnode_t *rbtree_last(rbtree_t *rbtree); 154 155 /** 156 * Returns next larger node in the tree 157 * @param rbtree: tree 158 * @return: next larger element or NULL if no larger in tree. 159 */ 160 rbnode_t *rbtree_next(rbnode_t *rbtree); 161 162 /** 163 * Returns previous smaller node in the tree 164 * @param rbtree: tree 165 * @return: previous smaller element or NULL if no previous in tree. 166 */ 167 rbnode_t *rbtree_previous(rbnode_t *rbtree); 168 169 /** 170 * Call with node=variable of struct* with rbnode_t as first element. 171 * with type is the type of a pointer to that struct. 172 */ 173 #define RBTREE_FOR(node, type, rbtree) \ 174 for(node=(type)rbtree_first(rbtree); \ 175 (rbnode_t*)node != RBTREE_NULL; \ 176 node = (type)rbtree_next((rbnode_t*)node)) 177 178 /** 179 * Call function for all elements in the redblack tree, such that 180 * leaf elements are called before parent elements. So that all 181 * elements can be safely free()d. 182 * Note that your function must not remove the nodes from the tree. 183 * Since that may trigger rebalances of the rbtree. 184 * @param tree: the tree 185 * @param func: function called with element and user arg. 186 * The function must not alter the rbtree. 187 * @param arg: user argument. 188 */ 189 void traverse_postorder(rbtree_t* tree, void (*func)(rbnode_t*, void*), 190 void* arg); 191 192 #endif /* UTIL_RBTREE_H_ */ 193