arena_tbl_buf.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <string.h>
#include <stdarg.h>
#include <limits.h>

#define cast(t,p) ((t)(p))
#define szof(a) ((int)sizeof(a))
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define cntof(a) ((int)(sizeof(a)/sizeof((a)[0])))
#define offsetof(st,m) ((int)((uintptr_t)&(((st*)0)->m)))
#define streq(a,b) (strcmp(a,b) == 0)
#define strneq(a,b,n) (strncmp(a,b,n) == 0)
#define alignof(t) ((int)((char*)(&((struct {char c; t _h;}*)0)->_h) - (char*)0))
#define isaligned(x,a) (!((uintptr_t)(x) & ((uintptr_t)(a-1))))
#define align(x,mask) ((void*)(((intptr_t)((const char*)(x)+(mask-1))&~(mask-1))))
#define align_mask(a) ((a)-1)
#define align_down_masked(n,m) ((n) & ~(m))
#define align_down(n,a) align_down_masked(n, align_mask(a))
#define align_up(n,a) align_down((n) + align_mask(a), (a))
#define align_down_ptr(p,a) ((void*)align_down((uintptr_t)(p),(a)))
#define align_up_ptr(p,a) ((void*)align_up((uintptr_t)(p),(a)))

/* ---------------------------------------------------------------------------
 *                                  Array
 * --------------------------------------------------------------------------- */
#define DYN_ALIGN 16
struct dyn_hdr {
    int cnt,cap;
    char buf[];
};

#define dyn__hdr(b) ((struct dyn_hdr*)(void*)((char*)(b) - offsetof(struct dyn_hdr, buf)))
#define dyn__fits(b,n) (dyn_cnt(b) + (n) <= dyn_cap(b))
#define dyn_req_siz(type_size) (sizeof(struct dyn_hdr) + (type_size) + DYN_ALIGN)
#define dyn_cnt(b) ((b) ? dyn__hdr(b)->cnt: 0)
#define dyn_cap(b) ((b) ? abs(dyn__hdr(b)->cap): 0)
#define dyn_begin(b) ((b) + 0)
#define dyn_end(b) ((b) + dyn_cnt(b))
#define dyn_fit(b,n) (dyn__fits((b), (n)) ? 0: ((b) = dyn__grow((b),dyn_cnt(b)+(n), sizeof(*(b)))))
#define dyn__add(b, x) (dyn_fit((b),1), (b)[dyn__hdr(b)->cnt++] = x)
#define dyn_add(b, ...) dyn__add(b, (__VA_ARGS__))
#define dyn_clr(b) ((b) ? dyn__hdr(b)->cnt = 0 : 0)
#define dyn_del(b,i) (dyn_cnt(b) ? (b)[i] = (b)[--dyn_hdr(b)->cnt] : 0)
#define dyn_rm(b,i) (dyn_cnt(b) ? memmove(&(b)[i], &(b)[i+1], (size_t)--dyn_hdr(b)->cnt - i) : 0)
#define dyn_printf(b, fmt, ...) ((b) = dyn__printf((b), (fmt), __VA_ARGS__))
#define dyn_free(b) ((!(b)) ? 0: (dyn__hdr(b)->cap <= 0) ? (b) = 0: (free(dyn__hdr(b)), (b) = 0))

static void*
dyn__grow(void *buf, int new_len, int elem_size)
{
    struct dyn_hdr *hdr = 0;
    int cap = dyn_cap(buf);
    int new_cap = max(2*cap + 1, new_len);
    int new_size = offsetof(struct dyn_hdr, buf) + new_cap*elem_size;
    assert(new_len <= new_cap);
    if (!buf) {
        hdr = calloc(new_size,1);
        hdr->cnt = 0;
    } else if (dyn__hdr(buf)->cap < 0) {
        hdr = malloc(new_size);
        hdr->cnt = dyn_cnt(buf);
        memcpy(hdr->buf, dyn__hdr(buf)->buf, (size_t)(cap*elem_size));
    } else hdr = realloc(dyn__hdr(buf), (size_t)new_size);
    hdr->cap = new_cap;
    return hdr->buf;
}
static void*
dyn__static(void *buf, int n)
{
    void *u = (char*)buf + DYN_ALIGN + sizeof(struct dyn_hdr) - 1;
    void *a = align_down_ptr(u, DYN_ALIGN);
    void *h = (char*)a - sizeof(struct dyn_hdr);

    struct dyn_hdr *hdr = h;
    hdr->cap = -n, hdr->cnt = 0;
    return hdr->buf;
}
static char*
dyn__printf(char *buf, const char *fmt, ...)
{
    int cap, n;
    va_list args;
    va_start(args, fmt);
    cap = dyn_cap(buf) - dyn_cnt(buf);
    n = 1 + vsnprintf(dyn_end(buf), (size_t)cap, fmt, args);
    va_end(args);

    if (n > cap) {
        dyn_fit(buf, n + dyn_cnt(buf));
        va_start(args, fmt);
        int new_cap = dyn_cap(buf) - dyn_cnt(buf);
        n = 1 + vsnprintf(dyn_end(buf), (size_t)new_cap, fmt, args);
        assert(n <= new_cap);
        va_end(args);
    }
    dyn__hdr(buf)->cnt += n - 1;
    return buf;
}

