2 * rbtree.h -- generic red-black tree
4 * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
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.
39 * Red black tree. Implementation taken from NSD 3.0.5, adjusted for use
40 * in unbound (memory allocation, logging and so on).
43 #ifndef LDNS_RBTREE_H_
44 #define LDNS_RBTREE_H_
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).
51 typedef struct ldns_rbnode_t ldns_rbnode_t;
53 * The rbnode_t struct definition.
55 struct ldns_rbnode_t {
56 /** parent in rbtree, RBTREE_NULL for root */
57 ldns_rbnode_t *parent;
58 /** left node (smaller items) */
60 /** right node (larger items) */
62 /** pointer to sorting key */
64 /** pointer to data */
66 /** colour of this node */
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;
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 */
82 /** The number of the nodes in the tree */
86 * Key compare function. <0,0,>0 like strcmp.
87 * Return 0 on two NULL ptrs.
89 int (*cmp) (const void *, const void *);
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.
97 ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *));
100 * Free the complete tree (but not its keys)
101 * @param rbtree The tree to free
103 void ldns_rbtree_free(ldns_rbtree_t *rbtree);
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.
110 void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *));
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.
118 ldns_rbnode_t *ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data);
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
126 void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree);
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
135 ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key);
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.
143 ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key);
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.
154 int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key,
155 ldns_rbnode_t **result);
158 * Returns first (smallest) node in the tree
159 * @param rbtree: tree
160 * @return: smallest element or NULL if tree empty.
162 ldns_rbnode_t *ldns_rbtree_first(ldns_rbtree_t *rbtree);
165 * Returns last (largest) node in the tree
166 * @param rbtree: tree
167 * @return: largest element or NULL if tree empty.
169 ldns_rbnode_t *ldns_rbtree_last(ldns_rbtree_t *rbtree);
172 * Returns next larger node in the tree
173 * @param rbtree: tree
174 * @return: next larger element or NULL if no larger in tree.
176 ldns_rbnode_t *ldns_rbtree_next(ldns_rbnode_t *rbtree);
179 * Returns previous smaller node in the tree
180 * @param rbtree: tree
181 * @return: previous smaller element or NULL if no previous in tree.
183 ldns_rbnode_t *ldns_rbtree_previous(ldns_rbnode_t *rbtree);
186 * split off 'elements' number of elements from the start
187 * of the name tree and return a new tree containing those
190 ldns_rbtree_t *ldns_rbtree_split(ldns_rbtree_t *tree, size_t elements);
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
196 void ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2);
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.
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))
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.
218 void ldns_traverse_postorder(ldns_rbtree_t* tree,
219 void (*func)(ldns_rbnode_t*, void*), void* arg);
221 #endif /* UTIL_RBTREE_H_ */