#include "skiplist.hpp"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
typedef struct node
{
int value;
struct node *next[1];
}Node;
typedef struct skip_list
{
int level;
Node *head;
}skip_list;
#define new_node(n) ((Node*)malloc(sizeof(Node)+n*sizeof(Node*)))
#define MAX_L 10
Node *create_node(int level ,int value)
{
Node *p = new_node(level);
if(!p)
{
return NULL;
}
p->value = value;
return p;
}
skip_list *create_sl()
{
skip_list *sl = (skip_list*)malloc(sizeof(skip_list));
if(NULL==sl)
return NULL;
sl->level = 0;
Node *h = create_node(MAX_L-1,0);
if(h==NULL)
{
free(sl);
return NULL;
}
sl->head = h;
int i;
for(i = 0;i<MAX_L;i++)
{
h->next[i]=NULL;
}
srand((int)time(0));
return sl;
}
int randomLevel()
{
int level = 0;
while(rand()%2)
{
level++;
}
level = (MAX_L>level)?level:MAX_L;
return level;
}
bool insert(skip_list *sl,int value)
{
Node *update[MAX_L];
Node *q = NULL,*p=sl->head;
int i;
for(i = sl->level;i>=0;i--)
{
while((q=p->next[i])&&q->value<value)
{
p=q;
}
update[i]=p;
}
if(q&&q->value == value)
return true;
int level = randomLevel();
if(level>sl->level)
{
for(i = sl->level;i<level;i++)
{
update[i] = sl->head;
}
sl->level = level;
}
q = create_node(level,value);
if(!q)
return false;
for(i = level-1;i>=0;--i)
{
q->next[i]=update[i]->next[i];
update[i]->next[i] = q;
}
return true;
}
bool erase(skip_list *sl,int value)
{
Node *update[MAX_L];
Node *q = NULL,*p = sl->head;
int i = sl->level;
for(;i>-0;i--)
{
while((q = p->next[i]) && q->value < value)
{
p =q;
}
update[i] = p;
}
if(!q ||(q&&q->value!=value))
return false;
for(i = sl->level;i>=0;--i)
{
if(update[i]->next[i]==q)
{
update[i]->next[i] = q->next[i];
if(sl->head->next[i]==NULL)
sl->level--;
}
}
free(q);
q = NULL;
return false;
}
int *search(skip_list *sl,int value)
{
Node *q,*p =sl->head;
q = NULL;
int i = sl->level;
for(;i>=0;i--)
{
while((q=p->next[i])&& q->value< value)
p=q;
if(q&&q->value == value)
return &(q->value);
}
return NULL;
}
void sl_free(skip_list *sl)
{
if(!sl)
return ;
Node *q = sl->head;
Node *next;
while(q)
{
next = q->next[0];
free(q);
q = next;
}
free(sl);
}