#ifndef __GSK_RBTREE_MACROS_H_
#define __GSK_RBTREE_MACROS_H_

/* Macros for construction of a red-black tree.
 * Like our other macro-based data-structures,
 * this doesn't allocate memory, and it doesn't
 * use any helper functions.
 *
 * It supports "invasive" tree structures,
 * for example, you can have nodes that are members
 * of two different trees.
 *
 * A rbtree is a tuple:
 *    top
 *    type*
 *    is_red
 *    set_is_red
 *    parent
 *    left
 *    right
 *    comparator
 * that should be defined by a macro like "GET_TREE()".
 * See tests/test-rbtree-macros.
 *
 * The methods are:
 *   INSERT(tree, node, collision_node) 
 *         Try to insert 'node' into tree.
 *         If an equivalent node exists,
 *         return it in collision_node, and do nothing else.
 *         Otherwise, node is added to the tree
 *         (and collision_node is set to NULL).
 *   REMOVE(tree, node)
 *         Remove a node from the tree.
 *   LOOKUP(tree, node, out)
 *         Find a node in the tree.
 *         Finds the node equivalent with 
 *         'node', and returns it in 'out',
 *         or sets out to NULL if no node exists.
 *   LOOKUP_COMPARATOR(tree, key, key_comparator, out)
 *         Find a node in the tree, based on a key
 *         which may not be in the same format as the node.
 *   FIRST(tree, out)
 *         Set 'out' to the first node in the tree.
 *   LAST(tree, out)
 *         Set 'out' to the last node in the tree.
 *   PREV(tree, cur, out)
 *         Set 'out' to the previous node in the tree before cur.
 *   NEXT(tree, cur, out)
 *         Set 'out' to the next node in the tree after cur.
 *   INFIMUM_COMPARATOR(tree, key, key_comparator, out)
 *         Find the last node in the tree which is before or equal to 'key'.
 *   SUPREMUM_COMPARATOR(tree, key, key_comparator, out)
 *         Find the first node in the tree which is after or equal to 'key'.
 *   INFIMUM(tree, key, out)
 *         Find the last node in the tree which is before or equal to 'key'.
 *   SUPREMUM(tree, key, out)
 *         Find the first node in the tree which is after or equal to 'key'.
 *
 * Occasionally, you may need the "RBCTREE", which has the is_red flag,
 * but also keeps a "count" field at every node telling the size of that subtree.
 * This then has all the methods of RBTREE, plus:
 *   GET_BY_INDEX(tree, n, out)
 *         Return the n-th element in the tree.
 *   GET_BY_INDEX_UNCHECKED(tree, n, out)
 *         Return the n-th element in the tree;
 *         n MUST be less than or equal to the number of
 *         nodes in the tree.
 *   GET_NODE_INDEX(tree, node, n_out)
 *        Sets n_out to the index of node in the tree.
 *   
 * An rbctree is a tuple:
 *    top
 *    type*
 *    is_red
 *    set_is_red
 *    get_count
 *    set_count
 *    parent
 *    left
 *    right
 *    comparator
 */

/*
 * By and large, the red-black tree algorithms used here are from
 * the classic text:
 *     _Introduction to Algorithms_. Thomas Cormen, Charles Leiserson,
 *     and Donald Rivest.  MIT Press.  1990.
 * Citations appears as Algorithms:300 indicating page 300 (for example).
 * The "rbctree" is my name for this idea (daveb),
 * which i suspect has been thought of and implemented before.
 */
#define GSK_RBTREE_INSERT(tree, node, collision_node)                         \
  GSK_RBTREE_INSERT_(tree, node, collision_node)
#define GSK_RBTREE_REMOVE(tree, node)                                         \
  GSK_RBTREE_REMOVE_(tree, node)
#define GSK_RBTREE_LOOKUP(tree, key, out)                                     \
  GSK_RBTREE_LOOKUP_(tree, key, out)
#define GSK_RBTREE_LOOKUP_COMPARATOR(tree, key, key_comparator, out)          \
  GSK_RBTREE_LOOKUP_COMPARATOR_(tree, key, key_comparator, out)

#define GSK_RBTREE_FIRST(tree, out)                                           \
  GSK_RBTREE_FIRST_(tree, out)
#define GSK_RBTREE_LAST(tree, out)                                            \
  GSK_RBTREE_LAST_(tree, out)
#define GSK_RBTREE_NEXT(tree, in, out)                                        \
  GSK_RBTREE_NEXT_(tree, in, out)
#define GSK_RBTREE_PREV(tree, in, out)                                        \
  GSK_RBTREE_PREV_(tree, in, out)

#define GSK_RBTREE_SUPREMUM(tree, key, out)                                   \
  GSK_RBTREE_SUPREMUM_(tree, key, out)
#define GSK_RBTREE_SUPREMUM_COMPARATOR(tree, key, key_comparator, out)        \
  GSK_RBTREE_SUPREMUM_COMPARATOR_(tree, key, key_comparator, out)
#define GSK_RBTREE_INFIMUM(tree, key, out)                                    \
  GSK_RBTREE_INFIMUM_(tree, key, out)
#define GSK_RBTREE_INFIMUM_COMPARATOR(tree, key, key_comparator, out)         \
  GSK_RBTREE_INFIMUM_COMPARATOR_(tree, key, key_comparator, out)

#if 1
#undef G_STMT_START
#define G_STMT_START do
#undef G_STMT_END
#define G_STMT_END while(0)
#endif

