path: root/src/badlib.h

#ifndef BADLIB_H
#define BADLIB_H

// TODO:
// - Add string operations.
//     - sub
//     - delete
// - Add math operations for vectors and matrices.
// - Breakdown this file in the different library parts.
// - Sort arrays / linked lists with custom functions?
// - Implement binary search for searching into an array:
//       SearchResult find_array(Array haystack, Array needle).
// - Logger functions for hash map and queues.
// - Make assert/abort macros dump the file name/line?
//

#include <stdarg.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

//
// Basic types.
//

_Static_assert(sizeof(double) == 8, "no support for IEEE-754");
_Static_assert(sizeof(float) == 4, "no support for IEEE-754");

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;
typedef float f32;
typedef double f64;
typedef ptrdiff_t sz;
typedef uintptr_t ptrsize;
typedef size_t usize;

#define KB(N) ((sz)(N)*1024)
#define MB(N) ((sz)KB(N) * 1024)
#define GB(N) ((sz)MB(N) * 1024)
#define TB(N) ((sz)GB(N) * 1024)

// Custom assert macro, better for debugging.
#ifdef DEBUG
#define assert(c) \
    while (!(c))  \
    __builtin_unreachable()
#else
#define assert(c) ;
#endif

// Abort macro without stdlib.
#define abort() __builtin_trap()

// Utility macros for numeric comparisons.
#define MIN(A, B) ((A) <= (B) ? (A) : (B))
#define MAX(A, B) ((A) >= (B) ? (A) : (B))
#define ABS(A) \
    (((A) ^ ((A) >> (sizeof(A) * 8 - 1))) - ((A) >> (sizeof(A) * 8 - 1)))
#define CLAMP(X, MIN, MAX) ((X) <= (MIN) ? (MIN) : (X) > (MAX) ? (MAX) : (X))
#define LEN(a) (sz)(sizeof(a) / sizeof(*(a)))

// Handy defer bacro for scoped operations.
#define MACRO_VAR_CONCAT_HELPER(X, Y) X##Y
#define MACRO_VAR_CONCAT(X, Y) MACRO_VAR_CONCAT_HELPER(X, Y)
#define MACRO_VAR(name) MACRO_VAR_CONCAT(name, __LINE__)
#define defer(begin, end)                                 \
    for (sz MACRO_VAR(_i_) = (begin, 0); !MACRO_VAR(_i_); \
         (MACRO_VAR(_i_) += 1), end)

//
// Allocators and Arenas.
//

typedef struct Allocator {
    void *(*malloc)(sz, void *ctx);
    void *(*calloc)(sz, void *ctx);
    void (*free)(void *, void *ctx);
    void *(*realloc)(void *ptr, sz old_size, sz new_size, void *ctx);
    void *ctx;
} Allocator;

typedef struct Arena {
    u8 *beg;
    sz size;
    sz cap;
} Arena;

#define ARENA_ALIGNMENT 8

void *
arena_malloc(sz size, void *ctx) {
    assert(size > 0);
    Arena *a = (Arena *)ctx;
    sz padding = -size & (ARENA_ALIGNMENT - 1);
    sz available = a->cap - a->size;
    if (available < 0 || available < size) {
        abort();
    }
    void *p = a->beg + a->size;
    a->size += padding + size;
    return p;
}

void *
arena_calloc(sz size, void *ctx) {
    void *mem = arena_malloc(size, ctx);
    return memset(mem, 0, size);
}

void
arena_free(void *ptr, sz size, void *ctx) {
    // Undo the latest allocation if possible.
    Arena *a = (Arena *)ctx;
    sz padding = -size & (ARENA_ALIGNMENT - 1);
    size += padding;
    if (ptr == a->beg + a->size - size) {
        a->size -= size;
    }
}

void *
arena_realloc(void *ptr, sz old_size, sz new_size, void *ctx) {
    // This function can avoid copying memory around if we could just extend the
    // latest allocation, otherwise a new malloc will be performed (keeping the
    // previous data alive!).
    Arena *a = (Arena *)ctx;
    sz old_padding = -old_size & (ARENA_ALIGNMENT - 1);
    old_size += old_padding;
    if (ptr == a->beg + a->size - old_size) {
        sz new_padding = -new_size & (ARENA_ALIGNMENT - 1);
        new_size += new_padding;
        a->size += new_size - old_size;
        return ptr;
    }
    u8 *p = arena_malloc(new_size, ctx);
    memcpy(p, ptr, old_size);
    return p;
}

Arena
arena_create(sz cap, Allocator allocator) {
    Arena arena = {0};
    arena.beg = allocator.malloc(cap, allocator.ctx);
    arena.cap = arena.beg ? cap : 0;
    return arena;
}

void
arena_destroy(Arena *arena, Allocator allocator) {
    if (arena) {
        allocator.free(arena->beg, allocator.ctx);
    }
}

void
arena_reset(Arena *a) {
    a->size = 0;
}

//
// Arrays, Buffers and Strings.
//

// A fixed buffer or buffer view, represented as a fat pointer.
typedef struct Array {
    u8 *mem;
    sz size;
} Array;

typedef struct SearchResult {
    // Position on the buffer where a result was found.
    sz pos;
    // Size of the matched query.
    sz matched;
    // Wether the search was successful or not.
    bool found;
} SearchResult;

bool
array_eq(Array a, Array b) {
    return a.size == b.size && !memcmp(a.mem, b.mem, a.size);
}

