DEV Community

Daniele Cruciani
Daniele Cruciani

Posted on

skiplist implementation

I share here my skiplist implementation. It is a good idea to keep in trained on C language.

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

#define LOGLEVEL 3

// a skip list is made of a single linked where each element has an
// array of pointers to the next element of the same level.
// I will name `level_pointer` the array of pointers,
// for each element "e" in the list e.level_pointer[n] points to
// the next element "e1" at the same level.
// Every pointer with m smaller than n, the e.level_pointer[m] points
// to an element "e2" such that e <= e2 <= e1
// and if it exists an element e4 with maxlevel>=m such that
// e <= e4 <= e2 then e4==e2
// with <= the order function defined between the elements.
// That implies that at level 0 each level_pointer represent
// a regular ordered linked list.
// The advance of skiplist is to consider the higher level to
// skip to the position where the element should be placed or
// looked at.
// Assuming the element is a pointer to the real element (so void *)
// a skiplist can be modelled by using a data structure like this

typedef struct skiplist {
    void *element;
    // skiplist specific fields
    int maxlevel;
    struct skiplist ** level_pointer;
} Skiplist;

// I define here a container as a main access point to the list.
// It has basically 3 fields:
typedef struct sklist {
    // the array of pointers to each element of the list at level x
    struct skiplist ** level_pointer;
    // x goes from 0 to maxlevel-1
    int maxlevel;
    // the compare function
    // this return -1, 0, or 1 if first param is less than, equal, or bigger than
    // the second, respectively
    int (*cmp)(void*, void*);
} Skiplistcontainer;
// a function that create a skiplist
struct sklist * create_skip(int (*cmp)(void*, void*)) {
    struct sklist * slc = (struct sklist *) malloc(sizeof(struct sklist));
    slc->level_pointer = (struct skiplist**) calloc(1, sizeof(struct skiplist*));
    slc->maxlevel = 1;
    slc->level_pointer[0] = NULL;
    slc->cmp = cmp;
    return slc;
}

void logit(const char *restrict format, ...) {
    va_list ap;
    va_start( ap, format );
    vprintf(format, ap);
}

void sklist_insert(struct sklist* slc, void *element) {
    // create the new node
    struct skiplist * sknode = (struct skiplist*) malloc(sizeof(struct skiplist*));
    sknode->element = element;
    sknode->maxlevel = 1;
    // toss a coin to determine the element maxlevel
    while ((rand() % 2) == 1)  {
        sknode->maxlevel++;
    }
    #if LOGLEVEL == 3
    logit("INSERTING %d at LEVE %d\n",*(int*)element, sknode->maxlevel);
    #endif
    sknode->level_pointer = (struct skiplist**) calloc(sknode->maxlevel, sizeof(struct skiplist*));
    int from_level = sknode->maxlevel-1;
    if (sknode->maxlevel > slc->maxlevel ) {
        // if the new element has the tallest level_pointer
        // it means all the pointers with higher level points to the new element
        slc->level_pointer = (struct skiplist**) realloc(slc->level_pointer, sknode->maxlevel * sizeof(struct skiplist*));
        int i;
        for (i = slc->maxlevel; i< sknode->maxlevel; i++) {
            slc->level_pointer[i] = sknode;
            sknode->level_pointer[i] = NULL;
        }
        from_level = slc->maxlevel - 1;
        slc->maxlevel = sknode->maxlevel;
    }
    // starting from_level the insertion must be checked
    struct skiplist ** left_p = slc->level_pointer;
    for(;from_level>=0;from_level--) {
        // peak the next element pointed, still staying a position before
        // keeping in mind that head is smaller than anything,
        // then left_p belong to something smaller than sknode
        while( (left_p[from_level] != NULL) && slc->cmp(left_p[from_level]->element, sknode->element)<=0 ) {
            left_p = left_p[from_level]->level_pointer;
        }
        sknode->level_pointer[from_level] = left_p[from_level];
        left_p[from_level] = sknode;
    #if LOGLEVEL == 3
        logit("Inserted %d\n", *(int*) sknode->element);
    #endif
        //printf("left %d\n", *(int*) left_p[from_level]->level_pointer[from_level]->element);
    }
}

struct skiplist * sklist_exists(struct sklist* slc, void *element) {
    // search for element and return it if it exists, return NULL otherwise
    int maxlevel = slc->maxlevel-1;
    struct skiplist ** lpoint = slc->level_pointer;
    for (;maxlevel>=0; maxlevel--) {
        struct skiplist ** prev;
        while (lpoint[maxlevel]!=NULL && slc->cmp(lpoint[maxlevel]->element, element) <0) {
            printf("Inspecting %d l: %d\n", *(int*) lpoint[maxlevel]->element, maxlevel);
            prev = lpoint;
            lpoint = lpoint[maxlevel]->level_pointer;
        }
        if (lpoint[maxlevel]!=NULL && slc->cmp(lpoint[maxlevel]->element, element) == 0) {
            return lpoint[maxlevel];
        } else {
            lpoint = prev;
        }
    }
    return NULL;
}