#define GSK_RBTREE_INSERT_(top,type,is_red,set_is_red,parent,left,right,comparator, node,collision_node) \
G_STMT_START{                                                                 \
  type _gsk_last = NULL;                                                      \
  type _gsk_at = (top);                                                       \
  gboolean _gsk_last_was_left = FALSE;                                        \
  collision_node = NULL;                                                      \
  while (_gsk_at != NULL)                                                     \
    {                                                                         \
      int _gsk_compare_rv;                                                    \
      _gsk_last = _gsk_at;                                                    \
      comparator(_gsk_at, (node), _gsk_compare_rv);                           \
      if (_gsk_compare_rv > 0)                                                \
        {                                                                     \
          _gsk_last_was_left = TRUE;                                          \
          _gsk_at = _gsk_at->left;                                            \
        }                                                                     \
      else if (_gsk_compare_rv < 0)                                           \
        {                                                                     \
          _gsk_last_was_left = FALSE;                                         \
          _gsk_at = _gsk_at->right;                                           \
        }                                                                     \
      else                                                                    \
        break;                                                                \
   }                                                                          \
  if (_gsk_at != NULL)                                                        \
    {                                                                         \
      /* collision */                                                         \
      collision_node = _gsk_at;                                               \
    }                                                                         \
  else if (_gsk_last == NULL)                                                 \
    {                                                                         \
      /* only node in tree */                                                 \
      top = (node);                                                           \
      set_is_red ((node), 0);                                                 \
      (node)->left = (node)->right = (node)->parent = NULL;                   \
    }                                                                         \
  else                                                                        \
    {                                                                         \
      (node)->parent = _gsk_last;                                             \
      (node)->left = (node)->right = NULL;                                    \
      if (_gsk_last_was_left)                                                 \
        _gsk_last->left = (node);                                             \
      else                                                                    \
        _gsk_last->right = (node);                                            \
                                                                              \
      /* fixup */                                                             \
      _gsk_at = (node);                                                       \
      set_is_red (_gsk_at, 1);                                                \
      while (top != _gsk_at && is_red(_gsk_at->parent))                       \
        {                                                                     \
          if (_gsk_at->parent == _gsk_at->parent->parent->left)               \
            {                                                                 \
              type _gsk_y = _gsk_at->parent->parent->right;                   \
              if (_gsk_y != NULL && is_red (_gsk_y))                          \
                {                                                             \
                  set_is_red (_gsk_at->parent, 0);                            \
                  set_is_red (_gsk_y, 0);                                     \
                  set_is_red (_gsk_at->parent->parent, 1);                    \
                  _gsk_at = _gsk_at->parent->parent;                          \
                }                                                             \
              else                                                            \
                {                                                             \
                  if (_gsk_at == _gsk_at->parent->right)                      \
                    {                                                         \
                      _gsk_at = _gsk_at->parent;                              \
                      GSK_RBTREE_ROTATE_LEFT (top,type,parent,left,right, _gsk_at);\
                    }                                                         \
                  set_is_red(_gsk_at->parent, 0);                             \
                  set_is_red(_gsk_at->parent->parent, 1);                     \
                  GSK_RBTREE_ROTATE_RIGHT (top,type,parent,left,right,        \
                                           _gsk_at->parent->parent);          \
                }                                                             \
            }                                                                 \
          else                                                                \
            {                                                                 \
              type _gsk_y = _gsk_at->parent->parent->left;                    \
              if (_gsk_y != NULL && is_red (_gsk_y))                          \
                {                                                             \
                  set_is_red (_gsk_at->parent, 0);                            \
                  set_is_red (_gsk_y, 0);                                     \
                  set_is_red (_gsk_at->parent->parent, 1);                    \
                  _gsk_at = _gsk_at->parent->parent;                          \
                }                                                             \
              else                                                            \
                {                                                             \
                  if (_gsk_at == _gsk_at->parent->left)                       \
                    {                                                         \
                      _gsk_at = _gsk_at->parent;                              \
                      GSK_RBTREE_ROTATE_RIGHT (top,type,parent,left,right,    \
                                               _gsk_at);                      \
                    }                                                         \
                  set_is_red(_gsk_at->parent, 0);                             \
                  set_is_red(_gsk_at->parent->parent, 1);                     \
                  GSK_RBTREE_ROTATE_LEFT (top,type,parent,left,right,         \
                                          _gsk_at->parent->parent);           \
                }                                                             \
            }                                                                 \
        }                                                                     \
      set_is_red((top), 0);                                                   \
    }                                                                         \
}G_STMT_END