SearchResult
array_find_next(Array haystack, Array needle) {
    sz pos = 0;
    while (haystack.size >= needle.size) {
        if (*haystack.mem == *needle.mem) {
            Array candidate = (Array){
                .mem = haystack.mem,
                .size = needle.size,
            };
            if (array_eq(candidate, needle)) {
                return (SearchResult){
                    .pos = pos,
                    .matched = needle.size,
                    .found = true,
                };
            }
        }
        haystack.mem++;
        haystack.size--;
        pos++;
    }
    return (SearchResult){.found = false};
}

// A growable arena backed buffer.
typedef struct Buf {
    u8 *mem;
    sz size;
    sz cap;
} Buf;

// Reserve a given amount of bytes for a growable buffer.
void
buf_reserve(Buf *buf, sz size, Arena *a) {
    assert(buf);
    buf->mem = arena_realloc(buf->mem, buf->size, size, a);
    buf->size = 0;
    buf->cap = size;
}

// Zero initialize a growable buffer.
void
buf_zero(Buf *buf, sz size, Arena *a) {
    buf_reserve(buf, size, a);
    memset(buf->mem, 0, buf->cap);
}

// Insert a number of bytes into a growable buffer.
void
buf_insert(Buf *buf, void *value, sz size, Arena *a) {
    assert(buf);
    if (size == 0) {
        return;
    }
    if (!buf->mem) {
        buf->mem = arena_malloc(size, a);
        buf->size = size;
        buf->cap = size;
        memcpy(buf->mem, value, size);
        return;
    }
    while (buf->cap < buf->size + size) {
        arena_realloc(buf->mem, buf->cap, buf->cap * 2, a);
        buf->cap *= 2;
    }
    memcpy(buf->mem + buf->size, value, size);
    buf->size += size;
}

// Gets a reference to a given position of the buffer. It doesn't copy any
// information so bear in mind it could become invalidated if the buffer is
// modified.
void *
buf_ref(Buf *buf, sz pos, sz size) {
    return buf->mem + pos * size;
}

// Copies a number of bytes from an indexed position from growable buffer into
// the given destination.
void
buf_get(Buf *buf, void *dst, sz pos, sz size) {
    memcpy(dst, buf->mem + pos * size, size);
}

// Pops a number of bytes from a growable buffer into the given destination,
// copying the result and reducing the size of the buffer.
void
buf_pop(Buf *buf, void *dst, sz size) {
    assert(buf->mem + buf->size - size >= buf->mem);
    memcpy(dst, buf->mem + buf->size - size, size);
    buf->size -= size;
}

// A string or string view.
typedef Array Str;

// Create a string object from a C literal.
#define cstr(s)               \
    (Str) {                   \
        (u8 *)(s), LEN(s) - 1 \
    }

// Create a string object from a char* array.
#define STR(s)             \
    (Str){                 \
        .mem = (u8 *)(s),  \
        .size = strlen(s), \
    };

bool
str_eq(Str a, Str b) {
    return array_eq(a, b);
}

Str
str_split(Str *a, Str split) {
    assert(a != NULL);
    Str ret = *a;
    SearchResult res = array_find_next(*a, split);
    if (res.found) {
        ret.size = res.pos;
        a->mem += res.pos + res.matched;
        a->size -= res.pos + res.matched;
        return ret;
    }
    *a = (Str){0};
    return ret;
}

// A customizable splitting function.
typedef sz(StrSplitFn)(Str s);

Str
str_split_fn(Str *a, StrSplitFn split_fn) {
    assert(a != NULL);
    Str ret = *a;
    while (a->size > 0) {
        sz advance = split_fn(*a);
        if (advance) {
            ret.size -= a->size;
            a->size -= advance;
            a->mem += advance;
            return ret;
        }
        a->size--;
        a->mem++;
    }
    return ret;
}

// Replaces a single pattern on a string. `from` and `to` have to be of the same
// size.
void
str_replace(Str *a, Str from, Str to) {
    assert(a != NULL);
    assert(from.size == to.size);
    SearchResult res = array_find_next(*a, from);
    if (res.found) {
        memcpy(a->mem + res.pos, to.mem, res.matched);
        return;
    }
}

// Same as `str_replace` but applied to all occurences of `from`.
void
str_replace_all(Str *a, Str from, Str to) {
    assert(a != NULL);
    assert(from.size == to.size);
    Str data = *a;
    SearchResult res = array_find_next(data, from);
    while (res.found) {
        memcpy(data.mem + res.pos, to.mem, res.matched);
        data.mem += res.pos;
        data.size -= res.pos;
        res = array_find_next(data, from);
    }
}

bool
str_has_prefix(Str str, Str prefix) {
    if (str.size < prefix.size) {
        return false;
    }
    Str candidate = (Str){
        .mem = str.mem,
        .size = prefix.size,
    };
    return str_eq(candidate, prefix);
}

bool
str_has_suffix(Str str, Str suffix) {
    if (str.size < suffix.size) {
        return false;
    }
    Str candidate = (Str){
        .mem = str.mem + str.size - suffix.size,
        .size = suffix.size,
    };
    return str_eq(candidate, suffix);
}

Str
str_remove_prefix(Str str, Str prefix) {
    if (!str_has_prefix(str, prefix)) {
        return str;
    }
    str.mem += prefix.size;
    str.size -= prefix.size;
    return str;
}

Str
str_remove_suffix(Str str, Str suffix) {
    if (!str_has_suffix(str, suffix)) {
        return str;
    }
    str.size -= suffix.size;
    return str;
}

