Listing 1 (skiplist.h)

/* skiplist.h */

#ifndef MAXLEVEL
#define MAXLEVEL    16  /* must be a constant */
#endif
#ifndef PARTITION
#define PARTITION   4 /* probably always a constant */
#endif

#ifdef SLTEST
int intcmp();
#define KEYTYPE int
#define COMPARE intcmp
#define DMAX    maxlevel    /* the denominator */
#define NMAX    partition   /* the numerator */
#else
#define DMAX    MAXLEVEL
#define NMAX    PARTITION
#endif

struct node {
   union {
      KEYTYPE key;
      int level;
   } korl;
   struct node *pointers[1];
};

#define NODE struct node
#define NIL (NODE *)NULL

#ifndef TRUE
#define TRUE    1
#endif
#ifndef FALSE
#define FALSE   0
#endif

/* declare skiplist.c routines */
NODE *newlist();
NODE *search();
NODE *insert();
int delete();
NODE *newnode();
int randomlevel ();