rbtree.h

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

/*
 * This file is part of the Sofia-SIP package
 *
 * Copyright (C) 2005 Nokia Corporation.
 *
 * Contact: Pekka Pessi <[e-mail]>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA
 *
 */

#ifndef RBTREE_H
/** Defined when <sofia-sip/rbtree.h> has been included. */
#define RBTREE_H 

/**@file sofia-sip/rbtree.h
 *
 * Red-black tree.
 *
 * This file contain a red-black-tree template for C. The red-black-tree is
 * a balanced binary tree containing structures as nodes. 
 *
 * The prototypes for red-black-tree functions are declared with macro
 * RBTREE_PROTOS(). The implementation is instantiated with macro
 * RBTREE_BODIES().
 *
 * When a entry with new identical key is added to the tree, it can be
 * either @e inserted (replacing other node with same key value) or @e
 * appended.
 * 
 * Example code can be found from <rbtree_test.c>.
 * 
 * @author Pekka Pessi <[e-mail]>.
 *
 * @date Created: Tue Sep  7 19:45:11 EEST 2004 ppessi
 *
 */

#if DOCUMENTATION_ONLY
/** Type used for rbtree nodes. */
typedef struct node Type;
#endif

  /*               x                c
   *              / \              / \
   * Convert     a   c    into    x   d
   *                / \          / \
   *               b   d        a   b
   */

#define RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent)	\
su_inline \
void prefix ## _left_rotate(Type **top, Type *x)   \
{						   \
  Type *c = right(x), *dad = parent(x); assert(c); \
  						   \
  if ((right(x) = left(c)))			   \
    parent(right(x)) = x;			   \
						   \
  if (!(parent(c) = dad))			   \
    *top = c;					   \
  else if (left(dad) == x)			   \
    left(dad) = c;				   \
  else						   \
    assert(right(dad) == x), right(dad) = c;	   \
						   \
  left(c) = x;					   \
  parent(x) = c;				   \
} \
extern int const prefix##_dummy 

  /*               x                c
   *              / \              / \
   * Convert     c   f    into    a   x
   *            / \                  / \
   *           a   d                d   f
   */

#define RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent)	\
su_inline \
void prefix ## _right_rotate(Type **top, Type *x)	\
{							\
  Type *c = left(x), *dad = parent(x); assert(c);	\
							\
  if ((left(x) = right(c)))				\
    parent(left(x)) = x;				\
							\
  if (!(parent(c) = dad))				\
    *top = c;						\
  else if (right(dad) == x)				\
    right(dad) = c;					\
  else							\
    assert(left(dad) == x), left(dad) = c;		\
							\
  right(c) = x;						\
  parent(x) = c;					\
} \
extern int const prefix##_dummy

#define RBTREE_BALANCE_INSERT1(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK)				\
su_inline								\
void prefix ## _balance_insert(Type **top, Type *node)			\
{									\
  Type *dad, *uncle, *granddad;						\
} \
extern int const prefix##_dummy


/* Balance Red-Black binary tree after inserting node @a n.
 *
 * The function red_black_balance_insert() balances a red-black tree after
 * insertion.
 *
 * RED(node) - set node as red
 */
#define RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK)				\
su_inline								\
void prefix ## _balance_insert(Type **top, Type *node)			\
{									\
  Type *dad, *uncle, *granddad;						\
									\
  SET_RED(node);							\
									\
  for (dad = parent(node); node != *top && IS_RED(dad); dad = parent(node)) { \
    /* Repeat until we are parent or we have a black dad */		\
    granddad = parent(dad); assert(granddad);				\
    if (dad == left(granddad)) {					\
      uncle = right(granddad);						\
      if (IS_RED(uncle)) {						\
	SET_BLACK(dad); SET_BLACK(uncle); SET_RED(granddad);		\
	node = granddad;						\
      } else {								\
	if (node == right(dad)) {					\
	  prefix##_left_rotate(top, node = dad);			\
	  dad = parent(node); assert(dad);				\
	  granddad = parent(dad); assert(granddad);			\
	}								\
	SET_BLACK(dad);							\
	SET_RED(granddad);						\
	prefix##_right_rotate(top, granddad);				\
      }									\
    } else { assert(dad == right(granddad));				\
      uncle = left(granddad);						\
      if (IS_RED(uncle)) {						\
	SET_BLACK(dad); SET_BLACK(uncle); SET_RED(granddad);		\
	node = granddad;						\
      } else {								\
	if (node == left(dad)) {					\
	  prefix##_right_rotate(top, node = dad);			\
	  dad = parent(node); assert(dad);				\
	  granddad = parent(dad); assert(granddad);			\
	}								\
	SET_BLACK(dad);							\
	SET_RED(granddad);						\
	prefix##_left_rotate(top, granddad);				\
      }									\
    }									\
  }									\
									\
  assert(*top);								\
									\
  SET_BLACK((*top));							\
} \
extern int const prefix##_dummy