#define GSK_RBTREE_REMOVE_(top,type,is_red,set_is_red,parent,left,right,comparator, node) \
/* Algorithms:273. */                                                         \
G_STMT_START{                                                                 \
  type _gsk_rb_del_z = (node);                                                \
  type _gsk_rb_del_x;                                                         \
  type _gsk_rb_del_y;                                                         \
  type _gsk_rb_del_nullpar = NULL;	/* Used to emulate sentinel nodes */  \
  gboolean _gsk_rb_del_fixup;                                                 \
  if (_gsk_rb_del_z->left == NULL || _gsk_rb_del_z->right == NULL)            \
    _gsk_rb_del_y = _gsk_rb_del_z;                                            \
  else                                                                        \
    {                                                                         \
      GSK_RBTREE_NEXT_ (top,type,is_red,set_is_red,parent,left,right,comparator,\
                        _gsk_rb_del_z, _gsk_rb_del_y);                        \
    }                                                                         \
  _gsk_rb_del_x = _gsk_rb_del_y->left ? _gsk_rb_del_y->left                   \
                                            : _gsk_rb_del_y->right;           \
  if (_gsk_rb_del_x)                                                          \
    _gsk_rb_del_x->parent = _gsk_rb_del_y->parent;                            \
  else                                                                        \
    _gsk_rb_del_nullpar = _gsk_rb_del_y->parent;                              \
  if (!_gsk_rb_del_y->parent)                                                 \
    top = _gsk_rb_del_x;                                                      \
  else                                                                        \
    {                                                                         \
      if (_gsk_rb_del_y == _gsk_rb_del_y->parent->left)                       \
	_gsk_rb_del_y->parent->left = _gsk_rb_del_x;                          \
      else                                                                    \
	_gsk_rb_del_y->parent->right = _gsk_rb_del_x;                         \
    }                                                                         \
  _gsk_rb_del_fixup = !is_red(_gsk_rb_del_y);                                 \
  if (_gsk_rb_del_y != _gsk_rb_del_z)                                         \
    {                                                                         \
      set_is_red(_gsk_rb_del_y, is_red(_gsk_rb_del_z));                       \
      _gsk_rb_del_y->left = _gsk_rb_del_z->left;                              \
      _gsk_rb_del_y->right = _gsk_rb_del_z->right;                            \
      _gsk_rb_del_y->parent = _gsk_rb_del_z->parent;                          \
      if (_gsk_rb_del_y->parent)                                              \
	{                                                                     \
	  if (_gsk_rb_del_y->parent->left == _gsk_rb_del_z)                   \
	    _gsk_rb_del_y->parent->left = _gsk_rb_del_y;                      \
	  else                                                                \
	    _gsk_rb_del_y->parent->right = _gsk_rb_del_y;                     \
	}                                                                     \
      else                                                                    \
	top = _gsk_rb_del_y;                                                  \
                                                                              \
      if (_gsk_rb_del_y->left)                                                \
	_gsk_rb_del_y->left->parent = _gsk_rb_del_y;                          \
      if (_gsk_rb_del_y->right)                                               \
	_gsk_rb_del_y->right->parent = _gsk_rb_del_y;                         \
      if (_gsk_rb_del_nullpar == _gsk_rb_del_z)                               \
	_gsk_rb_del_nullpar = _gsk_rb_del_y;                                  \
    }                                                                         \
  if (_gsk_rb_del_fixup)                                                      \
    {                                                                         \
      /* delete fixup (Algorithms, p 274) */                                  \
      while (_gsk_rb_del_x != top                                             \
         && !(_gsk_rb_del_x != NULL && is_red (_gsk_rb_del_x)))               \
        {                                                                     \
          type _gsk_rb_del_xparent = _gsk_rb_del_x ? _gsk_rb_del_x->parent    \
                                                   : _gsk_rb_del_nullpar;     \
          if (_gsk_rb_del_x == _gsk_rb_del_xparent->left)                     \
            {                                                                 \
              type _gsk_rb_del_w = _gsk_rb_del_xparent->right;                \
              if (_gsk_rb_del_w != NULL && is_red (_gsk_rb_del_w))            \
                {                                                             \
                  set_is_red (_gsk_rb_del_w, 0);                              \
                  set_is_red (_gsk_rb_del_xparent, 1);                        \
                  GSK_RBTREE_ROTATE_LEFT (top,type,parent,left,right,         \
                                          _gsk_rb_del_xparent);               \
                  _gsk_rb_del_w = _gsk_rb_del_xparent->right;                 \
                }                                                             \
              if (!(_gsk_rb_del_w->left && is_red (_gsk_rb_del_w->left))      \
               && !(_gsk_rb_del_w->right && is_red (_gsk_rb_del_w->right)))   \
                {                                                             \
                  set_is_red (_gsk_rb_del_w, 1);                              \
                  _gsk_rb_del_x = _gsk_rb_del_xparent;                        \
                }                                                             \
              else                                                            \
                {                                                             \
                  if (!(_gsk_rb_del_w->right && is_red (_gsk_rb_del_w->right)))\
                    {                                                         \
                      if (_gsk_rb_del_w->left)                                \
                        set_is_red (_gsk_rb_del_w->left, 0);                  \
                      set_is_red (_gsk_rb_del_w, 1);                          \
                      GSK_RBTREE_ROTATE_RIGHT (top,type,parent,left,right,    \
                                               _gsk_rb_del_w);                \
                      _gsk_rb_del_w = _gsk_rb_del_xparent->right;             \
                    }                                                         \
                  set_is_red (_gsk_rb_del_w, is_red (_gsk_rb_del_xparent));   \
                  set_is_red (_gsk_rb_del_xparent, 0);                        \
                  set_is_red (_gsk_rb_del_w->right, 0);                       \
                  GSK_RBTREE_ROTATE_LEFT (top,type,parent,left,right,         \
                                          _gsk_rb_del_xparent);               \
                  _gsk_rb_del_x = top;                                        \
                }                                                             \
            }                                                                 \
          else                                                                \
            {                                                                 \
              type _gsk_rb_del_w = _gsk_rb_del_xparent->left;                 \
              if (_gsk_rb_del_w && is_red (_gsk_rb_del_w))                    \
                {                                                             \
                  set_is_red (_gsk_rb_del_w, 0);                              \
                  set_is_red (_gsk_rb_del_xparent, 1);                        \
                  GSK_RBTREE_ROTATE_RIGHT (top,type,parent,left,right,        \
                                           _gsk_rb_del_xparent);              \
                  _gsk_rb_del_w = _gsk_rb_del_xparent->left;                  \
                }                                                             \
              if (!(_gsk_rb_del_w->right && is_red (_gsk_rb_del_w->right))    \
               && !(_gsk_rb_del_w->left && is_red (_gsk_rb_del_w->left)))     \
                {                                                             \
                  set_is_red (_gsk_rb_del_w, 1);                              \
                  _gsk_rb_del_x = _gsk_rb_del_xparent;                        \
                }                                                             \
              else                                                            \
                {                                                             \
                  if (!(_gsk_rb_del_w->left && is_red (_gsk_rb_del_w->left))) \
                    {                                                         \
                      set_is_red (_gsk_rb_del_w->right, 0);                   \
                      set_is_red (_gsk_rb_del_w, 1);                          \
                      GSK_RBTREE_ROTATE_LEFT (top,type,parent,left,right,     \
                                              _gsk_rb_del_w);                 \
                      _gsk_rb_del_w = _gsk_rb_del_xparent->left;              \
                    }                                                         \
                  set_is_red (_gsk_rb_del_w, is_red (_gsk_rb_del_xparent));   \
                  set_is_red (_gsk_rb_del_xparent, 0);                        \
                  if (_gsk_rb_del_w->left)                                    \
                    set_is_red (_gsk_rb_del_w->left, 0);                      \
                  GSK_RBTREE_ROTATE_RIGHT (top,type,parent,left,right,        \
                                           _gsk_rb_del_xparent);              \
                  _gsk_rb_del_x = top;                                        \
                }                                                             \
            }                                                                 \
        }                                                                     \
      if (_gsk_rb_del_x != NULL)                                              \
        set_is_red(_gsk_rb_del_x, 0);                                         \
    }                                                                         \
  _gsk_rb_del_z->left = NULL;                                                 \
  _gsk_rb_del_z->right = NULL;                                                \
  _gsk_rb_del_z->parent = NULL;                                               \
}G_STMT_END

#define GSK_RBTREE_LOOKUP_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, \
                                      key,key_comparator,out)                 \
G_STMT_START{                                                                 \
  type _gsk_lookup_at = (top);                                                \
  while (_gsk_lookup_at)                                                      \
    {                                                                         \
      int _gsk_compare_rv;                                                    \
      key_comparator(key,_gsk_lookup_at,_gsk_compare_rv);                     \
      if (_gsk_compare_rv < 0)                                                \
        _gsk_lookup_at = _gsk_lookup_at->left;                                \
      else if (_gsk_compare_rv > 0)                                           \
        _gsk_lookup_at = _gsk_lookup_at->right;                               \
      else                                                                    \
        break;                                                                \
    }                                                                         \
  out = _gsk_lookup_at;                                                       \
}G_STMT_END
 /* see comments for 'SUPREMUM'; it is the same with the sense of the comparators
  * and left,right reversed. */
