michael@0: /****************************************************************************** michael@0: * michael@0: * Copyright (C) 2008 Jason Evans . michael@0: * All rights reserved. michael@0: * michael@0: * Redistribution and use in source and binary forms, with or without michael@0: * modification, are permitted provided that the following conditions michael@0: * are met: michael@0: * 1. Redistributions of source code must retain the above copyright michael@0: * notice(s), this list of conditions and the following disclaimer michael@0: * unmodified other than the allowable addition of one or more michael@0: * copyright notices. michael@0: * 2. Redistributions in binary form must reproduce the above copyright michael@0: * notice(s), this list of conditions and the following disclaimer in michael@0: * the documentation and/or other materials provided with the michael@0: * distribution. michael@0: * michael@0: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY michael@0: * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE michael@0: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR michael@0: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE michael@0: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR michael@0: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF michael@0: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR michael@0: * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, michael@0: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE michael@0: * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, michael@0: * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. michael@0: * michael@0: ****************************************************************************** michael@0: * michael@0: * cpp macro implementation of left-leaning red-black trees. michael@0: * michael@0: * Usage: michael@0: * michael@0: * (Optional.) michael@0: * #define SIZEOF_PTR ... michael@0: * #define SIZEOF_PTR_2POW ... michael@0: * #define RB_NO_C99_VARARRAYS michael@0: * michael@0: * (Optional, see assert(3).) michael@0: * #define NDEBUG michael@0: * michael@0: * (Required.) michael@0: * #include michael@0: * #include michael@0: * ... michael@0: * michael@0: * All operations are done non-recursively. Parent pointers are not used, and michael@0: * color bits are stored in the least significant bit of right-child pointers, michael@0: * thus making node linkage as compact as is possible for red-black trees. michael@0: * michael@0: * Some macros use a comparison function pointer, which is expected to have the michael@0: * following prototype: michael@0: * michael@0: * int (a_cmp *)(a_type *a_node, a_type *a_other); michael@0: * ^^^^^^ michael@0: * or a_key michael@0: * michael@0: * Interpretation of comparision function return values: michael@0: * michael@0: * -1 : a_node < a_other michael@0: * 0 : a_node == a_other michael@0: * 1 : a_node > a_other michael@0: * michael@0: * In all cases, the a_node or a_key macro argument is the first argument to the michael@0: * comparison function, which makes it possible to write comparison functions michael@0: * that treat the first argument specially. michael@0: * michael@0: ******************************************************************************/ michael@0: michael@0: #ifndef RB_H_ michael@0: #define RB_H_ michael@0: michael@0: #if 0 michael@0: #include michael@0: __FBSDID("$FreeBSD: head/lib/libc/stdlib/rb.h 178995 2008-05-14 18:33:13Z jasone $"); michael@0: #endif michael@0: michael@0: /* Node structure. */ michael@0: #define rb_node(a_type) \ michael@0: struct { \ michael@0: a_type *rbn_left; \ michael@0: a_type *rbn_right_red; \ michael@0: } michael@0: michael@0: /* Root structure. */ michael@0: #define rb_tree(a_type) \ michael@0: struct { \ michael@0: a_type *rbt_root; \ michael@0: a_type rbt_nil; \ michael@0: } michael@0: michael@0: /* Left accessors. */ michael@0: #define rbp_left_get(a_type, a_field, a_node) \ michael@0: ((a_node)->a_field.rbn_left) michael@0: #define rbp_left_set(a_type, a_field, a_node, a_left) do { \ michael@0: (a_node)->a_field.rbn_left = a_left; \ michael@0: } while (0) michael@0: michael@0: /* Right accessors. */ michael@0: #define rbp_right_get(a_type, a_field, a_node) \ michael@0: ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \ michael@0: & ((ssize_t)-2))) michael@0: #define rbp_right_set(a_type, a_field, a_node, a_right) do { \ michael@0: (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \ michael@0: | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \ michael@0: } while (0) michael@0: michael@0: /* Color accessors. */ michael@0: #define rbp_red_get(a_type, a_field, a_node) \ michael@0: ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \ michael@0: & ((size_t)1))) michael@0: #define rbp_color_set(a_type, a_field, a_node, a_red) do { \ michael@0: (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \ michael@0: (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \ michael@0: | ((ssize_t)a_red)); \ michael@0: } while (0) michael@0: #define rbp_red_set(a_type, a_field, a_node) do { \ michael@0: (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \ michael@0: (a_node)->a_field.rbn_right_red) | ((size_t)1)); \ michael@0: } while (0) michael@0: #define rbp_black_set(a_type, a_field, a_node) do { \ michael@0: (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \ michael@0: (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \ michael@0: } while (0) michael@0: michael@0: /* Node initializer. */ michael@0: #define rbp_node_new(a_type, a_field, a_tree, a_node) do { \ michael@0: rbp_left_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil); \ michael@0: rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil); \ michael@0: rbp_red_set(a_type, a_field, (a_node)); \ michael@0: } while (0) michael@0: michael@0: /* Tree initializer. */ michael@0: #define rb_new(a_type, a_field, a_tree) do { \ michael@0: (a_tree)->rbt_root = &(a_tree)->rbt_nil; \ michael@0: rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil); \ michael@0: rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil); \ michael@0: } while (0) michael@0: michael@0: /* Tree operations. */ michael@0: #define rbp_black_height(a_type, a_field, a_tree, r_height) do { \ michael@0: a_type *rbp_bh_t; \ michael@0: for (rbp_bh_t = (a_tree)->rbt_root, (r_height) = 0; \ michael@0: rbp_bh_t != &(a_tree)->rbt_nil; \ michael@0: rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) { \ michael@0: if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) { \ michael@0: (r_height)++; \ michael@0: } \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rbp_first(a_type, a_field, a_tree, a_root, r_node) do { \ michael@0: for ((r_node) = (a_root); \ michael@0: rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil; \ michael@0: (r_node) = rbp_left_get(a_type, a_field, (r_node))) { \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rbp_last(a_type, a_field, a_tree, a_root, r_node) do { \ michael@0: for ((r_node) = (a_root); \ michael@0: rbp_right_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil; \ michael@0: (r_node) = rbp_right_get(a_type, a_field, (r_node))) { \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rbp_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do { \ michael@0: if (rbp_right_get(a_type, a_field, (a_node)) \ michael@0: != &(a_tree)->rbt_nil) { \ michael@0: rbp_first(a_type, a_field, a_tree, rbp_right_get(a_type, \ michael@0: a_field, (a_node)), (r_node)); \ michael@0: } else { \ michael@0: a_type *rbp_n_t = (a_tree)->rbt_root; \ michael@0: assert(rbp_n_t != &(a_tree)->rbt_nil); \ michael@0: (r_node) = &(a_tree)->rbt_nil; \ michael@0: while (true) { \ michael@0: int rbp_n_cmp = (a_cmp)((a_node), rbp_n_t); \ michael@0: if (rbp_n_cmp < 0) { \ michael@0: (r_node) = rbp_n_t; \ michael@0: rbp_n_t = rbp_left_get(a_type, a_field, rbp_n_t); \ michael@0: } else if (rbp_n_cmp > 0) { \ michael@0: rbp_n_t = rbp_right_get(a_type, a_field, rbp_n_t); \ michael@0: } else { \ michael@0: break; \ michael@0: } \ michael@0: assert(rbp_n_t != &(a_tree)->rbt_nil); \ michael@0: } \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rbp_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do { \ michael@0: if (rbp_left_get(a_type, a_field, (a_node)) != &(a_tree)->rbt_nil) {\ michael@0: rbp_last(a_type, a_field, a_tree, rbp_left_get(a_type, \ michael@0: a_field, (a_node)), (r_node)); \ michael@0: } else { \ michael@0: a_type *rbp_p_t = (a_tree)->rbt_root; \ michael@0: assert(rbp_p_t != &(a_tree)->rbt_nil); \ michael@0: (r_node) = &(a_tree)->rbt_nil; \ michael@0: while (true) { \ michael@0: int rbp_p_cmp = (a_cmp)((a_node), rbp_p_t); \ michael@0: if (rbp_p_cmp < 0) { \ michael@0: rbp_p_t = rbp_left_get(a_type, a_field, rbp_p_t); \ michael@0: } else if (rbp_p_cmp > 0) { \ michael@0: (r_node) = rbp_p_t; \ michael@0: rbp_p_t = rbp_right_get(a_type, a_field, rbp_p_t); \ michael@0: } else { \ michael@0: break; \ michael@0: } \ michael@0: assert(rbp_p_t != &(a_tree)->rbt_nil); \ michael@0: } \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rb_first(a_type, a_field, a_tree, r_node) do { \ michael@0: rbp_first(a_type, a_field, a_tree, (a_tree)->rbt_root, (r_node)); \ michael@0: if ((r_node) == &(a_tree)->rbt_nil) { \ michael@0: (r_node) = NULL; \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rb_last(a_type, a_field, a_tree, r_node) do { \ michael@0: rbp_last(a_type, a_field, a_tree, (a_tree)->rbt_root, r_node); \ michael@0: if ((r_node) == &(a_tree)->rbt_nil) { \ michael@0: (r_node) = NULL; \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rb_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do { \ michael@0: rbp_next(a_type, a_field, a_cmp, a_tree, (a_node), (r_node)); \ michael@0: if ((r_node) == &(a_tree)->rbt_nil) { \ michael@0: (r_node) = NULL; \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rb_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do { \ michael@0: rbp_prev(a_type, a_field, a_cmp, a_tree, (a_node), (r_node)); \ michael@0: if ((r_node) == &(a_tree)->rbt_nil) { \ michael@0: (r_node) = NULL; \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rb_search(a_type, a_field, a_cmp, a_tree, a_key, r_node) do { \ michael@0: int rbp_se_cmp; \ michael@0: (r_node) = (a_tree)->rbt_root; \ michael@0: while ((r_node) != &(a_tree)->rbt_nil \ michael@0: && (rbp_se_cmp = (a_cmp)((a_key), (r_node))) != 0) { \ michael@0: if (rbp_se_cmp < 0) { \ michael@0: (r_node) = rbp_left_get(a_type, a_field, (r_node)); \ michael@0: } else { \ michael@0: (r_node) = rbp_right_get(a_type, a_field, (r_node)); \ michael@0: } \ michael@0: } \ michael@0: if ((r_node) == &(a_tree)->rbt_nil) { \ michael@0: (r_node) = NULL; \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: /* michael@0: * Find a match if it exists. Otherwise, find the next greater node, if one michael@0: * exists. michael@0: */ michael@0: #define rb_nsearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do { \ michael@0: a_type *rbp_ns_t = (a_tree)->rbt_root; \ michael@0: (r_node) = NULL; \ michael@0: while (rbp_ns_t != &(a_tree)->rbt_nil) { \ michael@0: int rbp_ns_cmp = (a_cmp)((a_key), rbp_ns_t); \ michael@0: if (rbp_ns_cmp < 0) { \ michael@0: (r_node) = rbp_ns_t; \ michael@0: rbp_ns_t = rbp_left_get(a_type, a_field, rbp_ns_t); \ michael@0: } else if (rbp_ns_cmp > 0) { \ michael@0: rbp_ns_t = rbp_right_get(a_type, a_field, rbp_ns_t); \ michael@0: } else { \ michael@0: (r_node) = rbp_ns_t; \ michael@0: break; \ michael@0: } \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: /* michael@0: * Find a match if it exists. Otherwise, find the previous lesser node, if one michael@0: * exists. michael@0: */ michael@0: #define rb_psearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do { \ michael@0: a_type *rbp_ps_t = (a_tree)->rbt_root; \ michael@0: (r_node) = NULL; \ michael@0: while (rbp_ps_t != &(a_tree)->rbt_nil) { \ michael@0: int rbp_ps_cmp = (a_cmp)((a_key), rbp_ps_t); \ michael@0: if (rbp_ps_cmp < 0) { \ michael@0: rbp_ps_t = rbp_left_get(a_type, a_field, rbp_ps_t); \ michael@0: } else if (rbp_ps_cmp > 0) { \ michael@0: (r_node) = rbp_ps_t; \ michael@0: rbp_ps_t = rbp_right_get(a_type, a_field, rbp_ps_t); \ michael@0: } else { \ michael@0: (r_node) = rbp_ps_t; \ michael@0: break; \ michael@0: } \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rbp_rotate_left(a_type, a_field, a_node, r_node) do { \ michael@0: (r_node) = rbp_right_get(a_type, a_field, (a_node)); \ michael@0: rbp_right_set(a_type, a_field, (a_node), \ michael@0: rbp_left_get(a_type, a_field, (r_node))); \ michael@0: rbp_left_set(a_type, a_field, (r_node), (a_node)); \ michael@0: } while (0) michael@0: michael@0: #define rbp_rotate_right(a_type, a_field, a_node, r_node) do { \ michael@0: (r_node) = rbp_left_get(a_type, a_field, (a_node)); \ michael@0: rbp_left_set(a_type, a_field, (a_node), \ michael@0: rbp_right_get(a_type, a_field, (r_node))); \ michael@0: rbp_right_set(a_type, a_field, (r_node), (a_node)); \ michael@0: } while (0) michael@0: michael@0: #define rbp_lean_left(a_type, a_field, a_node, r_node) do { \ michael@0: bool rbp_ll_red; \ michael@0: rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \ michael@0: rbp_ll_red = rbp_red_get(a_type, a_field, (a_node)); \ michael@0: rbp_color_set(a_type, a_field, (r_node), rbp_ll_red); \ michael@0: rbp_red_set(a_type, a_field, (a_node)); \ michael@0: } while (0) michael@0: michael@0: #define rbp_lean_right(a_type, a_field, a_node, r_node) do { \ michael@0: bool rbp_lr_red; \ michael@0: rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \ michael@0: rbp_lr_red = rbp_red_get(a_type, a_field, (a_node)); \ michael@0: rbp_color_set(a_type, a_field, (r_node), rbp_lr_red); \ michael@0: rbp_red_set(a_type, a_field, (a_node)); \ michael@0: } while (0) michael@0: michael@0: #define rbp_move_red_left(a_type, a_field, a_node, r_node) do { \ michael@0: a_type *rbp_mrl_t, *rbp_mrl_u; \ michael@0: rbp_mrl_t = rbp_left_get(a_type, a_field, (a_node)); \ michael@0: rbp_red_set(a_type, a_field, rbp_mrl_t); \ michael@0: rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node)); \ michael@0: rbp_mrl_u = rbp_left_get(a_type, a_field, rbp_mrl_t); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_mrl_u)) { \ michael@0: rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u); \ michael@0: rbp_right_set(a_type, a_field, (a_node), rbp_mrl_u); \ michael@0: rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \ michael@0: rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node)); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_mrl_t)) { \ michael@0: rbp_black_set(a_type, a_field, rbp_mrl_t); \ michael@0: rbp_red_set(a_type, a_field, (a_node)); \ michael@0: rbp_rotate_left(a_type, a_field, (a_node), rbp_mrl_t); \ michael@0: rbp_left_set(a_type, a_field, (r_node), rbp_mrl_t); \ michael@0: } else { \ michael@0: rbp_black_set(a_type, a_field, (a_node)); \ michael@0: } \ michael@0: } else { \ michael@0: rbp_red_set(a_type, a_field, (a_node)); \ michael@0: rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rbp_move_red_right(a_type, a_field, a_node, r_node) do { \ michael@0: a_type *rbp_mrr_t; \ michael@0: rbp_mrr_t = rbp_left_get(a_type, a_field, (a_node)); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_mrr_t)) { \ michael@0: a_type *rbp_mrr_u, *rbp_mrr_v; \ michael@0: rbp_mrr_u = rbp_right_get(a_type, a_field, rbp_mrr_t); \ michael@0: rbp_mrr_v = rbp_left_get(a_type, a_field, rbp_mrr_u); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_mrr_v)) { \ michael@0: rbp_color_set(a_type, a_field, rbp_mrr_u, \ michael@0: rbp_red_get(a_type, a_field, (a_node))); \ michael@0: rbp_black_set(a_type, a_field, rbp_mrr_v); \ michael@0: rbp_rotate_left(a_type, a_field, rbp_mrr_t, rbp_mrr_u); \ michael@0: rbp_left_set(a_type, a_field, (a_node), rbp_mrr_u); \ michael@0: rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \ michael@0: rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \ michael@0: rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \ michael@0: } else { \ michael@0: rbp_color_set(a_type, a_field, rbp_mrr_t, \ michael@0: rbp_red_get(a_type, a_field, (a_node))); \ michael@0: rbp_red_set(a_type, a_field, rbp_mrr_u); \ michael@0: rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \ michael@0: rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \ michael@0: rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \ michael@0: } \ michael@0: rbp_red_set(a_type, a_field, (a_node)); \ michael@0: } else { \ michael@0: rbp_red_set(a_type, a_field, rbp_mrr_t); \ michael@0: rbp_mrr_t = rbp_left_get(a_type, a_field, rbp_mrr_t); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_mrr_t)) { \ michael@0: rbp_black_set(a_type, a_field, rbp_mrr_t); \ michael@0: rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \ michael@0: rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \ michael@0: rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \ michael@0: } else { \ michael@0: rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \ michael@0: } \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define rb_insert(a_type, a_field, a_cmp, a_tree, a_node) do { \ michael@0: a_type rbp_i_s; \ michael@0: a_type *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u; \ michael@0: int rbp_i_cmp = 0; \ michael@0: rbp_i_g = &(a_tree)->rbt_nil; \ michael@0: rbp_left_set(a_type, a_field, &rbp_i_s, (a_tree)->rbt_root); \ michael@0: rbp_right_set(a_type, a_field, &rbp_i_s, &(a_tree)->rbt_nil); \ michael@0: rbp_black_set(a_type, a_field, &rbp_i_s); \ michael@0: rbp_i_p = &rbp_i_s; \ michael@0: rbp_i_c = (a_tree)->rbt_root; \ michael@0: /* Iteratively search down the tree for the insertion point, */\ michael@0: /* splitting 4-nodes as they are encountered. At the end of each */\ michael@0: /* iteration, rbp_i_g->rbp_i_p->rbp_i_c is a 3-level path down */\ michael@0: /* the tree, assuming a sufficiently deep tree. */\ michael@0: while (rbp_i_c != &(a_tree)->rbt_nil) { \ michael@0: rbp_i_t = rbp_left_get(a_type, a_field, rbp_i_c); \ michael@0: rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_i_t) \ michael@0: && rbp_red_get(a_type, a_field, rbp_i_u)) { \ michael@0: /* rbp_i_c is the top of a logical 4-node, so split it. */\ michael@0: /* This iteration does not move down the tree, due to the */\ michael@0: /* disruptiveness of node splitting. */\ michael@0: /* */\ michael@0: /* Rotate right. */\ michael@0: rbp_rotate_right(a_type, a_field, rbp_i_c, rbp_i_t); \ michael@0: /* Pass red links up one level. */\ michael@0: rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t); \ michael@0: rbp_black_set(a_type, a_field, rbp_i_u); \ michael@0: if (rbp_left_get(a_type, a_field, rbp_i_p) == rbp_i_c) { \ michael@0: rbp_left_set(a_type, a_field, rbp_i_p, rbp_i_t); \ michael@0: rbp_i_c = rbp_i_t; \ michael@0: } else { \ michael@0: /* rbp_i_c was the right child of rbp_i_p, so rotate */\ michael@0: /* left in order to maintain the left-leaning */\ michael@0: /* invariant. */\ michael@0: assert(rbp_right_get(a_type, a_field, rbp_i_p) \ michael@0: == rbp_i_c); \ michael@0: rbp_right_set(a_type, a_field, rbp_i_p, rbp_i_t); \ michael@0: rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_u); \ michael@0: if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\ michael@0: rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_u); \ michael@0: } else { \ michael@0: assert(rbp_right_get(a_type, a_field, rbp_i_g) \ michael@0: == rbp_i_p); \ michael@0: rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_u); \ michael@0: } \ michael@0: rbp_i_p = rbp_i_u; \ michael@0: rbp_i_cmp = (a_cmp)((a_node), rbp_i_p); \ michael@0: if (rbp_i_cmp < 0) { \ michael@0: rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_p); \ michael@0: } else { \ michael@0: assert(rbp_i_cmp > 0); \ michael@0: rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_p); \ michael@0: } \ michael@0: continue; \ michael@0: } \ michael@0: } \ michael@0: rbp_i_g = rbp_i_p; \ michael@0: rbp_i_p = rbp_i_c; \ michael@0: rbp_i_cmp = (a_cmp)((a_node), rbp_i_c); \ michael@0: if (rbp_i_cmp < 0) { \ michael@0: rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_c); \ michael@0: } else { \ michael@0: assert(rbp_i_cmp > 0); \ michael@0: rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_c); \ michael@0: } \ michael@0: } \ michael@0: /* rbp_i_p now refers to the node under which to insert. */\ michael@0: rbp_node_new(a_type, a_field, a_tree, (a_node)); \ michael@0: if (rbp_i_cmp > 0) { \ michael@0: rbp_right_set(a_type, a_field, rbp_i_p, (a_node)); \ michael@0: rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_t); \ michael@0: if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) { \ michael@0: rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_t); \ michael@0: } else if (rbp_right_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\ michael@0: rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_t); \ michael@0: } \ michael@0: } else { \ michael@0: rbp_left_set(a_type, a_field, rbp_i_p, (a_node)); \ michael@0: } \ michael@0: /* Update the root and make sure that it is black. */\ michael@0: (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_i_s); \ michael@0: rbp_black_set(a_type, a_field, (a_tree)->rbt_root); \ michael@0: } while (0) michael@0: michael@0: #define rb_remove(a_type, a_field, a_cmp, a_tree, a_node) do { \ michael@0: a_type rbp_r_s; \ michael@0: a_type *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u; \ michael@0: int rbp_r_cmp; \ michael@0: rbp_left_set(a_type, a_field, &rbp_r_s, (a_tree)->rbt_root); \ michael@0: rbp_right_set(a_type, a_field, &rbp_r_s, &(a_tree)->rbt_nil); \ michael@0: rbp_black_set(a_type, a_field, &rbp_r_s); \ michael@0: rbp_r_p = &rbp_r_s; \ michael@0: rbp_r_c = (a_tree)->rbt_root; \ michael@0: rbp_r_xp = &(a_tree)->rbt_nil; \ michael@0: /* Iterate down the tree, but always transform 2-nodes to 3- or */\ michael@0: /* 4-nodes in order to maintain the invariant that the current */\ michael@0: /* node is not a 2-node. This allows simple deletion once a leaf */\ michael@0: /* is reached. Handle the root specially though, since there may */\ michael@0: /* be no way to convert it from a 2-node to a 3-node. */\ michael@0: rbp_r_cmp = (a_cmp)((a_node), rbp_r_c); \ michael@0: if (rbp_r_cmp < 0) { \ michael@0: rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c); \ michael@0: rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_r_t) == false \ michael@0: && rbp_red_get(a_type, a_field, rbp_r_u) == false) { \ michael@0: /* Apply standard transform to prepare for left move. */\ michael@0: rbp_move_red_left(a_type, a_field, rbp_r_c, rbp_r_t); \ michael@0: rbp_black_set(a_type, a_field, rbp_r_t); \ michael@0: rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t); \ michael@0: rbp_r_c = rbp_r_t; \ michael@0: } else { \ michael@0: /* Move left. */\ michael@0: rbp_r_p = rbp_r_c; \ michael@0: rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c); \ michael@0: } \ michael@0: } else { \ michael@0: if (rbp_r_cmp == 0) { \ michael@0: assert((a_node) == rbp_r_c); \ michael@0: if (rbp_right_get(a_type, a_field, rbp_r_c) \ michael@0: == &(a_tree)->rbt_nil) { \ michael@0: /* Delete root node (which is also a leaf node). */\ michael@0: if (rbp_left_get(a_type, a_field, rbp_r_c) \ michael@0: != &(a_tree)->rbt_nil) { \ michael@0: rbp_lean_right(a_type, a_field, rbp_r_c, rbp_r_t); \ michael@0: rbp_right_set(a_type, a_field, rbp_r_t, \ michael@0: &(a_tree)->rbt_nil); \ michael@0: } else { \ michael@0: rbp_r_t = &(a_tree)->rbt_nil; \ michael@0: } \ michael@0: rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t); \ michael@0: } else { \ michael@0: /* This is the node we want to delete, but we will */\ michael@0: /* instead swap it with its successor and delete the */\ michael@0: /* successor. Record enough information to do the */\ michael@0: /* swap later. rbp_r_xp is the a_node's parent. */\ michael@0: rbp_r_xp = rbp_r_p; \ michael@0: rbp_r_cmp = 1; /* Note that deletion is incomplete. */\ michael@0: } \ michael@0: } \ michael@0: if (rbp_r_cmp == 1) { \ michael@0: if (rbp_red_get(a_type, a_field, rbp_left_get(a_type, \ michael@0: a_field, rbp_right_get(a_type, a_field, rbp_r_c))) \ michael@0: == false) { \ michael@0: rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_r_t)) { \ michael@0: /* Standard transform. */\ michael@0: rbp_move_red_right(a_type, a_field, rbp_r_c, \ michael@0: rbp_r_t); \ michael@0: } else { \ michael@0: /* Root-specific transform. */\ michael@0: rbp_red_set(a_type, a_field, rbp_r_c); \ michael@0: rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_r_u)) { \ michael@0: rbp_black_set(a_type, a_field, rbp_r_u); \ michael@0: rbp_rotate_right(a_type, a_field, rbp_r_c, \ michael@0: rbp_r_t); \ michael@0: rbp_rotate_left(a_type, a_field, rbp_r_c, \ michael@0: rbp_r_u); \ michael@0: rbp_right_set(a_type, a_field, rbp_r_t, \ michael@0: rbp_r_u); \ michael@0: } else { \ michael@0: rbp_red_set(a_type, a_field, rbp_r_t); \ michael@0: rbp_rotate_left(a_type, a_field, rbp_r_c, \ michael@0: rbp_r_t); \ michael@0: } \ michael@0: } \ michael@0: rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t); \ michael@0: rbp_r_c = rbp_r_t; \ michael@0: } else { \ michael@0: /* Move right. */\ michael@0: rbp_r_p = rbp_r_c; \ michael@0: rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c); \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: if (rbp_r_cmp != 0) { \ michael@0: while (true) { \ michael@0: assert(rbp_r_p != &(a_tree)->rbt_nil); \ michael@0: rbp_r_cmp = (a_cmp)((a_node), rbp_r_c); \ michael@0: if (rbp_r_cmp < 0) { \ michael@0: rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c); \ michael@0: if (rbp_r_t == &(a_tree)->rbt_nil) { \ michael@0: /* rbp_r_c now refers to the successor node to */\ michael@0: /* relocate, and rbp_r_xp/a_node refer to the */\ michael@0: /* context for the relocation. */\ michael@0: if (rbp_left_get(a_type, a_field, rbp_r_xp) \ michael@0: == (a_node)) { \ michael@0: rbp_left_set(a_type, a_field, rbp_r_xp, \ michael@0: rbp_r_c); \ michael@0: } else { \ michael@0: assert(rbp_right_get(a_type, a_field, \ michael@0: rbp_r_xp) == (a_node)); \ michael@0: rbp_right_set(a_type, a_field, rbp_r_xp, \ michael@0: rbp_r_c); \ michael@0: } \ michael@0: rbp_left_set(a_type, a_field, rbp_r_c, \ michael@0: rbp_left_get(a_type, a_field, (a_node))); \ michael@0: rbp_right_set(a_type, a_field, rbp_r_c, \ michael@0: rbp_right_get(a_type, a_field, (a_node))); \ michael@0: rbp_color_set(a_type, a_field, rbp_r_c, \ michael@0: rbp_red_get(a_type, a_field, (a_node))); \ michael@0: if (rbp_left_get(a_type, a_field, rbp_r_p) \ michael@0: == rbp_r_c) { \ michael@0: rbp_left_set(a_type, a_field, rbp_r_p, \ michael@0: &(a_tree)->rbt_nil); \ michael@0: } else { \ michael@0: assert(rbp_right_get(a_type, a_field, rbp_r_p) \ michael@0: == rbp_r_c); \ michael@0: rbp_right_set(a_type, a_field, rbp_r_p, \ michael@0: &(a_tree)->rbt_nil); \ michael@0: } \ michael@0: break; \ michael@0: } \ michael@0: rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_r_t) == false \ michael@0: && rbp_red_get(a_type, a_field, rbp_r_u) == false) { \ michael@0: rbp_move_red_left(a_type, a_field, rbp_r_c, \ michael@0: rbp_r_t); \ michael@0: if (rbp_left_get(a_type, a_field, rbp_r_p) \ michael@0: == rbp_r_c) { \ michael@0: rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\ michael@0: } else { \ michael@0: rbp_right_set(a_type, a_field, rbp_r_p, \ michael@0: rbp_r_t); \ michael@0: } \ michael@0: rbp_r_c = rbp_r_t; \ michael@0: } else { \ michael@0: rbp_r_p = rbp_r_c; \ michael@0: rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c); \ michael@0: } \ michael@0: } else { \ michael@0: /* Check whether to delete this node (it has to be */\ michael@0: /* the correct node and a leaf node). */\ michael@0: if (rbp_r_cmp == 0) { \ michael@0: assert((a_node) == rbp_r_c); \ michael@0: if (rbp_right_get(a_type, a_field, rbp_r_c) \ michael@0: == &(a_tree)->rbt_nil) { \ michael@0: /* Delete leaf node. */\ michael@0: if (rbp_left_get(a_type, a_field, rbp_r_c) \ michael@0: != &(a_tree)->rbt_nil) { \ michael@0: rbp_lean_right(a_type, a_field, rbp_r_c, \ michael@0: rbp_r_t); \ michael@0: rbp_right_set(a_type, a_field, rbp_r_t, \ michael@0: &(a_tree)->rbt_nil); \ michael@0: } else { \ michael@0: rbp_r_t = &(a_tree)->rbt_nil; \ michael@0: } \ michael@0: if (rbp_left_get(a_type, a_field, rbp_r_p) \ michael@0: == rbp_r_c) { \ michael@0: rbp_left_set(a_type, a_field, rbp_r_p, \ michael@0: rbp_r_t); \ michael@0: } else { \ michael@0: rbp_right_set(a_type, a_field, rbp_r_p, \ michael@0: rbp_r_t); \ michael@0: } \ michael@0: break; \ michael@0: } else { \ michael@0: /* This is the node we want to delete, but we */\ michael@0: /* will instead swap it with its successor */\ michael@0: /* and delete the successor. Record enough */\ michael@0: /* information to do the swap later. */\ michael@0: /* rbp_r_xp is a_node's parent. */\ michael@0: rbp_r_xp = rbp_r_p; \ michael@0: } \ michael@0: } \ michael@0: rbp_r_t = rbp_right_get(a_type, a_field, rbp_r_c); \ michael@0: rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t); \ michael@0: if (rbp_red_get(a_type, a_field, rbp_r_u) == false) { \ michael@0: rbp_move_red_right(a_type, a_field, rbp_r_c, \ michael@0: rbp_r_t); \ michael@0: if (rbp_left_get(a_type, a_field, rbp_r_p) \ michael@0: == rbp_r_c) { \ michael@0: rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\ michael@0: } else { \ michael@0: rbp_right_set(a_type, a_field, rbp_r_p, \ michael@0: rbp_r_t); \ michael@0: } \ michael@0: rbp_r_c = rbp_r_t; \ michael@0: } else { \ michael@0: rbp_r_p = rbp_r_c; \ michael@0: rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c); \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: /* Update root. */\ michael@0: (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_r_s); \ michael@0: } while (0) michael@0: michael@0: /* michael@0: * The rb_wrap() macro provides a convenient way to wrap functions around the michael@0: * cpp macros. The main benefits of wrapping are that 1) repeated macro michael@0: * expansion can cause code bloat, especially for rb_{insert,remove)(), and michael@0: * 2) type, linkage, comparison functions, etc. need not be specified at every michael@0: * call point. michael@0: */ michael@0: michael@0: #define rb_wrap(a_attr, a_prefix, a_tree_type, a_type, a_field, a_cmp) \ michael@0: a_attr void \ michael@0: a_prefix##new(a_tree_type *tree) { \ michael@0: rb_new(a_type, a_field, tree); \ michael@0: } \ michael@0: a_attr a_type * \ michael@0: a_prefix##first(a_tree_type *tree) { \ michael@0: a_type *ret; \ michael@0: rb_first(a_type, a_field, tree, ret); \ michael@0: return (ret); \ michael@0: } \ michael@0: a_attr a_type * \ michael@0: a_prefix##last(a_tree_type *tree) { \ michael@0: a_type *ret; \ michael@0: rb_last(a_type, a_field, tree, ret); \ michael@0: return (ret); \ michael@0: } \ michael@0: a_attr a_type * \ michael@0: a_prefix##next(a_tree_type *tree, a_type *node) { \ michael@0: a_type *ret; \ michael@0: rb_next(a_type, a_field, a_cmp, tree, node, ret); \ michael@0: return (ret); \ michael@0: } \ michael@0: a_attr a_type * \ michael@0: a_prefix##prev(a_tree_type *tree, a_type *node) { \ michael@0: a_type *ret; \ michael@0: rb_prev(a_type, a_field, a_cmp, tree, node, ret); \ michael@0: return (ret); \ michael@0: } \ michael@0: a_attr a_type * \ michael@0: a_prefix##search(a_tree_type *tree, a_type *key) { \ michael@0: a_type *ret; \ michael@0: rb_search(a_type, a_field, a_cmp, tree, key, ret); \ michael@0: return (ret); \ michael@0: } \ michael@0: a_attr a_type * \ michael@0: a_prefix##nsearch(a_tree_type *tree, a_type *key) { \ michael@0: a_type *ret; \ michael@0: rb_nsearch(a_type, a_field, a_cmp, tree, key, ret); \ michael@0: return (ret); \ michael@0: } \ michael@0: a_attr a_type * \ michael@0: a_prefix##psearch(a_tree_type *tree, a_type *key) { \ michael@0: a_type *ret; \ michael@0: rb_psearch(a_type, a_field, a_cmp, tree, key, ret); \ michael@0: return (ret); \ michael@0: } \ michael@0: a_attr void \ michael@0: a_prefix##insert(a_tree_type *tree, a_type *node) { \ michael@0: rb_insert(a_type, a_field, a_cmp, tree, node); \ michael@0: } \ michael@0: a_attr void \ michael@0: a_prefix##remove(a_tree_type *tree, a_type *node) { \ michael@0: rb_remove(a_type, a_field, a_cmp, tree, node); \ michael@0: } michael@0: michael@0: /* michael@0: * The iterators simulate recursion via an array of pointers that store the michael@0: * current path. This is critical to performance, since a series of calls to michael@0: * rb_{next,prev}() would require time proportional to (n lg n), whereas this michael@0: * implementation only requires time proportional to (n). michael@0: * michael@0: * Since the iterators cache a path down the tree, any tree modification may michael@0: * cause the cached path to become invalid. In order to continue iteration, michael@0: * use something like the following sequence: michael@0: * michael@0: * { michael@0: * a_type *node, *tnode; michael@0: * michael@0: * rb_foreach_begin(a_type, a_field, a_tree, node) { michael@0: * ... michael@0: * rb_next(a_type, a_field, a_cmp, a_tree, node, tnode); michael@0: * rb_remove(a_type, a_field, a_cmp, a_tree, node); michael@0: * rb_foreach_next(a_type, a_field, a_cmp, a_tree, tnode); michael@0: * ... michael@0: * } rb_foreach_end(a_type, a_field, a_tree, node) michael@0: * } michael@0: * michael@0: * Note that this idiom is not advised if every iteration modifies the tree, michael@0: * since in that case there is no algorithmic complexity improvement over a michael@0: * series of rb_{next,prev}() calls, thus making the setup overhead wasted michael@0: * effort. michael@0: */ michael@0: michael@0: #ifdef RB_NO_C99_VARARRAYS michael@0: /* michael@0: * Avoid using variable-length arrays, at the cost of using more stack space. michael@0: * Size the path arrays such that they are always large enough, even if a michael@0: * tree consumes all of memory. Since each node must contain a minimum of michael@0: * two pointers, there can never be more nodes than: michael@0: * michael@0: * 1 << ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)) michael@0: * michael@0: * Since the depth of a tree is limited to 3*lg(#nodes), the maximum depth michael@0: * is: michael@0: * michael@0: * (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1))) michael@0: * michael@0: * This works out to a maximum depth of 87 and 180 for 32- and 64-bit michael@0: * systems, respectively (approximatly 348 and 1440 bytes, respectively). michael@0: */ michael@0: # define rbp_compute_f_height(a_type, a_field, a_tree) michael@0: # define rbp_f_height (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1))) michael@0: # define rbp_compute_fr_height(a_type, a_field, a_tree) michael@0: # define rbp_fr_height (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1))) michael@0: #else michael@0: # define rbp_compute_f_height(a_type, a_field, a_tree) \ michael@0: /* Compute the maximum possible tree depth (3X the black height). */\ michael@0: unsigned rbp_f_height; \ michael@0: rbp_black_height(a_type, a_field, a_tree, rbp_f_height); \ michael@0: rbp_f_height *= 3; michael@0: # define rbp_compute_fr_height(a_type, a_field, a_tree) \ michael@0: /* Compute the maximum possible tree depth (3X the black height). */\ michael@0: unsigned rbp_fr_height; \ michael@0: rbp_black_height(a_type, a_field, a_tree, rbp_fr_height); \ michael@0: rbp_fr_height *= 3; michael@0: #endif michael@0: michael@0: #define rb_foreach_begin(a_type, a_field, a_tree, a_var) { \ michael@0: rbp_compute_f_height(a_type, a_field, a_tree) \ michael@0: { \ michael@0: /* Initialize the path to contain the left spine. */\ michael@0: a_type *rbp_f_path[rbp_f_height]; \ michael@0: a_type *rbp_f_node; \ michael@0: bool rbp_f_synced = false; \ michael@0: unsigned rbp_f_depth = 0; \ michael@0: if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) { \ michael@0: rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root; \ michael@0: rbp_f_depth++; \ michael@0: while ((rbp_f_node = rbp_left_get(a_type, a_field, \ michael@0: rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) { \ michael@0: rbp_f_path[rbp_f_depth] = rbp_f_node; \ michael@0: rbp_f_depth++; \ michael@0: } \ michael@0: } \ michael@0: /* While the path is non-empty, iterate. */\ michael@0: while (rbp_f_depth > 0) { \ michael@0: (a_var) = rbp_f_path[rbp_f_depth-1]; michael@0: michael@0: /* Only use if modifying the tree during iteration. */ michael@0: #define rb_foreach_next(a_type, a_field, a_cmp, a_tree, a_node) \ michael@0: /* Re-initialize the path to contain the path to a_node. */\ michael@0: rbp_f_depth = 0; \ michael@0: if (a_node != NULL) { \ michael@0: if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) { \ michael@0: rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root; \ michael@0: rbp_f_depth++; \ michael@0: rbp_f_node = rbp_f_path[0]; \ michael@0: while (true) { \ michael@0: int rbp_f_cmp = (a_cmp)((a_node), \ michael@0: rbp_f_path[rbp_f_depth-1]); \ michael@0: if (rbp_f_cmp < 0) { \ michael@0: rbp_f_node = rbp_left_get(a_type, a_field, \ michael@0: rbp_f_path[rbp_f_depth-1]); \ michael@0: } else if (rbp_f_cmp > 0) { \ michael@0: rbp_f_node = rbp_right_get(a_type, a_field, \ michael@0: rbp_f_path[rbp_f_depth-1]); \ michael@0: } else { \ michael@0: break; \ michael@0: } \ michael@0: assert(rbp_f_node != &(a_tree)->rbt_nil); \ michael@0: rbp_f_path[rbp_f_depth] = rbp_f_node; \ michael@0: rbp_f_depth++; \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: rbp_f_synced = true; michael@0: michael@0: #define rb_foreach_end(a_type, a_field, a_tree, a_var) \ michael@0: if (rbp_f_synced) { \ michael@0: rbp_f_synced = false; \ michael@0: continue; \ michael@0: } \ michael@0: /* Find the successor. */\ michael@0: if ((rbp_f_node = rbp_right_get(a_type, a_field, \ michael@0: rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) { \ michael@0: /* The successor is the left-most node in the right */\ michael@0: /* subtree. */\ michael@0: rbp_f_path[rbp_f_depth] = rbp_f_node; \ michael@0: rbp_f_depth++; \ michael@0: while ((rbp_f_node = rbp_left_get(a_type, a_field, \ michael@0: rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) { \ michael@0: rbp_f_path[rbp_f_depth] = rbp_f_node; \ michael@0: rbp_f_depth++; \ michael@0: } \ michael@0: } else { \ michael@0: /* The successor is above the current node. Unwind */\ michael@0: /* until a left-leaning edge is removed from the */\ michael@0: /* path, or the path is empty. */\ michael@0: for (rbp_f_depth--; rbp_f_depth > 0; rbp_f_depth--) { \ michael@0: if (rbp_left_get(a_type, a_field, \ michael@0: rbp_f_path[rbp_f_depth-1]) \ michael@0: == rbp_f_path[rbp_f_depth]) { \ michael@0: break; \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: } michael@0: michael@0: #define rb_foreach_reverse_begin(a_type, a_field, a_tree, a_var) { \ michael@0: rbp_compute_fr_height(a_type, a_field, a_tree) \ michael@0: { \ michael@0: /* Initialize the path to contain the right spine. */\ michael@0: a_type *rbp_fr_path[rbp_fr_height]; \ michael@0: a_type *rbp_fr_node; \ michael@0: bool rbp_fr_synced = false; \ michael@0: unsigned rbp_fr_depth = 0; \ michael@0: if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) { \ michael@0: rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root; \ michael@0: rbp_fr_depth++; \ michael@0: while ((rbp_fr_node = rbp_right_get(a_type, a_field, \ michael@0: rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) { \ michael@0: rbp_fr_path[rbp_fr_depth] = rbp_fr_node; \ michael@0: rbp_fr_depth++; \ michael@0: } \ michael@0: } \ michael@0: /* While the path is non-empty, iterate. */\ michael@0: while (rbp_fr_depth > 0) { \ michael@0: (a_var) = rbp_fr_path[rbp_fr_depth-1]; michael@0: michael@0: /* Only use if modifying the tree during iteration. */ michael@0: #define rb_foreach_reverse_prev(a_type, a_field, a_cmp, a_tree, a_node) \ michael@0: /* Re-initialize the path to contain the path to a_node. */\ michael@0: rbp_fr_depth = 0; \ michael@0: if (a_node != NULL) { \ michael@0: if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) { \ michael@0: rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root; \ michael@0: rbp_fr_depth++; \ michael@0: rbp_fr_node = rbp_fr_path[0]; \ michael@0: while (true) { \ michael@0: int rbp_fr_cmp = (a_cmp)((a_node), \ michael@0: rbp_fr_path[rbp_fr_depth-1]); \ michael@0: if (rbp_fr_cmp < 0) { \ michael@0: rbp_fr_node = rbp_left_get(a_type, a_field, \ michael@0: rbp_fr_path[rbp_fr_depth-1]); \ michael@0: } else if (rbp_fr_cmp > 0) { \ michael@0: rbp_fr_node = rbp_right_get(a_type, a_field,\ michael@0: rbp_fr_path[rbp_fr_depth-1]); \ michael@0: } else { \ michael@0: break; \ michael@0: } \ michael@0: assert(rbp_fr_node != &(a_tree)->rbt_nil); \ michael@0: rbp_fr_path[rbp_fr_depth] = rbp_fr_node; \ michael@0: rbp_fr_depth++; \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: rbp_fr_synced = true; michael@0: michael@0: #define rb_foreach_reverse_end(a_type, a_field, a_tree, a_var) \ michael@0: if (rbp_fr_synced) { \ michael@0: rbp_fr_synced = false; \ michael@0: continue; \ michael@0: } \ michael@0: if (rbp_fr_depth == 0) { \ michael@0: /* rb_foreach_reverse_sync() was called with a NULL */\ michael@0: /* a_node. */\ michael@0: break; \ michael@0: } \ michael@0: /* Find the predecessor. */\ michael@0: if ((rbp_fr_node = rbp_left_get(a_type, a_field, \ michael@0: rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) { \ michael@0: /* The predecessor is the right-most node in the left */\ michael@0: /* subtree. */\ michael@0: rbp_fr_path[rbp_fr_depth] = rbp_fr_node; \ michael@0: rbp_fr_depth++; \ michael@0: while ((rbp_fr_node = rbp_right_get(a_type, a_field, \ michael@0: rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {\ michael@0: rbp_fr_path[rbp_fr_depth] = rbp_fr_node; \ michael@0: rbp_fr_depth++; \ michael@0: } \ michael@0: } else { \ michael@0: /* The predecessor is above the current node. Unwind */\ michael@0: /* until a right-leaning edge is removed from the */\ michael@0: /* path, or the path is empty. */\ michael@0: for (rbp_fr_depth--; rbp_fr_depth > 0; rbp_fr_depth--) {\ michael@0: if (rbp_right_get(a_type, a_field, \ michael@0: rbp_fr_path[rbp_fr_depth-1]) \ michael@0: == rbp_fr_path[rbp_fr_depth]) { \ michael@0: break; \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: } michael@0: michael@0: #endif /* RB_H_ */