// Concat.
Str
str_concat(Str x, Str y, Arena *a) {
    Buf buf = {0};
    buf_insert(&buf, x.mem, x.size, a);
    buf_insert(&buf, y.mem, y.size, a);
    return (Str){
        .mem = buf.mem,
        .size = buf.size,
    };
}

Str
str_insert(Str orig, Str value, sz position, Arena *a) {
    Buf buf = {0};
    buf_insert(&buf, orig.mem, position, a);
    buf_insert(&buf, value.mem, value.size, a);
    buf_insert(&buf, orig.mem + position, orig.size - position, a);
    return (Str){
        .mem = buf.mem,
        .size = buf.size,
    };
}

// Str
// str_delete(Str orig, Str value, Arena *a) {
//     Buf buf = {0};
//     // TODO: find first location
//     // TODO: insert orig until that location
//     // TODO: insert orig after location + value.size
//     // buf_insert(&buf, orig.mem, position, a);
//     // buf_insert(&buf, value.mem, value.size, a);
//     // buf_insert(&buf, orig.mem + position, orig.size - position, a);
//     return (Str){
//         .mem = buf.mem,
//         .size = buf.size,
//     };
// }

Str
str_from_int(sz num, Arena *a) {
    u8 tmp[64];
    u8 *end = tmp + sizeof(tmp);
    u8 *beg = end;
    sz t = num > 0 ? num : -num;
    do {
        *--beg = '0' + t % 10;
    } while (t /= 10);
    if (num < 0) {
        *--beg = '-';
    }
    sz num_size = end - beg;
    Str parsed = {
        .mem = arena_malloc(num_size, a),
        .size = num_size,
    };
    memcpy(parsed.mem, beg, num_size);
    return parsed;
}

Str
str_from_hex(u64 num, sz zeroes, Arena *a) {
    char char_map[] = "0123456789abcdef";
    u8 tmp[64];
    zeroes = MIN((sz)sizeof(ptrsize) * 2, zeroes);
    u8 *end = tmp + sizeof(tmp);
    u8 *beg = end;
    u64 t = num;
    do {
        *--beg = char_map[t % 16];
    } while (t /= 16);
    zeroes -= end - beg;
    while (zeroes-- > 0) {
        *--beg = '0';
    }
    sz num_size = end - beg;
    Str parsed = {
        .mem = arena_malloc(num_size, a),
        .size = num_size,
    };
    memcpy(parsed.mem, beg, num_size);
    return parsed;
}

Str
str_from_bin(sz num, sz zeroes, Arena *a) {
    char char_map[] = "01";
    u8 tmp[64];
    zeroes = MIN((sz)sizeof(ptrsize) * 2, zeroes);
    u8 *end = tmp + sizeof(tmp);
    u8 *beg = end;
    sz t = num > 0 ? num : -num;
    do {
        *--beg = char_map[t % 2];
    } while (t /= 2);
    zeroes -= end - beg;
    while (zeroes-- > 0) {
        *--beg = '0';
    }
    sz num_size = end - beg;
    Str parsed = {
        .mem = arena_malloc(num_size, a),
        .size = num_size,
    };
    memcpy(parsed.mem, beg, num_size);
    return parsed;
}

Str
str_from_float(f64 num, sz precision, Arena *a) {
    if (num == 0x7ff0000000000000L) {
        return cstr("inf");
    }
    if (num == 0xfff0000000000000L) {
        return cstr("-inf");
    }
    if (num == 0x7ff8000000000000L) {
        return cstr("nan");
    }
    if (precision == 0) {
        num += 0.5;
        sz integral = num;
        return str_from_int(integral, a);
    }
    Str parsed = {0};
    sz prec = 1;
    while (precision > 0) {
        prec *= 10;
        precision--;
    }
    if (num < 0) {
        parsed = str_concat(parsed, cstr("-"), a);
        num = -num;
    }
    num += 0.5 / prec;
    sz integral = num;
    sz fractional = (num - integral) * prec;

    parsed = str_concat(parsed, str_from_int(integral, a), a);
    parsed = str_concat(parsed, cstr("."), a);
    for (sz i = prec / 10; i > 1; i /= 10) {
        if (i > fractional) {
            parsed = str_concat(parsed, cstr("0"), a);
        }
    }
    parsed = str_concat(parsed, str_from_int(fractional, a), a);
    return parsed;
}

char
str_next(Str *s) {
    assert(s->mem);
    if (s->size == 0) {
        return EOF;
    }
    char c = *s->mem++;
    s->size--;
    return c;
}

char
str_peek(Str s) {
    assert(s.mem);
    if (s.size == 0) {
        return EOF;
    }
    return *s.mem;
}

