rb.h

Go to the documentation of this file.

/*-
 *******************************************************************************
 *
 * cpp macro implementation of left-leaning 2-3 red-black trees. Parent
 * pointers are not used, and color bits are stored in the least significant
 * bit of right-child pointers (if RB_COMPACT is defined), thus making node
 * linkage as compact as is possible for red-black trees.
 *
 * Usage:
 *
 * #include <stdint.h>
 * #include <stdbool.h>
 * #define NDEBUG // (Optional, see assert(3).)
 * #include <assert.h>
 * #define RB_COMPACT // (Optional, embed color bits in right-child pointers.)
 * #include <rb.h>
 * ...
 *
 *******************************************************************************
 */

#ifndef RB_H_
#define RB_H_

#ifdef RB_COMPACT
/* Node structure. */
#define rb_node(a_type) \
struct { \
 a_type *rbn_left; \
 a_type *rbn_right_red; \
}
#else
#define rb_node(a_type) \
struct { \
 a_type *rbn_left; \
 a_type *rbn_right; \
 bool rbn_red; \
}
#endif

/* Root structure. */
#define rb_tree(a_type) \
struct { \
 a_type *rbt_root; \
 a_type rbt_nil; \
}

/* Left accessors. */
#define rbtn_left_get(a_type, a_field, a_node) \
 ((a_node)->a_field.rbn_left)
#define rbtn_left_set(a_type, a_field, a_node, a_left) do { \
 (a_node)->a_field.rbn_left = a_left; \
} while (0)

#ifdef RB_COMPACT
/* Right accessors. */
#define rbtn_right_get(a_type, a_field, a_node) \
 ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \
 & ((ssize_t)-2)))
#define rbtn_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 rbtn_red_get(a_type, a_field, a_node) \
 ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \
 & ((size_t)1)))
#define rbtn_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 rbtn_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 rbtn_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)
#else
/* Right accessors. */
#define rbtn_right_get(a_type, a_field, a_node) \
 ((a_node)->a_field.rbn_right)
#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
 (a_node)->a_field.rbn_right = a_right; \
} while (0)

/* Color accessors. */
#define rbtn_red_get(a_type, a_field, a_node) \
 ((a_node)->a_field.rbn_red)
#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
 (a_node)->a_field.rbn_red = (a_red); \
} while (0)
#define rbtn_red_set(a_type, a_field, a_node) do { \
 (a_node)->a_field.rbn_red = true; \
} while (0)
#define rbtn_black_set(a_type, a_field, a_node) do { \
 (a_node)->a_field.rbn_red = false; \
} while (0)
#endif

/* Node initializer. */
#define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \
 rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \
 rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \
 rbtn_red_set(a_type, a_field, (a_node)); \
} while (0)

/* Tree initializer. */
#define rb_new(a_type, a_field, a_rbt) do { \
 (a_rbt)->rbt_root = &(a_rbt)->rbt_nil; \
 rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil); \
 rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil); \
} while (0)

/* Internal utility macros. */
#define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \
 (r_node) = (a_root); \
 if ((r_node) != &(a_rbt)->rbt_nil) { \
 for (; \
 rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\
 (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \
 } \
 } \
} while (0)

#define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \
 (r_node) = (a_root); \
 if ((r_node) != &(a_rbt)->rbt_nil) { \
 for (; rbtn_right_get(a_type, a_field, (r_node)) != \
 &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \
 (r_node))) { \
 } \
 } \
} while (0)

#define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \
 (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \
 rbtn_right_set(a_type, a_field, (a_node), \
 rbtn_left_get(a_type, a_field, (r_node))); \
 rbtn_left_set(a_type, a_field, (r_node), (a_node)); \
} while (0)

#define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \
 (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \
 rbtn_left_set(a_type, a_field, (a_node), \
 rbtn_right_get(a_type, a_field, (r_node))); \
 rbtn_right_set(a_type, a_field, (r_node), (a_node)); \
} while (0)

