The Tor Browser / file revision

 /******************************************************************************

  *

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