Skip to content

Instantly share code, notes, and snippets.

@slofurno
Created September 24, 2015 02:05
Show Gist options
  • Save slofurno/1dcc79ae101731330772 to your computer and use it in GitHub Desktop.
Save slofurno/1dcc79ae101731330772 to your computer and use it in GitHub Desktop.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment