Skip to content

Instantly share code, notes, and snippets.

@pervognsen pervognsen/std.ion.c
Last active Feb 26, 2019

Embed
What would you like to do?
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))");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.