std.ion.c

import libc {...}

struct Indexer {
    get: func(data: void*, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize;
    put: func(data: void*, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize;
    del: func(data: void*, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize;
    set: func(data: void*, a: void const*, x: void const *, xi: usize, len: usize, stride: usize, size: usize);
    free: func(data: void*);
}

struct Index {
    data: void*;
    indexer: Indexer*;
}

@inline
func index_get(index: Index, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize {
    return index.indexer.get(index.data, a, x, len, stride, size);
}

@inline
func index_put(index: Index, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize {
    return index.indexer.put(index.data, a, x, len, stride, size);
}

@inline
func index_del(index: Index, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize {
    return index.indexer.del(index.data, a, x, len, stride, size);
}

@inline
func index_set(index: Index, a: void const*, x: void const*, xi: usize, len: usize, stride: usize, size: usize) {
    #assert(xi < len);
    index.indexer.set(index.data, a, x, xi, len, stride, size);
}

@inline
func index_free(index: Index) {
    index.indexer.free(index.data);
}

func null_set(data: void*, a: void const*, x: void const*, xi: usize, len: usize, stride: usize, size: usize) {
}

func null_free(data: void*) {
}

func linear_get(data: void*, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize {
    for (i := 0; i < len; i++) {
        if (memcmp(a + i*stride, x, size) == 0) {
            return i;
        }
    }
    return len;
}

var linear_indexer_const = Indexer{
    get = linear_get,
    put = linear_get,
    del = linear_get,
    set = null_set,
    free = null_free,
};

var linear_indexer = &linear_indexer_const;

struct HashSlot {
    i: uint32;
    h: uint32;
}

struct HashIndex {
    slots: HashSlot*;
    mask: uint32;
    occupied: uint32;
    max_occupied: uint32;
}

const HASH_EMPTY: uint32 = 0xffffffff;
const HASH_DELETED: uint32 = 0xfffffffe;
const HASH_MIN_SLOTS: uint32 = 16;

func hash(buf: void const*, size: usize): uint64 {
    h: uint64 = 0xcbf29ce484222325;
    ptr: char const* = buf;
    for (i := 0; i < size; i++) {
        h ^= *ptr++;
        h *= 0x100000001b3;
        h ^= h >> 32;
    }
    return h;
}

func next_pow2(x: uint32): uint32 {
    x--;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x++;
    return x;
}

func hash_init(index: HashIndex*, len: uint32) {
    num_slots := next_pow2(len + len/2);
    if (num_slots < HASH_MIN_SLOTS) {
        num_slots = HASH_MIN_SLOTS;
    }
    index.slots = 0;
    index.mask = num_slots - 1;
    index.occupied = 0;
    index.max_occupied = num_slots/2 + num_slots/4;
    afill(index.slots, {HASH_EMPTY}, num_slots);
}

func hash_get_slot(index: HashIndex*, a: void const*, x: void const*, h: uint32, stride: usize, size: usize): HashSlot* {
    for (i := h & index.mask) {
        slot := &index.slots[i];
        if (slot.i == HASH_EMPTY || (slot.i != HASH_DELETED && h == slot.h && memcmp(a + slot.i*stride, x, size) == 0)) {
            return slot;
        }
        i++;
        if (i == alen(index.slots)) {
            i = 0;
        }
    }
    return 0;
}

func hash_put_slot(index: HashIndex*, new_slot: HashSlot) {
    for (i := new_slot.h & index.mask) {
        slot := &index.slots[i];
        if (slot.i == HASH_EMPTY) {
            *slot = new_slot;
            index.occupied++;
            return;
        }
        i++;
        if (i == alen(index.slots)) {
            i = 0;
        }
    }
}

func hash_get(data: void*, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize {
    index: HashIndex* = data;
    h := hash(x, size);
    slot := hash_get_slot(index, a, x, h, stride, size);
    if (slot.i == HASH_EMPTY) {
        return len;
    } else {
        return slot.i;
    }
}

func hash_put(data: void*, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize {
    index: HashIndex* = data;
    h := hash(x, size);
    slot := hash_get_slot(index, a, x, h, stride, size);
    if (slot.i == HASH_EMPTY) {
        *slot = {len, h};
        index.occupied++;
        if (index.occupied >= index.max_occupied) {
            hash_rehash(index, len + 1);
        }
        return len;
    } else {
        return slot.i;
    }
}

func hash_del(data: void*, a: void const*, x: void const*, len: usize, stride: usize, size: usize): usize {
    index: HashIndex* = data;
    h := hash(x, size);
    slot := hash_get_slot(index, a, x, h, stride, size);
    i := slot.i;
    if (i != HASH_EMPTY) {
        *slot = {HASH_DELETED};
        return i;
    } else {
        return len;
    }
}

func hash_set(data: void*, a: void const*, x: void const*, xi: usize, len: usize, stride: usize, size: usize) {
    index: HashIndex* = data;
    h := hash(x, size);
    slot := hash_get_slot(index, a, x, h, stride, size);
    i := slot.i;
    *slot = {xi, h};
    if (i == HASH_EMPTY) {
        index.occupied++;
        if (index.occupied >= index.max_occupied) {
            hash_rehash(index, len + 1);
        }
    }
}

func hash_free(data: void*) {
    index: HashIndex* = data;
    afree(index.slots);
    free(index);
}

func hash_rehash(index: HashIndex*, len: uint32) {
    new_index: HashIndex;
    hash_init(&new_index, len);
    for (i := 0; i < alen(index.slots); i++) {
        slot := index.slots[i];
        if (slot.i < HASH_DELETED) {
            hash_put_slot(&new_index, slot);
        }
    }
    afree(index.slots);
    *index = new_index;
}

var hash_indexer_const = Indexer{
    get = hash_get,
    put = hash_put,
    del = hash_del,
    set = hash_set,
    free = hash_free,
};

var hash_indexer = &hash_indexer_const;

func hash_index(): Index {
    index: HashIndex* = malloc(sizeof(HashIndex));
    hash_init(index, 0);
    return Index{data = index, indexer = hash_indexer};
}

var default_indexer_const = Indexer{
    get = linear_get,
    put = linear_get,
    del = linear_get,
    set = null_set,
    free = null_free,
};

var default_indexer = &default_indexer_const;

struct ArrayHdr {
    len: usize;
    cap: usize;
    index: Index;
    buf: char[];
}

@inline
func ahdr(a: void*): ArrayHdr* {
    #foreign(preamble = "#define ahdr(a) ((std_ArrayHdr *)((char *)(a) - offsetof(std_ArrayHdr, buf)))");
    return a ? (:ArrayHdr*)(a - offsetof(ArrayHdr, buf)) : 0;
}

@inline
func alen(a: void*): usize {
    return a ? ahdr(a).len : 0;
}

@inline
func acap(a: void*): usize {
    return a ? ahdr(a).cap : 0;
}

@inline
func aclear(a: void*) {
    if (a) {
        ahdr(a).len = 0;
    }
}

@inline
func afree_func(ap: void**) {
    a := *ap;
    if (a) {
        index := ahdr(a).index;
        #assert(index.indexer);
        index.indexer.free(index.data);
    }
    free(ahdr(a));
    *ap = 0;
}

@foreign
func afree(a: void*) {
    afree_func;
    #foreign(preamble = "#define afree(a) std_afree_func(&(a))");
}

func aalloc_func(): void* {
    hdr: ArrayHdr* = malloc(sizeof(ArrayHdr));
    hdr.len = 0;
    hdr.cap = 0;
    hdr.index = {indexer = default_indexer};
    return hdr.buf;
}

@inline
func ainit_func(ap: void**) {
    if (!*ap) {
        *ap = aalloc_func();
    }
}

@inline
func apop(a: void*) {
    if (alen(a) > 0) {
        ahdr(a).len--;
    }
}

func afill_func(ap: void**, x: void const*, n: usize, elem_size: usize) {
    afit_func(ap, alen(*ap) + n, elem_size);
    a := *ap;
    p := a + alen(a)*elem_size;
    for (i := 0; i < n; i++) {
        memcpy(p, x, elem_size);
        p += elem_size;
    }
    ahdr(a).len += n;
}

@foreign @intrinsic
func afill(a: void*, x: void, n: usize) {
    afill_func;
    #foreign(preamble = "#define afill(t, a, x, n) std_afill_func(&(a), (t[]){x}, n, sizeof(t))");
}

@foreign
func asetcap(a: void*, new_cap: usize) {
    asetcap_func;
    #foreign(preamble = "#define asetcap(a, n) std_asetcap_func(&(a), (n), sizeof(*(a)))");
}

@foreign
func afit(a: void*, min_cap: usize) {
    afit_func;
    #foreign(preamble = "#define afit(a, n) std_afit_func(&(a), (n), sizeof(*(a)))");
}

@foreign @intrinsic
func apush(a: void*, x: void) {
    acap;
    alen;
    ahdr;
    asetcap_func;
    #foreign(preamble = """#define apush(t, a, x)                                  \
    do {                                                \
        void **__ap = &(a);                             \
        void *__a = *__ap;                              \
        size_t __n = std_alen(__a);                     \
        if (__n < std_acap(__a)) {                      \
            ((t*)__a)[__n] = (x);                       \
            ahdr(__a)->len++;                           \
        } else {                                        \
            std_asetcap_func(__ap, __n+1, sizeof(t));   \
            __a = *__ap;                                \
            ((t*)__a)[__n] = (x);                       \
            ahdr(__a)->len++;                           \
        }                                               \
    } while(0)""");
}

@foreign
func aprintf(a: char*, fmt: char const*, ...) {
    aprintf_func;
    #foreign(preamble = "#define aprintf(a, fmt, ...) std_aprintf_func(&(a), (fmt), __VA_ARGS__)");
}

@foreign @intrinsic
func acatn(a: void*, src: void*, src_len: usize) {
    acatn_func;
    #foreign(preamble = "#define acatn(a, b, n) std_acatn_func(&(a), b, n, sizeof(*a))");
}

@foreign @intrinsic
func acat(a: void*, src: void*) {
    acat_func;
    #foreign(preamble = "#define acat(a, b) std_acat_func(&(a), b, sizeof(*a))");
}

func adeln_func(a: void*, i: usize, n: usize, elem_size: usize) {
    if (i >= alen(a)) {
        return;
    }
    if (i + n > alen(a)) {
        n = alen(a) - i;
    }
    memmove(a + i*elem_size, a + (i + n)*elem_size, (alen(a) - (i + n))*elem_size);
    ahdr(a).len -= n;
}

@foreign
func adel(a: void*, i: usize) {
    adeln_func;
    #foreign(preamble = "#define adel(a, i) std_adeln_func((a), (i), 1, sizeof(*(a)))");
}

@foreign
func adeln(a: void*, i: usize, n: usize) {
    adeln_func;
    #foreign(preamble = "#define adeln(a, i, n) std_adeln_func((a), (i), (n), sizeof(*(a)))");
}

func acatn_func(ap: void**, src: void const*, src_len: usize, elem_size: usize) {
    a := *ap;
    a_len := alen(a);
    afit_func(ap, a_len + src_len, elem_size);
    if (a != *ap && a <= src && src <= a + a_len*elem_size) {
        src = *ap + (src - a);
    }
    a = *ap;
    memmove(a + a_len*elem_size, src, src_len*elem_size);
    ahdr(a).len += src_len;
}

func acat_func(ap: void**, src: void*, elem_size: usize) {
    acatn_func(ap, src, alen(src), elem_size);
}

func aprintf_func(ap: char**, fmt: char const*, ...) {
    a := *ap;
    args: va_list;
    va_start(args, fmt);
    slack := acap(a) - alen(a);
    printed := vsnprintf(a + alen(a), slack, fmt, args) + 1;
    va_end(args);
    if (printed > slack) {
        afit(a, alen(a) + printed);
        va_start(args, fmt);
        new_slack := acap(a) - alen(a);
        printed = vsnprintf(a + alen(a), new_slack, fmt, args) + 1;
        va_end(args);
    }
    ahdr(a).len += printed - 1;
    *ap = a;
}

func asetcap_func(ap: void**, new_cap: usize, elem_size: usize) {
    a := *ap;
    cap := acap(a);
    if (new_cap > cap) {
        if (new_cap < 16) {
            new_cap = 16;
        }
        if (2*new_cap < 3*cap) {
            new_cap = cap + cap/2;
        }
    }
    size := offsetof(ArrayHdr, buf) + new_cap*elem_size;
    hdr: ArrayHdr*;
    if (a) {
        hdr = realloc(ahdr(a), size);
        if (hdr.len > new_cap) {
            hdr.len = new_cap;
        }
    } else {
        hdr = malloc(size);
        hdr.len = 0;
        hdr.index = {indexer = default_indexer};
    }
    hdr.cap = new_cap;
    *ap = hdr.buf;
}

@inline
func afit_func(ap: void**, min_cap: usize, elem_size: usize) {
    if (min_cap > acap(*ap)) {
        asetcap_func(ap, min_cap, elem_size);
    }
}

func iindex_func(ap: void**, new_index: Index, elem_size: usize, key_size: usize) {
    a := *ap;
    if (!a) {
        ainit_func(ap);
        a = *ap;
    }
    #assert(a);
    index := ahdr(a).index;
    index_free(index);
    ahdr(a).index = new_index;
    n := alen(a);
    for (i := 0; i < n; i++) {
        index_set(index, a, a + i*elem_size, i, n, elem_size, key_size);
    }
}

@foreign
func kindex(a: void*, new_index: Index) {
    iindex_func;
    #foreign(preamble = "#define kindex(a, new_index) std_iindex_func(&(a), (new_index), sizeof(*(a)), sizeof(*(a)))");
}

@foreign @intrinsic
func hindex(a: void*, new_index: Index) {
    iindex_func;
    #foreign(preamble = "#define hindex(t, a, new_index) std_iindex_func(&(a), (new_index), sizeof(*(a)), sizeof(t))");
}

func iget_func(a: void*, x: void const*, elem_size: usize, key_size: usize): usize {
    if (!a) {
        return 0;
    }
    return index_get(ahdr(a).index, a, x, alen(a), elem_size, key_size);
}

func iput_func(ap: void**, x: void const*, elem_size: usize, key_size: usize): usize {
    a := *ap;
    if (!a) {
        ainit_func(ap);
        a = *ap;
    }
    index := ahdr(a).index;
    n := alen(a);
    i := index_put(index, a, x, n, elem_size, key_size);
    if (i == n) {
        afit_func(ap, n + 1, elem_size);
        a = *ap;
        ahdr(a).len++;
    }
    memcpy(a + i*elem_size, x, elem_size);
    return i;
}

func idel_func(a: void*, x: void const*, elem_size: usize, key_size: usize) {
    if (!a) {
        return;
    }
    n := alen(a);
    index := ahdr(a).index;
    i := index_del(index, a, x, n, elem_size, key_size);
    if (i == n) {
        return;
    }
    if (i < n-1) {
        p := a + i*elem_size;
        q := a + (n-1)*elem_size;
        index_set(index, a, q, i, n, elem_size, key_size);
        memmove(p, q, elem_size);
    }
    ahdr(a).len--;
}

@foreign @intrinsic
func kdel(a: void*, k: void) {
    idel_func;
    #foreign(preamble = "#define kdel(t, a, x) std_idel_func((a), (t[]){x}, sizeof(t), sizeof(t))");
}

@foreign @intrinsic
func kget(a: void*, x: void): usize {
    iget_func;
    #foreign(preamble = "#define kget(t, a, x) std_iget_func((a), (t[]){x}, sizeof(t), sizeof(t))");
    return 0;
}

@foreign @intrinsic
func kput(a: void*, x: void) {
    iput_func;
    #foreign(preamble = "#define kput(t, a, x) std_iput_func(&(a), (t[]){x}, sizeof(t), sizeof(t))");
}

@foreign @intrinsic
func hget(a: void*, x: void): usize {
    iget_func;
    #foreign(preamble = "#define hget(t, a, x) std_iget_func((a), (t[]){x}, sizeof(*(a)), sizeof(t))");
    return 0;
}

@foreign @intrinsic
func hput(a: void*, k: void, v: void) {
    iput_func;
    #foreign(preamble = "#define hput(t, n, a, k, v) std_iput_func(&(a), &(t){(k), (v)}, sizeof(*(a)), sizeof((*a).n))");
}

@foreign @intrinsic
func hdel(a: void*, k: void) {
    idel_func;
    #foreign(preamble = "#define hdel(t, a, x) std_idel_func((a), (t[]){x}, sizeof(*(a)), sizeof(t))");
}