/*
 * The rb_proto() macro generates function prototypes that correspond to the
 * functions generated by an equivalently parameterized call to rb_gen().
 */

#define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \
a_attr void \
a_prefix##new(a_rbt_type *rbtree); \
a_attr a_type * \
a_prefix##first(a_rbt_type *rbtree); \
a_attr a_type * \
a_prefix##last(a_rbt_type *rbtree); \
a_attr a_type * \
a_prefix##next(a_rbt_type *rbtree, a_type *node); \
a_attr a_type * \
a_prefix##prev(a_rbt_type *rbtree, a_type *node); \
a_attr a_type * \
a_prefix##search(a_rbt_type *rbtree, a_type *key); \
a_attr a_type * \
a_prefix##nsearch(a_rbt_type *rbtree, a_type *key); \
a_attr a_type * \
a_prefix##psearch(a_rbt_type *rbtree, a_type *key); \
a_attr void \
a_prefix##insert(a_rbt_type *rbtree, a_type *node); \
a_attr void \
a_prefix##remove(a_rbt_type *rbtree, a_type *node); \
a_attr a_type * \
a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
 a_rbt_type *, a_type *, void *), void *arg); \
a_attr a_type * \
a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg);

/*
 * The rb_gen() macro generates a type-specific red-black tree implementation,
 * based on the above cpp macros.
 *
 * Arguments:
 *
 * a_attr : Function attribute for generated functions (ex: static).
 * a_prefix : Prefix for generated functions (ex: ex_).
 * a_rb_type : Type for red-black tree data structure (ex: ex_t).
 * a_type : Type for red-black tree node data structure (ex: ex_node_t).
 * a_field : Name of red-black tree node linkage (ex: ex_link).
 * a_cmp : Node comparison function name, with 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.
 *
 * Assuming the following setup:
 *
 * typedef struct ex_node_s ex_node_t;
 * struct ex_node_s {
 * rb_node(ex_node_t) ex_link;
 * };
 * typedef rb_tree(ex_node_t) ex_t;
 * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp)
 *
 * The following API is generated:
 *
 * static void
 * ex_new(ex_t *tree);
 * Description: Initialize a red-black tree structure.
 * Args:
 * tree: Pointer to an uninitialized red-black tree object.
 *
 * static ex_node_t *
 * ex_first(ex_t *tree);
 * static ex_node_t *
 * ex_last(ex_t *tree);
 * Description: Get the first/last node in tree.
 * Args:
 * tree: Pointer to an initialized red-black tree object.
 * Ret: First/last node in tree, or NULL if tree is empty.
 *
 * static ex_node_t *
 * ex_next(ex_t *tree, ex_node_t *node);
 * static ex_node_t *
 * ex_prev(ex_t *tree, ex_node_t *node);
 * Description: Get node's successor/predecessor.
 * Args:
 * tree: Pointer to an initialized red-black tree object.
 * node: A node in tree.
 * Ret: node's successor/predecessor in tree, or NULL if node is
 * last/first.
 *
 * static ex_node_t *
 * ex_search(ex_t *tree, ex_node_t *key);
 * Description: Search for node that matches key.
 * Args:
 * tree: Pointer to an initialized red-black tree object.
 * key : Search key.
 * Ret: Node in tree that matches key, or NULL if no match.
 *
 * static ex_node_t *
 * ex_nsearch(ex_t *tree, ex_node_t *key);
 * static ex_node_t *
 * ex_psearch(ex_t *tree, ex_node_t *key);
 * Description: Search for node that matches key. If no match is found,
 * return what would be key's successor/predecessor, were
 * key in tree.
 * Args:
 * tree: Pointer to an initialized red-black tree object.
 * key : Search key.
 * Ret: Node in tree that matches key, or if no match, hypothetical node's
 * successor/predecessor (NULL if no successor/predecessor).
 *
 * static void
 * ex_insert(ex_t *tree, ex_node_t *node);
 * Description: Insert node into tree.
 * Args:
 * tree: Pointer to an initialized red-black tree object.
 * node: Node to be inserted into tree.
 *
 * static void
 * ex_remove(ex_t *tree, ex_node_t *node);
 * Description: Remove node from tree.
 * Args:
 * tree: Pointer to an initialized red-black tree object.
 * node: Node in tree to be removed.
 *
 * static ex_node_t *
 * ex_iter(ex_t *tree, ex_node_t *start, ex_node_t *(*cb)(ex_t *,
 * ex_node_t *, void *), void *arg);
 * static ex_node_t *
 * ex_reverse_iter(ex_t *tree, ex_node_t *start, ex_node *(*cb)(ex_t *,
 * ex_node_t *, void *), void *arg);
 * Description: Iterate forward/backward over tree, starting at node. If
 * tree is modified, iteration must be immediately
 * terminated by the callback function that causes the
 * modification.
 * Args:
 * tree : Pointer to an initialized red-black tree object.
 * start: Node at which to start iteration, or NULL to start at
 * first/last node.
 * cb : Callback function, which is called for each node during
 * iteration. Under normal circumstances the callback function
 * should return NULL, which causes iteration to continue. If a
 * callback function returns non-NULL, iteration is immediately
 * terminated and the non-NULL return value is returned by the
 * iterator. This is useful for re-starting iteration after
 * modifying tree.
 * arg : Opaque pointer passed to cb().
 * Ret: NULL if iteration completed, or the non-NULL callback return value
 * that caused termination of the iteration.
 */
