Linked list tricks

list.c

// This is free and unencumbered software released into the public domain.
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define lenof(a)        (ptrdiff_t)(sizeof(a) / sizeof(*(a)))
#define S(s)            (Str){s, lenof(s)-1}
#define new(a, n, t)    (t *)alloc(a, n, sizeof(t), _Alignof(t))

size_t tousize(ptrdiff_t x)
{
    assert(x >= 0);
    return (size_t)x;
}

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

char *alloc(Arena *a, ptrdiff_t count, int size, int align)
{
    int pad = (int)-(uintptr_t)a->beg & (align - 1);
    assert(count < (a->end - a->beg - pad)/size);  // OOM policy
    char *r = a->beg + pad;
    a->beg += pad + count*size;
    return memset(r, 0, tousize(count*size));
}

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

Str span(char *beg, char *end)
{
    assert(beg <= end);
    return (Str){beg, end-beg};
}

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

uint64_t hash64(Str s)
{
    uint64_t r = 0x100;
    for (ptrdiff_t i = 0; i < s.len; i++) {
        r ^= s.data[i] & 0xff;
        r *= 1111111111111111111;
    }
    return r;
}

typedef struct {
    Str   tail;
    Str   head;
    _Bool ok;
} Cut;

Cut cut(Str s, char c)
{
    Cut r = {0};
    if (!s.len) return r;  // null pointer special case
    char *beg = s.data;
    char *end = s.data + s.len;
    char *cut = beg;
    for (; cut<end && *cut!=c; cut++) {}
    r.ok   = cut < end;
    r.head = span(beg, cut);
    r.tail = span(cut+r.ok, end);
    return r;
}

typedef struct Env Env;
struct Env {
    Env *next;
    Env *child[2];
    Str  key;
    Str  value;
};

Env *parse_reversed(Str s, Arena *a)
{
    Env *head = 0;
    for (Cut line = {s}; line.tail.len;) {
        line = cut(line.tail, '\n');
        Cut  pair  = cut(line.head, '=');
        Env *env   = new(a, 1, Env);
        env->key   = pair.head;
        env->value = pair.tail;
        env->next  = head;
        head = env;
    }
    return head;
}

Env *parse_ordered(Str s, Arena *a)
{
    Env  *head = 0;
    Env **tail = &head;
    for (Cut line = {s}; line.tail.len;) {
        line = cut(line.tail, '\n');
        Cut  pair  = cut(line.head, '=');
        Env *env   = new(a, 1, Env);
        env->key   = pair.head;
        env->value = pair.tail;
        *tail = env;
        tail = &env->next;
    }
    return head;
}

Str lookup_linear(Env *env, Str key)
{
    for (Env *var = env; var; var = var->next) {
        if (equals(key, var->key)) {
            return var->value;
        }
    }
    return (Str){};
}

Env *new_env(Arena *a, Env **env, Str key, Str value)
{
    for (uint64_t h = hash64(key); *env; h <<= 1) {
        env = &(*env)->child[h>>63];
    }
    *env = new(a, 1, Env);
    (*env)->key = key;
    (*env)->value = value;
    return *env;
}

Env *parse_mapped(Str s, Arena *a)
{
    Env  *head = 0;
    Env **tail = &head;
    for (Cut line = {s}; line.tail.len;) {
        line = cut(line.tail, '\n');
        Cut  pair = cut(line.head, '=');
        Env *env  = new_env(a, &head, pair.head, pair.tail);
        *tail = env;
        tail = &env->next;
    }
    return head;
}

Str lookup_logn(Env *env, Str key)
{
    for (uint64_t h = hash64(key); env; h <<= 1) {
        if (equals(key, env->key)) {
            return env->value;
        }
        env = env->child[h>>63];
    }
    return (Str){};
}

typedef struct {
    uint64_t hash;
    Str      key;
    Env     *env;
} EnvIter;

EnvIter new_enviter(Env *env, Str key)
{
    return (EnvIter){hash64(key), key, env};
}

Str enviter_next(EnvIter *it)
{
    while (it->env) {
        Env *cur = it->env;
        it->env = it->env->child[it->hash>>63];
        it->hash <<= 1;
        if (equals(it->key, cur->key)) {
            return cur->value;
        }
    }
    return (Str){};
}