sz
str_to_int(Str s) {
    sz num = 0;
    if (str_has_prefix(s, cstr("0b"))) {
        // Binary number.
        s = str_remove_prefix(s, cstr("0b"));
        while (s.size) {
            char c = str_next(&s);
            if (c == '_') {
                continue;
            }
            assert(c == '0' || c == '1');
            num = num * 2 + (c - '0');
        }
    } else if (str_has_prefix(s, cstr("0x"))) {
        // Hex number.
        s = str_remove_prefix(s, cstr("0x"));
        while (s.size) {
            char c = str_next(&s);
            if (c == '_') {
                continue;
            }
            assert((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') ||
                   (c >= 'A' && c <= 'F'));
            if (c >= '0' && c <= '9') {
                num = num * 16 + (c - '0');
            } else if (c >= 'a' && c <= 'f') {
                num = num * 16 + (c - 'a' + 10);
            } else if (c >= 'A' && c <= 'F') {
                num = num * 16 + (c - 'A' + 10);
            }
        }
    } else {
        // Decimal number.
        char c = str_peek(s);
        sz neg = 1;
        if (c == '-') {
            neg = -1;
            str_next(&s);
        } else if (c == '+') {
            str_next(&s);
        }
        // TODO: check if it fits within the s64 range.
        while (s.size) {
            char c = str_next(&s);
            if (c == '_') {
                continue;
            }
            assert(c >= '0' && c <= '9');
            num = num * 10 + (c - '0');
        }
        num *= neg;
    }
    return num;
}

u64
str_to_uint(Str s) {
    u64 num = 0;
    if (str_has_prefix(s, cstr("0b"))) {
        // Binary number.
        s = str_remove_prefix(s, cstr("0b"));
        while (s.size) {
            char c = str_next(&s);
            if (c == '_') {
                continue;
            }
            assert(c == '0' || c == '1');
            num = num * 2 + (c - '0');
        }
    } else if (str_has_prefix(s, cstr("0x"))) {
        // Hex number.
        s = str_remove_prefix(s, cstr("0x"));
        while (s.size) {
            char c = str_next(&s);
            if (c == '_') {
                continue;
            }
            assert((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') ||
                   (c >= 'A' && c <= 'F'));
            if (c >= '0' && c <= '9') {
                num = num * 16 + (c - '0');
            } else if (c >= 'a' && c <= 'f') {
                num = num * 16 + (c - 'a' + 10);
            } else if (c >= 'A' && c <= 'F') {
                num = num * 16 + (c - 'A' + 10);
            }
        }
    } else {
        // Decimal number.
        char c = str_peek(s);
        assert(c != '-');
        if (c == '+') {
            str_next(&s);
        }
        while (s.size) {
            char c = str_next(&s);
            if (c == '_') {
                continue;
            }
            assert(c >= '0' && c <= '9');
            num = num * 10 + (c - '0');
        }
    }
    return num;
}

f64
str_to_float(Str s) {
    char c = str_peek(s);
    f64 neg = 1.0;
    if (c == '-') {
        neg = -1.0;
        str_next(&s);
    } else if (c == '+') {
        str_next(&s);
    }
    f64 num = 0.0;
    // Integral part.
    while (s.size) {
        char c = str_next(&s);
        if (c == '_') {
            continue;
        }
        if (c == '.') {
            break;
        }
        assert(c >= '0' && c <= '9');
        num = num * 10 + (c - '0');
    }
    // Fractional part.
    f64 frac = 0;
    sz frac_digits = 1;
    bool has_exponent = false;
    while (s.size) {
        char c = str_next(&s);
        if (c == '_') {
            continue;
        }
        if (c == 'e' || c == 'E') {
            has_exponent = true;
            break;
        }
        assert(c >= '0' && c <= '9');
        frac = frac * 10 + (c - '0');
        frac_digits *= 10;
    }
    num *= neg;
    num += frac / frac_digits;
    if (has_exponent) {
        bool exp_neg = false;
        char c = str_peek(s);
        if (c == '-') {
            exp_neg = true;
            str_next(&s);
        } else if (c == '+') {
            str_next(&s);
        }
        sz exponent = 0;
        while (s.size) {
            c = str_next(&s);
            if (c == '_') {
                continue;
            }
            assert(c >= '0' && c <= '9');
            exponent = exponent * 10 + (c - '0');
        }
        for (sz i = 0; i < exponent; i++) {
            if (!exp_neg) {
                num *= 10;
            } else {
                num /= 10;
            }
        }
    }
    return num;
}

//
// Queue.
//

typedef struct QueueVal {
    struct QueueVal *next;
    void *val;
} QueueVal;

typedef struct Queue {
    QueueVal *head;
    QueueVal *tail;
    sz size;
} Queue;

void
queue_push(Queue *l, void *val, Arena *a) {
    assert(l);
    QueueVal *next = arena_calloc(sizeof(QueueVal), a);
    next->val = val;
    if (l->size == 0) {
        l->head = next;
        l->tail = next;
        l->size = 1;
        return;
    }
    QueueVal *cur = l->tail;
    cur->next = next;
    l->tail = next;
    l->size++;
}

void *
queue_peek(Queue *l) {
    assert(l);
    if (l->size == 0) {
        return NULL;
    }
    QueueVal *cur = l->head;
    return cur->val;
}

void *
queue_pop(Queue *l) {
    assert(l);
    if (l->size == 0) {
        return NULL;
    }
    QueueVal *cur = l->head;
    l->head = cur->next;
    l->size--;
    return cur->val;
}

//
// Map.
//

// Specialiced commonly used hash sets/maps as macro definitions. There is no
// delete on these ones but are trivial to implement!
#define SETDEF(STRUCTNAME, FUNCNAME, KEYTYPE, HASHFUNC, EQFUNC)            \
    typedef struct STRUCTNAME {                                            \
        struct STRUCTNAME *child[4];                                       \
        KEYTYPE key;                                                       \
    } STRUCTNAME;                                                          \
    STRUCTNAME *FUNCNAME##_lookup(STRUCTNAME **m, KEYTYPE key) {           \
        u64 h = HASHFUNC(key);                                             \
        while (*m) {                                                       \
            if (EQFUNC(key, (*m)->key)) {                                  \
                return *m;                                                 \
            }                                                              \
            h = (h << 2) | (h >> 62);                                      \
            m = &(*m)->child[h & 0x3];                                     \
        }                                                                  \
        return NULL;                                                       \
    }                                                                      \
    STRUCTNAME *FUNCNAME##_insert(STRUCTNAME **m, KEYTYPE key, Arena *a) { \
        u64 h = HASHFUNC(key);                                             \
        while (*m) {                                                       \
            if (EQFUNC(key, (*m)->key)) {                                  \
                return *m;                                                 \
            }                                                              \
            h = (h << 2) | (h >> 62);                                      \
            m = &(*m)->child[h & 0x3];                                     \
        }                                                                  \
        *m = arena_calloc(sizeof(STRUCTNAME), a);                          \
        (*m)->key = key;                                                   \
        return *m;                                                         \
    }                                                                      \
    typedef Queue STRUCTNAME##Iter;                                        \
    STRUCTNAME##Iter FUNCNAME##_iterator(STRUCTNAME *map, Arena *a) {      \
        STRUCTNAME##Iter it = {0};                                         \
        queue_push(&it, map, a);                                           \
        return it;                                                         \
    }                                                                      \
    STRUCTNAME *FUNCNAME##_next(STRUCTNAME##Iter *it, Arena *a) {          \
        assert(it);                                                        \
        assert(a);                                                         \
        while (it->head) {                                                 \
            STRUCTNAME *item = (STRUCTNAME *)queue_pop(it);                \
            if (!item) {                                                   \
                return NULL;                                               \
            }                                                              \
            for (sz i = 0; i < 4; i++) {                                   \
                STRUCTNAME *child = item->child[i];                        \
                if (child) {                                               \
                    queue_push(it, child, a);                              \
                }                                                          \
            }                                                              \
            return item;                                                   \
        }                                                                  \
        return NULL;                                                       \
    }

