From bacchus.pa.dec.com!shlump.nac.dec.com!decuac!haven!uflorida!rex!samsung!uunet!allbery Mon Jul 9 18:48:13 PDT 1990 Article 1704 of comp.sources.misc: Path: bacchus.pa.dec.com!shlump.nac.dec.com!decuac!haven!uflorida!rex!samsung!uunet!allbery From: pugh@cs.UMD.EDU (Bill Pugh) Newsgroups: comp.sources.misc Subject: v13i107: C implementation of skip lists (Comm. of the ACM, June 1990) Message-ID: <96791@uunet.UU.NET> Date: 9 Jul 90 22:54:01 GMT Sender: allbery@uunet.UU.NET Lines: 300 Approved: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc) 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 '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;iheader->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