diff options
Diffstat (limited to 'deps/jemalloc/include/jemalloc/internal/rb.h')
| -rw-r--r-- | deps/jemalloc/include/jemalloc/internal/rb.h | 920 |
1 files changed, 885 insertions, 35 deletions
diff --git a/deps/jemalloc/include/jemalloc/internal/rb.h b/deps/jemalloc/include/jemalloc/internal/rb.h index 47fa5ca99..a9a51cb68 100644 --- a/deps/jemalloc/include/jemalloc/internal/rb.h +++ b/deps/jemalloc/include/jemalloc/internal/rb.h @@ -1,3 +1,6 @@ +#ifndef JEMALLOC_INTERNAL_RB_H +#define JEMALLOC_INTERNAL_RB_H + /*- ******************************************************************************* * @@ -19,13 +22,19 @@ ******************************************************************************* */ -#ifndef RB_H_ -#define RB_H_ - #ifndef __PGI #define RB_COMPACT #endif +/* + * Each node in the RB tree consumes at least 1 byte of space (for the linkage + * if nothing else, so there are a maximum of sizeof(void *) << 3 rb tree nodes + * in any process (and thus, at most sizeof(void *) << 3 nodes in any rb tree). + * The choice of algorithm bounds the depth of a tree to twice the binary log of + * the number of elements in the tree; the following bound follows. + */ +#define RB_MAX_DEPTH (sizeof(void *) << 4) + #ifdef RB_COMPACT /* Node structure. */ #define rb_node(a_type) \ @@ -159,12 +168,22 @@ struct { \ rbtn_right_set(a_type, a_field, (r_node), (a_node)); \ } while (0) +#define rb_summarized_only_false(...) +#define rb_summarized_only_true(...) __VA_ARGS__ +#define rb_empty_summarize(a_node, a_lchild, a_rchild) false + /* - * The rb_proto() macro generates function prototypes that correspond to the - * functions generated by an equivalently parameterized call to rb_gen(). + * The rb_proto() and rb_summarized_proto() macros generate function prototypes + * that correspond to the functions generated by an equivalently parameterized + * call to rb_gen() or rb_summarized_gen(), respectively. */ #define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \ + rb_proto_impl(a_attr, a_prefix, a_rbt_type, a_type, false) +#define rb_summarized_proto(a_attr, a_prefix, a_rbt_type, a_type) \ + rb_proto_impl(a_attr, a_prefix, a_rbt_type, a_type, true) +#define rb_proto_impl(a_attr, a_prefix, a_rbt_type, a_type, \ + a_is_summarized) \ a_attr void \ a_prefix##new(a_rbt_type *rbtree); \ a_attr bool \ @@ -195,31 +214,94 @@ a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); \ a_attr void \ a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ - void *arg); + void *arg); \ +/* Extended API */ \ +rb_summarized_only_##a_is_summarized( \ +a_attr void \ +a_prefix##update_summaries(a_rbt_type *rbtree, a_type *node); \ +a_attr bool \ +a_prefix##empty_filtered(a_rbt_type *rbtree, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##first_filtered(a_rbt_type *rbtree, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##last_filtered(a_rbt_type *rbtree, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##next_filtered(a_rbt_type *rbtree, a_type *node, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##prev_filtered(a_rbt_type *rbtree, a_type *node, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##search_filtered(a_rbt_type *rbtree, const a_type *key, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##nsearch_filtered(a_rbt_type *rbtree, const a_type *key, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##psearch_filtered(a_rbt_type *rbtree, const a_type *key, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##iter_filtered(a_rbt_type *rbtree, a_type *start, \ + a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +a_attr a_type * \ +a_prefix##reverse_iter_filtered(a_rbt_type *rbtree, a_type *start, \ + a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx); \ +) /* * The rb_gen() macro generates a type-specific red-black tree implementation, * based on the above cpp macros. - * * Arguments: * - * a_attr : Function attribute for generated functions (ex: static). - * a_prefix : Prefix for generated functions (ex: ex_). - * a_rb_type : Type for red-black tree data structure (ex: ex_t). - * a_type : Type for red-black tree node data structure (ex: ex_node_t). - * a_field : Name of red-black tree node linkage (ex: ex_link). - * a_cmp : Node comparison function name, with the following prototype: - * int (a_cmp *)(a_type *a_node, a_type *a_other); - * ^^^^^^ - * or a_key - * Interpretation of comparison function return values: - * -1 : a_node < a_other - * 0 : a_node == a_other - * 1 : a_node > a_other - * In all cases, the a_node or a_key macro argument is the first - * argument to the comparison function, which makes it possible - * to write comparison functions that treat the first argument - * specially. + * a_attr: + * Function attribute for generated functions (ex: static). + * a_prefix: + * Prefix for generated functions (ex: ex_). + * a_rb_type: + * Type for red-black tree data structure (ex: ex_t). + * a_type: + * Type for red-black tree node data structure (ex: ex_node_t). + * a_field: + * Name of red-black tree node linkage (ex: ex_link). + * a_cmp: + * Node comparison function name, with the following prototype: + * + * int a_cmp(a_type *a_node, a_type *a_other); + * ^^^^^^ + * or a_key + * Interpretation of comparison function return values: + * -1 : a_node < a_other + * 0 : a_node == a_other + * 1 : a_node > a_other + * In all cases, the a_node or a_key macro argument is the first argument to + * the comparison function, which makes it possible to write comparison + * functions that treat the first argument specially. a_cmp must be a total + * order on values inserted into the tree -- duplicates are not allowed. * * Assuming the following setup: * @@ -338,8 +420,193 @@ a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ * during iteration. There is no way to stop iteration once it * has begun. * arg : Opaque pointer passed to cb(). + * + * The rb_summarized_gen() macro generates all the functions above, but has an + * expanded interface. In introduces the notion of summarizing subtrees, and of + * filtering searches in the tree according to the information contained in + * those summaries. + * The extra macro argument is: + * a_summarize: + * Tree summarization function name, with the following prototype: + * + * bool a_summarize(a_type *a_node, const a_type *a_left_child, + * const a_type *a_right_child); + * + * This function should update a_node with the summary of the subtree rooted + * there, using the data contained in it and the summaries in a_left_child + * and a_right_child. One or both of them may be NULL. When the tree + * changes due to an insertion or removal, it updates the summaries of all + * nodes whose subtrees have changed (always updating the summaries of + * children before their parents). If the user alters a node in the tree in + * a way that may change its summary, they can call the generated + * update_summaries function to bubble up the summary changes to the root. + * It should return true if the summary changed (or may have changed), and + * false if it didn't (which will allow the implementation to terminate + * "bubbling up" the summaries early). + * As the parameter names indicate, the children are ordered as they are in + * the tree, a_left_child, if it is not NULL, compares less than a_node, + * which in turn compares less than a_right_child (if a_right_child is not + * NULL). + * + * Using the same setup as above but replacing the macro with + * rb_summarized_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp, + * ex_summarize) + * + * Generates all the previous functions, but adds some more: + * + * static void + * ex_update_summaries(ex_t *tree, ex_node_t *node); + * Description: Recompute all summaries of ancestors of node. + * Args: + * tree: Pointer to an initialized red-black tree object. + * node: The element of the tree whose summary may have changed. + * + * For each of ex_empty, ex_first, ex_last, ex_next, ex_prev, ex_search, + * ex_nsearch, ex_psearch, ex_iter, and ex_reverse_iter, an additional function + * is generated as well, with the suffix _filtered (e.g. ex_empty_filtered, + * ex_first_filtered, etc.). These use the concept of a "filter"; a binary + * property some node either satisfies or does not satisfy. Clever use of the + * a_summary argument to rb_summarized_gen can allow efficient computation of + * these predicates across whole subtrees of the tree. + * The extended API functions accept three additional arguments after the + * arguments to the corresponding non-extended equivalent. + * + * ex_fn(..., bool (*filter_node)(void *, ex_node_t *), + * bool (*filter_subtree)(void *, ex_node_t *), void *filter_ctx); + * filter_node : Returns true if the node passes the filter. + * filter_subtree : Returns true if some node in the subtree rooted at + * node passes the filter. + * filter_ctx : A context argument passed to the filters. + * + * For a more concrete example of summarizing and filtering, suppose we're using + * the red-black tree to track a set of integers: + * + * struct ex_node_s { + * rb_node(ex_node_t) ex_link; + * unsigned data; + * }; + * + * Suppose, for some application-specific reason, we want to be able to quickly + * find numbers in the set which are divisible by large powers of 2 (say, for + * aligned allocation purposes). We augment the node with a summary field: + * + * struct ex_node_s { + * rb_node(ex_node_t) ex_link; + * unsigned data; + * unsigned max_subtree_ffs; + * } + * + * and define our summarization function as follows: + * + * bool + * ex_summarize(ex_node_t *node, const ex_node_t *lchild, + * const ex_node_t *rchild) { + * unsigned new_max_subtree_ffs = ffs(node->data); + * if (lchild != NULL && lchild->max_subtree_ffs > new_max_subtree_ffs) { + * new_max_subtree_ffs = lchild->max_subtree_ffs; + * } + * if (rchild != NULL && rchild->max_subtree_ffs > new_max_subtree_ffs) { + * new_max_subtree_ffs = rchild->max_subtree_ffs; + * } + * bool changed = (node->max_subtree_ffs != new_max_subtree_ffs) + * node->max_subtree_ffs = new_max_subtree_ffs; + * // This could be "return true" without any correctness or big-O + * // performance changes; but practically, precisely reporting summary + * // changes reduces the amount of work that has to be done when "bubbling + * // up" summary changes. + * return changed; + * } + * + * We can now implement our filter functions as follows: + * bool + * ex_filter_node(void *filter_ctx, ex_node_t *node) { + * unsigned required_ffs = *(unsigned *)filter_ctx; + * return ffs(node->data) >= required_ffs; + * } + * bool + * ex_filter_subtree(void *filter_ctx, ex_node_t *node) { + * unsigned required_ffs = *(unsigned *)filter_ctx; + * return node->max_subtree_ffs >= required_ffs; + * } + * + * We can now easily search for, e.g., the smallest integer in the set that's + * divisible by 128: + * ex_node_t * + * find_div_128(ex_tree_t *tree) { + * unsigned min_ffs = 7; + * return ex_first_filtered(tree, &ex_filter_node, &ex_filter_subtree, + * &min_ffs); + * } + * + * We could with similar ease: + * - Fnd the next multiple of 128 in the set that's larger than 12345 (with + * ex_nsearch_filtered) + * - Iterate over just those multiples of 64 that are in the set (with + * ex_iter_filtered) + * - Determine if the set contains any multiples of 1024 (with + * ex_empty_filtered). + * + * Some possibly subtle API notes: + * - The node argument to ex_next_filtered and ex_prev_filtered need not pass + * the filter; it will find the next/prev node that passes the filter. + * - ex_search_filtered will fail even for a node in the tree, if that node does + * not pass the filter. ex_psearch_filtered and ex_nsearch_filtered behave + * similarly; they may return a node larger/smaller than the key, even if a + * node equivalent to the key is in the tree (but does not pass the filter). + * - Similarly, if the start argument to a filtered iteration function does not + * pass the filter, the callback won't be invoked on it. + * + * These should make sense after a moment's reflection; each post-condition is + * the same as with the unfiltered version, with the added constraint that the + * returned node must pass the filter. */ #define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \ + rb_gen_impl(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp, \ + rb_empty_summarize, false) +#define rb_summarized_gen(a_attr, a_prefix, a_rbt_type, a_type, \ + a_field, a_cmp, a_summarize) \ + rb_gen_impl(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp, \ + a_summarize, true) + +#define rb_gen_impl(a_attr, a_prefix, a_rbt_type, a_type, \ + a_field, a_cmp, a_summarize, a_is_summarized) \ +typedef struct { \ + a_type *node; \ + int cmp; \ +} a_prefix##path_entry_t; \ +static inline void \ +a_prefix##summarize_range(a_prefix##path_entry_t *rfirst, \ + a_prefix##path_entry_t *rlast) { \ + while ((uintptr_t)rlast >= (uintptr_t)rfirst) { \ + a_type *node = rlast->node; \ + /* Avoid a warning when a_summarize is rb_empty_summarize. */ \ + (void)node; \ + bool changed = a_summarize(node, rbtn_left_get(a_type, a_field, \ + node), rbtn_right_get(a_type, a_field, node)); \ + if (!changed) { \ + break; \ + } \ + rlast--; \ + } \ +} \ +/* On the remove pathways, we sometimes swap the node being removed */\ +/* and its first successor; in such cases we need to do two range */\ +/* updates; one from the node to its (former) swapped successor, the */\ +/* next from that successor to the root (with either allowed to */\ +/* bail out early if appropriate. */\ +static inline void \ +a_prefix##summarize_swapped_range(a_prefix##path_entry_t *rfirst, \ + a_prefix##path_entry_t *rlast, a_prefix##path_entry_t *swap_loc) { \ + if (swap_loc == NULL || rlast <= swap_loc) { \ + a_prefix##summarize_range(rfirst, rlast); \ + } else { \ + a_prefix##summarize_range(swap_loc + 1, rlast); \ + (void)a_summarize(swap_loc->node, \ + rbtn_left_get(a_type, a_field, swap_loc->node), \ + rbtn_right_get(a_type, a_field, swap_loc->node)); \ + a_prefix##summarize_range(rfirst, swap_loc - 1); \ + } \ +} \ a_attr void \ a_prefix##new(a_rbt_type *rbtree) { \ rb_new(a_type, a_field, rbtree); \ @@ -465,10 +732,8 @@ a_prefix##psearch(a_rbt_type *rbtree, const a_type *key) { \ } \ a_attr void \ a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ - struct { \ - a_type *node; \ - int cmp; \ - } path[sizeof(void *) << 4], *pathp; \ + a_prefix##path_entry_t path[RB_MAX_DEPTH]; \ + a_prefix##path_entry_t *pathp; \ rbt_node_new(a_type, a_field, rbtree, node); \ /* Wind. */ \ path->node = rbtree->rbt_root; \ @@ -484,6 +749,13 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ } \ } \ pathp->node = node; \ + /* A loop invariant we maintain is that all nodes with */\ + /* out-of-date summaries live in path[0], path[1], ..., *pathp. */\ + /* To maintain this, we have to summarize node, since we */\ + /* decrement pathp before the first iteration. */\ + assert(rbtn_left_get(a_type, a_field, node) == NULL); \ + assert(rbtn_right_get(a_type, a_field, node) == NULL); \ + (void)a_summarize(node, NULL, NULL); \ /* Unwind. */ \ for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ a_type *cnode = pathp->node; \ @@ -498,9 +770,13 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ a_type *tnode; \ rbtn_black_set(a_type, a_field, leftleft); \ rbtn_rotate_right(a_type, a_field, cnode, tnode); \ + (void)a_summarize(cnode, \ + rbtn_left_get(a_type, a_field, cnode), \ + rbtn_right_get(a_type, a_field, cnode)); \ cnode = tnode; \ } \ } else { \ + a_prefix##summarize_range(path, pathp); \ return; \ } \ } else { \ @@ -521,13 +797,20 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ rbtn_rotate_left(a_type, a_field, cnode, tnode); \ rbtn_color_set(a_type, a_field, tnode, tred); \ rbtn_red_set(a_type, a_field, cnode); \ + (void)a_summarize(cnode, \ + rbtn_left_get(a_type, a_field, cnode), \ + rbtn_right_get(a_type, a_field, cnode)); \ cnode = tnode; \ } \ } else { \ + a_prefix##summarize_range(path, pathp); \ return; \ } \ } \ pathp->node = cnode; \ + (void)a_summarize(cnode, \ + rbtn_left_get(a_type, a_field, cnode), \ + rbtn_right_get(a_type, a_field, cnode)); \ } \ /* Set root, and make it black. */ \ rbtree->rbt_root = path->node; \ @@ -535,12 +818,18 @@ a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ } \ a_attr void \ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ - struct { \ - a_type *node; \ - int cmp; \ - } *pathp, *nodep, path[sizeof(void *) << 4]; \ + a_prefix##path_entry_t path[RB_MAX_DEPTH]; \ + a_prefix##path_entry_t *pathp; \ + a_prefix##path_entry_t *nodep; \ + a_prefix##path_entry_t *swap_loc; \ + /* This is a "real" sentinel -- NULL means we didn't swap the */\ + /* node to be pruned with one of its successors, and so */\ + /* summarization can terminate early whenever some summary */\ + /* doesn't change. */\ + swap_loc = NULL; \ + /* This is just to silence a compiler warning. */ \ + nodep = NULL; \ /* Wind. */ \ - nodep = NULL; /* Silence compiler warning. */ \ path->node = rbtree->rbt_root; \ for (pathp = path; pathp->node != NULL; pathp++) { \ int cmp = pathp->cmp = a_cmp(node, pathp->node); \ @@ -567,6 +856,7 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ pathp--; \ if (pathp->node != node) { \ /* Swap node with its successor. */ \ + swap_loc = nodep; \ bool tred = rbtn_red_get(a_type, a_field, pathp->node); \ rbtn_color_set(a_type, a_field, pathp->node, \ rbtn_red_get(a_type, a_field, node)); \ @@ -604,6 +894,9 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_black_set(a_type, a_field, left); \ if (pathp == path) { \ rbtree->rbt_root = left; \ + /* Nothing to summarize -- the subtree rooted at the */\ + /* node's left child hasn't changed, and it's now the */\ + /* root. */\ } else { \ if (pathp[-1].cmp < 0) { \ rbtn_left_set(a_type, a_field, pathp[-1].node, \ @@ -612,6 +905,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, pathp[-1].node, \ left); \ } \ + a_prefix##summarize_swapped_range(path, &pathp[-1], \ + swap_loc); \ } \ return; \ } else if (pathp == path) { \ @@ -620,10 +915,15 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ return; \ } \ } \ + /* We've now established the invariant that the node has no right */\ + /* child (well, morally; we didn't bother nulling it out if we */\ + /* swapped it with its successor), and that the only nodes with */\ + /* out-of-date summaries live in path[0], path[1], ..., pathp[-1].*/\ if (rbtn_red_get(a_type, a_field, pathp->node)) { \ /* Prune red node, which requires no fixup. */ \ assert(pathp[-1].cmp < 0); \ rbtn_left_set(a_type, a_field, pathp[-1].node, NULL); \ + a_prefix##summarize_swapped_range(path, &pathp[-1], swap_loc); \ return; \ } \ /* The node to be pruned is black, so unwind until balance is */\ @@ -657,6 +957,12 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, pathp->node, tnode);\ rbtn_rotate_left(a_type, a_field, pathp->node, \ tnode); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ + (void)a_summarize(right, \ + rbtn_left_get(a_type, a_field, right), \ + rbtn_right_get(a_type, a_field, right)); \ } else { \ /* || */\ /* pathp(r) */\ @@ -667,7 +973,12 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ /* */\ rbtn_rotate_left(a_type, a_field, pathp->node, \ tnode); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ } \ + (void)a_summarize(tnode, rbtn_left_get(a_type, a_field, \ + tnode), rbtn_right_get(a_type, a_field, tnode)); \ /* Balance restored, but rotation modified subtree */\ /* root. */\ assert((uintptr_t)pathp > (uintptr_t)path); \ @@ -678,6 +989,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, pathp[-1].node, \ tnode); \ } \ + a_prefix##summarize_swapped_range(path, &pathp[-1], \ + swap_loc); \ return; \ } else { \ a_type *right = rbtn_right_get(a_type, a_field, \ @@ -698,6 +1011,15 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, pathp->node, tnode);\ rbtn_rotate_left(a_type, a_field, pathp->node, \ tnode); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ + (void)a_summarize(right, \ + rbtn_left_get(a_type, a_field, right), \ + rbtn_right_get(a_type, a_field, right)); \ + (void)a_summarize(tnode, \ + rbtn_left_get(a_type, a_field, tnode), \ + rbtn_right_get(a_type, a_field, tnode)); \ /* Balance restored, but rotation modified */\ /* subtree root, which may actually be the tree */\ /* root. */\ @@ -712,6 +1034,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, \ pathp[-1].node, tnode); \ } \ + a_prefix##summarize_swapped_range(path, \ + &pathp[-1], swap_loc); \ } \ return; \ } else { \ @@ -725,6 +1049,12 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_red_set(a_type, a_field, pathp->node); \ rbtn_rotate_left(a_type, a_field, pathp->node, \ tnode); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ + (void)a_summarize(tnode, \ + rbtn_left_get(a_type, a_field, tnode), \ + rbtn_right_get(a_type, a_field, tnode)); \ pathp->node = tnode; \ } \ } \ @@ -757,6 +1087,12 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ tnode); \ rbtn_right_set(a_type, a_field, unode, tnode); \ rbtn_rotate_left(a_type, a_field, unode, tnode); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ + (void)a_summarize(unode, \ + rbtn_left_get(a_type, a_field, unode), \ + rbtn_right_get(a_type, a_field, unode)); \ } else { \ /* || */\ /* pathp(b) */\ @@ -771,7 +1107,13 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_rotate_right(a_type, a_field, pathp->node, \ tnode); \ rbtn_black_set(a_type, a_field, tnode); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ } \ + (void)a_summarize(tnode, \ + rbtn_left_get(a_type, a_field, tnode), \ + rbtn_right_get(a_type, a_field, tnode)); \ /* Balance restored, but rotation modified subtree */\ /* root, which may actually be the tree root. */\ if (pathp == path) { \ @@ -785,6 +1127,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, pathp[-1].node, \ tnode); \ } \ + a_prefix##summarize_swapped_range(path, &pathp[-1], \ + swap_loc); \ } \ return; \ } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \ @@ -803,6 +1147,12 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_black_set(a_type, a_field, leftleft); \ rbtn_rotate_right(a_type, a_field, pathp->node, \ tnode); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ + (void)a_summarize(tnode, \ + rbtn_left_get(a_type, a_field, tnode), \ + rbtn_right_get(a_type, a_field, tnode)); \ /* Balance restored, but rotation modified */\ /* subtree root. */\ assert((uintptr_t)pathp > (uintptr_t)path); \ @@ -813,6 +1163,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, pathp[-1].node, \ tnode); \ } \ + a_prefix##summarize_swapped_range(path, &pathp[-1], \ + swap_loc); \ return; \ } else { \ /* || */\ @@ -824,6 +1176,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_red_set(a_type, a_field, left); \ rbtn_black_set(a_type, a_field, pathp->node); \ /* Balance restored. */ \ + a_prefix##summarize_swapped_range(path, pathp, \ + swap_loc); \ return; \ } \ } else { \ @@ -840,6 +1194,12 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_black_set(a_type, a_field, leftleft); \ rbtn_rotate_right(a_type, a_field, pathp->node, \ tnode); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ + (void)a_summarize(tnode, \ + rbtn_left_get(a_type, a_field, tnode), \ + rbtn_right_get(a_type, a_field, tnode)); \ /* Balance restored, but rotation modified */\ /* subtree root, which may actually be the tree */\ /* root. */\ @@ -854,6 +1214,8 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ rbtn_right_set(a_type, a_field, \ pathp[-1].node, tnode); \ } \ + a_prefix##summarize_swapped_range(path, \ + &pathp[-1], swap_loc); \ } \ return; \ } else { \ @@ -864,6 +1226,9 @@ a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ /* / */\ /* (b) */\ rbtn_red_set(a_type, a_field, left); \ + (void)a_summarize(pathp->node, \ + rbtn_left_get(a_type, a_field, pathp->node), \ + rbtn_right_get(a_type, a_field, pathp->node)); \ } \ } \ } \ @@ -1001,6 +1366,491 @@ a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ void *arg) { \ a_prefix##destroy_recurse(rbtree, rbtree->rbt_root, cb, arg); \ rbtree->rbt_root = NULL; \ -} +} \ +/* BEGIN SUMMARIZED-ONLY IMPLEMENTATION */ \ +rb_summarized_only_##a_is_summarized( \ +static inline a_prefix##path_entry_t * \ +a_prefix##wind(a_rbt_type *rbtree, \ + a_prefix##path_entry_t path[RB_MAX_DEPTH], a_type *node) { \ + a_prefix##path_entry_t *pathp; \ + path->node = rbtree->rbt_root; \ + for (pathp = path; ; pathp++) { \ + assert((size_t)(pathp - path) < RB_MAX_DEPTH); \ + pathp->cmp = a_cmp(node, pathp->node); \ + if (pathp->cmp < 0) { \ + pathp[1].node = rbtn_left_get(a_type, a_field, \ + pathp->node); \ + } else if (pathp->cmp == 0) { \ + return pathp; \ + } else { \ + pathp[1].node = rbtn_right_get(a_type, a_field, \ + pathp->node); \ + } \ + } \ + unreachable(); \ +} \ +a_attr void \ +a_prefix##update_summaries(a_rbt_type *rbtree, a_type *node) { \ + a_prefix##path_entry_t path[RB_MAX_DEPTH]; \ + a_prefix##path_entry_t *pathp = a_prefix##wind(rbtree, path, node); \ + a_prefix##summarize_range(path, pathp); \ +} \ +a_attr bool \ +a_prefix##empty_filtered(a_rbt_type *rbtree, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *node = rbtree->rbt_root; \ + return node == NULL || !filter_subtree(filter_ctx, node); \ +} \ +static inline a_type * \ +a_prefix##first_filtered_from_node(a_type *node, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + assert(node != NULL && filter_subtree(filter_ctx, node)); \ + while (true) { \ + a_type *left = rbtn_left_get(a_type, a_field, node); \ + a_type *right = rbtn_right_get(a_type, a_field, node); \ + if (left != NULL && filter_subtree(filter_ctx, left)) { \ + node = left; \ + } else if (filter_node(filter_ctx, node)) { \ + return node; \ + } else { \ + assert(right != NULL \ + && filter_subtree(filter_ctx, right)); \ + node = right; \ + } \ + } \ + unreachable(); \ +} \ +a_attr a_type * \ +a_prefix##first_filtered(a_rbt_type *rbtree, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *node = rbtree->rbt_root; \ + if (node == NULL || !filter_subtree(filter_ctx, node)) { \ + return NULL; \ + } \ + return a_prefix##first_filtered_from_node(node, filter_node, \ + filter_subtree, filter_ctx); \ +} \ +static inline a_type * \ +a_prefix##last_filtered_from_node(a_type *node, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + assert(node != NULL && filter_subtree(filter_ctx, node)); \ + while (true) { \ + a_type *left = rbtn_left_get(a_type, a_field, node); \ + a_type *right = rbtn_right_get(a_type, a_field, node); \ + if (right != NULL && filter_subtree(filter_ctx, right)) { \ + node = right; \ + } else if (filter_node(filter_ctx, node)) { \ + return node; \ + } else { \ + assert(left != NULL \ + && filter_subtree(filter_ctx, left)); \ + node = left; \ + } \ + } \ + unreachable(); \ +} \ +a_attr a_type * \ +a_prefix##last_filtered(a_rbt_type *rbtree, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *node = rbtree->rbt_root; \ + if (node == NULL || !filter_subtree(filter_ctx, node)) { \ + return NULL; \ + } \ + return a_prefix##last_filtered_from_node(node, filter_node, \ + filter_subtree, filter_ctx); \ +} \ +/* Internal implementation function. Search for a node comparing */\ +/* equal to key matching the filter. If such a node is in the tree, */\ +/* return it. Additionally, the caller has the option to ask for */\ +/* bounds on the next / prev node in the tree passing the filter. */\ +/* If nextbound is true, then this function will do one of the */\ +/* following: */\ +/* - Fill in *nextbound_node with the smallest node in the tree */\ +/* greater than key passing the filter, and NULL-out */\ +/* *nextbound_subtree. */\ +/* - Fill in *nextbound_subtree with a parent of that node which is */\ +/* not a parent of the searched-for node, and NULL-out */\ +/* *nextbound_node. */\ +/* - NULL-out both *nextbound_node and *nextbound_subtree, in which */\ +/* case no node greater than key but passing the filter is in the */\ +/* tree. */\ +/* The prevbound case is similar. If the caller knows that key is in */\ +/* the tree and that the subtree rooted at key does not contain a */\ +/* node satisfying the bound being searched for, then they can pass */\ +/* false for include_subtree, in which case we won't bother searching */\ +/* there (risking a cache miss). */\ +/* */\ +/* This API is unfortunately complex; but the logic for filtered */\ +/* searches is very subtle, and otherwise we would have to repeat it */\ +/* multiple times for filtered search, nsearch, psearch, next, and */\ +/* prev. */\ +static inline a_type * \ +a_prefix##search_with_filter_bounds(a_rbt_type *rbtree, \ + const a_type *key, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx, \ + bool include_subtree, \ + bool nextbound, a_type **nextbound_node, a_type **nextbound_subtree, \ + bool prevbound, a_type **prevbound_node, a_type **prevbound_subtree) {\ + if (nextbound) { \ + *nextbound_node = NULL; \ + *nextbound_subtree = NULL; \ + } \ + if (prevbound) { \ + *prevbound_node = NULL; \ + *prevbound_subtree = NULL; \ + } \ + a_type *tnode = rbtree->rbt_root; \ + while (tnode != NULL && filter_subtree(filter_ctx, tnode)) { \ + int cmp = a_cmp(key, tnode); \ + a_type *tleft = rbtn_left_get(a_type, a_field, tnode); \ + a_type *tright = rbtn_right_get(a_type, a_field, tnode); \ + if (cmp < 0) { \ + if (nextbound) { \ + if (filter_node(filter_ctx, tnode)) { \ + *nextbound_node = tnode; \ + *nextbound_subtree = NULL; \ + } else if (tright != NULL && filter_subtree( \ + filter_ctx, tright)) { \ + *nextbound_node = NULL; \ + *nextbound_subtree = tright; \ + } \ + } \ + tnode = tleft; \ + } else if (cmp > 0) { \ + if (prevbound) { \ + if (filter_node(filter_ctx, tnode)) { \ + *prevbound_node = tnode; \ + *prevbound_subtree = NULL; \ + } else if (tleft != NULL && filter_subtree( \ + filter_ctx, tleft)) { \ + *prevbound_node = NULL; \ + *prevbound_subtree = tleft; \ + } \ + } \ + tnode = tright; \ + } else { \ + if (filter_node(filter_ctx, tnode)) { \ + return tnode; \ + } \ + if (include_subtree) { \ + if (prevbound && tleft != NULL && filter_subtree( \ + filter_ctx, tleft)) { \ + *prevbound_node = NULL; \ + *prevbound_subtree = tleft; \ + } \ + if (nextbound && tright != NULL && filter_subtree( \ + filter_ctx, tright)) { \ + *nextbound_node = NULL; \ + *nextbound_subtree = tright; \ + } \ + } \ + return NULL; \ + } \ + } \ + return NULL; \ +} \ +a_attr a_type * \ +a_prefix##next_filtered(a_rbt_type *rbtree, a_type *node, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *nright = rbtn_right_get(a_type, a_field, node); \ + if (nright != NULL && filter_subtree(filter_ctx, nright)) { \ + return a_prefix##first_filtered_from_node(nright, filter_node, \ + filter_subtree, filter_ctx); \ + } \ + a_type *node_candidate; \ + a_type *subtree_candidate; \ + a_type *search_result = a_prefix##search_with_filter_bounds( \ + rbtree, node, filter_node, filter_subtree, filter_ctx, \ + /* include_subtree */ false, \ + /* nextbound */ true, &node_candidate, &subtree_candidate, \ + /* prevbound */ false, NULL, NULL); \ + assert(node == search_result \ + || !filter_node(filter_ctx, node)); \ + if (node_candidate != NULL) { \ + return node_candidate; \ + } \ + if (subtree_candidate != NULL) { \ + return a_prefix##first_filtered_from_node( \ + subtree_candidate, filter_node, filter_subtree, \ + filter_ctx); \ + } \ + return NULL; \ +} \ +a_attr a_type * \ +a_prefix##prev_filtered(a_rbt_type *rbtree, a_type *node, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *nleft = rbtn_left_get(a_type, a_field, node); \ + if (nleft != NULL && filter_subtree(filter_ctx, nleft)) { \ + return a_prefix##last_filtered_from_node(nleft, filter_node, \ + filter_subtree, filter_ctx); \ + } \ + a_type *node_candidate; \ + a_type *subtree_candidate; \ + a_type *search_result = a_prefix##search_with_filter_bounds( \ + rbtree, node, filter_node, filter_subtree, filter_ctx, \ + /* include_subtree */ false, \ + /* nextbound */ false, NULL, NULL, \ + /* prevbound */ true, &node_candidate, &subtree_candidate); \ + assert(node == search_result \ + || !filter_node(filter_ctx, node)); \ + if (node_candidate != NULL) { \ + return node_candidate; \ + } \ + if (subtree_candidate != NULL) { \ + return a_prefix##last_filtered_from_node( \ + subtree_candidate, filter_node, filter_subtree, \ + filter_ctx); \ + } \ + return NULL; \ +} \ +a_attr a_type * \ +a_prefix##search_filtered(a_rbt_type *rbtree, const a_type *key, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *result = a_prefix##search_with_filter_bounds(rbtree, key, \ + filter_node, filter_subtree, filter_ctx, \ + /* include_subtree */ false, \ + /* nextbound */ false, NULL, NULL, \ + /* prevbound */ false, NULL, NULL); \ + return result; \ +} \ +a_attr a_type * \ +a_prefix##nsearch_filtered(a_rbt_type *rbtree, const a_type *key, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *node_candidate; \ + a_type *subtree_candidate; \ + a_type *result = a_prefix##search_with_filter_bounds(rbtree, key, \ + filter_node, filter_subtree, filter_ctx, \ + /* include_subtree */ true, \ + /* nextbound */ true, &node_candidate, &subtree_candidate, \ + /* prevbound */ false, NULL, NULL); \ + if (result != NULL) { \ + return result; \ + } \ + if (node_candidate != NULL) { \ + return node_candidate; \ + } \ + if (subtree_candidate != NULL) { \ + return a_prefix##first_filtered_from_node( \ + subtree_candidate, filter_node, filter_subtree, \ + filter_ctx); \ + } \ + return NULL; \ +} \ +a_attr a_type * \ +a_prefix##psearch_filtered(a_rbt_type *rbtree, const a_type *key, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *node_candidate; \ + a_type *subtree_candidate; \ + a_type *result = a_prefix##search_with_filter_bounds(rbtree, key, \ + filter_node, filter_subtree, filter_ctx, \ + /* include_subtree */ true, \ + /* nextbound */ false, NULL, NULL, \ + /* prevbound */ true, &node_candidate, &subtree_candidate); \ + if (result != NULL) { \ + return result; \ + } \ + if (node_candidate != NULL) { \ + return node_candidate; \ + } \ + if (subtree_candidate != NULL) { \ + return a_prefix##last_filtered_from_node( \ + subtree_candidate, filter_node, filter_subtree, \ + filter_ctx); \ + } \ + return NULL; \ +} \ +a_attr a_type * \ +a_prefix##iter_recurse_filtered(a_rbt_type *rbtree, a_type *node, \ + a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + if (node == NULL || !filter_subtree(filter_ctx, node)) { \ + return NULL; \ + } \ + a_type *ret; \ + a_type *left = rbtn_left_get(a_type, a_field, node); \ + a_type *right = rbtn_right_get(a_type, a_field, node); \ + ret = a_prefix##iter_recurse_filtered(rbtree, left, cb, arg, \ + filter_node, filter_subtree, filter_ctx); \ + if (ret != NULL) { \ + return ret; \ + } \ + if (filter_node(filter_ctx, node)) { \ + ret = cb(rbtree, node, arg); \ + } \ + if (ret != NULL) { \ + return ret; \ + } \ + return a_prefix##iter_recurse_filtered(rbtree, right, cb, arg, \ + filter_node, filter_subtree, filter_ctx); \ +} \ +a_attr a_type * \ +a_prefix##iter_start_filtered(a_rbt_type *rbtree, a_type *start, \ + a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \ + void *arg, bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + if (!filter_subtree(filter_ctx, node)) { \ + return NULL; \ + } \ + int cmp = a_cmp(start, node); \ + a_type *ret; \ + a_type *left = rbtn_left_get(a_type, a_field, node); \ + a_type *right = rbtn_right_get(a_type, a_field, node); \ + if (cmp < 0) { \ + ret = a_prefix##iter_start_filtered(rbtree, start, left, cb, \ + arg, filter_node, filter_subtree, filter_ctx); \ + if (ret != NULL) { \ + return ret; \ + } \ + if (filter_node(filter_ctx, node)) { \ + ret = cb(rbtree, node, arg); \ + if (ret != NULL) { \ + return ret; \ + } \ + } \ + return a_prefix##iter_recurse_filtered(rbtree, right, cb, arg, \ + filter_node, filter_subtree, filter_ctx); \ + } else if (cmp > 0) { \ + return a_prefix##iter_start_filtered(rbtree, start, right, \ + cb, arg, filter_node, filter_subtree, filter_ctx); \ + } else { \ + if (filter_node(filter_ctx, node)) { \ + ret = cb(rbtree, node, arg); \ + if (ret != NULL) { \ + return ret; \ + } \ + } \ + return a_prefix##iter_recurse_filtered(rbtree, right, cb, arg, \ + filter_node, filter_subtree, filter_ctx); \ + } \ +} \ +a_attr a_type * \ +a_prefix##iter_filtered(a_rbt_type *rbtree, a_type *start, \ + a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *ret; \ + if (start != NULL) { \ + ret = a_prefix##iter_start_filtered(rbtree, start, \ + rbtree->rbt_root, cb, arg, filter_node, filter_subtree, \ + filter_ctx); \ + } else { \ + ret = a_prefix##iter_recurse_filtered(rbtree, rbtree->rbt_root, \ + cb, arg, filter_node, filter_subtree, filter_ctx); \ + } \ + return ret; \ +} \ +a_attr a_type * \ +a_prefix##reverse_iter_recurse_filtered(a_rbt_type *rbtree, \ + a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \ + void *arg, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + if (node == NULL || !filter_subtree(filter_ctx, node)) { \ + return NULL; \ + } \ + a_type *ret; \ + a_type *left = rbtn_left_get(a_type, a_field, node); \ + a_type *right = rbtn_right_get(a_type, a_field, node); \ + ret = a_prefix##reverse_iter_recurse_filtered(rbtree, right, cb, \ + arg, filter_node, filter_subtree, filter_ctx); \ + if (ret != NULL) { \ + return ret; \ + } \ + if (filter_node(filter_ctx, node)) { \ + ret = cb(rbtree, node, arg); \ + } \ + if (ret != NULL) { \ + return ret; \ + } \ + return a_prefix##reverse_iter_recurse_filtered(rbtree, left, cb, \ + arg, filter_node, filter_subtree, filter_ctx); \ +} \ +a_attr a_type * \ +a_prefix##reverse_iter_start_filtered(a_rbt_type *rbtree, a_type *start,\ + a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \ + void *arg, bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + if (!filter_subtree(filter_ctx, node)) { \ + return NULL; \ + } \ + int cmp = a_cmp(start, node); \ + a_type *ret; \ + a_type *left = rbtn_left_get(a_type, a_field, node); \ + a_type *right = rbtn_right_get(a_type, a_field, node); \ + if (cmp > 0) { \ + ret = a_prefix##reverse_iter_start_filtered(rbtree, start, \ + right, cb, arg, filter_node, filter_subtree, filter_ctx); \ + if (ret != NULL) { \ + return ret; \ + } \ + if (filter_node(filter_ctx, node)) { \ + ret = cb(rbtree, node, arg); \ + if (ret != NULL) { \ + return ret; \ + } \ + } \ + return a_prefix##reverse_iter_recurse_filtered(rbtree, left, cb,\ + arg, filter_node, filter_subtree, filter_ctx); \ + } else if (cmp < 0) { \ + return a_prefix##reverse_iter_start_filtered(rbtree, start, \ + left, cb, arg, filter_node, filter_subtree, filter_ctx); \ + } else { \ + if (filter_node(filter_ctx, node)) { \ + ret = cb(rbtree, node, arg); \ + if (ret != NULL) { \ + return ret; \ + } \ + } \ + return a_prefix##reverse_iter_recurse_filtered(rbtree, left, cb,\ + arg, filter_node, filter_subtree, filter_ctx); \ + } \ +} \ +a_attr a_type * \ +a_prefix##reverse_iter_filtered(a_rbt_type *rbtree, a_type *start, \ + a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg, \ + bool (*filter_node)(void *, a_type *), \ + bool (*filter_subtree)(void *, a_type *), \ + void *filter_ctx) { \ + a_type *ret; \ + if (start != NULL) { \ + ret = a_prefix##reverse_iter_start_filtered(rbtree, start, \ + rbtree->rbt_root, cb, arg, filter_node, filter_subtree, \ + filter_ctx); \ + } else { \ + ret = a_prefix##reverse_iter_recurse_filtered(rbtree, \ + rbtree->rbt_root, cb, arg, filter_node, filter_subtree, \ + filter_ctx); \ + } \ + return ret; \ +} \ +) /* end rb_summarized_only */ -#endif /* RB_H_ */ +#endif /* JEMALLOC_INTERNAL_RB_H */ |