unbound/util/rbtree.h

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