a simple skiplist implementation

skiplist.h

//author liulijin<llj098@gmail.com>
//licence New BSD

#ifndef __SKIPLIST_H_
#define __SKIPLIST_H_


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

#define SK_DEFAULE_LEVEL 5
#define D(x) printf("DEBUG:%s\n",(x))

typedef struct sk_node_s{
  int key;
  void *value;
  struct sk_node_s *upfloor;
  struct sk_node_s *downfloor;
  struct sk_node_s *next;
}sk_node_t;

typedef struct skiplist_s{
  int level;
  sk_node_t *high;
  int count;
}skiplist_t;

inline sk_node_t* sk_node_new(int k,void* v)
{
  sk_node_t *node = malloc(sizeof(*node));
  if(node){
    node->key = k;
    node->value = v;
  }

  return node;
}

inline int 
sk_node_append(sk_node_t *n,sk_node_t *prev,sk_node_t *up)
{
  n->next = prev->next;
  prev->next = n;

  if(up){
    up->downfloor = n;
  }
}

skiplist_t* sk_new()
{
  int i;

  skiplist_t *list = malloc(sizeof(*list));
  list->level = SK_DEFAULE_LEVEL;

  for(i=0;i<SK_DEFAULE_LEVEL;i++) {

    sk_node_t *node = sk_node_new(-1,NULL);

    if(!node)
      return NULL;

    node->downfloor = list->high;

    if(list->high)
      list->high->upfloor = node;
    list->high = node;
  }
  

  return list;
}


void*
sk_find(skiplist_t *list,int k)
{
  if(list == NULL || list->count <= 0 || k <0)
    return NULL;


  int c,n = -1,i =0;
  sk_node_t *node,*prev;
  node = list->high;
  
  while(i < SK_DEFAULE_LEVEL){

    prev = node;

    while(node){
      c = node->key;

      if(c == k)
	return node->value;

      if(k < c){
	node = prev;
	break;
      }

      prev = node;
      node = node->next;
    }
 
    node = prev->downfloor;
    i++;
  }
  
  return NULL;
}



int
sk_insert(skiplist_t *list,int k,void *v)
{
  if(list == NULL || list->count <= 0 || k <0)
    return -1;

  int c,i,level  = k % SK_DEFAULE_LEVEL;
  sk_node_t *inserted,*new,*prev,*node = list->high;

  for(i=0;i<level;i++){node=node->downfloor;}
  i = SK_DEFAULE_LEVEL - level;
  inserted = NULL;

  while((i--)>0) {

    while(node){

      new = NULL;
      prev = node;
      c = node->key;
      
      if(k == c)
	return -2;//same key is not allow

      if(!node->next){//last?
	new = sk_node_new(k,v);
	sk_node_append(new,node,inserted);
	break;
      }
      
      if(c > k){// append after prev
	new = sk_node_new(k,v);
	sk_node_append(new,prev,inserted);
	break;
      }

      prev = node;
      node = node->next;
    }

    if(new){
      inserted = new;
    }

    node = prev->downfloor;
  }

  list->count++;
  return 1;
}

 
#endif