跳跃表的实现

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