#define GSK_RBTREE_INFIMUM_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, \
                                      key,key_comparator,out)                 \
G_STMT_START{                                                                 \
  type _gsk_lookup_at = (top);                                                \
  type _gsk_lookup_rv = NULL;                                                 \
  while (_gsk_lookup_at)                                                      \
    {                                                                         \
      int _gsk_compare_rv;                                                    \
      key_comparator(key,_gsk_lookup_at,_gsk_compare_rv);                     \
      if (_gsk_compare_rv >= 0)                                               \
        {                                                                     \
          _gsk_lookup_rv = _gsk_lookup_at;                                    \
          _gsk_lookup_at = _gsk_lookup_at->right;                             \
        }                                                                     \
      else                                                                    \
        _gsk_lookup_at = _gsk_lookup_at->left;                                \
    }                                                                         \
  out = _gsk_lookup_rv;                                                       \
}G_STMT_END
/* see introductory comments for a less mathematical
 * definition.  but what 'supremum' computes is:
 * sup(tree, key) = min S(tree,key) or NULL if S(tree, key)
 * is empty, where S(tree,key) = { t | t \in tree && t >= key }.
 * The 'min' is determined by the 'comparator',
 * and the 't >= key' is determined by the 'key_comparator'.
 * But they must be consistent.
 *
 * so, here's a recursive description.  suppose we wish to compute
 * the supremum sup(a, key), where 'a' is the node in the tree shown:
 *                    a       
 *                   / \      
 *                  b   c     
 * Is 'a >= key'?  Then 'a' is in S(a, key),                
 * and hence sup(a,key) exists.  But a "better" supremum,   
 * in terms of being the 'min' in the tree,                 
 * may lie in 'b'. Nothing better may lie in 'c', since it
 * is larger, and we are computing a minimum of S.
 * 
 * But if 'a < key', then 'a' is not in S.  hence 'b' and its children
 * are not in S.  Hence sup(a) = sup(c), including the possibility that
 * sup(C) = NULL.
 *
 * Therefore,
 *    
 *              sup(b)     if 'a >= key', and sub(b) exists,         [case0]
 *     sup(a) = a          if 'a >= key', and sub(b) does not exist, [case1]
 *              sup(c)     if 'a < key' and sub(c) exists,           [case2]
 *              NULL       if 'a < key' and sub(c) does not exist.   [case3]
 *
 * the non-recursive algo follows once you realize that it's just
 * a tree descent, keeping track of the best candidate you've found.
 * TODO: there's got to be a better way to describe it.
 */
#define GSK_RBTREE_SUPREMUM_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, \
                                      key,key_comparator,out)                 \
G_STMT_START{                                                                 \
  type _gsk_lookup_at = (top);                                                \
  type _gsk_lookup_rv = NULL;                                                 \
  while (_gsk_lookup_at)                                                      \
    {                                                                         \
      int _gsk_compare_rv;                                                    \
      key_comparator(key,_gsk_lookup_at,_gsk_compare_rv);                     \
      if (_gsk_compare_rv <= 0)                                               \
        {                                                                     \
          _gsk_lookup_rv = _gsk_lookup_at;                                    \
          _gsk_lookup_at = _gsk_lookup_at->left;                              \
        }                                                                     \
      else                                                                    \
        _gsk_lookup_at = _gsk_lookup_at->right;                               \
    }                                                                         \
  out = _gsk_lookup_rv;                                                       \
}G_STMT_END
#define GSK_RBTREE_LOOKUP_(top,type,is_red,set_is_red,parent,left,right,comparator, key,out) \
  GSK_RBTREE_LOOKUP_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, key,comparator,out)
#define GSK_RBTREE_SUPREMUM_(top,type,is_red,set_is_red,parent,left,right,comparator, key,out) \
  GSK_RBTREE_SUPREMUM_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, key,comparator,out)
#define GSK_RBTREE_INFIMUM_(top,type,is_red,set_is_red,parent,left,right,comparator, key,out) \
  GSK_RBTREE_INFIMUM_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, key,comparator,out)

/* these macros don't need the is_red/set_is_red macros, nor the comparator,
   so omit them, to keep the lines a bit shorter. */
#define GSK_RBTREE_ROTATE_RIGHT(top,type,parent,left,right, node)             \
  GSK_RBTREE_ROTATE_LEFT(top,type,parent,right,left, node)
#define GSK_RBTREE_ROTATE_LEFT(top,type,parent,left,right, node)              \
G_STMT_START{                                                                 \
  type _gsk_rot_x = (node);                                                   \
  type _gsk_rot_y = _gsk_rot_x->right;                                        \
                                                                              \
  _gsk_rot_x->right = _gsk_rot_y->left;                                       \
  if (_gsk_rot_y->left)                                                       \
    _gsk_rot_y->left->parent = _gsk_rot_x;                                    \
  _gsk_rot_y->parent = _gsk_rot_x->parent;                                    \
  if (_gsk_rot_x->parent == NULL)                                             \
    top = _gsk_rot_y;                                                         \
  else if (_gsk_rot_x == _gsk_rot_x->parent->left)                            \
    _gsk_rot_x->parent->left = _gsk_rot_y;                                    \
  else                                                                        \
    _gsk_rot_x->parent->right = _gsk_rot_y;                                   \
  _gsk_rot_y->left = _gsk_rot_x;                                              \
  _gsk_rot_x->parent = _gsk_rot_y;                                            \
}G_STMT_END

/* iteration */
#define GSK_RBTREE_NEXT_(top,type,is_red,set_is_red,parent,left,right,comparator, in, out)  \
G_STMT_START{                                                                 \
  type _gsk_next_at = (in);                                                   \
  g_assert (_gsk_next_at != NULL);                                            \
  if (_gsk_next_at->right != NULL)                                            \
    {                                                                         \
      _gsk_next_at = _gsk_next_at->right;                                     \
      while (_gsk_next_at->left != NULL)                                      \
        _gsk_next_at = _gsk_next_at->left;                                    \
      out = _gsk_next_at;                                                     \
    }                                                                         \
  else                                                                        \
    {                                                                         \
      type _gsk_next_parent = (in)->parent;                                   \
      while (_gsk_next_parent != NULL                                         \
          && _gsk_next_at == _gsk_next_parent->right)                         \
        {                                                                     \
          _gsk_next_at = _gsk_next_parent;                                    \
          _gsk_next_parent = _gsk_next_parent->parent;                        \
        }                                                                     \
      out = _gsk_next_parent;                                                 \
    }                                                                         \
}G_STMT_END

