#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#define ALLOW_REINSERT
//#define DEBUG
// Calculates log2 of number.
double Log2( double n )
{
// log(n)/log(2) is log2.
return log( n ) / log( 2 );
}
typedef struct ValueState {
int value;
unsigned char error_state;
} valuestate;
typedef struct SkipList {
char *key;
int value;
int m;
int *span;
struct SkipList **next;
} skiplist;
typedef struct SkipRanks {
int m;
skiplist **p;
int *ranks;
} skipranks;
skiplist *init(int size);
valuestate lookup(skiplist *list, char *key);
void assign(skiplist *list, char *key, int value);
skiplist **skip(skiplist *list, char *key);
skipranks skip_with_ranks(skiplist *list, char *key);
int insert(skiplist *list, char *key, int value);
int delete(skiplist *list, char *key);
skiplist *succ(skiplist *x);
void dump_skip_list(skiplist *list);
void free_skip_list(skiplist *list);
skiplist *init(int size) {
int i;
skiplist *list = (skiplist *)malloc(sizeof(skiplist) * size);
list->m = (int)ceil(Log2((double)size)) + 1;
list->span = (int *)malloc(sizeof(int) * list->m);
list->next = (skiplist **)malloc(sizeof(skiplist *) * list->m);
list->key = 0;
for (i = 0; i < list->m; i++) {
list->next[i] = NULL;
list->span[i] = 0;
}
return list;
}
valuestate lookup(skiplist *list, char *key) {
skiplist **p = skip(list, key);
skiplist *x = succ(p[0]);
free(p);
if (x == NULL || strcmp(x->key, key)) {
valuestate vs = {0, 1};
return vs;
} else {
valuestate vs = {x->value, 0};
return vs;
}
}
valuestate rank(skiplist *list, char *key) {
skiplist **p = (skiplist **)malloc(sizeof(skiplist *) * list->m);
skiplist *x = list;
int i;
int rank = 0;
for (i = list->m - 1; i >= 0; i--) {
while (x->next[i] != NULL && strcmp(key, x->next[i]->key) > 0) {
rank += x->span[i];
x = x->next[i];
}
p[i] = x;
}
x = succ(p[0]);
free(p);
if (x == NULL || strcmp(x->key, key)) {
valuestate vs = {0, 1};
return vs;
} else {
valuestate vs = {rank, 0};
return vs;
}
}
int insert(skiplist *list, char *key, int value) {
#ifdef DEBUG
char fence_line[] = "--------------------------------------------------";
printf("%s\n%s\n", fence_line, fence_line);
printf("Inserting \"%s\" key.\n", key);
dump_skip_list(list);
#endif
int error_state = 0;
skipranks sr = skip_with_ranks(list, key);
if (sr.p[0]->next[0] != NULL && !strcmp(sr.p[0]->next[0]->key, key)) {
#ifdef ALLOW_REINSERT
sr.p[0]->next[0]->value = value;
#else
printf("Wow! Such a fail! Reinsert forbidden!\n");
error_state = 1;
#endif
return error_state;
}
skiplist *x = (skiplist *)malloc(sizeof(skiplist));
x->value = value;
x->key = (char *)malloc(sizeof(char) * strlen(key));
strcpy(x->key, key);
x->span = (int *)malloc(sizeof(int) * list->m);
x->next = (skiplist **)malloc(sizeof(skiplist *) * list->m);
x->m = list->m;
int i;
for (i = 0; i < list->m; i++) {
x->next[i] = NULL;
x->span[i] = 0;
}
int x_rank = sr.ranks[0] + 1;
#ifdef DEBUG
printf("ranks:\n");
for (i = 0; i < list->m; i++)
printf("%d\t", sr.ranks[i]);
printf("\n");
printf(" rank: %d", x_rank);
#endif
i = 0;
long r = rand() * 2;
while (i < list->m && r%2 == 0) {
int delta = x_rank - sr.ranks[i];
if (sr.p[i]->next[i] == NULL) {
x->span[i] = 0;
} else {
if (sr.p[i]->span[i]) {
x->span[i] = sr.p[i]->span[i] - delta + 1;
}
}
sr.p[i]->span[i] = delta;
x->next[i] = sr.p[i]->next[i];
sr.p[i]->next[i] = x;
i++;
r >>= 2;
}
while (i < list->m) {
x->next[i] = NULL;
i++;
}
#ifdef DEBUG
printf("%s\n", fence_line);
printf("After inserting \"%s\" key.\n", key);
dump_skip_list(list);
printf("%s\n\n", fence_line);
#endif
free(sr.p);
free(sr.ranks);
return error_state;
}
int delete(skiplist *list, char *key) {
#ifdef DEBUG
char fence_line[] = "--------------------------------------------------";
printf("%s\n%s\n", fence_line, fence_line);
printf("Deleting \"%s\" key.\n", key);
dump_skip_list(list);
#endif
int error_state = 0;
skiplist **p = skip(list, key);
skiplist *x = succ(p[0]);
if (x == NULL || strcmp(x->key, key)) {
error_state = 1;
} else {
int i = 0;
for (i = 0; i < x->m; i++) {
p[i]->next[i] = x->next[i];
if (x->span[i]) {
p[i]->span[i] += x->span[i] - 1;
} else {
p[i]->span[i] = 0;
}
}
free(x->key);
free(x->next);
free(x->span);
free(x);
}
#ifdef DEBUG
printf("%s\n", fence_line);
printf("After deleting \"%s\" key.\n", key);
dump_skip_list(list);
printf("%s\n\n", fence_line);
#endif
free(p);
return error_state;
}
skipranks skip_with_ranks(skiplist *list, char *key) {
skipranks sr;
sr.m = list->m;
sr.p = (skiplist **)malloc(sizeof(skiplist *) * list->m);
sr.ranks = (int *)malloc(sizeof(int) * list->m);
skiplist *x = list;
int i;
for (i = list->m - 1; i >= 0; i--) {
int skip_rank = 0;
while (x->next[i] != NULL && strcmp(key, x->next[i]->key) > 0) {
skip_rank = x->span[i];
x = x->next[i];
sr.ranks[i] += skip_rank;
}
if (i < list->m - 1) {
sr.ranks[i] += sr.ranks[i+1];
}
sr.p[i] = x;
}
return sr;
}
skiplist **skip(skiplist *list, char *key) {
skiplist **p = (skiplist **)malloc(sizeof(skiplist *) * list->m);
skiplist *x = list;
int i;
for (i = list->m - 1; i >= 0; i--) {
while (x->next[i] != NULL && strcmp(key, x->next[i]->key) > 0) {
x = x->next[i];
}
p[i] = x;
}
return p;
}
void dump_skip_list(skiplist *list) {
char hole[] = "-------";
skiplist *x = list;
int length = 0;
while (x != NULL) {
length++;
x = x->next[0];
}
skiplist **items = (skiplist **)malloc(sizeof(skiplist *) * length);
x = list;
int i = 0;
while (x != NULL) {
items[i] = x;
x = x->next[0];
i++;
}
int j;
for (j = list->m - 1; j >= 0; j--) {
skiplist *current = list;
printf("(%-7s, v=%d, sp=%d) -> ", "<<init>>", list->value, list->span[j]);
for (i = 1; i < length; i++) {
char *filler;
int val = 0;
int span = 0;
if (current->next[j] == items[i]) {
current = items[i];
filler = items[i]->key;
val = items[i]->value;
span = items[i]->span[j];
} else {
filler = hole;
val = 0;
span = items[i]->span[j];
}
printf("(%-7s, v=%d, sp=%d) -> ", filler, val, span);
}
printf("NULL\n");
}
free(items);
}
void free_skip_list(skiplist *list) {
skiplist *next;
while(list != NULL) {
next = list->next[0];
if (list->key)
free(list->key);
free(list->next);
free(list->span);
free(list);
list = 0;
list = next;
}
}
skiplist *succ(skiplist *x) {
return x->next[0];
}
int ITEMS = 8;
int main(int argc, char const *argv[])
{
char *names[] = { "cabbage", "apple", "banana", "honey", "dessert", "fromage", "egg", "guava" };
int values[] = {0, 1, 2, 3, 4, 5, 6, 7};
int idx = 2;
if (argc == 2) {
idx = atoi(argv[1]);
}
skiplist *dict = init(ITEMS);
int i = 0;
//printf("1\n");
for (i = 0; i < ITEMS; i++)
insert(dict, names[i], values[i]);
//int idx = 1;
for (i = 0; i < ITEMS; i++) {
valuestate vs = lookup(dict, names[i]);
if (!vs.error_state) {
printf("Key \"%-7s\" exists! Here is value: %d\n", names[i], vs.value);
valuestate rs = rank(dict, names[i]);
if (!rs.error_state) {
printf("It's rank is %-7d\n", rs.value);
}
} else {
printf("Sorry, I can't find key \"%-12s\" in dict :(\n", names[i]);
}
}
dump_skip_list(dict);
int del_idx = 6;
printf("Trying to delete \"%s\" key:\n", names[del_idx]);
int err_state = delete(dict, names[del_idx]);
if (!err_state) {
printf("\"%s\" deleted.\n", names[del_idx]);
} else {
printf("There is no key \"%s\" in dict\n", names[del_idx]);
}
printf("\n Dict after \"%s\" key deleted:", names[del_idx]);
dump_skip_list(dict);
printf("\nDelete all keys (and one of them is missed):\n");
for (i = ITEMS - 1; i >= 0; i--) {
printf("Trying to delete \"%s\" key:\n", names[i]);
int err_state = delete(dict, names[i]);
if (!err_state) {
printf("\"%s\" deleted.\n", names[i]);
} else {
printf("There is no key \"%s\" in dict\n", names[i]);
}
}
printf("\n Dict aster all entries deleted.\n");
dump_skip_list(dict);
free_skip_list(dict);
return 0;
}