1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
|
/*
* rbtree.h -- generic red-black tree
*
* Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
*
* This software is open source.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the NLNET LABS nor the names of its contributors may
* be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
/**
* \file
* Red black tree. Implementation taken from NSD 3.0.5, adjusted for use
* in unbound (memory allocation, logging and so on).
*/
#ifndef LDNS_RBTREE_H_
#define LDNS_RBTREE_H_
#ifdef __cplusplus
extern "C" {
#endif
/**
* This structure must be the first member of the data structure in
* the rbtree. This allows easy casting between an rbnode_t and the
* user data (poor man's inheritance).
* Or you can use the data pointer member to get to your data item.
*/
typedef struct ldns_rbnode_t ldns_rbnode_t;
/**
* The rbnode_t struct definition.
*/
struct ldns_rbnode_t {
/** parent in rbtree, RBTREE_NULL for root */
ldns_rbnode_t *parent;
/** left node (smaller items) */
ldns_rbnode_t *left;
/** right node (larger items) */
ldns_rbnode_t *right;
/** pointer to sorting key */
const void *key;
/** pointer to data */
const void *data;
/** colour of this node */
uint8_t color;
};
/** The nullpointer, points to empty node */
#define LDNS_RBTREE_NULL &ldns_rbtree_null_node
/** the global empty node */
extern ldns_rbnode_t ldns_rbtree_null_node;
/** An entire red black tree */
typedef struct ldns_rbtree_t ldns_rbtree_t;
/** definition for tree struct */
struct ldns_rbtree_t {
/** The root of the red-black tree */
ldns_rbnode_t *root;
/** The number of the nodes in the tree */
size_t count;
/**
* Key compare function. <0,0,>0 like strcmp.
* Return 0 on two NULL ptrs.
*/
int (*cmp) (const void *, const void *);
};
/**
* Create new tree (malloced) with given key compare function.
* @param cmpf: compare function (like strcmp) takes pointers to two keys.
* @return: new tree, empty.
*/
ldns_rbtree_t *ldns_rbtree_create(int (*cmpf)(const void *, const void *));
/**
* Free the complete tree (but not its keys)
* @param rbtree The tree to free
*/
void ldns_rbtree_free(ldns_rbtree_t *rbtree);
/**
* Init a new tree (malloced by caller) with given key compare function.
* @param rbtree: uninitialised memory for new tree, returned empty.
* @param cmpf: compare function (like strcmp) takes pointers to two keys.
*/
void ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *));
/**
* Insert data into the tree.
* @param rbtree: tree to insert to.
* @param data: element to insert.
* @return: data ptr or NULL if key already present.
*/
ldns_rbnode_t *ldns_rbtree_insert(ldns_rbtree_t *rbtree, ldns_rbnode_t *data);
/**
* Insert data into the tree (reversed arguments, for use as callback)
* \param[in] data element to insert
* \param[out] rbtree tree to insert in to
* \return data ptr or NULL if key is already present
*/
void ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree);
/**
* Delete element from tree.
* @param rbtree: tree to delete from.
* @param key: key of item to delete.
* @return: node that is now unlinked from the tree. User to delete it.
* returns 0 if node not present
*/
ldns_rbnode_t *ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key);
/**
* Find key in tree. Returns NULL if not found.
* @param rbtree: tree to find in.
* @param key: key that must match.
* @return: node that fits or NULL.
*/
ldns_rbnode_t *ldns_rbtree_search(ldns_rbtree_t *rbtree, const void *key);
/**
* Find, but match does not have to be exact.
* @param rbtree: tree to find in.
* @param key: key to find position of.
* @param result: set to the exact node if present, otherwise to element that
* precedes the position of key in the tree. NULL if no smaller element.
* @return: true if exact match in result. Else result points to <= element,
* or NULL if key is smaller than the smallest key.
*/
int ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key,
ldns_rbnode_t **result);
/**
* Returns first (smallest) node in the tree
* @param rbtree: tree
* @return: smallest element or NULL if tree empty.
*/
ldns_rbnode_t *ldns_rbtree_first(const ldns_rbtree_t *rbtree);
/**
* Returns last (largest) node in the tree
* @param rbtree: tree
* @return: largest element or NULL if tree empty.
*/
ldns_rbnode_t *ldns_rbtree_last(const ldns_rbtree_t *rbtree);
/**
* Returns next larger node in the tree
* @param rbtree: tree
* @return: next larger element or NULL if no larger in tree.
*/
ldns_rbnode_t *ldns_rbtree_next(ldns_rbnode_t *rbtree);
/**
* Returns previous smaller node in the tree
* @param rbtree: tree
* @return: previous smaller element or NULL if no previous in tree.
*/
ldns_rbnode_t *ldns_rbtree_previous(ldns_rbnode_t *rbtree);
/**
* split off 'elements' number of elements from the start
* of the name tree and return a new tree containing those
* elements
*/
ldns_rbtree_t *ldns_rbtree_split(ldns_rbtree_t *tree, size_t elements);
/**
* add all node from the second tree to the first (removing them from the
* second), and fix up nsec(3)s if present
*/
void ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2);
/**
* Call with node=variable of struct* with rbnode_t as first element.
* with type is the type of a pointer to that struct.
*/
#define LDNS_RBTREE_FOR(node, type, rbtree) \
for(node=(type)ldns_rbtree_first(rbtree); \
(ldns_rbnode_t*)node != LDNS_RBTREE_NULL; \
node = (type)ldns_rbtree_next((ldns_rbnode_t*)node))
/**
* Call function for all elements in the redblack tree, such that
* leaf elements are called before parent elements. So that all
* elements can be safely free()d.
* Note that your function must not remove the nodes from the tree.
* Since that may trigger rebalances of the rbtree.
* @param tree: the tree
* @param func: function called with element and user arg.
* The function must not alter the rbtree.
* @param arg: user argument.
*/
void ldns_traverse_postorder(ldns_rbtree_t* tree,
void (*func)(ldns_rbnode_t*, void*), void* arg);
#ifdef __cplusplus
}
#endif
#endif /* UTIL_RBTREE_H_ */
|
