pugh@cs.UMD.EDU (Bill Pugh) (07/10/90)
Posting-number: Volume 13, Issue 107
Submitted-by: pugh@cs.UMD.EDU (Bill Pugh)
Archive-name: skiplists/part01
The following is a C implementation of skip lists, as described in the
June 1990 issue of the Communications of the ACM. Skip lists are
a simple and efficient alternative to balanced trees. A Pascal implementation
is also available from the author or by anonymous ftp from mimsy.cs.umd.edu.
Bill Pugh
pugh@cs.umd.edu
-----
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: skipLists.c
# Wrapped by pugh@cs.umd.edu on Mon Jul 1 20:00:00 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'skipLists.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'skipLists.c'\"
else
echo shar: Extracting \"'skipLists.c'\" \(5876 characters\)
sed "s/^X//" >'skipLists.c' <<'END_OF_FILE'
X/*
X
XExample of Skip List source code for C:
X
XSkip Lists are a probabilistic alternative to balanced trees, as
Xdescribed in the June 1990 issue of CACM and were invented by
XWilliam Pugh in 1987.
X
XThe author can be contacted at pugh@cs.umd.edu
X
XThis file contains source code to implement a dictionary using
Xskip lists and a test driver to test the routines.
X
XA couple of comments about this implementation:
X The routine randomLevel has been hard-coded to generate random
X levels using p=0.25. It can be easily changed.
X
X The insertion routine has been implemented so as to use the
X dirty hack described in the CACM paper: if a random level is
X generated that is more than the current maximum level, the
X current maximum level plus one is used instead.
X
X Levels start at zero and go up to MaxLevel (which is equal to
X (MaxNumberOfLevels-1).
X
XThe compile flag allowDuplicates determines whether or not duplicates
Xare allowed. If defined, duplicates are allowed and act in a FIFO manner.
XIf not defined, an insertion of a value already in the file updates the
Xpreviously existing binding.
X
XBitsInRandom is defined to be the number of bits returned by a call to
Xrandom(). For most all machines with 32-bit integers, this is 31 bits
Xas currently set.
X
XThe routines defined in this file are:
X
X init: defines NIL and initializes the random bit source
X
X newList: returns a new, empty list
X
X freeList(l): deallocates the list l (along with any elements in l)
X
X randomLevel: Returns a random level
X
X insert(l,key,value): inserts the binding (key,value) into l. If
X allowDuplicates is undefined, returns true if key was newly
X inserted into the list, false if key already existed
X
X delete(l,key): deletes any binding of key from the l. Returns
X false if key was not defined.
X
X search(l,key,&value): Searches for key in l and returns true if found.
X If found, the value associated with key is stored in the
X location pointed to by &value
X
X*/
X
X
X#define false 0
X#define true 1
Xtypedef char boolean;
X#define BitsInRandom 31
X
X#define allowDuplicates
X
X#define MaxNumberOfLevels 16
X#define MaxLevel (MaxNumberOfLevels-1)
X#define newNodeOfLevel(l) (node)malloc(sizeof(struct nodeStructure)+(l)*sizeof(node *))
X
Xtypedef int keyType;
Xtypedef int valueType;
X
X#ifdef allowDuplicates
Xboolean delete(), search();
Xvoid insert();
X#else
Xboolean insert(), delete(), search();
X#endif
X
Xtypedef struct nodeStructure *node;
X
Xtypedef struct nodeStructure{
X keyType key;
X valueType value;
X node forward[1]; /* variable sized array of forward pointers */
X };
X
Xtypedef struct listStructure{
X int level; /* Maximum level of the list
X (1 more than the number of levels in the list) */
X struct nodeStructure * header; /* pointer to header */
X } * list;
X
Xnode NIL;
X
Xint randomsLeft;
Xint randomBits;
X
Xinit() {
X NIL = newNodeOfLevel(0);
X NIL->key = 0x7fffffff;
X randomBits = random();
X randomsLeft = BitsInRandom/2;
X};
X
Xlist newList() {
X list l;
X int i;
X
X l = (list)malloc(sizeof(struct listStructure));
X l->level = 0;
X l->header = newNodeOfLevel(MaxNumberOfLevels);
X for(i=0;i<MaxNumberOfLevels;i++) l->header->forward[i] = NIL;
X return(l);
X };
X
XfreeList(l)
X list l;
X {
X register node p,q;
X p = l->header;
X do {
X q = p->forward[0];
X free(p);
X p = q; }
X while (p!=NIL);
X free(l);
X };
X
Xint randomLevel()
X {register int level = 0;
X register int b;
X do {
X b = randomBits&3;
X if (!b) level++;
X randomBits>>=2;
X if (--randomsLeft == 0) {
X randomBits = random();
X randomsLeft = BitsInRandom/2;
X };
X } while (!b);
X return(level>MaxLevel ? MaxLevel : level);
X };
X
X#ifdef allowDuplicates
Xvoid insert(l,key,value)
X#else
Xboolean insert(l,key,value)
X#endif
X
Xregister list l;
Xregister keyType key;
Xregister valueType value;
X {
X register int k;
X node update[MaxNumberOfLevels];
X register node p,q;
X
X p = l->header;
X k = l->level;
X do {
X while (q = p->forward[k], q->key < key) p = q;
X update[k] = p;
X } while(--k>=0);
X
X#ifndef allowDuplicates
X if (q->key == key) {
X q->value = value;
X return(false);
X };
X#endif
X
X k = randomLevel();
X if (k>l->level) {
X k = ++l->level;
X update[k] = l->header;
X };
X q = newNodeOfLevel(k);
X q->key = key;
X q->value = value;
X do {
X p = update[k];
X q->forward[k] = p->forward[k];
X p->forward[k] = q;
X } while(--k>=0);
X#ifndef allowDuplicates
X return(true);
X#endif
X }
X
Xboolean delete(l,key)
Xregister list l;
Xregister keyType key;
X {
X register int k,m;
X node update[MaxNumberOfLevels];
X register node p,q;
X
X p = l->header;
X k = m = l->level;
X do {
X while (q = p->forward[k], q->key < key) p = q;
X update[k] = p;
X } while(--k>=0);
X
X if (q->key == key) {
X for(k=0; k<=m && (p=update[k])->forward[k] == q; k++)
X p->forward[k] = q->forward[k];
X free(q);
X while( l->header->forward[m] == NIL && m > 0 )
X m--;
X l->level = m;
X return(true);
X }
X else return(false);
X }
X
Xboolean search(l,key,valuePointer)
Xregister list l;
Xregister keyType key;
XvalueType * valuePointer;
X {
X register int k;
X register node p,q;
X p = l->header;
X k = l->level;
X do while (q = p->forward[k], q->key < key) p = q;
X while (--k>=0);
X if (q->key != key) return(false);
X *valuePointer = q->value;
X return(true);
X };
X
X#define sampleSize 65536
Xmain() {
X list l;
X register int i,k;
X keyType keys[sampleSize];
X valueType v;
X
X init();
X
X l= newList();
X
X for(k=0;k<sampleSize;k++) {
X keys[k]=random();
X insert(l,keys[k],keys[k]);
X };
X
X
X for(i=0;i<4;i++) {
X for(k=0;k<sampleSize;k++) {
X if (!search(l,keys[k],&v)) printf("error in search #%d,#%d\n",i,k);
X if (v != keys[k]) printf("search returned wrong value\n");
X };
X for(k=0;k<sampleSize;k++) {
X if (! delete(l,keys[k])) printf("error in delete\n");
X keys[k] = random();
X insert(l,keys[k],keys[k]);
X };
X };
X
X freeList(l);
X
X };
END_OF_FILE
if test 5876 -ne `wc -c <'skipLists.c'`; then
echo shar: \"'skipLists.c'\" unpacked with wrong size!
fi
fi
echo shar: End of shell archive
exit 0