#define MAPDEF(STRUCTNAME, FUNCNAME, KEYTYPE, VALTYPE, HASHFUNC, EQFUNC)    \
    typedef struct STRUCTNAME {                                             \
        struct STRUCTNAME *child[4];                                        \
        KEYTYPE key;                                                        \
        VALTYPE val;                                                        \
    } STRUCTNAME;                                                           \
    STRUCTNAME *FUNCNAME##_insert(STRUCTNAME **m, KEYTYPE key, VALTYPE val, \
                                  Arena *a) {                               \
        u64 h = HASHFUNC(key);                                              \
        while (*m) {                                                        \
            if (EQFUNC(key, (*m)->key)) {                                   \
                (*m)->val = val;                                            \
                return *m;                                                  \
            }                                                               \
            h = (h << 2) | (h >> 62);                                       \
            m = &(*m)->child[h & 0x3];                                      \
        }                                                                   \
        *m = arena_calloc(sizeof(STRUCTNAME), a);                           \
        (*m)->key = key;                                                    \
        (*m)->val = val;                                                    \
        return *m;                                                          \
    }                                                                       \
    STRUCTNAME *FUNCNAME##_lookup(STRUCTNAME **m, KEYTYPE key) {            \
        u64 h = HASHFUNC(key);                                              \
        while (*m) {                                                        \
            if (EQFUNC(key, (*m)->key)) {                                   \
                return *m;                                                  \
            }                                                               \
            h = (h << 2) | (h >> 62);                                       \
            m = &(*m)->child[h & 0x3];                                      \
        }                                                                   \
        return NULL;                                                        \
    }                                                                       \
    typedef Queue STRUCTNAME##Iter;                                         \
    STRUCTNAME##Iter FUNCNAME##_iterator(STRUCTNAME *map, Arena *a) {       \
        STRUCTNAME##Iter it = {0};                                          \
        queue_push(&it, map, a);                                            \
        return it;                                                          \
    }                                                                       \
    STRUCTNAME *FUNCNAME##_next(STRUCTNAME##Iter *it, Arena *a) {           \
        assert(it);                                                         \
        assert(a);                                                          \
        while (it->head) {                                                  \
            STRUCTNAME *item = (STRUCTNAME *)queue_pop(it);                 \
            if (!item) {                                                    \
                return NULL;                                                \
            }                                                               \
            for (sz i = 0; i < 4; i++) {                                    \
                STRUCTNAME *child = item->child[i];                         \
                if (child) {                                                \
                    queue_push(it, child, a);                               \
                }                                                           \
            }                                                               \
            return item;                                                    \
        }                                                                   \
        return NULL;                                                        \
    }

u64
str_hash(Str s) {
    u64 h = 0x100;
    for (sz i = 0; i < s.size; i++) {
        h ^= s.mem[i];
        h *= 1111111111111111111u;
    }
    return h;
}

bool
_int_eq(sz a, sz b) {
    return a == b;
}

bool
_int_hash(sz a) {
    return a * UINT64_C(11400714819323198485);
}

// Commonly used map/set types.
SETDEF(StrSet, strset, Str, str_hash, str_eq)
MAPDEF(StrIntMap, strintmap, Str, sz, str_hash, str_eq)
SETDEF(IntSet, intset, sz, _int_hash, _int_eq)
MAPDEF(IntStrMap, intstrmap, sz, Str, _int_hash, _int_eq)

//
// Dynamic arrays.
//

typedef struct ArrayHeader {
    sz size;
    sz cap;
} ArrayHeader;

// Header/Size/capacity accessors.
#define array_head(ARR) ((ArrayHeader *)((char *)(ARR) - sizeof(ArrayHeader)))
#define array_size(ARR) ((ARR) ? array_head(ARR)->size : 0)
#define array_cap(ARR) ((ARR) ? array_head(ARR)->cap : 0)

// Initialize a dynamic array ARR with N elements. The initialization doesn't
// zero out the data, so thread carefully. Use array_zero instead if that's what
// you need.
#define array_init(ARR, N, ARENA) \
    ((ARR) = _array_reserve(N, sizeof(*(ARR)), (ARENA)))