/* prev is just next with left/right child reversed. */
#define GSK_RBTREE_PREV_(top,type,is_red,set_is_red,parent,left,right,comparator, in, out)  \
  GSK_RBTREE_NEXT_(top,type,is_red,set_is_red,parent,right,left,comparator, in, out)

#define GSK_RBTREE_FIRST_(top,type,is_red,set_is_red,parent,left,right,comparator, out)  \
G_STMT_START{                                                                 \
  type _gsk_first_at = (top);                                                 \
  if (_gsk_first_at != NULL)                                                  \
    while (_gsk_first_at->left != NULL)                                       \
      _gsk_first_at = _gsk_first_at->left;                                    \
  out = _gsk_first_at;                                                        \
}G_STMT_END
#define GSK_RBTREE_LAST_(top,type,is_red,set_is_red,parent,left,right,comparator, out)  \
  GSK_RBTREE_FIRST_(top,type,is_red,set_is_red,parent,right,left,comparator, out)

 /* --- RBC-Tree --- */
#define GSK_RBCTREE_INSERT(tree, node, collision_node)                         \
  GSK_RBCTREE_INSERT_(tree, node, collision_node)
#define GSK_RBCTREE_REMOVE(tree, node)                                         \
  GSK_RBCTREE_REMOVE_(tree, node)
#define GSK_RBCTREE_LOOKUP(tree, key, out)                                     \
  GSK_RBCTREE_LOOKUP_(tree, key, out)
#define GSK_RBCTREE_LOOKUP_COMPARATOR(tree, key, key_comparator, out)          \
  GSK_RBCTREE_LOOKUP_COMPARATOR_(tree, key, key_comparator, out)

#define GSK_RBCTREE_FIRST(tree, out)                                           \
  GSK_RBCTREE_FIRST_(tree, out)
#define GSK_RBCTREE_LAST(tree, out)                                            \
  GSK_RBCTREE_LAST_(tree, out)
#define GSK_RBCTREE_NEXT(tree, in, out)                                        \
  GSK_RBCTREE_NEXT_(tree, in, out)
#define GSK_RBCTREE_PREV(tree, in, out)                                        \
  GSK_RBCTREE_PREV_(tree, in, out)

#define GSK_RBCTREE_SUPREMUM(tree, key, out)                                   \
  GSK_RBCTREE_SUPREMUM_(tree, key, out)
#define GSK_RBCTREE_SUPREMUM_COMPARATOR(tree, key, key_comparator, out)        \
  GSK_RBCTREE_SUPREMUM_COMPARATOR_(tree, key, key_comparator, out)
#define GSK_RBCTREE_INFIMUM(tree, key, out)                                    \
  GSK_RBCTREE_INFIMUM_(tree, key, out)
#define GSK_RBCTREE_INFIMUM_COMPARATOR(tree, key, key_comparator, out)         \
  GSK_RBCTREE_INFIMUM_COMPARATOR_(tree, key, key_comparator, out)

#define GSK_RBCTREE_GET_BY_INDEX(tree, index, out)                             \
  GSK_RBCTREE_GET_BY_INDEX_(tree, index, out)
#define GSK_RBCTREE_GET_BY_INDEX_UNCHECKED(tree, index, out)                   \
  GSK_RBCTREE_GET_BY_INDEX_UNCHECKED_(tree, index, out)
#define GSK_RBCTREE_GET_NODE_INDEX(tree, node, index_out)                      \
  GSK_RBCTREE_GET_NODE_INDEX_(tree, node, index_out)

#if 1
#undef G_STMT_START
#define G_STMT_START do
#undef G_STMT_END
#define G_STMT_END while(0)
#endif


#define GSK_RBCTREE_INSERT_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, node,collision_node) \
G_STMT_START{                                                                 \
  type _gsk_last = NULL;                                                      \
  type _gsk_at = (top);                                                       \
  gboolean _gsk_last_was_left = FALSE;                                        \
  collision_node = NULL;                                                      \
  while (_gsk_at != NULL)                                                     \
    {                                                                         \
      int _gsk_compare_rv;                                                    \
      _gsk_last = _gsk_at;                                                    \
      comparator(_gsk_at, (node), _gsk_compare_rv);                           \
      if (_gsk_compare_rv > 0)                                                \
        {                                                                     \
          _gsk_last_was_left = TRUE;                                          \
          _gsk_at = _gsk_at->left;                                            \
        }                                                                     \
      else if (_gsk_compare_rv < 0)                                           \
        {                                                                     \
          _gsk_last_was_left = FALSE;                                         \
          _gsk_at = _gsk_at->right;                                           \
        }                                                                     \
      else                                                                    \
        break;                                                                \
   }                                                                          \
  if (_gsk_at != NULL)                                                        \
    {                                                                         \
      /* collision */                                                         \
      collision_node = _gsk_at;                                               \
    }                                                                         \
  else if (_gsk_last == NULL)                                                 \
    {                                                                         \
      /* only node in tree */                                                 \
      top = (node);                                                           \
      set_is_red ((node), 0);                                                 \
      (node)->left = (node)->right = (node)->parent = NULL;                   \
      set_count ((node), 1);                                                  \
    }                                                                         \
  else                                                                        \
    {                                                                         \
      (node)->parent = _gsk_last;                                             \
      (node)->left = (node)->right = NULL;                                    \
      if (_gsk_last_was_left)                                                 \
        _gsk_last->left = (node);                                             \
      else                                                                    \
        _gsk_last->right = (node);                                            \
                                                                              \
      /* fixup counts */                                                      \
      set_count ((node), 1);                                                  \
      for (_gsk_at = _gsk_last; _gsk_at; _gsk_at = _gsk_at->parent)           \
        {                                                                     \
          guint _gsk_new_count = get_count(_gsk_at) + 1;                      \
          set_count(_gsk_at, _gsk_new_count);                                 \
        }                                                                     \
                                                                              \
      /* fixup */                                                             \
      _gsk_at = (node);                                                       \
      set_is_red (_gsk_at, 1);                                                \
      while (_gsk_at->parent != NULL && is_red(_gsk_at->parent))              \
        {                                                                     \
          if (_gsk_at->parent == _gsk_at->parent->parent->left)               \
            {                                                                 \
              type _gsk_y = _gsk_at->parent->parent->right;                   \
              if (_gsk_y != NULL && is_red (_gsk_y))                          \
                {                                                             \
                  set_is_red (_gsk_at->parent, 0);                            \
                  set_is_red (_gsk_y, 0);                                     \
                  set_is_red (_gsk_at->parent->parent, 1);                    \
                  _gsk_at = _gsk_at->parent->parent;                          \
                }                                                             \
              else                                                            \
                {                                                             \
                  if (_gsk_at == _gsk_at->parent->right)                      \
                    {                                                         \
                      _gsk_at = _gsk_at->parent;                              \
                      GSK_RBCTREE_ROTATE_LEFT (top,type,parent,left,right,get_count,set_count, _gsk_at);\
                    }                                                         \
                  set_is_red(_gsk_at->parent, 0);                             \
                  set_is_red(_gsk_at->parent->parent, 1);                     \
                  GSK_RBCTREE_ROTATE_RIGHT (top,type,parent,left,right,get_count,set_count,\
                                         _gsk_at->parent->parent);            \
                }                                                             \
            }                                                                 \
          else                                                                \
            {                                                                 \
              type _gsk_y = _gsk_at->parent->parent->left;                    \
              if (_gsk_y != NULL && is_red (_gsk_y))                          \
                {                                                             \
                  set_is_red (_gsk_at->parent, 0);                            \
                  set_is_red (_gsk_y, 0);                                     \
                  set_is_red (_gsk_at->parent->parent, 1);                    \
                  _gsk_at = _gsk_at->parent->parent;                          \
                }                                                             \
              else                                                            \
                {                                                             \
                  if (_gsk_at == _gsk_at->parent->left)                       \
                    {                                                         \
                      _gsk_at = _gsk_at->parent;                              \
                      GSK_RBCTREE_ROTATE_RIGHT (top,type,parent,left,right,get_count,set_count,\
                                             _gsk_at);                        \
                    }                                                         \
                  set_is_red(_gsk_at->parent, 0);                             \
                  set_is_red(_gsk_at->parent->parent, 1);                     \
                  GSK_RBCTREE_ROTATE_LEFT (top,type,parent,left,right,get_count,set_count,\
                                          _gsk_at->parent->parent);           \
                }                                                             \
            }                                                                 \
        }                                                                     \
      set_is_red((top), 0);                                                   \
    }                                                                         \
}G_STMT_END

