rbtree.h

Sofia SIP is an open-source SIP User-Agent library, compliant with the IETF RFC3261 specification.

 *
 * @param tree pointer to the root of the tree
 * @param node pointer to node to be appended
 *
 * @retval 0 when successful (always)
 */
int rbtree_append(Type ** tree,
		  Type *  node);
#endif

/* Define function appending a node into the tree */
#define RBTREE_APPEND(SCOPE, prefix, Type, left, right, parent,		\
		      IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,	\
		      CMP, REMOVE, INSERT)				\
SCOPE									\
int prefix ## _append(Type **const tree,				\
	 	      Type * const node)				\
{									\
  Type *old, *dad, **slot;						\
									\
  if (tree == NULL || node == NULL) return -1;				\
									\
  for (slot = tree, old = *slot, dad = NULL; old; old = *slot) {	\
    if (old == node)							\
      return 0;								\
    if (CMP(node, old) < 0)						\
      dad = old, slot = &(left(old));					\
    else								\
      dad = old, slot = &(right(old));					\
  }									\
									\
  *slot = node;								\
  parent(node) = dad;							\
									\
  if (tree != slot) {							\
    prefix##_balance_insert(tree, node);				\
  } else {								\
    SET_BLACK(node);							\
  }									\
									\
  INSERT(node);								\
									\
  return 0;								\
}  \
extern int const prefix##_dummy

#if DOCUMENTATION_ONLY
/** Remove a @a node from the @a tree.
 *
 * @param tree pointer to the root of the tree
 * @param node pointer to node to be appended
 */
void rbtree_remove(Type **tree, Type *node);				
#endif

#define RBTREE_REMOVE(SCOPE, prefix, Type, left, right, parent,		\
		      IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
		      REMOVE, INSERT)					\
SCOPE									\
void prefix##_remove(Type **top, Type *node)				\
{									\
  Type *kid, *dad;							\
  int need_to_balance;							\
									\
  if (top == NULL || node == NULL)					\
    return;								\
									\
  /* Make sure that node is in tree */					\
  for (dad = node; dad; dad = parent(dad))				\
    if (dad == *top)							\
      break;								\
									\
  if (!dad) return;							\
									\
  /* Find a successor node with a free branch */			\
  if (!left(node) || !right(node))					\
    dad = node;								\
  else for (dad = right(node); left(dad); dad = left(dad))		\
    ;									\
  /* Dad has a free branch => kid is dad's only child */		\
  kid = left(dad) ? left(dad) : right(dad);				\
									\
  /* Remove dad from tree */						\
  if (!(parent(dad)))							\
    *top = kid;								\
  else if (left(parent(dad)) == dad)					\
    left(parent(dad)) = kid;						\
  else assert(right(parent(dad)) == dad),				\
    right(parent(dad)) = kid;						\
  if (kid)								\
    parent(kid) = parent(dad);						\
									\
  need_to_balance = kid && IS_BLACK(dad);				\
									\
  /* Put dad in place of node */					\
  if (node != dad) {							\
    if (!(parent(dad) = parent(node)))					\
      *top = dad;							\
    else if (left(parent(dad)) == node)					\
      left(parent(dad)) = dad;						\
    else assert(right(parent(dad)) == node),				\
      right(parent(dad)) = dad;						\
									\
    COPY_COLOR(dad, node);						\
									\
    if ((left(dad) = left(node)))					\
      parent(left(dad)) = dad;						\
									\
    if ((right(dad) = right(node)))					\
      parent(right(dad)) = dad;						\
  }									\
									\
  REMOVE(node);								\
  SET_RED(node);							\
									\
  if (need_to_balance)							\
    prefix##_balance_delete(top, kid);					\
} \
extern int const prefix##_dummy

#if DOCUMENTATION_ONLY
/** Return inorder successor of node @a node.
 *
 * @param node pointer to node
 *
 * @return Pointer to successor, or NULL if @a node was last.
 */
Type *rbtree_succ(Type const *node);
#endif

/* Define function returning inorder successor of node @a node. */
#define RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent)	\
SCOPE Type *prefix##_succ(Type const *node)				\
{									\
  Type const *dad;							\
									\
  if (right(node)) {							\
    for (node = right(node); left(node); node = left(node))		\
      ;									\
    return (Type *)node;						\
  }									\
									\
  for (dad = parent(node); dad && node == right(dad); dad = parent(node)) \
    node = dad;								\
									\
  return (Type *)dad;							\
} \
extern int const prefix##_dummy

#if DOCUMENTATION_ONLY
/** Return inorder precedessor of node @a node.
 *
 * @param node pointer to node
 *
 * @return Pointer to precedessor, or NULL if @a node was first.
 */
Type *rbtree_prec(Type const *node);
#endif

/* Define function returning inorder precedessor of node @a node. */
#define RBTREE_PREC(SCOPE, prefix, Type, left, right, parent)	\
  SCOPE Type *prefix##_prec(Type const *node)				\
{									\
  Type const *dad;							\
									\
  if (left(node)) {							\
    for (node = left(node); right(node); node = right(node))		\
      ;									\
    return (Type *)node;						\
  }									\
									\
  for (dad = parent(node); dad && node == left(dad); dad = parent(node)) \
    node = dad;								\
									\
  return (Type *)dad;							\
} \
extern int const prefix##_dummy

#if DOCUMENTATION_ONLY
/** Return first node in the tree to which @a node belongs to.
 *
 * @param node pointer to node
 *
 * @return Pointer to first node.
 */
Type *rbtree_first(Type const *node);
#endif

