Skip to content

Instantly share code, notes, and snippets.

@zhpengg
Created June 5, 2012 07:52
Show Gist options
  • Save zhpengg/2873424 to your computer and use it in GitHub Desktop.
Save zhpengg/2873424 to your computer and use it in GitHub Desktop.
skiplist implementation in c
/* Skip Lists: A Probabilistic Alternative to Balanced Trees */
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#define SKIPLIST_MAX_LEVEL 6
typedef struct snode {
int key;
int value;
struct snode **forward;
} snode;
typedef struct skiplist {
int level;
int size;
struct snode *header;
} skiplist;
skiplist *skiplist_init(skiplist *list)
{
int i;
snode *header = (snode *)malloc(sizeof(struct snode));
list->header = header;
header->key = INT_MAX;
header->forward = (snode **)malloc(sizeof(snode*) * (SKIPLIST_MAX_LEVEL+1));
for (i = 0; i <= SKIPLIST_MAX_LEVEL; i++) {
header->forward[i] = list->header;
}
list->level = 1;
list->size = 0;
return list;
}
static int rand_level()
{
int level = 1;
while (rand() < RAND_MAX/2 && level < SKIPLIST_MAX_LEVEL)
level++;
return level;
}
int skiplist_insert(skiplist *list, int key, int value)
{
snode *update[SKIPLIST_MAX_LEVEL+1];
snode *x = list->header;
int i, level;
for (i = list->level; i >= 1; i--) {
while (x->forward[i]->key < key)
x = x->forward[i];
update[i] = x;
}
x = x->forward[1];
if (key == x->key) {
x->value = value;
return 0;
} else {
level = rand_level();
if (level > list->level) {
for (i = list->level+1; i <= level; i++) {
update[i] = list->header;
}
list->level = level;
}
x = (snode *)malloc(sizeof(snode));
x->key = key;
x->value = value;
x->forward = (snode **)malloc(sizeof(snode*) * (level + 1));
for (i = 1; i <= level; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
}
return 0;
}
snode *skiplist_search(skiplist *list, int key)
{
snode *x = list->header;
int i;
for (i = list->level; i >= 1; i--) {
while (x->forward[i]->key < key)
x = x->forward[i];
}
if (x->forward[1]->key == key) {
return x->forward[1];
} else {
return NULL;
}
return NULL;
}
static void skiplist_node_free(snode *x)
{
if (x) {
free(x->forward);
free(x);
}
}
int skiplist_delete(skiplist *list, int key)
{
int i;
snode *update[SKIPLIST_MAX_LEVEL + 1];
snode *x = list->header;
for (i = list->level; i >= 1; i--) {
while (x->forward[i]->key < key)
x = x->forward[i];
update[i] = x;
}
x = x->forward[1];
if (x->key == key) {
for (i = 1; i <= list->level; i++) {
if (update[i]->forward[i] != x)
break;
update[i]->forward[1] = x->forward[i];
}
skiplist_node_free(x);
while (list->level > 1 && list->header->forward[list->level] == list->header)
list->level--;
return 0;
}
return 1;
}
static void skiplist_dump(skiplist *list)
{
snode *x = list->header;
while (x && x->forward[1] != list->header) {
printf("%d[%d]->", x->forward[1]->key, x->forward[1]->value);
x = x->forward[1];
}
printf("NIL\n");
}
int main()
{
int arr[] = {3, 6, 9, 2, 11, 1, 4}, i;
skiplist list;
skiplist_init(&list);
printf("Insert:--------------------\n");
for (i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
skiplist_insert(&list, arr[i], arr[i]);
}
skiplist_dump(&list);
printf("Search:--------------------\n");
int keys[] = {3, 4, 7, 10, 111};
for (i = 0; i < sizeof(keys)/sizeof(keys[0]); i++) {
snode *x = skiplist_search(&list, keys[i]);
if (x) {
printf("key = %d, value = %d\n", keys[i], x->value);
} else {
printf("key = %d, not fuound\n", keys[i]);
}
}
printf("Search:--------------------\n");
skiplist_delete(&list, 3);
skiplist_delete(&list, 9);
skiplist_dump(&list);
return 0;
}
@liujunming
Copy link

liujunming commented Aug 18, 2016

Thanks for your code. According to the suggestion of those programmer above,I have fixed some bugs in your code,I will show the code :

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#define SKIPLIST_MAX_LEVEL 6

typedef struct snode {
    int key;
    int value;
    struct snode **forward;
} snode;

typedef struct skiplist {
    int level;
    struct snode *header;
} skiplist;

skiplist *skiplist_init(skiplist *list) {
    int i;
    snode *header = (snode *) malloc(sizeof(struct snode));
    list->header = header;
    header->key = INT_MAX;
    header->forward = (snode **) malloc(
            sizeof(snode*) * (SKIPLIST_MAX_LEVEL + 1));
    for (i = 0; i <= SKIPLIST_MAX_LEVEL; i++) {
        header->forward[i] = list->header;
    }

    list->level = 1;

    return list;
}

static int rand_level() {
    int level = 1;
    while (rand() < RAND_MAX / 2 && level < SKIPLIST_MAX_LEVEL)
        level++;
    return level;
}

int skiplist_insert(skiplist *list, int key, int value) {
    snode *update[SKIPLIST_MAX_LEVEL + 1];
    snode *x = list->header;
    int i, level;
    for (i = list->level; i >= 1; i--) {
        while (x->forward[i]->key < key)
            x = x->forward[i];
        update[i] = x;
    }
    x = x->forward[1];

    if (key == x->key) {
        x->value = value;
        return 0;
    } else {
        level = rand_level();
        if (level > list->level) {
            for (i = list->level + 1; i <= level; i++) {
                update[i] = list->header;
            }
            list->level = level;
        }

        x = (snode *) malloc(sizeof(snode));
        x->key = key;
        x->value = value;
        x->forward = (snode **) malloc(sizeof(snode*) * (level + 1));
        for (i = 1; i <= level; i++) {
            x->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = x;
        }
    }
    return 0;
}

snode *skiplist_search(skiplist *list, int key) {
    snode *x = list->header;
    int i;
    for (i = list->level; i >= 1; i--) {
        while (x->forward[i]->key < key)
            x = x->forward[i];
    }
    if (x->forward[1]->key == key) {
        return x->forward[1];
    } else {
        return NULL;
    }
    return NULL;
}

static void skiplist_node_free(snode *x) {
    if (x) {
        free(x->forward);
        free(x);
    }
}

int skiplist_delete(skiplist *list, int key) {
    int i;
    snode *update[SKIPLIST_MAX_LEVEL + 1];
    snode *x = list->header;
    for (i = list->level; i >= 1; i--) {
        while (x->forward[i]->key < key)
            x = x->forward[i];
        update[i] = x;
    }

    x = x->forward[1];
    if (x->key == key) {
        for (i = 1; i <= list->level; i++) {
            if (update[i]->forward[i] != x)
                break;
            update[i]->forward[i] = x->forward[i];
        }
        skiplist_node_free(x);

        while (list->level > 1 && list->header->forward[list->level]
                == list->header)
            list->level--;
        return 0;
    }
    return 1;
}

void skiplist_free(skiplist *list)
{
    snode *current_node = list->header->forward[1];
    while(current_node != list->header) {
        snode *next_node = current_node->forward[1];
        free(current_node->forward);
        free(current_node);
        current_node = next_node;
    }
    free(current_node->forward);
    free(current_node);
    free(list);
}

static void skiplist_dump(skiplist *list) {
    snode *x = list->header;
    while (x && x->forward[1] != list->header) {
        printf("%d[%d]->", x->forward[1]->key, x->forward[1]->value);
        x = x->forward[1];
    }
    printf("NIL\n");
}

int main() {
    int arr[] = { 3, 6, 9, 2, 11, 1, 4 }, i;
    skiplist * list;
    list = (skiplist *)malloc(sizeof(skiplist));
    skiplist_init(list);

    printf("Insert:--------------------\n");
    for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
        skiplist_insert(list, arr[i], arr[i]);
    }
    skiplist_dump(list);

    printf("Search:--------------------\n");
    int keys[] = { 3, 4, 7, 10, 111 };

    for (i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
        snode *x = skiplist_search(list, keys[i]);
        if (x) {
            printf("key = %d, value = %d\n", keys[i], x->value);
        } else {
            printf("key = %d, not fuound\n", keys[i]);
        }
    }

    printf("Search:--------------------\n");
    skiplist_delete(list, 3);
    skiplist_delete(list, 9);
    skiplist_dump(list);
    skiplist_free(list);

    return 0;
}

@daveyc
Copy link

daveyc commented Sep 29, 2016

I don't like the look of those unchecked mallocs()! Memory might be plentiful on your PC but not so much so in constrained environments.

@zhaozhao15
Copy link

What does the forward[0] of each node store? I think forward[0] is never used after header. So, is the initialization of (maxlevel+1) necessary?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment