cont.c

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

/* ---------------------------------------------------------------------------
 *                                  UTIL
 * --------------------------------------------------------------------------- */
#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 aligned(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)))

static void*
xrealloc(void *p, int size)
{
    p = realloc(p, (size_t)size);
    if (!p) {
        perror("xrealloc failed!\n");
        exit(1);
    } return p;
}
static void*
xmalloc(int size)
{
    void *p = calloc(1,(size_t)size);
    if (!p) {
        perror("xmalloc failed!\n");
        exit(1);
    } return p;
}
/* ---------------------------------------------------------------------------
 *                                  Buffer
 * --------------------------------------------------------------------------- */
#define BUF_ALIGNMENT 16
struct buf_hdr {
    int cnt,cap;
    char buf[];
};
#define buf__hdr(b) ((struct buf_hdr*)(void*)((char*)(b) - offsetof(struct buf_hdr, buf)))
#define buf__fits(b,n) (buf_cnt(b) + (n) <= buf_cap(b))
#define buf_req_siz(type_size) (sizeof(struct buf_hdr) + type_size + BUF_ALIGNMENT)
#define buf_space(t,n) buf_req_siz(sizeof(t) * n)
#define buf_cnt(b) ((b) ? buf__hdr(b)->cnt: 0)
#define buf_cap(b) ((b) ? abs(buf__hdr(b)->cap): 0) // MODIFIED
#define buf_begin(b) ((b) + 0)
#define buf_end(b) ((b) + buf_cnt(b))
#define buf_fit(b,n) (buf__fits((b), (n)) ? 0: ((b) = buf__grow((b),buf_cnt(b)+(n), sizeof(*(b)))))
#define buf_push(b, x) (buf_fit((b),1), (b)[buf__hdr(b)->cnt++] = x)
#define buf_free(b) ((!(b)) ? 0: (buf__hdr(b)->cap <= 0) ? (b) = 0: (free(buf__hdr(b)), (b) = 0))
#define buf_clear(b) ((b) ? buf__hdr(b)->n = 0 : 0)
#define buf_printf(b, fmt, ...) ((b) = buf__printf((b), (fmt), __VA_ARGS__))
#define buf_static(T,b) (T*)buf__static(b, (sizeof(b) - (offsetof(struct buf_hdr, buf) + BUF_ALIGNMENT)) / sizeof(T))

static void*
buf__grow(void *buf, int new_len, int elem_size)
{
    struct buf_hdr *hdr = 0;
    int cap = buf_cap(buf);
    int new_cap = max(2*cap + 1, new_len);
    int new_size = offsetof(struct buf_hdr, buf) + new_cap*elem_size;
    assert(new_len <= new_cap);
    if (!buf) {
        hdr = malloc(new_size);
        hdr->cnt = 0;
    } else if (buf__hdr(buf)->cap < 0) {
        /* NEW */
        hdr = malloc(new_size);
        hdr->cnt = buf_cnt(buf);
        memcpy(hdr->buf, buf__hdr(buf)->buf, (size_t)(cap*elem_size));
    } else hdr = realloc(buf__hdr(buf), (size_t)new_size);
    hdr->cap = new_cap;
    return hdr->buf;
}
static void*
buf__static(void *buf, int n)
{
    /* NEW */
    void *u = (char*)buf + BUF_ALIGNMENT + sizeof(struct buf_hdr) - 1;
    void *a = align_down_ptr(u, BUF_ALIGNMENT);
    void *h = (char*)a - sizeof(struct buf_hdr);

    struct buf_hdr *hdr = h;
    assert(isaligned(hdr, alignof(struct buf_hdr)));
    assert(isaligned(a, BUF_ALIGNMENT));
    hdr->cap = -n, hdr->cnt = 0;
    return hdr->buf;
}
static char*
buf__printf(char *buf, const char *fmt, ...)
{
    int cap, n;
    va_list args;
    va_start(args, fmt);
    cap = buf_cap(buf) - buf_cnt(buf);
    n = 1 + vsnprintf(buf_end(buf), (size_t)cap, fmt, args);
    va_end(args);

    if (n > cap) {
        buf_fit(buf, n + buf_cnt(buf));
        va_start(args, fmt);
        int new_cap = buf_cap(buf) - buf_cnt(buf);
        n = 1 + vsnprintf(buf_end(buf), (size_t)new_cap, fmt, args);
        assert(n <= new_cap);
        va_end(args);
    }
    buf__hdr(buf)->cnt += n - 1;
    return buf;
}
static void
buf_test(void)
{
    int i, *buf = 0;
    char *str = 0;

    /* dynamic buffer */
    static const int N = 1024;
    assert(buf_cnt(buf) == 0);
    for (i = 0; i < N; ++i)
        buf_push(buf, i);
    assert(buf_cnt(buf) == N);
    
    for (i = 0; i < N; ++i)
        assert(buf[i] == i);
    buf_free(buf);
    assert(buf == 0);
    assert(buf_cnt(buf) == 0);

    /* printf buffer */
    buf_printf(str, "One: %d ", 1);
    buf_printf(str, "Hex: 0x%x", 0x42);
    assert(strcmp(str, "One: 1 Hex: 0x42") == 0);
    buf_free(str);
}
static void
fixed_buf_test(void)
{
    int i = 0;
    #define N 32
    static const int NN = 1024;
    char fix[buf_space(int,N)];
    int *buf = buf_fixed(fix,N);

    /* fixed buffer */
    assert(aligned(buf, alignof(int)));
    for (i = 0; i < N; ++i)
        buf_push(buf, i);
    for (i = 0; i < N; ++i)
        assert(buf[i] == i);

    assert((char*)buf__hdr(buf) == fix);
    buf_free(buf);
    assert(buf == 0);
    assert(buf_cnt(buf) == 0);

    buf = buf_fixed(fix,N);
    for (i = 0; i < NN; ++i)
        buf_push(buf, i);
    for (i = 0; i < NN; ++i)
        assert(buf[i] == i);

    assert((char*)buf__hdr(buf) != fix);
    buf_free(buf);

    assert(buf == 0);
    assert(buf_cnt(buf) == 0);
    #undef N
}
static void
fixed_sprintf_buf_test(void)
{
    #define N 8
    char fix[buf_space(char,N)];
    char *str = buf_fixed(fix,N);

    buf_printf(str, "One: %d ", 1);
    assert((char*)buf__hdr(str) == fix);
    buf_printf(str, "Hex: 0x%x", 0x42);
    assert((char*)buf__hdr(str) != fix);
    assert(strcmp(str, "One: 1 Hex: 0x42") == 0);
    buf_free(str);
    #undef N
}

