diff options
| -rw-r--r-- | dynarr.h | 32 | ||||
| -rw-r--r-- | ihash.h | 109 | ||||
| -rw-r--r-- | shash.h | 5 | ||||
| -rw-r--r-- | stdwrm.h | 6 | ||||
| -rw-r--r-- | str.h | 41 | ||||
| -rw-r--r-- | strio.h | 17 | ||||
| -rw-r--r-- | typ.h | 33 | ||||
| -rw-r--r-- | zone.h | 291 |
8 files changed, 506 insertions, 28 deletions
diff --git a/dynarr.h b/dynarr.h index 986c6ab..bbdd45f 100644 --- a/dynarr.h +++ b/dynarr.h @@ -4,9 +4,6 @@ #include <stdlib.h> #include <stdint.h> #include <string.h> -#include <err.h> - -#include "stdwrm.h" typedef struct { size_t count, capacity; } DynArrHeader; @@ -14,40 +11,43 @@ typedef struct { size_t count, capacity; } DynArrHeader; #define DA_HEADER(da) ((DynArrHeader*)(da) - 1) #define DA_INIT_CAP 16 -#define DA_INIT(da) {\ - char *da_init_ptr = ((char*)malloc(sizeof(DynArrHeader) + DA_INIT_CAP * sizeof(*da)));\ - if (!da_init_ptr) err(1, "dynamic array allocation failed");\ +#define DA_INIT_SZ(da, cap) do {\ + char *da_init_ptr = ((char*)malloc(sizeof(DynArrHeader) + cap * sizeof(*da)));\ + if (!da_init_ptr) { fprintf(stderr, "dynamic array allocation failed\n"); abort(); }\ da = (void *)(da_init_ptr + sizeof(DynArrHeader));\ - *DA_HEADER(da) = (DynArrHeader) { 0, DA_INIT_CAP };\ -} + *DA_HEADER(da) = (DynArrHeader) { 0, cap };\ +} while(0) + +#define DA_INIT(da) DA_INIT_SZ(da, DA_INIT_CAP) #define DA_FREE(da)\ free(DA_HEADER(da)) #define DA_LEN(da) (DA_HEADER(da)->count) -#define DA_FIT(da, count)\ +#define DA_FIT(da, count) do {\ if (count >= DA_HEADER(da)->capacity) {\ while (count >= DA_HEADER(da)->capacity) DA_HEADER(da)->capacity <<= 1;\ char *da_fit_ptr = realloc(DA_HEADER(da), sizeof(DynArrHeader) + DA_HEADER(da)->capacity * sizeof(*da));\ - if (!da_fit_ptr) err(1, "dynamic array reallocation failed");\ + if (!da_fit_ptr) { fprintf(stderr, "dynamic array reallocation failed\n"); abort(); }\ (da) = (void *)(da_fit_ptr + sizeof(DynArrHeader));\ - } + }\ +} while(0) -#define DA_PUSH(da, ...) {\ +#define DA_PUSH(da, ...) do {\ DA_FIT(da, DA_LEN(da) + 1);\ (da)[DA_HEADER(da)->count++] = (__VA_ARGS__);\ -} +} while(0) -#define DA_PUSH_MULT(da, buf, n) {\ +#define DA_PUSH_MULT(da, buf, n) do {\ DA_FIT(da, DA_LEN(da) + n);\ memcpy(&(da)[DA_HEADER(da)->count], buf, n * sizeof(*(da)));\ DA_HEADER(da)->count += n;\ -} +} while(0) #define DA_FOR(da, name)\ for (typeof(da) name = (da); name < &(da)[DA_LEN(da)]; name++) #define DA_FORVAL(da, name)\ - for (volatile typeof(*(da)) *da_iter = (da), name; da_iter < &(da)[DA_LEN(da)] && (name = *da_iter, 1); da_iter++) + for (volatile typeof(*(da)) *stdwrm__da_iter = (da), name; stdwrm__da_iter < &(da)[DA_LEN(da)] && (name = *stdwrm__da_iter, 1); stdwrm__da_iter++) #endif diff --git a/ihash.h b/ihash.h new file mode 100644 index 0000000..242e97c --- /dev/null +++ b/ihash.h @@ -0,0 +1,109 @@ +#ifndef IHASH_H +#define IHASH_H + +#include <stdlib.h> +#include <stdint.h> +#include <ctype.h> + +#include "dynarr.h" +#include "str.h" + +#ifndef IHASH_SLOTS +#define IHASH_SLOTS 8192 +#endif + +typedef uint64_t hash_t; + +typedef struct { + intptr_t key; + void *value; + hash_t hash; +} IntHashEntry; + +typedef struct { + DYNARR(IntHashEntry) entries; +} IntHashSlot; + +typedef struct { + IntHashSlot slots[IHASH_SLOTS]; +} IntHashTable; + +hash_t ihash(intptr_t s); +void ihash_init(IntHashTable *h); +void ihash_free(IntHashTable *h); +void *ihash_get(IntHashTable *h, intptr_t key); +void ihash_put(IntHashTable *h, intptr_t key, void *value); +IntHashEntry *ihash_find(IntHashTable *h, intptr_t key); + +#ifdef IHASH_IMPL + +/* murmur64 integer hash */ + +hash_t ihash(intptr_t h) { + h *= h >> 33; + h *= 0xff51afd7ed558ccdL; + h *= h >> 33; + h *= 0xc4ceb9fe1a85ec53L; + h *= h >> 33; + return h; +} + +/* hash table */ + +void ihash_init(IntHashTable *h) { + *h = (IntHashTable) { 0 }; +} + +void ihash_free(IntHashTable *h) { + for (unsigned i = 0; i < IHASH_SLOTS; i++) { + IntHashSlot *s = &h->slots[i]; + if (!s->entries) continue; + DA_FREE(s->entries); + } +} + +static inline int ihash_entry_match(IntHashEntry *h, intptr_t s, hash_t ihash) { + return s == ihash; +} + +static inline IntHashEntry *ihash_find_hashed(IntHashTable *h, intptr_t key, hash_t k) { + size_t i = k & (IHASH_SLOTS - 1); + if (h->slots[i].entries) { + DA_FOR(h->slots[i].entries, e) { + if (ihash_entry_match(e, key, k)) { + return e; + } + } + } + return NULL; +} + +IntHashEntry *ihash_find(IntHashTable *h, intptr_t key) { + return ihash_find_hashed(h, key, ihash(key)); +} + +void *ihash_get(IntHashTable *h, intptr_t key) { + IntHashEntry *e = ihash_find(h, key); + return e ? e->value : NULL; +} + +void ihash_put(IntHashTable *h, intptr_t key, void *value) { + hash_t keyh = ihash(key); + IntHashEntry *e = ihash_find_hashed(h, key, keyh); + if (e) { + e->value = value; + } else { + hash_t keyi = keyh & (IHASH_SLOTS - 1); + if (!h->slots[keyi].entries) { + DA_INIT(h->slots[keyi].entries); + } + DA_PUSH(h->slots[keyi].entries, (IntHashEntry) { + .key = key, + .value = value, + .hash = keyh + }); + } +} + +#endif +#endif diff --git a/shash.h b/shash.h index 537449e..e039ebb 100644 --- a/shash.h +++ b/shash.h @@ -5,7 +5,6 @@ #include <stdint.h> #include <ctype.h> -#include "stdwrm.h" #include "dynarr.h" #include "str.h" @@ -36,7 +35,7 @@ void *shash_get(StrHashTable *h, strv_t key); void shash_put(StrHashTable *h, strv_t key, void *value); StrHashEntry *shash_find(StrHashTable *h, strv_t key); -#ifdef STDWRM_IMPL_SHASH +#ifdef SHASH_IMPL /* hacky FNV-1a hash */ @@ -44,7 +43,7 @@ StrHashEntry *shash_find(StrHashTable *h, strv_t key); #define FNV_OFFSET_BASIS (hash_t)14695981039346656037LU hash_t shash(strv_t s) { hash_t h = FNV_OFFSET_BASIS; - for (size_t i = 0; i < s.n; i++) h = (h ^ s.s[i]) * FNV_64_PRIME; + for (size_t i = 0; i < s.n; i++) h = (h ^ (s.s[i] & 255)) * FNV_64_PRIME; return h; } diff --git a/stdwrm.h b/stdwrm.h index 1ee7281..46992c3 100644 --- a/stdwrm.h +++ b/stdwrm.h @@ -2,8 +2,10 @@ #define STDWRM_H #ifdef STDWRM_IMPL -#define STDWRM_IMPL_SHASH -#define STDWRM_IMPL_STR +#define SHASH_IMPL +#define IHASH_IMPL +#define ZONE_IMPL +#define STR_IMPL #endif #endif diff --git a/str.h b/str.h index 47ff676..9848983 100644 --- a/str.h +++ b/str.h @@ -3,7 +3,6 @@ #include <string.h> -#include "stdwrm.h" #include "dynarr.h" typedef DYNARR(char) string; @@ -14,14 +13,20 @@ typedef struct { } strv_t; #define strv(s) (strv_t) { s, strlen(s) } +#define strvs(s) (strv_t) { s, slen(s) } string snew(void); size_t slen(const string); void scats(string *, strv_t); void scatc(string *, char); void sfree(string); +void sreplace(string *str, size_t i, size_t n, strv_t with); +string sfmt(const char *fmt, ...); +string sdup(const char *); -#ifdef STDWRM_IMPL_STR +#ifdef STR_IMPL + +#include <stdarg.h> string snew(void) { string s; @@ -54,5 +59,37 @@ void sfree(string s) { DA_FREE(s); } +string sfmt(const char *fmt, ...) { + va_list count, print; + string s; + FILE *f = fopen("/dev/null", "w/o"); + va_start(print, fmt); + va_copy(count, print); + size_t n = vfprintf(f, fmt, count) + 1; + DA_INIT_SZ(s, n); + vsprintf(s, fmt, print); + va_end(print); + fclose(f); + return s; +} + +string sdup(const char *s) { + string d; + size_t n = strlen(s) + 1; + DA_INIT_SZ(d, n); + memcpy(d, s, n); + return d; +} + +void sreplace(string *str, size_t i, size_t n, strv_t with) { + string s = *str; + size_t new_n = DA_LEN(s) + with.n - n; + DA_FIT(s, new_n); + memmove(&s[i + with.n], &s[i + n], slen(s) - (i + n)); + memcpy(&s[i], with.s, with.n); + s[new_n - 1] = 0; + DA_LEN(s) = new_n; +} + #endif #endif diff --git a/strio.h b/strio.h index 20d0ddf..0395dd7 100644 --- a/strio.h +++ b/strio.h @@ -5,17 +5,24 @@ #include "str.h" +#ifndef STRIO_CHUNK_SIZE +#define STRIO_CHUNK_SIZE 256 +#endif + string read_whole_file(FILE *f); -#ifdef STDWRM_IMPL_STR +#ifdef STR_IMPL + +#include <stdio.h> string read_whole_file(FILE *f) { - char chunk[256]; string s; - DA_INIT(s); + DA_INIT_SZ(s, STRIO_CHUNK_SIZE); while (!feof(f)) { - size_t n = fread(chunk, 1, sizeof chunk, f); - DA_PUSH_MULT(s, chunk, n); + char *buf = &s[DA_LEN(s)]; + size_t n = fread(buf, 1, STRIO_CHUNK_SIZE, f); + DA_FIT(s, DA_LEN(s) + n); + DA_LEN(s) += n; } DA_PUSH(s, 0); return s; diff --git a/typ.h b/typ.h new file mode 100644 index 0000000..02174be --- /dev/null +++ b/typ.h @@ -0,0 +1,33 @@ +#ifndef TYP_H +#define TYP_H + +#include <stdint.h> +#include <stddef.h> + +typedef uint8_t u8; +typedef uint16_t u16; +typedef uint32_t u32; +typedef uint64_t u64; + +typedef int8_t i8; +typedef int16_t i16; +typedef int32_t i32; +typedef int64_t i64; + +typedef float f32; +typedef double f64; + +typedef size_t usize; +typedef ptrdiff_t isize; + +typedef intptr_t iptr; +typedef uintptr_t uptr; + +typedef u8 uchar8; +typedef u16 uchar16; +typedef u32 uchar32; +typedef i8 ichar8; +typedef i16 ichar16; +typedef i32 ichar32; + +#endif diff --git a/zone.h b/zone.h new file mode 100644 index 0000000..d10ef6e --- /dev/null +++ b/zone.h @@ -0,0 +1,291 @@ +#ifndef ZONE_H +#define ZONE_H + +#include <stdint.h> +#include <stddef.h> + +#define ZONE_USE_MALLOC 0 +#define ZONE_USE_MMAP 1 +#define ZONE_USE_WASM_BULKMEM 2 + +#ifndef ZONE_BACKEND + #ifdef __unix__ + #define ZONE_BACKEND ZONE_USE_MMAP + #else + #define ZONE_BACKEND ZONE_USE_MALLOC + #endif +#endif + +#if !defined(ZONE_NOSTDLIB) && (ZONE_BACKEND != ZONE_USE_MMAP && ZONE_BACKEND != ZONE_USE_MALLOC) + #define ZONE_NOSTDLIB +#endif + +typedef struct ZoneFrame ZoneFrame; +struct ZoneFrame { + ZoneFrame *prev, *next; + uint8_t *beg, *end; + uint8_t data[]; +}; + +typedef struct ZoneState ZoneState; + +struct ZoneState { + ZoneFrame *zf; + ZoneState *last; + uint8_t *beg; +}; + +typedef struct { + ZoneFrame *cur, *tail; + ZoneState *last; +} Zone; + +void zn_free(Zone *z); +void zn_reset(Zone *z); + +void zn_begin(Zone *z); +void zn_end(Zone *z); +void zn_save(Zone *z, ZoneState *m); +void zn_load(Zone *z, ZoneState *m); + +void *zn_alloc(Zone *z, ptrdiff_t n); +void *zn_alloc_align(Zone *z, ptrdiff_t n, size_t align); +void *zn_realloc(Zone *z, void *ptr, ptrdiff_t oldsz, ptrdiff_t newsz); +void *zn_realloc_align(Zone *z, void *ptr, ptrdiff_t oldsz, ptrdiff_t newsz, size_t align); + +char *zn_strdup(Zone *z, const char *s); +void *zn_zeroed(void *, size_t); + +#define zn_new(z, t) (t*)zn_zeroed(zn_alloc_align(z, sizeof(t), _Alignof(t)), sizeof(t)) + +#ifdef ZONE_IMPL + +#ifndef ZONE_PAGE_MULT +#define ZONE_PAGE_MULT 2 +#endif + +#define UPTR_ALIGN(x, align) ((x)+((-x)&((align)-1))) +#define PTR_ALIGN(ptr, align) (typeof(ptr)) (((uintptr_t)ptr + (align - 1)) & -align) + +#if ZONE_BACKEND == ZONE_USE_MMAP || ZONE_BACKEND == ZONE_USE_MALLOC + #include <stdio.h> + #include <stdlib.h> + [[noreturn]] void zn_abort(const char *msg) { + fprintf(stderr, "%s\n", msg); + abort(); + } +#elif ZONE_BACKEND == ZONE_USE_WASM_BULKMEM + __attribute((import_name("alert"))) void js_alert(const char *msg); + __attribute((import_name("abort"))) [[noreturn]] void js_abort(void); + [[noreturn]] void zn_abort(const char *msg) { + js_alert(msg); + js_abort(); + } +#else + #error "zn_abort not implemented for the current platform -- using __builtin_trap() instead" + [[noreturn]] void zn_abort(cont char *msg) { + (void)msg; + __builtin_trap(); + } +#endif + +#define ZONE_MEMSET __builtin_memset +#define ZONE_MEMCPY __builtin_memcpy + +#if ZONE_BACKEND == ZONE_USE_MMAP + + #include <sys/mman.h> + #include <unistd.h> + + #define ZONE_PAGE_SIZE (ZONE_PAGE_MULT * sysconf(_SC_PAGE_SIZE)) + #define ZONE_PAGE_FAIL MAP_FAILED + + static void *zn_pg_alloc(size_t n) { + return mmap(NULL, n * ZONE_PAGE_SIZE, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); + } + static void zn_pg_free(void *p, size_t n) { + munmap(p, n); + } + +#elif ZONE_BACKEND == ZONE_USE_MALLOC + + #define ZONE_PAGE_SIZE (ZONE_PAGE_MULT * 4 * 1024) + #define ZONE_PAGE_FAIL NULL + + static void *zn_pg_alloc(size_t n) { + return malloc(n * ZONE_PAGE_SIZE); + } + static void zn_pg_free(void *p, size_t n) { + free(p); + } + +#elif ZONE_BACKEND == ZONE_USE_WASM_BULKMEM + + #define ZONE_PAGE_SIZE 65536 + #define ZONE_PAGE_FAIL (void*)(uintptr_t)-1 + extern uint8_t __heap_base; + static void *zn_pg_free_adr = 0; + static void *zn_pg_alloc(size_t n) { + if (zn_pg_free_adr) { + void *p = zn_pg_free_adr; + zn_pg_free_adr = *(void **)zn_pg_free_adr; + return p; + } + void *p = &__heap_base + __builtin_wasm_memory_size(0); + __builtin_wasm_memory_grow(0, 1); + return p; + } + static void zn_pg_free(void *p, size_t n) { + uintptr_t adr = ((uintptr_t)p & ~0xFFFF); + n = (n + 0xFFFF) >> 16; + while (n--) { + void *pg = (void *)(adr + (n << 16)); + *(void **)pg = zn_pg_free_adr; + zn_pg_free_adr = pg; + } + } + +#else + + #error "unknown or unsupported zone backend" + +#endif + +static inline size_t zn_pg_fit(size_t cap) { + return cap + (-cap & (ZONE_PAGE_SIZE - 1)); +} + +static ZoneFrame *zn_zf_new(size_t capacity) { + ZoneFrame *zf = zn_pg_alloc(capacity / ZONE_PAGE_SIZE); + if (zf == ZONE_PAGE_FAIL) zn_abort("failed to allocate zone frame\n"); + zf->prev = NULL; + zf->next = NULL; + zf->beg = zf->data; + zf->end = (uint8_t*)zf + capacity; + return zf; +} + +static void zn_zf_free(ZoneFrame *z) { + zn_pg_free(z, (uintptr_t)z->end - (uintptr_t)z->beg); +} + +void *zn_alloc_align(Zone *z, ptrdiff_t n, size_t align) { + ZoneFrame *zf = z->cur; + uint8_t *aligned; + for (;;) { + if (!zf) { + zf = zn_zf_new(zn_pg_fit(n + sizeof(ZoneFrame) + align - 1)); + zf->prev = z->tail; + if (z->tail) z->tail->next = zf; + z->tail = zf; + z->cur = zf; + } + aligned = PTR_ALIGN(zf->beg, align); + if (aligned + n < zf->end) break; + zf = zf->next; + } + zf->beg = aligned + n; + return aligned; +} + +void *zn_realloc_align(Zone *z, void *ptr, ptrdiff_t oldsz, ptrdiff_t newsz, size_t align) { + if (!ptr || !oldsz) return zn_alloc_align(z, newsz, align); + if (z->cur && ptr == z->cur->beg - oldsz && z->cur->beg - oldsz + newsz < z->cur->end) { + z->cur->beg -= oldsz; + z->cur->beg += newsz; + return ptr; + } else { + void *p = zn_alloc_align(z, newsz, align); + ZONE_MEMCPY(p, ptr, oldsz); + return p; + } +} + +static inline size_t zn_align_for(size_t n) { + size_t a = 1; + while (n > a) a <<= 1; + return a; +} + +void *zn_alloc(Zone *z, ptrdiff_t n) { + return zn_alloc_align(z, n, zn_align_for(n)); +} + +void *zn_realloc(Zone *z, void *ptr, ptrdiff_t oldsz, ptrdiff_t newsz) { + return zn_realloc_align(z, ptr, oldsz, newsz, zn_align_for(newsz)); +} + +void *zn_calloc(Zone *z, size_t n, size_t size) { + void *p = zn_alloc_align(z, n * size, zn_align_for(size)); + ZONE_MEMSET(p, 0, n * size); + return p; +} + +void zn_free(Zone *z) { + ZoneFrame *a = z->tail, *b; + while (a) { + b = a->prev; + zn_zf_free(a); + a = b; + } +} + +void zn_reset(Zone *z) { + ZoneFrame *zf = z->tail; + while (zf) { + zf->beg = zf->data; + if (!zf->prev) break; + zf = zf->prev; + } + if (zf) z->cur = zf; +} + +void zn_save(Zone *z, ZoneState *m) { + m->zf = z->cur; + m->beg = z->cur ? z->cur->beg : 0; + m->last = z->last; +} + +void zn_load(Zone *z, ZoneState *m) { + if (m->zf) { + while (z->cur != m->zf) { + z->cur->beg = z->cur->data; + z->cur = z->cur->prev; + } + m->zf->beg = m->beg; + } else { + zn_reset(z); + } + z->last = m->last; +} + +/* utils */ + +#ifndef ZONE_NOSTDLIB +char *zn_strdup(Zone *z, const char *s) { + size_t n = strlen(s) + 1; + char *d = zn_alloc_align(z, n, 1); + ZONE_MEMCPY(d, s, n); + return d; +} +#endif + +void *zn_zeroed(void *ptr, size_t n) { + ZONE_MEMSET(ptr, 0, n); + return ptr; +} + +void zn_begin(Zone *z) { + ZoneState m = { 0 }; + zn_save(z, &m); + ZoneState *p = zn_new(z, ZoneState); + *p = m; + z->last = p; +} + +void zn_end(Zone *z) { + zn_load(z, z->last); +} + +#endif +#endif |