implementation of skip list in c

skip_list.c

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

#define MAXLEVEL 7

typedef struct node{
	int key;
	int value;
	struct node **next;
}slNode;


typedef struct skip_list{
	int     level;
	slNode  *head;
}slList;


slList * create_list(){
	slList *sl = malloc(sizeof(struct skip_list));
	if(sl == NULL)
		return NULL;

	sl->level = 0;

	slNode *header = malloc(sizeof(struct node));
	header->next = malloc(sizeof(struct node *) * MAXLEVEL);
    header->key = 0;
	header->value = 0;

	sl->head = header;

	int i;

	for(i = 0; i< MAXLEVEL; i++){
		header->next[i] = NULL;
	}

	srand(time(NULL));

	return sl;
}

int randomLevel(){
	int level = 1;
	while(rand() % 2)
		level++;
	
	level=(MAXLEVEL > level) ? level: MAXLEVEL;
	
	return level;
}

slNode *create_node(int level,int key, int value){
	slNode *p = malloc(sizeof(struct node));
	if(p == NULL)
		return NULL;
	p->next = malloc(sizeof(struct node *) * level);
	if(p->next == NULL)
		return NULL;
	p->value = value;
	p->key  =key;

	return p;
		
}


int insert(slList *sl, int key, int value){
	slNode *update[MAXLEVEL];
	slNode *q = NULL, *p = sl->head;
	int i = sl->level -1;

	for(; i>= 0; i--){
		while((q=p->next[i]) && q->key < key)
			p = q;
		update[i] = p; //find a first suitable place to insert
	}

	if(q && q->key == key){ //key has exsist
		q->value = value;
		return 1;
	}

	/*generate a random level*/
	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, key, value);
	if(q == NULL)
		return 0;

	for(i = level-1; i>=0; i--){
		q->next[i] = update[i]->next[i];
		update[i]->next[i] = q;
	}

	return 1;

}

int *search(slList *sl, int key){
	slNode *q, *p = sl->head;

	q= NULL;
	int i = sl->level -1;

	for(; i >= 0; i--){
		while((q=p->next[i]) && q->key < key){
			p = q;
		}

		if(q && key == q->key)
			return &(q->value);
	}

	return NULL;
}

int deleteNode(slList *sl, int key){
	slNode *update[MAXLEVEL];
	slNode *q=NULL, *p= sl->head;
	int i = sl->level - 1;

	for(; i >= 0; i--){
		while((q=p->next[i]) && q->key < key){
			p = q;
		}

		update[i] = p;
	}

	if(!q || (q && q->key != key))
		return 0;

	for(i = sl->level -1; 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 1;
}

void sl_free(slList *sl){
	if(sl == NULL)
		return;

	slNode *q = sl->head;
	slNode *next;

	while(q){
		next= q->next[0];
		free(q);
		q = next;
	}

	free(sl);
}

void sl_dump(slList *sl){
	int i;
	slNode *head = sl->head;
	slNode *p = NULL;

	for(i = sl->level-1; i >= 0; i--){
		p = head->next[i];
		printf("level %d: ", i);
		while(p != NULL){
			printf("%d  ",p->value);
			p = p->next[i];
		}
		printf("\n");
	}

}


int main(){
	int arr[] = {1,2,3,4,5,6,7,43,2,56,89,100};

	slList *sl = create_list();
	int i;

	for(i = 0; i <sizeof(arr)/sizeof(arr[0]); i++)
		insert(sl,arr[i],arr[i]);

	sl_dump(sl);
	printf("Search %d\n", *search(sl,56));

	sl_free(sl);

	return 0;
}