libtree test

test.c

#define _XOPEN_SOURCE
#include <libtree.h>
#include <search.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

#define NITEMS 1024
#define progress_mask ((1<<5) -1)
#define item_type unsigned
#define item_type_max UINT_MAX
#define count_type int

static item_type data_table[NITEMS];
static item_type data_copy[NITEMS];
static count_type ndata = 0;

#define min(a,b) (((a)<(b))?(a):(b))

static count_type _table_find_position(item_type item) {
  count_type high = ndata;
  count_type low = 0;
  count_type dif;
  if (!ndata) return 0;
  if (data_table[0] >= item) return 0;
  for(;;) {
    if (low + 1 == high) return high;
    if ((high < ndata) && (data_table[high] == item)) return high;
    while (dif = (high-low)/2 , (dif > 0) && (data_table[low+dif] < item ))
      low += dif;
    if (data_table[low] == item) return low;
    while (dif = (high-low)/2 , (dif > 0) && (data_table[high-dif] >= item ))
      high -= dif;
  }
}

static count_type table_find(item_type item) {
  count_type pos = _table_find_position(item);
  if ((data_table[pos] == item) && (pos < ndata)) return pos;
  return -1;
}

static void _table_push(count_type pos) {
  if (pos < ndata)
    memmove(data_table+pos+1, data_table+pos, (ndata-pos) * sizeof(item_type));
}

static void _table_pop(count_type pos) {
  if (pos < ndata - 1)
    memmove(data_table+pos, data_table+pos+1, (ndata-pos-1) * sizeof(item_type));
}

static void table_insert(item_type item) {
  count_type pos = _table_find_position(item);
  _table_push(pos);
  assert((pos == ndata) || (data_table[pos] != item));
  data_table[pos] = item;
  ndata ++;
}

static void table_delete(item_type item) {
  count_type pos = _table_find_position(item);
  assert((pos < ndata) && (data_table[pos] == item));
  _table_pop(pos);
  ndata --;
}

static item_type genitem(void) {
  item_type item = drand48() * item_type_max;
  while (table_find(item) >= 0)
    item =  drand48() * item_type_max;
  return item;
}

static item_type randitem(void) {
  return data_table[(count_type)(drand48() * ndata)];
}

static struct avltree avl;
static struct rbtree rb;
static struct bstree bs;
static struct splaytree splay;

static struct avl_data {
  struct avltree_node node;
  item_type key;
} avl_data[NITEMS+1];

static struct rb_data {
  struct rbtree_node node;
  item_type key;
} rb_data[NITEMS+1];

static struct bs_data {
  struct bstree_node node;
  item_type key;
} bs_data[NITEMS+1];

static struct splay_data {
  struct splaytree_node node;
  item_type key;
} splay_data[NITEMS+1];

static int cmp_avl(const struct avltree_node *a, const struct avltree_node *b)
{
  struct avl_data *p = avltree_container_of(a, struct avl_data, node);
  struct avl_data *q = avltree_container_of(b, struct avl_data, node);
  return (p->key < q->key)? -1 : (p->key > q->key) ? 1 : 0 ;
}

static int cmp_rb(const struct rbtree_node *a, const struct rbtree_node *b)
{
  struct rb_data *p = rbtree_container_of(a, struct rb_data, node);
  struct rb_data *q = rbtree_container_of(b, struct rb_data, node);
  return (p->key < q->key)? -1 : (p->key > q->key) ? 1 : 0 ;
}

static int cmp_bs(const struct bstree_node *a, const struct bstree_node *b)
{
  struct bs_data *p = bstree_container_of(a, struct bs_data, node);
  struct bs_data *q = bstree_container_of(b, struct bs_data, node);
  return (p->key < q->key)? -1 : (p->key > q->key) ? 1 : 0 ;
  }

static int cmp_splay(const struct splaytree_node *a, const struct splaytree_node *b)
{
  struct splay_data *p = splaytree_container_of(a, struct splay_data, node);
  struct splay_data *q = splaytree_container_of(b, struct splay_data, node);
  return (p->key < q->key)? -1 : (p->key > q->key) ? 1 : 0 ;
}

static void insert(item_type item) {
#ifdef verbose
  fprintf(stderr," <- %11u\n", item);
#endif
  data_copy[ndata] = item;
  avl_data[ndata].key = item;
  avltree_insert(&(avl_data[ndata].node), &avl);
  rb_data[ndata].key = item;
  rbtree_insert(&(rb_data[ndata].node), &rb);
  bs_data[ndata].key = item;
  bstree_insert(&(bs_data[ndata].node), &bs);
  splay_data[ndata].key = item;
  splaytree_insert(&(splay_data[ndata].node), &splay);
  table_insert(item);
}

static void delete(item_type item) {
#ifdef verbose
  fprintf(stderr," -> %11u\n", item);
#endif
  table_delete(item);
  struct avltree_node *avl_node;
  struct rbtree_node *rb_node;
  struct bstree_node *bs_node;
  struct splaytree_node *splay_node;
  avl_data[NITEMS].key = item;
  avl_node = avltree_lookup(&(avl_data[NITEMS].node), &avl);
  assert(avl_node);
  avltree_remove(avl_node, &avl);
  rb_data[NITEMS].key = item;
  rb_node = rbtree_lookup(&(rb_data[NITEMS].node), &rb);
  assert(rb_node);
  rbtree_remove(rb_node, &rb);
  bs_data[NITEMS].key = item;
  bs_node = bstree_lookup(&(bs_data[NITEMS].node), &bs);
  assert(bs_node);
  bstree_remove(bs_node, &bs);
  splay_data[NITEMS].key = item;
  splay_node = splaytree_lookup(&(splay_data[NITEMS].node), &splay);
  assert(splay_node);
  splaytree_remove(splay_node, &splay);
}

static void awalk(void) {
  count_type i;
  for ( i=1; i<ndata; i++)
    assert(data_table[i-1]<data_table[i]);
}
#ifndef verbose
#define test_tree_item(type) assert(type##tree_container_of(type##_node, struct type##_data, node)->key == data_table[i])
#else
static void printu(void) {
  item_type i;
  fprintf(stderr, "inserted data_table:\n");
  for (i=0; i < ndata; i++) {
    fprintf(stderr, "%15u", data_copy[i]);
  }
  putc('\n', stderr);
}
static const char * avl_name = "avl";
static const char * rb_name = "rb";
static const char * bs_name = "bs";
static const char * splay_name = "splay";
#define test_tree_item(type) if (type##tree_container_of(type##_node, struct type##_data, node)->key != data_table[i]) \
fprintf(stderr, "\n%s tree: item %i (%u) != %u\n", type##_name, i, type##tree_container_of(type##_node, struct type##_data, node)->key, data_table[i]),printu(),abort()
#endif

static void walk(void) {
  struct avltree_node *avl_node = avltree_first(&avl);
  struct rbtree_node *rb_node = rbtree_first(&rb);
  struct bstree_node *bs_node = bstree_first(&bs);
  struct splaytree_node *splay_node = splaytree_first(&splay);
  item_type i;
#ifdef verbose
  for (i=0; i < ndata; i++) {
    fprintf(stderr, "%15u", data_table[i]);
  }
#endif
  for (i=0; ndata && (i < ndata-1); i++) {
    test_tree_item(avl);
    test_tree_item(rb);
    test_tree_item(bs);
    test_tree_item(splay);
    avl_node = avltree_next(avl_node);
    rb_node = rbtree_next(rb_node);
    bs_node = bstree_next(bs_node);
    splay_node = splaytree_next(splay_node);
  }
  if (ndata > 0) {
    test_tree_item(avl);
    test_tree_item(rb);
    test_tree_item(bs);
    test_tree_item(splay);
    assert(avl_node == avltree_last(&avl));
    assert(rb_node == rbtree_last(&rb));
    assert(bs_node == bstree_last(&bs));
    assert(splay_node == splaytree_last(&splay));
  }
}

void bsort_data_copy(void)
{
  count_type pos = 1;
  while (pos < ndata) {
    if (data_copy[pos-1] > data_copy[pos]) {
      count_type pos2 = pos;
      while ((pos2>0) && (data_copy[pos2] < data_copy[pos2-1])) {
        item_type tmp;
        tmp = data_copy[pos2];
        data_copy[pos2] = data_copy[pos2-1];
        data_copy[pos2-1] = tmp;
        pos2--;
      }
    }
    pos++;
    if (!(pos & progress_mask))  putc('.', stderr);
  }
  putc('\n', stderr);
}

int main (int argc, char ** argv) {
  count_type i;
  srand48(0xdeadbeef);
  fprintf(stderr, "\nins  ");
  for ( i=0; i<NITEMS; i++) {
    item_type item = genitem();
    data_copy[i] = item;
    table_insert(item);
    awalk();
    if (! (i & progress_mask)) putc('.', stderr);
  }
  fprintf(stderr, "\nfind ");
  for ( i=0; i<NITEMS; i++) {
    if (i) assert(data_table[i-1] < data_table[i]);
    assert(table_find(data_copy[i])>=0);
    if (! (i & progress_mask)) putc('.', stderr);
  }
  fprintf(stderr, "\nsort ");
  bsort_data_copy();
  assert(memcmp(data_table, data_copy, sizeof(data_copy)) == 0);
  fprintf(stderr, "del  ");
  for (i=0; i<NITEMS; i++) {
    table_delete(randitem());
    awalk();
    if (! (i & progress_mask)) putc('.', stderr);
  }
  fprintf(stderr, "\nins t");
  assert(ndata == 0);
  srand48(0xdeadbeef);
  avltree_init(&avl, cmp_avl, 0);
  rbtree_init(&rb, cmp_rb, 0);
  bstree_init(&bs, cmp_bs, 0);
  splaytree_init(&splay, cmp_splay, 0);
  for ( i=0; i<NITEMS; i++) {
    insert(genitem());
    walk();
#ifndef verbose
    if (! (i & progress_mask)) putc('.', stderr);
#endif
  }
  fprintf(stderr, "\ndel t");
  for (i=0; i<NITEMS; i++) {
    delete(randitem());
    walk();
    if (! (i & progress_mask)) putc('.', stderr);
  }
  putc('\n', stderr);
  return 0;
}