memory/mozjemalloc/rb.h
author Gregory Szorc <gps@mozilla.com>
Tue, 24 May 2016 08:47:24 -0700
changeset 298856 408319d87eacb28848efeab0346eb815440adade
parent 96044 87bd340fac6aa9f70c42bb4a8fbe0b7325277b0d
child 359108 1a4fb12801bd124d3b025ffcf40ac2724a2e9f2e
permissions -rw-r--r--
Bug 1275297 - Create Visual Studio project files by default on Windows; r=glandium Now that the VisualStudio backend will no-op if nothing has changed, it should be safe to always run this backend. On first run, backend generation takes ~3.5s on my machine. On subsequent run, it takes ~1.5s. Wall time for a no-op config.status is now ~15.7s. We could like make the Visual Studio backend faster by not writing so many project files. But this would require consolidating libraries in moz.build files. And that's out of scope for this change. MozReview-Commit-ID: 5W38HMGmcuV

/******************************************************************************
 *
 * 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_ */