That's for that link, it was just what I needed. Here's what I came up with
Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_LEV 4
#define LEAK_CHECK 1
#ifdef LEAK_CHECK
int cnt;
#define LeakMalloc(x) (cnt++, malloc(x))
#define LeakFree(x) (cnt--, free(x))
#define LeakPrint() (printf("Leaks found: %d\n", cnt))
#else
#define LeakMalloc(x) (malloc(x))
#define LeakFree(x) (free(x))
#define LeakPrint()
#endif
typedef struct node_s {
int key;
struct node_s **forward;
} *NODE;
typedef struct list_s {
int level;
struct node_s *header;
} *LIST;
static NODE NIL; /* End of list marker */
static NODE make_node(int lvl, int key)
{
NODE np = LeakMalloc(sizeof *np);
if (np == 0)
{
fprintf(stderr, "%d: Bad allocation in make_node()", __LINE__);
exit(1);
}
np->forward = LeakMalloc(sizeof *np->forward * lvl);
if (np->forward == 0)
{
fprintf(stderr, "%d: Bad allocation in make_node()", __LINE__);
exit(1);
}
np->key = key;
return np;
}
static int randomLevel(void)
{
int lvl = 0;
while (rand() < RAND_MAX/2 && lvl < MAX_LEV)
{
lvl++;
}
return lvl;
}
void skip_init(void)
{
NIL = make_node(0, INT_MAX);
}
void skip_end(void)
{
LeakFree(NIL->forward);
LeakFree(NIL);
}
LIST skip_new_list(void)
{
int i;
LIST list;
list = LeakMalloc(sizeof *list);
if (list == 0)
{
fprintf(stderr, "%d: Bad allocation in skip_new_list()", __LINE__);
exit(1);
}
list->level = 0;
list->header = make_node(MAX_LEV, -1);
for (i = 0; i < MAX_LEV; i++)
{
list->header->forward[i] = NIL;
}
return list;
}
void skip_free_list(LIST list)
{
NODE np, nn;
for (np = list->header; np != NIL; np = nn)
{
nn = np->forward[0];
LeakFree(np->forward);
LeakFree(np);
}
LeakFree(list);
}
void skip_insert(LIST list, int searchkey)
{
int i, lvl;
NODE update[MAX_LEV + 1];
NODE x = list->header;
/* Find the insertion point */
for (i = list->level; i >= 0; i--)
{
while (x->forward[i] != NIL && x->forward[i]->key < searchkey)
{
x = x->forward[i];
}
update[i] = x;
}
x = x->forward[0];
/* If it's a duplicate, replace */
if (x->key == searchkey)
{
x->key = searchkey;
}
/* Not found */
else
{
lvl = randomLevel();
/* Update the current max level if i is bigger */
if (lvl > list->level)
{
for (i = list->level + 1; i <= lvl; i++)
{
update[i] = list->header;
}
list->level = lvl;
}
x = make_node(lvl, searchkey);
/* Link it */
for (i = 0; i <= lvl; i++)
{
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
}
}
int main(void)
{
int i;
LIST list;
NODE np;
skip_init();
list = skip_new_list();
for (i = 0; i < 10; i++)
{
skip_insert(list, i);
}
for (i = 0; i < MAX_LEV; i++)
{
for (np = list->header; np != NIL; np = np->forward[i])
{
printf("%d%s", np->key, np->forward[i] == NIL ? "\n" : "->");
}
}
skip_free_list(list);
skip_end();
LeakPrint();
return 0;
}