skiplist/skiplist.h

#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