Category : Files from Magazines
Archive   : JAN94.ZIP
Filename : SKIP.ASC

_SKIP LISTS_
by Bruce Schneier

[LISTING ONE]

/* This file contains source code to implement a dictionary using
skip lists and a test driver to test the routines. A couple of comments
about this implementation: The routine randomLevel has been hard-coded to
generate random levels using p=0.25. It can be easily changed. The insertion
routine has been implemented so as to use the dirty hack described in the CACM
paper: if a random level is generated that is more than the current maximum
level, the current maximum level plus one is used instead. Levels start at
zero and go up to MaxLevel (which is equal to (MaxNumberOfLevels-1).
The compile flag allowDuplicates determines whether or not duplicates
are allowed. If defined, duplicates are allowed and act in a FIFO manner.
If not defined, an insertion of a value already in the file updates the
previously existing binding. BitsInRandom is defined to be the number of bits
returned by a call to random(). For most all machines with 32-bit integers,
this is 31 bits as currently set. The routines defined in this file are:
init: defines NIL and initializes the random bit source
newList: returns a new, empty list
freeList(l): deallocates the list l (along with any elements in l)
randomLevel: Returns a random level
insert(l,key,value): inserts the binding (key,value) into l. If
allowDuplicates is undefined, returns true if key was newly
inserted into the list, false if key already existed
delete(l,key): deletes any binding of key from the l. Returns
false if key was not defined.
search(l,key,&value): Searches for key in l and returns true if found.
If found, the value associated with key is stored in the
location pointed to by &value
*/

#define false 0
#define true 1
typedef char boolean;
#define BitsInRandom 31
#define allowDuplicates
#define MaxNumberOfLevels 16
#define MaxLevel (MaxNumberOfLevels-1)
#define newNodeOfLevel(l) (node)malloc(sizeof(struct
nodeStructure)+(l)*sizeof(node *))

typedef int keyType;
typedef int valueType;

#ifdef allowDuplicates
boolean delete(), search();
void insert();
#else
boolean insert(), delete(), search();
#endif