/* Define function returning first node in tree @a node. */
#define RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent)	\
SCOPE Type *prefix##_first(Type const *node)    \
{						\
  while (node && left(node))			\
    node = left(node);				\
						\
  return (Type *)node;				\
} \
extern int const prefix##_dummy

#if DOCUMENTATION_ONLY
/** Return last node in the tree to which @a node belongs to.
 *
 * @param node pointer to node
 *
 * @return Pointer to last node.
 */
Type *rbtree_last(Type const *node);
#endif

/* Define function returning last node in tree @a node. */
#define RBTREE_LAST(SCOPE, prefix, Type, left, right, parent)	\
SCOPE Type *prefix##_last(Type const *node)	\
{						\
  while (node && right(node))			\
    node = right(node);				\
						\
  return (Type *)node;				\
} \
extern int const prefix##_dummy

#if DOCUMENTATION_ONLY
/** Return height of the tree below @a node.
 *
 * @param node pointer to node
 *
 * @return Height of the tree.
 */
int rbtree_height(Type const *node);
#endif

/* Define function returning height of the tree from the @a node. */
#define RBTREE_HEIGHT(SCOPE, prefix, Type, getleft, getright, getparent)	\
SCOPE int prefix##_height(Type const *node)			\
{								\
  int left, right;						\
								\
  if (!node)							\
    return 0;							\
								\
  left = getleft(node) ? prefix##_height(getleft(node)) : 0;	\
  right = getright(node) ? prefix##_height(getright(node)) : 0;	\
								\
  if (left > right)						\
    return left + 1;						\
  else								\
    return right + 1;						\
} \
extern int const prefix##_dummy

/** Define prototypes for red-black tree functions. @HIDE 
 *
 * @param SCOPE function scope (e.g., su_inline)
 * @param prefix function prefix (e.g., rbtree)
 * @param Type node type
 *
 * @par Example
 * @code
 * RBTREE_PROTOS(su_inline, rbtree, struct node);
 * @endcode
 */
#define RBTREE_PROTOS(SCOPE, prefix, Type)				\
  SCOPE int prefix ## _insert(Type **, Type *, Type **return_old);	\
  SCOPE int prefix ## _append(Type **, Type *);				\
  SCOPE void prefix ## _remove(Type **, Type *);			\
  SCOPE Type *prefix ## _succ(Type const *);				\
  SCOPE Type *prefix ## _prec(Type const *);				\
  SCOPE Type *prefix ## _first(Type const *);				\
  SCOPE Type *prefix ## _last(Type const *);				\
  SCOPE int prefix ## _height(Type const *)

/** Define bodies for red-black tree functions. @HIDE 
 *
 * @param SCOPE function scope (e.g., su_inline)
 * @param prefix function prefix (e.g., rbtree)
 * @param Type node type
 * @param left accessor of left node 
 * @param right accessor of right node
 * @param parent accessor of parent node
 * @param IS_RED predicate testing if node is red
 * @param SET_RED setter marking node as red
 * @param IS_BLACK predicate testing if node is black
 * @param SET_BLACK setter marking node as black
 * @param COPY_COLOR method copying color from node to another
 * @param CMP method comparing two nodes
 * @param INSERT setter marking node as inserted to the tree
 * @param REMOVE method marking node as removed and possibly deleting node
 * 
 * @par Example
 *
 * @code
 * #define LEFT(node) ((node)->left)
 * #define RIGHT(node) ((node)->right)
 * #define PARENT(node) ((node)->parent)
 * #define SET_RED(node) ((node)->black = 0)
 * #define SET_BLACK(node) ((node)->black = 1)
 * #define CMP(a, b) ((a)->value - (b)->value)
 * #define IS_RED(node) ((node) && (node)->black == 0)
 * #define IS_BLACK(node) (!(node) || (node)->black == 1)
 * #define COPY_COLOR(dst, src) ((dst)->black = (src)->black)
 * #define INSERT(node) ((node)->inserted = 1)
 * #define REMOVE(node) ((node)->left = (node)->right = (node)->parent = NULL, \
 *                       (node)->inserted = 0)
 * 
 * RBTREE_BODIES(su_inline, rbtree, struct node,
 *               LEFT, RIGHT, PARENT,
 *               IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,
 *               CMP, INSERT, REMOVE);
 * @endcode
 */
#define RBTREE_BODIES(SCOPE, prefix, Type,				\
		      left, right, parent,				\
		      IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \
		      CMP, INSERT, REMOVE)				\
  RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent);		\
  RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent);		\
  RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent,		\
			IS_RED, SET_RED, IS_BLACK, SET_BLACK);		\
  RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent,		\
			IS_RED, SET_RED, IS_BLACK, SET_BLACK,		\
			COPY_COLOR);					\
  RBTREE_INSERT(SCOPE, prefix, Type, left, right, parent,		\
		IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,	\
		CMP, REMOVE, INSERT);					\
  RBTREE_APPEND(SCOPE, prefix, Type, left, right, parent,		\
		IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,	\
		CMP, REMOVE, INSERT);					\
  RBTREE_REMOVE(SCOPE, prefix, Type, left, right, parent,		\
		IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,	\
		REMOVE, INSERT);					\
  RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent);		\
  RBTREE_PREC(SCOPE, prefix, Type, left, right, parent);		\
  RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent);		\
  RBTREE_LAST(SCOPE, prefix, Type, left, right, parent);		\
  RBTREE_HEIGHT(SCOPE, prefix, Type, left, right, parent)

#endif /* !define(RBTREE_H) */