skiplist/skiplist.c

#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);
}