typedef struct nodeStructure *node;
typedef struct nodeStructure{
keyType key;
valueType value;
node forward[1]; /* variable sized array of forward pointers */
};
typedef struct listStructure{
int level; /* Maximum level of the list
(1 more than the number of levels in the list) */
struct nodeStructure * header; /* pointer to header */
} * list;
node NIL;
int randomsLeft;
int randomBits;
init() {
NIL = newNodeOfLevel(0);
NIL->key = 0x7fffffff;
randomBits = random();
randomsLeft = BitsInRandom/2;
};
list newList() {
list l;
int i;
l = (list)malloc(sizeof(struct listStructure));
l->level = 0;
l->header = newNodeOfLevel(MaxNumberOfLevels);
for(i=0;iheader->forward[i] = NIL;
return(l);
};
freeList(l)
list l;
{
register node p,q;
p = l->header;
do {
q = p->forward[0];
free(p);
p = q; }
while (p!=NIL);
free(l);
};
int randomLevel()
{register int level = 0;
register int b;
do {
b = randomBits&3;
if (!b) level++;
randomBits>>=2;
if (--randomsLeft == 0) {
randomBits = random();
randomsLeft = BitsInRandom/2;
};
} while (!b);
return(level>MaxLevel ? MaxLevel : level);
};
#ifdef allowDuplicates
void insert(l,key,value)
#else
boolean insert(l,key,value)
#endif

register list l;
register keyType key;
register valueType value;
{
register int k;
node update[MaxNumberOfLevels];
register node p,q;
p = l->header;
k = l->level;
do {
while (q = p->forward[k], q->key < key) p = q;
update[k] = p;
} while(--k>=0);
#ifndef allowDuplicates
if (q->key == key) {
q->value = value;
return(false);
};
#endif
k = randomLevel();
if (k>l->level) {
k = ++l->level;
update[k] = l->header;
};
q = newNodeOfLevel(k);
q->key = key;
q->value = value;
do {
p = update[k];
q->forward[k] = p->forward[k];
p->forward[k] = q;
} while(--k>=0);
#ifndef allowDuplicates
return(true);
#endif
}
boolean delete(l,key)
register list l;
register keyType key;
{
register int k,m;
node update[MaxNumberOfLevels];
register node p,q;
p = l->header;
k = m = l->level;
do {
while (q = p->forward[k], q->key < key) p = q;
update[k] = p;
} while(--k>=0);
if (q->key == key) {
for(k=0; k<=m && (p=update[k])->forward[k] == q; k++)
p->forward[k] = q->forward[k];
free(q);
while( l->header->forward[m] == NIL && m > 0 )
m--;
l->level = m;
return(true);
}
else return(false);
}
boolean search(l,key,valuePointer)
register list l;
register keyType key;
valueType * valuePointer;
{
register int k;
register node p,q;
p = l->header;
k = l->level;
do while (q = p->forward[k], q->key < key) p = q;
while (--k>=0);
if (q->key != key) return(false);
*valuePointer = q->value;
return(true);
};
#define sampleSize 65536
main() {
list l;
register int i,k;
keyType keys[sampleSize];
valueType v;
init();
l= newList();
for(k=0;k keys[k]=random();
insert(l,keys[k],keys[k]);
};
for(i=0;i<4;i++) {
for(k=0;k if (!search(l,keys[k],&v)) printf("error in search #%d,#%d\n",i,k);
if (v != keys[k]) printf("search returned wrong value\n");
};
for(k=0;k if (! delete(l,keys[k])) printf("error in delete\n");
keys[k] = random();
insert(l,keys[k],keys[k]);
};
};
freeList(l);
};



=====================================================


(* Example of Skip List source code for Pascal: Skip Lists are a probabilistic
alternative to balanced trees, as described in the June 1990 issue of CACM

and were invented by William Pugh in 1987. This file contains source code to
implement a dictionary using skip lists and a test driver to test the routines.
A couple of comments about this implementation:
The routine randomLevel has been hard-coded to generate random levels using
p=0.25. It can be easily changed. The insertion routine has been implemented
so as to use the dirty hack described in the CACM paper: if a random level is
generated that is more than the current maximum level, the current maximum
level plus one is used instead.
The code, as presented, allows duplicate entries which act in a FIFO manner.
To disallow duplicates, the insert procedure needs to be modified as indicated
in the insert procedure. The library includes an adaptation of the Unix C
random number generator, since the standard Pascal random number generator is
unsuitable. An attempt has been made to make sure that no integer overflow
occurs in the random number generator. However, this could not be tested.
randomBits is defined to be the number of bits returned by a call to random().
For most all machines with 32-bit integers, this is 31 bits as currently set.
The routines defined in this file are:
init: defines terminator and initializes the random bit source
newList: returns a new, empty list
freeList(l): deallocates the list l
randomLevel: Returns a random level
insert(l,key,value): inserts the binding (key,value) into l. If
allowDuplicates is undefined, returns true if key was newly
inserted into the list, false if key already existed
delete(l,key): deletes any binding of key from the l. Returns
false if key was not defined.
search(l,key,value): Searches for key in l and returns true if found.
If found, the value associated with key is stored in value
*)

program test(input,output);
const
sampleSize = 65536;

(* Constants are associated with the random number generator *)
differentRandoms = 1073741824; (* 2^30 *)
randomTableSize = 31; (* size of table used *)

(* constants associated with the routines to procedure random levels *)
ChunkSize = 4; (* ChunkSize = 1/p *)
randomChucksInAWord = 15; (* = log(base ChunkSize) differentRandoms *)
MaxLevel = 16;
type
randomStuff = 0..maxint;
keyType= 0..maxint;
valueType = 0..maxint;
levelNum = 1..MaxLevel;
node = ^nodeRec;
list = ^listRec;
listRec = record
level : integer;
header : node;
end;
nodeRec = record
key: keyType;
value: valueType;
case levelNum of
1: (fwd1: array [1..1] of node;);
2: (fwd2: array [1..2] of node;);
3: (fwd3: array [1..3] of node;);
4: (fwd4: array [1..4] of node;);
5: (fwd5: array [1..5] of node;);
6: (fwd6: array [1..6] of node;);
7: (fwd7: array [1..7] of node;);
8: (fwd8: array [1..8] of node;);
9: (fwd9: array [1..9] of node;);
10: (fwd10: array [1..10] of node;);
11: (fwd11: array [1..11] of node;);
12: (fwd12: array [1..12] of node;);
13: (fwd13: array [1..13] of node;);
14: (fwd14: array [1..14] of node;);
15: (fwd15: array [1..15] of node;);
16: (fwd: array [1..16] of node;)
end;
var randomChunksLeft : integer;
randomBits : randomStuff;
l : list;
i,k : integer;
v : valueType;
keys : array [1..sampleSize] of keyType;
terminator:node;

head,tail : integer;
randomTable : array[1..31] of randomStuff;

function randomNumber: integer;
begin
randomTable[head] := (randomTable[head] + randomTable[tail])
mod differentRandoms;
head := (head mod randomTableSize) + 1;
tail := (tail mod randomTableSize) + 1;
randomNumber := randomTable[head];
end;
procedure initRandom;
begin
head := 4;
tail := 1;
randomTable[1] := 1005175229;
randomTable[2] := 143302914;
randomTable[3] := 1027100827;
randomTable[4] := 879468478;
randomTable[5] := 755253631;
randomTable[6] := 928858961;
randomTable[7] := 331648406;
randomTable[8] := 45248011;
randomTable[9] := 26209743;
randomTable[10] := 433832350;
randomTable[11] := 944843483;
randomTable[12] := 438263339;
randomTable[13] := 813528929;
randomTable[14] := 629457392;
randomTable[15] := 618906479;
randomTable[16] := 573714703;
randomTable[17] := 766270699;
randomTable[18] := 275680090;
randomTable[19] := 436578616;
randomTable[20] := 509842102;
randomTable[21] := 649659208;
randomTable[22] := 891701505;
randomTable[23] := 24441858;
randomTable[24] := 562763940;
randomTable[25] := 980071615;
randomTable[26] := 1011597961;
randomTable[27] := 643279273;
randomTable[28] := 241719451;
randomTable[29] := 157584038;
randomTable[30] := 1069844923;
randomTable[31] := 471560540;
end;
function randomLevel:integer;
var newLevel : integer;
shiftedBits : randomStuff;
done : boolean;
begin
newLevel := 0;
done := false;
repeat
shiftedBits := randomBits div ChunkSize;
done := (shiftedBits * ChunkSize) <> randomBits;
newLevel := newLevel + 1;
randomBits := shiftedBits;
randomChunksLeft := randomChunksLeft -1;
if randomChunksLeft = 0 then
begin
randomBits := randomNumber;
randomChunksLeft := randomChucksInAWord;
end;
until done;
if newLevel > MaxLevel then newLevel := MaxLevel;
randomLevel := newLevel;
end;
procedure init;
begin
new(terminator,1);
terminator^.key := (256*256*256*64-1)*2+1;
randomBits := randomNumber;
randomChunksLeft := randomChucksInAWord;
end;
function newList:list;
var l : list;
i : integer;
begin
new(l);
l^.level := 1;
new(l^.header,MaxLevel);
for i := 1 to MaxLevel do l^.header^.fwd[i] := terminator;
newList := l;
end;
procedure freeList(l:list);
var
k : levelNum;
done : boolean;
p : node;
begin
p := l^.header^.fwd[1];
while (p <> terminator) do begin
k := 1;
done := false;
while not done do begin
l^.header^.fwd[k] := p^.fwd[k];
k := k+1;
if k > l^.level then done := true
else done := l^.header^.fwd[k] <> p;
end;
case k-1 of
1 : dispose(p,1);
2 : dispose(p,2);
3 : dispose(p,3);
4 : dispose(p,4);
5 : dispose(p,5);
6 : dispose(p,6);
7 : dispose(p,7);
8 : dispose(p,8);
9 : dispose(p,9);
10 : dispose(p,10);
11 : dispose(p,11);
12 : dispose(p,12);
13 : dispose(p,13);
14 : dispose(p,14);
15 : dispose(p,15);
16 : dispose(p,16)
end;
p := l^.header^.fwd[1];
end;
dispose(l^.header,MaxLevel);
dispose(l);
end;
procedure insert(l:list;key:keyType;value:valueType);
var
k : levelNum;
update : array[1..MaxLevel] of node;
p,q : node;
begin
p := l^.header;

for k:= l^.level downto 1 do begin
q := p^.fwd[k];
while q^.key < key do begin
p := q;
q := p^.fwd[k];
end;
update[k] := p;
end;
(* The insert routine currently allows duplicate entries. To make
it update previous entries instead, put in the following code:
if q^.key == key then begin
q^.value = value;
end;
else
*)
begin
k := randomLevel;
if k>l^.level then begin
k := l^.level+1;
l^.level := k;
update[k] := l^.header;
end;
case k of
1 : new(q,1);
2 : new(q,2);
3 : new(q,3);
4 : new(q,4);
5 : new(q,5);
6 : new(q,6);
7 : new(q,7);
8 : new(q,8);
9 : new(q,9);
10 : new(q,10);
11 : new(q,11);
12 : new(q,12);
13 : new(q,13);
14 : new(q,14);
15 : new(q,15);
16 : new(q,16)
end;
q^.key := key;
q^.value := value;

for k := k downto 1 do begin
p := update[k];
q^.fwd[k] := p^.fwd[k];
p^.fwd[k] := q;
end;
end;
end;
procedure delete(l:list;key:keyType);
var
k : levelNum;
update : array[1..MaxLevel] of node;
p,q : node;
done : boolean;
begin
p := l^.header;

for k:= l^.level downto 1 do begin
q := p^.fwd[k];
while q^.key < key do begin
p := q;
q := p^.fwd[k];
end;
update[k] := p;
end;

if (q^.key = key) then begin
k := 1;
done := false;
while not done do begin
update[k]^.fwd[k] := q^.fwd[k];
k := k+1;
if k > l^.level then done := true
else done := update[k]^.fwd[k] <> q;
end;
case k-1 of
1 : dispose(q,1);
2 : dispose(q,2);
3 : dispose(q,3);
4 : dispose(q,4);
5 : dispose(q,5);
6 : dispose(q,6);
7 : dispose(q,7);
8 : dispose(q,8);
9 : dispose(q,9);
10 : dispose(q,10);
11 : dispose(q,11);
12 : dispose(q,12);
13 : dispose(q,13);
14 : dispose(q,14);
15 : dispose(q,15);
16 : dispose(q,16)
end;
end;
end;
function search(l : list; key : keyType; var value : valueType) : boolean;
var k : integer;
p,q : node;
begin
p := l^.header;
for k:= l^.level downto 1 do begin
q := p^.fwd[k];
while q^.key < key do begin
p := q;
q := p^.fwd[k];
end;
end;
if (q^.key <> key) then search := false
else begin
value := q^.value;
search := true;
end;
end;
begin
initRandom;
init;
l := newList;
for k := 1 to sampleSize do begin
keys[k]:=randomNumber;
insert(l,keys[k],keys[k]);
end;
for i := 1 to 4 do begin
for k := 1 to sampleSize do
if not search(l,keys[k],v) then writeln('not found');
for k := 1 to sampleSize do begin
delete(l,keys[k]);
keys[k] := randomNumber;
insert(l,keys[k],keys[k]);
end;
end;
freeList(l);
end.