/* ---------------------------------------------------------------------------
 *                                  Table
 * --------------------------------------------------------------------------- */
#define TBL_MIN_SIZE 32
#define TBL_GROW_FACTOR 2.8f
#define TBL_FULL_PERCENT 0.7f
#define TBL_MIN_GROW_PERCENT 1.3f
#define TBL_DELETED ((uintptr_t)-1)

struct tbl {
    int n, cap;
    uintptr_t *keys;
    intptr_t *vals;
};
#define tbl__fits(t, cnt) ((cnt) < (int)((float)(t)->cap * TBL_FULL_PERCENT))
#define tbl__fit(t, n) (tbl__fits(t, n) ? 0: tbl__grow(t, n))
#define tbl_insert(t, key, val) (tbl__fit(t, (t)->n + 1), tbl__put(t, key, val))
#define tbl_remove(t,k) tbl__del(t, k, 0)
#define tbl_free(t) do{free((t)->keys); memset((t), 0, sizeof(*t));}while(0)
#define tbl_slot(s) ((s) != 0u && (s) != TBL_DELETED)

static intptr_t
tbl__put(struct tbl *t, uintptr_t key, intptr_t val)
{
    uintptr_t n = cast(uintptr_t, t->cap);
    uintptr_t i = key % n, b = i;
    do {uintptr_t k = t->keys[i];
        if (k && k != TBL_DELETED) continue;
        t->keys[i] = key;
        t->vals[i] = val;
        return ++t->n, (intptr_t)i;
    } while ((i = ((i+1) % n)) != b);
    return t->cap;
}
static int
tbl__grow(struct tbl *t, int n)
{
    int i = 0;
    struct tbl old = *t;

    /* allocate new hash table */
    n = max(TBL_MIN_SIZE, (int)((float)n * TBL_MIN_GROW_PERCENT));
    t->cap = max(n, cast(int, TBL_GROW_FACTOR * cast(float, old.cap)));
    t->keys = xmalloc(t->cap * szof(uintptr_t) * 2);
    t->vals = cast(intptr_t*, t->keys + t->cap);
    t->n = 0;

    /* rehash old table entries */
    for (i = 0; i < old.cap; ++i)
        if (old.keys[i] && old.keys[i] != TBL_DELETED)
            tbl__put(t, old.keys[i], old.vals[i]);
    free(old.keys);
    return t->cap;
}
static intptr_t
tbl__find(const struct tbl *t, uintptr_t key)
{
    uintptr_t n = cast(uintptr_t, t->cap);
    uintptr_t i = key % n, b = i;
    do {uintptr_t k = t->keys[i];
        if (!k) return t->cap;
        if (k == key) return cast(intptr_t,i);
    } while ((i = ((i+1) % n)) != b);
    return t->cap;
}
static intptr_t
tbl__del(struct tbl *t, uintptr_t key, intptr_t not_found)
{
    if (!t->n) return not_found;
    {intptr_t i = tbl__find(t, key);
    if (i >= t->cap) return not_found;
    t->n--; t->keys[i] = TBL_DELETED;
    return t->vals[i];}
}
static intptr_t
tbl_lookup(const struct tbl *t, uintptr_t key, intptr_t not_found)
{
    if (!t->n) return not_found;
    {intptr_t i = tbl__find(t, key);
    if (i >= t->cap) return not_found;
    return t->vals[i];}
}
static void
tbl_test(void)
{
    intptr_t i, n, a, b;
    static const int N = 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)

    /* test insert */
    struct tbl t = {0};
    tbl_insert(&t, id("test"), 42);
    assert(t.n == 1);
    assert(t.cap);
    assert(t.keys);
    assert(t.vals);

    tbl_insert(&t, id("root"), 1337);
    assert(t.n == 2);

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

    /* test removing */
    tbl_remove(&t, id("test"));
    assert(t.n == 1);
    assert(t.cap);
    assert(t.keys);
    assert(t.vals);

    tbl_remove(&t, id("test0"));
    assert(t.n == 1);
    assert(t.cap);
    assert(t.keys);
    assert(t.vals);

    tbl_remove(&t, id("root"));
    assert(t.n == 0);
    assert(t.cap);
    assert(t.keys);
    assert(t.vals);

    /* test growth */
    for (i = 0; i < N; ++i)
        tbl_insert(&t, (uintptr_t)i+1, i);
    assert(t.n == N);
    for (i = 0; i < N; ++i) {
        n = tbl_lookup(&t, (uintptr_t)i+1, 0);
        tbl_remove(&t, (uintptr_t)i+1);
        assert(n == i);
    }
    assert(t.n == 0);
    tbl_free(&t);

    assert(t.n == 0);
    assert(t.cap == 0);
    assert(t.keys == 0);
    assert(t.vals == 0);

    /* test slot refilling after marked as deleted */
    tbl_insert(&t, id("test"), 42);
    a = tbl__find(&t, id("test"));
    tbl_remove(&t, id("test"));
    tbl_insert(&t, id("test"), 1337);
    b = tbl__find(&t, id("test"));
    assert(a == b);
    n = tbl_lookup(&t, id("test"), INT_MAX);
    assert(n == 1337);
    tbl_free(&t);
}

