Logo Search packages:      
Sourcecode: sofia-sip version File versions  Download package

rbtree.h

Go to the documentation of this file.
/*
 * This file is part of the Sofia-SIP package
 *
 * Copyright (C) 2005 Nokia Corporation.
 *
 * Contact: Pekka Pessi <pekka.pessi@nokia.com>
 *
 * 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 <Pekka.Pessi@nokia.com>.
 *
 * @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)     \
static 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)    \
static 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)                       \
static 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)                        \
static 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)                   \
static 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.
 *
 * @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., static inline)
 * @param prefix function prefix (e.g., rbtree)
 * @param Type node type
 *
 * @par Example
 * @code
 * RBTREE_PROTOS(static inline, rbtree, struct node);
 * @endcode
 */
00598 #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., static 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(static 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, \
00650                   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) */

Generated by  Doxygen 1.6.0   Back to index