93 lines
2.3 KiB
C
93 lines
2.3 KiB
C
#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
|
|
|