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