#define GSK_RBCTREE_REMOVE_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, node) \
/* Algorithms:273. */                                                         \
G_STMT_START{                                                                 \
  type _gsk_rb_del_z = (node);                                                \
  type _gsk_rb_del_x;                                                         \
  type _gsk_rb_del_y;                                                         \
  type _gsk_rb_del_nullpar = NULL;	/* Used to emulate sentinel nodes */  \
  gboolean _gsk_rb_del_fixup;                                                 \
  if (_gsk_rb_del_z->left == NULL || _gsk_rb_del_z->right == NULL)            \
    _gsk_rb_del_y = _gsk_rb_del_z;                                            \
  else                                                                        \
    {                                                                         \
      GSK_RBTREE_NEXT_ (top,type,is_red,set_is_red,parent,left,right,comparator,\
                        _gsk_rb_del_z, _gsk_rb_del_y);                        \
    }                                                                         \
  _gsk_rb_del_x = _gsk_rb_del_y->left ? _gsk_rb_del_y->left                   \
                                            : _gsk_rb_del_y->right;           \
  if (_gsk_rb_del_x)                                                          \
    _gsk_rb_del_x->parent = _gsk_rb_del_y->parent;                            \
  else                                                                        \
    _gsk_rb_del_nullpar = _gsk_rb_del_y->parent;                              \
  if (!_gsk_rb_del_y->parent)                                                 \
    top = _gsk_rb_del_x;                                                      \
  else                                                                        \
    {                                                                         \
      if (_gsk_rb_del_y == _gsk_rb_del_y->parent->left)                       \
	_gsk_rb_del_y->parent->left = _gsk_rb_del_x;                          \
      else                                                                    \
	_gsk_rb_del_y->parent->right = _gsk_rb_del_x;                         \
      _GSK_RBCTREE_FIX_COUNT_AND_UP(type,parent,left,right,get_count,set_count, _gsk_rb_del_y->parent);\
    }                                                                         \
  _gsk_rb_del_fixup = !is_red(_gsk_rb_del_y);                                 \
  if (_gsk_rb_del_y != _gsk_rb_del_z)                                         \
    {                                                                         \
      set_is_red(_gsk_rb_del_y, is_red(_gsk_rb_del_z));                       \
      _gsk_rb_del_y->left = _gsk_rb_del_z->left;                              \
      _gsk_rb_del_y->right = _gsk_rb_del_z->right;                            \
      _gsk_rb_del_y->parent = _gsk_rb_del_z->parent;                          \
      if (_gsk_rb_del_y->parent)                                              \
	{                                                                     \
	  if (_gsk_rb_del_y->parent->left == _gsk_rb_del_z)                   \
	    _gsk_rb_del_y->parent->left = _gsk_rb_del_y;                      \
	  else                                                                \
	    _gsk_rb_del_y->parent->right = _gsk_rb_del_y;                     \
	}                                                                     \
      else                                                                    \
        {                                                                     \
          top = _gsk_rb_del_y;                                                \
        }                                                                     \
      /* TODO: look at pictures to see if "_AND_UP" is necessary */           \
      _GSK_RBCTREE_FIX_COUNT_AND_UP(type,parent,left,right,get_count,set_count, _gsk_rb_del_y);\
                                                                              \
      if (_gsk_rb_del_y->left)                                                \
	_gsk_rb_del_y->left->parent = _gsk_rb_del_y;                          \
      if (_gsk_rb_del_y->right)                                               \
	_gsk_rb_del_y->right->parent = _gsk_rb_del_y;                         \
      if (_gsk_rb_del_nullpar == _gsk_rb_del_z)                               \
	_gsk_rb_del_nullpar = _gsk_rb_del_y;                                  \
    }                                                                         \
  if (_gsk_rb_del_fixup)                                                      \
    {                                                                         \
      /* delete fixup (Algorithms, p 274) */                                  \
      while (_gsk_rb_del_x != top                                             \
         && !(_gsk_rb_del_x != NULL && is_red (_gsk_rb_del_x)))               \
        {                                                                     \
          type _gsk_rb_del_xparent = _gsk_rb_del_x ? _gsk_rb_del_x->parent    \
                                                   : _gsk_rb_del_nullpar;     \
          if (_gsk_rb_del_x == _gsk_rb_del_xparent->left)                     \
            {                                                                 \
              type _gsk_rb_del_w = _gsk_rb_del_xparent->right;                \
              if (_gsk_rb_del_w != NULL && is_red (_gsk_rb_del_w))            \
                {                                                             \
                  set_is_red (_gsk_rb_del_w, 0);                              \
                  set_is_red (_gsk_rb_del_xparent, 1);                        \
                  GSK_RBCTREE_ROTATE_LEFT (top,type,parent,left,right,get_count,set_count, \
                                          _gsk_rb_del_xparent);               \
                  _gsk_rb_del_w = _gsk_rb_del_xparent->right;                 \
                }                                                             \
              if (!(_gsk_rb_del_w->left && is_red (_gsk_rb_del_w->left))      \
               && !(_gsk_rb_del_w->right && is_red (_gsk_rb_del_w->right)))   \
                {                                                             \
                  set_is_red (_gsk_rb_del_w, 1);                              \
                  _gsk_rb_del_x = _gsk_rb_del_xparent;                        \
                }                                                             \
              else                                                            \
                {                                                             \
                  if (!(_gsk_rb_del_w->right && is_red (_gsk_rb_del_w->right)))\
                    {                                                         \
                      if (_gsk_rb_del_w->left)                                \
                        set_is_red (_gsk_rb_del_w->left, 0);                  \
                      set_is_red (_gsk_rb_del_w, 1);                          \
                      GSK_RBCTREE_ROTATE_RIGHT (top,type,parent,left,right,get_count,set_count, \
                                               _gsk_rb_del_w);                \
                      _gsk_rb_del_w = _gsk_rb_del_xparent->right;             \
                    }                                                         \
                  set_is_red (_gsk_rb_del_w, is_red (_gsk_rb_del_xparent));   \
                  set_is_red (_gsk_rb_del_xparent, 0);                        \
                  set_is_red (_gsk_rb_del_w->right, 0);                       \
                  GSK_RBCTREE_ROTATE_LEFT (top,type,parent,left,right,get_count,set_count, \
                                          _gsk_rb_del_xparent);               \
                  _gsk_rb_del_x = top;                                        \
                }                                                             \
            }                                                                 \
          else                                                                \
            {                                                                 \
              type _gsk_rb_del_w = _gsk_rb_del_xparent->left;                 \
              if (_gsk_rb_del_w && is_red (_gsk_rb_del_w))                    \
                {                                                             \
                  set_is_red (_gsk_rb_del_w, 0);                              \
                  set_is_red (_gsk_rb_del_xparent, 1);                        \
                  GSK_RBCTREE_ROTATE_RIGHT (top,type,parent,left,right,get_count,set_count, \
                                           _gsk_rb_del_xparent);              \
                  _gsk_rb_del_w = _gsk_rb_del_xparent->left;                  \
                }                                                             \
              if (!(_gsk_rb_del_w->right && is_red (_gsk_rb_del_w->right))    \
               && !(_gsk_rb_del_w->left && is_red (_gsk_rb_del_w->left)))     \
                {                                                             \
                  set_is_red (_gsk_rb_del_w, 1);                              \
                  _gsk_rb_del_x = _gsk_rb_del_xparent;                        \
                }                                                             \
              else                                                            \
                {                                                             \
                  if (!(_gsk_rb_del_w->left && is_red (_gsk_rb_del_w->left))) \
                    {                                                         \
                      set_is_red (_gsk_rb_del_w->right, 0);                   \
                      set_is_red (_gsk_rb_del_w, 1);                          \
                      GSK_RBCTREE_ROTATE_LEFT (top,type,parent,left,right,get_count,set_count, \
                                              _gsk_rb_del_w);                 \
                      _gsk_rb_del_w = _gsk_rb_del_xparent->left;              \
                    }                                                         \
                  set_is_red (_gsk_rb_del_w, is_red (_gsk_rb_del_xparent));   \
                  set_is_red (_gsk_rb_del_xparent, 0);                        \
                  if (_gsk_rb_del_w->left)                                    \
                    set_is_red (_gsk_rb_del_w->left, 0);                      \
                  GSK_RBCTREE_ROTATE_RIGHT (top,type,parent,left,right,get_count,set_count, \
                                           _gsk_rb_del_xparent);              \
                  _gsk_rb_del_x = top;                                        \
                }                                                             \
            }                                                                 \
        }                                                                     \
      if (_gsk_rb_del_x != NULL)                                              \
        set_is_red(_gsk_rb_del_x, 0);                                         \
    }                                                                         \
  _gsk_rb_del_z->left = NULL;                                                 \
  _gsk_rb_del_z->right = NULL;                                                \
  _gsk_rb_del_z->parent = NULL;                                               \
}G_STMT_END

