1234370Sjasone/*- 2234370Sjasone ******************************************************************************* 3234370Sjasone * 4234370Sjasone * cpp macro implementation of left-leaning 2-3 red-black trees. Parent 5234370Sjasone * pointers are not used, and color bits are stored in the least significant 6234370Sjasone * bit of right-child pointers (if RB_COMPACT is defined), thus making node 7234370Sjasone * linkage as compact as is possible for red-black trees. 8234370Sjasone * 9234370Sjasone * Usage: 10234370Sjasone * 11234370Sjasone * #include <stdint.h> 12234370Sjasone * #include <stdbool.h> 13234370Sjasone * #define NDEBUG // (Optional, see assert(3).) 14234370Sjasone * #include <assert.h> 15234370Sjasone * #define RB_COMPACT // (Optional, embed color bits in right-child pointers.) 16234370Sjasone * #include <rb.h> 17234370Sjasone * ... 18234370Sjasone * 19234370Sjasone ******************************************************************************* 20234370Sjasone */ 21234370Sjasone 22234370Sjasone#ifndef RB_H_ 23234370Sjasone#define RB_H_ 24234370Sjasone 25234370Sjasone#if 0 26234370Sjasone__FBSDID("$FreeBSD$"); 27234370Sjasone#endif 28234370Sjasone 29234370Sjasone#ifdef RB_COMPACT 30234370Sjasone/* Node structure. */ 31234370Sjasone#define rb_node(a_type) \ 32234370Sjasonestruct { \ 33234370Sjasone a_type *rbn_left; \ 34234370Sjasone a_type *rbn_right_red; \ 35234370Sjasone} 36234370Sjasone#else 37234370Sjasone#define rb_node(a_type) \ 38234370Sjasonestruct { \ 39234370Sjasone a_type *rbn_left; \ 40234370Sjasone a_type *rbn_right; \ 41234370Sjasone bool rbn_red; \ 42234370Sjasone} 43234370Sjasone#endif 44234370Sjasone 45234370Sjasone/* Root structure. */ 46234370Sjasone#define rb_tree(a_type) \ 47234370Sjasonestruct { \ 48234370Sjasone a_type *rbt_root; \ 49234370Sjasone a_type rbt_nil; \ 50234370Sjasone} 51234370Sjasone 52234370Sjasone/* Left accessors. */ 53234370Sjasone#define rbtn_left_get(a_type, a_field, a_node) \ 54234370Sjasone ((a_node)->a_field.rbn_left) 55234370Sjasone#define rbtn_left_set(a_type, a_field, a_node, a_left) do { \ 56234370Sjasone (a_node)->a_field.rbn_left = a_left; \ 57234370Sjasone} while (0) 58234370Sjasone 59234370Sjasone#ifdef RB_COMPACT 60234370Sjasone/* Right accessors. */ 61234370Sjasone#define rbtn_right_get(a_type, a_field, a_node) \ 62234370Sjasone ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \ 63234370Sjasone & ((ssize_t)-2))) 64234370Sjasone#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \ 65234370Sjasone (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \ 66234370Sjasone | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \ 67234370Sjasone} while (0) 68234370Sjasone 69234370Sjasone/* Color accessors. */ 70234370Sjasone#define rbtn_red_get(a_type, a_field, a_node) \ 71234370Sjasone ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \ 72234370Sjasone & ((size_t)1))) 73234370Sjasone#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \ 74234370Sjasone (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \ 75234370Sjasone (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \ 76234370Sjasone | ((ssize_t)a_red)); \ 77234370Sjasone} while (0) 78234370Sjasone#define rbtn_red_set(a_type, a_field, a_node) do { \ 79234370Sjasone (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \ 80234370Sjasone (a_node)->a_field.rbn_right_red) | ((size_t)1)); \ 81234370Sjasone} while (0) 82234370Sjasone#define rbtn_black_set(a_type, a_field, a_node) do { \ 83234370Sjasone (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \ 84234370Sjasone (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \ 85234370Sjasone} while (0) 86234370Sjasone#else 87234370Sjasone/* Right accessors. */ 88234370Sjasone#define rbtn_right_get(a_type, a_field, a_node) \ 89234370Sjasone ((a_node)->a_field.rbn_right) 90234370Sjasone#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \ 91234370Sjasone (a_node)->a_field.rbn_right = a_right; \ 92234370Sjasone} while (0) 93234370Sjasone 94234370Sjasone/* Color accessors. */ 95234370Sjasone#define rbtn_red_get(a_type, a_field, a_node) \ 96234370Sjasone ((a_node)->a_field.rbn_red) 97234370Sjasone#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \ 98234370Sjasone (a_node)->a_field.rbn_red = (a_red); \ 99234370Sjasone} while (0) 100234370Sjasone#define rbtn_red_set(a_type, a_field, a_node) do { \ 101234370Sjasone (a_node)->a_field.rbn_red = true; \ 102234370Sjasone} while (0) 103234370Sjasone#define rbtn_black_set(a_type, a_field, a_node) do { \ 104234370Sjasone (a_node)->a_field.rbn_red = false; \ 105234370Sjasone} while (0) 106234370Sjasone#endif 107234370Sjasone 108234370Sjasone/* Node initializer. */ 109234370Sjasone#define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \ 110234370Sjasone rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \ 111234370Sjasone rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \ 112234370Sjasone rbtn_red_set(a_type, a_field, (a_node)); \ 113234370Sjasone} while (0) 114234370Sjasone 115234370Sjasone/* Tree initializer. */ 116234370Sjasone#define rb_new(a_type, a_field, a_rbt) do { \ 117234370Sjasone (a_rbt)->rbt_root = &(a_rbt)->rbt_nil; \ 118234370Sjasone rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil); \ 119234370Sjasone rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil); \ 120234370Sjasone} while (0) 121234370Sjasone 122234370Sjasone/* Internal utility macros. */ 123234370Sjasone#define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \ 124234370Sjasone (r_node) = (a_root); \ 125234370Sjasone if ((r_node) != &(a_rbt)->rbt_nil) { \ 126234370Sjasone for (; \ 127234370Sjasone rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\ 128234370Sjasone (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \ 129234370Sjasone } \ 130234370Sjasone } \ 131234370Sjasone} while (0) 132234370Sjasone 133234370Sjasone#define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \ 134234370Sjasone (r_node) = (a_root); \ 135234370Sjasone if ((r_node) != &(a_rbt)->rbt_nil) { \ 136234370Sjasone for (; rbtn_right_get(a_type, a_field, (r_node)) != \ 137234370Sjasone &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \ 138234370Sjasone (r_node))) { \ 139234370Sjasone } \ 140234370Sjasone } \ 141234370Sjasone} while (0) 142234370Sjasone 143234370Sjasone#define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \ 144234370Sjasone (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \ 145234370Sjasone rbtn_right_set(a_type, a_field, (a_node), \ 146234370Sjasone rbtn_left_get(a_type, a_field, (r_node))); \ 147234370Sjasone rbtn_left_set(a_type, a_field, (r_node), (a_node)); \ 148234370Sjasone} while (0) 149234370Sjasone 150234370Sjasone#define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \ 151234370Sjasone (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \ 152234370Sjasone rbtn_left_set(a_type, a_field, (a_node), \ 153234370Sjasone rbtn_right_get(a_type, a_field, (r_node))); \ 154234370Sjasone rbtn_right_set(a_type, a_field, (r_node), (a_node)); \ 155234370Sjasone} while (0) 156234370Sjasone 157234370Sjasone/* 158234370Sjasone * The rb_proto() macro generates function prototypes that correspond to the 159234370Sjasone * functions generated by an equivalently parameterized call to rb_gen(). 160234370Sjasone */ 161234370Sjasone 162234370Sjasone#define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \ 163234370Sjasonea_attr void \ 164234370Sjasonea_prefix##new(a_rbt_type *rbtree); \ 165234370Sjasonea_attr a_type * \ 166234370Sjasonea_prefix##first(a_rbt_type *rbtree); \ 167234370Sjasonea_attr a_type * \ 168234370Sjasonea_prefix##last(a_rbt_type *rbtree); \ 169234370Sjasonea_attr a_type * \ 170234370Sjasonea_prefix##next(a_rbt_type *rbtree, a_type *node); \ 171234370Sjasonea_attr a_type * \ 172234370Sjasonea_prefix##prev(a_rbt_type *rbtree, a_type *node); \ 173234370Sjasonea_attr a_type * \ 174234370Sjasonea_prefix##search(a_rbt_type *rbtree, a_type *key); \ 175234370Sjasonea_attr a_type * \ 176234370Sjasonea_prefix##nsearch(a_rbt_type *rbtree, a_type *key); \ 177234370Sjasonea_attr a_type * \ 178234370Sjasonea_prefix##psearch(a_rbt_type *rbtree, a_type *key); \ 179234370Sjasonea_attr void \ 180234370Sjasonea_prefix##insert(a_rbt_type *rbtree, a_type *node); \ 181234370Sjasonea_attr void \ 182234370Sjasonea_prefix##remove(a_rbt_type *rbtree, a_type *node); \ 183234370Sjasonea_attr a_type * \ 184234370Sjasonea_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ 185234370Sjasone a_rbt_type *, a_type *, void *), void *arg); \ 186234370Sjasonea_attr a_type * \ 187234370Sjasonea_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ 188234370Sjasone a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); 189234370Sjasone 190234370Sjasone/* 191234370Sjasone * The rb_gen() macro generates a type-specific red-black tree implementation, 192234370Sjasone * based on the above cpp macros. 193234370Sjasone * 194234370Sjasone * Arguments: 195234370Sjasone * 196234370Sjasone * a_attr : Function attribute for generated functions (ex: static). 197234370Sjasone * a_prefix : Prefix for generated functions (ex: ex_). 198234370Sjasone * a_rb_type : Type for red-black tree data structure (ex: ex_t). 199234370Sjasone * a_type : Type for red-black tree node data structure (ex: ex_node_t). 200234370Sjasone * a_field : Name of red-black tree node linkage (ex: ex_link). 201234370Sjasone * a_cmp : Node comparison function name, with the following prototype: 202234370Sjasone * int (a_cmp *)(a_type *a_node, a_type *a_other); 203234370Sjasone * ^^^^^^ 204234370Sjasone * or a_key 205234370Sjasone * Interpretation of comparision function return values: 206234370Sjasone * -1 : a_node < a_other 207234370Sjasone * 0 : a_node == a_other 208234370Sjasone * 1 : a_node > a_other 209234370Sjasone * In all cases, the a_node or a_key macro argument is the first 210234370Sjasone * argument to the comparison function, which makes it possible 211234370Sjasone * to write comparison functions that treat the first argument 212234370Sjasone * specially. 213234370Sjasone * 214234370Sjasone * Assuming the following setup: 215234370Sjasone * 216234370Sjasone * typedef struct ex_node_s ex_node_t; 217234370Sjasone * struct ex_node_s { 218234370Sjasone * rb_node(ex_node_t) ex_link; 219234370Sjasone * }; 220234370Sjasone * typedef rb_tree(ex_node_t) ex_t; 221234370Sjasone * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp) 222234370Sjasone * 223234370Sjasone * The following API is generated: 224234370Sjasone * 225234370Sjasone * static void 226234370Sjasone * ex_new(ex_t *tree); 227234370Sjasone * Description: Initialize a red-black tree structure. 228234370Sjasone * Args: 229234370Sjasone * tree: Pointer to an uninitialized red-black tree object. 230234370Sjasone * 231234370Sjasone * static ex_node_t * 232234370Sjasone * ex_first(ex_t *tree); 233234370Sjasone * static ex_node_t * 234234370Sjasone * ex_last(ex_t *tree); 235234370Sjasone * Description: Get the first/last node in tree. 236234370Sjasone * Args: 237234370Sjasone * tree: Pointer to an initialized red-black tree object. 238234370Sjasone * Ret: First/last node in tree, or NULL if tree is empty. 239234370Sjasone * 240234370Sjasone * static ex_node_t * 241234370Sjasone * ex_next(ex_t *tree, ex_node_t *node); 242234370Sjasone * static ex_node_t * 243234370Sjasone * ex_prev(ex_t *tree, ex_node_t *node); 244234370Sjasone * Description: Get node's successor/predecessor. 245234370Sjasone * Args: 246234370Sjasone * tree: Pointer to an initialized red-black tree object. 247234370Sjasone * node: A node in tree. 248234370Sjasone * Ret: node's successor/predecessor in tree, or NULL if node is 249234370Sjasone * last/first. 250234370Sjasone * 251234370Sjasone * static ex_node_t * 252234370Sjasone * ex_search(ex_t *tree, ex_node_t *key); 253234370Sjasone * Description: Search for node that matches key. 254234370Sjasone * Args: 255234370Sjasone * tree: Pointer to an initialized red-black tree object. 256234370Sjasone * key : Search key. 257234370Sjasone * Ret: Node in tree that matches key, or NULL if no match. 258234370Sjasone * 259234370Sjasone * static ex_node_t * 260234370Sjasone * ex_nsearch(ex_t *tree, ex_node_t *key); 261234370Sjasone * static ex_node_t * 262234370Sjasone * ex_psearch(ex_t *tree, ex_node_t *key); 263234370Sjasone * Description: Search for node that matches key. If no match is found, 264234370Sjasone * return what would be key's successor/predecessor, were 265234370Sjasone * key in tree. 266234370Sjasone * Args: 267234370Sjasone * tree: Pointer to an initialized red-black tree object. 268234370Sjasone * key : Search key. 269234370Sjasone * Ret: Node in tree that matches key, or if no match, hypothetical node's 270234370Sjasone * successor/predecessor (NULL if no successor/predecessor). 271234370Sjasone * 272234370Sjasone * static void 273234370Sjasone * ex_insert(ex_t *tree, ex_node_t *node); 274234370Sjasone * Description: Insert node into tree. 275234370Sjasone * Args: 276234370Sjasone * tree: Pointer to an initialized red-black tree object. 277234370Sjasone * node: Node to be inserted into tree. 278234370Sjasone * 279234370Sjasone * static void 280234370Sjasone * ex_remove(ex_t *tree, ex_node_t *node); 281234370Sjasone * Description: Remove node from tree. 282234370Sjasone * Args: 283234370Sjasone * tree: Pointer to an initialized red-black tree object. 284234370Sjasone * node: Node in tree to be removed. 285234370Sjasone * 286234370Sjasone * static ex_node_t * 287234370Sjasone * ex_iter(ex_t *tree, ex_node_t *start, ex_node_t *(*cb)(ex_t *, 288234370Sjasone * ex_node_t *, void *), void *arg); 289234370Sjasone * static ex_node_t * 290234370Sjasone * ex_reverse_iter(ex_t *tree, ex_node_t *start, ex_node *(*cb)(ex_t *, 291234370Sjasone * ex_node_t *, void *), void *arg); 292234370Sjasone * Description: Iterate forward/backward over tree, starting at node. If 293234370Sjasone * tree is modified, iteration must be immediately 294234370Sjasone * terminated by the callback function that causes the 295234370Sjasone * modification. 296234370Sjasone * Args: 297234370Sjasone * tree : Pointer to an initialized red-black tree object. 298234370Sjasone * start: Node at which to start iteration, or NULL to start at 299234370Sjasone * first/last node. 300234370Sjasone * cb : Callback function, which is called for each node during 301234370Sjasone * iteration. Under normal circumstances the callback function 302234370Sjasone * should return NULL, which causes iteration to continue. If a 303234370Sjasone * callback function returns non-NULL, iteration is immediately 304234370Sjasone * terminated and the non-NULL return value is returned by the 305234370Sjasone * iterator. This is useful for re-starting iteration after 306234370Sjasone * modifying tree. 307234370Sjasone * arg : Opaque pointer passed to cb(). 308234370Sjasone * Ret: NULL if iteration completed, or the non-NULL callback return value 309234370Sjasone * that caused termination of the iteration. 310234370Sjasone */ 311234370Sjasone#define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \ 312234370Sjasonea_attr void \ 313234370Sjasonea_prefix##new(a_rbt_type *rbtree) { \ 314234370Sjasone rb_new(a_type, a_field, rbtree); \ 315234370Sjasone} \ 316234370Sjasonea_attr a_type * \ 317234370Sjasonea_prefix##first(a_rbt_type *rbtree) { \ 318234370Sjasone a_type *ret; \ 319234370Sjasone rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ 320234370Sjasone if (ret == &rbtree->rbt_nil) { \ 321234370Sjasone ret = NULL; \ 322234370Sjasone } \ 323234370Sjasone return (ret); \ 324234370Sjasone} \ 325234370Sjasonea_attr a_type * \ 326234370Sjasonea_prefix##last(a_rbt_type *rbtree) { \ 327234370Sjasone a_type *ret; \ 328234370Sjasone rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ 329234370Sjasone if (ret == &rbtree->rbt_nil) { \ 330234370Sjasone ret = NULL; \ 331234370Sjasone } \ 332234370Sjasone return (ret); \ 333234370Sjasone} \ 334234370Sjasonea_attr a_type * \ 335234370Sjasonea_prefix##next(a_rbt_type *rbtree, a_type *node) { \ 336234370Sjasone a_type *ret; \ 337234370Sjasone if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) { \ 338234370Sjasone rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \ 339234370Sjasone a_field, node), ret); \ 340234370Sjasone } else { \ 341234370Sjasone a_type *tnode = rbtree->rbt_root; \ 342234370Sjasone assert(tnode != &rbtree->rbt_nil); \ 343234370Sjasone ret = &rbtree->rbt_nil; \ 344234370Sjasone while (true) { \ 345234370Sjasone int cmp = (a_cmp)(node, tnode); \ 346234370Sjasone if (cmp < 0) { \ 347234370Sjasone ret = tnode; \ 348234370Sjasone tnode = rbtn_left_get(a_type, a_field, tnode); \ 349234370Sjasone } else if (cmp > 0) { \ 350234370Sjasone tnode = rbtn_right_get(a_type, a_field, tnode); \ 351234370Sjasone } else { \ 352234370Sjasone break; \ 353234370Sjasone } \ 354234370Sjasone assert(tnode != &rbtree->rbt_nil); \ 355234370Sjasone } \ 356234370Sjasone } \ 357234370Sjasone if (ret == &rbtree->rbt_nil) { \ 358234370Sjasone ret = (NULL); \ 359234370Sjasone } \ 360234370Sjasone return (ret); \ 361234370Sjasone} \ 362234370Sjasonea_attr a_type * \ 363234370Sjasonea_prefix##prev(a_rbt_type *rbtree, a_type *node) { \ 364234370Sjasone a_type *ret; \ 365234370Sjasone if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) { \ 366234370Sjasone rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \ 367234370Sjasone a_field, node), ret); \ 368234370Sjasone } else { \ 369234370Sjasone a_type *tnode = rbtree->rbt_root; \ 370234370Sjasone assert(tnode != &rbtree->rbt_nil); \ 371234370Sjasone ret = &rbtree->rbt_nil; \ 372234370Sjasone while (true) { \ 373234370Sjasone int cmp = (a_cmp)(node, tnode); \ 374234370Sjasone if (cmp < 0) { \ 375234370Sjasone tnode = rbtn_left_get(a_type, a_field, tnode); \ 376234370Sjasone } else if (cmp > 0) { \ 377234370Sjasone ret = tnode; \ 378234370Sjasone tnode = rbtn_right_get(a_type, a_field, tnode); \ 379234370Sjasone } else { \ 380234370Sjasone break; \ 381234370Sjasone } \ 382234370Sjasone assert(tnode != &rbtree->rbt_nil); \ 383234370Sjasone } \ 384234370Sjasone } \ 385234370Sjasone if (ret == &rbtree->rbt_nil) { \ 386234370Sjasone ret = (NULL); \ 387234370Sjasone } \ 388234370Sjasone return (ret); \ 389234370Sjasone} \ 390234370Sjasonea_attr a_type * \ 391234370Sjasonea_prefix##search(a_rbt_type *rbtree, a_type *key) { \ 392234370Sjasone a_type *ret; \ 393234370Sjasone int cmp; \ 394234370Sjasone ret = rbtree->rbt_root; \ 395234370Sjasone while (ret != &rbtree->rbt_nil \ 396234370Sjasone && (cmp = (a_cmp)(key, ret)) != 0) { \ 397234370Sjasone if (cmp < 0) { \ 398234370Sjasone ret = rbtn_left_get(a_type, a_field, ret); \ 399234370Sjasone } else { \ 400234370Sjasone ret = rbtn_right_get(a_type, a_field, ret); \ 401234370Sjasone } \ 402234370Sjasone } \ 403234370Sjasone if (ret == &rbtree->rbt_nil) { \ 404234370Sjasone ret = (NULL); \ 405234370Sjasone } \ 406234370Sjasone return (ret); \ 407234370Sjasone} \ 408234370Sjasonea_attr a_type * \ 409234370Sjasonea_prefix##nsearch(a_rbt_type *rbtree, a_type *key) { \ 410234370Sjasone a_type *ret; \ 411234370Sjasone a_type *tnode = rbtree->rbt_root; \ 412234370Sjasone ret = &rbtree->rbt_nil; \ 413234370Sjasone while (tnode != &rbtree->rbt_nil) { \ 414234370Sjasone int cmp = (a_cmp)(key, tnode); \ 415234370Sjasone if (cmp < 0) { \ 416234370Sjasone ret = tnode; \ 417234370Sjasone tnode = rbtn_left_get(a_type, a_field, tnode); \ 418234370Sjasone } else if (cmp > 0) { \ 419234370Sjasone tnode = rbtn_right_get(a_type, a_field, tnode); \ 420234370Sjasone } else { \ 421234370Sjasone ret = tnode; \ 422234370Sjasone break; \ 423234370Sjasone } \ 424234370Sjasone } \ 425234370Sjasone if (ret == &rbtree->rbt_nil) { \ 426234370Sjasone ret = (NULL); \ 427234370Sjasone } \ 428234370Sjasone return (ret); \ 429234370Sjasone} \ 430234370Sjasonea_attr a_type * \ 431234370Sjasonea_prefix##psearch(a_rbt_type *rbtree, a_type *key) { \ 432234370Sjasone a_type *ret; \ 433234370Sjasone a_type *tnode = rbtree->rbt_root; \ 434234370Sjasone ret = &rbtree->rbt_nil; \ 435234370Sjasone while (tnode != &rbtree->rbt_nil) { \ 436234370Sjasone int cmp = (a_cmp)(key, tnode); \ 437234370Sjasone if (cmp < 0) { \ 438234370Sjasone tnode = rbtn_left_get(a_type, a_field, tnode); \ 439234370Sjasone } else if (cmp > 0) { \ 440234370Sjasone ret = tnode; \ 441234370Sjasone tnode = rbtn_right_get(a_type, a_field, tnode); \ 442234370Sjasone } else { \ 443234370Sjasone ret = tnode; \ 444234370Sjasone break; \ 445234370Sjasone } \ 446234370Sjasone } \ 447234370Sjasone if (ret == &rbtree->rbt_nil) { \ 448234370Sjasone ret = (NULL); \ 449234370Sjasone } \ 450234370Sjasone return (ret); \ 451234370Sjasone} \ 452234370Sjasonea_attr void \ 453234370Sjasonea_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ 454234370Sjasone struct { \ 455234370Sjasone a_type *node; \ 456234370Sjasone int cmp; \ 457234370Sjasone } path[sizeof(void *) << 4], *pathp; \ 458234370Sjasone rbt_node_new(a_type, a_field, rbtree, node); \ 459234370Sjasone /* Wind. */ \ 460234370Sjasone path->node = rbtree->rbt_root; \ 461234370Sjasone for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \ 462234370Sjasone int cmp = pathp->cmp = a_cmp(node, pathp->node); \ 463234370Sjasone assert(cmp != 0); \ 464234370Sjasone if (cmp < 0) { \ 465234370Sjasone pathp[1].node = rbtn_left_get(a_type, a_field, \ 466234370Sjasone pathp->node); \ 467234370Sjasone } else { \ 468234370Sjasone pathp[1].node = rbtn_right_get(a_type, a_field, \ 469234370Sjasone pathp->node); \ 470234370Sjasone } \ 471234370Sjasone } \ 472234370Sjasone pathp->node = node; \ 473234370Sjasone /* Unwind. */ \ 474234370Sjasone for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ 475234370Sjasone a_type *cnode = pathp->node; \ 476234370Sjasone if (pathp->cmp < 0) { \ 477234370Sjasone a_type *left = pathp[1].node; \ 478234370Sjasone rbtn_left_set(a_type, a_field, cnode, left); \ 479234370Sjasone if (rbtn_red_get(a_type, a_field, left)) { \ 480234370Sjasone a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ 481234370Sjasone if (rbtn_red_get(a_type, a_field, leftleft)) { \ 482234370Sjasone /* Fix up 4-node. */ \ 483234370Sjasone a_type *tnode; \ 484234370Sjasone rbtn_black_set(a_type, a_field, leftleft); \ 485234370Sjasone rbtn_rotate_right(a_type, a_field, cnode, tnode); \ 486234370Sjasone cnode = tnode; \ 487234370Sjasone } \ 488234370Sjasone } else { \ 489234370Sjasone return; \ 490234370Sjasone } \ 491234370Sjasone } else { \ 492234370Sjasone a_type *right = pathp[1].node; \ 493234370Sjasone rbtn_right_set(a_type, a_field, cnode, right); \ 494234370Sjasone if (rbtn_red_get(a_type, a_field, right)) { \ 495234370Sjasone a_type *left = rbtn_left_get(a_type, a_field, cnode); \ 496234370Sjasone if (rbtn_red_get(a_type, a_field, left)) { \ 497234370Sjasone /* Split 4-node. */ \ 498234370Sjasone rbtn_black_set(a_type, a_field, left); \ 499234370Sjasone rbtn_black_set(a_type, a_field, right); \ 500234370Sjasone rbtn_red_set(a_type, a_field, cnode); \ 501234370Sjasone } else { \ 502234370Sjasone /* Lean left. */ \ 503234370Sjasone a_type *tnode; \ 504234370Sjasone bool tred = rbtn_red_get(a_type, a_field, cnode); \ 505234370Sjasone rbtn_rotate_left(a_type, a_field, cnode, tnode); \ 506234370Sjasone rbtn_color_set(a_type, a_field, tnode, tred); \ 507234370Sjasone rbtn_red_set(a_type, a_field, cnode); \ 508234370Sjasone cnode = tnode; \ 509234370Sjasone } \ 510234370Sjasone } else { \ 511234370Sjasone return; \ 512234370Sjasone } \ 513234370Sjasone } \ 514234370Sjasone pathp->node = cnode; \ 515234370Sjasone } \ 516234370Sjasone /* Set root, and make it black. */ \ 517234370Sjasone rbtree->rbt_root = path->node; \ 518234370Sjasone rbtn_black_set(a_type, a_field, rbtree->rbt_root); \ 519234370Sjasone} \ 520234370Sjasonea_attr void \ 521234370Sjasonea_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ 522234370Sjasone struct { \ 523234370Sjasone a_type *node; \ 524234370Sjasone int cmp; \ 525234370Sjasone } *pathp, *nodep, path[sizeof(void *) << 4]; \ 526234370Sjasone /* Wind. */ \ 527234370Sjasone nodep = NULL; /* Silence compiler warning. */ \ 528234370Sjasone path->node = rbtree->rbt_root; \ 529234370Sjasone for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \ 530234370Sjasone int cmp = pathp->cmp = a_cmp(node, pathp->node); \ 531234370Sjasone if (cmp < 0) { \ 532234370Sjasone pathp[1].node = rbtn_left_get(a_type, a_field, \ 533234370Sjasone pathp->node); \ 534234370Sjasone } else { \ 535234370Sjasone pathp[1].node = rbtn_right_get(a_type, a_field, \ 536234370Sjasone pathp->node); \ 537234370Sjasone if (cmp == 0) { \ 538234370Sjasone /* Find node's successor, in preparation for swap. */ \ 539234370Sjasone pathp->cmp = 1; \ 540234370Sjasone nodep = pathp; \ 541234370Sjasone for (pathp++; pathp->node != &rbtree->rbt_nil; \ 542234370Sjasone pathp++) { \ 543234370Sjasone pathp->cmp = -1; \ 544234370Sjasone pathp[1].node = rbtn_left_get(a_type, a_field, \ 545234370Sjasone pathp->node); \ 546234370Sjasone } \ 547234370Sjasone break; \ 548234370Sjasone } \ 549234370Sjasone } \ 550234370Sjasone } \ 551234370Sjasone assert(nodep->node == node); \ 552234370Sjasone pathp--; \ 553234370Sjasone if (pathp->node != node) { \ 554234370Sjasone /* Swap node with its successor. */ \ 555234370Sjasone bool tred = rbtn_red_get(a_type, a_field, pathp->node); \ 556234370Sjasone rbtn_color_set(a_type, a_field, pathp->node, \ 557234370Sjasone rbtn_red_get(a_type, a_field, node)); \ 558234370Sjasone rbtn_left_set(a_type, a_field, pathp->node, \ 559234370Sjasone rbtn_left_get(a_type, a_field, node)); \ 560234370Sjasone /* If node's successor is its right child, the following code */\ 561234370Sjasone /* will do the wrong thing for the right child pointer. */\ 562234370Sjasone /* However, it doesn't matter, because the pointer will be */\ 563234370Sjasone /* properly set when the successor is pruned. */\ 564234370Sjasone rbtn_right_set(a_type, a_field, pathp->node, \ 565234370Sjasone rbtn_right_get(a_type, a_field, node)); \ 566234370Sjasone rbtn_color_set(a_type, a_field, node, tred); \ 567234370Sjasone /* The pruned leaf node's child pointers are never accessed */\ 568234370Sjasone /* again, so don't bother setting them to nil. */\ 569234370Sjasone nodep->node = pathp->node; \ 570234370Sjasone pathp->node = node; \ 571234370Sjasone if (nodep == path) { \ 572234370Sjasone rbtree->rbt_root = nodep->node; \ 573234370Sjasone } else { \ 574234370Sjasone if (nodep[-1].cmp < 0) { \ 575234370Sjasone rbtn_left_set(a_type, a_field, nodep[-1].node, \ 576234370Sjasone nodep->node); \ 577234370Sjasone } else { \ 578234370Sjasone rbtn_right_set(a_type, a_field, nodep[-1].node, \ 579234370Sjasone nodep->node); \ 580234370Sjasone } \ 581234370Sjasone } \ 582234370Sjasone } else { \ 583234370Sjasone a_type *left = rbtn_left_get(a_type, a_field, node); \ 584234370Sjasone if (left != &rbtree->rbt_nil) { \ 585234370Sjasone /* node has no successor, but it has a left child. */\ 586234370Sjasone /* Splice node out, without losing the left child. */\ 587234370Sjasone assert(rbtn_red_get(a_type, a_field, node) == false); \ 588234370Sjasone assert(rbtn_red_get(a_type, a_field, left)); \ 589234370Sjasone rbtn_black_set(a_type, a_field, left); \ 590234370Sjasone if (pathp == path) { \ 591234370Sjasone rbtree->rbt_root = left; \ 592234370Sjasone } else { \ 593234370Sjasone if (pathp[-1].cmp < 0) { \ 594234370Sjasone rbtn_left_set(a_type, a_field, pathp[-1].node, \ 595234370Sjasone left); \ 596234370Sjasone } else { \ 597234370Sjasone rbtn_right_set(a_type, a_field, pathp[-1].node, \ 598234370Sjasone left); \ 599234370Sjasone } \ 600234370Sjasone } \ 601234370Sjasone return; \ 602234370Sjasone } else if (pathp == path) { \ 603234370Sjasone /* The tree only contained one node. */ \ 604234370Sjasone rbtree->rbt_root = &rbtree->rbt_nil; \ 605234370Sjasone return; \ 606234370Sjasone } \ 607234370Sjasone } \ 608234370Sjasone if (rbtn_red_get(a_type, a_field, pathp->node)) { \ 609234370Sjasone /* Prune red node, which requires no fixup. */ \ 610234370Sjasone assert(pathp[-1].cmp < 0); \ 611234370Sjasone rbtn_left_set(a_type, a_field, pathp[-1].node, \ 612234370Sjasone &rbtree->rbt_nil); \ 613234370Sjasone return; \ 614234370Sjasone } \ 615234370Sjasone /* The node to be pruned is black, so unwind until balance is */\ 616234370Sjasone /* restored. */\ 617234370Sjasone pathp->node = &rbtree->rbt_nil; \ 618234370Sjasone for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ 619234370Sjasone assert(pathp->cmp != 0); \ 620234370Sjasone if (pathp->cmp < 0) { \ 621234370Sjasone rbtn_left_set(a_type, a_field, pathp->node, \ 622234370Sjasone pathp[1].node); \ 623234370Sjasone assert(rbtn_red_get(a_type, a_field, pathp[1].node) \ 624234370Sjasone == false); \ 625234370Sjasone if (rbtn_red_get(a_type, a_field, pathp->node)) { \ 626234370Sjasone a_type *right = rbtn_right_get(a_type, a_field, \ 627234370Sjasone pathp->node); \ 628234370Sjasone a_type *rightleft = rbtn_left_get(a_type, a_field, \ 629234370Sjasone right); \ 630234370Sjasone a_type *tnode; \ 631234370Sjasone if (rbtn_red_get(a_type, a_field, rightleft)) { \ 632234370Sjasone /* In the following diagrams, ||, //, and \\ */\ 633234370Sjasone /* indicate the path to the removed node. */\ 634234370Sjasone /* */\ 635234370Sjasone /* || */\ 636234370Sjasone /* pathp(r) */\ 637234370Sjasone /* // \ */\ 638234370Sjasone /* (b) (b) */\ 639234370Sjasone /* / */\ 640234370Sjasone /* (r) */\ 641234370Sjasone /* */\ 642234370Sjasone rbtn_black_set(a_type, a_field, pathp->node); \ 643234370Sjasone rbtn_rotate_right(a_type, a_field, right, tnode); \ 644234370Sjasone rbtn_right_set(a_type, a_field, pathp->node, tnode);\ 645234370Sjasone rbtn_rotate_left(a_type, a_field, pathp->node, \ 646234370Sjasone tnode); \ 647234370Sjasone } else { \ 648234370Sjasone /* || */\ 649234370Sjasone /* pathp(r) */\ 650234370Sjasone /* // \ */\ 651234370Sjasone /* (b) (b) */\ 652234370Sjasone /* / */\ 653234370Sjasone /* (b) */\ 654234370Sjasone /* */\ 655234370Sjasone rbtn_rotate_left(a_type, a_field, pathp->node, \ 656234370Sjasone tnode); \ 657234370Sjasone } \ 658234370Sjasone /* Balance restored, but rotation modified subtree */\ 659234370Sjasone /* root. */\ 660234370Sjasone assert((uintptr_t)pathp > (uintptr_t)path); \ 661234370Sjasone if (pathp[-1].cmp < 0) { \ 662234370Sjasone rbtn_left_set(a_type, a_field, pathp[-1].node, \ 663234370Sjasone tnode); \ 664234370Sjasone } else { \ 665234370Sjasone rbtn_right_set(a_type, a_field, pathp[-1].node, \ 666234370Sjasone tnode); \ 667234370Sjasone } \ 668234370Sjasone return; \ 669234370Sjasone } else { \ 670234370Sjasone a_type *right = rbtn_right_get(a_type, a_field, \ 671234370Sjasone pathp->node); \ 672234370Sjasone a_type *rightleft = rbtn_left_get(a_type, a_field, \ 673234370Sjasone right); \ 674234370Sjasone if (rbtn_red_get(a_type, a_field, rightleft)) { \ 675234370Sjasone /* || */\ 676234370Sjasone /* pathp(b) */\ 677234370Sjasone /* // \ */\ 678234370Sjasone /* (b) (b) */\ 679234370Sjasone /* / */\ 680234370Sjasone /* (r) */\ 681234370Sjasone a_type *tnode; \ 682234370Sjasone rbtn_black_set(a_type, a_field, rightleft); \ 683234370Sjasone rbtn_rotate_right(a_type, a_field, right, tnode); \ 684234370Sjasone rbtn_right_set(a_type, a_field, pathp->node, tnode);\ 685234370Sjasone rbtn_rotate_left(a_type, a_field, pathp->node, \ 686234370Sjasone tnode); \ 687234370Sjasone /* Balance restored, but rotation modified */\ 688234370Sjasone /* subree root, which may actually be the tree */\ 689234370Sjasone /* root. */\ 690234370Sjasone if (pathp == path) { \ 691234370Sjasone /* Set root. */ \ 692234370Sjasone rbtree->rbt_root = tnode; \ 693234370Sjasone } else { \ 694234370Sjasone if (pathp[-1].cmp < 0) { \ 695234370Sjasone rbtn_left_set(a_type, a_field, \ 696234370Sjasone pathp[-1].node, tnode); \ 697234370Sjasone } else { \ 698234370Sjasone rbtn_right_set(a_type, a_field, \ 699234370Sjasone pathp[-1].node, tnode); \ 700234370Sjasone } \ 701234370Sjasone } \ 702234370Sjasone return; \ 703234370Sjasone } else { \ 704234370Sjasone /* || */\ 705234370Sjasone /* pathp(b) */\ 706234370Sjasone /* // \ */\ 707234370Sjasone /* (b) (b) */\ 708234370Sjasone /* / */\ 709234370Sjasone /* (b) */\ 710234370Sjasone a_type *tnode; \ 711234370Sjasone rbtn_red_set(a_type, a_field, pathp->node); \ 712234370Sjasone rbtn_rotate_left(a_type, a_field, pathp->node, \ 713234370Sjasone tnode); \ 714234370Sjasone pathp->node = tnode; \ 715234370Sjasone } \ 716234370Sjasone } \ 717234370Sjasone } else { \ 718234370Sjasone a_type *left; \ 719234370Sjasone rbtn_right_set(a_type, a_field, pathp->node, \ 720234370Sjasone pathp[1].node); \ 721234370Sjasone left = rbtn_left_get(a_type, a_field, pathp->node); \ 722234370Sjasone if (rbtn_red_get(a_type, a_field, left)) { \ 723234370Sjasone a_type *tnode; \ 724234370Sjasone a_type *leftright = rbtn_right_get(a_type, a_field, \ 725234370Sjasone left); \ 726234370Sjasone a_type *leftrightleft = rbtn_left_get(a_type, a_field, \ 727234370Sjasone leftright); \ 728234370Sjasone if (rbtn_red_get(a_type, a_field, leftrightleft)) { \ 729234370Sjasone /* || */\ 730234370Sjasone /* pathp(b) */\ 731234370Sjasone /* / \\ */\ 732234370Sjasone /* (r) (b) */\ 733234370Sjasone /* \ */\ 734234370Sjasone /* (b) */\ 735234370Sjasone /* / */\ 736234370Sjasone /* (r) */\ 737234370Sjasone a_type *unode; \ 738234370Sjasone rbtn_black_set(a_type, a_field, leftrightleft); \ 739234370Sjasone rbtn_rotate_right(a_type, a_field, pathp->node, \ 740234370Sjasone unode); \ 741234370Sjasone rbtn_rotate_right(a_type, a_field, pathp->node, \ 742234370Sjasone tnode); \ 743234370Sjasone rbtn_right_set(a_type, a_field, unode, tnode); \ 744234370Sjasone rbtn_rotate_left(a_type, a_field, unode, tnode); \ 745234370Sjasone } else { \ 746234370Sjasone /* || */\ 747234370Sjasone /* pathp(b) */\ 748234370Sjasone /* / \\ */\ 749234370Sjasone /* (r) (b) */\ 750234370Sjasone /* \ */\ 751234370Sjasone /* (b) */\ 752234370Sjasone /* / */\ 753234370Sjasone /* (b) */\ 754234370Sjasone assert(leftright != &rbtree->rbt_nil); \ 755234370Sjasone rbtn_red_set(a_type, a_field, leftright); \ 756234370Sjasone rbtn_rotate_right(a_type, a_field, pathp->node, \ 757234370Sjasone tnode); \ 758234370Sjasone rbtn_black_set(a_type, a_field, tnode); \ 759234370Sjasone } \ 760234370Sjasone /* Balance restored, but rotation modified subtree */\ 761234370Sjasone /* root, which may actually be the tree root. */\ 762234370Sjasone if (pathp == path) { \ 763234370Sjasone /* Set root. */ \ 764234370Sjasone rbtree->rbt_root = tnode; \ 765234370Sjasone } else { \ 766234370Sjasone if (pathp[-1].cmp < 0) { \ 767234370Sjasone rbtn_left_set(a_type, a_field, pathp[-1].node, \ 768234370Sjasone tnode); \ 769234370Sjasone } else { \ 770234370Sjasone rbtn_right_set(a_type, a_field, pathp[-1].node, \ 771234370Sjasone tnode); \ 772234370Sjasone } \ 773234370Sjasone } \ 774234370Sjasone return; \ 775234370Sjasone } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \ 776234370Sjasone a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ 777234370Sjasone if (rbtn_red_get(a_type, a_field, leftleft)) { \ 778234370Sjasone /* || */\ 779234370Sjasone /* pathp(r) */\ 780234370Sjasone /* / \\ */\ 781234370Sjasone /* (b) (b) */\ 782234370Sjasone /* / */\ 783234370Sjasone /* (r) */\ 784234370Sjasone a_type *tnode; \ 785234370Sjasone rbtn_black_set(a_type, a_field, pathp->node); \ 786234370Sjasone rbtn_red_set(a_type, a_field, left); \ 787234370Sjasone rbtn_black_set(a_type, a_field, leftleft); \ 788234370Sjasone rbtn_rotate_right(a_type, a_field, pathp->node, \ 789234370Sjasone tnode); \ 790234370Sjasone /* Balance restored, but rotation modified */\ 791234370Sjasone /* subtree root. */\ 792234370Sjasone assert((uintptr_t)pathp > (uintptr_t)path); \ 793234370Sjasone if (pathp[-1].cmp < 0) { \ 794234370Sjasone rbtn_left_set(a_type, a_field, pathp[-1].node, \ 795234370Sjasone tnode); \ 796234370Sjasone } else { \ 797234370Sjasone rbtn_right_set(a_type, a_field, pathp[-1].node, \ 798234370Sjasone tnode); \ 799234370Sjasone } \ 800234370Sjasone return; \ 801234370Sjasone } else { \ 802234370Sjasone /* || */\ 803234370Sjasone /* pathp(r) */\ 804234370Sjasone /* / \\ */\ 805234370Sjasone /* (b) (b) */\ 806234370Sjasone /* / */\ 807234370Sjasone /* (b) */\ 808234370Sjasone rbtn_red_set(a_type, a_field, left); \ 809234370Sjasone rbtn_black_set(a_type, a_field, pathp->node); \ 810234370Sjasone /* Balance restored. */ \ 811234370Sjasone return; \ 812234370Sjasone } \ 813234370Sjasone } else { \ 814234370Sjasone a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ 815234370Sjasone if (rbtn_red_get(a_type, a_field, leftleft)) { \ 816234370Sjasone /* || */\ 817234370Sjasone /* pathp(b) */\ 818234370Sjasone /* / \\ */\ 819234370Sjasone /* (b) (b) */\ 820234370Sjasone /* / */\ 821234370Sjasone /* (r) */\ 822234370Sjasone a_type *tnode; \ 823234370Sjasone rbtn_black_set(a_type, a_field, leftleft); \ 824234370Sjasone rbtn_rotate_right(a_type, a_field, pathp->node, \ 825234370Sjasone tnode); \ 826234370Sjasone /* Balance restored, but rotation modified */\ 827234370Sjasone /* subtree root, which may actually be the tree */\ 828234370Sjasone /* root. */\ 829234370Sjasone if (pathp == path) { \ 830234370Sjasone /* Set root. */ \ 831234370Sjasone rbtree->rbt_root = tnode; \ 832234370Sjasone } else { \ 833234370Sjasone if (pathp[-1].cmp < 0) { \ 834234370Sjasone rbtn_left_set(a_type, a_field, \ 835234370Sjasone pathp[-1].node, tnode); \ 836234370Sjasone } else { \ 837234370Sjasone rbtn_right_set(a_type, a_field, \ 838234370Sjasone pathp[-1].node, tnode); \ 839234370Sjasone } \ 840234370Sjasone } \ 841234370Sjasone return; \ 842234370Sjasone } else { \ 843234370Sjasone /* || */\ 844234370Sjasone /* pathp(b) */\ 845234370Sjasone /* / \\ */\ 846234370Sjasone /* (b) (b) */\ 847234370Sjasone /* / */\ 848234370Sjasone /* (b) */\ 849234370Sjasone rbtn_red_set(a_type, a_field, left); \ 850234370Sjasone } \ 851234370Sjasone } \ 852234370Sjasone } \ 853234370Sjasone } \ 854234370Sjasone /* Set root. */ \ 855234370Sjasone rbtree->rbt_root = path->node; \ 856234370Sjasone assert(rbtn_red_get(a_type, a_field, rbtree->rbt_root) == false); \ 857234370Sjasone} \ 858234370Sjasonea_attr a_type * \ 859234370Sjasonea_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \ 860234370Sjasone a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ 861234370Sjasone if (node == &rbtree->rbt_nil) { \ 862234370Sjasone return (&rbtree->rbt_nil); \ 863234370Sjasone } else { \ 864234370Sjasone a_type *ret; \ 865234370Sjasone if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \ 866234370Sjasone a_field, node), cb, arg)) != &rbtree->rbt_nil \ 867234370Sjasone || (ret = cb(rbtree, node, arg)) != NULL) { \ 868234370Sjasone return (ret); \ 869234370Sjasone } \ 870234370Sjasone return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ 871234370Sjasone a_field, node), cb, arg)); \ 872234370Sjasone } \ 873234370Sjasone} \ 874234370Sjasonea_attr a_type * \ 875234370Sjasonea_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \ 876234370Sjasone a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ 877234370Sjasone int cmp = a_cmp(start, node); \ 878234370Sjasone if (cmp < 0) { \ 879234370Sjasone a_type *ret; \ 880234370Sjasone if ((ret = a_prefix##iter_start(rbtree, start, \ 881234370Sjasone rbtn_left_get(a_type, a_field, node), cb, arg)) != \ 882234370Sjasone &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ 883234370Sjasone return (ret); \ 884234370Sjasone } \ 885234370Sjasone return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ 886234370Sjasone a_field, node), cb, arg)); \ 887234370Sjasone } else if (cmp > 0) { \ 888234370Sjasone return (a_prefix##iter_start(rbtree, start, \ 889234370Sjasone rbtn_right_get(a_type, a_field, node), cb, arg)); \ 890234370Sjasone } else { \ 891234370Sjasone a_type *ret; \ 892234370Sjasone if ((ret = cb(rbtree, node, arg)) != NULL) { \ 893234370Sjasone return (ret); \ 894234370Sjasone } \ 895234370Sjasone return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ 896234370Sjasone a_field, node), cb, arg)); \ 897234370Sjasone } \ 898234370Sjasone} \ 899234370Sjasonea_attr a_type * \ 900234370Sjasonea_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ 901234370Sjasone a_rbt_type *, a_type *, void *), void *arg) { \ 902234370Sjasone a_type *ret; \ 903234370Sjasone if (start != NULL) { \ 904234370Sjasone ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \ 905234370Sjasone cb, arg); \ 906234370Sjasone } else { \ 907234370Sjasone ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\ 908234370Sjasone } \ 909234370Sjasone if (ret == &rbtree->rbt_nil) { \ 910234370Sjasone ret = NULL; \ 911234370Sjasone } \ 912234370Sjasone return (ret); \ 913234370Sjasone} \ 914234370Sjasonea_attr a_type * \ 915234370Sjasonea_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \ 916234370Sjasone a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ 917234370Sjasone if (node == &rbtree->rbt_nil) { \ 918234370Sjasone return (&rbtree->rbt_nil); \ 919234370Sjasone } else { \ 920234370Sjasone a_type *ret; \ 921234370Sjasone if ((ret = a_prefix##reverse_iter_recurse(rbtree, \ 922234370Sjasone rbtn_right_get(a_type, a_field, node), cb, arg)) != \ 923234370Sjasone &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ 924234370Sjasone return (ret); \ 925234370Sjasone } \ 926234370Sjasone return (a_prefix##reverse_iter_recurse(rbtree, \ 927234370Sjasone rbtn_left_get(a_type, a_field, node), cb, arg)); \ 928234370Sjasone } \ 929234370Sjasone} \ 930234370Sjasonea_attr a_type * \ 931234370Sjasonea_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \ 932234370Sjasone a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \ 933234370Sjasone void *arg) { \ 934234370Sjasone int cmp = a_cmp(start, node); \ 935234370Sjasone if (cmp > 0) { \ 936234370Sjasone a_type *ret; \ 937234370Sjasone if ((ret = a_prefix##reverse_iter_start(rbtree, start, \ 938234370Sjasone rbtn_right_get(a_type, a_field, node), cb, arg)) != \ 939234370Sjasone &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ 940234370Sjasone return (ret); \ 941234370Sjasone } \ 942234370Sjasone return (a_prefix##reverse_iter_recurse(rbtree, \ 943234370Sjasone rbtn_left_get(a_type, a_field, node), cb, arg)); \ 944234370Sjasone } else if (cmp < 0) { \ 945234370Sjasone return (a_prefix##reverse_iter_start(rbtree, start, \ 946234370Sjasone rbtn_left_get(a_type, a_field, node), cb, arg)); \ 947234370Sjasone } else { \ 948234370Sjasone a_type *ret; \ 949234370Sjasone if ((ret = cb(rbtree, node, arg)) != NULL) { \ 950234370Sjasone return (ret); \ 951234370Sjasone } \ 952234370Sjasone return (a_prefix##reverse_iter_recurse(rbtree, \ 953234370Sjasone rbtn_left_get(a_type, a_field, node), cb, arg)); \ 954234370Sjasone } \ 955234370Sjasone} \ 956234370Sjasonea_attr a_type * \ 957234370Sjasonea_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ 958234370Sjasone a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ 959234370Sjasone a_type *ret; \ 960234370Sjasone if (start != NULL) { \ 961234370Sjasone ret = a_prefix##reverse_iter_start(rbtree, start, \ 962234370Sjasone rbtree->rbt_root, cb, arg); \ 963234370Sjasone } else { \ 964234370Sjasone ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \ 965234370Sjasone cb, arg); \ 966234370Sjasone } \ 967234370Sjasone if (ret == &rbtree->rbt_nil) { \ 968234370Sjasone ret = NULL; \ 969234370Sjasone } \ 970234370Sjasone return (ret); \ 971234370Sjasone} 972234370Sjasone 973234370Sjasone#endif /* RB_H_ */ 974