#define array_zero(ARR, N, ARENA) \
    ((ARR) = _array_reserve_zero(N, sizeof(*(ARR)), (ARENA)))

// Push a given element T to the dynamic array ARR.
#define array_push(ARR, T, ARENA)                          \
    ((ARR) = _array_maybe_grow((ARR), sizeof(T), (ARENA)), \
     (ARR)[array_head(ARR)->size++] = (T))

// Return the last element of the array. Can be used to build stacks.
#define array_pop(ARR) \
    ((ARR) && array_size(ARR) ? (ARR)[--array_head(ARR)->size] : NULL)

// Return the value stored at the OFFSET position from the tail of the array.
#define array_peek(ARR, OFFSET) (ARR)[array_head(ARR)->size - 1 - (OFFSET)]

// Insert N bytes from the SRC array into the ARR dynamic array.
#define array_insert(ARR, SRC, N, ARENA) \
    ((ARR) = _array_insert((ARR), (SRC), (N), sizeof(*(ARR)), (ARENA)))

// Free the memory from the original allocated position.
#define array_free(ARR) ((ARR) ? free(array_head(ARR)), (ARR) = NULL : 0)

static inline void *
_array_reserve(sz num_elem, sz type_size, Arena *a) {
    u8 *p = arena_malloc(num_elem * type_size + sizeof(ArrayHeader), a);
    p += sizeof(ArrayHeader);
    array_head(p)->size = 0;
    array_head(p)->cap = num_elem;
    return p;
}

static inline void *
_array_reserve_zero(sz num_elem, sz type_size, Arena *a) {
    u8 *p = arena_calloc(num_elem * type_size + sizeof(ArrayHeader), a);
    p += sizeof(ArrayHeader);
    array_head(p)->size = 0;
    array_head(p)->cap = num_elem;
    return p;
}

static inline void *
_array_maybe_grow(void *arr, sz type_size, Arena *a) {
    if (!arr) {
        arr = _array_reserve(0, 0, a);
    }
    ArrayHeader *head = array_head(arr);
    if (head->cap == head->size) {
        sz prev_size = head->cap * type_size + sizeof(ArrayHeader);
        if (head->cap == 0) {
            head->cap++;
        } else {
            head->cap *= 2;
        }
        sz new_size = head->cap * type_size + sizeof(ArrayHeader);
        head = (ArrayHeader *)arena_realloc(head, prev_size, new_size, a);
    }
    arr = (char *)head + sizeof(ArrayHeader);
    return arr;
}

static inline char *
_array_insert(char *arr, const char *src, sz n_bytes, sz type_size, Arena *a) {
    if (!arr) {
        arr = _array_reserve(0, 0, a);
    }
    ArrayHeader *head = array_head(arr);
    sz new_size = n_bytes + head->size;
    if (new_size > head->cap * type_size) {
        sz prev_size = head->cap * type_size + sizeof(ArrayHeader);
        if (head->cap == 0) {
            head->cap = 1;
        }
        while (new_size >= head->cap * type_size) {
            head->cap *= 2;
        }
        sz new_size = head->cap * type_size + sizeof(ArrayHeader);
        head = (ArrayHeader *)arena_realloc(head, prev_size, new_size, a);
    }
    arr = (char *)head + sizeof(ArrayHeader);
    memcpy((arr + head->size), src, n_bytes);
    head->size = new_size;
    return arr;
}

//
// Math.
//

typedef union Vec2f {
    struct {
        f32 x, y;
    };
    struct {
        f32 u, v;
    };
    struct {
        f32 left, right;
    };
    struct {
        f32 width, height;
    };
    f32 data[2];
} Vec2f;

typedef union Vec3f {
    struct {
        f32 x, y, z;
    };
    struct {
        f32 u, v, w;
    };
    struct {
        f32 r, g, b;
    };
    struct {
        Vec2f xy;
        f32 _z;
    };
    struct {
        f32 _x;
        Vec2f yz;
    };
    struct {
        Vec2f uv;
        f32 _w;
    };
    struct {
        f32 _u;
        Vec2f vw;
    };
    f32 data[2];
} Vec3f;

typedef union Vec4f {
    struct {
        f32 x, y, z, w;
    };
    struct {
        Vec3f xyz;
        f32 _w;
    };
    struct {
        union {
            Vec3f rgb;
            struct {
                f32 r, g, b;
            };
        };
        f32 a;
    };
    struct {
        Vec2f xy;
        f32 _y0;
        f32 _z0;
    };
    struct {
        f32 _x0;
        Vec2f yz;
        f32 _z1;
    };
    struct {
        f32 _x1;
        f32 _y1;
        Vec2f zw;
    };
    f32 data[4];
} Vec4f;

//
// OS/Platform stuff.
//

typedef enum {
    FILE_ERR_OK = 0,
    FILE_ERR_CANT_OPEN,
    FILE_ERR_READ_ERR,
    FILE_ERR_EMPTY,
    FILE_ERR_NUM,
} FileErr;

Str file_err_str[FILE_ERR_NUM] = {
    cstr(""),
    cstr("couldn't open file"),
    cstr("couldn't read file"),
    cstr("empty file"),
};

typedef struct FileContents {
    Str path;
    Array data;
    FileErr err;
} FileContents;

