Academic example of skip list implementation in C.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

92 lines
2.3 KiB

#ifndef __SKIPLIST
#define __SKIPLIST
#include <inttypes.h>
#include <limits.h>
#include <stdio.h>
#include <sys/types.h>
#define KEY_INF_MIN INT_MIN /* -INFINITY */
#define KEY_INF_MAX INT_MAX /* +INFINITY */
#define SL_ADD_NEW 1 /* added new key */
#define SL_ADD_SAME 0 /* added existing key */
#define SL_ADD_INV -1 /* added invalid key (+-INFINITY) */
#define max(x, y) ((x) > (y) ? (x) : (y))
/* skip list node */
typedef struct skiplist_node {
int key;
void *data;
struct skiplist_node *next;
struct skiplist_node *prev;
struct skiplist_node *below;
struct skiplist_node *above;
} sl_node;
/* skiplist statistics */
typedef struct skiplist_stats {
size_t srchcnt; /* count nodes visited while searching */
size_t rmcnt; /* count nodes visited while removing */
size_t addcnt; /* count nodes visited while adding */
size_t srchnum; /* number of searches */
size_t rmnum; /* number of removals */
size_t addnum; /* number of additions */
size_t maxlen; /* maximum list len */
size_t currsrch; /* nodes visited for current search */
size_t currrm; /* nodes visited for current search */
size_t curradd; /* nodes visited for current search */
size_t srchcntmax; /* max nodes count visited while searching */
size_t rmcntmax; /* max nodes count visited while removing */
size_t addcntmax; /* max nodes count visited while adding */
} slstat;
/* skiplist object */
typedef struct skiplist {
sl_node *topleft;
sl_node *bottomleft;
sl_node *topright;
sl_node *bottomright;
int maxlevel;
size_t len;
slstat stat;
} slist;
/*
* Initialize empty skip list.
*/
void sl_init(slist *sl);
/*
* Free skip list memory. After free list is not initialized
* for subsequent use.
*/
void sl_free(slist *sl);
/*
* Print skip list level by level and in down to up form.
*/
void sl_print(const slist *sl);
/*
* Add new key with data into skip list.
*/
int sl_add(slist *sl, int key, void *data);
/*
* Find node in skip list with given key.
* If key is not found returns NULL.
*/
sl_node *sl_find(slist *sl, int key);
/*
* Remove node from skip list with given key.
* If key is found and removed return 1, otherwise 0.
*/
int sl_remove(slist *sl, int key);
/*
* Print current statistics.
*/
void sl_stat_print(const slist *sl);
#endif