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