torture_rbtree.c

sip协议栈

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

/**
 * @file torture_rbtree.c
 * @brief Test red-black tree
 *
 * @author Pekka Pessi <[e-mail]>
 *
 * @date Created: Wed Mar 10 17:05:23 2004 ppessi
 *
 */

#include "config.h"

#include <stddef.h>
#include <string.h>
#include <assert.h>
#include <errno.h>

#include "sofia-sip/rbtree.h"

typedef struct node Node;

struct node {
  Node *left, *right, *parent;
  int black;
  int value;
  int inserted;
};

int tstflags;

#define TSTFLAGS tstflags

#include <stdio.h>
#include <sofia-sip/tstdef.h>

char const *name = "torture_rbtree";

/* Define accessor macros */
#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) ((void)0)
#define REMOVE(node) ((node)->left = (node)->right = (node)->parent = NULL)

#if 0
RBTREE_PROTOS(static, prefix, Node);

RBTREE_LEFT_ROTATE(prefix, Node, LEFT, RIGHT, PARENT); 
RBTREE_RIGHT_ROTATE(prefix, Node, LEFT, RIGHT, PARENT); 

RBTREE_BALANCE_INSERT(prefix, Node, LEFT, RIGHT, PARENT, 
		      IS_RED, SET_RED, IS_BLACK, SET_BLACK); 

RBTREE_BALANCE_DELETE(prefix, Node, LEFT, RIGHT, PARENT, 
		      IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR); 

RBTREE_INSERT(static, prefix, Node, LEFT, RIGHT, PARENT, 
	      IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, 
	      CMP, REMOVE, INSERT);				  

RBTREE_REMOVE(static, prefix, Node, LEFT, RIGHT, PARENT, 
	      IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, 
	      REMOVE, INSERT); 

RBTREE_SUCC(static, prefix, Node, LEFT, RIGHT, PARENT);	

RBTREE_PREC(static, prefix, Node, LEFT, RIGHT, PARENT);	

RBTREE_FIRST(static, prefix, Node, LEFT, RIGHT, PARENT);	

RBTREE_LAST(static, prefix, Node, LEFT, RIGHT, PARENT);	

RBTREE_HEIGHT(static, prefix, Node, LEFT, RIGHT, PARENT);

#endif

RBTREE_PROTOS(static inline, redblack, Node);

RBTREE_BODIES(static inline, redblack, Node, LEFT, RIGHT, PARENT,
	      IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR,
	      CMP, INSERT, REMOVE);

#include <sofia-sip/su_alloc.h>

static
Node *node_new(su_home_t *home, int value)
{
  Node *n = su_zalloc(home, sizeof (*n));
  
  n->value = value;

  return n;
}

/** ceil of log2 */
unsigned log2ceil(unsigned k)
{
  unsigned result = 0;

#if 0
  if (k > (1 << 32))
    result += 32, k = (k >> 32) + ((k & ((1 << 32) - 1)) != 0);
#endif
  if (k > (1 << 16)) 
    result += 16, k = (k >> 16) + ((k & ((1 << 16) - 1)) != 0);
  if (k > (1 << 8)) 
    result += 8, k = (k >> 8) + ((k & ((1 << 8) - 1)) != 0);
  if (k > (1 << 4))
    result += 4, k = (k >> 4) + ((k & 15) != 0);
  if (k > (1 << 2))
    result += 2, k = (k >> 2) + ((k & 3) != 0);
  if (k > (1 << 1))
    result += 1, k = (k >> 1) + (k & 1);
  if (k > 1)
    result += 1;
  
  return result;
}

static
Node *node_find(Node *tree, int value)
{
  while (tree) {
    if (tree->value == value)
      break;
    else if (tree->value < value)
      tree = tree->right;
    else
      tree = tree->left;
  }
   
  return tree;
}

/** Check consistency */
static
int redblack_check(Node const *n)
{
  Node const *l, *r;

  if (!n)
    return 1;

  l = n->left, r = n->right;

  if (n->black || ((!l || l->black) && (!r || r->black)))
    return (!l || redblack_check(l)) && (!r || redblack_check(r));
  else
    return 0;
}

