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) \ |
41 | struct { \ |
42 | a_type *rbn_left; \ |
43 | a_type *rbn_right_red; \ |
44 | } |
45 | #else |
46 | #define rb_node(a_type) \ |
47 | struct { \ |
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) \ |
56 | struct { \ |
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) \ |
187 | a_attr void \ |
188 | a_prefix##new(a_rbt_type *rbtree); \ |
189 | a_attr bool \ |
190 | a_prefix##empty(a_rbt_type *rbtree); \ |
191 | a_attr a_type * \ |
192 | a_prefix##first(a_rbt_type *rbtree); \ |
193 | a_attr a_type * \ |
194 | a_prefix##last(a_rbt_type *rbtree); \ |
195 | a_attr a_type * \ |
196 | a_prefix##next(a_rbt_type *rbtree, a_type *node); \ |
197 | a_attr a_type * \ |
198 | a_prefix##prev(a_rbt_type *rbtree, a_type *node); \ |
199 | a_attr a_type * \ |
200 | a_prefix##search(a_rbt_type *rbtree, const a_type *key); \ |
201 | a_attr a_type * \ |
202 | a_prefix##nsearch(a_rbt_type *rbtree, const a_type *key); \ |
203 | a_attr a_type * \ |
204 | a_prefix##psearch(a_rbt_type *rbtree, const a_type *key); \ |
205 | a_attr void \ |
206 | a_prefix##insert(a_rbt_type *rbtree, a_type *node); \ |
207 | a_attr void \ |
208 | a_prefix##remove(a_rbt_type *rbtree, a_type *node); \ |
209 | a_attr a_type * \ |
210 | a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ |
211 | a_rbt_type *, a_type *, void *), void *arg); \ |
212 | a_attr a_type * \ |
213 | a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ |
214 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); \ |
215 | a_attr void \ |
216 | a_prefix##destroy(a_rbt_type *rbtree, void (*cb)(a_type *, void *), \ |
217 | void *arg); \ |
218 | /* Extended API */ \ |
219 | rb_summarized_only_##a_is_summarized( \ |
220 | a_attr void \ |
221 | a_prefix##update_summaries(a_rbt_type *rbtree, a_type *node); \ |
222 | a_attr bool \ |
223 | a_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); \ |
227 | a_attr a_type * \ |
228 | a_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); \ |
232 | a_attr a_type * \ |
233 | a_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); \ |
237 | a_attr a_type * \ |
238 | a_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); \ |
242 | a_attr a_type * \ |
243 | a_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); \ |
247 | a_attr a_type * \ |
248 | a_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); \ |
252 | a_attr a_type * \ |
253 | a_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); \ |
257 | a_attr a_type * \ |
258 | a_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); \ |
262 | a_attr a_type * \ |
263 | a_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); \ |
268 | a_attr a_type * \ |
269 | a_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) \ |
573 | typedef struct { \ |
574 | a_type *node; \ |
575 | int cmp; \ |
576 | } a_prefix##path_entry_t; \ |
577 | static inline void \ |
578 | a_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. */\ |
597 | static inline void \ |
598 | a_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 | } \ |
610 | a_attr void \ |
611 | a_prefix##new(a_rbt_type *rbtree) { \ |
612 | rb_new(a_type, a_field, rbtree); \ |
613 | } \ |
614 | a_attr bool \ |
615 | a_prefix##empty(a_rbt_type *rbtree) { \ |
616 | return (rbtree->rbt_root == NULL); \ |
617 | } \ |
618 | a_attr a_type * \ |
619 | a_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 | } \ |
624 | a_attr a_type * \ |
625 | a_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 | } \ |
630 | a_attr a_type * \ |
631 | a_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 | } \ |
655 | a_attr a_type * \ |
656 | a_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 | } \ |
680 | a_attr a_type * \ |
681 | a_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 | } \ |
695 | a_attr a_type * \ |
696 | a_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 | } \ |
714 | a_attr a_type * \ |
715 | a_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 | } \ |
733 | a_attr void \ |
734 | a_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 | } \ |
819 | a_attr void \ |
820 | a_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 | } \ |
1240 | a_attr a_type * \ |
1241 | a_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 | } \ |
1256 | a_attr a_type * \ |
1257 | a_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 | } \ |
1281 | a_attr a_type * \ |
1282 | a_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 | } \ |
1293 | a_attr a_type * \ |
1294 | a_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 | } \ |
1309 | a_attr a_type * \ |
1310 | a_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 | } \ |
1335 | a_attr a_type * \ |
1336 | a_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 | } \ |
1348 | a_attr void \ |
1349 | a_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 | } \ |
1364 | a_attr void \ |
1365 | a_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 */ \ |
1371 | rb_summarized_only_##a_is_summarized( \ |
1372 | static inline a_prefix##path_entry_t * \ |
1373 | a_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 | } \ |
1392 | a_attr void \ |
1393 | a_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 | } \ |
1398 | a_attr bool \ |
1399 | a_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 | } \ |
1406 | static inline a_type * \ |
1407 | a_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 | } \ |
1427 | a_attr a_type * \ |
1428 | a_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 | } \ |
1439 | static inline a_type * \ |
1440 | a_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 | } \ |
1460 | a_attr a_type * \ |
1461 | a_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. */\ |
1497 | static inline a_type * \ |
1498 | a_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 | } \ |
1564 | a_attr a_type * \ |
1565 | a_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 | } \ |
1593 | a_attr a_type * \ |
1594 | a_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 | } \ |
1622 | a_attr a_type * \ |
1623 | a_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 | } \ |
1634 | a_attr a_type * \ |
1635 | a_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 | } \ |
1659 | a_attr a_type * \ |
1660 | a_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 | } \ |
1684 | a_attr a_type * \ |
1685 | a_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 | } \ |
1710 | a_attr a_type * \ |
1711 | a_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 | } \ |
1751 | a_attr a_type * \ |
1752 | a_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 | } \ |
1768 | a_attr a_type * \ |
1769 | a_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 | } \ |
1795 | a_attr a_type * \ |
1796 | a_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 | } \ |
1836 | a_attr a_type * \ |
1837 | a_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 | |