1#ifndef JEMALLOC_INTERNAL_RB_H
2#define JEMALLOC_INTERNAL_RB_H
3
4/*-
5 *******************************************************************************
6 *
7 * cpp macro implementation of left-leaning 2-3 red-black trees. Parent
8 * pointers are not used, and color bits are stored in the least significant
9 * bit of right-child pointers (if RB_COMPACT is defined), thus making node
10 * linkage as compact as is possible for red-black trees.
11 *
12 * Usage:
13 *
14 * #include <stdint.h>
15 * #include <stdbool.h>
16 * #define NDEBUG // (Optional, see assert(3).)
17 * #include <assert.h>
18 * #define RB_COMPACT // (Optional, embed color bits in right-child pointers.)
19 * #include <rb.h>
20 * ...
21 *
22 *******************************************************************************
23 */
24
25#ifndef __PGI
26#define RB_COMPACT
27#endif
28
29/*
30 * Each node in the RB tree consumes at least 1 byte of space (for the linkage
31 * if nothing else, so there are a maximum of sizeof(void *) << 3 rb tree nodes
32 * in any process (and thus, at most sizeof(void *) << 3 nodes in any rb tree).
33 * The choice of algorithm bounds the depth of a tree to twice the binary log of
34 * the number of elements in the tree; the following bound follows.
35 */
36#define RB_MAX_DEPTH (sizeof(void *) << 4)
37
38#ifdef RB_COMPACT
39/* Node structure. */
40#define rb_node(a_type) \
41struct { \
42 a_type *rbn_left; \
43 a_type *rbn_right_red; \
44}
45#else
46#define rb_node(a_type) \
47struct { \
48 a_type *rbn_left; \
49 a_type *rbn_right; \
50 bool rbn_red; \
51}
52#endif
53
54/* Root structure. */
55#define rb_tree(a_type) \
56struct { \
57 a_type *rbt_root; \
58}
59
60/* Left accessors. */
61#define rbtn_left_get(a_type, a_field, a_node) \
62 ((a_node)->a_field.rbn_left)
63#define rbtn_left_set(a_type, a_field, a_node, a_left) do { \
64 (a_node)->a_field.rbn_left = a_left; \
65} while (0)
66
67#ifdef RB_COMPACT
68/* Right accessors. */
69#define rbtn_right_get(a_type, a_field, a_node) \
70 ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \
71 & ((ssize_t)-2)))
72#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
73 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
74 | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \
75} while (0)
76
77/* Color accessors. */
78#define rbtn_red_get(a_type, a_field, a_node) \
79 ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \
80 & ((size_t)1)))
81#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
82 (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \
83 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \
84 | ((ssize_t)a_red)); \
85} while (0)
86#define rbtn_red_set(a_type, a_field, a_node) do { \
87 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \
88 (a_node)->a_field.rbn_right_red) | ((size_t)1)); \
89} while (0)
90#define rbtn_black_set(a_type, a_field, a_node) do { \
91 (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \
92 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \
93} while (0)
94
95/* Node initializer. */
96#define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \
97 /* Bookkeeping bit cannot be used by node pointer. */ \
98 assert(((uintptr_t)(a_node) & 0x1) == 0); \
99 rbtn_left_set(a_type, a_field, (a_node), NULL); \
100 rbtn_right_set(a_type, a_field, (a_node), NULL); \
101 rbtn_red_set(a_type, a_field, (a_node)); \
102} while (0)
103#else
104/* Right accessors. */
105#define rbtn_right_get(a_type, a_field, a_node) \
106 ((a_node)->a_field.rbn_right)
107#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
108 (a_node)->a_field.rbn_right = a_right; \
109} while (0)
110
111/* Color accessors. */
112#define rbtn_red_get(a_type, a_field, a_node) \
113 ((a_node)->a_field.rbn_red)
114#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
115 (a_node)->a_field.rbn_red = (a_red); \
116} while (0)
117#define rbtn_red_set(a_type, a_field, a_node) do { \
118 (a_node)->a_field.rbn_red = true; \
119} while (0)
120#define rbtn_black_set(a_type, a_field, a_node) do { \
121 (a_node)->a_field.rbn_red = false; \
122} while (0)
123
124/* Node initializer. */
125#define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \
126 rbtn_left_set(a_type, a_field, (a_node), NULL); \
127 rbtn_right_set(a_type, a_field, (a_node), NULL); \
128 rbtn_red_set(a_type, a_field, (a_node)); \
129} while (0)
130#endif
131
132/* Tree initializer. */
133#define rb_new(a_type, a_field, a_rbt) do { \
134 (a_rbt)->rbt_root = NULL; \
135} while (0)
136
137/* Internal utility macros. */
138#define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \
139 (r_node) = (a_root); \
140 if ((r_node) != NULL) { \
141 for (; \
142 rbtn_left_get(a_type, a_field, (r_node)) != NULL; \
143 (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \
144 } \
145 } \
146} while (0)
147
148#define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \
149 (r_node) = (a_root); \
150 if ((r_node) != NULL) { \
151 for (; rbtn_right_get(a_type, a_field, (r_node)) != NULL; \
152 (r_node) = rbtn_right_get(a_type, a_field, (r_node))) { \
153 } \
154 } \
155} while (0)
156
157#define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \
158 (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \
159 rbtn_right_set(a_type, a_field, (a_node), \
160 rbtn_left_get(a_type, a_field, (r_node))); \
161 rbtn_left_set(a_type, a_field, (r_node), (a_node)); \
162} while (0)
163
164#define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \
165 (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \
166 rbtn_left_set(a_type, a_field, (a_node), \
167 rbtn_right_get(a_type, a_field, (r_node))); \
168 rbtn_right_set(a_type, a_field, (r_node), (a_node)); \
169} while (0)
170
171#define rb_summarized_only_false(...)
172#define rb_summarized_only_true(...) __VA_ARGS__
173#define rb_empty_summarize(a_node, a_lchild, a_rchild) false
174
175/*
176 * The rb_proto() and rb_summarized_proto() macros generate function prototypes
177 * that correspond to the functions generated by an equivalently parameterized
178 * call to rb_gen() or rb_summarized_gen(), respectively.
179 */
180
181#define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \
182 rb_proto_impl(a_attr, a_prefix, a_rbt_type, a_type, false)
183#define rb_summarized_proto(a_attr, a_prefix, a_rbt_type, a_type) \
184 rb_proto_impl(a_attr, a_prefix, a_rbt_type, a_type, true)
185#define rb_proto_impl(a_attr, a_prefix, a_rbt_type, a_type, \
186 a_is_summarized) \
187a_attr void \
188a_prefix##new(a_rbt_type *rbtree); \
189a_attr bool \
190a_prefix##empty(a_rbt_type *rbtree); \
191a_attr a_type * \
192a_prefix##first(a_rbt_type *rbtree); \
193a_attr a_type * \
194a_prefix##last(a_rbt_type *rbtree); \
195a_attr a_type * \
196a_prefix##next(a_rbt_type *rbtree, a_type *node); \
197a_attr a_type * \
198a_prefix##prev(a_rbt_type *rbtree, a_type *node); \
199a_attr a_type * \
200a_prefix##search(a_rbt_type *rbtree, const a_type *key); \
201a_attr a_type * \
202a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key); \
203a_attr a_type * \
204a_prefix##psearch(a_rbt_type *rbtree, const a_type *key); \
205a_attr void \
206a_prefix##insert(a_rbt_type *rbtree, a_type *node); \
207a_attr void \
208a_prefix##remove(a_rbt_type *rbtree, a_type *node); \
209a_attr a_type * \
210a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
211 a_rbt_type *, a_type *, void *), void *arg); \
212a_attr a_type * \
213a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
214 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); \
215a_attr void \
216a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \
217 void *arg); \
218/* Extended API */ \
219rb_summarized_only_##a_is_summarized( \
220a_attr void \
221a_prefix##update_summaries(a_rbt_type *rbtree, a_type *node); \
222a_attr bool \
223a_prefix##empty_filtered(a_rbt_type *rbtree, \
224 bool (*filter_node)(void *, a_type *), \
225 bool (*filter_subtree)(void *, a_type *), \
226 void *filter_ctx); \
227a_attr a_type * \
228a_prefix##first_filtered(a_rbt_type *rbtree, \
229 bool (*filter_node)(void *, a_type *), \
230 bool (*filter_subtree)(void *, a_type *), \
231 void *filter_ctx); \
232a_attr a_type * \
233a_prefix##last_filtered(a_rbt_type *rbtree, \
234 bool (*filter_node)(void *, a_type *), \
235 bool (*filter_subtree)(void *, a_type *), \
236 void *filter_ctx); \
237a_attr a_type * \
238a_prefix##next_filtered(a_rbt_type *rbtree, a_type *node, \
239 bool (*filter_node)(void *, a_type *), \
240 bool (*filter_subtree)(void *, a_type *), \
241 void *filter_ctx); \
242a_attr a_type * \
243a_prefix##prev_filtered(a_rbt_type *rbtree, a_type *node, \
244 bool (*filter_node)(void *, a_type *), \
245 bool (*filter_subtree)(void *, a_type *), \
246 void *filter_ctx); \
247a_attr a_type * \
248a_prefix##search_filtered(a_rbt_type *rbtree, const a_type *key, \
249 bool (*filter_node)(void *, a_type *), \
250 bool (*filter_subtree)(void *, a_type *), \
251 void *filter_ctx); \
252a_attr a_type * \
253a_prefix##nsearch_filtered(a_rbt_type *rbtree, const a_type *key, \
254 bool (*filter_node)(void *, a_type *), \
255 bool (*filter_subtree)(void *, a_type *), \
256 void *filter_ctx); \
257a_attr a_type * \
258a_prefix##psearch_filtered(a_rbt_type *rbtree, const a_type *key, \
259 bool (*filter_node)(void *, a_type *), \
260 bool (*filter_subtree)(void *, a_type *), \
261 void *filter_ctx); \
262a_attr a_type * \
263a_prefix##iter_filtered(a_rbt_type *rbtree, a_type *start, \
264 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \
265 bool (*filter_node)(void *, a_type *), \
266 bool (*filter_subtree)(void *, a_type *), \
267 void *filter_ctx); \
268a_attr a_type * \
269a_prefix##reverse_iter_filtered(a_rbt_type *rbtree, a_type *start, \
270 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \
271 bool (*filter_node)(void *, a_type *), \
272 bool (*filter_subtree)(void *, a_type *), \
273 void *filter_ctx); \
274)
275
276/*
277 * The rb_gen() macro generates a type-specific red-black tree implementation,
278 * based on the above cpp macros.
279 * Arguments:
280 *
281 * a_attr:
282 * Function attribute for generated functions (ex: static).
283 * a_prefix:
284 * Prefix for generated functions (ex: ex_).
285 * a_rb_type:
286 * Type for red-black tree data structure (ex: ex_t).
287 * a_type:
288 * Type for red-black tree node data structure (ex: ex_node_t).
289 * a_field:
290 * Name of red-black tree node linkage (ex: ex_link).
291 * a_cmp:
292 * Node comparison function name, with the following prototype:
293 *
294 * int a_cmp(a_type *a_node, a_type *a_other);
295 * ^^^^^^
296 * or a_key
297 * Interpretation of comparison function return values:
298 * -1 : a_node < a_other
299 * 0 : a_node == a_other
300 * 1 : a_node > a_other
301 * In all cases, the a_node or a_key macro argument is the first argument to
302 * the comparison function, which makes it possible to write comparison
303 * functions that treat the first argument specially. a_cmp must be a total
304 * order on values inserted into the tree -- duplicates are not allowed.
305 *
306 * Assuming the following setup:
307 *
308 * typedef struct ex_node_s ex_node_t;
309 * struct ex_node_s {
310 * rb_node(ex_node_t) ex_link;
311 * };
312 * typedef rb_tree(ex_node_t) ex_t;
313 * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp)
314 *
315 * The following API is generated:
316 *
317 * static void
318 * ex_new(ex_t *tree);
319 * Description: Initialize a red-black tree structure.
320 * Args:
321 * tree: Pointer to an uninitialized red-black tree object.
322 *
323 * static bool
324 * ex_empty(ex_t *tree);
325 * Description: Determine whether tree is empty.
326 * Args:
327 * tree: Pointer to an initialized red-black tree object.
328 * Ret: True if tree is empty, false otherwise.
329 *
330 * static ex_node_t *
331 * ex_first(ex_t *tree);
332 * static ex_node_t *
333 * ex_last(ex_t *tree);
334 * Description: Get the first/last node in tree.
335 * Args:
336 * tree: Pointer to an initialized red-black tree object.
337 * Ret: First/last node in tree, or NULL if tree is empty.
338 *
339 * static ex_node_t *
340 * ex_next(ex_t *tree, ex_node_t *node);
341 * static ex_node_t *
342 * ex_prev(ex_t *tree, ex_node_t *node);
343 * Description: Get node's successor/predecessor.
344 * Args:
345 * tree: Pointer to an initialized red-black tree object.
346 * node: A node in tree.
347 * Ret: node's successor/predecessor in tree, or NULL if node is
348 * last/first.
349 *
350 * static ex_node_t *
351 * ex_search(ex_t *tree, const ex_node_t *key);
352 * Description: Search for node that matches key.
353 * Args:
354 * tree: Pointer to an initialized red-black tree object.
355 * key : Search key.
356 * Ret: Node in tree that matches key, or NULL if no match.
357 *
358 * static ex_node_t *
359 * ex_nsearch(ex_t *tree, const ex_node_t *key);
360 * static ex_node_t *
361 * ex_psearch(ex_t *tree, const ex_node_t *key);
362 * Description: Search for node that matches key. If no match is found,
363 * return what would be key's successor/predecessor, were
364 * key in tree.
365 * Args:
366 * tree: Pointer to an initialized red-black tree object.
367 * key : Search key.
368 * Ret: Node in tree that matches key, or if no match, hypothetical node's
369 * successor/predecessor (NULL if no successor/predecessor).
370 *
371 * static void
372 * ex_insert(ex_t *tree, ex_node_t *node);
373 * Description: Insert node into tree.
374 * Args:
375 * tree: Pointer to an initialized red-black tree object.
376 * node: Node to be inserted into tree.
377 *
378 * static void
379 * ex_remove(ex_t *tree, ex_node_t *node);
380 * Description: Remove node from tree.
381 * Args:
382 * tree: Pointer to an initialized red-black tree object.
383 * node: Node in tree to be removed.
384 *
385 * static ex_node_t *
386 * ex_iter(ex_t *tree, ex_node_t *start, ex_node_t *(*cb)(ex_t *,
387 * ex_node_t *, void *), void *arg);
388 * static ex_node_t *
389 * ex_reverse_iter(ex_t *tree, ex_node_t *start, ex_node *(*cb)(ex_t *,
390 * ex_node_t *, void *), void *arg);
391 * Description: Iterate forward/backward over tree, starting at node. If
392 * tree is modified, iteration must be immediately
393 * terminated by the callback function that causes the
394 * modification.
395 * Args:
396 * tree : Pointer to an initialized red-black tree object.
397 * start: Node at which to start iteration, or NULL to start at
398 * first/last node.
399 * cb : Callback function, which is called for each node during
400 * iteration. Under normal circumstances the callback function
401 * should return NULL, which causes iteration to continue. If a
402 * callback function returns non-NULL, iteration is immediately
403 * terminated and the non-NULL return value is returned by the
404 * iterator. This is useful for re-starting iteration after
405 * modifying tree.
406 * arg : Opaque pointer passed to cb().
407 * Ret: NULL if iteration completed, or the non-NULL callback return value
408 * that caused termination of the iteration.
409 *
410 * static void
411 * ex_destroy(ex_t *tree, void (*cb)(ex_node_t *, void *), void *arg);
412 * Description: Iterate over the tree with post-order traversal, remove
413 * each node, and run the callback if non-null. This is
414 * used for destroying a tree without paying the cost to
415 * rebalance it. The tree must not be otherwise altered
416 * during traversal.
417 * Args:
418 * tree: Pointer to an initialized red-black tree object.
419 * cb : Callback function, which, if non-null, is called for each node
420 * during iteration. There is no way to stop iteration once it
421 * has begun.
422 * arg : Opaque pointer passed to cb().
423 *
424 * The rb_summarized_gen() macro generates all the functions above, but has an
425 * expanded interface. In introduces the notion of summarizing subtrees, and of
426 * filtering searches in the tree according to the information contained in
427 * those summaries.
428 * The extra macro argument is:
429 * a_summarize:
430 * Tree summarization function name, with the following prototype:
431 *
432 * bool a_summarize(a_type *a_node, const a_type *a_left_child,
433 * const a_type *a_right_child);
434 *
435 * This function should update a_node with the summary of the subtree rooted
436 * there, using the data contained in it and the summaries in a_left_child
437 * and a_right_child. One or both of them may be NULL. When the tree
438 * changes due to an insertion or removal, it updates the summaries of all
439 * nodes whose subtrees have changed (always updating the summaries of
440 * children before their parents). If the user alters a node in the tree in
441 * a way that may change its summary, they can call the generated
442 * update_summaries function to bubble up the summary changes to the root.
443 * It should return true if the summary changed (or may have changed), and
444 * false if it didn't (which will allow the implementation to terminate
445 * "bubbling up" the summaries early).
446 * As the parameter names indicate, the children are ordered as they are in
447 * the tree, a_left_child, if it is not NULL, compares less than a_node,
448 * which in turn compares less than a_right_child (if a_right_child is not
449 * NULL).
450 *
451 * Using the same setup as above but replacing the macro with
452 * rb_summarized_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp,
453 * ex_summarize)
454 *
455 * Generates all the previous functions, but adds some more:
456 *
457 * static void
458 * ex_update_summaries(ex_t *tree, ex_node_t *node);
459 * Description: Recompute all summaries of ancestors of node.
460 * Args:
461 * tree: Pointer to an initialized red-black tree object.
462 * node: The element of the tree whose summary may have changed.
463 *
464 * For each of ex_empty, ex_first, ex_last, ex_next, ex_prev, ex_search,
465 * ex_nsearch, ex_psearch, ex_iter, and ex_reverse_iter, an additional function
466 * is generated as well, with the suffix _filtered (e.g. ex_empty_filtered,
467 * ex_first_filtered, etc.). These use the concept of a "filter"; a binary
468 * property some node either satisfies or does not satisfy. Clever use of the
469 * a_summary argument to rb_summarized_gen can allow efficient computation of
470 * these predicates across whole subtrees of the tree.
471 * The extended API functions accept three additional arguments after the
472 * arguments to the corresponding non-extended equivalent.
473 *
474 * ex_fn(..., bool (*filter_node)(void *, ex_node_t *),
475 * bool (*filter_subtree)(void *, ex_node_t *), void *filter_ctx);
476 * filter_node : Returns true if the node passes the filter.
477 * filter_subtree : Returns true if some node in the subtree rooted at
478 * node passes the filter.
479 * filter_ctx : A context argument passed to the filters.
480 *
481 * For a more concrete example of summarizing and filtering, suppose we're using
482 * the red-black tree to track a set of integers:
483 *
484 * struct ex_node_s {
485 * rb_node(ex_node_t) ex_link;
486 * unsigned data;
487 * };
488 *
489 * Suppose, for some application-specific reason, we want to be able to quickly
490 * find numbers in the set which are divisible by large powers of 2 (say, for
491 * aligned allocation purposes). We augment the node with a summary field:
492 *
493 * struct ex_node_s {
494 * rb_node(ex_node_t) ex_link;
495 * unsigned data;
496 * unsigned max_subtree_ffs;
497 * }
498 *
499 * and define our summarization function as follows:
500 *
501 * bool
502 * ex_summarize(ex_node_t *node, const ex_node_t *lchild,
503 * const ex_node_t *rchild) {
504 * unsigned new_max_subtree_ffs = ffs(node->data);
505 * if (lchild != NULL && lchild->max_subtree_ffs > new_max_subtree_ffs) {
506 * new_max_subtree_ffs = lchild->max_subtree_ffs;
507 * }
508 * if (rchild != NULL && rchild->max_subtree_ffs > new_max_subtree_ffs) {
509 * new_max_subtree_ffs = rchild->max_subtree_ffs;
510 * }
511 * bool changed = (node->max_subtree_ffs != new_max_subtree_ffs)
512 * node->max_subtree_ffs = new_max_subtree_ffs;
513 * // This could be "return true" without any correctness or big-O
514 * // performance changes; but practically, precisely reporting summary
515 * // changes reduces the amount of work that has to be done when "bubbling
516 * // up" summary changes.
517 * return changed;
518 * }
519 *
520 * We can now implement our filter functions as follows:
521 * bool
522 * ex_filter_node(void *filter_ctx, ex_node_t *node) {
523 * unsigned required_ffs = *(unsigned *)filter_ctx;
524 * return ffs(node->data) >= required_ffs;
525 * }
526 * bool
527 * ex_filter_subtree(void *filter_ctx, ex_node_t *node) {
528 * unsigned required_ffs = *(unsigned *)filter_ctx;
529 * return node->max_subtree_ffs >= required_ffs;
530 * }
531 *
532 * We can now easily search for, e.g., the smallest integer in the set that's
533 * divisible by 128:
534 * ex_node_t *
535 * find_div_128(ex_tree_t *tree) {
536 * unsigned min_ffs = 7;
537 * return ex_first_filtered(tree, &ex_filter_node, &ex_filter_subtree,
538 * &min_ffs);
539 * }
540 *
541 * We could with similar ease:
542 * - Fnd the next multiple of 128 in the set that's larger than 12345 (with
543 * ex_nsearch_filtered)
544 * - Iterate over just those multiples of 64 that are in the set (with
545 * ex_iter_filtered)
546 * - Determine if the set contains any multiples of 1024 (with
547 * ex_empty_filtered).
548 *
549 * Some possibly subtle API notes:
550 * - The node argument to ex_next_filtered and ex_prev_filtered need not pass
551 * the filter; it will find the next/prev node that passes the filter.
552 * - ex_search_filtered will fail even for a node in the tree, if that node does
553 * not pass the filter. ex_psearch_filtered and ex_nsearch_filtered behave
554 * similarly; they may return a node larger/smaller than the key, even if a
555 * node equivalent to the key is in the tree (but does not pass the filter).
556 * - Similarly, if the start argument to a filtered iteration function does not
557 * pass the filter, the callback won't be invoked on it.
558 *
559 * These should make sense after a moment's reflection; each post-condition is
560 * the same as with the unfiltered version, with the added constraint that the
561 * returned node must pass the filter.
562 */
563#define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \
564 rb_gen_impl(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp, \
565 rb_empty_summarize, false)
566#define rb_summarized_gen(a_attr, a_prefix, a_rbt_type, a_type, \
567 a_field, a_cmp, a_summarize) \
568 rb_gen_impl(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp, \
569 a_summarize, true)
570
571#define rb_gen_impl(a_attr, a_prefix, a_rbt_type, a_type, \
572 a_field, a_cmp, a_summarize, a_is_summarized) \
573typedef struct { \
574 a_type *node; \
575 int cmp; \
576} a_prefix##path_entry_t; \
577static inline void \
578a_prefix##summarize_range(a_prefix##path_entry_t *rfirst, \
579 a_prefix##path_entry_t *rlast) { \
580 while ((uintptr_t)rlast >= (uintptr_t)rfirst) { \
581 a_type *node = rlast->node; \
582 /* Avoid a warning when a_summarize is rb_empty_summarize. */ \
583 (void)node; \
584 bool changed = a_summarize(node, rbtn_left_get(a_type, a_field, \
585 node), rbtn_right_get(a_type, a_field, node)); \
586 if (!changed) { \
587 break; \
588 } \
589 rlast--; \
590 } \
591} \
592/* On the remove pathways, we sometimes swap the node being removed */\
593/* and its first successor; in such cases we need to do two range */\
594/* updates; one from the node to its (former) swapped successor, the */\
595/* next from that successor to the root (with either allowed to */\
596/* bail out early if appropriate. */\
597static inline void \
598a_prefix##summarize_swapped_range(a_prefix##path_entry_t *rfirst, \
599 a_prefix##path_entry_t *rlast, a_prefix##path_entry_t *swap_loc) { \
600 if (swap_loc == NULL || rlast <= swap_loc) { \
601 a_prefix##summarize_range(rfirst, rlast); \
602 } else { \
603 a_prefix##summarize_range(swap_loc + 1, rlast); \
604 (void)a_summarize(swap_loc->node, \
605 rbtn_left_get(a_type, a_field, swap_loc->node), \
606 rbtn_right_get(a_type, a_field, swap_loc->node)); \
607 a_prefix##summarize_range(rfirst, swap_loc - 1); \
608 } \
609} \
610a_attr void \
611a_prefix##new(a_rbt_type *rbtree) { \
612 rb_new(a_type, a_field, rbtree); \
613} \
614a_attr bool \
615a_prefix##empty(a_rbt_type *rbtree) { \
616 return (rbtree->rbt_root == NULL); \
617} \
618a_attr a_type * \
619a_prefix##first(a_rbt_type *rbtree) { \
620 a_type *ret; \
621 rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
622 return ret; \
623} \
624a_attr a_type * \
625a_prefix##last(a_rbt_type *rbtree) { \
626 a_type *ret; \
627 rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
628 return ret; \
629} \
630a_attr a_type * \
631a_prefix##next(a_rbt_type *rbtree, a_type *node) { \
632 a_type *ret; \
633 if (rbtn_right_get(a_type, a_field, node) != NULL) { \
634 rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \
635 a_field, node), ret); \
636 } else { \
637 a_type *tnode = rbtree->rbt_root; \
638 assert(tnode != NULL); \
639 ret = NULL; \
640 while (true) { \
641 int cmp = (a_cmp)(node, tnode); \
642 if (cmp < 0) { \
643 ret = tnode; \
644 tnode = rbtn_left_get(a_type, a_field, tnode); \
645 } else if (cmp > 0) { \
646 tnode = rbtn_right_get(a_type, a_field, tnode); \
647 } else { \
648 break; \
649 } \
650 assert(tnode != NULL); \
651 } \
652 } \
653 return ret; \
654} \
655a_attr a_type * \
656a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \
657 a_type *ret; \
658 if (rbtn_left_get(a_type, a_field, node) != NULL) { \
659 rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \
660 a_field, node), ret); \
661 } else { \
662 a_type *tnode = rbtree->rbt_root; \
663 assert(tnode != NULL); \
664 ret = NULL; \
665 while (true) { \
666 int cmp = (a_cmp)(node, tnode); \
667 if (cmp < 0) { \
668 tnode = rbtn_left_get(a_type, a_field, tnode); \
669 } else if (cmp > 0) { \
670 ret = tnode; \
671 tnode = rbtn_right_get(a_type, a_field, tnode); \
672 } else { \
673 break; \
674 } \
675 assert(tnode != NULL); \
676 } \
677 } \
678 return ret; \
679} \
680a_attr a_type * \
681a_prefix##search(a_rbt_type *rbtree, const a_type *key) { \
682 a_type *ret; \
683 int cmp; \
684 ret = rbtree->rbt_root; \
685 while (ret != NULL \
686 && (cmp = (a_cmp)(key, ret)) != 0) { \
687 if (cmp < 0) { \
688 ret = rbtn_left_get(a_type, a_field, ret); \
689 } else { \
690 ret = rbtn_right_get(a_type, a_field, ret); \
691 } \
692 } \
693 return ret; \
694} \
695a_attr a_type * \
696a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key) { \
697 a_type *ret; \
698 a_type *tnode = rbtree->rbt_root; \
699 ret = NULL; \
700 while (tnode != NULL) { \
701 int cmp = (a_cmp)(key, tnode); \
702 if (cmp < 0) { \
703 ret = tnode; \
704 tnode = rbtn_left_get(a_type, a_field, tnode); \
705 } else if (cmp > 0) { \
706 tnode = rbtn_right_get(a_type, a_field, tnode); \
707 } else { \
708 ret = tnode; \
709 break; \
710 } \
711 } \
712 return ret; \
713} \
714a_attr a_type * \
715a_prefix##psearch(a_rbt_type *rbtree, const a_type *key) { \
716 a_type *ret; \
717 a_type *tnode = rbtree->rbt_root; \
718 ret = NULL; \
719 while (tnode != NULL) { \
720 int cmp = (a_cmp)(key, tnode); \
721 if (cmp < 0) { \
722 tnode = rbtn_left_get(a_type, a_field, tnode); \
723 } else if (cmp > 0) { \
724 ret = tnode; \
725 tnode = rbtn_right_get(a_type, a_field, tnode); \
726 } else { \
727 ret = tnode; \
728 break; \
729 } \
730 } \
731 return ret; \
732} \
733a_attr void \
734a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \
735 a_prefix##path_entry_t path[RB_MAX_DEPTH]; \
736 a_prefix##path_entry_t *pathp; \
737 rbt_node_new(a_type, a_field, rbtree, node); \
738 /* Wind. */ \
739 path->node = rbtree->rbt_root; \
740 for (pathp = path; pathp->node != NULL; pathp++) { \
741 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
742 assert(cmp != 0); \
743 if (cmp < 0) { \
744 pathp[1].node = rbtn_left_get(a_type, a_field, \
745 pathp->node); \
746 } else { \
747 pathp[1].node = rbtn_right_get(a_type, a_field, \
748 pathp->node); \
749 } \
750 } \
751 pathp->node = node; \
752 /* A loop invariant we maintain is that all nodes with */\
753 /* out-of-date summaries live in path[0], path[1], ..., *pathp. */\
754 /* To maintain this, we have to summarize node, since we */\
755 /* decrement pathp before the first iteration. */\
756 assert(rbtn_left_get(a_type, a_field, node) == NULL); \
757 assert(rbtn_right_get(a_type, a_field, node) == NULL); \
758 (void)a_summarize(node, NULL, NULL); \
759 /* Unwind. */ \
760 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
761 a_type *cnode = pathp->node; \
762 if (pathp->cmp < 0) { \
763 a_type *left = pathp[1].node; \
764 rbtn_left_set(a_type, a_field, cnode, left); \
765 if (rbtn_red_get(a_type, a_field, left)) { \
766 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
767 if (leftleft != NULL && rbtn_red_get(a_type, a_field, \
768 leftleft)) { \
769 /* Fix up 4-node. */ \
770 a_type *tnode; \
771 rbtn_black_set(a_type, a_field, leftleft); \
772 rbtn_rotate_right(a_type, a_field, cnode, tnode); \
773 (void)a_summarize(cnode, \
774 rbtn_left_get(a_type, a_field, cnode), \
775 rbtn_right_get(a_type, a_field, cnode)); \
776 cnode = tnode; \
777 } \
778 } else { \
779 a_prefix##summarize_range(path, pathp); \
780 return; \
781 } \
782 } else { \
783 a_type *right = pathp[1].node; \
784 rbtn_right_set(a_type, a_field, cnode, right); \
785 if (rbtn_red_get(a_type, a_field, right)) { \
786 a_type *left = rbtn_left_get(a_type, a_field, cnode); \
787 if (left != NULL && rbtn_red_get(a_type, a_field, \
788 left)) { \
789 /* Split 4-node. */ \
790 rbtn_black_set(a_type, a_field, left); \
791 rbtn_black_set(a_type, a_field, right); \
792 rbtn_red_set(a_type, a_field, cnode); \
793 } else { \
794 /* Lean left. */ \
795 a_type *tnode; \
796 bool tred = rbtn_red_get(a_type, a_field, cnode); \
797 rbtn_rotate_left(a_type, a_field, cnode, tnode); \
798 rbtn_color_set(a_type, a_field, tnode, tred); \
799 rbtn_red_set(a_type, a_field, cnode); \
800 (void)a_summarize(cnode, \
801 rbtn_left_get(a_type, a_field, cnode), \
802 rbtn_right_get(a_type, a_field, cnode)); \
803 cnode = tnode; \
804 } \
805 } else { \
806 a_prefix##summarize_range(path, pathp); \
807 return; \
808 } \
809 } \
810 pathp->node = cnode; \
811 (void)a_summarize(cnode, \
812 rbtn_left_get(a_type, a_field, cnode), \
813 rbtn_right_get(a_type, a_field, cnode)); \
814 } \
815 /* Set root, and make it black. */ \
816 rbtree->rbt_root = path->node; \
817 rbtn_black_set(a_type, a_field, rbtree->rbt_root); \
818} \
819a_attr void \
820a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \
821 a_prefix##path_entry_t path[RB_MAX_DEPTH]; \
822 a_prefix##path_entry_t *pathp; \
823 a_prefix##path_entry_t *nodep; \
824 a_prefix##path_entry_t *swap_loc; \
825 /* This is a "real" sentinel -- NULL means we didn't swap the */\
826 /* node to be pruned with one of its successors, and so */\
827 /* summarization can terminate early whenever some summary */\
828 /* doesn't change. */\
829 swap_loc = NULL; \
830 /* This is just to silence a compiler warning. */ \
831 nodep = NULL; \
832 /* Wind. */ \
833 path->node = rbtree->rbt_root; \
834 for (pathp = path; pathp->node != NULL; pathp++) { \
835 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
836 if (cmp < 0) { \
837 pathp[1].node = rbtn_left_get(a_type, a_field, \
838 pathp->node); \
839 } else { \
840 pathp[1].node = rbtn_right_get(a_type, a_field, \
841 pathp->node); \
842 if (cmp == 0) { \
843 /* Find node's successor, in preparation for swap. */ \
844 pathp->cmp = 1; \
845 nodep = pathp; \
846 for (pathp++; pathp->node != NULL; pathp++) { \
847 pathp->cmp = -1; \
848 pathp[1].node = rbtn_left_get(a_type, a_field, \
849 pathp->node); \
850 } \
851 break; \
852 } \
853 } \
854 } \
855 assert(nodep->node == node); \
856 pathp--; \
857 if (pathp->node != node) { \
858 /* Swap node with its successor. */ \
859 swap_loc = nodep; \
860 bool tred = rbtn_red_get(a_type, a_field, pathp->node); \
861 rbtn_color_set(a_type, a_field, pathp->node, \
862 rbtn_red_get(a_type, a_field, node)); \
863 rbtn_left_set(a_type, a_field, pathp->node, \
864 rbtn_left_get(a_type, a_field, node)); \
865 /* If node's successor is its right child, the following code */\
866 /* will do the wrong thing for the right child pointer. */\
867 /* However, it doesn't matter, because the pointer will be */\
868 /* properly set when the successor is pruned. */\
869 rbtn_right_set(a_type, a_field, pathp->node, \
870 rbtn_right_get(a_type, a_field, node)); \
871 rbtn_color_set(a_type, a_field, node, tred); \
872 /* The pruned leaf node's child pointers are never accessed */\
873 /* again, so don't bother setting them to nil. */\
874 nodep->node = pathp->node; \
875 pathp->node = node; \
876 if (nodep == path) { \
877 rbtree->rbt_root = nodep->node; \
878 } else { \
879 if (nodep[-1].cmp < 0) { \
880 rbtn_left_set(a_type, a_field, nodep[-1].node, \
881 nodep->node); \
882 } else { \
883 rbtn_right_set(a_type, a_field, nodep[-1].node, \
884 nodep->node); \
885 } \
886 } \
887 } else { \
888 a_type *left = rbtn_left_get(a_type, a_field, node); \
889 if (left != NULL) { \
890 /* node has no successor, but it has a left child. */\
891 /* Splice node out, without losing the left child. */\
892 assert(!rbtn_red_get(a_type, a_field, node)); \
893 assert(rbtn_red_get(a_type, a_field, left)); \
894 rbtn_black_set(a_type, a_field, left); \
895 if (pathp == path) { \
896 rbtree->rbt_root = left; \
897 /* Nothing to summarize -- the subtree rooted at the */\
898 /* node's left child hasn't changed, and it's now the */\
899 /* root. */\
900 } else { \
901 if (pathp[-1].cmp < 0) { \
902 rbtn_left_set(a_type, a_field, pathp[-1].node, \
903 left); \
904 } else { \
905 rbtn_right_set(a_type, a_field, pathp[-1].node, \
906 left); \
907 } \
908 a_prefix##summarize_swapped_range(path, &pathp[-1], \
909 swap_loc); \
910 } \
911 return; \
912 } else if (pathp == path) { \
913 /* The tree only contained one node. */ \
914 rbtree->rbt_root = NULL; \
915 return; \
916 } \
917 } \
918 /* We've now established the invariant that the node has no right */\
919 /* child (well, morally; we didn't bother nulling it out if we */\
920 /* swapped it with its successor), and that the only nodes with */\
921 /* out-of-date summaries live in path[0], path[1], ..., pathp[-1].*/\
922 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
923 /* Prune red node, which requires no fixup. */ \
924 assert(pathp[-1].cmp < 0); \
925 rbtn_left_set(a_type, a_field, pathp[-1].node, NULL); \
926 a_prefix##summarize_swapped_range(path, &pathp[-1], swap_loc); \
927 return; \
928 } \
929 /* The node to be pruned is black, so unwind until balance is */\
930 /* restored. */\
931 pathp->node = NULL; \
932 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
933 assert(pathp->cmp != 0); \
934 if (pathp->cmp < 0) { \
935 rbtn_left_set(a_type, a_field, pathp->node, \
936 pathp[1].node); \
937 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
938 a_type *right = rbtn_right_get(a_type, a_field, \
939 pathp->node); \
940 a_type *rightleft = rbtn_left_get(a_type, a_field, \
941 right); \
942 a_type *tnode; \
943 if (rightleft != NULL && rbtn_red_get(a_type, a_field, \
944 rightleft)) { \
945 /* In the following diagrams, ||, //, and \\ */\
946 /* indicate the path to the removed node. */\
947 /* */\
948 /* || */\
949 /* pathp(r) */\
950 /* // \ */\
951 /* (b) (b) */\
952 /* / */\
953 /* (r) */\
954 /* */\
955 rbtn_black_set(a_type, a_field, pathp->node); \
956 rbtn_rotate_right(a_type, a_field, right, tnode); \
957 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
958 rbtn_rotate_left(a_type, a_field, pathp->node, \
959 tnode); \
960 (void)a_summarize(pathp->node, \
961 rbtn_left_get(a_type, a_field, pathp->node), \
962 rbtn_right_get(a_type, a_field, pathp->node)); \
963 (void)a_summarize(right, \
964 rbtn_left_get(a_type, a_field, right), \
965 rbtn_right_get(a_type, a_field, right)); \
966 } else { \
967 /* || */\
968 /* pathp(r) */\
969 /* // \ */\
970 /* (b) (b) */\
971 /* / */\
972 /* (b) */\
973 /* */\
974 rbtn_rotate_left(a_type, a_field, pathp->node, \
975 tnode); \
976 (void)a_summarize(pathp->node, \
977 rbtn_left_get(a_type, a_field, pathp->node), \
978 rbtn_right_get(a_type, a_field, pathp->node)); \
979 } \
980 (void)a_summarize(tnode, rbtn_left_get(a_type, a_field, \
981 tnode), rbtn_right_get(a_type, a_field, tnode)); \
982 /* Balance restored, but rotation modified subtree */\
983 /* root. */\
984 assert((uintptr_t)pathp > (uintptr_t)path); \
985 if (pathp[-1].cmp < 0) { \
986 rbtn_left_set(a_type, a_field, pathp[-1].node, \
987 tnode); \
988 } else { \
989 rbtn_right_set(a_type, a_field, pathp[-1].node, \
990 tnode); \
991 } \
992 a_prefix##summarize_swapped_range(path, &pathp[-1], \
993 swap_loc); \
994 return; \
995 } else { \
996 a_type *right = rbtn_right_get(a_type, a_field, \
997 pathp->node); \
998 a_type *rightleft = rbtn_left_get(a_type, a_field, \
999 right); \
1000 if (rightleft != NULL && rbtn_red_get(a_type, a_field, \
1001 rightleft)) { \
1002 /* || */\
1003 /* pathp(b) */\
1004 /* // \ */\
1005 /* (b) (b) */\
1006 /* / */\
1007 /* (r) */\
1008 a_type *tnode; \
1009 rbtn_black_set(a_type, a_field, rightleft); \
1010 rbtn_rotate_right(a_type, a_field, right, tnode); \
1011 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
1012 rbtn_rotate_left(a_type, a_field, pathp->node, \
1013 tnode); \
1014 (void)a_summarize(pathp->node, \
1015 rbtn_left_get(a_type, a_field, pathp->node), \
1016 rbtn_right_get(a_type, a_field, pathp->node)); \
1017 (void)a_summarize(right, \
1018 rbtn_left_get(a_type, a_field, right), \
1019 rbtn_right_get(a_type, a_field, right)); \
1020 (void)a_summarize(tnode, \
1021 rbtn_left_get(a_type, a_field, tnode), \
1022 rbtn_right_get(a_type, a_field, tnode)); \
1023 /* Balance restored, but rotation modified */\
1024 /* subtree root, which may actually be the tree */\
1025 /* root. */\
1026 if (pathp == path) { \
1027 /* Set root. */ \
1028 rbtree->rbt_root = tnode; \
1029 } else { \
1030 if (pathp[-1].cmp < 0) { \
1031 rbtn_left_set(a_type, a_field, \
1032 pathp[-1].node, tnode); \
1033 } else { \
1034 rbtn_right_set(a_type, a_field, \
1035 pathp[-1].node, tnode); \
1036 } \
1037 a_prefix##summarize_swapped_range(path, \
1038 &pathp[-1], swap_loc); \
1039 } \
1040 return; \
1041 } else { \
1042 /* || */\
1043 /* pathp(b) */\
1044 /* // \ */\
1045 /* (b) (b) */\
1046 /* / */\
1047 /* (b) */\
1048 a_type *tnode; \
1049 rbtn_red_set(a_type, a_field, pathp->node); \
1050 rbtn_rotate_left(a_type, a_field, pathp->node, \
1051 tnode); \
1052 (void)a_summarize(pathp->node, \
1053 rbtn_left_get(a_type, a_field, pathp->node), \
1054 rbtn_right_get(a_type, a_field, pathp->node)); \
1055 (void)a_summarize(tnode, \
1056 rbtn_left_get(a_type, a_field, tnode), \
1057 rbtn_right_get(a_type, a_field, tnode)); \
1058 pathp->node = tnode; \
1059 } \
1060 } \
1061 } else { \
1062 a_type *left; \
1063 rbtn_right_set(a_type, a_field, pathp->node, \
1064 pathp[1].node); \
1065 left = rbtn_left_get(a_type, a_field, pathp->node); \
1066 if (rbtn_red_get(a_type, a_field, left)) { \
1067 a_type *tnode; \
1068 a_type *leftright = rbtn_right_get(a_type, a_field, \
1069 left); \
1070 a_type *leftrightleft = rbtn_left_get(a_type, a_field, \
1071 leftright); \
1072 if (leftrightleft != NULL && rbtn_red_get(a_type, \
1073 a_field, leftrightleft)) { \
1074 /* || */\
1075 /* pathp(b) */\
1076 /* / \\ */\
1077 /* (r) (b) */\
1078 /* \ */\
1079 /* (b) */\
1080 /* / */\
1081 /* (r) */\
1082 a_type *unode; \
1083 rbtn_black_set(a_type, a_field, leftrightleft); \
1084 rbtn_rotate_right(a_type, a_field, pathp->node, \
1085 unode); \
1086 rbtn_rotate_right(a_type, a_field, pathp->node, \
1087 tnode); \
1088 rbtn_right_set(a_type, a_field, unode, tnode); \
1089 rbtn_rotate_left(a_type, a_field, unode, tnode); \
1090 (void)a_summarize(pathp->node, \
1091 rbtn_left_get(a_type, a_field, pathp->node), \
1092 rbtn_right_get(a_type, a_field, pathp->node)); \
1093 (void)a_summarize(unode, \
1094 rbtn_left_get(a_type, a_field, unode), \
1095 rbtn_right_get(a_type, a_field, unode)); \
1096 } else { \
1097 /* || */\
1098 /* pathp(b) */\
1099 /* / \\ */\
1100 /* (r) (b) */\
1101 /* \ */\
1102 /* (b) */\
1103 /* / */\
1104 /* (b) */\
1105 assert(leftright != NULL); \
1106 rbtn_red_set(a_type, a_field, leftright); \
1107 rbtn_rotate_right(a_type, a_field, pathp->node, \
1108 tnode); \
1109 rbtn_black_set(a_type, a_field, tnode); \
1110 (void)a_summarize(pathp->node, \
1111 rbtn_left_get(a_type, a_field, pathp->node), \
1112 rbtn_right_get(a_type, a_field, pathp->node)); \
1113 } \
1114 (void)a_summarize(tnode, \
1115 rbtn_left_get(a_type, a_field, tnode), \
1116 rbtn_right_get(a_type, a_field, tnode)); \
1117 /* Balance restored, but rotation modified subtree */\
1118 /* root, which may actually be the tree root. */\
1119 if (pathp == path) { \
1120 /* Set root. */ \
1121 rbtree->rbt_root = tnode; \
1122 } else { \
1123 if (pathp[-1].cmp < 0) { \
1124 rbtn_left_set(a_type, a_field, pathp[-1].node, \
1125 tnode); \
1126 } else { \
1127 rbtn_right_set(a_type, a_field, pathp[-1].node, \
1128 tnode); \
1129 } \
1130 a_prefix##summarize_swapped_range(path, &pathp[-1], \
1131 swap_loc); \
1132 } \
1133 return; \
1134 } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \
1135 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
1136 if (leftleft != NULL && rbtn_red_get(a_type, a_field, \
1137 leftleft)) { \
1138 /* || */\
1139 /* pathp(r) */\
1140 /* / \\ */\
1141 /* (b) (b) */\
1142 /* / */\
1143 /* (r) */\
1144 a_type *tnode; \
1145 rbtn_black_set(a_type, a_field, pathp->node); \
1146 rbtn_red_set(a_type, a_field, left); \
1147 rbtn_black_set(a_type, a_field, leftleft); \
1148 rbtn_rotate_right(a_type, a_field, pathp->node, \
1149 tnode); \
1150 (void)a_summarize(pathp->node, \
1151 rbtn_left_get(a_type, a_field, pathp->node), \
1152 rbtn_right_get(a_type, a_field, pathp->node)); \
1153 (void)a_summarize(tnode, \
1154 rbtn_left_get(a_type, a_field, tnode), \
1155 rbtn_right_get(a_type, a_field, tnode)); \
1156 /* Balance restored, but rotation modified */\
1157 /* subtree root. */\
1158 assert((uintptr_t)pathp > (uintptr_t)path); \
1159 if (pathp[-1].cmp < 0) { \
1160 rbtn_left_set(a_type, a_field, pathp[-1].node, \
1161 tnode); \
1162 } else { \
1163 rbtn_right_set(a_type, a_field, pathp[-1].node, \
1164 tnode); \
1165 } \
1166 a_prefix##summarize_swapped_range(path, &pathp[-1], \
1167 swap_loc); \
1168 return; \
1169 } else { \
1170 /* || */\
1171 /* pathp(r) */\
1172 /* / \\ */\
1173 /* (b) (b) */\
1174 /* / */\
1175 /* (b) */\
1176 rbtn_red_set(a_type, a_field, left); \
1177 rbtn_black_set(a_type, a_field, pathp->node); \
1178 /* Balance restored. */ \
1179 a_prefix##summarize_swapped_range(path, pathp, \
1180 swap_loc); \
1181 return; \
1182 } \
1183 } else { \
1184 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
1185 if (leftleft != NULL && rbtn_red_get(a_type, a_field, \
1186 leftleft)) { \
1187 /* || */\
1188 /* pathp(b) */\
1189 /* / \\ */\
1190 /* (b) (b) */\
1191 /* / */\
1192 /* (r) */\
1193 a_type *tnode; \
1194 rbtn_black_set(a_type, a_field, leftleft); \
1195 rbtn_rotate_right(a_type, a_field, pathp->node, \
1196 tnode); \
1197 (void)a_summarize(pathp->node, \
1198 rbtn_left_get(a_type, a_field, pathp->node), \
1199 rbtn_right_get(a_type, a_field, pathp->node)); \
1200 (void)a_summarize(tnode, \
1201 rbtn_left_get(a_type, a_field, tnode), \
1202 rbtn_right_get(a_type, a_field, tnode)); \
1203 /* Balance restored, but rotation modified */\
1204 /* subtree root, which may actually be the tree */\
1205 /* root. */\
1206 if (pathp == path) { \
1207 /* Set root. */ \
1208 rbtree->rbt_root = tnode; \
1209 } else { \
1210 if (pathp[-1].cmp < 0) { \
1211 rbtn_left_set(a_type, a_field, \
1212 pathp[-1].node, tnode); \
1213 } else { \
1214 rbtn_right_set(a_type, a_field, \
1215 pathp[-1].node, tnode); \
1216 } \
1217 a_prefix##summarize_swapped_range(path, \
1218 &pathp[-1], swap_loc); \
1219 } \
1220 return; \
1221 } else { \
1222 /* || */\
1223 /* pathp(b) */\
1224 /* / \\ */\
1225 /* (b) (b) */\
1226 /* / */\
1227 /* (b) */\
1228 rbtn_red_set(a_type, a_field, left); \
1229 (void)a_summarize(pathp->node, \
1230 rbtn_left_get(a_type, a_field, pathp->node), \
1231 rbtn_right_get(a_type, a_field, pathp->node)); \
1232 } \
1233 } \
1234 } \
1235 } \
1236 /* Set root. */ \
1237 rbtree->rbt_root = path->node; \
1238 assert(!rbtn_red_get(a_type, a_field, rbtree->rbt_root)); \
1239} \
1240a_attr a_type * \
1241a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \
1242 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
1243 if (node == NULL) { \
1244 return NULL; \
1245 } else { \
1246 a_type *ret; \
1247 if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \
1248 a_field, node), cb, arg)) != NULL || (ret = cb(rbtree, node, \
1249 arg)) != NULL) { \
1250 return ret; \
1251 } \
1252 return a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
1253 a_field, node), cb, arg); \
1254 } \
1255} \
1256a_attr a_type * \
1257a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \
1258 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
1259 int cmp = a_cmp(start, node); \
1260 if (cmp < 0) { \
1261 a_type *ret; \
1262 if ((ret = a_prefix##iter_start(rbtree, start, \
1263 rbtn_left_get(a_type, a_field, node), cb, arg)) != NULL || \
1264 (ret = cb(rbtree, node, arg)) != NULL) { \
1265 return ret; \
1266 } \
1267 return a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
1268 a_field, node), cb, arg); \
1269 } else if (cmp > 0) { \
1270 return a_prefix##iter_start(rbtree, start, \
1271 rbtn_right_get(a_type, a_field, node), cb, arg); \
1272 } else { \
1273 a_type *ret; \
1274 if ((ret = cb(rbtree, node, arg)) != NULL) { \
1275 return ret; \
1276 } \
1277 return a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
1278 a_field, node), cb, arg); \
1279 } \
1280} \
1281a_attr a_type * \
1282a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
1283 a_rbt_type *, a_type *, void *), void *arg) { \
1284 a_type *ret; \
1285 if (start != NULL) { \
1286 ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \
1287 cb, arg); \
1288 } else { \
1289 ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\
1290 } \
1291 return ret; \
1292} \
1293a_attr a_type * \
1294a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \
1295 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
1296 if (node == NULL) { \
1297 return NULL; \
1298 } else { \
1299 a_type *ret; \
1300 if ((ret = a_prefix##reverse_iter_recurse(rbtree, \
1301 rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL || \
1302 (ret = cb(rbtree, node, arg)) != NULL) { \
1303 return ret; \
1304 } \
1305 return a_prefix##reverse_iter_recurse(rbtree, \
1306 rbtn_left_get(a_type, a_field, node), cb, arg); \
1307 } \
1308} \
1309a_attr a_type * \
1310a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \
1311 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \
1312 void *arg) { \
1313 int cmp = a_cmp(start, node); \
1314 if (cmp > 0) { \
1315 a_type *ret; \
1316 if ((ret = a_prefix##reverse_iter_start(rbtree, start, \
1317 rbtn_right_get(a_type, a_field, node), cb, arg)) != NULL || \
1318 (ret = cb(rbtree, node, arg)) != NULL) { \
1319 return ret; \
1320 } \
1321 return a_prefix##reverse_iter_recurse(rbtree, \
1322 rbtn_left_get(a_type, a_field, node), cb, arg); \
1323 } else if (cmp < 0) { \
1324 return a_prefix##reverse_iter_start(rbtree, start, \
1325 rbtn_left_get(a_type, a_field, node), cb, arg); \
1326 } else { \
1327 a_type *ret; \
1328 if ((ret = cb(rbtree, node, arg)) != NULL) { \
1329 return ret; \
1330 } \
1331 return a_prefix##reverse_iter_recurse(rbtree, \
1332 rbtn_left_get(a_type, a_field, node), cb, arg); \
1333 } \
1334} \
1335a_attr a_type * \
1336a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
1337 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
1338 a_type *ret; \
1339 if (start != NULL) { \
1340 ret = a_prefix##reverse_iter_start(rbtree, start, \
1341 rbtree->rbt_root, cb, arg); \
1342 } else { \
1343 ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \
1344 cb, arg); \
1345 } \
1346 return ret; \
1347} \
1348a_attr void \
1349a_prefix##destroy_recurse(a_rbt_type *rbtree, a_type *node, void (*cb)( \
1350 a_type *, void *), void *arg) { \
1351 if (node == NULL) { \
1352 return; \
1353 } \
1354 a_prefix##destroy_recurse(rbtree, rbtn_left_get(a_type, a_field, \
1355 node), cb, arg); \
1356 rbtn_left_set(a_type, a_field, (node), NULL); \
1357 a_prefix##destroy_recurse(rbtree, rbtn_right_get(a_type, a_field, \
1358 node), cb, arg); \
1359 rbtn_right_set(a_type, a_field, (node), NULL); \
1360 if (cb) { \
1361 cb(node, arg); \
1362 } \
1363} \
1364a_attr void \
1365a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \
1366 void *arg) { \
1367 a_prefix##destroy_recurse(rbtree, rbtree->rbt_root, cb, arg); \
1368 rbtree->rbt_root = NULL; \
1369} \
1370/* BEGIN SUMMARIZED-ONLY IMPLEMENTATION */ \
1371rb_summarized_only_##a_is_summarized( \
1372static inline a_prefix##path_entry_t * \
1373a_prefix##wind(a_rbt_type *rbtree, \
1374 a_prefix##path_entry_t path[RB_MAX_DEPTH], a_type *node) { \
1375 a_prefix##path_entry_t *pathp; \
1376 path->node = rbtree->rbt_root; \
1377 for (pathp = path; ; pathp++) { \
1378 assert((size_t)(pathp - path) < RB_MAX_DEPTH); \
1379 pathp->cmp = a_cmp(node, pathp->node); \
1380 if (pathp->cmp < 0) { \
1381 pathp[1].node = rbtn_left_get(a_type, a_field, \
1382 pathp->node); \
1383 } else if (pathp->cmp == 0) { \
1384 return pathp; \
1385 } else { \
1386 pathp[1].node = rbtn_right_get(a_type, a_field, \
1387 pathp->node); \
1388 } \
1389 } \
1390 unreachable(); \
1391} \
1392a_attr void \
1393a_prefix##update_summaries(a_rbt_type *rbtree, a_type *node) { \
1394 a_prefix##path_entry_t path[RB_MAX_DEPTH]; \
1395 a_prefix##path_entry_t *pathp = a_prefix##wind(rbtree, path, node); \
1396 a_prefix##summarize_range(path, pathp); \
1397} \
1398a_attr bool \
1399a_prefix##empty_filtered(a_rbt_type *rbtree, \
1400 bool (*filter_node)(void *, a_type *), \
1401 bool (*filter_subtree)(void *, a_type *), \
1402 void *filter_ctx) { \
1403 a_type *node = rbtree->rbt_root; \
1404 return node == NULL || !filter_subtree(filter_ctx, node); \
1405} \
1406static inline a_type * \
1407a_prefix##first_filtered_from_node(a_type *node, \
1408 bool (*filter_node)(void *, a_type *), \
1409 bool (*filter_subtree)(void *, a_type *), \
1410 void *filter_ctx) { \
1411 assert(node != NULL && filter_subtree(filter_ctx, node)); \
1412 while (true) { \
1413 a_type *left = rbtn_left_get(a_type, a_field, node); \
1414 a_type *right = rbtn_right_get(a_type, a_field, node); \
1415 if (left != NULL && filter_subtree(filter_ctx, left)) { \
1416 node = left; \
1417 } else if (filter_node(filter_ctx, node)) { \
1418 return node; \
1419 } else { \
1420 assert(right != NULL \
1421 && filter_subtree(filter_ctx, right)); \
1422 node = right; \
1423 } \
1424 } \
1425 unreachable(); \
1426} \
1427a_attr a_type * \
1428a_prefix##first_filtered(a_rbt_type *rbtree, \
1429 bool (*filter_node)(void *, a_type *), \
1430 bool (*filter_subtree)(void *, a_type *), \
1431 void *filter_ctx) { \
1432 a_type *node = rbtree->rbt_root; \
1433 if (node == NULL || !filter_subtree(filter_ctx, node)) { \
1434 return NULL; \
1435 } \
1436 return a_prefix##first_filtered_from_node(node, filter_node, \
1437 filter_subtree, filter_ctx); \
1438} \
1439static inline a_type * \
1440a_prefix##last_filtered_from_node(a_type *node, \
1441 bool (*filter_node)(void *, a_type *), \
1442 bool (*filter_subtree)(void *, a_type *), \
1443 void *filter_ctx) { \
1444 assert(node != NULL && filter_subtree(filter_ctx, node)); \
1445 while (true) { \
1446 a_type *left = rbtn_left_get(a_type, a_field, node); \
1447 a_type *right = rbtn_right_get(a_type, a_field, node); \
1448 if (right != NULL && filter_subtree(filter_ctx, right)) { \
1449 node = right; \
1450 } else if (filter_node(filter_ctx, node)) { \
1451 return node; \
1452 } else { \
1453 assert(left != NULL \
1454 && filter_subtree(filter_ctx, left)); \
1455 node = left; \
1456 } \
1457 } \
1458 unreachable(); \
1459} \
1460a_attr a_type * \
1461a_prefix##last_filtered(a_rbt_type *rbtree, \
1462 bool (*filter_node)(void *, a_type *), \
1463 bool (*filter_subtree)(void *, a_type *), \
1464 void *filter_ctx) { \
1465 a_type *node = rbtree->rbt_root; \
1466 if (node == NULL || !filter_subtree(filter_ctx, node)) { \
1467 return NULL; \
1468 } \
1469 return a_prefix##last_filtered_from_node(node, filter_node, \
1470 filter_subtree, filter_ctx); \
1471} \
1472/* Internal implementation function. Search for a node comparing */\
1473/* equal to key matching the filter. If such a node is in the tree, */\
1474/* return it. Additionally, the caller has the option to ask for */\
1475/* bounds on the next / prev node in the tree passing the filter. */\
1476/* If nextbound is true, then this function will do one of the */\
1477/* following: */\
1478/* - Fill in *nextbound_node with the smallest node in the tree */\
1479/* greater than key passing the filter, and NULL-out */\
1480/* *nextbound_subtree. */\
1481/* - Fill in *nextbound_subtree with a parent of that node which is */\
1482/* not a parent of the searched-for node, and NULL-out */\
1483/* *nextbound_node. */\
1484/* - NULL-out both *nextbound_node and *nextbound_subtree, in which */\
1485/* case no node greater than key but passing the filter is in the */\
1486/* tree. */\
1487/* The prevbound case is similar. If the caller knows that key is in */\
1488/* the tree and that the subtree rooted at key does not contain a */\
1489/* node satisfying the bound being searched for, then they can pass */\
1490/* false for include_subtree, in which case we won't bother searching */\
1491/* there (risking a cache miss). */\
1492/* */\
1493/* This API is unfortunately complex; but the logic for filtered */\
1494/* searches is very subtle, and otherwise we would have to repeat it */\
1495/* multiple times for filtered search, nsearch, psearch, next, and */\
1496/* prev. */\
1497static inline a_type * \
1498a_prefix##search_with_filter_bounds(a_rbt_type *rbtree, \
1499 const a_type *key, \
1500 bool (*filter_node)(void *, a_type *), \
1501 bool (*filter_subtree)(void *, a_type *), \
1502 void *filter_ctx, \
1503 bool include_subtree, \
1504 bool nextbound, a_type **nextbound_node, a_type **nextbound_subtree, \
1505 bool prevbound, a_type **prevbound_node, a_type **prevbound_subtree) {\
1506 if (nextbound) { \
1507 *nextbound_node = NULL; \
1508 *nextbound_subtree = NULL; \
1509 } \
1510 if (prevbound) { \
1511 *prevbound_node = NULL; \
1512 *prevbound_subtree = NULL; \
1513 } \
1514 a_type *tnode = rbtree->rbt_root; \
1515 while (tnode != NULL && filter_subtree(filter_ctx, tnode)) { \
1516 int cmp = a_cmp(key, tnode); \
1517 a_type *tleft = rbtn_left_get(a_type, a_field, tnode); \
1518 a_type *tright = rbtn_right_get(a_type, a_field, tnode); \
1519 if (cmp < 0) { \
1520 if (nextbound) { \
1521 if (filter_node(filter_ctx, tnode)) { \
1522 *nextbound_node = tnode; \
1523 *nextbound_subtree = NULL; \
1524 } else if (tright != NULL && filter_subtree( \
1525 filter_ctx, tright)) { \
1526 *nextbound_node = NULL; \
1527 *nextbound_subtree = tright; \
1528 } \
1529 } \
1530 tnode = tleft; \
1531 } else if (cmp > 0) { \
1532 if (prevbound) { \
1533 if (filter_node(filter_ctx, tnode)) { \
1534 *prevbound_node = tnode; \
1535 *prevbound_subtree = NULL; \
1536 } else if (tleft != NULL && filter_subtree( \
1537 filter_ctx, tleft)) { \
1538 *prevbound_node = NULL; \
1539 *prevbound_subtree = tleft; \
1540 } \
1541 } \
1542 tnode = tright; \
1543 } else { \
1544 if (filter_node(filter_ctx, tnode)) { \
1545 return tnode; \
1546 } \
1547 if (include_subtree) { \
1548 if (prevbound && tleft != NULL && filter_subtree( \
1549 filter_ctx, tleft)) { \
1550 *prevbound_node = NULL; \
1551 *prevbound_subtree = tleft; \
1552 } \
1553 if (nextbound && tright != NULL && filter_subtree( \
1554 filter_ctx, tright)) { \
1555 *nextbound_node = NULL; \
1556 *nextbound_subtree = tright; \
1557 } \
1558 } \
1559 return NULL; \
1560 } \
1561 } \
1562 return NULL; \
1563} \
1564a_attr a_type * \
1565a_prefix##next_filtered(a_rbt_type *rbtree, a_type *node, \
1566 bool (*filter_node)(void *, a_type *), \
1567 bool (*filter_subtree)(void *, a_type *), \
1568 void *filter_ctx) { \
1569 a_type *nright = rbtn_right_get(a_type, a_field, node); \
1570 if (nright != NULL && filter_subtree(filter_ctx, nright)) { \
1571 return a_prefix##first_filtered_from_node(nright, filter_node, \
1572 filter_subtree, filter_ctx); \
1573 } \
1574 a_type *node_candidate; \
1575 a_type *subtree_candidate; \
1576 a_type *search_result = a_prefix##search_with_filter_bounds( \
1577 rbtree, node, filter_node, filter_subtree, filter_ctx, \
1578 /* include_subtree */ false, \
1579 /* nextbound */ true, &node_candidate, &subtree_candidate, \
1580 /* prevbound */ false, NULL, NULL); \
1581 assert(node == search_result \
1582 || !filter_node(filter_ctx, node)); \
1583 if (node_candidate != NULL) { \
1584 return node_candidate; \
1585 } \
1586 if (subtree_candidate != NULL) { \
1587 return a_prefix##first_filtered_from_node( \
1588 subtree_candidate, filter_node, filter_subtree, \
1589 filter_ctx); \
1590 } \
1591 return NULL; \
1592} \
1593a_attr a_type * \
1594a_prefix##prev_filtered(a_rbt_type *rbtree, a_type *node, \
1595 bool (*filter_node)(void *, a_type *), \
1596 bool (*filter_subtree)(void *, a_type *), \
1597 void *filter_ctx) { \
1598 a_type *nleft = rbtn_left_get(a_type, a_field, node); \
1599 if (nleft != NULL && filter_subtree(filter_ctx, nleft)) { \
1600 return a_prefix##last_filtered_from_node(nleft, filter_node, \
1601 filter_subtree, filter_ctx); \
1602 } \
1603 a_type *node_candidate; \
1604 a_type *subtree_candidate; \
1605 a_type *search_result = a_prefix##search_with_filter_bounds( \
1606 rbtree, node, filter_node, filter_subtree, filter_ctx, \
1607 /* include_subtree */ false, \
1608 /* nextbound */ false, NULL, NULL, \
1609 /* prevbound */ true, &node_candidate, &subtree_candidate); \
1610 assert(node == search_result \
1611 || !filter_node(filter_ctx, node)); \
1612 if (node_candidate != NULL) { \
1613 return node_candidate; \
1614 } \
1615 if (subtree_candidate != NULL) { \
1616 return a_prefix##last_filtered_from_node( \
1617 subtree_candidate, filter_node, filter_subtree, \
1618 filter_ctx); \
1619 } \
1620 return NULL; \
1621} \
1622a_attr a_type * \
1623a_prefix##search_filtered(a_rbt_type *rbtree, const a_type *key, \
1624 bool (*filter_node)(void *, a_type *), \
1625 bool (*filter_subtree)(void *, a_type *), \
1626 void *filter_ctx) { \
1627 a_type *result = a_prefix##search_with_filter_bounds(rbtree, key, \
1628 filter_node, filter_subtree, filter_ctx, \
1629 /* include_subtree */ false, \
1630 /* nextbound */ false, NULL, NULL, \
1631 /* prevbound */ false, NULL, NULL); \
1632 return result; \
1633} \
1634a_attr a_type * \
1635a_prefix##nsearch_filtered(a_rbt_type *rbtree, const a_type *key, \
1636 bool (*filter_node)(void *, a_type *), \
1637 bool (*filter_subtree)(void *, a_type *), \
1638 void *filter_ctx) { \
1639 a_type *node_candidate; \
1640 a_type *subtree_candidate; \
1641 a_type *result = a_prefix##search_with_filter_bounds(rbtree, key, \
1642 filter_node, filter_subtree, filter_ctx, \
1643 /* include_subtree */ true, \
1644 /* nextbound */ true, &node_candidate, &subtree_candidate, \
1645 /* prevbound */ false, NULL, NULL); \
1646 if (result != NULL) { \
1647 return result; \
1648 } \
1649 if (node_candidate != NULL) { \
1650 return node_candidate; \
1651 } \
1652 if (subtree_candidate != NULL) { \
1653 return a_prefix##first_filtered_from_node( \
1654 subtree_candidate, filter_node, filter_subtree, \
1655 filter_ctx); \
1656 } \
1657 return NULL; \
1658} \
1659a_attr a_type * \
1660a_prefix##psearch_filtered(a_rbt_type *rbtree, const a_type *key, \
1661 bool (*filter_node)(void *, a_type *), \
1662 bool (*filter_subtree)(void *, a_type *), \
1663 void *filter_ctx) { \
1664 a_type *node_candidate; \
1665 a_type *subtree_candidate; \
1666 a_type *result = a_prefix##search_with_filter_bounds(rbtree, key, \
1667 filter_node, filter_subtree, filter_ctx, \
1668 /* include_subtree */ true, \
1669 /* nextbound */ false, NULL, NULL, \
1670 /* prevbound */ true, &node_candidate, &subtree_candidate); \
1671 if (result != NULL) { \
1672 return result; \
1673 } \
1674 if (node_candidate != NULL) { \
1675 return node_candidate; \
1676 } \
1677 if (subtree_candidate != NULL) { \
1678 return a_prefix##last_filtered_from_node( \
1679 subtree_candidate, filter_node, filter_subtree, \
1680 filter_ctx); \
1681 } \
1682 return NULL; \
1683} \
1684a_attr a_type * \
1685a_prefix##iter_recurse_filtered(a_rbt_type *rbtree, a_type *node, \
1686 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \
1687 bool (*filter_node)(void *, a_type *), \
1688 bool (*filter_subtree)(void *, a_type *), \
1689 void *filter_ctx) { \
1690 if (node == NULL || !filter_subtree(filter_ctx, node)) { \
1691 return NULL; \
1692 } \
1693 a_type *ret; \
1694 a_type *left = rbtn_left_get(a_type, a_field, node); \
1695 a_type *right = rbtn_right_get(a_type, a_field, node); \
1696 ret = a_prefix##iter_recurse_filtered(rbtree, left, cb, arg, \
1697 filter_node, filter_subtree, filter_ctx); \
1698 if (ret != NULL) { \
1699 return ret; \
1700 } \
1701 if (filter_node(filter_ctx, node)) { \
1702 ret = cb(rbtree, node, arg); \
1703 } \
1704 if (ret != NULL) { \
1705 return ret; \
1706 } \
1707 return a_prefix##iter_recurse_filtered(rbtree, right, cb, arg, \
1708 filter_node, filter_subtree, filter_ctx); \
1709} \
1710a_attr a_type * \
1711a_prefix##iter_start_filtered(a_rbt_type *rbtree, a_type *start, \
1712 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \
1713 void *arg, bool (*filter_node)(void *, a_type *), \
1714 bool (*filter_subtree)(void *, a_type *), \
1715 void *filter_ctx) { \
1716 if (!filter_subtree(filter_ctx, node)) { \
1717 return NULL; \
1718 } \
1719 int cmp = a_cmp(start, node); \
1720 a_type *ret; \
1721 a_type *left = rbtn_left_get(a_type, a_field, node); \
1722 a_type *right = rbtn_right_get(a_type, a_field, node); \
1723 if (cmp < 0) { \
1724 ret = a_prefix##iter_start_filtered(rbtree, start, left, cb, \
1725 arg, filter_node, filter_subtree, filter_ctx); \
1726 if (ret != NULL) { \
1727 return ret; \
1728 } \
1729 if (filter_node(filter_ctx, node)) { \
1730 ret = cb(rbtree, node, arg); \
1731 if (ret != NULL) { \
1732 return ret; \
1733 } \
1734 } \
1735 return a_prefix##iter_recurse_filtered(rbtree, right, cb, arg, \
1736 filter_node, filter_subtree, filter_ctx); \
1737 } else if (cmp > 0) { \
1738 return a_prefix##iter_start_filtered(rbtree, start, right, \
1739 cb, arg, filter_node, filter_subtree, filter_ctx); \
1740 } else { \
1741 if (filter_node(filter_ctx, node)) { \
1742 ret = cb(rbtree, node, arg); \
1743 if (ret != NULL) { \
1744 return ret; \
1745 } \
1746 } \
1747 return a_prefix##iter_recurse_filtered(rbtree, right, cb, arg, \
1748 filter_node, filter_subtree, filter_ctx); \
1749 } \
1750} \
1751a_attr a_type * \
1752a_prefix##iter_filtered(a_rbt_type *rbtree, a_type *start, \
1753 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \
1754 bool (*filter_node)(void *, a_type *), \
1755 bool (*filter_subtree)(void *, a_type *), \
1756 void *filter_ctx) { \
1757 a_type *ret; \
1758 if (start != NULL) { \
1759 ret = a_prefix##iter_start_filtered(rbtree, start, \
1760 rbtree->rbt_root, cb, arg, filter_node, filter_subtree, \
1761 filter_ctx); \
1762 } else { \
1763 ret = a_prefix##iter_recurse_filtered(rbtree, rbtree->rbt_root, \
1764 cb, arg, filter_node, filter_subtree, filter_ctx); \
1765 } \
1766 return ret; \
1767} \
1768a_attr a_type * \
1769a_prefix##reverse_iter_recurse_filtered(a_rbt_type *rbtree, \
1770 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \
1771 void *arg, \
1772 bool (*filter_node)(void *, a_type *), \
1773 bool (*filter_subtree)(void *, a_type *), \
1774 void *filter_ctx) { \
1775 if (node == NULL || !filter_subtree(filter_ctx, node)) { \
1776 return NULL; \
1777 } \
1778 a_type *ret; \
1779 a_type *left = rbtn_left_get(a_type, a_field, node); \
1780 a_type *right = rbtn_right_get(a_type, a_field, node); \
1781 ret = a_prefix##reverse_iter_recurse_filtered(rbtree, right, cb, \
1782 arg, filter_node, filter_subtree, filter_ctx); \
1783 if (ret != NULL) { \
1784 return ret; \
1785 } \
1786 if (filter_node(filter_ctx, node)) { \
1787 ret = cb(rbtree, node, arg); \
1788 } \
1789 if (ret != NULL) { \
1790 return ret; \
1791 } \
1792 return a_prefix##reverse_iter_recurse_filtered(rbtree, left, cb, \
1793 arg, filter_node, filter_subtree, filter_ctx); \
1794} \
1795a_attr a_type * \
1796a_prefix##reverse_iter_start_filtered(a_rbt_type *rbtree, a_type *start,\
1797 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \
1798 void *arg, bool (*filter_node)(void *, a_type *), \
1799 bool (*filter_subtree)(void *, a_type *), \
1800 void *filter_ctx) { \
1801 if (!filter_subtree(filter_ctx, node)) { \
1802 return NULL; \
1803 } \
1804 int cmp = a_cmp(start, node); \
1805 a_type *ret; \
1806 a_type *left = rbtn_left_get(a_type, a_field, node); \
1807 a_type *right = rbtn_right_get(a_type, a_field, node); \
1808 if (cmp > 0) { \
1809 ret = a_prefix##reverse_iter_start_filtered(rbtree, start, \
1810 right, cb, arg, filter_node, filter_subtree, filter_ctx); \
1811 if (ret != NULL) { \
1812 return ret; \
1813 } \
1814 if (filter_node(filter_ctx, node)) { \
1815 ret = cb(rbtree, node, arg); \
1816 if (ret != NULL) { \
1817 return ret; \
1818 } \
1819 } \
1820 return a_prefix##reverse_iter_recurse_filtered(rbtree, left, cb,\
1821 arg, filter_node, filter_subtree, filter_ctx); \
1822 } else if (cmp < 0) { \
1823 return a_prefix##reverse_iter_start_filtered(rbtree, start, \
1824 left, cb, arg, filter_node, filter_subtree, filter_ctx); \
1825 } else { \
1826 if (filter_node(filter_ctx, node)) { \
1827 ret = cb(rbtree, node, arg); \
1828 if (ret != NULL) { \
1829 return ret; \
1830 } \
1831 } \
1832 return a_prefix##reverse_iter_recurse_filtered(rbtree, left, cb,\
1833 arg, filter_node, filter_subtree, filter_ctx); \
1834 } \
1835} \
1836a_attr a_type * \
1837a_prefix##reverse_iter_filtered(a_rbt_type *rbtree, a_type *start, \
1838 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \
1839 bool (*filter_node)(void *, a_type *), \
1840 bool (*filter_subtree)(void *, a_type *), \
1841 void *filter_ctx) { \
1842 a_type *ret; \
1843 if (start != NULL) { \
1844 ret = a_prefix##reverse_iter_start_filtered(rbtree, start, \
1845 rbtree->rbt_root, cb, arg, filter_node, filter_subtree, \
1846 filter_ctx); \
1847 } else { \
1848 ret = a_prefix##reverse_iter_recurse_filtered(rbtree, \
1849 rbtree->rbt_root, cb, arg, filter_node, filter_subtree, \
1850 filter_ctx); \
1851 } \
1852 return ret; \
1853} \
1854) /* end rb_summarized_only */
1855
1856#endif /* JEMALLOC_INTERNAL_RB_H */
1857