/* ---------------------------------------------------------------------------
 *                                  Set
 * --------------------------------------------------------------------------- */
#define SET_MIN_SIZE 64
#define SET_GROW_FACTOR 2.8f
#define SET_FULL_PERCENT 0.7f
#define SET_MIN_GROW_PERCENT 1.3f
#define SET_DELETED ((uintptr_t)-1)

#define set_cnt(s) dyn_cnt(s)
#define set_cap(s) dyn_cap(s)
#define set_key(k) ((k) != 0u && (k) != SET_DELETED)
#define set_fnd(s,k) (set__fnd(s,k,set_cap(s)) < set_cap(s))
#define set__fits(t, cnt) ((cnt) < (int)((float)set_cap(t) * SET_FULL_PERCENT))
#define set__fit(t, n) (set__fits(t, n) ? 0: ((t) = set__grow(t, n)))
#define set__add(t, k) (set__fit(t, set_cnt(t) + 1), set__put(t, k))
#define set_put(t, k) ((!(t) || !set_fnd(t,k)) ? set__add(t,k): set_cap(t))
#define set_del(s,k) set__del(s,k,set_cap(s))
#define set_free(s) dyn_free(s)
#define set__mod(k,n) ((k) % (n))
#define set_mod(s,k) (!(s) ? -1 : set__mod(k, set_cap(s)))

static intptr_t
set_slot(uintptr_t *t, uintptr_t key, int cap)
{
    uintptr_t n = cast(uintptr_t, cap);
    uintptr_t i = key % n, b = i;
    do {const uintptr_t k = t[i];
        if (set_key(k)) continue;
        else return (intptr_t)i;
    } while ((i = (((i+1) % n))) != b);
    return cap;
}
static uintptr_t*
set_new(int o, int n)
{
    const int nn = max(SET_MIN_SIZE, (int)((float)n * SET_MIN_GROW_PERCENT));
    const int cap = max(nn, cast(int, SET_GROW_FACTOR * cast(float, o)));
    return dyn__grow(0, cap, sizeof(uintptr_t));
}
static intptr_t
set__put(uintptr_t *set, uintptr_t key)
{
    const intptr_t i = set_slot(set, key, set_cap(set));
    if (i < set_cap(set)) {
        dyn__hdr(set)->cnt++;
        set[i] = key;
    } return i;
}
static uintptr_t*
set__grow(uintptr_t *old, int n)
{
    uintptr_t *set = set_new(set_cap(old), n);
    for (int i = 0; i < set_cap(old); ++i)
        if (set_key(old[i]))
            set__put(set, old[i]);
    dyn_free(old);
    return set;
}
static intptr_t
set__fnd(uintptr_t *set, uintptr_t key, int cap)
{
    uintptr_t n = cast(uintptr_t, cap);
    uintptr_t i = key % n, b = i;
    do {uintptr_t k = set[i];
        if (!k) return cap;
        if (k == key) return (intptr_t)i;
    } while ((i = ((i+1) % n)) != b);
    return cap;
}
static intptr_t
set__del(uintptr_t *set, uintptr_t key, int cap)
{
    if (!set_cnt(set)) return cap;
    const intptr_t i = set__fnd(set, key, cap);
    if (i < cap) {
        dyn__hdr(set)->cnt--;
        set[i] = SET_DELETED;
    } return i;
}

/* ---------------------------------------------------------------------------
 *                                  Table
 * --------------------------------------------------------------------------- */