#define GSK_RBCTREE_LOOKUP_COMPARATOR_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, \
                                      key,key_comparator,out)                 \
 GSK_RBTREE_LOOKUP_COMPARATOR_(top,type,is_red,set_count,parent,left,right,comparator, key,key_comparator,out)
#define GSK_RBCTREE_INFIMUM_COMPARATOR_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, \
                                      key,key_comparator,out)                 \
 GSK_RBTREE_INFIMUM_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, key,key_comparator,out)
#define GSK_RBCTREE_SUPREMUM_COMPARATOR_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, \
                                      key,key_comparator,out)                 \
 GSK_RBTREE_SUPREMUM_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, key,key_comparator,out)
#define GSK_RBCTREE_LOOKUP_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, key,out) \
  GSK_RBTREE_LOOKUP_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, key,comparator,out)
#define GSK_RBCTREE_SUPREMUM_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, key,out) \
  GSK_RBTREE_SUPREMUM_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, key,comparator,out)
#define GSK_RBCTREE_INFIMUM_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, key,out) \
  GSK_RBTREE_INFIMUM_COMPARATOR_(top,type,is_red,set_is_red,parent,left,right,comparator, key,comparator,out)
#define GSK_RBCTREE_NEXT_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, in, out)  \
   GSK_RBTREE_NEXT_(top,type,is_red,set_is_red,parent,left,right,comparator, in, out)
#define GSK_RBCTREE_PREV_(top,type,is_red,set_is_red,parent,left,right,comparator, in, out)  \
   GSK_RBTREE_PREV_(top,type,is_red,set_is_red,parent,left,right,comparator, in, out)
