Skip to content

Instantly share code, notes, and snippets.

@vurtun
Last active May 16, 2024 04:17
Show Gist options
  • Save vurtun/dcb0cbdf24df27768b1d2df6c7e4f764 to your computer and use it in GitHub Desktop.
Save vurtun/dcb0cbdf24df27768b1d2df6c7e4f764 to your computer and use it in GitHub Desktop.
#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;
}
Copy link

ghost commented Aug 12, 2019

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

@vurtun
Copy link
Author

vurtun commented Aug 14, 2019

Thanks! Fixed it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment