arena stuff

demo.c

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define assert(c)     while (!(c)) *(volatile int *)0 = 0
#define countof(a)    (ptrdiff_t)(sizeof(a) / sizeof(*(a)))
#define new(a, t, n)  (t *)alloc(a, sizeof(t), n)
#define S(s)          (str){(char *)s, countof(s)-1}

typedef struct {
    char *beg;
    char *end;
} arena;

void *alloc(arena *a, ptrdiff_t size, ptrdiff_t count)
{
    int align = -((unsigned)size * (unsigned)count) & 7;
    if (count > (a->end - a->beg - align)/size) {
        assert(0);
    }
    return memset(a->end -= count*size + align, 0, count*size);
}

typedef struct {
    char     *data;
    ptrdiff_t len;
} str;

_Bool equals(str a, str b)
{
    return a.len==b.len && !memcmp(a.data, b.data, a.len);
}

unsigned hashstr(str s)
{
    unsigned h = 0x811c9dc5;
    for (ptrdiff_t i = 0; i < s.len; i++) {
        h ^= s.data[i] & 255;
        h *= 0x01000193;
    }
    return h;
}

typedef struct {
    str    buf;
    arena *perm;
} membuf;

membuf newmembuf(arena *perm)
{
    membuf b = {0};
    b.buf.data = perm->beg;
    b.perm = perm;
    return b;
}

void append(membuf *b, str s)
{
    assert(b->buf.data == b->perm->beg - b->buf.len);
    ptrdiff_t available = b->perm->end - b->perm->beg;
    if (available < s.len) {
        assert(0);
    }
    memcpy(b->buf.data+b->buf.len, s.data, s.len);
    b->perm->beg += s.len;
    b->buf.len += s.len;
}

// Construct a null-terminated path (i.e. to be opened) to a config file.
str getconfigpath(str home, str app, arena *perm)
{
    membuf buf = newmembuf(perm);
    append(&buf, home);
    append(&buf, S("/."));
    append(&buf, app);
    append(&buf, S("rc\0"));
    return buf.buf;
}

typedef struct pathset pathset;
struct pathset {
    pathset *child[2];
    str      path;
};

_Bool insert(pathset **m, str path, arena *perm)
{
    for (unsigned h = hashstr(path); *m; h <<= 1) {
        if (equals((*m)->path, path)) {
            return 0;
        }
        m = &(*m)->child[h>>31];
    }
    *m = new(perm, pathset, 1);
    (*m)->path = path;
    return 1;
}

// For constructing $PATH variables without repeats.
typedef struct {
    pathset *seen;
    membuf   path;
} pathbuilder;

pathbuilder *newpathbuilder(arena *perm)
{
    pathbuilder *b = new(perm, pathbuilder, 1);
    b->path = newmembuf(perm);
    return b;
}

// Append a path to the $PATH if not already present.
void add(pathbuilder *b, str path)
{
    if (insert(&b->seen, path, b->path.perm)) {
        if (b->path.buf.len) {
            append(&b->path, S(":"));
        }
        append(&b->path, path);
        // NOTE: The key stored in the set could instead point into the
        // accumulated $PATH, retaining a local copy (for free!) instead
        // of retaining a pointer to the provided string.
    }
}

arena newarena(ptrdiff_t cap)
{
    arena a = {0};
    a.beg = malloc(cap);
    if (!a.beg) {
        cap = 0;
        a.beg = (char *)16;  // empty, non-null arena
    }
    a.end = a.beg + cap;
    memset(a.beg, 0x55, cap);  // for testing
    return a;
}

int main(void)
{
    arena scratch = newarena(1<<24);
    str home = S("/home/skeeto");
    str path = getconfigpath(home, S("vim"), &scratch);

    pathbuilder *pb = newpathbuilder(&scratch);
    add(pb, S("/bin"));
    add(pb, S("/usr/bin"));
    add(pb, S("/usr/local/bin"));
    add(pb, S("/usr/bin"));  // won't get added
    path = pb->path.buf;
    asm ("b:");
    return 0;
}