typedef struct {
    Env **slots;
    int   exp;
} EnvTable;

EnvTable new_table(Arena *a, Env *env)
{
    ptrdiff_t len = 0;
    for (Env *var = env; var; var = var->next) {
        len++;
    }

    EnvTable table = {};
    table.exp = 3;
    ptrdiff_t one = 1;
    for (; (one<<table.exp) - (one<<(table.exp-3)) < len; table.exp++) {}
    table.slots = new(a, one<<table.exp, Env *);

    for (Env *var = env; var; var = var->next) {
        uint64_t hash = hash64(var->key);
        size_t   mask = ((size_t)1 << table.exp) - 1;
        size_t   step = (size_t)(hash >> (64 - table.exp)) | 1;
        for (size_t i = (size_t)hash;;) {
            i = (i + step) & mask;
            if (!table.slots[i]) {
                table.slots[i] = var;
                break;
            }
        }
    }

    return table;
}

Str lookup_constant(EnvTable table, Str key)
{
    uint64_t hash = hash64(key);
    size_t   mask = ((size_t)1 << table.exp) - 1;
    size_t   step = (size_t)(hash >> (64 - table.exp)) | 1;
    for (size_t i = (size_t)hash;;) {
        i = (i + step) & mask;
        if (!table.slots[i]) {
            return (Str){};
        } else if (equals(table.slots[i]->key, key)) {
            return table.slots[i]->value;
        }
    }
}

typedef struct {
    EnvTable table;
    Str      key;
    size_t   step;
    size_t   i;
} TableIter;

TableIter new_tableiter(EnvTable table, Str key)
{
    uint64_t hash = hash64(key);
    size_t   step = (size_t)(hash >> (64 - table.exp)) | 1;
    size_t   idx  = (size_t)hash;
    return (TableIter){table, key, step, idx};
}

Str table_next(TableIter *it)
{
    size_t mask  = ((size_t)1 << it->table.exp) - 1;
    Env  **slots = it->table.slots;
    for (;;) {
        it->i = (it->i + it->step) & mask;
        if (!slots[it->i]) {
            return (Str){};
        } else if (equals(slots[it->i]->key, it->key)) {
            return slots[it->i]->value;
        }
    }
}

int main()
{
    static char mem[1<<21];
    Arena a = {mem, mem+lenof(mem)};

    Str input = S(
        "EDITOR=vim\n"
        "HOME=/home/user\n"
        "PATH=/bin:/usr/bin\n"
        "SHELL=/bin/bash\n"
        "TERM=xterm-256color\n"
        "USER=user\n"
        "SHELL=/bin/sh\n"
    );

    {
        Arena scratch = a;
        Env *env = parse_reversed(input, &scratch);
        Str value = lookup_linear(env, S("SHELL"));
        printf("reversed\t%.*s\n", (int)value.len, value.data);
    }

    {
        Arena scratch = a;
        Env *env = parse_ordered(input, &scratch);
        Str value = lookup_linear(env, S("SHELL"));
        printf("linear\t\t%.*s\n", (int)value.len, value.data);
    }

    {
        Arena scratch = a;
        Env *env = parse_mapped(input, &scratch);
        Str value = lookup_logn(env, S("SHELL"));
        printf("logn\t\t%.*s\n", (int)value.len, value.data);
    }

    {
        Arena scratch = a;
        Env *env = parse_mapped(input, &scratch);
        for (EnvIter it = new_enviter(env, S("SHELL"));;) {
            Str value = enviter_next(&it);
            if (!value.data) break;
            printf("multi-logn\t%.*s\n", (int)value.len, value.data);
        }
    }

    {
        Arena scratch = a;
        Env *env = parse_ordered(input, &scratch);
        EnvTable table = new_table(&scratch, env);
        Str value = lookup_constant(table, S("SHELL"));
        printf("msi\t\t%.*s\n", (int)value.len, value.data);
    }

    {
        Arena scratch = a;
        Env *env = parse_ordered(input, &scratch);
        EnvTable table = new_table(&scratch, env);
        for (TableIter it = new_tableiter(table, S("SHELL"));;) {
            Str value = table_next(&it);
            if (!value.data) break;
            printf("multi-msi\t%.*s\n", (int)value.len, value.data);
        }
    }

    return 0;
}