/****************************************************************************** * * Copyright (C) 2008 Jason Evans . * Copyright (C) 2015-2019 Mark Straver * * 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 * #include * ... * * 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_ /* 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_ */