int test_insert(void)
{
  su_home_t *home;
  Node *tree = NULL, *o, *old;
  Node *one, *three, *five, *six, *seven;

  BEGIN();

  home = su_home_clone(NULL, sizeof(*home)); TEST_1(home);
  one = node_new(home, 1);
  three = node_new(home, 3);
  five = node_new(home, 5);
  six = node_new(home, 6);
  seven = node_new(home, 7);

  TEST_1(one); 
  TEST_1(three);
  TEST_1(five);
  TEST_1(six);
  TEST_1(seven);

  /* Check single node */
  TEST(redblack_insert(&tree, five, &o), 0); TEST(o, NULL);
  TEST(tree, five);
  TEST(five->left, NULL); TEST(five->right, NULL);
  TEST(five->parent, NULL); TEST(five->black, 1);

  /* Check after another node: 
   *
   *         5b
   *        / 
   *       3r
   */
  TEST(redblack_insert(&tree, three, &o), 0); TEST(o, NULL);
  TEST(tree->left, three); TEST(tree->black, 1);
  TEST(three->left, NULL); TEST(three->right, NULL);
  TEST(three->parent, tree); TEST(three->black, 0); 

  /* Check third node
   *         5b
   *        / \
   *       3r  7r
   */
  TEST(redblack_insert(&tree, seven, &o), 0); TEST(o, NULL);
  TEST(tree->right, seven); TEST(tree->black, 1);
  TEST(seven->left, NULL); TEST(seven->right, NULL);
  TEST(seven->parent, tree); TEST(seven->black, 0); 

  /* Check after fourth node:
   *         5b
   *        / \
   *       3b  7b
   *      /
   *     1r  
   */
  TEST(redblack_insert(&tree, one, &o), 0); TEST(o, NULL);
  TEST(tree->left->left, one); 
  TEST(tree->black, 1); 
  TEST(tree->left->black, 1); TEST(tree->right->black, 1);
  TEST(one->left, NULL); TEST(one->right, NULL);
  TEST(one->parent, tree->left); TEST(one->black, 0); 

  /* Checks that we got after fifth node:
   *         5b
   *        / \
   *       3b  7b
   *      /   /
   *     1r  6r
   */
  TEST(redblack_insert(&tree, six, &o), 0); TEST(o, NULL);
  TEST(tree, five); TEST(five->black, 1);
  TEST(tree->left, three); TEST(three->black, 1);
  TEST(tree->left->left, one); TEST(one->black, 0);
  TEST(tree->right, seven); TEST(seven->black, 1);
  TEST(tree->right->left, six); TEST(six->black, 0);

  /* Insert five second time */
  old = five;
  five = node_new(home, 5);
  TEST(redblack_insert(&tree, five, &o), 0); TEST(o, old);
  TEST(tree, five); TEST(five->black, 1);
  TEST(tree->left, three); TEST(three->black, 1);
  TEST(three->parent, five);
  TEST(tree->left->left, one); TEST(one->black, 0);
  TEST(tree->right, seven); TEST(seven->black, 1);
  TEST(seven->parent, five);
  TEST(tree->right->left, six); TEST(six->black, 0);

  su_home_check(home);
  su_home_zap(home);

  END();
}

int test_rotate(void)
{
  su_home_t *home;
  Node *tree = NULL;
  Node *x, *y, *o;

  BEGIN();

  home = su_home_clone(NULL, sizeof(*home)); TEST_1(home);

  x = node_new(home, 1);
  y = node_new(home, 2);

  TEST_1(x);
  TEST_1(y); 

  /*
   *              x                   y               x
   * Checks that   \  transforms to  /   and back to   \
   *                y               x                   y
   */
  TEST(redblack_insert(&tree, x, &o), 0); TEST(o, NULL);
  TEST(redblack_insert(&tree, y, &o), 0); TEST(o, NULL);

  TEST(tree, x); TEST(x->right, y);
  redblack_left_rotate(&tree, x);
  TEST(tree, y); TEST(y->left, x);
  redblack_right_rotate(&tree, y);
  TEST(tree, x); TEST(x->right, y);

  su_home_check(home);
  su_home_zap(home);

  END();
}

int test_simple(void)
{
  su_home_t *home;
  Node *tree = NULL, *o;
  int i;
  Node *um, *um103, *um497, *um995;

  BEGIN();

  home = su_home_clone(NULL, sizeof(*home)); TEST_1(home);

  for (i = 3; i < 1000; i += 3) {
    um = node_new(home, i); TEST_1(um);
    o = (void *)-1; TEST(redblack_insert(&tree, um, &o), 0); TEST(o, NULL);
  }

  um103 = node_new(home, 103); TEST_1(um103);
  um497 = node_new(home, 497); TEST_1(um497);
  um995 = node_new(home, 995); TEST_1(um995);

  o = (void *)-1; TEST(redblack_insert(&tree, um995, &o), 0); TEST(o, NULL); 
  o = (void *)-1; TEST(redblack_insert(&tree, um497, &o), 0); TEST(o, NULL); 
  o = (void *)-1; TEST(redblack_insert(&tree, um103, &o), 0); TEST(o, NULL);

  um = node_find(tree, 103); TEST(um, um103);
  um = node_find(tree, 497); TEST(um, um497);
  um = node_find(tree, 995); TEST(um, um995);
  um = node_find(tree, 994); TEST(um, NULL);
  um = node_find(tree, 1); TEST(um, NULL);

  su_home_check(home);
  su_home_zap(home);

  END();
}

int test_balance(void)
{
  su_home_t *home;
  Node *tree = NULL, *o = NULL;
  Node *node, **nodes;
  int i, j;
  int const N = 1000;

  BEGIN();

  home = su_home_clone(NULL, sizeof(*home)); TEST_1(home);
  nodes = su_zalloc(home, (N + 2) * (sizeof *nodes)); TEST_1(nodes);
  nodes++;

  for (i = 0; i < N; i++) {
    nodes[i] = node = node_new(home, i); TEST_1(node);
    TEST(redblack_insert(&tree, node, &o), 0);
    TEST(o, NULL);
    TEST_1(redblack_height(tree) <= 2 * log2ceil(i + 1 + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    node = node_find(tree, i);