#define tbl_cnt(t) set_cnt(t)
#define tbl_cap(t) (set_cap(t) >> 1)
#define tbl_key(k) set_key(k)
#define tbl_val(t,i) ((intptr_t)((t)[tbl_cap(t)+i]))
#define tbl_slot(t,k,c) set_slot(t,k,c)
#define tbl__fits(t, cnt) ((cnt) < (int)((float)tbl_cap(t) * SET_FULL_PERCENT))
#define tbl__fit(t,n) (tbl__fits(t, n) ? 0: ((t) = tbl__grow(t, n)))
#define tbl__add(t,k,v) (tbl__fit(t, tbl_cnt(t) + 1), tbl__put(t,k,v))
#define tbl_put(t,k,v) ((!(t) || set__fnd(t,k,tbl_cap(t)) >= tbl_cap(t)) ? tbl__add(t,k,v): tbl_cap(t))
#define tbl_del(t,k) tbl__del(t, k, 0)
#define tbl_free(t) set_free(t)
#define tbl_mod(t,k) (!(t) ? -1 : set__mod(k, tbl_cap(t)))
#define tbl_at(t,i) (((i) >= tbl_cap(t)) ? 0: tbl_key((t)[i]))

static intptr_t
tbl__put(uintptr_t *tbl, uintptr_t key, intptr_t val)
{
    const intptr_t i = tbl_slot(tbl, key, tbl_cap(tbl));
    if (i < tbl_cap(tbl)) {
        dyn__hdr(tbl)->cnt++;
        tbl[tbl_cap(tbl)+i]= (uintptr_t)val;
        tbl[i] = key;
    } return i;
}
static uintptr_t*
tbl__grow(uintptr_t *old, int n)
{
    uintptr_t *tbl = set_new(set_cap(old), n << 1);
    for (int i = 0; i < tbl_cap(old); ++i)
        if (tbl_key(old[i]))
            tbl__put(tbl, old[i], tbl_val(old,i));
    dyn_free(old);
    return tbl;
}
static intptr_t
tbl__del(uintptr_t *tbl, uintptr_t key, intptr_t not_found)
{
    const intptr_t i = set__del(tbl, key, tbl_cap(tbl));
    if (i >= tbl_cap(tbl)) return not_found;
    return tbl_val(tbl,i);
}
static intptr_t
tbl_fnd(uintptr_t *tbl, uintptr_t key, intptr_t not_found)
{
    if (!tbl_cnt(tbl)) return not_found;
    const intptr_t i = set__fnd(tbl, key, tbl_cap(tbl));
    return (i >= tbl_cap(tbl)) ? not_found: (intptr_t)tbl_val(tbl,i);
}

/* ---------------------------------------------------------------------------
 *                                  Arena
 * --------------------------------------------------------------------------- */
#define ARENA_ALIGNMENT 8
#define ARENA_BLOCK_CNT 1024
#define ARENA_BLOCK_SIZE (64*1024)

struct scope {
    char *ptr;
    char *end;
    int blk;
};
struct arena {
    char *ptr;
    char *end;
    char **blks;
};
#define arena_dyn(a,T,n) cast(T*,dyn__static(arena_push(a, dyn_req_siz(sizeof(T) * (n))), (n)))
#define arena_set(a,n)  arena_dyn(a,uintptr_t,n)
#define arena_tbl(a,n)  arena_dyn(a,uintptr_t, (n << 1))
#define arena_arr(a,T,n) cast(T*, arena_push(a, sizeof(T) * n))