struct skiplist * sklist_extract(struct sklist* slc, void *element) {
    // search for element and return it if it exists, return NULL otherwise
    int maxlevel = slc->maxlevel-1;
    struct skiplist ** lpoint = slc->level_pointer;
    struct skiplist * el_pile = NULL;
    while (maxlevel>=0) {
        struct skiplist ** prev = NULL;
        while (lpoint[maxlevel]!=NULL && slc->cmp(lpoint[maxlevel]->element, element) <0) {
            #if LOGLEVEL == 3
            logit("Inspecting %d l: %d\n", *(int*) lpoint[maxlevel]->element, maxlevel);
            #endif
            prev = lpoint;
            lpoint = lpoint[maxlevel]->level_pointer;
        }
        if (lpoint[maxlevel]!=NULL && slc->cmp(lpoint[maxlevel]->element, element) == 0) {
            #if LOGLEVEL == 3
            logit("FOUND HHHHH l:%d\n",lpoint[maxlevel]->maxlevel);
            #endif
            // remove everything from this level here to below:
            if (el_pile == NULL && lpoint[maxlevel]->maxlevel == slc->maxlevel)  {
                el_pile = lpoint[maxlevel];
                // it must resize the maxlevel of the main structure
                // for this just inspect the main level_pointer and this element level_pointer
                // until the second one is NULL and the first one is exactly this element
                // reduce the maxlevel of the mail structure
                int i = el_pile->maxlevel-1;
                while(i>0 && (slc->level_pointer[i] == el_pile && el_pile->level_pointer[i] == NULL)) i--;
                slc->maxlevel = i+1; // the level is the size
                maxlevel = slc->maxlevel;
                #if LOGLEVEL == 3
                logit("shrink level %d\n", maxlevel);
                #endif
            }
            // eat one pos
            lpoint[maxlevel] = lpoint[maxlevel]->level_pointer[maxlevel];
        } else {
            lpoint = prev;
        }
        maxlevel--;
    }
    return el_pile;
    //return NULL;
}

int compare_ints(void *X, void *Y) {
    int *x = (int*) X;
    int *y = (int*) Y;
    if(*x<*y) return -1;
    if (*x == *y) return 0;
    return 1;
}


void print_it(struct sklist* slc) {
    printf("generic staff: maxlevel: %d\n", slc->maxlevel);
    int l = slc->maxlevel;
    for(int i=0;i<l;i++) {
        struct skiplist * head = slc->level_pointer[i];
        printf("\nLEVEL: %d\n",i);
        while (head != NULL) {
            printf("%d\t-\t", *(int*) (head->element));
            head = head->level_pointer[i];
        }
    }
    printf("\n");
}

void pile_print_it(struct sklist* slc) {
    printf("PILE staff: maxlevel: %d\n", slc->maxlevel);
    int l = slc->maxlevel;
    for(int i=0;i<l;i++) {
        printf("\nLEVEL: %d\n",i);
        struct skiplist * head = slc->level_pointer[i];
        struct skiplist * head0 = slc->level_pointer[0];
        while (head != NULL) {
            while (head0!= head) {
                printf("--\t-\t");
                head0 = head0->level_pointer[0];
            }
            printf("%d\t-\t", *(int*) (head->element));
            head = head->level_pointer[i];
            head0 = head0->level_pointer[0];
        }
    }
    printf("\n");
}

int main() {
    int *i;
    *i = 190;
    int j = 12;
    printf("COMPARE %d vs %d : %d\n", j, *i, compare_ints((void*) &j, (void *) i));
    // *j = 12;
    struct sklist *skipl = create_skip(compare_ints);
    print_it(skipl);
    sklist_insert(skipl, (void*)i);
    print_it(skipl);
    sklist_insert(skipl, (void*)&j);
    print_it(skipl);
    int k = 23;
    sklist_insert(skipl, (void*)&k);
    print_it(skipl);
    int kk = 123;
    sklist_insert(skipl, (void*)&kk);
    pile_print_it(skipl);
    int kk2 = 23;
    struct skiplist *el = sklist_exists(skipl, (void*) &kk2);
    if(el!=NULL) {
        printf("FOUND!!!!!\n");
    } else {
        printf("NOOOOT FOUND!!\n");
    }
    for(;;) {
        printf("command (I_nsert/L_ookup): \n");
        char command = (char) getchar();
        //if (command == '\n') command = (char) getchar();
        switch (command) {
            case 'i':
            case 'I':
            {
                printf("insert a num: ");
                int *xx = malloc(sizeof(int));
                scanf("%d", xx);
                sklist_insert(skipl, (void*)xx);
                pile_print_it(skipl);
            }
            break;
            case 'l':
            case 'L':
            {
                printf("lookup a num: ");
                int *xx = malloc(sizeof(int));
                scanf("%d", xx);
                struct skiplist *el = sklist_exists(skipl, (void*) xx);
                if(el!=NULL) {
                    printf("%d FOUND!!!!!\n", *xx);
                } else {
                    printf("%d NOOOOT FOUND!!\n", *xx);
                }
            }
            break;
            case 'e':
            case 'E':
            {
                printf("extract a num: ");
                int *xx = malloc(sizeof(int));
                scanf("%d", xx);
                struct skiplist *el = sklist_extract(skipl, (void*) xx);
                if(el!=NULL) {
                    printf("%d FOUND!!!!!\n", *xx);
                } else {
                    printf("%d NOOOOT FOUND!!\n", *xx);
                }
                //free(el);
            }
            case 'p':
            case 'P':
                pile_print_it(skipl);
                break;
            case 'x':
                return 0;
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

there is some bugs in there, to be fixed

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up