Listing 4 (sltest.c)

/* sltest.c */

#define SLTEST 1
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
#include "skiplist.h"

/* globals */

int listsize;   /* size of our test list */
int maxlevel = MAXLEVEL;
int partition;
int *emptr; /* dynamic array of list elements */
int nnodes; /* count of nodes allocated */
long ctotals;   /* total number of comparisons */
int comps;  /* temporary counter */
int mincomps;
int maxcomps;
#define COMPMAX 80  /* width of screen */
int compary[COMPMAX] = { 0 };   /* for graph routine */
int overflow = 0;
int levels[MAXLEVEL] = { 0 };
jmp_buf errbuf; /* short circuit when out of memory */
NODE *testlist;
int orderflag;  /* non-zero for random insertions */
#define SL_RAND_MAX 32767

int intcmp(a, b)    /* test comparison routine */
KEYTYPE a, b;
{
   comps += 1; /* track length of search path */
   if(a < b)
      return(-1);
   else if(a == b)
      return(0);
   else
      return(1);
}

main(argc, argv)
int argc;
char *argv[];
{
   if(argc < 6)
      usage();
   if((listsize = atoi(argv[i])) < 1)
      usage();
   if(listsize > SL_RAND_MAX)
   {
      listsize = SL_RAND_MAX;
      printf("listsize reduced to %d\n", SL_RAND_MAX);
   }
   if((maxlevel = atoi(argv[2])) < 1)
      usage();
   if(maxlevel > MAXLEVEL)
   {
      maxlevel = MAXLEVEL;
      printf("maxlevel reduced to %d\n", MAXLEVEL);
   }
   if((partition = atoi(argv[3])) < 1)
      || (partition >= maxlevel))
   {
      usage();
   }
   slsrand((unsigned) atoi(argv[4]));
   orderflag = atoi(argv[5]);

   list_init();
   list_build();
   list_test();
   list_stats();
   exit(EXIT_SUCCESS);
}

usage() /* describe command line errors */
{
   printf("\nUsage:\t");
   printf("sltest <size> <maxlevel> <partition> <seed> <flag>\n");
   printf("\t<size> of test list (>= 1)\n");
   printf("\t<maxlevel> max number of pointers per node (>= 1)\n");
   printf("\t<partition> (>= 1 && < maxlevel [= %d])\n", maxlevel);
   printf("\t<seed> for the random number generator\n");
   printf("\t<flag> 0 for in-order insertions, otherwise random");
   exit(EXIT_FAILURE);
}

list_init()
{
   if((emptr = (int *) calloc(listsize, sizeof(int)))
      == NULL)
   {
      nomem();
   }
   if((testlist = newlist()) == NIL)
      nomem();
}

nomem()
{
   printf("Not enough memory for a list of size %u\n",
      (unsigned)listsize);
   exit(EXIT_FAILURE);
}

list_build()
{
   unsigned slrand();
   unsigned i;

   if(setjmp(errbuf))
      listsize = nnodes;  /* largest possible */
   else if(orderflag == 0)
   {
      for(nnodes = 0, i = 1; i <= listsize; )
         insert(testlist, i++);
   }
   else
   {
      for(nnodes = 0; nnodes < listsize; )
         insert(testlist, slrand());
   }
}

list_test()
{
   int i;

   ctotals = 0L;
   mincomps = listsize;
   maxcomps = 0;
   for(i = 0, comps = 0; i < listsize; ++i, comps = 0)
   {
      search(testlist, emptr[i]);
      ctotals += (long) comps;
      if(comps < mincomps)
         mincomps = comps;
      else if(comps > maxcomps)
         maxcomps = comps;
      if(comps < COMPMAX)
         compary[comps] += 1;
      else
         overflow += 1;  /* won't fit on screen */
   }
}

/* for computing behavior of balanced trees */
unsigned treelevels[] = {
   1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
   11, 12, 13, 14, 15, 16 };
unsigned powersof2[] = {
   1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
   4096, 8192, 16384, (SL_RAND_MAX + 1) };
int depth;
long accumulator;

list_stats()    /*  print out statistics */
{
   int i;
   int scale;
   int temp;
   int cmax;

   printf("\nskiplist size = %d", listsize);
   printf("\npointers per level = ");
   for(i = 0; i < maxlevel; i += 1)
      printf("%d ", levels[i]);
   printf("\ncomparisons per search: ");
   printf("mean = %.3f, minimum = %d, maximum = %d\n",
      ((float)ctotals) / ((float)listsize),
      mincomps, maxcomps);
   if(overflow != 0)  /*  graph won't fit on screen */
      printf("distribution of comparisons overflows buffer\n");
   else
   {
      cmax = 0;
      for(i = mincomps; i <= maxcomps; i += 1)
      {
         if(compary[i] > cmax)
            cmax = compary[i];
      }
      scale = cmax / 10;
      if(scale == 0)  /* watch out for cmax < 10!! */
         scale = 1;
      temp = cmax % 10;
      if((temp / scale) > 5)
         scale += 1;
      for(temp = cmax; temp >= 0; temp -= scale)
      {
         if(temp <= scale)   /* last pass through */
            if(scale > 1)   /* make sure we */
                temp = 1;   /* print all */
         for(i = mincomps;i <= maxcomps; i += 1)
         {
            if(compary[i] /temp)
                printf("*");
            else
                printf(" ");
         }
         printf("\n");
      }
      printf("distribution from minimum through maximum:");
      printf(" scale = %d:1\n", scale);
   }
   for(i = 0; (powersof2[i] - 1) < listsize; i += 1)
      ;
   depth = i--;    /* maximum for perfectly balanced tree */
   accumulator = ((long) treelevels[i])
      * ((listsize - powersof2[i--]) + 1);
   white(i >= 0)
   {
      accumulator += (long) (treelevels[i]
         * powersof2[i--]);
   }
   printf("for perfect trees: ");
   printf("mean = %.3f, minimum = 1, maximum = %d/n",
      (((float)accumulator) / ((float)listsize)), depth);
   printf("for degenerate trees: ");
   printf("mean = %.3f, minimum = 1, maximum = %d\n",
      ((float) (listsize + 1) / 2), listsize);
}

/* EOF */