#define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \
a_attr void \
a_prefix##new(a_rbt_type *rbtree) { \
 rb_new(a_type, a_field, rbtree); \
} \
a_attr a_type * \
a_prefix##first(a_rbt_type *rbtree) { \
 a_type *ret; \
 rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
 if (ret == &rbtree->rbt_nil) { \
 ret = NULL; \
 } \
 return (ret); \
} \
a_attr a_type * \
a_prefix##last(a_rbt_type *rbtree) { \
 a_type *ret; \
 rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
 if (ret == &rbtree->rbt_nil) { \
 ret = NULL; \
 } \
 return (ret); \
} \
a_attr a_type * \
a_prefix##next(a_rbt_type *rbtree, a_type *node) { \
 a_type *ret; \
 if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) { \
 rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \
 a_field, node), ret); \
 } else { \
 a_type *tnode = rbtree->rbt_root; \
 assert(tnode != &rbtree->rbt_nil); \
 ret = &rbtree->rbt_nil; \
 while (true) { \
 int cmp = (a_cmp)(node, tnode); \
 if (cmp < 0) { \
 ret = tnode; \
 tnode = rbtn_left_get(a_type, a_field, tnode); \
 } else if (cmp > 0) { \
 tnode = rbtn_right_get(a_type, a_field, tnode); \
 } else { \
 break; \
 } \
 assert(tnode != &rbtree->rbt_nil); \
 } \
 } \
 if (ret == &rbtree->rbt_nil) { \
 ret = (NULL); \
 } \
 return (ret); \
} \
a_attr a_type * \
a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \
 a_type *ret; \
 if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) { \
 rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \
 a_field, node), ret); \
 } else { \
 a_type *tnode = rbtree->rbt_root; \
 assert(tnode != &rbtree->rbt_nil); \
 ret = &rbtree->rbt_nil; \
 while (true) { \
 int cmp = (a_cmp)(node, tnode); \
 if (cmp < 0) { \
 tnode = rbtn_left_get(a_type, a_field, tnode); \
 } else if (cmp > 0) { \
 ret = tnode; \
 tnode = rbtn_right_get(a_type, a_field, tnode); \
 } else { \
 break; \
 } \
 assert(tnode != &rbtree->rbt_nil); \
 } \
 } \
 if (ret == &rbtree->rbt_nil) { \
 ret = (NULL); \
 } \
 return (ret); \
} \
a_attr a_type * \
a_prefix##search(a_rbt_type *rbtree, a_type *key) { \
 a_type *ret; \
 int cmp; \
 ret = rbtree->rbt_root; \
 while (ret != &rbtree->rbt_nil \
 && (cmp = (a_cmp)(key, ret)) != 0) { \
 if (cmp < 0) { \
 ret = rbtn_left_get(a_type, a_field, ret); \
 } else { \
 ret = rbtn_right_get(a_type, a_field, ret); \
 } \
 } \
 if (ret == &rbtree->rbt_nil) { \
 ret = (NULL); \
 } \
 return (ret); \
} \
a_attr a_type * \
a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) { \
 a_type *ret; \
 a_type *tnode = rbtree->rbt_root; \
 ret = &rbtree->rbt_nil; \
 while (tnode != &rbtree->rbt_nil) { \
 int cmp = (a_cmp)(key, tnode); \
 if (cmp < 0) { \
 ret = tnode; \
 tnode = rbtn_left_get(a_type, a_field, tnode); \
 } else if (cmp > 0) { \
 tnode = rbtn_right_get(a_type, a_field, tnode); \
 } else { \
 ret = tnode; \
 break; \
 } \
 } \
 if (ret == &rbtree->rbt_nil) { \
 ret = (NULL); \
 } \
 return (ret); \
} \
a_attr a_type * \
a_prefix##psearch(a_rbt_type *rbtree, a_type *key) { \
 a_type *ret; \
 a_type *tnode = rbtree->rbt_root; \
 ret = &rbtree->rbt_nil; \
 while (tnode != &rbtree->rbt_nil) { \
 int cmp = (a_cmp)(key, tnode); \
 if (cmp < 0) { \
 tnode = rbtn_left_get(a_type, a_field, tnode); \
 } else if (cmp > 0) { \
 ret = tnode; \
 tnode = rbtn_right_get(a_type, a_field, tnode); \
 } else { \
 ret = tnode; \
 break; \
 } \
 } \
 if (ret == &rbtree->rbt_nil) { \
 ret = (NULL); \
 } \
 return (ret); \
} \
a_attr void \
a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \
 struct { \
 a_type *node; \
 int cmp; \
 } path[sizeof(void *) << 4], *pathp; \
 rbt_node_new(a_type, a_field, rbtree, node); \
 /* Wind. */ \
 path->node = rbtree->rbt_root; \
 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
 assert(cmp != 0); \
 if (cmp < 0) { \
 pathp[1].node = rbtn_left_get(a_type, a_field, \
 pathp->node); \
 } else { \
 pathp[1].node = rbtn_right_get(a_type, a_field, \
 pathp->node); \
 } \
 } \
 pathp->node = node; \
 /* Unwind. */ \
 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
 a_type *cnode = pathp->node; \
 if (pathp->cmp < 0) { \
 a_type *left = pathp[1].node; \
 rbtn_left_set(a_type, a_field, cnode, left); \
 if (rbtn_red_get(a_type, a_field, left)) { \
 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
 if (rbtn_red_get(a_type, a_field, leftleft)) { \
 /* Fix up 4-node. */ \
 a_type *tnode; \
 rbtn_black_set(a_type, a_field, leftleft); \
 rbtn_rotate_right(a_type, a_field, cnode, tnode); \
 cnode = tnode; \
 } \
 } else { \
 return; \
 } \
 } else { \
 a_type *right = pathp[1].node; \
 rbtn_right_set(a_type, a_field, cnode, right); \
 if (rbtn_red_get(a_type, a_field, right)) { \
 a_type *left = rbtn_left_get(a_type, a_field, cnode); \
 if (rbtn_red_get(a_type, a_field, left)) { \
 /* Split 4-node. */ \
 rbtn_black_set(a_type, a_field, left); \
 rbtn_black_set(a_type, a_field, right); \
 rbtn_red_set(a_type, a_field, cnode); \
 } else { \
 /* Lean left. */ \
 a_type *tnode; \
 bool tred = rbtn_red_get(a_type, a_field, cnode); \
 rbtn_rotate_left(a_type, a_field, cnode, tnode); \
 rbtn_color_set(a_type, a_field, tnode, tred); \
 rbtn_red_set(a_type, a_field, cnode); \
 cnode = tnode; \
 } \
 } else { \
 return; \
 } \
 } \
 pathp->node = cnode; \
 } \
 /* Set root, and make it black. */ \
 rbtree->rbt_root = path->node; \
 rbtn_black_set(a_type, a_field, rbtree->rbt_root); \
} \
a_attr void \
a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \
 struct { \
 a_type *node; \
 int cmp; \
 } *pathp, *nodep, path[sizeof(void *) << 4]; \
 /* Wind. */ \
 nodep = NULL; /* Silence compiler warning. */ \
 path->node = rbtree->rbt_root; \
 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
 if (cmp < 0) { \
 pathp[1].node = rbtn_left_get(a_type, a_field, \
 pathp->node); \
 } else { \
 pathp[1].node = rbtn_right_get(a_type, a_field, \
 pathp->node); \
 if (cmp == 0) { \
 /* Find node's successor, in preparation for swap. */ \
 pathp->cmp = 1; \
 nodep = pathp; \
 for (pathp++; pathp->node != &rbtree->rbt_nil; \
 pathp++) { \
 pathp->cmp = -1; \
 pathp[1].node = rbtn_left_get(a_type, a_field, \
 pathp->node); \
 } \
 break; \
 } \
 } \
 } \
 assert(nodep->node == node); \
 pathp--; \
 if (pathp->node != node) { \
 /* Swap node with its successor. */ \
 bool tred = rbtn_red_get(a_type, a_field, pathp->node); \
 rbtn_color_set(a_type, a_field, pathp->node, \
 rbtn_red_get(a_type, a_field, node)); \
 rbtn_left_set(a_type, a_field, pathp->node, \
 rbtn_left_get(a_type, a_field, node)); \
 /* If node's successor is its right child, the following code */\
 /* will do the wrong thing for the right child pointer. */\
 /* However, it doesn't matter, because the pointer will be */\
 /* properly set when the successor is pruned. */\
 rbtn_right_set(a_type, a_field, pathp->node, \
 rbtn_right_get(a_type, a_field, node)); \
 rbtn_color_set(a_type, a_field, node, tred); \
 /* The pruned leaf node's child pointers are never accessed */\
 /* again, so don't bother setting them to nil. */\
 nodep->node = pathp->node; \
 pathp->node = node; \
 if (nodep == path) { \
 rbtree->rbt_root = nodep->node; \
 } else { \
 if (nodep[-1].cmp < 0) { \
 rbtn_left_set(a_type, a_field, nodep[-1].node, \
 nodep->node); \
 } else { \
 rbtn_right_set(a_type, a_field, nodep[-1].node, \
 nodep->node); \
 } \
 } \
 } else { \
 a_type *left = rbtn_left_get(a_type, a_field, node); \
 if (left != &rbtree->rbt_nil) { \
 /* node has no successor, but it has a left child. */\
 /* Splice node out, without losing the left child. */\
 assert(rbtn_red_get(a_type, a_field, node) == false); \
 assert(rbtn_red_get(a_type, a_field, left)); \
 rbtn_black_set(a_type, a_field, left); \
 if (pathp == path) { \
 rbtree->rbt_root = left; \
 } else { \
 if (pathp[-1].cmp < 0) { \
 rbtn_left_set(a_type, a_field, pathp[-1].node, \
 left); \
 } else { \
 rbtn_right_set(a_type, a_field, pathp[-1].node, \
 left); \
 } \
 } \
 return; \
 } else if (pathp == path) { \
 /* The tree only contained one node. */ \
 rbtree->rbt_root = &rbtree->rbt_nil; \
 return; \
 } \
 } \
 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
 /* Prune red node, which requires no fixup. */ \
 assert(pathp[-1].cmp < 0); \
 rbtn_left_set(a_type, a_field, pathp[-1].node, \
 &rbtree->rbt_nil); \
 return; \
 } \
 /* The node to be pruned is black, so unwind until balance is */\
 /* restored. */\
 pathp->node = &rbtree->rbt_nil; \
 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
 assert(pathp->cmp != 0); \
 if (pathp->cmp < 0) { \
 rbtn_left_set(a_type, a_field, pathp->node, \
 pathp[1].node); \
 assert(rbtn_red_get(a_type, a_field, pathp[1].node) \
 == false); \
 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
 a_type *right = rbtn_right_get(a_type, a_field, \
 pathp->node); \
 a_type *rightleft = rbtn_left_get(a_type, a_field, \
 right); \
 a_type *tnode; \
 if (rbtn_red_get(a_type, a_field, rightleft)) { \
 /* In the following diagrams, ||, //, and \\ */\
 /* indicate the path to the removed node. */\
 /* */\
 /* || */\
 /* pathp(r) */\
 /* // \ */\
 /* (b) (b) */\
 /* / */\
 /* (r) */\
 /* */\
 rbtn_black_set(a_type, a_field, pathp->node); \
 rbtn_rotate_right(a_type, a_field, right, tnode); \
 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
 rbtn_rotate_left(a_type, a_field, pathp->node, \
 tnode); \
 } else { \
 /* || */\
 /* pathp(r) */\
 /* // \ */\
 /* (b) (b) */\
 /* / */\
 /* (b) */\
 /* */\
 rbtn_rotate_left(a_type, a_field, pathp->node, \
 tnode); \
 } \
 /* Balance restored, but rotation modified subtree */\
 /* root. */\
 assert((uintptr_t)pathp > (uintptr_t)path); \
 if (pathp[-1].cmp < 0) { \
 rbtn_left_set(a_type, a_field, pathp[-1].node, \
 tnode); \
 } else { \
 rbtn_right_set(a_type, a_field, pathp[-1].node, \
 tnode); \
 } \
 return; \
 } else { \
 a_type *right = rbtn_right_get(a_type, a_field, \
 pathp->node); \
 a_type *rightleft = rbtn_left_get(a_type, a_field, \
 right); \
 if (rbtn_red_get(a_type, a_field, rightleft)) { \
 /* || */\
 /* pathp(b) */\
 /* // \ */\
 /* (b) (b) */\
 /* / */\
 /* (r) */\
 a_type *tnode; \
 rbtn_black_set(a_type, a_field, rightleft); \
 rbtn_rotate_right(a_type, a_field, right, tnode); \
 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
 rbtn_rotate_left(a_type, a_field, pathp->node, \
 tnode); \
 /* Balance restored, but rotation modified */\
 /* subree root, which may actually be the tree */\
 /* root. */\
 if (pathp == path) { \
 /* Set root. */ \
 rbtree->rbt_root = tnode; \
 } else { \
 if (pathp[-1].cmp < 0) { \
 rbtn_left_set(a_type, a_field, \
 pathp[-1].node, tnode); \
 } else { \
 rbtn_right_set(a_type, a_field, \
 pathp[-1].node, tnode); \
 } \
 } \
 return; \
 } else { \
 /* || */\
 /* pathp(b) */\
 /* // \ */\
 /* (b) (b) */\
 /* / */\
 /* (b) */\
 a_type *tnode; \
 rbtn_red_set(a_type, a_field, pathp->node); \
 rbtn_rotate_left(a_type, a_field, pathp->node, \
 tnode); \
 pathp->node = tnode; \
 } \
 } \
 } else { \
 a_type *left; \
 rbtn_right_set(a_type, a_field, pathp->node, \
 pathp[1].node); \
 left = rbtn_left_get(a_type, a_field, pathp->node); \
 if (rbtn_red_get(a_type, a_field, left)) { \
 a_type *tnode; \
 a_type *leftright = rbtn_right_get(a_type, a_field, \
 left); \
 a_type *leftrightleft = rbtn_left_get(a_type, a_field, \
 leftright); \
 if (rbtn_red_get(a_type, a_field, leftrightleft)) { \
 /* || */\
 /* pathp(b) */\
 /* / \\ */\
 /* (r) (b) */\
 /* \ */\
 /* (b) */\
 /* / */\
 /* (r) */\
 a_type *unode; \
 rbtn_black_set(a_type, a_field, leftrightleft); \
 rbtn_rotate_right(a_type, a_field, pathp->node, \
 unode); \
 rbtn_rotate_right(a_type, a_field, pathp->node, \
 tnode); \
 rbtn_right_set(a_type, a_field, unode, tnode); \
 rbtn_rotate_left(a_type, a_field, unode, tnode); \
 } else { \
 /* || */\
 /* pathp(b) */\
 /* / \\ */\
 /* (r) (b) */\
 /* \ */\
 /* (b) */\
 /* / */\
 /* (b) */\
 assert(leftright != &rbtree->rbt_nil); \
 rbtn_red_set(a_type, a_field, leftright); \
 rbtn_rotate_right(a_type, a_field, pathp->node, \
 tnode); \
 rbtn_black_set(a_type, a_field, tnode); \
 } \
 /* Balance restored, but rotation modified subtree */\
 /* root, which may actually be the tree root. */\
 if (pathp == path) { \
 /* Set root. */ \
 rbtree->rbt_root = tnode; \
 } else { \
 if (pathp[-1].cmp < 0) { \
 rbtn_left_set(a_type, a_field, pathp[-1].node, \
 tnode); \
 } else { \
 rbtn_right_set(a_type, a_field, pathp[-1].node, \
 tnode); \
 } \
 } \
 return; \
 } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \
 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
 if (rbtn_red_get(a_type, a_field, leftleft)) { \
 /* || */\
 /* pathp(r) */\
 /* / \\ */\
 /* (b) (b) */\
 /* / */\
 /* (r) */\
 a_type *tnode; \
 rbtn_black_set(a_type, a_field, pathp->node); \
 rbtn_red_set(a_type, a_field, left); \
 rbtn_black_set(a_type, a_field, leftleft); \
 rbtn_rotate_right(a_type, a_field, pathp->node, \
 tnode); \
 /* Balance restored, but rotation modified */\
 /* subtree root. */\
 assert((uintptr_t)pathp > (uintptr_t)path); \
 if (pathp[-1].cmp < 0) { \
 rbtn_left_set(a_type, a_field, pathp[-1].node, \
 tnode); \
 } else { \
 rbtn_right_set(a_type, a_field, pathp[-1].node, \
 tnode); \
 } \
 return; \
 } else { \
 /* || */\
 /* pathp(r) */\
 /* / \\ */\
 /* (b) (b) */\
 /* / */\
 /* (b) */\
 rbtn_red_set(a_type, a_field, left); \
 rbtn_black_set(a_type, a_field, pathp->node); \
 /* Balance restored. */ \
 return; \
 } \
 } else { \
 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
 if (rbtn_red_get(a_type, a_field, leftleft)) { \
 /* || */\
 /* pathp(b) */\
 /* / \\ */\
 /* (b) (b) */\
 /* / */\
 /* (r) */\
 a_type *tnode; \
 rbtn_black_set(a_type, a_field, leftleft); \
 rbtn_rotate_right(a_type, a_field, pathp->node, \
 tnode); \
 /* Balance restored, but rotation modified */\
 /* subtree root, which may actually be the tree */\
 /* root. */\
 if (pathp == path) { \
 /* Set root. */ \
 rbtree->rbt_root = tnode; \
 } else { \
 if (pathp[-1].cmp < 0) { \
 rbtn_left_set(a_type, a_field, \
 pathp[-1].node, tnode); \
 } else { \
 rbtn_right_set(a_type, a_field, \
 pathp[-1].node, tnode); \
 } \
 } \
 return; \
 } else { \
 /* || */\
 /* pathp(b) */\
 /* / \\ */\
 /* (b) (b) */\
 /* / */\
 /* (b) */\
 rbtn_red_set(a_type, a_field, left); \
 } \
 } \
 } \
 } \
 /* Set root. */ \
 rbtree->rbt_root = path->node; \
 assert(rbtn_red_get(a_type, a_field, rbtree->rbt_root) == false); \
} \
a_attr a_type * \
a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \
 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
 if (node == &rbtree->rbt_nil) { \
 return (&rbtree->rbt_nil); \
 } else { \
 a_type *ret; \
 if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \
 a_field, node), cb, arg)) != &rbtree->rbt_nil \
 || (ret = cb(rbtree, node, arg)) != NULL) { \
 return (ret); \
 } \
 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
 a_field, node), cb, arg)); \
 } \
} \
a_attr a_type * \
a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \
 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
 int cmp = a_cmp(start, node); \
 if (cmp < 0) { \
 a_type *ret; \
 if ((ret = a_prefix##iter_start(rbtree, start, \
 rbtn_left_get(a_type, a_field, node), cb, arg)) != \
 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
 return (ret); \
 } \
 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
 a_field, node), cb, arg)); \
 } else if (cmp > 0) { \
 return (a_prefix##iter_start(rbtree, start, \
 rbtn_right_get(a_type, a_field, node), cb, arg)); \
 } else { \
 a_type *ret; \
 if ((ret = cb(rbtree, node, arg)) != NULL) { \
 return (ret); \
 } \
 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
 a_field, node), cb, arg)); \
 } \
} \
a_attr a_type * \
a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
 a_rbt_type *, a_type *, void *), void *arg) { \
 a_type *ret; \
 if (start != NULL) { \
 ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \
 cb, arg); \
 } else { \
 ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\
 } \
 if (ret == &rbtree->rbt_nil) { \
 ret = NULL; \
 } \
 return (ret); \
} \
a_attr a_type * \
a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \
 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
 if (node == &rbtree->rbt_nil) { \
 return (&rbtree->rbt_nil); \
 } else { \
 a_type *ret; \
 if ((ret = a_prefix##reverse_iter_recurse(rbtree, \
 rbtn_right_get(a_type, a_field, node), cb, arg)) != \
 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
 return (ret); \
 } \
 return (a_prefix##reverse_iter_recurse(rbtree, \
 rbtn_left_get(a_type, a_field, node), cb, arg)); \
 } \
} \
a_attr a_type * \
a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \
 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \
 void *arg) { \
 int cmp = a_cmp(start, node); \
 if (cmp > 0) { \
 a_type *ret; \
 if ((ret = a_prefix##reverse_iter_start(rbtree, start, \
 rbtn_right_get(a_type, a_field, node), cb, arg)) != \
 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
 return (ret); \
 } \
 return (a_prefix##reverse_iter_recurse(rbtree, \
 rbtn_left_get(a_type, a_field, node), cb, arg)); \
 } else if (cmp < 0) { \
 return (a_prefix##reverse_iter_start(rbtree, start, \
 rbtn_left_get(a_type, a_field, node), cb, arg)); \
 } else { \
 a_type *ret; \
 if ((ret = cb(rbtree, node, arg)) != NULL) { \
 return (ret); \
 } \
 return (a_prefix##reverse_iter_recurse(rbtree, \
 rbtn_left_get(a_type, a_field, node), cb, arg)); \
 } \
} \
a_attr a_type * \
a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
 a_type *ret; \
 if (start != NULL) { \
 ret = a_prefix##reverse_iter_start(rbtree, start, \
 rbtree->rbt_root, cb, arg); \
 } else { \
 ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \
 cb, arg); \
 } \
 if (ret == &rbtree->rbt_nil) { \
 ret = NULL; \
 } \
 return (ret); \
}

#endif /* RB_H_ */