]> git.proxmox.com Git - rustc.git/blob - src/jemalloc/include/jemalloc/internal/rb.h
projects / rustc.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / jemalloc / include / jemalloc / internal / rb.h
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
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; \
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)
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)
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)
110
111 /* Node initializer. */
112 #define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \
113 rbtn_left_set(a_type, a_field, (a_node), NULL); \
114 rbtn_right_set(a_type, a_field, (a_node), NULL); \
115 rbtn_red_set(a_type, a_field, (a_node)); \
116 } while (0)
117 #endif
118
119 /* Tree initializer. */
120 #define rb_new(a_type, a_field, a_rbt) do { \
121 (a_rbt)->rbt_root = NULL; \
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); \
127 if ((r_node) != NULL) { \
128 for (; \
129 rbtn_left_get(a_type, a_field, (r_node)) != NULL; \
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); \
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))) { \
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); \
166 a_attr bool \
167 a_prefix##empty(a_rbt_type *rbtree); \
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 * \
177 a_prefix##search(a_rbt_type *rbtree, const a_type *key); \
178 a_attr a_type * \
179 a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key); \
180 a_attr a_type * \
181 a_prefix##psearch(a_rbt_type *rbtree, const a_type *key); \
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, \
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);
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
211 * Interpretation of comparison function return values:
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 *
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 *
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 *
265 * ex_search(ex_t *tree, const ex_node_t *key);
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 *
273 * ex_nsearch(ex_t *tree, const ex_node_t *key);
274 * static ex_node_t *
275 * ex_psearch(ex_t *tree, const ex_node_t *key);
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.
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().
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 } \
343 a_attr bool \
344 a_prefix##empty(a_rbt_type *rbtree) { \
345 return (rbtree->rbt_root == NULL); \
346 } \
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); \
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); \
357 return (ret); \
358 } \
359 a_attr a_type * \
360 a_prefix##next(a_rbt_type *rbtree, a_type *node) { \
361 a_type *ret; \
362 if (rbtn_right_get(a_type, a_field, node) != NULL) { \
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; \
367 assert(tnode != NULL); \
368 ret = NULL; \
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 } \
379 assert(tnode != NULL); \
380 } \
381 } \
382 return (ret); \
383 } \
384 a_attr a_type * \
385 a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \
386 a_type *ret; \
387 if (rbtn_left_get(a_type, a_field, node) != NULL) { \
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; \
392 assert(tnode != NULL); \
393 ret = NULL; \
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 } \
404 assert(tnode != NULL); \
405 } \
406 } \
407 return (ret); \
408 } \
409 a_attr a_type * \
410 a_prefix##search(a_rbt_type *rbtree, const a_type *key) { \
411 a_type *ret; \
412 int cmp; \
413 ret = rbtree->rbt_root; \
414 while (ret != NULL \
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 } \
422 return (ret); \
423 } \
424 a_attr a_type * \
425 a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key) { \
426 a_type *ret; \
427 a_type *tnode = rbtree->rbt_root; \
428 ret = NULL; \
429 while (tnode != NULL) { \
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 } \
441 return (ret); \
442 } \
443 a_attr a_type * \
444 a_prefix##psearch(a_rbt_type *rbtree, const a_type *key) { \
445 a_type *ret; \
446 a_type *tnode = rbtree->rbt_root; \
447 ret = NULL; \
448 while (tnode != NULL) { \
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 } \
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; \
471 for (pathp = path; pathp->node != NULL; pathp++) { \
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);\
491 if (leftleft != NULL && rbtn_red_get(a_type, a_field, \
492 leftleft)) { \
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); \
507 if (left != NULL && rbtn_red_get(a_type, a_field, \
508 left)) { \
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; \
541 for (pathp = path; pathp->node != NULL; pathp++) { \
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; \
553 for (pathp++; pathp->node != NULL; \
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); \
596 if (left != NULL) { \
597 /* node has no successor, but it has a left child. */\
598 /* Splice node out, without losing the left child. */\
599 assert(!rbtn_red_get(a_type, a_field, node)); \
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. */ \
616 rbtree->rbt_root = NULL; \
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); \
623 rbtn_left_set(a_type, a_field, pathp[-1].node, NULL); \
624 return; \
625 } \
626 /* The node to be pruned is black, so unwind until balance is */\
627 /* restored. */\
628 pathp->node = NULL; \
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); \
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; \
640 if (rightleft != NULL && rbtn_red_get(a_type, a_field, \
641 rightleft)) { \
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); \
684 if (rightleft != NULL && rbtn_red_get(a_type, a_field, \
685 rightleft)) { \
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 */\
699 /* subtree root, which may actually be the tree */\
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); \
739 if (leftrightleft != NULL && rbtn_red_get(a_type, \
740 a_field, leftrightleft)) { \
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) */\
766 assert(leftright != NULL); \
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);\
789 if (leftleft != NULL && rbtn_red_get(a_type, a_field, \
790 leftleft)) { \
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);\
828 if (leftleft != NULL && rbtn_red_get(a_type, a_field, \
829 leftleft)) { \
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; \
870 assert(!rbtn_red_get(a_type, a_field, rbtree->rbt_root)); \
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) { \
875 if (node == NULL) { \
876 return (NULL); \
877 } else { \
878 a_type *ret; \
879 if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \
880 a_field, node), cb, arg)) != NULL || (ret = cb(rbtree, node, \
881 arg)) != NULL) { \
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, \
895 rbtn_left_get(a_type, a_field, node), cb, arg)) != NULL || \
896 (ret = cb(rbtree, node, arg)) != NULL) { \
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 } \
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) { \
928 if (node == NULL) { \
929 return (NULL); \
930 } else { \
931 a_type *ret; \
932 if ((ret = a_prefix##reverse_iter_recurse(rbtree, \
933 rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL || \
934 (ret = cb(rbtree, node, arg)) != NULL) { \
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, \
949 rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL || \
950 (ret = cb(rbtree, node, arg)) != NULL) { \
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 } \
978 return (ret); \
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; \
1001 }
1002
1003 #endif /* RB_H_ */
backport for Debian buster