FileContents
platform_read_file(Str path, Arena *a) {
    // Transform Str to cstr.
    Str path_str = str_concat(path, cstr("\0"), a);

    // Read the entire file into memory.
    sz file_size = 0;
    FILE *fp = fopen((char *)path_str.mem, "rb+");
    if (!fp) {
        return (FileContents){
            .path = path,
            .err = FILE_ERR_CANT_OPEN,
        };
    }
    fseek(fp, 0, SEEK_END);
    file_size = ftell(fp);
    rewind(fp);
    u8 *memory = arena_malloc(file_size, a);
    sz read = fread(memory, 1, file_size, fp);
    fclose(fp);
    if (read == 0) {
        return (FileContents){
            .path = path,
            .err = FILE_ERR_EMPTY,
        };
    }
    return (FileContents){
        .path = path,
        .data = (Array){.mem = memory, .size = file_size},
        .err = FILE_ERR_OK,
    };
}

void *
platform_calloc(sz size, void *ctx) {
    (void)ctx;
    return calloc(1, size);
}

void *
platform_malloc(sz size, void *ctx) {
    (void)ctx;
    return malloc(size);
}

void *
platform_realloc(void *ptr, sz old_size, sz new_size, void *ctx) {
    (void)ctx;
    (void)old_size;
    (void)new_size;
    return realloc(ptr, new_size);
}

void
platform_free(void *ptr, void *ctx) {
    (void)ctx;
    free(ptr);
}

Allocator os_allocator = {
    .malloc = platform_malloc,
    .calloc = platform_calloc,
    .realloc = platform_realloc,
    .free = platform_free,
};

#include <time.h>
#include <unistd.h>

void
platform_sleep(size_t microseconds) {
    usleep(microseconds);
}

sz
platform_time(void) {
    struct timespec ts;
    timespec_get(&ts, TIME_UTC);
    return ts.tv_sec * 1000000000 + ts.tv_nsec;
}

//
// Custom logger.
//

// Our custom logging functions for structs and other entities.
typedef struct Logger Logger;
typedef void(LogFunc)(Logger *l, void *in);

typedef struct LogFuncMap {
    Str name;
    LogFunc *func;
} LogFuncMap;

typedef struct Logger {
    Buf buf;
    FILE *dest;
    LogFuncMap *func_map;
    Arena storage;
} Logger;

void
log_flush(Logger *l) {
    if (l->buf.size) {
        fprintf(l->dest, "%.*s", (int)l->buf.size, l->buf.mem);
        l->buf.size = 0;
    }
}

void
log_str(Logger *l, Str str) {
    assert(l);
    Buf *buf = &l->buf;
    assert(buf->mem);
    while (str.size > 0) {
        sz avail = buf->cap - buf->size;
        if (avail == 0) {
            log_flush(l);
            avail = buf->cap - buf->size;
            assert(avail > 0);
        }
        if (str.size < avail) {
            buf_insert(&l->buf, str.mem, str.size, &l->storage);
            str.size = 0;
            return;
        }
        buf_insert(&l->buf, str.mem, avail, &l->storage);
        str.mem += avail;
        str.size -= avail;
    }
}

void
log_byte(Logger *l, u8 b) {
    assert(l);
    Buf *buf = &l->buf;
    assert(buf->mem);
    sz avail = buf->cap - buf->size;
    if (avail == 0) {
        log_flush(l);
        avail = buf->cap - buf->size;
        assert(avail > 0);
    }
    buf_insert(&l->buf, &b, 1, &l->storage);
}
void
log_int(Logger *l, sz num) {
    assert(l);
    Arena scratch = l->storage;
    log_str(l, str_from_int(num, &scratch));
}

void
log_hex(Logger *l, sz num, sz zeroes) {
    assert(l);
    log_str(l, cstr("0x"));
    Arena scratch = l->storage;
    log_str(l, str_from_hex(num, zeroes, &scratch));
}

void
log_bin(Logger *l, sz num, sz zeroes) {
    assert(l);
    log_str(l, cstr("0b"));
    Arena scratch = l->storage;
    log_str(l, str_from_bin(num, zeroes, &scratch));
}

void
log_float(Logger *l, f64 num, sz precision) {
    assert(l);
    Arena scratch = l->storage;
    log_str(l, str_from_float(num, precision, &scratch));
}

