Skip list implementation in C99

skip_list.c

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <stdbool.h>
#include <string.h>
#include <inttypes.h>
#include <assert.h>

static inline uint8_t first_bit_set(uint32_t bits) {
#if defined(__GNUC__) || defined(__clang__)
    return __builtin_ctz(bits);
#else
    if (bits & 1)
        return 0;
    size_t index = 1;
    if ((bits & 0xFFFF) == 0) {
        index += 16;
        bits >>= 16;
    }
    if ((bits & 0xFF) == 0) {
        index += 8;
        bits >>= 8;
    }
    if ((bits & 0xF) == 0) {
        index += 4;
        bits >>= 4;
    }
    if ((bits & 0x3) == 0) {
        index += 2;
        bits >>= 2;
    }
    return index - (bits & 0x1);
#endif
}

#define SLIST_MAX_LEVELS 32

#define FORALL_SLIST(slist, value_t, val, ...) \
    { \
        node_t* node = slist->levels[SLIST_MAX_LEVELS - 1]; \
        while (node) { \
            value_t val = node->value; \
            __VA_ARGS__ \
            node = node->levels[node->nlevels - 1]; \
        } \
    }

typedef uint32_t value_t;
typedef struct pcg_s pcg_t;
typedef struct slist_s slist_t;
typedef struct node_s node_t;

struct pcg_s {
    uint64_t state;
    uint64_t inc;
};

struct node_s {
    value_t value;
    uint8_t nlevels;
    node_t* levels[1];
};

struct slist_s {
    size_t nelems;
    pcg_t pcg;
    node_t* levels[SLIST_MAX_LEVELS];
};

static inline pcg_t pcg_init(void) {
    return (pcg_t) { UINT64_C(0x853C49E6748FEA9B), UINT64_C(0xDA3E39CB94B95BDB) };
}

static inline uint32_t pcg_rand(pcg_t* pcg) {
    uint64_t old = pcg->state;
    pcg->state = old * UINT64_C(6364136223846793005) + (pcg->inc | 1);
    uint32_t xs  = ((old >> 18u) ^ old) >> 27u;
    uint32_t rot = old >> 59u;
    return (xs >> rot) | (xs << ((-rot) & 31));
}

static inline bool cmplt(const value_t* a, const value_t* b) {
    return *a < *b;
}

static inline bool cmpeq(const value_t* a, const value_t* b) {
    return *a == *b;
}

static inline uint8_t slist_level(slist_t* slist) {
    return (first_bit_set(pcg_rand(&slist->pcg)) & (SLIST_MAX_LEVELS - 1)) + 1;
}

static size_t total_levels = 0;

static inline node_t* slist_alloc(slist_t* slist, uint8_t level) {
    total_levels += level;
    node_t* node = malloc(sizeof(node_t) + sizeof(node_t*) * (level - 1));
    node->nlevels = level;
    return node;
}

static inline bool slist_insert(slist_t* slist, const value_t* value) {
    node_t** stack[SLIST_MAX_LEVELS];
    node_t** levels = slist->levels;
    uint8_t level = 0;
    uint8_t target = slist_level(slist);
    while (true) {
        while (!levels[level] || cmplt(value, &levels[level]->value)) {
            stack[level] = &levels[level];
            if (++level >= SLIST_MAX_LEVELS)
                goto end;
        }
        if (cmpeq(&levels[level]->value, value))
            return false;
        levels = levels[level]->levels - (SLIST_MAX_LEVELS - levels[level]->nlevels);
    }
end:
    assert(target > 0 && target <= SLIST_MAX_LEVELS);
    node_t* node = slist_alloc(slist, target);
    memcpy(&node->value, value, sizeof(value_t));
    for (uint8_t i = 0; i < target; ++i) {
        node->levels[i] = *stack[i + SLIST_MAX_LEVELS - target];
        *stack[i + SLIST_MAX_LEVELS - target] = node;
    }
    slist->nelems++;
    return true;
}

static inline value_t* slist_search(slist_t* slist, const value_t* value) {
    uint8_t level = 0;
    node_t** levels = slist->levels;
    while (true) {
        while (!levels[level] || cmplt(value, &levels[level]->value)) {
            if (++level >= SLIST_MAX_LEVELS)
                return NULL;
        }
        if (cmpeq(&levels[level]->value, value))
            return &levels[level]->value;
        levels = levels[level]->levels - (SLIST_MAX_LEVELS - levels[level]->nlevels);
    }
    return NULL;
}

static inline slist_t* slist_create(void) {
    slist_t* slist = malloc(sizeof(slist_t));
    slist->nelems = 0;
    slist->pcg = pcg_init();
    memset(slist->levels, 0, sizeof(node_t*) * SLIST_MAX_LEVELS);
    return slist;
}

int main() {
    /*size_t c = 0;
    for (uint32_t i = 0; i < 0xFFFFFFFF; ++i) {
        uint32_t a = __builtin_ctz(i);
        uint32_t b = ffs(i);
        if (a != b) {
            printf("%d: %d -- %d\n", i, a, b);
            break;
        }
    }
    for (uint32_t i = 0; i < 0xFFFFFFFF; ++i) {
        c += ffs(i);
    }
    return c;*/
    slist_t* slist = slist_create();
    size_t N = 100000, M = 100, P = 100;
    for (size_t j = 0; j < M; ++j) {
        pcg_t pcg = pcg_init();
        for (size_t i = 0; i < N; ++i) {
            value_t val = pcg_rand(&pcg) % N;
            slist_insert(slist, &val);
        }
    }
    size_t count = 0;
    for (size_t j = 0; j < P; ++j) {
        for (size_t i = 0; i < N; ++i) {
           value_t val = i; count += slist_search(slist, &val) != NULL;
        }
    }
    if (N < 100) {
        FORALL_SLIST(slist, value_t, value, {
            printf("%"PRIu32" ", value);
        })
        printf("\n");
    }
    printf("%zu found, %zu element(s), %f levels per node\n", count, slist->nelems, (double)total_levels / (double)slist->nelems);
    return count;
}