sl.c

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

unsigned char rndtable[256] = {
    0,   8, 109, 220, 222, 241, 149, 107,  75, 248, 254, 140,  16,  66 ,
    74,  21, 211,  47,  80, 242, 154,  27, 205, 128, 161,  89,  77,  36 ,
    95, 110,  85,  48, 212, 140, 211, 249,  22,  79, 200,  50,  28, 188 ,
    52, 140, 202, 120,  68, 145,  62,  70, 184, 190,  91, 197, 152, 224 ,
    149, 104,  25, 178, 252, 182, 202, 182, 141, 197,   4,  81, 181, 242 ,
    145,  42,  39, 227, 156, 198, 225, 193, 219,  93, 122, 175, 249,   0 ,
    175, 143,  70, 239,  46, 246, 163,  53, 163, 109, 168, 135,   2, 235 ,
    25,  92,  20, 145, 138,  77,  69, 166,  78, 176, 173, 212, 166, 113 ,
    94, 161,  41,  50, 239,  49, 111, 164,  70,  60,   2,  37, 171,  75 ,
    136, 156,  11,  56,  42, 146, 138, 229,  73, 146,  77,  61,  98, 196 ,
    135, 106,  63, 197, 195,  86,  96, 203, 113, 101, 170, 247, 181, 113 ,
    80, 250, 108,   7, 255, 237, 129, 226,  79, 107, 112, 166, 103, 241 ,
    24, 223, 239, 120, 198,  58,  60,  82, 128,   3, 184,  66, 143, 224 ,
    145, 224,  81, 206, 163,  45,  63,  90, 168, 114,  59,  33, 159,  95 ,
    28, 139, 123,  98, 125, 196,  15,  70, 194, 253,  54,  14, 109, 226 ,
    71,  17, 161,  93, 186,  87, 244, 138,  20,  52, 123, 251,  26,  36 ,
    17,  46,  52, 231, 232,  76,  31, 221,  84,  37, 216, 165, 212, 106 ,
    197, 242,  98,  43,  39, 175, 254, 145, 190,  84, 118, 222, 187, 136 ,
    120, 163, 236, 249
};

int rndindex = 0;

double nextRandom (void)
{
    rndindex = (rndindex+1)&0xff;
    double result = rndtable[rndindex]/255.0;
    printf("%G\n", result);
    return result;
}

typedef struct Node{
  struct Node** nodes;
  char* value;
  char* key;

} Node;

typedef struct SkipList{
  Node* head;
  int height;

} SkipList;

int SkipListAdd(SkipList *skiplist, char *key, char *value){

  Node *node = malloc(sizeof(Node));
  node->key=key;
  node->value=value;
  //Node *node = malloc(sizeof(Node));
  int oldheight = skiplist->height;
  //printf("%d\n", oldheight);
  Node *leadingNodes[oldheight];// = malloc(sizeof(Node*)*oldheight);

  Node *current = skiplist->head;
  int i;
  for(i = oldheight-1;i>=0;i--){
    while(current->nodes[i]!=NULL &&strcmp(node->key, current->nodes[i]->key)<0){
      printf("%s greater than %s\n",current->nodes[i]->key,node->key );
      current=current->nodes[i];
    }
    leadingNodes[i]=current;

  }



  int height = 1;
  while(height<oldheight+1 &&nextRandom()>=0.5){
    //printf("%s\n", "bigger");
    height+=1;
  }

  int upheight = height;
  if (height>oldheight){

  }
  printf("new height now %d\n", height);
  node->nodes = malloc(sizeof(Node*)*height);

  if (height>oldheight){
    skiplist->height=height;
    skiplist->head->nodes[height-1]=node;
    node->nodes[height-1]=NULL;
    upheight=oldheight;
  }

  for(i=0;i<upheight;i++){
    node->nodes[i]=leadingNodes[i]->nodes[i];
    leadingNodes[i]->nodes[i]=node;
  }  

}

int main(){

  Node node1;
  Node node2;
  Node head;

  SkipList skiplist;
  skiplist.head=&head;
  skiplist.height=1;
  head.nodes = malloc(sizeof(Node*)*20);
  head.value="";

  char *key1="aaa";
  char *value1="value1";

  char *key2="bbb";
  char *value2="value2";

  char *key3="ccc";
  char *value3="value3";

  char *key4="ddd";
  char *value4="value4";

  char *key5="eee";
  char *value5="value5";

  char *key6="fff";
  char *value6="value6";

  SkipListAdd(&skiplist, key6, value1);
  SkipListAdd(&skiplist, key5, value2);
  SkipListAdd(&skiplist, key4, value3);
  SkipListAdd(&skiplist, key3, value4);
  SkipListAdd(&skiplist, key2, value5);
  SkipListAdd(&skiplist, key1, value6);

  int i;
  int j;

  Node *current;

  printf("%s\n","----------");

  for (i = skiplist.height-1; i >=0; --i)
  {
    current = skiplist.head;
    while(current!=NULL){
      printf(" %s ",current->key);
      current=current->nodes[i];
    }
    printf("\n");
  }

  return 0;
}