A Simple Skiplist in C

I absolutely love the skiplist. Compared to a Red-Black or AVL tree, I find the implementation much simpler. Whenever I need an ordered map of some sort, I reach for my standard "generic" skiplist implementation.

Now, I've seen a lot of overly complication implementations, so I wanted to show my take on it. Like most of my other projects, I utilize CCAN whenever I can, and my skiplist implementation is no exception. Here, we use the CCAN list.h that is inspired by the similar embedded list in the Linux kernel. My skiplist implementation is similarly "embedded", which means that the data we want to store in it, itself contains the actual skiplist node.

First, the struct skiplist_node that is embedded in our data.

struct skiplist_node {
        struct list_node list[SKIPLIST_LEVELS];
};

Here, as I mentioned, we use struct list_node from ccan/list/list.h. Our actual skiplist is defined by a height, a sentinel node and list heads for each level.

struct skiplist {
        int height;
        struct skiplist_node sentinel;
        struct list_head heads[SKIPLIST_LEVELS];
};

To make it easier to work with, we define a set of helper macros.

#define skiplist_top(h, t, k) \
        list_top(&(h)->heads[k], t, list[k])

#define skiplist_next(h, n, k) \
        list_next(&(h)->heads[k], (n), list[k])

#define skiplist_add_after(h, p, n, k) \
        list_add_after(&(h)->heads[k], &(p)->list[k], &(n)->list[k])

#define skiplist_add(h, n, k) \
        list_add(&(h)->heads[k], &(n)->list[k])

#define skiplist_del_from(h, n, k) \
        list_del_from(&(h)->heads[k], &(n)->list[k])

#define skiplist_for_each_safe(h, n, next, k) \
        list_for_each_safe(&(h)->heads[k], n, next, list[k])

These macros simply makes it easy to deal with the individual levels of the skiplist when we have the list, potentially a node to add or insert, and the level at which we are modifying the skiplist.

Now, let's look at the implementation, given these simple data structures.

To initialize the list we need to initialize the heads for each level and add the sentinel node on each level.

void skiplist_init(struct skiplist *list)
{
        list->height = 0;

        for (int k = 0; k < SKIPLIST_LEVELS; k++) {
                list_head_init(&list->heads[k]);
                skiplist_add(list, &list->sentinel, k);
        }
}

Remember that list->sentinel is a struct skiplist_node with a struct list_node for each level.

Inserting into skiplists cause the node to be added to a randomized number of levels. We use the below function to randomize that key property. The below just tosses a coin a number of times to determine the level to insert at.

static inline int __skiplist_random_level(void)
{
        int k = 0;

        while (k < SKIPLIST_LEVELS - 1 && (rand() > (RAND_MAX / 2)))
                k++;

        return k;
}

#define SKIPLIST_RANDOM_LEVEL __skiplist_random_level()

A key invariant of the skiplist is that the lists of each level must be properly updated whenever we insert or remove from the list. That is, if a node is present in levels 0 through k we need to remove it from the individual struct list_head's that make up the levels. Similarly, when inserting at level k, we need to make sure that the new node is inserted at the right position in level 0 through k. We will call these levels the "update set".

For both inserts and deletions, we need to calculate this update set. For insertions, our new node will be inserted following each node in the update set, and for deletions, we remove the node if it is in the update set.

To calculate the update set, we need to traverse the list, starting at the top level and dropping down a level whenever advancing to the next node would cause us to move past the value position that we are locating.

Given a standard comparison function returning -1, 0 or 1 respectively, we can define a generic find function.

struct skiplist_node *skiplist_find(struct skiplist *list, const void *key,
                                    int (*cmp)(const void *key, const struct skiplist_node *n),
                                    struct skiplist_node **path)
{
        /* start at the sentinel node in the top most level */
        struct skiplist_node *next, *p = &list->sentinel;
        int k = list->height;

        do {
                next = skiplist_next(list, p, k);

                /* advance at this level as long as key is larger than next */
                while (next && cmp(key, next) > 0) {
                        p = next;
                        next = skiplist_next(list, p, k);
                }

                /*
                 * Our key is smaller than (or equal to) next or we reached the
                 * end of the list.
                 *
                 * Drop down a level, and record the node where we did so.
                 */
                if (path)
                        path[k] = p;
        } while (--k >= 0);

