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