Academic example of skip list implementation in C.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

413 lines
9.3 KiB

#include <strings.h>
#include "skiplist.h"
#include "x.h"
sl_node *_sl_create_node(int key, void *data)
{
sl_node *x = xmalloc(sizeof(sl_node));
x->key = key;
x->data = data;
x->next = x->prev = x->below = x->above = NULL;
return x;
}
void sl_init(slist *sl)
{
sl_node *x = _sl_create_node(KEY_INF_MIN, NULL);
sl_node *y = _sl_create_node(KEY_INF_MAX, NULL);
x->next = y;
y->prev = x;
sl->topleft = x;
sl->bottomleft = x;
sl->topright = y;
sl->bottomright = y;
sl->maxlevel = 0;
sl->len = 2; /* -INF and +INF */
sl->stat.srchcnt = 0;
sl->stat.rmcnt = 0;
sl->stat.addcnt = 0;
sl->stat.srchnum = 0;
sl->stat.rmnum = 0;
sl->stat.addnum = 0;
sl->stat.maxlen = sl->len;
sl->stat.currsrch = 0;
sl->stat.currrm = 0;
sl->stat.curradd = 0;
sl->stat.srchcntmax = 0;
sl->stat.rmcntmax = 0;
sl->stat.addcntmax = 0;
}
void _sl_add_level(slist *sl)
{
sl_node *x = _sl_create_node(KEY_INF_MIN, NULL);
sl_node *y = _sl_create_node(KEY_INF_MAX, NULL);
x->next = y;
y->prev = x;
x->below = sl->topleft;
y->below = sl->topright;
sl->topleft->above = x;
sl->topright->above = y;
sl->topleft = x;
sl->topright = y;
++sl->maxlevel;
}
void sl_free(slist *sl)
{
sl_node *foo;
sl_node *x;
sl_node *y;
for (foo = sl->bottomleft; foo != NULL;) {
x = foo;
foo = foo->next;
while (x != NULL) {
y = x;
x = x->above;
free(y->data);
free(y);
}
}
}
void _print_key(int key)
{
if (key == KEY_INF_MIN) {
print("-INF -> ");
} else if (key == KEY_INF_MAX) {
print("+INF -> ");
} else {
print("%d -> ", key);
}
}
void _sl_println()
{
int i;
for (i = 0; i < 79; ++i) {
print("-");
}
print("\n");
}
void sl_print(const slist *sl)
{
sl_node *foo;
sl_node *x;
int level = sl->maxlevel;
_sl_println();
print("from top to bottom:\n");
for (foo = sl->topleft; foo != NULL; foo = foo->below, --level) {
print("level %d: ", level);
for (x = foo; x != NULL; x = x->next) {
_print_key(x->key);
}
print("\n");
}
_sl_println();
print("from below to above:\n");
for (foo = sl->bottomleft; foo != NULL; foo = foo->next) {
for (x = foo; x != NULL; x = x->above) {
_print_key(x->key);
}
print("\n");
}
_sl_println();
}
#define HEAD 1
#define TAIL 0
/*
* Repeatedly toss a coin until we get tails.
* Denote with i the number of times coin came up heads
* and return it.
*/
int _toss_coin(int maxlevel) {
int i;
int x;
i = 0;
while(1) {
x = random() & 0x1;
if (x == TAIL) {
break;
}
++i;
/* inc level only by one at one iter */
if (i == maxlevel + 1) {
break;
}
};
return i;
}
/*
* Remove top levels with only INFINITY nodes until only one such
* level exists.
*/
void _sl_clean_top(slist *sl)
{
sl_node *foo;
for (foo = sl->topleft; foo->below != NULL;) {
if (foo->next->key == KEY_INF_MAX
&& foo->below->next->key == KEY_INF_MAX) {
sl->topleft = foo->below;
sl->topright = foo->below->next;
sl->topleft->above = NULL;
sl->topright->above = NULL;
--sl->maxlevel;
free(foo->data);
free(foo->next);
free(foo);
foo = sl->topleft;
debug("cleaned one level\n");
} else {
break;
}
}
}
/*
* Toss coin and get i.
* If i is greather than or equal to skip list max level then
* add one more level.
* Search for x and find the positions of the items with largest key
* less than x.
* Insert item into each level up to i.
* If key is found then just update its data.
*/
int sl_add(slist *sl, int key, void *data)
{
sl_node *foo;
sl_node *x;
int i;
int k;
int level;
sl_node **update;
int res;
if (key == KEY_INF_MIN || key == KEY_INF_MAX) {
return SL_ADD_INV;
}
i = _toss_coin(sl->maxlevel);
debug("toss coin result: %d\n", i);
if (i >= sl->maxlevel) {
/* add one more level */
_sl_add_level(sl);
debug("added level\n");
}
update = (sl_node **) xmalloc(sizeof(sl_node *) * (sl->maxlevel + 1));
bzero(update, sizeof(sl_node *) * (sl->maxlevel + 1));
level = sl->maxlevel;
++sl->stat.addnum;
foo = sl->topleft;
++sl->stat.addcnt;
sl->stat.curradd = 1;
while (1) {
while (key >= foo->next->key) {
foo = foo->next;
++sl->stat.addcnt;
++sl->stat.curradd;
}
if (foo->below == NULL) {
break;
}
/*
* Save nodes that will be updated with new node.
*/
update[level--] = foo;
foo = foo->below;
++sl->stat.addcnt;
++sl->stat.curradd;
}
sl->stat.addcntmax = max(sl->stat.addcntmax, sl->stat.curradd);
update[level] = foo;
debug("search finished at key: %d\n", foo->key);
debug("update list keys:\n");
for (k = 0; k <= sl->maxlevel; ++k) {
if (update[k] != 0) {
debug("%d\n", update[k]->key);
}
}
debug("adding\n");
if (foo->key == key) {
res = SL_ADD_SAME;
debug("key exists\n");
do {
foo->data = data;
foo = foo->above;
} while (foo != NULL);
} else {
res = SL_ADD_NEW;
debug("new key\n");
while (level <= i) {
x = _sl_create_node(key, data);
x->next = update[level]->next;
update[level]->next->prev = x;
x->prev = update[level];
update[level]->next = x;
if (level > 0) {
x->below = update[level - 1]->next;
update[level - 1]->next->above = x;
}
++level;
}
++sl->len;
if (sl->len > sl->stat.maxlen) {
sl->stat.maxlen = sl->len;
}
}
_sl_clean_top(sl);
free(update);
return res;
}
/*
* Start at the top left position.
* At the current position compare key with node's key.
* If key is found then return it.
* If key > node's key then scan forward.
* If key < node's key then drop down.
* If we drop down past the bottom list then return NULL.
*/
sl_node *sl_find(slist *sl, int key)
{
sl_node *foo;
foo = sl->topleft;
sl->stat.currsrch = 1;
++sl->stat.srchcnt;
++sl->stat.srchnum;
while (1) {
while (key >= foo->next->key) {
foo = foo->next;
++sl->stat.srchcnt;
++sl->stat.currsrch;
}
if (foo->below == NULL) {
break;
}
foo = foo->below;
++sl->stat.srchcnt;
++sl->stat.currsrch;
}
sl->stat.srchcntmax = max(sl->stat.srchcntmax, sl->stat.currsrch);
if (foo->key != key) {
foo = NULL;
}
return foo;
}
/*
* Search for key and find positions with the key.
* Remove found positions.
* Remove all but one list containing only INFINITY keys.
*/
int sl_remove(slist *sl, int key)
{
sl_node *foo;
sl_node *x;
int result;
foo = sl->topleft;
sl->stat.currrm = 1;
++sl->stat.rmcnt;
++sl->stat.rmnum;
while (1) {
while (key >= foo->next->key) {
foo = foo->next;
++sl->stat.rmcnt;
++sl->stat.currrm;
}
if (foo->below == NULL) {
break;
}
foo = foo->below;
++sl->stat.rmcnt;
++sl->stat.currrm;
}
sl->stat.rmcntmax = max(sl->stat.rmcntmax, sl->stat.currrm);
if (foo->key == key) {
result = 1;
while (foo != NULL) {
foo->prev->next = foo->next;
foo->next->prev = foo->prev;
free(foo->data);
x = foo;
foo = foo->above;
free(x);
}
--sl->len;
_sl_clean_top(sl);
} else {
result = 0;
}
return result;
}
void sl_stat_print(const slist *sl)
{
size_t avgsrch;
size_t avgadd;
size_t avgrm;
_sl_println();
print("skiplist statistics:\n");
print("current len: %lu\n", sl->len);
print("search count: %lu\n", sl->stat.srchcnt);
print("add count: %lu\n", sl->stat.addcnt);
print("remove count: %lu\n", sl->stat.rmcnt);
print("search num: %lu\n", sl->stat.srchnum);
print("add num: %lu\n", sl->stat.addnum);
print("remove num: %lu\n", sl->stat.rmnum);
print("current search count: %lu\n", sl->stat.currsrch);
print("current add count: %lu\n", sl->stat.curradd);
print("current remove count: %lu\n", sl->stat.currrm);
if (sl->stat.srchnum != 0) {
avgsrch = sl->stat.srchcnt / sl->stat.srchnum;
print("average search count: %lu\n", avgsrch);
}
if (sl->stat.addnum != 0) {
avgadd = sl->stat.addcnt / sl->stat.addnum;
print("average add count: %lu\n", avgadd);
}
if (sl->stat.rmnum != 0) {
avgrm = sl->stat.rmcnt / sl->stat.rmnum;
print("average remove count: %lu\n", avgrm);
}
print("maxlen: %lu\n", sl->stat.maxlen);
print("max search count: %lu\n", sl->stat.srchcntmax);
print("max add count: %lu\n", sl->stat.addcntmax);
print("max remove count: %lu\n", sl->stat.rmcntmax);
}