#include "stdlib.h"
#include "stdio.h"
#include "limits.h"
 
typedef struct _Node{
    int key;
    int val;
 
    int topLevel;
    struct _Node **next;
} Node;
 
typedef struct _SkipList{
    int maxLevel;
    Node *head, *tail;
 
    Node **preds, **succs;
} SkipList;
 
Node *create_node(int topLevel, int key, int val){
    Node *node;
    node = calloc(1, sizeof(Node));
    node->next = (Node **) calloc(topLevel+1, sizeof(Node *));
    node->key = key;
    node->val = val;
    node->topLevel = topLevel;
    return node;
}
 
void free_node(Node *node){
    free(node->next);
    free(node);
    return;
}
 
int search(SkipList *sl, int key){
    int res, level;
    Node *pre, *crr;
    pre = sl -> head;
    res = -1;
    for(level = sl->maxLevel - 1; level >= 0; --level){
        crr = pre->next[level];
        while(key > crr->key){
            pre = crr;
            crr = pre->next[level];
        }
        if(res == -1 && key == crr->key) res = level;
        sl->preds[level] = pre;
        sl->succs[level] = crr;
    }
    return res;
}
 
int delete(SkipList *sl, int key){
    int level;
    int res;
    Node *node;
    if(search(sl, key) == -1) return -1;
    node = sl->preds[0]->next[0];
    for(level = node->topLevel; level>=0; --level)
        sl->preds[level]->next[level] = node->next[level];
    res = node->val;
    free_node(node);
    return res;
}
 
SkipList *init_list(int maxLevel){
    SkipList *sl;
    Node *head, *tail;
    int i;
    sl = (SkipList *) calloc(1, sizeof(SkipList));
    sl->preds = (Node**) calloc(maxLevel+1, sizeof(Node*));
    sl->succs = (Node**) calloc(maxLevel+1, sizeof(Node*));
    sl -> maxLevel = maxLevel;
 
    head = create_node(maxLevel, INT_MIN, 0);
    tail = create_node(maxLevel, INT_MAX, 0);
    for(i=0; i<maxLevel; ++i){
        head -> next[i] = tail;
        tail -> next[i] = NULL;
    }
    sl -> head = head;
    sl -> tail = tail;
    return sl;
}
 
void free_list(SkipList *sl){
    Node *node;
    while(sl->head->next[0] != sl->tail) delete(sl, sl->head->next[0]->key);
    free_node(sl->head);
    free_node(sl->tail);
    free(sl->preds);
    free(sl->succs);
    free(sl);
}
 
 
int add(SkipList *sl, int key, int val){
    int level, topLevel, fLevel;
    Node *node;
    int r = rand();
    if((fLevel = search(sl, key)) != -1) return -1;
    topLevel = (r % sl->maxLevel);
    node = create_node(topLevel, key, val);
    for(level = 0; level <= topLevel; ++level){
        node->next[level] = sl->succs[level];
        sl->preds[level]->next[level] = node;
    }
    return 0;
}
 
int find(SkipList *sl, int key){
    int res;
    if(search(sl, key) != -1) return -1;
    return sl->preds[0]->next[0]->val;
}
 
void print_list(SkipList *sl){
    int i;
    Node *node;
    for(i=sl->maxLevel-1; i>=0; --i){
        printf("\tlevel %2d: ", i);
        for(node = sl->head->next[0]; node != sl->tail; node = node->next[0]){
            if(i <= node->topLevel)
                printf(" [%5d]", node->key);
            else
                printf("        ");
        }
        printf("\n");
    }
    return;
}
 
 
 
int main(void) {
    int i;
    SkipList *sl;
 
    int *nums;
    int t = 10;
 
    nums = calloc(t, sizeof(int));
    sl = init_list(4);
 
    for (i = 0; i < t; i++) {
        add(sl, (nums[i] = i), i);
        printf("add %d\n", nums[i]);
        print_list(sl);
    }
 
    for (i = t - 1; 1 <= i; i--) {
        printf("delete %d\n", delete(sl, nums[i]));
        print_list(sl);
    }
 
    free(nums);
    free_list(sl);
    exit(0);
    return 0;
}

