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