]>
Commit | Line | Data |
---|---|---|
970d7e83 LB |
1 | /*- |
2 | ******************************************************************************* | |
3 | * | |
4 | * cpp macro implementation of left-leaning 2-3 red-black trees. Parent | |
5 | * pointers are not used, and color bits are stored in the least significant | |
6 | * bit of right-child pointers (if RB_COMPACT is defined), thus making node | |
7 | * linkage as compact as is possible for red-black trees. | |
8 | * | |
9 | * Usage: | |
10 | * | |
11 | * #include <stdint.h> | |
12 | * #include <stdbool.h> | |
13 | * #define NDEBUG // (Optional, see assert(3).) | |
14 | * #include <assert.h> | |
15 | * #define RB_COMPACT // (Optional, embed color bits in right-child pointers.) | |
16 | * #include <rb.h> | |
17 | * ... | |
18 | * | |
19 | ******************************************************************************* | |
20 | */ | |
21 | ||
22 | #ifndef RB_H_ | |
23 | #define RB_H_ | |
24 | ||
970d7e83 LB |
25 | #ifdef RB_COMPACT |
26 | /* Node structure. */ | |
27 | #define rb_node(a_type) \ | |
28 | struct { \ | |
29 | a_type *rbn_left; \ | |
30 | a_type *rbn_right_red; \ | |
31 | } | |
32 | #else | |
33 | #define rb_node(a_type) \ | |
34 | struct { \ | |
35 | a_type *rbn_left; \ | |
36 | a_type *rbn_right; \ | |
37 | bool rbn_red; \ | |
38 | } | |
39 | #endif | |
40 | ||
41 | /* Root structure. */ | |
42 | #define rb_tree(a_type) \ | |
43 | struct { \ | |
44 | a_type *rbt_root; \ | |
970d7e83 LB |
45 | } |
46 | ||
47 | /* Left accessors. */ | |
48 | #define rbtn_left_get(a_type, a_field, a_node) \ | |
49 | ((a_node)->a_field.rbn_left) | |
50 | #define rbtn_left_set(a_type, a_field, a_node, a_left) do { \ | |
51 | (a_node)->a_field.rbn_left = a_left; \ | |
52 | } while (0) | |
53 | ||
54 | #ifdef RB_COMPACT | |
55 | /* Right accessors. */ | |
56 | #define rbtn_right_get(a_type, a_field, a_node) \ | |
57 | ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \ | |
58 | & ((ssize_t)-2))) | |
59 | #define rbtn_right_set(a_type, a_field, a_node, a_right) do { \ | |
60 | (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \ | |
61 | | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \ | |
62 | } while (0) | |
63 | ||
64 | /* Color accessors. */ | |
65 | #define rbtn_red_get(a_type, a_field, a_node) \ | |
66 | ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \ | |
67 | & ((size_t)1))) | |
68 | #define rbtn_color_set(a_type, a_field, a_node, a_red) do { \ | |
69 | (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \ | |
70 | (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \ | |
71 | | ((ssize_t)a_red)); \ | |
72 | } while (0) | |
73 | #define rbtn_red_set(a_type, a_field, a_node) do { \ | |
74 | (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \ | |
75 | (a_node)->a_field.rbn_right_red) | ((size_t)1)); \ | |
76 | } while (0) | |
77 | #define rbtn_black_set(a_type, a_field, a_node) do { \ | |
78 | (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \ | |
79 | (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \ | |
80 | } while (0) | |
54a0048b SL |
81 | |
82 | /* Node initializer. */ | |
83 | #define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \ | |
84 | /* Bookkeeping bit cannot be used by node pointer. */ \ | |
85 | assert(((uintptr_t)(a_node) & 0x1) == 0); \ | |
86 | rbtn_left_set(a_type, a_field, (a_node), NULL); \ | |
87 | rbtn_right_set(a_type, a_field, (a_node), NULL); \ | |
88 | rbtn_red_set(a_type, a_field, (a_node)); \ | |
89 | } while (0) | |
970d7e83 LB |
90 | #else |
91 | /* Right accessors. */ | |
92 | #define rbtn_right_get(a_type, a_field, a_node) \ | |
93 | ((a_node)->a_field.rbn_right) | |
94 | #define rbtn_right_set(a_type, a_field, a_node, a_right) do { \ | |
95 | (a_node)->a_field.rbn_right = a_right; \ | |
96 | } while (0) | |
97 | ||
98 | /* Color accessors. */ | |
99 | #define rbtn_red_get(a_type, a_field, a_node) \ | |
100 | ((a_node)->a_field.rbn_red) | |
101 | #define rbtn_color_set(a_type, a_field, a_node, a_red) do { \ | |
102 | (a_node)->a_field.rbn_red = (a_red); \ | |
103 | } while (0) | |
104 | #define rbtn_red_set(a_type, a_field, a_node) do { \ | |
105 | (a_node)->a_field.rbn_red = true; \ | |
106 | } while (0) | |
107 | #define rbtn_black_set(a_type, a_field, a_node) do { \ | |
108 | (a_node)->a_field.rbn_red = false; \ | |
109 | } while (0) | |
970d7e83 LB |
110 | |
111 | /* Node initializer. */ | |
112 | #define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \ | |
54a0048b SL |
113 | rbtn_left_set(a_type, a_field, (a_node), NULL); \ |
114 | rbtn_right_set(a_type, a_field, (a_node), NULL); \ | |
970d7e83 LB |
115 | rbtn_red_set(a_type, a_field, (a_node)); \ |
116 | } while (0) | |
54a0048b | 117 | #endif |
970d7e83 LB |
118 | |
119 | /* Tree initializer. */ | |
120 | #define rb_new(a_type, a_field, a_rbt) do { \ | |
54a0048b | 121 | (a_rbt)->rbt_root = NULL; \ |
970d7e83 LB |
122 | } while (0) |
123 | ||
124 | /* Internal utility macros. */ | |
125 | #define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \ | |
126 | (r_node) = (a_root); \ | |
54a0048b | 127 | if ((r_node) != NULL) { \ |
970d7e83 | 128 | for (; \ |
54a0048b | 129 | rbtn_left_get(a_type, a_field, (r_node)) != NULL; \ |
970d7e83 LB |
130 | (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \ |
131 | } \ | |
132 | } \ | |
133 | } while (0) | |
134 | ||
135 | #define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \ | |
136 | (r_node) = (a_root); \ | |
54a0048b SL |
137 | if ((r_node) != NULL) { \ |
138 | for (; rbtn_right_get(a_type, a_field, (r_node)) != NULL; \ | |
139 | (r_node) = rbtn_right_get(a_type, a_field, (r_node))) { \ | |
970d7e83 LB |
140 | } \ |
141 | } \ | |
142 | } while (0) | |
143 | ||
144 | #define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \ | |
145 | (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \ | |
146 | rbtn_right_set(a_type, a_field, (a_node), \ | |
147 | rbtn_left_get(a_type, a_field, (r_node))); \ | |
148 | rbtn_left_set(a_type, a_field, (r_node), (a_node)); \ | |
149 | } while (0) | |
150 | ||
151 | #define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \ | |
152 | (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \ | |
153 | rbtn_left_set(a_type, a_field, (a_node), \ | |
154 | rbtn_right_get(a_type, a_field, (r_node))); \ | |
155 | rbtn_right_set(a_type, a_field, (r_node), (a_node)); \ | |
156 | } while (0) | |
157 | ||
158 | /* | |
159 | * The rb_proto() macro generates function prototypes that correspond to the | |
160 | * functions generated by an equivalently parameterized call to rb_gen(). | |
161 | */ | |
162 | ||
163 | #define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \ | |
164 | a_attr void \ | |
165 | a_prefix##new(a_rbt_type *rbtree); \ | |
1a4d82fc JJ |
166 | a_attr bool \ |
167 | a_prefix##empty(a_rbt_type *rbtree); \ | |
970d7e83 LB |
168 | a_attr a_type * \ |
169 | a_prefix##first(a_rbt_type *rbtree); \ | |
170 | a_attr a_type * \ | |
171 | a_prefix##last(a_rbt_type *rbtree); \ | |
172 | a_attr a_type * \ | |
173 | a_prefix##next(a_rbt_type *rbtree, a_type *node); \ | |
174 | a_attr a_type * \ | |
175 | a_prefix##prev(a_rbt_type *rbtree, a_type *node); \ | |
176 | a_attr a_type * \ | |
54a0048b | 177 | a_prefix##search(a_rbt_type *rbtree, const a_type *key); \ |
970d7e83 | 178 | a_attr a_type * \ |
54a0048b | 179 | a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key); \ |
970d7e83 | 180 | a_attr a_type * \ |
54a0048b | 181 | a_prefix##psearch(a_rbt_type *rbtree, const a_type *key); \ |
970d7e83 LB |
182 | a_attr void \ |
183 | a_prefix##insert(a_rbt_type *rbtree, a_type *node); \ | |
184 | a_attr void \ | |
185 | a_prefix##remove(a_rbt_type *rbtree, a_type *node); \ | |
186 | a_attr a_type * \ | |
187 | a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ | |
188 | a_rbt_type *, a_type *, void *), void *arg); \ | |
189 | a_attr a_type * \ | |
190 | a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ | |
54a0048b SL |
191 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); \ |
192 | a_attr void \ | |
193 | a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ | |
194 | void *arg); | |
970d7e83 LB |
195 | |
196 | /* | |
197 | * The rb_gen() macro generates a type-specific red-black tree implementation, | |
198 | * based on the above cpp macros. | |
199 | * | |
200 | * Arguments: | |
201 | * | |
202 | * a_attr : Function attribute for generated functions (ex: static). | |
203 | * a_prefix : Prefix for generated functions (ex: ex_). | |
204 | * a_rb_type : Type for red-black tree data structure (ex: ex_t). | |
205 | * a_type : Type for red-black tree node data structure (ex: ex_node_t). | |
206 | * a_field : Name of red-black tree node linkage (ex: ex_link). | |
207 | * a_cmp : Node comparison function name, with the following prototype: | |
208 | * int (a_cmp *)(a_type *a_node, a_type *a_other); | |
209 | * ^^^^^^ | |
210 | * or a_key | |
54a0048b | 211 | * Interpretation of comparison function return values: |
970d7e83 LB |
212 | * -1 : a_node < a_other |
213 | * 0 : a_node == a_other | |
214 | * 1 : a_node > a_other | |
215 | * In all cases, the a_node or a_key macro argument is the first | |
216 | * argument to the comparison function, which makes it possible | |
217 | * to write comparison functions that treat the first argument | |
218 | * specially. | |
219 | * | |
220 | * Assuming the following setup: | |
221 | * | |
222 | * typedef struct ex_node_s ex_node_t; | |
223 | * struct ex_node_s { | |
224 | * rb_node(ex_node_t) ex_link; | |
225 | * }; | |
226 | * typedef rb_tree(ex_node_t) ex_t; | |
227 | * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp) | |
228 | * | |
229 | * The following API is generated: | |
230 | * | |
231 | * static void | |
232 | * ex_new(ex_t *tree); | |
233 | * Description: Initialize a red-black tree structure. | |
234 | * Args: | |
235 | * tree: Pointer to an uninitialized red-black tree object. | |
236 | * | |
1a4d82fc JJ |
237 | * static bool |
238 | * ex_empty(ex_t *tree); | |
239 | * Description: Determine whether tree is empty. | |
240 | * Args: | |
241 | * tree: Pointer to an initialized red-black tree object. | |
242 | * Ret: True if tree is empty, false otherwise. | |
243 | * | |
970d7e83 LB |
244 | * static ex_node_t * |
245 | * ex_first(ex_t *tree); | |
246 | * static ex_node_t * | |
247 | * ex_last(ex_t *tree); | |
248 | * Description: Get the first/last node in tree. | |
249 | * Args: | |
250 | * tree: Pointer to an initialized red-black tree object. | |
251 | * Ret: First/last node in tree, or NULL if tree is empty. | |
252 | * | |
253 | * static ex_node_t * | |
254 | * ex_next(ex_t *tree, ex_node_t *node); | |
255 | * static ex_node_t * | |
256 | * ex_prev(ex_t *tree, ex_node_t *node); | |
257 | * Description: Get node's successor/predecessor. | |
258 | * Args: | |
259 | * tree: Pointer to an initialized red-black tree object. | |
260 | * node: A node in tree. | |
261 | * Ret: node's successor/predecessor in tree, or NULL if node is | |
262 | * last/first. | |
263 | * | |
264 | * static ex_node_t * | |
54a0048b | 265 | * ex_search(ex_t *tree, const ex_node_t *key); |
970d7e83 LB |
266 | * Description: Search for node that matches key. |
267 | * Args: | |
268 | * tree: Pointer to an initialized red-black tree object. | |
269 | * key : Search key. | |
270 | * Ret: Node in tree that matches key, or NULL if no match. | |
271 | * | |
272 | * static ex_node_t * | |
54a0048b | 273 | * ex_nsearch(ex_t *tree, const ex_node_t *key); |
970d7e83 | 274 | * static ex_node_t * |
54a0048b | 275 | * ex_psearch(ex_t *tree, const ex_node_t *key); |
970d7e83 LB |
276 | * Description: Search for node that matches key. If no match is found, |
277 | * return what would be key's successor/predecessor, were | |
278 | * key in tree. | |
279 | * Args: | |
280 | * tree: Pointer to an initialized red-black tree object. | |
281 | * key : Search key. | |
282 | * Ret: Node in tree that matches key, or if no match, hypothetical node's | |
283 | * successor/predecessor (NULL if no successor/predecessor). | |
284 | * | |
285 | * static void | |
286 | * ex_insert(ex_t *tree, ex_node_t *node); | |
287 | * Description: Insert node into tree. | |
288 | * Args: | |
289 | * tree: Pointer to an initialized red-black tree object. | |
290 | * node: Node to be inserted into tree. | |
291 | * | |
292 | * static void | |
293 | * ex_remove(ex_t *tree, ex_node_t *node); | |
294 | * Description: Remove node from tree. | |
295 | * Args: | |
296 | * tree: Pointer to an initialized red-black tree object. | |
297 | * node: Node in tree to be removed. | |
298 | * | |
299 | * static ex_node_t * | |
300 | * ex_iter(ex_t *tree, ex_node_t *start, ex_node_t *(*cb)(ex_t *, | |
301 | * ex_node_t *, void *), void *arg); | |
302 | * static ex_node_t * | |
303 | * ex_reverse_iter(ex_t *tree, ex_node_t *start, ex_node *(*cb)(ex_t *, | |
304 | * ex_node_t *, void *), void *arg); | |
305 | * Description: Iterate forward/backward over tree, starting at node. If | |
306 | * tree is modified, iteration must be immediately | |
307 | * terminated by the callback function that causes the | |
308 | * modification. | |
309 | * Args: | |
310 | * tree : Pointer to an initialized red-black tree object. | |
311 | * start: Node at which to start iteration, or NULL to start at | |
312 | * first/last node. | |
313 | * cb : Callback function, which is called for each node during | |
314 | * iteration. Under normal circumstances the callback function | |
315 | * should return NULL, which causes iteration to continue. If a | |
316 | * callback function returns non-NULL, iteration is immediately | |
317 | * terminated and the non-NULL return value is returned by the | |
318 | * iterator. This is useful for re-starting iteration after | |
319 | * modifying tree. | |
320 | * arg : Opaque pointer passed to cb(). | |
321 | * Ret: NULL if iteration completed, or the non-NULL callback return value | |
322 | * that caused termination of the iteration. | |
54a0048b SL |
323 | * |
324 | * static void | |
325 | * ex_destroy(ex_t *tree, void (*cb)(ex_node_t *, void *), void *arg); | |
326 | * Description: Iterate over the tree with post-order traversal, remove | |
327 | * each node, and run the callback if non-null. This is | |
328 | * used for destroying a tree without paying the cost to | |
329 | * rebalance it. The tree must not be otherwise altered | |
330 | * during traversal. | |
331 | * Args: | |
332 | * tree: Pointer to an initialized red-black tree object. | |
333 | * cb : Callback function, which, if non-null, is called for each node | |
334 | * during iteration. There is no way to stop iteration once it | |
335 | * has begun. | |
336 | * arg : Opaque pointer passed to cb(). | |
970d7e83 LB |
337 | */ |
338 | #define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \ | |
339 | a_attr void \ | |
340 | a_prefix##new(a_rbt_type *rbtree) { \ | |
341 | rb_new(a_type, a_field, rbtree); \ | |
342 | } \ | |
1a4d82fc JJ |
343 | a_attr bool \ |
344 | a_prefix##empty(a_rbt_type *rbtree) { \ | |
54a0048b | 345 | return (rbtree->rbt_root == NULL); \ |
1a4d82fc | 346 | } \ |
970d7e83 LB |
347 | a_attr a_type * \ |
348 | a_prefix##first(a_rbt_type *rbtree) { \ | |
349 | a_type *ret; \ | |
350 | rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ | |
970d7e83 LB |
351 | return (ret); \ |
352 | } \ | |
353 | a_attr a_type * \ | |
354 | a_prefix##last(a_rbt_type *rbtree) { \ | |
355 | a_type *ret; \ | |
356 | rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ | |
970d7e83 LB |
357 | return (ret); \ |
358 | } \ | |
359 | a_attr a_type * \ | |
360 | a_prefix##next(a_rbt_type *rbtree, a_type *node) { \ | |
361 | a_type *ret; \ | |
54a0048b | 362 | if (rbtn_right_get(a_type, a_field, node) != NULL) { \ |
970d7e83 LB |
363 | rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \ |
364 | a_field, node), ret); \ | |
365 | } else { \ | |
366 | a_type *tnode = rbtree->rbt_root; \ | |
54a0048b SL |
367 | assert(tnode != NULL); \ |
368 | ret = NULL; \ | |
970d7e83 LB |
369 | while (true) { \ |
370 | int cmp = (a_cmp)(node, tnode); \ | |
371 | if (cmp < 0) { \ | |
372 | ret = tnode; \ | |
373 | tnode = rbtn_left_get(a_type, a_field, tnode); \ | |
374 | } else if (cmp > 0) { \ | |
375 | tnode = rbtn_right_get(a_type, a_field, tnode); \ | |
376 | } else { \ | |
377 | break; \ | |
378 | } \ | |
54a0048b | 379 | assert(tnode != NULL); \ |
970d7e83 LB |
380 | } \ |
381 | } \ | |
970d7e83 LB |
382 | return (ret); \ |
383 | } \ | |
384 | a_attr a_type * \ | |
385 | a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \ | |
386 | a_type *ret; \ | |
54a0048b | 387 | if (rbtn_left_get(a_type, a_field, node) != NULL) { \ |
970d7e83 LB |
388 | rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \ |
389 | a_field, node), ret); \ | |
390 | } else { \ | |
391 | a_type *tnode = rbtree->rbt_root; \ | |
54a0048b SL |
392 | assert(tnode != NULL); \ |
393 | ret = NULL; \ | |
970d7e83 LB |
394 | while (true) { \ |
395 | int cmp = (a_cmp)(node, tnode); \ | |
396 | if (cmp < 0) { \ | |
397 | tnode = rbtn_left_get(a_type, a_field, tnode); \ | |
398 | } else if (cmp > 0) { \ | |
399 | ret = tnode; \ | |
400 | tnode = rbtn_right_get(a_type, a_field, tnode); \ | |
401 | } else { \ | |
402 | break; \ | |
403 | } \ | |
54a0048b | 404 | assert(tnode != NULL); \ |
970d7e83 LB |
405 | } \ |
406 | } \ | |
970d7e83 LB |
407 | return (ret); \ |
408 | } \ | |
409 | a_attr a_type * \ | |
54a0048b | 410 | a_prefix##search(a_rbt_type *rbtree, const a_type *key) { \ |
970d7e83 LB |
411 | a_type *ret; \ |
412 | int cmp; \ | |
413 | ret = rbtree->rbt_root; \ | |
54a0048b | 414 | while (ret != NULL \ |
970d7e83 LB |
415 | && (cmp = (a_cmp)(key, ret)) != 0) { \ |
416 | if (cmp < 0) { \ | |
417 | ret = rbtn_left_get(a_type, a_field, ret); \ | |
418 | } else { \ | |
419 | ret = rbtn_right_get(a_type, a_field, ret); \ | |
420 | } \ | |
421 | } \ | |
970d7e83 LB |
422 | return (ret); \ |
423 | } \ | |
424 | a_attr a_type * \ | |
54a0048b | 425 | a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key) { \ |
970d7e83 LB |
426 | a_type *ret; \ |
427 | a_type *tnode = rbtree->rbt_root; \ | |
54a0048b SL |
428 | ret = NULL; \ |
429 | while (tnode != NULL) { \ | |
970d7e83 LB |
430 | int cmp = (a_cmp)(key, tnode); \ |
431 | if (cmp < 0) { \ | |
432 | ret = tnode; \ | |
433 | tnode = rbtn_left_get(a_type, a_field, tnode); \ | |
434 | } else if (cmp > 0) { \ | |
435 | tnode = rbtn_right_get(a_type, a_field, tnode); \ | |
436 | } else { \ | |
437 | ret = tnode; \ | |
438 | break; \ | |
439 | } \ | |
440 | } \ | |
970d7e83 LB |
441 | return (ret); \ |
442 | } \ | |
443 | a_attr a_type * \ | |
54a0048b | 444 | a_prefix##psearch(a_rbt_type *rbtree, const a_type *key) { \ |
970d7e83 LB |
445 | a_type *ret; \ |
446 | a_type *tnode = rbtree->rbt_root; \ | |
54a0048b SL |
447 | ret = NULL; \ |
448 | while (tnode != NULL) { \ | |
970d7e83 LB |
449 | int cmp = (a_cmp)(key, tnode); \ |
450 | if (cmp < 0) { \ | |
451 | tnode = rbtn_left_get(a_type, a_field, tnode); \ | |
452 | } else if (cmp > 0) { \ | |
453 | ret = tnode; \ | |
454 | tnode = rbtn_right_get(a_type, a_field, tnode); \ | |
455 | } else { \ | |
456 | ret = tnode; \ | |
457 | break; \ | |
458 | } \ | |
459 | } \ | |
970d7e83 LB |
460 | return (ret); \ |
461 | } \ | |
462 | a_attr void \ | |
463 | a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ | |
464 | struct { \ | |
465 | a_type *node; \ | |
466 | int cmp; \ | |
467 | } path[sizeof(void *) << 4], *pathp; \ | |
468 | rbt_node_new(a_type, a_field, rbtree, node); \ | |
469 | /* Wind. */ \ | |
470 | path->node = rbtree->rbt_root; \ | |
54a0048b | 471 | for (pathp = path; pathp->node != NULL; pathp++) { \ |
970d7e83 LB |
472 | int cmp = pathp->cmp = a_cmp(node, pathp->node); \ |
473 | assert(cmp != 0); \ | |
474 | if (cmp < 0) { \ | |
475 | pathp[1].node = rbtn_left_get(a_type, a_field, \ | |
476 | pathp->node); \ | |
477 | } else { \ | |
478 | pathp[1].node = rbtn_right_get(a_type, a_field, \ | |
479 | pathp->node); \ | |
480 | } \ | |
481 | } \ | |
482 | pathp->node = node; \ | |
483 | /* Unwind. */ \ | |
484 | for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ | |
485 | a_type *cnode = pathp->node; \ | |
486 | if (pathp->cmp < 0) { \ | |
487 | a_type *left = pathp[1].node; \ | |
488 | rbtn_left_set(a_type, a_field, cnode, left); \ | |
489 | if (rbtn_red_get(a_type, a_field, left)) { \ | |
490 | a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ | |
54a0048b SL |
491 | if (leftleft != NULL && rbtn_red_get(a_type, a_field, \ |
492 | leftleft)) { \ | |
970d7e83 LB |
493 | /* Fix up 4-node. */ \ |
494 | a_type *tnode; \ | |
495 | rbtn_black_set(a_type, a_field, leftleft); \ | |
496 | rbtn_rotate_right(a_type, a_field, cnode, tnode); \ | |
497 | cnode = tnode; \ | |
498 | } \ | |
499 | } else { \ | |
500 | return; \ | |
501 | } \ | |
502 | } else { \ | |
503 | a_type *right = pathp[1].node; \ | |
504 | rbtn_right_set(a_type, a_field, cnode, right); \ | |
505 | if (rbtn_red_get(a_type, a_field, right)) { \ | |
506 | a_type *left = rbtn_left_get(a_type, a_field, cnode); \ | |
54a0048b SL |
507 | if (left != NULL && rbtn_red_get(a_type, a_field, \ |
508 | left)) { \ | |
970d7e83 LB |
509 | /* Split 4-node. */ \ |
510 | rbtn_black_set(a_type, a_field, left); \ | |
511 | rbtn_black_set(a_type, a_field, right); \ | |
512 | rbtn_red_set(a_type, a_field, cnode); \ | |
513 | } else { \ | |
514 | /* Lean left. */ \ | |
515 | a_type *tnode; \ | |
516 | bool tred = rbtn_red_get(a_type, a_field, cnode); \ | |
517 | rbtn_rotate_left(a_type, a_field, cnode, tnode); \ | |
518 | rbtn_color_set(a_type, a_field, tnode, tred); \ | |
519 | rbtn_red_set(a_type, a_field, cnode); \ | |
520 | cnode = tnode; \ | |
521 | } \ | |
522 | } else { \ | |
523 | return; \ | |
524 | } \ | |
525 | } \ | |
526 | pathp->node = cnode; \ | |
527 | } \ | |
528 | /* Set root, and make it black. */ \ | |
529 | rbtree->rbt_root = path->node; \ | |
530 | rbtn_black_set(a_type, a_field, rbtree->rbt_root); \ | |
531 | } \ | |
532 | a_attr void \ | |
533 | a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ | |
534 | struct { \ | |
535 | a_type *node; \ | |
536 | int cmp; \ | |
537 | } *pathp, *nodep, path[sizeof(void *) << 4]; \ | |
538 | /* Wind. */ \ | |
539 | nodep = NULL; /* Silence compiler warning. */ \ | |
540 | path->node = rbtree->rbt_root; \ | |
54a0048b | 541 | for (pathp = path; pathp->node != NULL; pathp++) { \ |
970d7e83 LB |
542 | int cmp = pathp->cmp = a_cmp(node, pathp->node); \ |
543 | if (cmp < 0) { \ | |
544 | pathp[1].node = rbtn_left_get(a_type, a_field, \ | |
545 | pathp->node); \ | |
546 | } else { \ | |
547 | pathp[1].node = rbtn_right_get(a_type, a_field, \ | |
548 | pathp->node); \ | |
549 | if (cmp == 0) { \ | |
550 | /* Find node's successor, in preparation for swap. */ \ | |
551 | pathp->cmp = 1; \ | |
552 | nodep = pathp; \ | |
54a0048b | 553 | for (pathp++; pathp->node != NULL; \ |
970d7e83 LB |
554 | pathp++) { \ |
555 | pathp->cmp = -1; \ | |
556 | pathp[1].node = rbtn_left_get(a_type, a_field, \ | |
557 | pathp->node); \ | |
558 | } \ | |
559 | break; \ | |
560 | } \ | |
561 | } \ | |
562 | } \ | |
563 | assert(nodep->node == node); \ | |
564 | pathp--; \ | |
565 | if (pathp->node != node) { \ | |
566 | /* Swap node with its successor. */ \ | |
567 | bool tred = rbtn_red_get(a_type, a_field, pathp->node); \ | |
568 | rbtn_color_set(a_type, a_field, pathp->node, \ | |
569 | rbtn_red_get(a_type, a_field, node)); \ | |
570 | rbtn_left_set(a_type, a_field, pathp->node, \ | |
571 | rbtn_left_get(a_type, a_field, node)); \ | |
572 | /* If node's successor is its right child, the following code */\ | |
573 | /* will do the wrong thing for the right child pointer. */\ | |
574 | /* However, it doesn't matter, because the pointer will be */\ | |
575 | /* properly set when the successor is pruned. */\ | |
576 | rbtn_right_set(a_type, a_field, pathp->node, \ | |
577 | rbtn_right_get(a_type, a_field, node)); \ | |
578 | rbtn_color_set(a_type, a_field, node, tred); \ | |
579 | /* The pruned leaf node's child pointers are never accessed */\ | |
580 | /* again, so don't bother setting them to nil. */\ | |
581 | nodep->node = pathp->node; \ | |
582 | pathp->node = node; \ | |
583 | if (nodep == path) { \ | |
584 | rbtree->rbt_root = nodep->node; \ | |
585 | } else { \ | |
586 | if (nodep[-1].cmp < 0) { \ | |
587 | rbtn_left_set(a_type, a_field, nodep[-1].node, \ | |
588 | nodep->node); \ | |
589 | } else { \ | |
590 | rbtn_right_set(a_type, a_field, nodep[-1].node, \ | |
591 | nodep->node); \ | |
592 | } \ | |
593 | } \ | |
594 | } else { \ | |
595 | a_type *left = rbtn_left_get(a_type, a_field, node); \ | |
54a0048b | 596 | if (left != NULL) { \ |
970d7e83 LB |
597 | /* node has no successor, but it has a left child. */\ |
598 | /* Splice node out, without losing the left child. */\ | |
1a4d82fc | 599 | assert(!rbtn_red_get(a_type, a_field, node)); \ |
970d7e83 LB |
600 | assert(rbtn_red_get(a_type, a_field, left)); \ |
601 | rbtn_black_set(a_type, a_field, left); \ | |
602 | if (pathp == path) { \ | |
603 | rbtree->rbt_root = left; \ | |
604 | } else { \ | |
605 | if (pathp[-1].cmp < 0) { \ | |
606 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ | |
607 | left); \ | |
608 | } else { \ | |
609 | rbtn_right_set(a_type, a_field, pathp[-1].node, \ | |
610 | left); \ | |
611 | } \ | |
612 | } \ | |
613 | return; \ | |
614 | } else if (pathp == path) { \ | |
615 | /* The tree only contained one node. */ \ | |
54a0048b | 616 | rbtree->rbt_root = NULL; \ |
970d7e83 LB |
617 | return; \ |
618 | } \ | |
619 | } \ | |
620 | if (rbtn_red_get(a_type, a_field, pathp->node)) { \ | |
621 | /* Prune red node, which requires no fixup. */ \ | |
622 | assert(pathp[-1].cmp < 0); \ | |
54a0048b | 623 | rbtn_left_set(a_type, a_field, pathp[-1].node, NULL); \ |
970d7e83 LB |
624 | return; \ |
625 | } \ | |
626 | /* The node to be pruned is black, so unwind until balance is */\ | |
627 | /* restored. */\ | |
54a0048b | 628 | pathp->node = NULL; \ |
970d7e83 LB |
629 | for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ |
630 | assert(pathp->cmp != 0); \ | |
631 | if (pathp->cmp < 0) { \ | |
632 | rbtn_left_set(a_type, a_field, pathp->node, \ | |
633 | pathp[1].node); \ | |
970d7e83 LB |
634 | if (rbtn_red_get(a_type, a_field, pathp->node)) { \ |
635 | a_type *right = rbtn_right_get(a_type, a_field, \ | |
636 | pathp->node); \ | |
637 | a_type *rightleft = rbtn_left_get(a_type, a_field, \ | |
638 | right); \ | |
639 | a_type *tnode; \ | |
54a0048b SL |
640 | if (rightleft != NULL && rbtn_red_get(a_type, a_field, \ |
641 | rightleft)) { \ | |
970d7e83 LB |
642 | /* In the following diagrams, ||, //, and \\ */\ |
643 | /* indicate the path to the removed node. */\ | |
644 | /* */\ | |
645 | /* || */\ | |
646 | /* pathp(r) */\ | |
647 | /* // \ */\ | |
648 | /* (b) (b) */\ | |
649 | /* / */\ | |
650 | /* (r) */\ | |
651 | /* */\ | |
652 | rbtn_black_set(a_type, a_field, pathp->node); \ | |
653 | rbtn_rotate_right(a_type, a_field, right, tnode); \ | |
654 | rbtn_right_set(a_type, a_field, pathp->node, tnode);\ | |
655 | rbtn_rotate_left(a_type, a_field, pathp->node, \ | |
656 | tnode); \ | |
657 | } else { \ | |
658 | /* || */\ | |
659 | /* pathp(r) */\ | |
660 | /* // \ */\ | |
661 | /* (b) (b) */\ | |
662 | /* / */\ | |
663 | /* (b) */\ | |
664 | /* */\ | |
665 | rbtn_rotate_left(a_type, a_field, pathp->node, \ | |
666 | tnode); \ | |
667 | } \ | |
668 | /* Balance restored, but rotation modified subtree */\ | |
669 | /* root. */\ | |
670 | assert((uintptr_t)pathp > (uintptr_t)path); \ | |
671 | if (pathp[-1].cmp < 0) { \ | |
672 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ | |
673 | tnode); \ | |
674 | } else { \ | |
675 | rbtn_right_set(a_type, a_field, pathp[-1].node, \ | |
676 | tnode); \ | |
677 | } \ | |
678 | return; \ | |
679 | } else { \ | |
680 | a_type *right = rbtn_right_get(a_type, a_field, \ | |
681 | pathp->node); \ | |
682 | a_type *rightleft = rbtn_left_get(a_type, a_field, \ | |
683 | right); \ | |
54a0048b SL |
684 | if (rightleft != NULL && rbtn_red_get(a_type, a_field, \ |
685 | rightleft)) { \ | |
970d7e83 LB |
686 | /* || */\ |
687 | /* pathp(b) */\ | |
688 | /* // \ */\ | |
689 | /* (b) (b) */\ | |
690 | /* / */\ | |
691 | /* (r) */\ | |
692 | a_type *tnode; \ | |
693 | rbtn_black_set(a_type, a_field, rightleft); \ | |
694 | rbtn_rotate_right(a_type, a_field, right, tnode); \ | |
695 | rbtn_right_set(a_type, a_field, pathp->node, tnode);\ | |
696 | rbtn_rotate_left(a_type, a_field, pathp->node, \ | |
697 | tnode); \ | |
698 | /* Balance restored, but rotation modified */\ | |
54a0048b | 699 | /* subtree root, which may actually be the tree */\ |
970d7e83 LB |
700 | /* root. */\ |
701 | if (pathp == path) { \ | |
702 | /* Set root. */ \ | |
703 | rbtree->rbt_root = tnode; \ | |
704 | } else { \ | |
705 | if (pathp[-1].cmp < 0) { \ | |
706 | rbtn_left_set(a_type, a_field, \ | |
707 | pathp[-1].node, tnode); \ | |
708 | } else { \ | |
709 | rbtn_right_set(a_type, a_field, \ | |
710 | pathp[-1].node, tnode); \ | |
711 | } \ | |
712 | } \ | |
713 | return; \ | |
714 | } else { \ | |
715 | /* || */\ | |
716 | /* pathp(b) */\ | |
717 | /* // \ */\ | |
718 | /* (b) (b) */\ | |
719 | /* / */\ | |
720 | /* (b) */\ | |
721 | a_type *tnode; \ | |
722 | rbtn_red_set(a_type, a_field, pathp->node); \ | |
723 | rbtn_rotate_left(a_type, a_field, pathp->node, \ | |
724 | tnode); \ | |
725 | pathp->node = tnode; \ | |
726 | } \ | |
727 | } \ | |
728 | } else { \ | |
729 | a_type *left; \ | |
730 | rbtn_right_set(a_type, a_field, pathp->node, \ | |
731 | pathp[1].node); \ | |
732 | left = rbtn_left_get(a_type, a_field, pathp->node); \ | |
733 | if (rbtn_red_get(a_type, a_field, left)) { \ | |
734 | a_type *tnode; \ | |
735 | a_type *leftright = rbtn_right_get(a_type, a_field, \ | |
736 | left); \ | |
737 | a_type *leftrightleft = rbtn_left_get(a_type, a_field, \ | |
738 | leftright); \ | |
54a0048b SL |
739 | if (leftrightleft != NULL && rbtn_red_get(a_type, \ |
740 | a_field, leftrightleft)) { \ | |
970d7e83 LB |
741 | /* || */\ |
742 | /* pathp(b) */\ | |
743 | /* / \\ */\ | |
744 | /* (r) (b) */\ | |
745 | /* \ */\ | |
746 | /* (b) */\ | |
747 | /* / */\ | |
748 | /* (r) */\ | |
749 | a_type *unode; \ | |
750 | rbtn_black_set(a_type, a_field, leftrightleft); \ | |
751 | rbtn_rotate_right(a_type, a_field, pathp->node, \ | |
752 | unode); \ | |
753 | rbtn_rotate_right(a_type, a_field, pathp->node, \ | |
754 | tnode); \ | |
755 | rbtn_right_set(a_type, a_field, unode, tnode); \ | |
756 | rbtn_rotate_left(a_type, a_field, unode, tnode); \ | |
757 | } else { \ | |
758 | /* || */\ | |
759 | /* pathp(b) */\ | |
760 | /* / \\ */\ | |
761 | /* (r) (b) */\ | |
762 | /* \ */\ | |
763 | /* (b) */\ | |
764 | /* / */\ | |
765 | /* (b) */\ | |
54a0048b | 766 | assert(leftright != NULL); \ |
970d7e83 LB |
767 | rbtn_red_set(a_type, a_field, leftright); \ |
768 | rbtn_rotate_right(a_type, a_field, pathp->node, \ | |
769 | tnode); \ | |
770 | rbtn_black_set(a_type, a_field, tnode); \ | |
771 | } \ | |
772 | /* Balance restored, but rotation modified subtree */\ | |
773 | /* root, which may actually be the tree root. */\ | |
774 | if (pathp == path) { \ | |
775 | /* Set root. */ \ | |
776 | rbtree->rbt_root = tnode; \ | |
777 | } else { \ | |
778 | if (pathp[-1].cmp < 0) { \ | |
779 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ | |
780 | tnode); \ | |
781 | } else { \ | |
782 | rbtn_right_set(a_type, a_field, pathp[-1].node, \ | |
783 | tnode); \ | |
784 | } \ | |
785 | } \ | |
786 | return; \ | |
787 | } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \ | |
788 | a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ | |
54a0048b SL |
789 | if (leftleft != NULL && rbtn_red_get(a_type, a_field, \ |
790 | leftleft)) { \ | |
970d7e83 LB |
791 | /* || */\ |
792 | /* pathp(r) */\ | |
793 | /* / \\ */\ | |
794 | /* (b) (b) */\ | |
795 | /* / */\ | |
796 | /* (r) */\ | |
797 | a_type *tnode; \ | |
798 | rbtn_black_set(a_type, a_field, pathp->node); \ | |
799 | rbtn_red_set(a_type, a_field, left); \ | |
800 | rbtn_black_set(a_type, a_field, leftleft); \ | |
801 | rbtn_rotate_right(a_type, a_field, pathp->node, \ | |
802 | tnode); \ | |
803 | /* Balance restored, but rotation modified */\ | |
804 | /* subtree root. */\ | |
805 | assert((uintptr_t)pathp > (uintptr_t)path); \ | |
806 | if (pathp[-1].cmp < 0) { \ | |
807 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ | |
808 | tnode); \ | |
809 | } else { \ | |
810 | rbtn_right_set(a_type, a_field, pathp[-1].node, \ | |
811 | tnode); \ | |
812 | } \ | |
813 | return; \ | |
814 | } else { \ | |
815 | /* || */\ | |
816 | /* pathp(r) */\ | |
817 | /* / \\ */\ | |
818 | /* (b) (b) */\ | |
819 | /* / */\ | |
820 | /* (b) */\ | |
821 | rbtn_red_set(a_type, a_field, left); \ | |
822 | rbtn_black_set(a_type, a_field, pathp->node); \ | |
823 | /* Balance restored. */ \ | |
824 | return; \ | |
825 | } \ | |
826 | } else { \ | |
827 | a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ | |
54a0048b SL |
828 | if (leftleft != NULL && rbtn_red_get(a_type, a_field, \ |
829 | leftleft)) { \ | |
970d7e83 LB |
830 | /* || */\ |
831 | /* pathp(b) */\ | |
832 | /* / \\ */\ | |
833 | /* (b) (b) */\ | |
834 | /* / */\ | |
835 | /* (r) */\ | |
836 | a_type *tnode; \ | |
837 | rbtn_black_set(a_type, a_field, leftleft); \ | |
838 | rbtn_rotate_right(a_type, a_field, pathp->node, \ | |
839 | tnode); \ | |
840 | /* Balance restored, but rotation modified */\ | |
841 | /* subtree root, which may actually be the tree */\ | |
842 | /* root. */\ | |
843 | if (pathp == path) { \ | |
844 | /* Set root. */ \ | |
845 | rbtree->rbt_root = tnode; \ | |
846 | } else { \ | |
847 | if (pathp[-1].cmp < 0) { \ | |
848 | rbtn_left_set(a_type, a_field, \ | |
849 | pathp[-1].node, tnode); \ | |
850 | } else { \ | |
851 | rbtn_right_set(a_type, a_field, \ | |
852 | pathp[-1].node, tnode); \ | |
853 | } \ | |
854 | } \ | |
855 | return; \ | |
856 | } else { \ | |
857 | /* || */\ | |
858 | /* pathp(b) */\ | |
859 | /* / \\ */\ | |
860 | /* (b) (b) */\ | |
861 | /* / */\ | |
862 | /* (b) */\ | |
863 | rbtn_red_set(a_type, a_field, left); \ | |
864 | } \ | |
865 | } \ | |
866 | } \ | |
867 | } \ | |
868 | /* Set root. */ \ | |
869 | rbtree->rbt_root = path->node; \ | |
1a4d82fc | 870 | assert(!rbtn_red_get(a_type, a_field, rbtree->rbt_root)); \ |
970d7e83 LB |
871 | } \ |
872 | a_attr a_type * \ | |
873 | a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \ | |
874 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ | |
54a0048b SL |
875 | if (node == NULL) { \ |
876 | return (NULL); \ | |
970d7e83 LB |
877 | } else { \ |
878 | a_type *ret; \ | |
879 | if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \ | |
54a0048b SL |
880 | a_field, node), cb, arg)) != NULL || (ret = cb(rbtree, node, \ |
881 | arg)) != NULL) { \ | |
970d7e83 LB |
882 | return (ret); \ |
883 | } \ | |
884 | return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ | |
885 | a_field, node), cb, arg)); \ | |
886 | } \ | |
887 | } \ | |
888 | a_attr a_type * \ | |
889 | a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \ | |
890 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ | |
891 | int cmp = a_cmp(start, node); \ | |
892 | if (cmp < 0) { \ | |
893 | a_type *ret; \ | |
894 | if ((ret = a_prefix##iter_start(rbtree, start, \ | |
54a0048b SL |
895 | rbtn_left_get(a_type, a_field, node), cb, arg)) != NULL || \ |
896 | (ret = cb(rbtree, node, arg)) != NULL) { \ | |
970d7e83 LB |
897 | return (ret); \ |
898 | } \ | |
899 | return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ | |
900 | a_field, node), cb, arg)); \ | |
901 | } else if (cmp > 0) { \ | |
902 | return (a_prefix##iter_start(rbtree, start, \ | |
903 | rbtn_right_get(a_type, a_field, node), cb, arg)); \ | |
904 | } else { \ | |
905 | a_type *ret; \ | |
906 | if ((ret = cb(rbtree, node, arg)) != NULL) { \ | |
907 | return (ret); \ | |
908 | } \ | |
909 | return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ | |
910 | a_field, node), cb, arg)); \ | |
911 | } \ | |
912 | } \ | |
913 | a_attr a_type * \ | |
914 | a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ | |
915 | a_rbt_type *, a_type *, void *), void *arg) { \ | |
916 | a_type *ret; \ | |
917 | if (start != NULL) { \ | |
918 | ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \ | |
919 | cb, arg); \ | |
920 | } else { \ | |
921 | ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\ | |
922 | } \ | |
970d7e83 LB |
923 | return (ret); \ |
924 | } \ | |
925 | a_attr a_type * \ | |
926 | a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \ | |
927 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ | |
54a0048b SL |
928 | if (node == NULL) { \ |
929 | return (NULL); \ | |
970d7e83 LB |
930 | } else { \ |
931 | a_type *ret; \ | |
932 | if ((ret = a_prefix##reverse_iter_recurse(rbtree, \ | |
54a0048b SL |
933 | rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL || \ |
934 | (ret = cb(rbtree, node, arg)) != NULL) { \ | |
970d7e83 LB |
935 | return (ret); \ |
936 | } \ | |
937 | return (a_prefix##reverse_iter_recurse(rbtree, \ | |
938 | rbtn_left_get(a_type, a_field, node), cb, arg)); \ | |
939 | } \ | |
940 | } \ | |
941 | a_attr a_type * \ | |
942 | a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \ | |
943 | a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \ | |
944 | void *arg) { \ | |
945 | int cmp = a_cmp(start, node); \ | |
946 | if (cmp > 0) { \ | |
947 | a_type *ret; \ | |
948 | if ((ret = a_prefix##reverse_iter_start(rbtree, start, \ | |
54a0048b SL |
949 | rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL || \ |
950 | (ret = cb(rbtree, node, arg)) != NULL) { \ | |
970d7e83 LB |
951 | return (ret); \ |
952 | } \ | |
953 | return (a_prefix##reverse_iter_recurse(rbtree, \ | |
954 | rbtn_left_get(a_type, a_field, node), cb, arg)); \ | |
955 | } else if (cmp < 0) { \ | |
956 | return (a_prefix##reverse_iter_start(rbtree, start, \ | |
957 | rbtn_left_get(a_type, a_field, node), cb, arg)); \ | |
958 | } else { \ | |
959 | a_type *ret; \ | |
960 | if ((ret = cb(rbtree, node, arg)) != NULL) { \ | |
961 | return (ret); \ | |
962 | } \ | |
963 | return (a_prefix##reverse_iter_recurse(rbtree, \ | |
964 | rbtn_left_get(a_type, a_field, node), cb, arg)); \ | |
965 | } \ | |
966 | } \ | |
967 | a_attr a_type * \ | |
968 | a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ | |
969 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ | |
970 | a_type *ret; \ | |
971 | if (start != NULL) { \ | |
972 | ret = a_prefix##reverse_iter_start(rbtree, start, \ | |
973 | rbtree->rbt_root, cb, arg); \ | |
974 | } else { \ | |
975 | ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \ | |
976 | cb, arg); \ | |
977 | } \ | |
970d7e83 | 978 | return (ret); \ |
54a0048b SL |
979 | } \ |
980 | a_attr void \ | |
981 | a_prefix##destroy_recurse(a_rbt_type *rbtree, a_type *node, void (*cb)( \ | |
982 | a_type *, void *), void *arg) { \ | |
983 | if (node == NULL) { \ | |
984 | return; \ | |
985 | } \ | |
986 | a_prefix##destroy_recurse(rbtree, rbtn_left_get(a_type, a_field, \ | |
987 | node), cb, arg); \ | |
988 | rbtn_left_set(a_type, a_field, (node), NULL); \ | |
989 | a_prefix##destroy_recurse(rbtree, rbtn_right_get(a_type, a_field, \ | |
990 | node), cb, arg); \ | |
991 | rbtn_right_set(a_type, a_field, (node), NULL); \ | |
992 | if (cb) { \ | |
993 | cb(node, arg); \ | |
994 | } \ | |
995 | } \ | |
996 | a_attr void \ | |
997 | a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ | |
998 | void *arg) { \ | |
999 | a_prefix##destroy_recurse(rbtree, rbtree->rbt_root, cb, arg); \ | |
1000 | rbtree->rbt_root = NULL; \ | |
970d7e83 LB |
1001 | } |
1002 | ||
1003 | #endif /* RB_H_ */ |