torture_rbtree.c

sip协议栈

    TEST_1(node); 
    TEST(node->value, i);
    TEST(nodes[i], node); 
  }

  node = node_find(tree, 0);

  for (i = 0; i < N; i++) {
    TEST_1(node); TEST(node->value, i);
    node = redblack_succ(node);
  }
  TEST_1(node == NULL);

  for (i = 0; i < N; i++) {
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  for (i = 0; i < N; i++) {
    node = node_find(tree, i);
    TEST_1(node); TEST(node->value, i);
    redblack_remove(&tree, node);
    TEST_1(node->parent == NULL && 
	   node->left == NULL && 
	   node->right == NULL); 
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

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

  for (i = 0; i < N; i++) {
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  for (i = 0; i < N; i++) {
    redblack_remove(&tree, nodes[i]);
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

  for (i = 0; i < N; i++) {
    int sn = (i * 57) % N;
    o = (void *)-1;
    TEST(nodes[sn]->inserted, 0);
    TEST(redblack_insert(&tree, nodes[sn], &o), 0); 
    nodes[sn]->inserted = 1;
    TEST(o, NULL);
    TEST_1(redblack_height(tree) <= 2 * log2ceil(i + 1 + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->inserted, 1);
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  for (i = 0; i < N; i++) {
    int sn = (i * 23) % N;	/* 23 is relative prime to N */
    TEST(nodes[sn]->inserted, 1);
    redblack_remove(&tree, nodes[sn]);
    nodes[sn]->inserted = 0;
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

  for (i = 0; i < N; i++) {
    int sn = (i * 517) % N;	/* relative prime to N */
    o = (void *)-1;
    TEST(nodes[sn]->inserted, 0);
    TEST(redblack_insert(&tree, nodes[sn], &o), 0); 
    nodes[sn]->inserted = 1;
    TEST(o, NULL);
    TEST_1(redblack_height(tree) <= 2 * log2ceil(i + 1 + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->inserted, 1);
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  for (i = 0; i < N; i++) {
    int sn = (i * 497) % N;	/* relative prime to N */
    TEST(nodes[sn]->inserted, 1);
    redblack_remove(&tree, nodes[sn]);
    nodes[sn]->inserted = 0;
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

  for (i = 0; i < N; i++) {
    int sn = (i * 1957) % N;	/* relative prime to N */
    o = (void *)-1;
    TEST(nodes[sn]->inserted, 0);
    TEST(redblack_insert(&tree, nodes[sn], &o), 0); 
    nodes[sn]->inserted = 1;
    TEST(o, NULL);
    TEST_1(redblack_height(tree) <= 2 * log2ceil(i + 1 + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->inserted, 1);
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  for (i = 0; i < N; i++) {
    int sn = (i * 1519) % N;	/* relative prime to N */
    TEST(nodes[sn]->inserted, 1);
    redblack_remove(&tree, nodes[sn]);
    nodes[sn]->inserted = 0;
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

  /* Insert small, big, small, big ... */

  for (i = 0; i < N / 2; i++) {
    int sn = N - i - 1;
    TEST(nodes[i]->inserted, 0);
    o = (void *)-1;
    TEST(redblack_insert(&tree, nodes[i], &o), 0); 
    TEST(o, NULL);
    nodes[i]->inserted = 1;

    TEST(nodes[sn]->inserted, 0);
    o = (void *)-1;
    TEST(redblack_insert(&tree, nodes[sn], &o), 0); 
    TEST(o, NULL);
    nodes[sn]->inserted = 1;
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->inserted, 1);
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  for (i = 0; i < N; i++) {
    node = ((i & 1) ? redblack_succ(tree) : redblack_prec(tree));
    if (node == NULL)
      node = tree;
    TEST(node->inserted, 1);
    redblack_remove(&tree, node);
    node->inserted = 0;
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

  /* Insert small, big, small, big ... */

  for (i = 0; i < N / 2; i++) {
    int sn = N - i - 1;
    TEST(nodes[i]->inserted, 0);
    o = (void *)-1;
    TEST(redblack_insert(&tree, nodes[i], &o), 0); 
    TEST(o, NULL);
    nodes[i]->inserted = 1;

    TEST(nodes[sn]->inserted, 0);
    o = (void *)-1;
    TEST(redblack_insert(&tree, nodes[sn], &o), 0); 
    TEST(o, NULL);
    nodes[sn]->inserted = 1;
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->inserted, 1);
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  /* Remove last, first, last, first, ... */
  for (i = 0; i < N; i++) {
    node = ((i & 1) ? redblack_first(tree) : redblack_last(tree));
    TEST_1(node);
    TEST(node->inserted, 1);
    redblack_remove(&tree, node);
    node->inserted = 0;
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

  /* Insert small, big, small, big ... */

  for (i = 0; i < N / 2; i++) {
    int sn = N / 2 + i;
    TEST(nodes[i]->inserted, 0);
    o = (void *)-1;
    TEST(redblack_insert(&tree, nodes[i], &o), 0); 
    TEST(o, NULL);
    nodes[i]->inserted = 1;

    TEST(nodes[sn]->inserted, 0);
    o = (void *)-1;
    TEST(redblack_insert(&tree, nodes[sn], &o), 0); 
    TEST(o, NULL);
    nodes[sn]->inserted = 1;
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->inserted, 1);
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  /* Remove last, first, last, first, ... */
  for (i = 0; i < N; i++) {
    node = ((i & 1) ? redblack_first(tree) : redblack_last(tree));
    TEST_1(node);
    TEST(node->inserted, 1);
    redblack_remove(&tree, node);
    node->inserted = 0;
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

  /* Insert in perfect order ... */
  
  for (j = N / 2; j > 0; j /= 2) {
    for (i = N - j; i >= 0; i -= j) {
      if (nodes[i]->inserted)
	continue;
      o = (void *)-1;
      TEST(redblack_insert(&tree, nodes[i], &o), 0); 
      TEST(o, NULL);
      nodes[i]->inserted = 1;
    }
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->inserted, 1);
    TEST(redblack_succ(nodes[i]), nodes[i + 1]);
    TEST(redblack_prec(nodes[i]), nodes[i - 1]);
  }

  /* Remove such nodes that inserts red uncles into tree */
  for (i = 0; i < N; i++) {
    node = redblack_last(tree);
    for (o = node; o; o = redblack_prec(o)) {
      Node *dad, *granddad, *uncle, *to_be_removed;
      /* We must have a node with black dad, no brother, red granddad and uncle */
      if (!(dad = o->parent) || !dad->black)
	continue;
      if (dad->left && dad->right)
	continue;
      if (!(granddad = dad->parent) || granddad->black)
	continue;
      if (granddad->left == dad)
	uncle = granddad->right;
      else
	uncle = granddad->left;
      if (!uncle || uncle->black)
	continue;
      to_be_removed = redblack_prec(o->parent);
      if (to_be_removed == granddad || to_be_removed == uncle)
	continue;
      if (!to_be_removed->left || !to_be_removed->right)
	continue;
      node = to_be_removed;
      break;
    }
    TEST(node->inserted, 1);
    redblack_remove(&tree, node);
    node->inserted = 0;
    TEST_1(redblack_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST(tree, NULL);

  su_home_check(home);
  su_home_zap(home);

  END();
}

int test_speed(void)
{
  su_home_t *home;
  Node *tree = NULL, *o = NULL;
  Node *node;
  unsigned i;
  int const N = 1000000;

  BEGIN();

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

  for (i = 0; i < N; i++) {
    node = node_new(home, i);
    TEST(redblack_insert(&tree, node, &o), 0);
    TEST(o, NULL);
  }

  TEST_1(redblack_height(tree) <= 2 * log2ceil(i + 1));

  for (i = 0; i < N; i++) {
    node = node_find(tree, i);
    TEST_1(node); TEST(node->value, i);
  }

  node = node_find(tree, 0);
  for (i = 0; i < N; i++) {
    TEST_1(node); TEST(node->value, i);
    node = redblack_succ(node);
  }
  TEST_1(node == NULL);

  su_home_check(home);
  su_home_zap(home);

  END();
}


void usage(void)
{
  fprintf(stderr,
	  "usage: %s [-v]\n",
	  name);
}

int main(int argc, char *argv[])
{
  int retval = 0;
  int i;

  for (i = 1; argv[i]; i++) {
    if (strcmp(argv[i], "-v") == 0)
      tstflags |= tst_verbatim;
    else
      usage();
  }

  retval |= test_insert(); fflush(stdout);
  retval |= test_rotate(); fflush(stdout);
  retval |= test_simple(); fflush(stdout);
  retval |= test_balance(); fflush(stdout);
  retval |= test_speed(); fflush(stdout);

  return retval;
}