#define GSK_RBCTREE_FIRST_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, out)  \
  GSK_RBTREE_FIRST_(top,type,is_red,set_is_red,parent,left,right,comparator, out)
#define GSK_RBCTREE_LAST_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, out)  \
  GSK_RBTREE_LAST_(top,type,is_red,set_is_red,parent,left,right,comparator, out)

#define GSK_RBCTREE_GET_BY_INDEX_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, index,out) \
  G_STMT_START{                                                                \
    if (top == NULL || (index) >= get_count(top))                              \
      out = NULL;                                                              \
    else                                                                       \
      GSK_RBCTREE_GET_BY_INDEX_UNCHECKED_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, index,out);\
  }G_STMT_END
#define GSK_RBCTREE_GET_BY_INDEX_UNCHECKED_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, index,out) \
   G_STMT_START{                                                               \
     type _gsk_at = (top);                                                     \
     guint _gsk_index = (index);                                               \
     for (;;)                                                                  \
       {                                                                       \
         guint _gsk_left_size = _gsk_at->left ? get_count(_gsk_at->left) : 0;  \
         if (_gsk_index < _gsk_left_size)                                      \
           _gsk_at = _gsk_at->left;                                            \
         else if (_gsk_index == _gsk_left_size)                                \
           break;                                                              \
         else                                                                  \
           {                                                                   \
             _gsk_index -= (_gsk_left_size + 1);                               \
             _gsk_at = _gsk_at->right;                                         \
           }                                                                   \
       }                                                                       \
     out = _gsk_at;                                                            \
   }G_STMT_END

#define GSK_RBCTREE_GET_NODE_INDEX_(top,type,is_red,set_is_red,get_count,set_count,parent,left,right,comparator, node,index_out) \
   G_STMT_START{                                                               \
     type _gsk_at = (node);                                                    \
     guint _gsk_rv = _gsk_at->left ? get_count (_gsk_at->left) : 0;            \
     while (_gsk_at->parent != NULL)                                           \
       {                                                                       \
         if (_gsk_at->parent->left == _gsk_at)                                 \
           ;                                                                   \
         else                                                                  \
           {                                                                   \
             if (_gsk_at->parent->left)                                        \
               _gsk_rv += get_count((_gsk_at->parent->left));                  \
             _gsk_rv += 1;                                                     \
           }                                                                   \
         _gsk_at = _gsk_at->parent;                                            \
       }                                                                       \
     index_out = _gsk_rv;                                                      \
   }G_STMT_END

#define GSK_RBCTREE_ROTATE_RIGHT(top,type,parent,left,right,get_count,set_count, node) \
  GSK_RBCTREE_ROTATE_LEFT(top,type,parent,right,left,get_count,set_count, node)
#define GSK_RBCTREE_ROTATE_LEFT(top,type,parent,left,right,get_count,set_count, node)  \
G_STMT_START{                                                                 \
  type _gsk_rot_x = (node);                                                   \
  type _gsk_rot_y = _gsk_rot_x->right;                                        \
                                                                              \
  _gsk_rot_x->right = _gsk_rot_y->left;                                       \
  if (_gsk_rot_y->left)                                                       \
    _gsk_rot_y->left->parent = _gsk_rot_x;                                    \
  _gsk_rot_y->parent = _gsk_rot_x->parent;                                    \
  if (_gsk_rot_x->parent == NULL)                                             \
    top = _gsk_rot_y;                                                         \
  else if (_gsk_rot_x == _gsk_rot_x->parent->left)                            \
    _gsk_rot_x->parent->left = _gsk_rot_y;                                    \
  else                                                                        \
    _gsk_rot_x->parent->right = _gsk_rot_y;                                   \
  _gsk_rot_y->left = _gsk_rot_x;                                              \
  _gsk_rot_x->parent = _gsk_rot_y;                                            \
                                                                              \
  /* fixup counts. */                                                         \
  /* to re-derive this here's what rotate_left(x) does pictorially: */        \
  /*       x                                 y                      */        \
  /*      / \                               / \                     */        \
  /*     a   y     == rotate_left(x) ==>   x   c                    */        \
  /*        / \                           / \                       */        \
  /*       b   c                         a   b                      */        \
  /*                                                                */        \
  /* so:       n0 = get_count(x) (==a+b+c+2)                        */        \
  /*           n1 = get_count(c)   (c may be null)                  */        \
  /*           n2 = n0 - n1 - 1;                                    */        \
  /*           set_count(x, n2)                                     */        \
  /*           set_count(y, n0)                                     */        \
  /*     c is _gsk_rot_y->right at this point                       */        \
  /*                                                                */        \
  /* equivalently:                                                  */        \
  /*      y->count = x->count;                                      */        \
  /*      x->count -= c->count + 1                                  */        \
  {                                                                           \
    guint _gsk_rot_n0 = get_count(_gsk_rot_x);                                \
    guint _gsk_rot_n1 = _gsk_rot_y->right ? get_count(_gsk_rot_y->right) : 0; \
    guint _gsk_rot_n2 = _gsk_rot_n0 - _gsk_rot_n1 - 1;                        \
    set_count (_gsk_rot_x, _gsk_rot_n2);                                      \
    set_count (_gsk_rot_y, _gsk_rot_n0);                                      \
  }                                                                           \
}G_STMT_END

 /* utility: recompute node's count, based on count of its children */
#define _GSK_RBCTREE_FIX_COUNT(type,parent,left,right,get_count,set_count, node)          \
G_STMT_START{                                                                 \
  guint _gsk_fixcount_count = 1;                                              \
  if ((node)->left != NULL)                                                   \
    _gsk_fixcount_count += get_count((node)->left);                           \
  if ((node)->right != NULL)                                                  \
    _gsk_fixcount_count += get_count((node)->right);                          \
  set_count((node), _gsk_fixcount_count);                                     \
}G_STMT_END

 /* utility: recompute node's count, based on count of its children */
#define _GSK_RBCTREE_FIX_COUNT_AND_UP(type,parent,left,right,get_count,set_count, node)   \
G_STMT_START{                                                                 \
  type _tmp_fix_count_up;                                                     \
  for (_tmp_fix_count_up = (node);                                            \
       _tmp_fix_count_up != NULL;                                             \
       _tmp_fix_count_up = _tmp_fix_count_up->parent)                         \
    _GSK_RBCTREE_FIX_COUNT (type,parent,left,right,get_count,set_count, _tmp_fix_count_up);\
}G_STMT_END

#endif
