<< Care to post the source? >>
Sure, it's a bit a mess, though (mixing C and C++ here!):
----------- source: --------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define false 0
#define true 1
typedef char boolean;
#define BitsInRandom 31
// #define allowDuplicates // duplicates are allowed if defined.
#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;
void init() {
srand(time(NULL));
NIL = newNodeOfLevel(0);
NIL->key = 0x7fffffff;
randomBits = rand() % 1;
//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;i<MaxNumberOfLevels;i++) l->header->forward[ I ] = NIL;
return(l);
};
void 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 = rand() % 1;
//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);
};
// -----------------------
// ---- Test Code ----
#define sampleSize 65536
main() {
list l;
register int i,k;
keyType keys[sampleSize];
valueType v;
init();
l= newList();
for(k=0;k<sampleSize;k++) {
//keys[k]=random();
keys[k]=rand() % 1;
insert(l,keys[k],keys[k]);
};
for(i=0;i<4;i++) {
for(k=0;k<sampleSize;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<sampleSize;k++) {
if (! delete(l,keys[k])) printf("error in delete\n");
//keys[k] = random();
keys[k] = rand() % 1;
insert(l,keys[k],keys[k]);
};
};
freeList(l);
};
--------------------------
By the way, as you can above, I've replaced random() with srand() and rand(), because a random number between 0 and 1 was needed yet I could not find a definition of the function random() anywhere in the source.
I'm going to bed anyway =)
Facebook
Twitter