------------------------------ skiplist.h ------------------------------
#ifndef _OLIO_SKIPLIST_H_
#define _OLIO_SKIPLIST_H_
#include <inttypes.h>
/* a skiplist sorted array with logarithmic behavior for searches, inserts, and deletes.
* similar to a b-tree, but a simpler algorithm.
* the current implementation uses a simple, static height increment on key addition,
* and this assumes that the entry keys are added with either:
* 1) a generally sequential pattern, or
* 2) a random pattern
*
* TODO: top-down deterministic height management. a bit more complicated, and hasn't
* been necessary yet.
* Munro, J et al. "Deterministic Skip Lists." Proc. ACM-SIAM Symposium on Discrete Algo. 1992
*/
/* maximum height the skiplist can grow to */
#define OLIO_SKIPLIST_MAX_HEIGHT 16
/* height is built up geometrically with this base */
#define OLIO_SKIPLIST_HIGHER_EVERY 4
typedef struct _olio_skiplist_entry {
struct _olio_skiplist_entry * next;
void * data;
uint32_t key;
} olio_skiplist_entry;
typedef struct _olio_skiplist {
struct _olio_skiplist_entry heads[OLIO_SKIPLIST_MAX_HEIGHT];
uint32_t count;
uint8_t height;
} olio_skiplist;
#ifdef __cplusplus
extern "C" {
#endif
/* basic init/free functions for the skiplist */
void olio_skiplist_init(olio_skiplist *);
void olio_skiplist_free(olio_skiplist *);
/* find the entry for a particular key */
void * olio_skiplist_find(olio_skiplist *, uint32_t key);
/* prepare for a sequential search, with keys >= key */
void olio_skiplist_range_begin(olio_skiplist *, uint32_t key, void ** opaque);
/* iterate on the sequential search, with keys <= mkey */
void * olio_skiplist_range_next(olio_skiplist *, uint32_t mkey,
uint32_t * ckey, void ** opaque);
/* add an entry to the skiplist */
int olio_skiplist_add(olio_skiplist *, uint32_t key, void * data);
#ifdef OLIO_DEBUG
/* show the entries (and keys) at each height level */
void olio_skiplist_display(olio_skiplist * sk);
#endif
#ifdef __cplusplus
} /* extern C */
#endif
#endif /* _OLIO_SKIPLIST_H_ */
------------------------------ skiplist.c ------------------------------
#include <stdlib.h>
#include "skiplist.h"
void olio_skiplist_init(olio_skiplist * sk)
{
int i;
/* initialize the lowest height head */
sk->heads[0].next = NULL;
sk->heads[0].key = 0xffffffff;
sk->heads[0].data = NULL;
/* initialize higher level heads */
for (i = 1; i < OLIO_SKIPLIST_MAX_HEIGHT; i++) {
sk->heads[i].next = NULL;
sk->heads[i].key = 0xffffffff;
/* the head's data is the head below it */
sk->heads[i].data = &sk->heads[i-1];
}
/* count of items */
sk->count = 0;
/* how much height is the skip list using */
sk->height = 1;
}
void olio_skiplist_free(olio_skiplist * sk)
{
olio_skiplist_entry * a;
olio_skiplist_entry * b;
int i;
for (i = 0; i < OLIO_SKIPLIST_MAX_HEIGHT; i++) {
/* for each head, free everything on that level */
a = sk->heads[i].next;
while (a != NULL) {
b = a->next;
free(a);
a = b;
}
sk->heads[i].next = NULL;
}
/* reset to initialized state */
sk->count = 0;
sk->height = 1;
}
void * olio_skiplist_find(olio_skiplist * sk, uint32_t key)
{
/* use the current height to skip past unused layers */
void * el = &sk->heads[sk->height-1];
olio_skiplist_entry * h = NULL;
uint8_t cd = sk->height;
/* while we are above the data (bottom-most) layer */
while (cd > 0) {
/* previous el is the entry for this level */
h = (olio_skiplist_entry *) el;
/* skip along this level until we would exceed our key */
while (h->next != NULL && h->next->key <= key)
h = h->next;
/* store el with this entry's data */
el = h->data;
/* next level down... */
cd--;
}
/* make sure we have an entry with a matching key */
if (h->key != key)
return NULL;
return el;
}
/* set up for a range search, >= key */
void olio_skiplist_range_begin(olio_skiplist * sk, uint32_t key,
void ** opaque)
{
/* use the current height to skip past unused layers */
void * el = &sk->heads[sk->height-1];
olio_skiplist_entry * h = NULL;
uint8_t cd = sk->height;
/* while we are above the data (bottom-most) layer */
while (cd > 0) {
/* previous el is the entry for this level */
h = (olio_skiplist_entry *) el;
/* skip along this level until we would exceed our key */
while (h->next != NULL && h->next->key <= key)
h = h->next;
/* store el with this entry's data */
el = h->data;
/* next level down... */
cd--;
}
/* if we have don't match the key, we want the next entry */
if (h->key != key)
*opaque = h->next;
else
*opaque = h;
}
/* iterator for range search, <= mkey */
void * olio_skiplist_range_next(olio_skiplist * sk, uint32_t mkey,
uint32_t * ckey, void ** opaque)
{
olio_skiplist_entry * h = (olio_skiplist_entry *) (*opaque);
if (h == NULL) return NULL;
if (h->key > mkey) return NULL;
*ckey = h->key;
*opaque = h->next;
return h->data;
}
int olio_skiplist_add(olio_skiplist * sk, uint32_t key, void * data)
{
/* we need to store the previous entry for each level */
olio_skiplist_entry * path[OLIO_SKIPLIST_MAX_HEIGHT];
/* like the find above, except we have to start from the
* top to record the full path. we can't skip to the first
* used layer */
void * el = &sk->heads[OLIO_SKIPLIST_MAX_HEIGHT-1];
olio_skiplist_entry * h;
uint8_t cd = OLIO_SKIPLIST_MAX_HEIGHT;
uint32_t mm;
/* while we are above the data layer */
while (cd > 0) {
/* previous el is the entry point for this level */
h = (olio_skiplist_entry *) el;
/* skip along this level until we would exceed our key */
while (h->next != NULL && h->next->key <= key)
h = h->next;
/* store this node in our path list */
path[cd-1] = h;
/* store el with this entry's data */
el = h->data;
/* next level down... */
cd--;
}
/* increment the list's entry count */
mm = ++sk->count;
/* now we insert an entry for each applicable layer,
* starting from the bottom */
cd = 0;
/* the first level's data attribute will be set to the
* caller provided data pointer */
el = data;
/* limit of MAX_HEIGHT */
while (cd < OLIO_SKIPLIST_MAX_HEIGHT) {
/* allocated a new entry for this level */
h = (olio_skiplist_entry *)
malloc(sizeof(olio_skiplist_entry));
if (h == NULL) return -1;
/* set the key and data fields */
h->key = key;
h->data = el;
/* insert into the list at the current (cd) level */
h->next = path[cd]->next;
path[cd]->next = h;
/* if count is not a modulus of HIGHER_EVERY,
* break out of the loop */
if (mm % OLIO_SKIPLIST_HIGHER_EVERY) break;
/* it is a modulus, so we'll loop again at
* the next level up. */
/* our temporary count must be shifted down */
mm /= OLIO_SKIPLIST_HIGHER_EVERY;
/* the next entry's data will point to this
* level's entry */
el = h;
cd++;
}
/* reset our max used height, if needed */
if (cd + 1 > sk->height) sk->height = cd + 1;
return 0;
}
#ifdef OLIO_DEBUG
#include <stdio.h>
void olio_skiplist_display(olio_skiplist * sk)
{
olio_skiplist_entry * se;
uint8_t h;
fprintf(stderr, "skiplist:\n");
fprintf(stderr, "count: %lu\n", sk->count);
fprintf(stderr, "height: %u\n", sk->height);
h = sk->height;
while (h > 0) {
fprintf(stderr, " @ height: %u\n", h);
se = &sk->heads[h-1];
while (se != NULL) {
fprintf(stderr, " key: 0x%x\n", se->key);
se = se->next;
}
h--;
}
}
#endif /* OLIO_DEBUG */
