contrib/ldns/ldns/rbtree.h

   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 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_ */