static void
arena__grow(struct arena *a, int min_size)
{
    min_size = align_up(min_size, ARENA_ALIGNMENT);
    a->ptr = calloc(1,min_size);
    a->end = a->ptr + min_size;
    dyn_add(a->blks, a->ptr);
}
static void*
arena_push(struct arena *a, int size)
{
    char *p = 0;
    if (size > (a->end - a->ptr)) {
        int min_size = max(size, ARENA_BLOCK_SIZE);
        arena__grow(a, min_size);
    }
    p = a->ptr;
    a->ptr = align_up_ptr(p + size, ARENA_ALIGNMENT);
    assert(a->ptr < a->end);
    return p;
}
static char*
arena_printf(struct arena *a, const char *fmt, ...)
{
    int n = 0;
    char *res = 0;

    va_list args;
    va_start(args, fmt);
    n = 1 + vsnprintf(0, 0, fmt, args);
    va_end(args);

    res = arena_push(a, n);
    va_start(args, fmt);
    vsnprintf(res, (size_t)n, fmt, args);
    va_end(args);
    return res;
}
static void
arena_free(struct arena *a)
{
    for (int i = 0; i < dyn_cnt(a->blks); ++i)
        free(a->blks[i]);
    dyn_free(a->blks);
    memset(a, 0, sizeof(*a));
}
static void
scope_begin(struct scope *s, struct arena *a)
{
    assert(a);
    assert(s);

    s->ptr = a->ptr;
    s->end = a->end;
    s->blk = dyn_cnt(a->blks);
}
static void
scope_end(struct scope *s, struct arena *a)
{
    assert(s);
    assert(a);

    a->ptr = s->ptr;
    a->end = s->end;

    int i = dyn_cnt(a->blks);
    while (i > s->blk) {
        free(a->blks[--i]);
        a->blks[i] = 0;
    } dyn__hdr(a->blks)->cnt = s->blk;
}
int main()
{
    #define N 32
    #define NN 1024

    #define len(s) (cntof(s)-1)
    #define h1(s,i,x) (x*65599lu+(unsigned char)(s)[(i)<len(s)?len(s)-1-(i):len(s)])
    #define h4(s,i,x) h1(s,i,h1(s,i+1,h1(s,i+2,h1(s,i+3,x))))
    #define h16(s,i,x) h4(s,i,h4(s,i+4,h4(s,i+8,h4(s,i+12,x))))
    #define h32(s,i,x) h16(s,i,h16(s,i+16,x))
    #define hash(s,i) ((uintptr_t)(h32(s,0,i)^(h32(s,0,i)>>32)))
    #define idx(s,i) hash(s,(uintptr_t)i)
    #define id(s) idx(s,0)

    struct arena a = {0};
    {
        struct scope scp = {0};
        scope_begin(&scp, &a);
        {
            int *st_buf = arena_dyn(&a, int, N);
            assert(isaligned(st_buf, alignof(int)));

            int *buf = st_buf;
            for (int i = 0; i < N; ++i)
                dyn_add(buf, i);
            assert(dyn_cnt(buf) == N);

            for (int i = 0; i < N; ++i)
                assert(buf[i] == i);
            assert(buf == st_buf);

            dyn_free(buf);
            assert(buf == 0);
            assert(dyn_cnt(buf) == 0);
        }
        scope_end(&scp, &a);
    }
    {
        struct scope scp = {0};
        scope_begin(&scp, &a);
        {
            int *st_buf = arena_dyn(&a, int, N);
            assert(isaligned(st_buf, alignof(int)));

            int *buf = st_buf;
            for (int i = 0; i < NN; ++i)
                dyn_add(buf, i);
            assert(dyn_cnt(buf) == NN);

            for (int i = 0; i < NN; ++i)
                assert(buf[i] == i);
            assert(buf != st_buf);

            dyn_free(buf);
            assert(buf == 0);
            assert(dyn_cnt(buf) == 0);
        }
        scope_end(&scp, &a);
    }
    {
        struct scope scp = {0};
        scope_begin(&scp, &a);
        {
            int *buf = arena_dyn(&a, int, N);
            for (int i = 0; i < NN; ++i)
                dyn_add(buf, i);
            dyn_free(buf);
        }
        scope_end(&scp, &a);
    }
    {
        static const int K = 1024;

        /* test insert */
        uintptr_t *set = 0;
        set_put(set, id("test"));
        assert(set);
        assert(set_cnt(set) == 1);
        assert(set_cap(set));

        set_put(set, id("root"));
        assert(tbl_cnt(set) == 2);

        /* test lookup */
        int n = set_fnd(set, id("test"));
        assert(n);
        n = set_fnd(set, id("test0"));
        assert(!n);
        n = set_fnd(set, id("root"));
        assert(n);

        /* test removing */
        set_del(set, id("test"));
        assert(set);
        assert(set_cnt(set) == 1);
        assert(set_cap(set));

        set_del(set, id("test0"));
        assert(set);
        assert(set_cnt(set) == 1);
        assert(set_cap(set));

        set_del(set, id("root"));
        assert(set);
        assert(set_cnt(set) == 0);
        assert(set_cap(set));

        /* test growth */
        for (int i = 0; i < K; ++i)
            set_put(set, (uintptr_t)i+1);
        assert(set_cnt(set) == K);

        for (int i = 0; i < K; ++i) {
            n = set_fnd(set, (uintptr_t)i+1);
            set_del(set, (uintptr_t)i+1);
            assert(n);
        }
        assert(set_cnt(set) == 0);
        set_free(set);

        assert(set_cnt(set) == 0);
        assert(set_cap(set) == 0);
        assert(set == 0);

        /* test slot refilling after marked as deleted */
        set_put(set, id("test"));
        intptr_t x = set__fnd(set, id("test"), set_cap(set));
        set_del(set, id("test"));
        set_put(set, id("test"));
        intptr_t y = set__fnd(set, id("test"), set_cap(set));
        assert(x == y);
        n = set_fnd(set, id("test"));
        assert(n);
        set_free(set);
    }
    {
        intptr_t i, n, x, y;
        static const int K = 1024;

        /* test insert */
        uintptr_t *t = 0;
        tbl_put(t, id("test"), 42);
        assert(t);
        assert(tbl_cnt(t) == 1);
        assert(tbl_cap(t));

        tbl_put(t, id("root"), 1337);
        assert(tbl_cnt(t) == 2);

        /* test lookup */
        n = tbl_fnd(t, id("test"), 0);
        assert(n == 42);
        n = tbl_fnd(t, id("test0"), INT_MAX);
        assert(n == INT_MAX);
        n = tbl_fnd(t, id("root"), 0);
        assert(n == 1337);

        /* test removing */
        tbl_del(t, id("test"));
        assert(t);
        assert(tbl_cnt(t) == 1);
        assert(tbl_cap(t));

        tbl_del(t, id("test0"));
        assert(t);
        assert(tbl_cnt(t) == 1);
        assert(tbl_cap(t));

        tbl_del(t, id("root"));
        assert(t);
        assert(tbl_cnt(t) == 0);
        assert(tbl_cap(t));

        /* test growth */
        for (i = 0; i < K; ++i)
            tbl_put(t, (uintptr_t)i+1, i);
        assert(tbl_cnt(t) == K);

        for (i = 0; i < K; ++i) {
            n = tbl_fnd(t, (uintptr_t)i+1, 0);
            tbl_del(t, (uintptr_t)i+1);
            assert(n == i);
        }
        assert(tbl_cnt(t) == 0);
        tbl_free(t);

        assert(tbl_cnt(t) == 0);
        assert(tbl_cap(t) == 0);
        assert(t == 0);

        /* test slot refilling after marked as deleted */
        tbl_put(t, id("test"), 42);
        x = set__fnd(t, id("test"), tbl_cap(t));
        tbl_del(t, id("test"));
        tbl_put(t, id("test"), 1337);
        y = set__fnd(t, id("test"), tbl_cap(t));
        assert(x == y);
        n = tbl_fnd(t, id("test"), INT_MAX);
        assert(n == 1337);
        tbl_free(t);
        {
            /* test static tbl */
            struct scope scp = {0};
            scope_begin(&scp, &a);
            {
                uintptr_t *ref = arena_tbl(&a, 2 * 1024);
                t = ref;

                for (i = 0; i < K; ++i)
                    tbl_put(t, (uintptr_t)i+1, i);

                assert(t);
                assert(tbl_cnt(t) == K);

                tbl_free(t);
            }
            scope_end(&scp, &a);
        }
        {
            /* test static tbl */
            struct scope scp = {0};
            scope_begin(&scp, &a);
            {
                uintptr_t *ref = arena_tbl(&a, 32);
                t = ref;

                for (i = 0; i < K; ++i)
                    tbl_put(t, (uintptr_t)i+1, i);

                assert(t != 0);
                assert(tbl_cnt(t) == K);

                tbl_free(t);
            }
            scope_end(&scp, &a);
        }
        {
            struct scope scp = {0};
            scope_begin(&scp, &a);
            {
                uintptr_t *tbl = arena_tbl(&a, 32);
                for (i = 0; i < 1024; ++i)
                    tbl_put(tbl, (uintptr_t)i+1, i);
                tbl_free(tbl);
            }
            scope_end(&scp, &a);
        }
#if 0
        {
            struct elm {
                int nxt;
                /* ... */
                const char *name;
            };
            struct elm *elms = 0;
            /* fill dyn array */
            
            struct scope scp = {0};
            scope_begin(&scp, &a);
            {
                uintptr_t *tbl = arena_tbl(&a, 32);
                for (i = 0; i < dyn_cnt(elms); ++i) {
                    const uintptr_t key = hash_str(elms[i].name);
                    const int at = tbl_mod(tbl, key);
                    if (tbl_at(tbl, at)) {
                        struct elm *elm = tbl_val(tbl, at);
                        elm->nxt = i;
                    } else tbl_put(tbl, key, i);   
                }
                tbl_free(tbl);
            }
            scope_end(&scp, &a);     
        }
#endif
    }
    arena_free(&a);
    return 0;
}

The containerof macro doesn't seem to be used but there's syntax mistake there: ... offsof(....

Thanks! Fixed it.