void
log_print(Logger *l, Str format, ...) {
    assert(l);
    assert(l->buf.mem);
    va_list argp;
    va_start(argp, format);
    va_start(argp, format);
    while (format.size) {
        char c = str_next(&format);
        if (c == '%') {
            c = str_next(&format);
            switch (c) {
                case '%': {
                    log_byte(l, '%');
                } break;
                case 'd': {
                    // Integer decimal formatting.
                    sz num = va_arg(argp, sz);
                    log_int(l, num);
                } break;
                case 'c': {
                    // Integer decimal formatting.
                    u8 num = va_arg(argp, sz);
                    log_byte(l, num);
                } break;
                case 'x': {
                    // Hex number formatting.
                    sz num = va_arg(argp, sz);
                    char n = str_peek(format);
                    sz zeroes = 0;
                    if (n == '{') {
                        str_next(&format);
                        SearchResult res = array_find_next(format, cstr("}"));
                        if (res.found) {
                            Str arg = format;
                            arg.size = res.pos;
                            sz inc = res.pos + res.matched;
                            format.mem += inc;
                            format.size -= inc;
                            zeroes = str_to_int(arg);
                        } else {
                            break;
                        }
                    }
                    log_hex(l, num, zeroes);
                } break;
                case 'b': {
                    // Binary number formatting.
                    sz num = va_arg(argp, sz);
                    char n = str_peek(format);
                    sz zeroes = 0;
                    if (n == '{') {
                        str_next(&format);
                        SearchResult res = array_find_next(format, cstr("}"));
                        if (res.found) {
                            Str arg = format;
                            arg.size = res.pos;
                            sz inc = res.pos + res.matched;
                            format.mem += inc;
                            format.size -= inc;
                            zeroes = str_to_int(arg);
                        } else {
                            break;
                        }
                    }
                    log_bin(l, num, zeroes);
                } break;
                case 'f': {
                    // Floating point formatting.
                    f64 num = va_arg(argp, f64);
                    char n = str_peek(format);
                    sz precision = 4;
                    if (n == '{') {
                        str_next(&format);
                        SearchResult res = array_find_next(format, cstr("}"));
                        if (res.found) {
                            Str arg = format;
                            arg.size = res.pos;
                            sz inc = res.pos + res.matched;
                            format.mem += inc;
                            format.size -= inc;
                            precision = str_to_int(arg);
                        } else {
                            break;
                        }
                    }
                    log_float(l, num, precision);
                } break;
                case 's': {
                    // String formatting.
                    Str val = va_arg(argp, Str);
                    log_str(l, val);
                } break;
                case '{': {
                    SearchResult res = array_find_next(format, cstr("}"));
                    if (res.found) {
                        Str arg = format;
                        arg.size = res.pos;
                        sz inc = res.pos + res.matched;
                        format.mem += inc;
                        format.size -= inc;
                        void *val = va_arg(argp, void *);
                        for (sz i = 0; i < array_size(l->func_map); i++) {
                            if (str_eq(arg, l->func_map[i].name)) {
                                l->func_map[i].func(l, val);
                                break;
                            }
                        }
                    }
                } break;
            }
            continue;
        }
        log_byte(l, c);
    }
    log_flush(l);
    va_end(argp);
}

void
log_func_arena(Logger *l, void *in) {
    assert(l);
    Arena *val = in;
    log_str(l, cstr("Arena{ size: "));
    log_int(l, val->size);
    log_str(l, cstr(" cap: "));
    log_int(l, val->cap);
    log_str(l, cstr(" mem: "));
    log_hex(l, (ptrsize)val->beg, 16);
    log_str(l, cstr(" }"));
}

void
log_func_buf(Logger *l, void *in) {
    assert(l);
    Buf *val = in;
    log_str(l, cstr("Buf{ size: "));
    log_int(l, val->size);
    log_str(l, cstr(" cap: "));
    log_int(l, val->cap);
    log_str(l, cstr(" mem: "));
    log_hex(l, (ptrsize)val->mem, 16);
    log_str(l, cstr(" }"));
}

void
log_func_array(Logger *l, void *in) {
    assert(l);
    Array *val = in;
    log_str(l, cstr("Array{ size: "));
    log_int(l, val->size);
    log_str(l, cstr(" mem: "));
    log_hex(l, (ptrsize)val->mem, 16);
    log_str(l, cstr(" }"));
}

void
log_func_memory(Logger *l, void *in) {
    assert(l);
    Array *val = in;
    for (sz i = 0; i < MIN(64, val->size); i++) {
        Arena scratch = l->storage;
        log_str(l, str_from_hex(val->mem[i], 2, &scratch));
        if ((i + 1) % 16 == 0) {
            log_str(l, cstr("\n"));
        } else {
            log_str(l, cstr(" "));
        }
    }
}

#define LOG_BUF_SIZE KB(1)
#define LOG_MEM_SIZE KB(2)

Logger
log_init(sz memsize, FILE *dest, Arena arena) {
    Logger logger = {
        .dest = dest,
        .storage = arena,
    };
    buf_reserve(&logger.buf, memsize, &logger.storage);
    return logger;
}

// Default loggers and convenience macros for printing.
Logger logger_inf, logger_err;

#define _print(format, ...) \
    log_print(&logger_inf, (Str){(u8 *)(format), LEN(format) - 1}, __VA_ARGS__)
#define _println(format, ...) print(format "\n", __VA_ARGS__)
#define print(...) _print(__VA_ARGS__, "")
#define println(...) _println(__VA_ARGS__, "")

#define _eprint(format, ...) \
    log_print(&logger_err, (Str){(u8 *)(format), LEN(format) - 1}, __VA_ARGS__)
#define _eprintln(format, ...) eprint(format "\n", __VA_ARGS__)
#define eprint(...) _eprint(__VA_ARGS__, "")
#define eprintln(...) _eprintln(__VA_ARGS__, "")

void
log_func_register(Logger *l, LogFuncMap map) {
    array_push(l->func_map, map, &l->storage);
}

void
log_init_default(void) {
    // Allocate and initialize loggers.
    Arena arena_inf = arena_create(LOG_MEM_SIZE, os_allocator);
    Arena arena_err = arena_create(LOG_MEM_SIZE, os_allocator);
    logger_inf = log_init(LOG_BUF_SIZE, stdout, arena_inf);
    logger_err = log_init(LOG_BUF_SIZE, stderr, arena_err);

    // Register default log_funcs into loggers.
    array_init(logger_inf.func_map, 16, &logger_inf.storage);
    array_init(logger_err.func_map, 16, &logger_err.storage);
    LogFuncMap log_funcs[] = {
        {cstr("Arena"), log_func_arena},
        {cstr("Buf"), log_func_buf},
        {cstr("Array"), log_func_array},
        {cstr("Mem"), log_func_memory},
    };
    for (sz i = 0; i < LEN(log_funcs); i++) {
        log_func_register(&logger_inf, log_funcs[i]);
        log_func_register(&logger_err, log_funcs[i]);
    }
}

#endif  // BADLIB_H