rbtree.h

来自「sip协议栈」· C头文件 代码 · 共 536 行 · 第 1/2 页

      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 ((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

/* Append node into 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


/* Remove node. */
#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

/* Functions currently used only by test cases */

/** Return 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

/** Return 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

/** Return 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

/** Return 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

/** Return height of the tree */
#define RBTREE_HEIGHT(SCOPE, prefix, Type, left, right, parent)	\
SCOPE int prefix##_height(Type const *tree)			\
{								\
  int left, right;						\
								\
  if (!tree)							\
    return 0;							\
								\
  left = left(tree) ? prefix##_height(left(tree)) : 0;		\
  right = right(tree) ? prefix##_height(right(tree)) : 0;	\
								\
  if (left > right)						\
    return left + 1;						\
  else								\
    return right + 1;						\
} \
extern int const prefix##_dummy

#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 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) */