#define RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent,	\
			      IS_RED, SET_RED, IS_BLACK, SET_BLACK,	\
                              COPY_COLOR)				\
su_inline								\
void prefix##_balance_delete(Type **top, Type *node)			\
{									\
  Type *dad, *brother;							\
									\
  for (dad = parent(node); node != *top && IS_RED(dad); dad = parent(node)) { \
    if (node == left(dad)) {						\
      brother = right(dad);						\
									\
      if (!brother) {							\
	node = dad;							\
	continue;							\
      }									\
									\
      assert(IS_BLACK(brother));					\
									\
      if (IS_BLACK(left(brother)) && IS_BLACK(right(brother))) {	\
	SET_RED(brother);						\
	node = dad;							\
	continue;							\
      }									\
									\
      if (IS_BLACK(right(brother))) {					\
	SET_RED(brother);						\
	SET_BLACK(left(brother));					\
	prefix##_right_rotate(top, brother);				\
	brother = right(dad);						\
      }									\
									\
      COPY_COLOR(brother, dad);						\
      SET_BLACK(dad);							\
      if (right(brother))						\
	SET_BLACK(right(brother));					\
      prefix##_left_rotate(top, dad);					\
      node = *top;							\
      break;								\
    } else {								\
      assert(node == right(dad));					\
									\
      brother = left(dad);						\
									\
      if (!brother) {							\
	node = dad;							\
	continue;							\
      }									\
									\
      assert(IS_BLACK(brother));					\
									\
      if (IS_BLACK(left(brother)) && IS_BLACK(right(brother))) {	\
	SET_RED(brother);						\
	node = dad;							\
	continue;							\
      }									\
									\
      if (IS_BLACK(left(brother))) {					\
	SET_BLACK(right(brother));					\
	SET_RED(brother);						\
	prefix##_left_rotate(top, brother);				\
	brother = left(dad);						\
      }									\
									\
      COPY_COLOR(brother, parent(node));				\
      SET_BLACK(parent(node));						\
      if (left(brother))						\
	SET_BLACK(left(brother));					\
      prefix##_right_rotate(top, dad);					\
      node = *top;							\
      break;								\
    }									\
  }									\
									\
  SET_BLACK(node);							\
}  \
extern int const prefix##_dummy

#if DOCUMENTATION_ONLY
/**Insert a @a node into the @a tree.
 *
 * @param tree pointer to the root of the tree
 * @param node pointer to node to be inserted
 * @param return_old return value parameter for matching node 
 *                   already in the @a tree
 *
 * @retval 0 if node was inserted
 * @retval -1 if there already was an matching node 
 *            and return_old is NULL.
 */
int rbtree_insert(Type **tree, Type *node, Type **return_old);
#endif

/* Insert node into tree. */
#define RBTREE_INSERT(SCOPE, prefix, Type, left, right, parent,		\
		      IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,	\
		      CMP, REMOVE, INSERT)				\
SCOPE									\
int prefix ## _insert(Type **const tree,				\
	 	      Type * const node,				\
		      Type **return_old)				\
{									\
  Type *old, *dad, **slot;						\
									\
  if (tree == NULL || node == NULL) return -1;				\
									\
  for (slot = tree, old = *slot, dad = NULL; old; old = *slot) {	\
    int result = CMP(node, old);					\
    if (result < 0)							\
      dad = old, slot = &(left(old));					\
    else if (result > 0)						\
      dad = old, slot = &(right(old));					\
    else								\
      break;								\
  }									\
									\
  if (old == node)							\
    old = NULL;								\
  else if (old) {							\
    if (!return_old) return -1;						\
									\
    if ((left(node) = left(old)))					\
      parent(left(node)) = node;					\
    if ((right(node) = right(old)))					\
      parent(right(node)) = node;					\
									\
    if (!(parent(node) = parent(old)))					\
      *tree = node;							\
    else if (left(parent(node)) == old)					\
      left(parent(node)) = node;					\
    else assert(right(parent(node)) == old),				\
      right(parent(node)) = node;					\
									\
    COPY_COLOR(node, old);						\
									\
    REMOVE(old);							\
									\
  } else {								\
    *slot = node;							\
    parent(node) = dad;							\
									\
    if (tree != slot) {							\
      prefix##_balance_insert(tree, node);				\
    } else {								\
      SET_BLACK(node);							\
    }									\
  }									\
									\
  INSERT(node);								\
									\
  if (return_old)							\
    *return_old = old;							\
									\
  return 0;								\
}  \
extern int const prefix##_dummy

#if DOCUMENTATION_ONLY
/** Append @a a node into the @a tree.