I2luY2x1ZGUgInN0ZGxpYi5oIgojaW5jbHVkZSAic3RkaW8uaCIKI2luY2x1ZGUgImxpbWl0cy5oIgoKdHlwZWRlZiBzdHJ1Y3QgX05vZGV7CiAgICBpbnQga2V5OwogICAgaW50IHZhbDsKCiAgICBpbnQgdG9wTGV2ZWw7CiAgICBzdHJ1Y3QgX05vZGUgKipuZXh0Owp9IE5vZGU7Cgp0eXBlZGVmIHN0cnVjdCBfU2tpcExpc3R7CiAgICBpbnQgbWF4TGV2ZWw7CiAgICBOb2RlICpoZWFkLCAqdGFpbDsKCiAgICBOb2RlICoqcHJlZHMsICoqc3VjY3M7Cn0gU2tpcExpc3Q7CgpOb2RlICpjcmVhdGVfbm9kZShpbnQgdG9wTGV2ZWwsIGludCBrZXksIGludCB2YWwpewogICAgTm9kZSAqbm9kZTsKICAgIG5vZGUgPSBjYWxsb2MoMSwgc2l6ZW9mKE5vZGUpKTsKICAgIG5vZGUtPm5leHQgPSAoTm9kZSAqKikgY2FsbG9jKHRvcExldmVsKzEsIHNpemVvZihOb2RlICopKTsKICAgIG5vZGUtPmtleSA9IGtleTsKICAgIG5vZGUtPnZhbCA9IHZhbDsKICAgIG5vZGUtPnRvcExldmVsID0gdG9wTGV2ZWw7CiAgICByZXR1cm4gbm9kZTsKfQoKdm9pZCBmcmVlX25vZGUoTm9kZSAqbm9kZSl7CiAgICBmcmVlKG5vZGUtPm5leHQpOwogICAgZnJlZShub2RlKTsKICAgIHJldHVybjsKfQoKaW50IHNlYXJjaChTa2lwTGlzdCAqc2wsIGludCBrZXkpewogICAgaW50IHJlcywgbGV2ZWw7CiAgICBOb2RlICpwcmUsICpjcnI7CiAgICBwcmUgPSBzbCAtPiBoZWFkOwogICAgcmVzID0gLTE7CiAgICBmb3IobGV2ZWwgPSBzbC0+bWF4TGV2ZWwgLSAxOyBsZXZlbCA+PSAwOyAtLWxldmVsKXsKICAgICAgICBjcnIgPSBwcmUtPm5leHRbbGV2ZWxdOwogICAgICAgIHdoaWxlKGtleSA+IGNyci0+a2V5KXsKICAgICAgICAgICAgcHJlID0gY3JyOwogICAgICAgICAgICBjcnIgPSBwcmUtPm5leHRbbGV2ZWxdOwogICAgICAgIH0KICAgICAgICBpZihyZXMgPT0gLTEgJiYga2V5ID09IGNyci0+a2V5KSByZXMgPSBsZXZlbDsKICAgICAgICBzbC0+cHJlZHNbbGV2ZWxdID0gcHJlOwogICAgICAgIHNsLT5zdWNjc1tsZXZlbF0gPSBjcnI7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgppbnQgZGVsZXRlKFNraXBMaXN0ICpzbCwgaW50IGtleSl7CiAgICBpbnQgbGV2ZWw7CiAgICBpbnQgcmVzOwogICAgTm9kZSAqbm9kZTsKICAgIGlmKHNlYXJjaChzbCwga2V5KSA9PSAtMSkgcmV0dXJuIC0xOwogICAgbm9kZSA9IHNsLT5wcmVkc1swXS0+bmV4dFswXTsKICAgIGZvcihsZXZlbCA9IG5vZGUtPnRvcExldmVsOyBsZXZlbD49MDsgLS1sZXZlbCkKICAgICAgICBzbC0+cHJlZHNbbGV2ZWxdLT5uZXh0W2xldmVsXSA9IG5vZGUtPm5leHRbbGV2ZWxdOwogICAgcmVzID0gbm9kZS0+dmFsOwogICAgZnJlZV9ub2RlKG5vZGUpOwogICAgcmV0dXJuIHJlczsKfQoKU2tpcExpc3QgKmluaXRfbGlzdChpbnQgbWF4TGV2ZWwpewogICAgU2tpcExpc3QgKnNsOwogICAgTm9kZSAqaGVhZCwgKnRhaWw7CiAgICBpbnQgaTsKICAgIHNsID0gKFNraXBMaXN0ICopIGNhbGxvYygxLCBzaXplb2YoU2tpcExpc3QpKTsKICAgIHNsLT5wcmVkcyA9IChOb2RlKiopIGNhbGxvYyhtYXhMZXZlbCsxLCBzaXplb2YoTm9kZSopKTsKICAgIHNsLT5zdWNjcyA9IChOb2RlKiopIGNhbGxvYyhtYXhMZXZlbCsxLCBzaXplb2YoTm9kZSopKTsKICAgIHNsIC0+IG1heExldmVsID0gbWF4TGV2ZWw7CgogICAgaGVhZCA9IGNyZWF0ZV9ub2RlKG1heExldmVsLCBJTlRfTUlOLCAwKTsKICAgIHRhaWwgPSBjcmVhdGVfbm9kZShtYXhMZXZlbCwgSU5UX01BWCwgMCk7CiAgICBmb3IoaT0wOyBpPG1heExldmVsOyArK2kpewogICAgICAgIGhlYWQgLT4gbmV4dFtpXSA9IHRhaWw7CiAgICAgICAgdGFpbCAtPiBuZXh0W2ldID0gTlVMTDsKICAgIH0KICAgIHNsIC0+IGhlYWQgPSBoZWFkOwogICAgc2wgLT4gdGFpbCA9IHRhaWw7CiAgICByZXR1cm4gc2w7Cn0KCnZvaWQgZnJlZV9saXN0KFNraXBMaXN0ICpzbCl7CiAgICBOb2RlICpub2RlOwogICAgd2hpbGUoc2wtPmhlYWQtPm5leHRbMF0gIT0gc2wtPnRhaWwpIGRlbGV0ZShzbCwgc2wtPmhlYWQtPm5leHRbMF0tPmtleSk7CiAgICBmcmVlX25vZGUoc2wtPmhlYWQpOwogICAgZnJlZV9ub2RlKHNsLT50YWlsKTsKICAgIGZyZWUoc2wtPnByZWRzKTsKICAgIGZyZWUoc2wtPnN1Y2NzKTsKICAgIGZyZWUoc2wpOwp9CgoKaW50IGFkZChTa2lwTGlzdCAqc2wsIGludCBrZXksIGludCB2YWwpewogICAgaW50IGxldmVsLCB0b3BMZXZlbCwgZkxldmVsOwogICAgTm9kZSAqbm9kZTsKICAgIGludCByID0gcmFuZCgpOwogICAgaWYoKGZMZXZlbCA9IHNlYXJjaChzbCwga2V5KSkgIT0gLTEpIHJldHVybiAtMTsKICAgIHRvcExldmVsID0gKHIgJSBzbC0+bWF4TGV2ZWwpOwogICAgbm9kZSA9IGNyZWF0ZV9ub2RlKHRvcExldmVsLCBrZXksIHZhbCk7CiAgICBmb3IobGV2ZWwgPSAwOyBsZXZlbCA8PSB0b3BMZXZlbDsgKytsZXZlbCl7CiAgICAgICAgbm9kZS0+bmV4dFtsZXZlbF0gPSBzbC0+c3VjY3NbbGV2ZWxdOwogICAgICAgIHNsLT5wcmVkc1tsZXZlbF0tPm5leHRbbGV2ZWxdID0gbm9kZTsKICAgIH0KICAgIHJldHVybiAwOwp9CgppbnQgZmluZChTa2lwTGlzdCAqc2wsIGludCBrZXkpewogICAgaW50IHJlczsKICAgIGlmKHNlYXJjaChzbCwga2V5KSAhPSAtMSkgcmV0dXJuIC0xOwogICAgcmV0dXJuIHNsLT5wcmVkc1swXS0+bmV4dFswXS0+dmFsOwp9Cgp2b2lkIHByaW50X2xpc3QoU2tpcExpc3QgKnNsKXsKICAgIGludCBpOwogICAgTm9kZSAqbm9kZTsKICAgIGZvcihpPXNsLT5tYXhMZXZlbC0xOyBpPj0wOyAtLWkpewogICAgICAgIHByaW50ZigiXHRsZXZlbCAlMmQ6ICIsIGkpOwogICAgICAgIGZvcihub2RlID0gc2wtPmhlYWQtPm5leHRbMF07IG5vZGUgIT0gc2wtPnRhaWw7IG5vZGUgPSBub2RlLT5uZXh0WzBdKXsKICAgICAgICAgICAgaWYoaSA8PSBub2RlLT50b3BMZXZlbCkKICAgICAgICAgICAgICAgIHByaW50ZigiIFslNWRdIiwgbm9kZS0+a2V5KTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgcHJpbnRmKCIgICAgICAgICIpOwogICAgICAgIH0KICAgICAgICBwcmludGYoIlxuIik7CiAgICB9CiAgICByZXR1cm47Cn0KCgoKaW50IG1haW4odm9pZCkgewogICAgaW50IGk7CiAgICBTa2lwTGlzdCAqc2w7CgogICAgaW50ICpudW1zOwogICAgaW50IHQgPSAxMDsKCiAgICBudW1zID0gY2FsbG9jKHQsIHNpemVvZihpbnQpKTsKICAgIHNsID0gaW5pdF9saXN0KDQpOwoKICAgIGZvciAoaSA9IDA7IGkgPCB0OyBpKyspIHsKICAgICAgICBhZGQoc2wsIChudW1zW2ldID0gaSksIGkpOwogICAgICAgIHByaW50ZigiYWRkICVkXG4iLCBudW1zW2ldKTsKICAgICAgICBwcmludF9saXN0KHNsKTsKICAgIH0KCiAgICBmb3IgKGkgPSB0IC0gMTsgMSA8PSBpOyBpLS0pIHsKICAgICAgICBwcmludGYoImRlbGV0ZSAlZFxuIiwgZGVsZXRlKHNsLCBudW1zW2ldKSk7CiAgICAgICAgcHJpbnRfbGlzdChzbCk7CiAgICB9CgogICAgZnJlZShudW1zKTsKICAgIGZyZWVfbGlzdChzbCk7CiAgICBleGl0KDApOwogICAgcmV0dXJuIDA7Cn0=