| |
Jump table (skiplist) is a very good data structure is simple, insert, delete, find complexity are O (logN). LevelDB core data structure is implemented jump table, redis sorted set of data structures it is also a jump table implementation.
Find all operations step by step from the top down, the upper span of the larger one next operation. Its implementation is a typical space for time.
Specific details, refer to Wikipedia http://en.wikipedia.org/wiki/Skip_list
The author of the sorted set will redis code sorting, will realize jump table portion extracted for reference.
skiplist.h
#ifndef __SKIPLIST_H
#define __SKIPLIST_H
#define SKIPLIST_MAXLEVEL 8
typedef struct skiplistNode {
double score;
struct skiplistNode * backward;
struct skiplistLevel {
struct skiplistNode * forward;
} Level [];
} SkiplistNode;
typedef struct skiplist {
struct skiplistNode * header, * tail;
unsigned long length;
int level;
} Skiplist;
#endif
skiplist.c
#include "skiplist.h"
#include < stdlib.h>
#include < stdio.h>
skiplistNode * slCreateNode (int level, double score) {
skiplistNode * sn = malloc (sizeof (* sn) + level * sizeof (struct skiplistLevel));
sn-> score = score;
return sn;
}
skiplist * slCreate (void) {
int j;
skiplist * sl;
sl = malloc (sizeof (* sl));
sl-> level = 1;
sl-> length = 0;
sl-> header = slCreateNode (SKIPLIST_MAXLEVEL, 0);
for (j = 0; j < SKIPLIST_MAXLEVEL; j ++) {
sl-> header-> level [j] .forward = NULL;
}
sl-> header-> backward = NULL;
sl-> tail = NULL;
return sl;
}
void slFreeNode (skiplistNode * sn) {
free (sn);
}
void slFree (skiplist * sl) {
skiplistNode * node = sl-> header-> level [0] .forward, * next;
free (sl-> header);
while (node) {
next = node-> level [0] .forward;
slFreeNode (node);
node = next;
}
free (sl);
}
int slRandomLevel (void) {
int level = 1;
while ((rand () & 0xFFFF) < (0.5 * 0xFFFF))
level + = 1;
? Return (level < SKIPLIST_MAXLEVEL) level: SKIPLIST_MAXLEVEL;
}
skiplistNode * slInsert (skiplist * sl, double score) {
skiplistNode * update [SKIPLIST_MAXLEVEL];
skiplistNode * node;
node = sl-> header;
int i, level;
for (i = sl-> level-1; i> = 0; i--) {
while (node-> level [i] .forward && node-> level [i] .forward-> score < score) {
node = node-> level [i] .forward;
}
update [i] = node;
}
level = slRandomLevel ();
if (level> sl-> level) {
for (i = sl-> level; i < level; i ++) {
update [i] = sl-> header;
}
sl-> level = level;
}
node = slCreateNode (level, score);
for (i = 0; i < level; i ++) {
node-> level [i] .forward = update [i] -> level [i] .forward;
update [i] -> level [i] .forward = node;
}
node-> backward = (update [0] == sl-> header NULL:? update [0]);
if (node-> level [0] .forward)
node-> level [0] .forward-> backward = node;
else
sl-> tail = node;
sl-> length ++;
return node;
}
void slDeleteNode (skiplist * sl, skiplistNode * x, skiplistNode ** update) {
int i;
for (i = 0; i < sl-> level; i ++) {
if (update [i] -> level [i] .forward == x) {
update [i] -> level [i] .forward = x-> level [i] .forward;
}
}
if (x-> level [0] .forward) {
x-> level [0] .forward-> backward = x-> backward;
} Else {
sl-> tail = x-> backward;
}
while (sl-> level> 1 && sl-> header-> level [sl-> level-1] .forward == NULL)
sl-> level--;
sl-> length--;
}
int slDelete (skiplist * sl, double score) {
skiplistNode * update [SKIPLIST_MAXLEVEL], * node;
int i;
node = sl-> header;
for (i = sl-> level-1; i> = 0; i--) {
while (node-> level [i] .forward && node-> level [i] .forward-> score < score) {
node = node-> level [i] .forward;
}
update [i] = node;
}
node = node-> level [0] .forward;
if (node && score == node-> score) {
slDeleteNode (sl, node, update);
slFreeNode (node);
return 1;
} Else {
return 0;
}
return 0;
}
int slSearch (skiplist * sl, double score) {
skiplistNode * node;
int i;
node = sl-> header;
for (i = sl-> level-1; i> = 0; i--) {
while (node-> level [i] .forward && node-> level [i] .forward-> score < score) {
node = node-> level [i] .forward;
}
}
node = node-> level [0] .forward;
if (node && score == node-> score) {
printf ( "Found% d \ n", (int) node-> score);
return 1;
} Else {
printf ( "Not found% d \ n", (int) score);
return 0;
}
}
void slPrint (skiplist * sl) {
skiplistNode * node;
int i;
for (i = 0; i < SKIPLIST_MAXLEVEL; i ++) {
printf ( "LEVEL [% d]:", i);
node = sl-> header-> level [i] .forward;
while (node) {
printf ( "% d ->", (int) (node-> score));
node = node-> level [i] .forward;
}
printf ( "NULL \ n");
}
}
#ifdef SKIP_LIST_TEST_MAIN
int main () {
srand ((unsigned) time (0));
int count = 20, i;
printf ( "### Function Test ### \ n");
printf ( "=== Init Skip List === \ n");
skiplist * sl = slCreate ();
for (i = 0; i < count; i ++) {
slInsert (sl, i);
}
printf ( "=== Print Skip List === \ n");
slPrint (sl);
printf ( "=== Search Skip List === \ n");
for (i = 0; i < count; i ++) {
int value = rand ()% (count + 10);
slSearch (sl, value);
}
printf ( "=== Delete Skip List === \ n");
for (i = 0; i < count + 10; i + = 2) {
printf ( "Delete [% d]:% s \ n", i, slDelete (sl, i) "SUCCESS":? "NOT FOUND");
}
slPrint (sl);
slFree (sl);
sl = NULL;
}
#endif
Test results are as follows:
### Function Test ###
=== Init Skip List ===
=== Print Skip List ===
LEVEL [0]: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> NULL
LEVEL [1]: 0 -> 2 -> 4 -> 7 -> 9 -> 10 -> 11 -> 12 -> 14 -> 15 -> 17 -> 18 -> NULL
LEVEL [2]: 7 -> 10 -> 12 -> 14 -> 15 -> NULL
LEVEL [3]: 10 -> 14 -> 15 -> NULL
LEVEL [4]: 10 -> 14 -> NULL
LEVEL [5]: NULL
LEVEL [6]: NULL
LEVEL [7]: NULL
=== Search Skip List ===
Found 1
Found 18
Not found 21
Not found 24
Found 10
Not found 20
Found 14
Found 10
Found 19
Found 18
Not found 27
Found 5
Found 0
Found 0
Found 18
Not found 26
Found 13
Not found 28
Not found 29
Not found 23
=== Delete Skip List ===
Delete [0]: SUCCESS
Delete [2]: SUCCESS
Delete [4]: SUCCESS
Delete [6]: SUCCESS
Delete [8]: SUCCESS
Delete [10]: SUCCESS
Delete [12]: SUCCESS
Delete [14]: SUCCESS
Delete [16]: SUCCESS
Delete [18]: SUCCESS
Delete [20]: NOT FOUND
Delete [22]: NOT FOUND
Delete [24]: NOT FOUND
Delete [26]: NOT FOUND
Delete [28]: NOT FOUND
LEVEL [0]: 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19 -> NULL
LEVEL [1]: 7 -> 9 -> 11 -> 15 -> 17 -> NULL
LEVEL [2]: 7 -> 15 -> NULL
LEVEL [3]: 15 -> NULL
LEVEL [4]: NULL
LEVEL [5]: NULL
LEVEL [6]: NULL
LEVEL [7]: NULL |
|
|
|