/* ---------------------------------------------------------------------------
 *                                  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_buf(a,T,n) cast(T*,buf__static(arena_push(a, buf_req_siz(sizeof(T) * n)), n))

static void
arena__grow(struct arena *a, int min_size)
{
    min_size = align_up(min_size, ARENA_ALIGNMENT);
    a->ptr = malloc(min_size);
    a->end = a->ptr + min_size;
    buf_push(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)
{
    int i = 0;
    for (i = 0; i < buf_cnt(a->blks); ++i)
        free(a->blks[i]);
    buf_free(a->blks);
}
static void
scope_begin(struct scope *s, struct arena *a)
{
    assert(a);
    s->ptr = a->ptr;
    s->end = a->end;
    s->blk = buf_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 = buf_cnt(a->blks);
    while (i > s->blk) {
        free(a->blks[--i]);
        a->blks[i] = 0;
    } buf__hdr(a->blks)->cnt = s->blk;
}

/* ---------------------------------------------------------------------------
 *                                  TABLE TEST
 * --------------------------------------------------------------------------- */
typedef uintptr_t id;
struct foo {
    int i;
    float f;
    intptr_t next;
};
static struct foo *foos = 0;
static struct tbl foo_tbl;
static intptr_t freelist = -1;

static void
add_foo(id id, int i, float f)
{
    if (freelist < 0) {
        struct foo foo;
        foo.i = i, foo.f = f, foo.next = -1;
        buf_push(foos, foo);
        tbl_insert(&foo_tbl, id, buf_cnt(foos)-1);
    } else {
        struct foo *foo = foos + freelist;
        tbl_insert(&foo_tbl, id, freelist);
        freelist = foo->next;
        foo->i = i, foo->f = f, foo->next = -1;
    }
}
static void
del_foo(id key)
{
    struct foo *foo = 0;
    intptr_t i = tbl__del(&foo_tbl, key, buf_cnt(foos));
    if (i >= buf_cnt(foos)) return;
    foo = foos + i;
    foo->next = freelist;
    freelist = i;
}
static struct foo*
get_foo(id key)
{
    intptr_t i = tbl_lookup(&foo_tbl, key, buf_cnt(foos));
    if (i >= buf_cnt(foos)) return 0;
    return foos + i;
}
static void
free_foo(void)
{
    buf_free(foos);
    tbl_free(&foo_tbl);
    freelist = -1;
}
static void
tbl_buf_test(void)
{
    add_foo(id("root"), 42, 3.141592654f);
    add_foo(id("glub"), 12, 6.24f);
    add_foo(id("flub"), 24, 8.4f);
    add_foo(id("swub"), 1337, 2.8f);
    {
        struct foo *root = get_foo(id("root"));
        struct foo *glub = get_foo(id("glub"));
        struct foo *flub = get_foo(id("flub"));
        struct foo *swub = get_foo(id("swub"));

        assert(root);
        assert(root->i == 42);
        assert(root->f == 3.141592654f);

        assert(glub);
        assert(glub->i == 12);
        assert(glub->f == 6.24f);

        assert(flub);
        assert(flub->i == 24);
        assert(flub->f == 8.4f);

        assert(swub);
        assert(swub->i == 1337);
        assert(swub->f == 2.8f);
    }
    del_foo(id("glub"));
    assert(freelist != -1);
    add_foo(id("crub"), 69, -1.0f);
    assert(freelist == -1);

    del_foo(id("root"));
    del_foo(id("flub"));
    del_foo(id("swub"));
    assert(freelist != -1);
    free_foo();
    assert(freelist == -1);
}
/* ---------------------------------------------------------------------------
 *                                  Iterators
 * --------------------------------------------------------------------------- */
struct str_iter {
    const char *next;
    const char *delims;
    const char *str;
    const char *end;
};
static struct str_iter
str_lines(const char *str)
{
    struct str_iter it = {0};
    it.next = str;
    return it;
}
static int
str_line_next(struct str_iter *i)
{
    if (!i->next || !*i->next) return 0;
    i->str = i->end = i->next;
    while (*i->end && *i->end != '\n')
        i->end++;

    i->next = *i->end ? i->end+1: i->end;
    return 1;
}
static struct str_iter
str_words(const char *str)
{
    struct str_iter i = {0};
    i.next = str;
    return i;
}
static int
str_word_next(struct str_iter *i)
{
    if (!i->next) return 0;
    i->str = i->next;
    while (isspace(*i->str))
        i->str++;

    i->end = i->str;
    if (!(*i->str)) return 0;
    while (*i->end && !isspace(*i->end))
        i->end++;

    i->next = *i->end ? i->end + 1: i->end;
    return 1;
}
static struct str_iter
str_tokens(const char *str, const char *delims)
{
    struct str_iter i = {0};
    i.next = str;
    i.delims = delims;
    return i;
}
static int
str_has(const char *str, int c)
{
    while (*str) {
        if (*str == c)
            return 1;
        str++;
    } return 0;
}
static int
str_token_next(struct str_iter *i)
{
    if (!i->next) return 0;
    i->str = i->next;
    while (str_has(i->delims, *i->str))
        i->str++;

    i->end = i->str;
    if (!(*i->str)) return 0;
    while (*i->end && !str_has(i->delims, *i->end))
        i->end++;
    i->next = *i->end ? i->end + 1: i->end;
    return 1;
}
static void
iter_test(void)
{
    struct str_iter i;
    const char line_str[] = " first\n\n \nsecond\nthird";
    const char word_str[] = "    first second\r third\n\t fourth  ";

    for (i = str_lines(line_str); str_line_next(&i);)
        printf("%.*s\n", (int)(i.end - i.str), i.str);
    for (i = str_words(word_str); str_word_next(&i);)
        printf("%.*s\n", (int)(i.end - i.str), i.str);
    for (i = str_tokens(word_str, " \r\n\t\f\v"); str_token_next(&i);)
        printf("%.*s\n", (int)(i.end - i.str), i.str);
}

/* ---------------------------------------------------------------------------
 *                                  Main
 * --------------------------------------------------------------------------- */
int main(void)
{
    buf_test();
    fixed_buf_test();
    fixed_sprintf_buf_test();
    tbl_test();
    tbl_buf_test();
    iter_test();
    return 0;
}

Just noticed on line 26 shall be xmalloc instead of xrealloc 😉.

Holy shit. How come you always find all these embarrassing mistakes 😄. I revisit and read many of my gist every few days and still for some reason don't see these dumbest of mind slips. Damn.

Frankly, the reason is, that thanks to my job I unfortunately don't have any time to do anything more than just read very quickly the source code on the web (I do it even on a smartphone as sometimes nothing better is available). Therefore I usually catch just the "embarrassing mistakes", but not the real ones (even though I consider your code of a high quality and therefore I don't expect them basically anywhere 😉).