        /* at this point we are at level zero; check if we have a winner */
        if (next && cmp(key, next) == 0)
                return next;

        return NULL;
}

skiplist_find() can be used for both inserts and deletions. skiplist__find() is included for convenience, you can opt to write your own that does not rely on a comparison function callback. The key is that you need to calculate the update set like above.

With the update set calculated, we can do the insert (link) and deletion (erase).

void skiplist_link(struct skiplist *list, struct skiplist_node *n,
                   struct skiplist_node *update[SKIPLIST_LEVELS])
{
        /* randomize level to insert at */
        int k = SKIPLIST_RANDOM_LEVEL;

        if (k > list->height) {
                /* increase the height of the skiplist */
                k = ++(list->height);

                /* new level k; insert new node after the sentinel */
                update[k] = &list->sentinel;
        }

        /* insert from level k and down */
        do {
                skiplist_add_after(list, update[k], n, k);
        } while (--k >= 0);
}

void skiplist_erase(struct skiplist *list, struct skiplist_node *n,
                    struct skiplist_node *update[SKIPLIST_LEVELS])
{
        /* start from the top-most level */
        for (int k = 0; k <= list->height; k++) {
                /*
                 * Note: update[k] is the node **preceeding** the node to
                 * potentially remove.
                 */
                struct skiplist_node *next = skiplist_next(list, update[k], k);

                /*
                 * If the next node is not the right one, then this node is not
                 * present in any layer above current k.
                 */
                if (next != n)
                        break;

                skiplist_del_from(list, n, k);
        }

        /* reduce height if possible (if level is empty) */
        while (list->height && skiplist_next(list, &list->sentinel, list->height) == NULL)
                list->height--;
}

Finally, below is an example of how to use this.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#include <sys/mman.h>

#include "ccan/compiler/compiler.h"
#include "ccan/tap/tap.h"

#define SKIPLIST_LEVELS 8
#include "skiplist.h"

static struct skiplist list;

struct entry {
        unsigned int v;

        struct skiplist_node list;
};

static int cmp(const void *key, const struct skiplist_node *n)
{
        struct entry *e = container_of_var(n, e, list);
        const unsigned int *v = key;

        if (*v < e->v)
                return -1;
        else if (*v > e->v)
                return 1;

        return 0;
}

static int add(unsigned int v)
{
        struct skiplist_node *update[SKIPLIST_LEVELS] = {};
        struct entry *e = malloc(sizeof(*e));

        memset(e, 0x0, sizeof(*e));

        e->v = v;

        if (skiplist_find(&list, &v, cmp, update))
                return -EEXIST;

        skiplist_link(&list, &e->list, update);

        return 0;
}

static void erase(unsigned int v)
{

        struct skiplist_node *n, *update[SKIPLIST_LEVELS];

        n = skiplist_find(&list, &v, cmp, update);
        skiplist_erase(&list, n, update);
}

int main(void)
{
        struct skiplist_node *n, *update[SKIPLIST_LEVELS];
        unsigned int v;

        plan_no_plan();

        /* tests rely on seed 1 */
        srand(1);
        skiplist_init(&list);

        ok(list.height == 0, "initial height is zero");

        /* add ok */
        ok(add(1), "add 1");
        ok(add(3), "add 3");
        ok(add(2), "add 2");
        ok(add(0), "add 0");

        ok(list.height == 2, "height is now 2");

        for (v = 1; v < 4; v++) {
                n = skiplist_find(&list, &v, cmp, NULL);

                ok(n && skiplist_entry(n, struct entry, list)->v == v,
                   "find %d ok", v);
        }

        v = 4;

        ok(skiplist_find(&list, &v, cmp, NULL) == NULL, "find 4 not ok");

        del(3);

        ok(list.height == 1, "height is now 1");

        ok(skiplist_find(&list, &v, cmp, NULL) == NULL, "find 3 not ok");

        return exit_status();
}