Initial vendor import of ldns-1.6.4 into contrib.
[dragonfly.git] / 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 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 /**
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 ldns_rbnode_t ldns_rbnode_t;
52 /**
53  * The rbnode_t struct definition.
54  */
55 struct ldns_rbnode_t {
56         /** parent in rbtree, RBTREE_NULL for root */
57         ldns_rbnode_t   *parent;
58         /** left node (smaller items) */
59         ldns_rbnode_t   *left;
60         /** right node (larger items) */
61         ldns_rbnode_t   *right;
62         /** pointer to sorting key */
63         const void *key;
64         /** pointer to data */
65         const void *data;
66         /** colour of this node */
67         uint8_t     color;
68 };
69
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;
74
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 */
80         ldns_rbnode_t    *root;
81
82         /** The number of the nodes in the tree */
83         size_t       count;
84
85         /** 
86          * Key compare function. <0,0,>0 like strcmp. 
87          * Return 0 on two NULL ptrs. 
88          */
89         int (*cmp) (const void *, const void *);
90 };
91
92 /** 
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.
96  */
97 ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *));
98
99 /**
100  * Free the complete tree (but not its keys)
101  * @param rbtree The tree to free
102  */
103 void ldns_rbtree_free(ldns_rbtree_t *rbtree);
104
105 /** 
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.
109  */
110 void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *));
111
112 /** 
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. 
117  */
118 ldns_rbnode_t *ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data);
119
120 /**
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
125  */
126 void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree);
127
128 /**
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 
134  */
135 ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key);
136
137 /**
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.
142  */
143 ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key);
144
145 /**
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. 
153  */
154 int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, 
155         ldns_rbnode_t **result);
156
157 /**
158  * Returns first (smallest) node in the tree
159  * @param rbtree: tree
160  * @return: smallest element or NULL if tree empty.
161  */
162 ldns_rbnode_t *ldns_rbtree_first(ldns_rbtree_t *rbtree);
163
164 /**
165  * Returns last (largest) node in the tree
166  * @param rbtree: tree
167  * @return: largest element or NULL if tree empty.
168  */
169 ldns_rbnode_t *ldns_rbtree_last(ldns_rbtree_t *rbtree);
170
171 /**
172  * Returns next larger node in the tree
173  * @param rbtree: tree
174  * @return: next larger element or NULL if no larger in tree.
175  */
176 ldns_rbnode_t *ldns_rbtree_next(ldns_rbnode_t *rbtree);
177
178 /**
179  * Returns previous smaller node in the tree
180  * @param rbtree: tree
181  * @return: previous smaller element or NULL if no previous in tree.
182  */
183 ldns_rbnode_t *ldns_rbtree_previous(ldns_rbnode_t *rbtree);
184
185 /**
186  * split off 'elements' number of elements from the start
187  * of the name tree and return a new tree containing those
188  * elements
189  */
190 ldns_rbtree_t *ldns_rbtree_split(ldns_rbtree_t *tree, size_t elements);
191
192 /**
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
195  */
196 void ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2);
197
198 /**
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. 
201  */
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))
206
207 /**
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.
217  */
218 void ldns_traverse_postorder(ldns_rbtree_t* tree, 
219         void (*func)(ldns_rbnode_t*, void*), void* arg);
220
221 #endif /* UTIL_RBTREE_H_ */