From d874d01e8e9a30f0073a6e559cbae07244dec7bf Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Thu, 3 Oct 2024 00:36:26 +0200 Subject: Huge library overhaul --- README | 2 +- gen/prop/cm.c | 23 +++--- include/_alloc_fn.h | 7 -- include/_allocator.h | 22 ++++++ include/alloc.h | 125 +++++++++++++++++++------------ include/array.h | 63 ++++++++++++++++ include/dynarr.h | 81 -------------------- include/unicode/string.h | 51 ++++++------- lib/alloc/alloc_arena.c | 22 ------ lib/alloc/alloc_heap.c | 31 -------- lib/alloc/arena_alloc.c | 155 ++++++++++++++++++++++++++------------- lib/alloc/arena_free.c | 20 ----- lib/alloc/arena_realloc.c | 62 ---------------- lib/alloc/arena_zero.c | 15 ---- lib/alloc/bufalloc.c | 10 --- lib/alloc/bufalloc_noterm.c | 16 ---- lib/alloc/heap_alloc.c | 76 +++++++++++++++++++ lib/alloc/static_scratch_alloc.c | 44 +++++++++++ lib/array/array_free.c | 12 +++ lib/array/array_new.c | 29 ++++++++ lib/array/array_resz.c | 28 +++++++ lib/unicode/string/u8casefold.c | 9 +-- lib/unicode/string/u8lower.c | 9 +-- lib/unicode/string/u8norm.c | 41 ++++++----- lib/unicode/string/u8title.c | 9 +-- lib/unicode/string/u8upper.c | 9 +-- test/_brk-test.h | 41 +++++------ test/_case-test.h | 21 +++--- test/_norm-test.h | 31 +++----- test/array-test.c | 82 +++++++++++++++++++++ test/wbrk-human-test.c | 22 +++--- 31 files changed, 669 insertions(+), 499 deletions(-) delete mode 100644 include/_alloc_fn.h create mode 100644 include/_allocator.h create mode 100644 include/array.h delete mode 100644 include/dynarr.h delete mode 100644 lib/alloc/alloc_arena.c delete mode 100644 lib/alloc/alloc_heap.c delete mode 100644 lib/alloc/arena_free.c delete mode 100644 lib/alloc/arena_realloc.c delete mode 100644 lib/alloc/arena_zero.c delete mode 100644 lib/alloc/bufalloc.c delete mode 100644 lib/alloc/bufalloc_noterm.c create mode 100644 lib/alloc/heap_alloc.c create mode 100644 lib/alloc/static_scratch_alloc.c create mode 100644 lib/array/array_free.c create mode 100644 lib/array/array_new.c create mode 100644 lib/array/array_resz.c create mode 100644 test/array-test.c diff --git a/README b/README index e34b327..c807cb4 100644 --- a/README +++ b/README @@ -11,9 +11,9 @@ library. It is a C23 library with no plans to support older standards. The headers as of now are: • alloc.h — allocators and memory allocation functions + • array.h — dynamic array implementation • bitset.h — bitset implementation • cli.h — CLI-option parsing functions - • dynarr.h — dynamic array implementation • errors.h — err.h-inspired diagnostics functions • macros.h — miscellaneous utility macros (MIN/MAX/lengthof/etc.) • mbio.h — multibyte file I/O diff --git a/gen/prop/cm.c b/gen/prop/cm.c index 5188ccd..4c408f0 100755 --- a/gen/prop/cm.c +++ b/gen/prop/cm.c @@ -15,7 +15,7 @@ exit 0 #include #include -#include +#include #include #include #include @@ -38,7 +38,8 @@ static uint64_t hash(uint64_t); int main(void) { - dynarr(struct mapping) maps = {.alloc = alloc_heap}; + allocator_t mem = init_heap_allocator(nullptr); + struct mapping *maps = array_new(mem, typeof(*maps), 1024); for (rune ch = 0; ch <= RUNE_MAX; ch++) { if (uprop_get_dt(ch) != DT_CAN || uprop_is_comp_ex(ch)) @@ -57,21 +58,21 @@ main(void) m += rtoucs(buf, sizeof(buf), ch); assert(n >= m); - DAPUSH(&maps, ((struct mapping){ + array_push(&maps, (struct mapping){ .k = (uint64_t)rv.p[0] << 32 | rv.p[1], .v = ch, - })); + }); } struct ht t = {}; - size_t sz = (size_t)1 << (SIZE_WIDTH - stdc_leading_zeros(maps.len) + N); + size_t sz = (size_t)1 << (SIZE_WIDTH - stdc_leading_zeros(array_len(maps)) + N); int e = stdc_trailing_zeros(sz); t.ht = bufalloc(nullptr, sizeof(*t.ht), sz); memset(t.ht, 0, sizeof(*t.ht) * sz); assert(sz == ((size_t)1 << e)); /* Build up hashtable */ - da_foreach (maps, m) { + array_foreach (maps, m) { uint64_t h = hash(m->k); uint32_t i = h; for (;;) { @@ -112,9 +113,9 @@ main(void) "hash(uint64_t x)\n" "{\n" "\tx ^= x >> 30;\n" - "\tx *= 0xbf58476d1ce4e5b9U;\n" + "\tx *= 0xBF58476D1CE4E5B9u;\n" "\tx ^= x >> 27;\n" - "\tx *= 0x94d049bb133111ebU;\n" + "\tx *= 0x94D049BB133111EBu;\n" "\tx ^= x >> 31;\n" "\treturn x;\n" "}\n"); @@ -143,7 +144,7 @@ main(void) "}"); free(t.ht); - free(maps.buf); + array_free(maps); } uint32_t @@ -158,9 +159,9 @@ uint64_t hash(uint64_t x) { x ^= x >> 30; - x *= 0xbf58476d1ce4e5b9U; + x *= 0xBF58476D1CE4E5B9u; x ^= x >> 27; - x *= 0x94d049bb133111ebU; + x *= 0x94D049BB133111EBu; x ^= x >> 31; return x; } diff --git a/include/_alloc_fn.h b/include/_alloc_fn.h deleted file mode 100644 index aae4bd0..0000000 --- a/include/_alloc_fn.h +++ /dev/null @@ -1,7 +0,0 @@ -#ifndef MLIB__ALLOC_FN_H -#define MLIB__ALLOC_FN_H - -typedef void *(*alloc_fn)(void *ctx, void *ptr, size_t old, size_t new, - size_t elemsz, size_t align); - -#endif /* !MLIB__ALLOC_FN_H */ diff --git a/include/_allocator.h b/include/_allocator.h new file mode 100644 index 0000000..3bd78b2 --- /dev/null +++ b/include/_allocator.h @@ -0,0 +1,22 @@ +#ifndef MLIB__ALLOCATOR_H +#define MLIB__ALLOCATOR_H + +#include +#include + +typedef enum { + ALLOC_NEW, + ALLOC_RESIZE, + ALLOC_FREE, + ALLOC_FREEALL, +} alloc_mode_t; + +typedef struct allocator { + void *(*alloc)(struct allocator mem, alloc_mode_t mode, void *ptr, + ptrdiff_t oldnmemb, ptrdiff_t newnmemb, ptrdiff_t elemsz, + ptrdiff_t align); + jmp_buf *err; + void *ctx; +} allocator_t; + +#endif /* !MLIB__ALLOCATOR_H */ diff --git a/include/alloc.h b/include/alloc.h index 8004cd0..2786757 100644 --- a/include/alloc.h +++ b/include/alloc.h @@ -1,60 +1,95 @@ #ifndef MLIB_ALLOC_H #define MLIB_ALLOC_H -#include -#include - +#include "_allocator.h" #include "_attrs.h" -#ifndef MLIB_ARENA_BLKSIZE -# define MLIB_ARENA_BLKSIZE (8 * 1024) -#endif +typedef enum { + ALLOC_OOM, +} alloc_err_t; + +typedef struct arena_blk arena_blk_t; -struct _region { - size_t len, cap; - void *data, *last; - struct _region *next; -}; +typedef struct { + ptrdiff_t blksz; + struct arena_blk *_head; +} arena_ctx_t; typedef struct { - struct _region *_head; - size_t _init; -} arena; + void *buf; + ptrdiff_t len; +} st_buf_t; -/* Heap allocation functions */ -[[nodiscard, gnu::returns_nonnull]] void *bufalloc(void *, size_t, size_t); -[[nodiscard]] void *bufalloc_noterm(void *, size_t, size_t); +#define new(mem, T, n) \ + ((typeof(T) *)((mem).alloc((mem), \ + ALLOC_NEW, \ + nullptr, \ + 0, \ + (n), \ + sizeof(T), \ + alignof(T)))) +#define resz(mem, p, o, n) \ + ((typeof(p))((mem).alloc((mem), \ + ALLOC_RESIZE, \ + (p), \ + (o), \ + (n), \ + sizeof(*(p)), \ + alignof(typeof(*(p)))))) +#define delete(mem, p, sz) \ + (mem).alloc((mem), \ + ALLOC_FREE, \ + (p), \ + (sz), \ + 0, \ + sizeof(*(p)), \ + alignof(typeof(*p))) +#define deleteall(mem) \ + ((mem).alloc((mem), \ + ALLOC_FREEALL, \ + nullptr, \ + 0, \ + 0, \ + 0, \ + 0)) -[[_mlib_pure, _mlib_inline]] -static inline arena -mkarena(size_t n) +void *arena_alloc(allocator_t mem, alloc_mode_t mode, void *ptr, + ptrdiff_t oldnmemb, ptrdiff_t newnmemb, ptrdiff_t elemsz, + ptrdiff_t align); +void *heap_alloc(allocator_t mem, alloc_mode_t mode, void *ptr, + ptrdiff_t oldnmemb, ptrdiff_t newnmemb, ptrdiff_t elemsz, + ptrdiff_t align); +void *static_scratch_alloc(allocator_t mem, alloc_mode_t mode, void *ptr, + ptrdiff_t oldnmemb, ptrdiff_t newnmemb, ptrdiff_t elemsz, + ptrdiff_t align); + +[[_mlib_inline]] static inline allocator_t +init_arena_allocator(arena_ctx_t *ctx, jmp_buf *jmp) { - return (arena){._init = n ? n : MLIB_ARENA_BLKSIZE}; + return (allocator_t){ + .alloc = arena_alloc, + .err = jmp, + .ctx = ctx, + }; } -/* Arena allocation functions */ -[[nodiscard, gnu::malloc, gnu::alloc_size(2, 3), gnu::alloc_align(4)]] -void *arena_alloc(arena *, size_t, size_t, size_t); -[[nodiscard]] -void *arena_realloc(arena *, void *, size_t, size_t, size_t, size_t); -void arena_zero(arena *); -void arena_free(arena *); - -/* Arena allocation macro wrappers */ -#define arena_new(a, T, n) ((T *)arena_alloc((a), (n), sizeof(T), alignof(T))) -#define arena_resz(a, T, p, n) \ - ((T *)arena_realloc((a), (p), (n), sizeof(T), alignof(T))) - -/* Memory allocator callbacks for memory-allocating functions */ -struct arena_ctx { - arena *a; - jmp_buf *jmp; -}; -struct heap_ctx { - jmp_buf *jmp; -}; - -[[nodiscard]] void *alloc_arena(void *, void *, size_t, size_t, size_t, size_t); -[[nodiscard]] void *alloc_heap(void *, void *, size_t, size_t, size_t, size_t); +[[_mlib_inline]] static inline allocator_t +init_heap_allocator(jmp_buf *jmp) +{ + return (allocator_t){ + .alloc = heap_alloc, + .err = jmp, + }; +} + +[[_mlib_inline]] static inline allocator_t +init_static_scratch_allocator(st_buf_t *ctx, jmp_buf *jmp) +{ + return (allocator_t){ + .alloc = static_scratch_alloc, + .err = jmp, + .ctx = ctx, + }; +} #endif /* !MLIB_ALLOC_H */ diff --git a/include/array.h b/include/array.h new file mode 100644 index 0000000..de45a65 --- /dev/null +++ b/include/array.h @@ -0,0 +1,63 @@ +#ifndef MLIB_ARRAY_H +#define MLIB_ARRAY_H + +#include +#include + +#include "_allocator.h" +#include "_attrs.h" + +typedef struct { + ptrdiff_t len, cap; + allocator_t mem; +} _mlib_arr_hdr_t; + +[[_mlib_inline]] +static inline _mlib_arr_hdr_t * +_mlib_array_hdr(void *p, ptrdiff_t align) +{ + ptrdiff_t pad = -sizeof(_mlib_arr_hdr_t) & (align - 1); + return (_mlib_arr_hdr_t *)((char *)p - pad - sizeof(_mlib_arr_hdr_t)); +} + +#define array_hdr(p) (_mlib_array_hdr(p, alignof(typeof(*(p))))) +#define array_len(p) (_mlib_array_hdr(p, alignof(typeof(*(p))))->len) +#define array_cap(p) (_mlib_array_hdr(p, alignof(typeof(*(p))))->cap) + +#define array_new(mem, T, n) \ + ((T *)array_new((mem), (n), sizeof(T), alignof(T))) +#define array_resz(p, cap) \ + ((typeof(p))array_resz((p), (cap), sizeof(*(p)), alignof(typeof(*(p))))) +#define array_free(p) \ + array_free((p), sizeof(*(p)), alignof(typeof(*(p)))) + +#define array_push(p, x) \ + do { \ + _mlib_arr_hdr_t *hdr = _mlib_array_hdr(*(p), alignof(typeof(**(p)))); \ + if (hdr->len == hdr->cap) { \ + *(p) = array_resz(*(p), hdr->len * 2); \ + hdr = _mlib_array_hdr(*(p), alignof(typeof(**(p)))); \ + } \ + (*(p))[hdr->len++] = (x); \ + } while (false) + +/* TODO: Make the resizing not bad */ +#define array_extend(p, xs, n) \ + do { \ + _mlib_arr_hdr_t *hdr = _mlib_array_hdr((p), alignof(typeof(*(p)))); \ + if (hdr->len + (n) <= hdr->cap) { \ + (p) = array_resz((p), hdr->len * 2 + (n)); \ + hdr = _mlib_array_hdr((p), alignof(typeof(*(p)))); \ + } \ + memcpy(&(p)[hdr->len], (xs), (n) * sizeof(*xs)); \ + hdr->len += (n); \ + } while (false) + +#define array_foreach(p, i) for (typeof(p) i = (p); i < (p) + array_len(p); i++) + +void *(array_new)(allocator_t mem, ptrdiff_t nmemb, ptrdiff_t elemsz, + ptrdiff_t align); +void *(array_resz)(void *ptr, ptrdiff_t ncap, ptrdiff_t elemsz, ptrdiff_t align); +void (array_free)(void *ptr, ptrdiff_t elemsz, ptrdiff_t align); + +#endif /* !MLIB_ARRAY_H */ diff --git a/include/dynarr.h b/include/dynarr.h deleted file mode 100644 index 75bdcc8..0000000 --- a/include/dynarr.h +++ /dev/null @@ -1,81 +0,0 @@ -#ifndef MLIB_DYNARR_H -#define MLIB_DYNARR_H - -#include -#include - -#include "_alloc_fn.h" -#include "alloc.h" - -/* This is required because alignof() only portably works with types and not - expressions… */ -/* clang-format off */ -#ifdef __GNUC__ -# define _mlib_da_alignof(expr) __extension__ alignof(expr) -#else -# include -# define _mlib_da_alignof(expr) \ - ((size_t) &((struct {char x; typeof(expr) y;} *)0)->y) -#endif -/* clang-format on */ - -#define dafields(T) \ - T *buf; \ - size_t len, cap; \ - alloc_fn alloc; \ - void *ctx - -#define dynarr(T) \ - struct { \ - dafields(T); \ - } - -#define DAPUSH(da, x) \ - do { \ - if (++(da)->len > (da)->cap) { \ - size_t ncap = stdc_bit_ceil((da)->len); \ - (da)->buf = (da)->alloc((da)->ctx, (da)->buf, (da)->cap, ncap, \ - sizeof(*(da)->buf), \ - _mlib_da_alignof(*(da)->buf)); \ - (da)->cap = ncap; \ - } \ - (da)->buf[(da)->len - 1] = (x); \ - } while (false) - -#define DAEXTEND(da, xs, n) \ - do { \ - if (((da)->len += (n)) > (da)->cap) { \ - size_t ncap = stdc_bit_ceil((da)->len); \ - (da)->buf = (da)->alloc((da)->ctx, (da)->buf, (da)->cap, ncap, \ - sizeof(*(da)->buf), \ - _mlib_da_alignof(*(da)->buf)); \ - (da)->cap = ncap; \ - } \ - memcpy((da)->buf + (da)->len - (n), (xs), (n) * sizeof(*(da)->buf)); \ - } while (false) - -#define DAGROW(da, n) \ - do { \ - if ((n) > (da)->cap) { \ - (da)->buf = (da)->alloc((da)->ctx, (da)->buf, (da)->cap, (n), \ - sizeof(*(da)->buf), \ - _mlib_da_alignof(*(da)->buf)); \ - (da)->cap = (n); \ - } \ - } while (false) - -#define DAPOP(da) ((da)->buf[--(da)->len]) - -#define DAREMOVE(da, i) DA_REMOVE_RANGE((da), (i), (i) + 1) - -#define DA_REMOVE_RANGE(da, i, j) \ - do { \ - memmove((da)->buf + (i), (da)->buf + (j), \ - ((da)->len - (j)) * sizeof(*(da)->buf)); \ - (da)->len -= j - i; \ - } while (false) - -#define da_foreach(da, p) \ - for (auto p = (da).buf; (size_t)(p - (da).buf) < (da).len; p++) - -#endif /* !MLIB_DYNARR_H */ diff --git a/include/unicode/string.h b/include/unicode/string.h index 7d62171..077a45a 100644 --- a/include/unicode/string.h +++ b/include/unicode/string.h @@ -3,22 +3,22 @@ #include -#include "_alloc_fn.h" +#include "_allocator.h" #include "_charN_t.h" #include "_uNview.h" /* clang-format off */ -enum [[clang::flag_enum]] caseflags { +typedef enum [[clang::flag_enum]] { CF_LANG_AZ = 1 << 0, /* Azeri; alias for CF_LANG_TR */ CF_LANG_TR = 1 << 0, /* Turkish; alias for CF_LANG_AZ */ CF_LANG_LT = 1 << 1, /* Lithuanian */ CF_LANG_NL = 1 << 2, /* Dutch */ CF_SS = 1 << 3, /* Use ‘ẞ’ as the uppercase of ‘ß’; alias for CF_ẞ */ CF_ẞ = 1 << 3, /* Use ‘ẞ’ as the uppercase of ‘ß’; alias for CF_SS */ -}; +} caseflags_t; -enum normform { +typedef enum { /* If bit 0 is set, then composition is performed after decomposition. If bit-1 is set then compatibility (de)composition is used as opposed to canonical (de)composition. */ @@ -26,7 +26,7 @@ enum normform { NF_NFC = 0b01, NF_NFKD = 0b10, NF_NFKC = 0b11, -}; +} normform_t; /* clang-format on */ @@ -37,16 +37,11 @@ enum normform { size_t u8gnext(u8view_t *, u8view_t *); size_t u8wnext(u8view_t *, u8view_t *); size_t u8wnext_human(u8view_t *, u8view_t *); -[[nodiscard]] char8_t *u8casefold(size_t *, u8view_t, enum caseflags, - alloc_fn, void *); -[[nodiscard]] char8_t *u8lower(size_t *, u8view_t, enum caseflags, - alloc_fn, void *); -[[nodiscard]] char8_t *u8title(size_t *, u8view_t, enum caseflags, - alloc_fn, void *); -[[nodiscard]] char8_t *u8upper(size_t *, u8view_t, enum caseflags, - alloc_fn, void *); -[[nodiscard]] char8_t *u8norm(size_t *, u8view_t, alloc_fn, void *, - enum normform); +[[nodiscard]] char8_t *u8casefold(size_t *, u8view_t, caseflags_t, allocator_t); +[[nodiscard]] char8_t *u8lower(size_t *, u8view_t, caseflags_t, allocator_t); +[[nodiscard]] char8_t *u8title(size_t *, u8view_t, caseflags_t, allocator_t); +[[nodiscard]] char8_t *u8upper(size_t *, u8view_t, caseflags_t, allocator_t); +[[nodiscard]] char8_t *u8norm(size_t *, u8view_t, allocator_t, normform_t); /* Encoding-generic macros */ #define ucswdth(sv, ts) _Generic((sv), u8view_t: u8wdth)((sv), (ts)) @@ -55,22 +50,18 @@ size_t u8wnext_human(u8view_t *, u8view_t *); #define ucswcnt_human(sv) _Generic((sv), u8view_t: u8wcnt_human)((sv)) #define ucsgnext(g, sv) _Generic((sv), u8view_t *: u8gnext)((g), (sv)) #define ucswnext(g, sv) _Generic((sv), u8view_t *: u8wnext)((g), (sv)) -#define ucswnext_human(g, sv) \ +#define ucswnext_human(g, sv) \ _Generic((sv), u8view_t *: u8wnext_human)((g), (sv)) -#define ucscasefold(dstn, sv, flags, alloc, ctx) \ - _Generic((sv), u8view_t: u8casefold)((dstn), (sv), (flags), (alloc), \ - (ctx)) -#define ucslower(dstn, sv, flags, alloc, ctx) \ - _Generic((sv), u8view_t: u8lower)((dstn), (sv), (flags), (alloc), \ - (ctx)) -#define ucstitle(dstn, sv, flags, alloc, ctx) \ - _Generic((sv), u8view_t: u8title)((dstn), (sv), (flags), (alloc), \ - (ctx)) -#define ucsupper(dstn, sv, flags, alloc, ctx) \ - _Generic((sv), u8view_t: u8upper)((dstn), (sv), (flags), (alloc), \ - (ctx)) -#define ucsnorm(dstn, sv, alloc, ctx, nf) \ - _Generic((sv), u8view_t: u8norm)((dstn), (sv), (alloc), (ctx), (nf)) +#define ucscasefold(dstn, sv, flags, mem) \ + _Generic((sv), u8view_t: u8casefold)((dstn), (sv), (flags), (mem)) +#define ucslower(dstn, sv, flags, mem) \ + _Generic((sv), u8view_t: u8lower)((dstn), (sv), (flags), (mem)) +#define ucstitle(dstn, sv, flags, mem) \ + _Generic((sv), u8view_t: u8title)((dstn), (sv), (flags), (mem)) +#define ucsupper(dstn, sv, flags, mem) \ + _Generic((sv), u8view_t: u8upper)((dstn), (sv), (flags), (mem)) +#define ucsnorm(dstn, sv, mem, nf) \ + _Generic((sv), u8view_t: u8norm)((dstn), (sv), (mem), (nf)) constexpr double U8CASEFOLD_SCALE = 3; constexpr double U8LOWER_SCALE = 1.5; diff --git a/lib/alloc/alloc_arena.c b/lib/alloc/alloc_arena.c deleted file mode 100644 index 8d2aa11..0000000 --- a/lib/alloc/alloc_arena.c +++ /dev/null @@ -1,22 +0,0 @@ -#include - -#include "alloc.h" -#include "errors.h" -#include "macros.h" - -void * -alloc_arena(void *raw_ctx, void *ptr, size_t old, size_t new, size_t elemsz, - size_t align) -{ - struct arena_ctx *ctx = raw_ctx; - ASSUME(ctx != nullptr); - ASSUME(ctx->a != nullptr); - - void *p = arena_realloc(ctx->a, ptr, old, new, elemsz, align); - if (new == 0 || p != nullptr) - return p; - - if (ctx->jmp != nullptr) - longjmp(*ctx->jmp, 1); - err("arena_realloc:"); -} diff --git a/lib/alloc/alloc_heap.c b/lib/alloc/alloc_heap.c deleted file mode 100644 index fccfcfc..0000000 --- a/lib/alloc/alloc_heap.c +++ /dev/null @@ -1,31 +0,0 @@ -#include -#include -#include -#include -#include - -#include "alloc.h" -#include "errors.h" - -void * -alloc_heap(void *raw_ctx, void *ptr, size_t, size_t new, size_t elemsz, size_t) -{ - if (new == 0) { - free(ptr); - return nullptr; - } - - if (!ckd_mul(&new, new, elemsz)) { - void *p = realloc(ptr, new); - if (p != nullptr) - return p; - } else - errno = EOVERFLOW; - - struct heap_ctx *ctx = raw_ctx; - if (ctx == nullptr || ctx->jmp == nullptr) - err("realloc:"); - - longjmp(*ctx->jmp, 1); - unreachable(); -} diff --git a/lib/alloc/arena_alloc.c b/lib/alloc/arena_alloc.c index 65123d4..d953423 100644 --- a/lib/alloc/arena_alloc.c +++ b/lib/alloc/arena_alloc.c @@ -1,80 +1,137 @@ +/* TODO: Support malloc() backend for systems without MAP_ANONYMOUS */ + #include #include +#include #include -#include +#include +#include +#include +#include #include "_attrs.h" +#include "_charN_t.h" #include "alloc.h" +#include "error.h" #include "macros.h" -#define IS_POW_2(n) ((n) != 0 && ((n) & ((n) - 1)) == 0) +#define PAD(len, align) (((len) + (align) - 1) & ~((align) - 1)) -[[_mlib_pure, _mlib_inline]] static size_t pad(size_t, size_t); -static struct _region *mkregion(size_t); +struct arena_blk { + char8_t *head, *tail, *fngr; + struct arena_blk *next; +}; -size_t -pad(size_t len, size_t align) -{ - return (len + align - 1) & ~(align - 1); -} +static void *alloc(allocator_t mem, ptrdiff_t nmemb, ptrdiff_t elemsz, + ptrdiff_t align); +static void freeall(allocator_t mem); +static arena_blk_t *mkblk(ptrdiff_t blksz); +[[noreturn]] static void errjmp(jmp_buf *env); -struct _region * -mkregion(size_t cap) +void * +arena_alloc(allocator_t mem, alloc_mode_t mode, void *ptr, ptrdiff_t oldnmemb, + ptrdiff_t newnmemb, ptrdiff_t elemsz, ptrdiff_t align) { - struct _region *r = malloc(sizeof(struct _region)); - if (r == nullptr) + (void)ptr; + (void)oldnmemb; + switch (mode) { + case ALLOC_NEW: + return alloc(mem, newnmemb, elemsz, align); + case ALLOC_RESIZE: + /* TODO: Make this more efficient */ + void *p = alloc(mem, newnmemb, elemsz, align); + memcpy(p, ptr, MIN(oldnmemb, newnmemb) * elemsz); + return p; + case ALLOC_FREE: + /* TODO: Allow freeing the very last allocation */ return nullptr; - *r = (struct _region){ - .cap = cap, - .data = mmap(nullptr, cap, PROT_READ | PROT_WRITE, - MAP_PRIVATE | MAP_ANONYMOUS, -1, 0), - }; - if (r->data == MAP_FAILED) { - int save = errno; - free(r); - errno = save; + case ALLOC_FREEALL: + freeall(mem); return nullptr; + default: + unreachable(); } - r->last = r->data; - return r; } void * -arena_alloc(arena *a, size_t sz, size_t n, size_t align) +alloc(allocator_t mem, ptrdiff_t nmemb, ptrdiff_t elemsz, ptrdiff_t align) { - ASSUME(a != nullptr); - ASSUME(IS_POW_2(align)); + arena_ctx_t *ctx = mem.ctx; + if (ctx->blksz == 0) { + long blksz = sysconf(_SC_PAGESIZE); + if (blksz == -1) + errjmp(mem.err); + ctx->blksz = blksz; + } - if (ckd_mul(&sz, sz, n)) { + ptrdiff_t bufsz; + if (ckd_mul(&bufsz, nmemb, elemsz)) { errno = EOVERFLOW; - return nullptr; + errjmp(mem.err); } - for (struct _region *r = a->_head; r != nullptr; r = r->next) { - size_t nlen, off = pad(r->len, align); + for (arena_blk_t *blk = ctx->_head; blk != nullptr; blk = blk->next) { + ptrdiff_t nbufsz, off = PAD((uintptr_t)blk->fngr, align); + if (ckd_add(&nbufsz, bufsz, off)) + continue; - /* Technically there are other ways to solve this… but at this point you - might as well just fail */ - if (ckd_add(&nlen, off, sz)) { - errno = EOVERFLOW; - return nullptr; + if (blk->tail - blk->fngr >= nbufsz) { + void *p = blk->fngr + off; + blk->fngr += nbufsz; + return p; } + } - if (nlen <= r->cap) { - void *ret = (char *)r->data + off; - r->len = nlen; - r->last = ret; - return ret; - } + /* No page exists that is large enough for our allocation */ + ptrdiff_t padding = PAD(sizeof(arena_blk_t), align); + + if (ckd_add(&bufsz, bufsz, sizeof(arena_blk_t)) + || ckd_add(&bufsz, bufsz, padding)) + { + errno = EOVERFLOW; + errjmp(mem.err); } + + arena_blk_t *blk = mkblk(MAX(bufsz, ctx->blksz)); + if (blk == nullptr) + errjmp(mem.err); + blk->next = ctx->_head; + blk->fngr = blk->head + bufsz; + ctx->_head = blk; + return blk->head + sizeof(arena_blk_t) + padding; +} - /* No page exists with enough space */ - struct _region *r = mkregion(MAX(sz, a->_init)); - if (r == nullptr) +void +freeall(allocator_t mem) +{ + arena_ctx_t *ctx = mem.ctx; + arena_blk_t *blk = ctx->_head; + while (blk != nullptr) { + arena_blk_t *next = blk->next; + (void)munmap(blk, blk->tail - blk->head); + blk = next; + } + ctx->_head = nullptr; +} + +static arena_blk_t * +mkblk(ptrdiff_t blksz) +{ + arena_blk_t blk; + /* blk.next and blk.fngr get set by the caller */ + blk.head = mmap(nullptr, blksz, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANON, -1, 0); + if (blk.head == MAP_FAILED) return nullptr; - r->next = a->_head; - r->len = sz; - a->_head = r; - return r->data; + blk.tail = blk.head + blksz; + return memcpy(blk.head, &blk, sizeof blk); +} + +void +errjmp(jmp_buf *env) +{ + if (env != nullptr) + longjmp(*env, 1); + err("arena_alloc:"); } diff --git a/lib/alloc/arena_free.c b/lib/alloc/arena_free.c deleted file mode 100644 index dc2b45e..0000000 --- a/lib/alloc/arena_free.c +++ /dev/null @@ -1,20 +0,0 @@ -#include - -#include - -#include "alloc.h" -#include "macros.h" - -void -arena_free(arena *a) -{ - ASSUME(a != nullptr); - - struct _region *cur, *next; - for (cur = a->_head; cur != nullptr; cur = next) { - next = cur->next; - munmap(cur->data, cur->cap); - free(cur); - } - a->_head = nullptr; -} diff --git a/lib/alloc/arena_realloc.c b/lib/alloc/arena_realloc.c deleted file mode 100644 index 6877ae1..0000000 --- a/lib/alloc/arena_realloc.c +++ /dev/null @@ -1,62 +0,0 @@ -#include -#include -#include - -#include "alloc.h" -#include "macros.h" - -void * -arena_realloc(arena *a, void *ptr, size_t old, size_t new, size_t elemsz, - size_t align) -{ - ASSUME(a != nullptr); - - if (ptr == nullptr) - return arena_alloc(a, new, elemsz, align); - - if (old == new) - return ptr; - - struct _region *cur = a->_head; - while (cur != nullptr) { - if (ptr >= cur->data && (char *)ptr < (char *)cur->data + cur->cap) - break; - cur = cur->next; - } - if (cur == nullptr) - cur = a->_head; - - /* cur now points to the region containing ‘ptr’ */ - - /* If we are shrinking the buffer, then we don’t need to move our allocation - and can just return it directly. As a minor optimization if the - allocation we are shrinking is the last allocation in the current region, - we can decrease the region length to make space for more future - allocations. */ - if (old > new) { - if (ptr == cur->last) - cur->len -= (old - new) * elemsz; - return ptr; - } - - ASSUME(old < new); - - /* If we need to grow the given allocation, but it was the last allocation - made in a region, then we first see if we can just eat more trailing free - space in the region to avoid a memcpy(). */ - if (ptr == cur->last) { - size_t need, free = cur->cap - cur->len; - if (ckd_mul(&need, new - old, elemsz)) { - errno = EOVERFLOW; - return nullptr; - } - if (need <= free) { - cur->len += need; - return ptr; - } - } - - /* At this point we just make a new allocation and copy the data over */ - void *dst = arena_alloc(a, new, elemsz, align); - return dst == nullptr ? nullptr : memcpy(dst, ptr, old * elemsz); -} diff --git a/lib/alloc/arena_zero.c b/lib/alloc/arena_zero.c deleted file mode 100644 index 296007e..0000000 --- a/lib/alloc/arena_zero.c +++ /dev/null @@ -1,15 +0,0 @@ -#include "alloc.h" -#include "macros.h" - -void -arena_zero(arena *a) -{ - ASSUME(a != nullptr); - - struct _region *cur = a->_head; - while (cur != nullptr) { - cur->len = 0; - cur->last = cur->data; - cur = cur->next; - } -} diff --git a/lib/alloc/bufalloc.c b/lib/alloc/bufalloc.c deleted file mode 100644 index 264f242..0000000 --- a/lib/alloc/bufalloc.c +++ /dev/null @@ -1,10 +0,0 @@ -#include "alloc.h" -#include "errors.h" - -void * -bufalloc(void *p, size_t n, size_t m) -{ - if ((p = bufalloc_noterm(p, n, m)) == nullptr) - err("%s:", __func__); - return p; -} diff --git a/lib/alloc/bufalloc_noterm.c b/lib/alloc/bufalloc_noterm.c deleted file mode 100644 index e46d2a1..0000000 --- a/lib/alloc/bufalloc_noterm.c +++ /dev/null @@ -1,16 +0,0 @@ -#include -#include -#include - -#include "alloc.h" - -void * -bufalloc_noterm(void *p, size_t n, size_t m) -{ - if (ckd_mul(&n, n, m)) { - errno = EOVERFLOW; - return nullptr; - } - - return realloc(p, n); -} diff --git a/lib/alloc/heap_alloc.c b/lib/alloc/heap_alloc.c new file mode 100644 index 0000000..4779ff6 --- /dev/null +++ b/lib/alloc/heap_alloc.c @@ -0,0 +1,76 @@ +#include +#include +#include +#include +#include + +#include "alloc.h" +#include "errors.h" + +[[noreturn]] static void oom(jmp_buf *env); + +void * +heap_alloc(allocator_t mem, alloc_mode_t mode, void *ptr, ptrdiff_t oldnmemb, + ptrdiff_t newnmemb, ptrdiff_t elemsz, ptrdiff_t align) +{ + void *p; + ptrdiff_t oldsz, newsz; + + switch (mode) { + case ALLOC_NEW: + if (ckd_mul(&newsz, newnmemb, elemsz)) + oom(mem.err); + /* Malloc is guaranteed to return a pointer aligned to an + alignment that is suitable for all fundamental types. For + larger alignments we need to use specialized functionality. */ + if ((size_t)align <= alignof(max_align_t)) { + if ((p = malloc(newsz)) == nullptr) + oom(mem.err); + } else { + if ((p = aligned_alloc(align, newsz)) == nullptr) + oom(mem.err); + } + return p; + case ALLOC_RESIZE: + if (ckd_mul(&newsz, newnmemb, elemsz)) + oom(mem.err); + if (ckd_mul(&oldsz, oldnmemb, elemsz)) + oom(mem.err); + if ((size_t)align <= alignof(max_align_t)) { + if ((p = realloc(ptr, newsz)) == nullptr) + oom(mem.err); + } else { + /* We were allocated using aligned_alloc(). Unfortunately + there is no way to reallocate a buffer aligned via + aligned_alloc() so we need to allocate a new buffer and do + a manual copy… */ + if ((p = aligned_alloc(align, newsz)) == nullptr) + oom(mem.err); + memcpy(p, ptr, oldsz); +#if 0 + /* We would rather use free_aligned_size(), but it isn’t + available yet on most systems. */ + free_aligned_sized(ptr, align, oldsz); +#else + free(ptr); +#endif + } + return p; + case ALLOC_FREE: + free(ptr); + return nullptr; + case ALLOC_FREEALL: + assert(!"Not implemented"); + return nullptr; + default: + unreachable(); + } +} + +void +oom(jmp_buf *env) +{ + if (env != nullptr) + longjmp(*env, 1); + err("heap_alloc:"); +} diff --git a/lib/alloc/static_scratch_alloc.c b/lib/alloc/static_scratch_alloc.c new file mode 100644 index 0000000..2489b98 --- /dev/null +++ b/lib/alloc/static_scratch_alloc.c @@ -0,0 +1,44 @@ +#include +#include +#include +#include + +#include "alloc.h" +#include "errors.h" + +[[noreturn]] static void oom(jmp_buf *env); + +void * +static_scratch_alloc(allocator_t mem, alloc_mode_t mode, void *, + ptrdiff_t, ptrdiff_t newnmemb, ptrdiff_t elemsz, + ptrdiff_t align) +{ + st_buf_t *ctx = mem.ctx; + + switch (mode) { + case ALLOC_NEW: + case ALLOC_RESIZE: + ptrdiff_t pad, avail, total; + if (ckd_mul(&total, newnmemb, elemsz)) + oom(mem.err); + pad = -(uintptr_t)ctx->buf & (align - 1); + avail = ctx->len - pad; + if (avail < 0 || total > avail) + oom(mem.err); + return (char *)ctx->buf + pad; + case ALLOC_FREE: + case ALLOC_FREEALL: + return nullptr; + default: + unreachable(); + } +} + +void +oom(jmp_buf *env) +{ + errno = ENOMEM; + if (env != nullptr) + longjmp(*env, 1); + err("static_scratch_alloc:"); +} diff --git a/lib/array/array_free.c b/lib/array/array_free.c new file mode 100644 index 0000000..0e5560e --- /dev/null +++ b/lib/array/array_free.c @@ -0,0 +1,12 @@ +#include + +#include "array.h" +#include "alloc.h" + +void +(array_free)(void *vptr, ptrdiff_t elemsz, ptrdiff_t align) +{ + ptrdiff_t pad = -sizeof(_mlib_arr_hdr_t) & (align - 1); + _mlib_arr_hdr_t *hdr = _mlib_array_hdr(vptr, align); + delete(hdr->mem, (uint8_t *)hdr, sizeof(*hdr) + pad + hdr->cap*elemsz); +} diff --git a/lib/array/array_new.c b/lib/array/array_new.c new file mode 100644 index 0000000..7339ba5 --- /dev/null +++ b/lib/array/array_new.c @@ -0,0 +1,29 @@ +#include +#include +#include +#include + +#include "array.h" +#include "alloc.h" + +void * +(array_new)(allocator_t mem, ptrdiff_t nmemb, ptrdiff_t elemsz, ptrdiff_t align) +{ + ptrdiff_t total, pad = -sizeof(_mlib_arr_hdr_t) & (align - 1); + + /* Overflow; just call the allocator with the maximum size to force + proper error handling */ + if (ckd_mul(&total, nmemb, elemsz) + || ckd_add(&total, total, pad) + || ckd_add(&total, total, sizeof(_mlib_arr_hdr_t))) + { + mem.alloc(mem, ALLOC_NEW, nullptr, 0, + PTRDIFF_MAX, PTRDIFF_MAX, PTRDIFF_MAX); + unreachable(); + } + + uint8_t *buf = new(mem, uint8_t, total); + _mlib_arr_hdr_t hdr = {0, nmemb, mem}; + memcpy(buf, &hdr, sizeof(hdr)); + return buf + sizeof(_mlib_arr_hdr_t) + pad; +} diff --git a/lib/array/array_resz.c b/lib/array/array_resz.c new file mode 100644 index 0000000..d28a7a0 --- /dev/null +++ b/lib/array/array_resz.c @@ -0,0 +1,28 @@ +#include +#include +#include + +#include "array.h" +#include "alloc.h" + +void * +(array_resz)(void *ptr, ptrdiff_t ncap, ptrdiff_t elemsz, ptrdiff_t align) +{ + ptrdiff_t newsz, pad = -sizeof(_mlib_arr_hdr_t) & (align - 1); + _mlib_arr_hdr_t *hdr = _mlib_array_hdr(ptr, align); + /* Overflow; just call the allocator with the maximum size to force + proper error handling */ + if (ckd_mul(&newsz, ncap, elemsz) + || ckd_add(&newsz, newsz, pad) + || ckd_add(&newsz, newsz, sizeof(_mlib_arr_hdr_t))) + { + hdr->mem.alloc(hdr->mem, ALLOC_NEW, nullptr, 0, + PTRDIFF_MAX, PTRDIFF_MAX, PTRDIFF_MAX); + unreachable(); + } + + ptrdiff_t oldsz = sizeof(_mlib_arr_hdr_t) + pad + hdr->cap*elemsz; + hdr = (_mlib_arr_hdr_t *)resz(hdr->mem, (uint8_t *)hdr, oldsz, newsz); + hdr->cap = ncap; + return (uint8_t *)hdr + sizeof(*hdr) + pad; +} diff --git a/lib/unicode/string/u8casefold.c b/lib/unicode/string/u8casefold.c index e3a3402..fc9ed54 100644 --- a/lib/unicode/string/u8casefold.c +++ b/lib/unicode/string/u8casefold.c @@ -1,3 +1,4 @@ +#include #include #include @@ -7,11 +8,9 @@ #include "unicode/string.h" char8_t * -u8casefold(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, - void *alloc_ctx) +u8casefold(size_t *dstn, u8view_t sv, caseflags_t flags, allocator_t mem) { ASSUME(dstn != nullptr); - ASSUME(alloc != nullptr); size_t bufsz; if (ckd_mul(&bufsz, sv.len, (size_t)U8CASEFOLD_SCALE)) { @@ -19,7 +18,7 @@ u8casefold(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, return nullptr; } - char8_t *dst = alloc(alloc_ctx, nullptr, 0, bufsz, 1, alignof(char8_t)); + char8_t *dst = new(mem, typeof(*dst), bufsz); rune ch; size_t n = 0; @@ -30,5 +29,5 @@ u8casefold(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, } *dstn = n; - return alloc(alloc_ctx, dst, bufsz, n, 1, alignof(char8_t)); + return resz(mem, dst, bufsz, n); } diff --git a/lib/unicode/string/u8lower.c b/lib/unicode/string/u8lower.c index 2b1ec36..e553f98 100644 --- a/lib/unicode/string/u8lower.c +++ b/lib/unicode/string/u8lower.c @@ -2,6 +2,7 @@ #include #include "_attrs.h" +#include "alloc.h" #include "macros.h" #include "mbstring.h" #include "unicode/prop.h" @@ -17,11 +18,9 @@ uprop_ccc_0_or_230(rune ch) } char8_t * -u8lower(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, - void *alloc_ctx) +u8lower(size_t *dstn, u8view_t sv, caseflags_t flags, allocator_t mem) { ASSUME(dstn != nullptr); - ASSUME(alloc != nullptr); struct lcctx ctx = { .az_or_tr = flags & CF_LANG_AZ, @@ -46,7 +45,7 @@ u8lower(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, return nullptr; } - char8_t *dst = alloc(alloc_ctx, nullptr, 0, bufsz, 1, alignof(char8_t)); + char8_t *dst = new(mem, typeof(*dst), bufsz); while (u8next(&ch, &sv)) { rune next = 0; @@ -103,5 +102,5 @@ u8lower(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, } *dstn = n; - return alloc(alloc_ctx, dst, bufsz, n, 1, alignof(char8_t)); + return resz(mem, dst, bufsz, n); } diff --git a/lib/unicode/string/u8norm.c b/lib/unicode/string/u8norm.c index 02156ea..c60fa5b 100644 --- a/lib/unicode/string/u8norm.c +++ b/lib/unicode/string/u8norm.c @@ -1,6 +1,10 @@ +#include #include +#include +#include #include +#include "alloc.h" #include "macros.h" #include "mbstring.h" #include "unicode/_cm.h" @@ -28,22 +32,20 @@ constexpr int TCNT = 28; constexpr int NCNT = VCNT * TCNT; constexpr int SCNT = LCNT * NCNT; -static void decomp(char8_t *, size_t *, size_t, rune, enum normform); +static void decomp(char8_t *, size_t *, size_t, rune, normform_t); static void compbuf(char8_t *, size_t *); static const qcfn qc_lookup[] = { - [NF_NFC] = (qcfn)uprop_get_nfc_qc, - [NF_NFD] = (qcfn)uprop_get_nfd_qc, + [NF_NFC] = (qcfn)uprop_get_nfc_qc, + [NF_NFD] = (qcfn)uprop_get_nfd_qc, [NF_NFKC] = (qcfn)uprop_get_nfkc_qc, [NF_NFKD] = (qcfn)uprop_get_nfkd_qc, }; char8_t * -u8norm(size_t *dstn, u8view_t src, alloc_fn alloc, void *ctx, - enum normform nf) +u8norm(size_t *dstn, u8view_t src, allocator_t mem, normform_t nf) { ASSUME(dstn != nullptr); - ASSUME(alloc != nullptr); ASSUME(BETWEEN(0, nf, 4)); { @@ -57,30 +59,31 @@ u8norm(size_t *dstn, u8view_t src, alloc_fn alloc, void *ctx, } *dstn = src.len; - char8_t *dst = alloc(ctx, nullptr, 0, src.len, 1, alignof(char8_t)); + char8_t *dst = new(mem, typeof(*dst), src.len); return memcpy(dst, src.p, src.len); } no: - /* Pre-allocate a buffer with some initial capacity; there is no need to - check for overflow when computing bufsz because alloc() will handle the - overflow error for us. */ int scale = (nf & 0b10) ? NFKD_SCALE : NFD_SCALE; - size_t bufsz = src.len * scale; - char8_t *dst = alloc(ctx, nullptr, 0, src.len, scale, alignof(char8_t)); + ptrdiff_t bufsz; + if (ckd_mul(&bufsz, src.len, scale)) { + errno = EOVERFLOW; + return nullptr; + } + char8_t *dst = new(mem, typeof(*dst), bufsz); *dstn = 0; for (rune ch; ucsnext(&ch, &src) != 0; decomp(dst, dstn, bufsz, ch, nf)) ; if (nf & 0b01) compbuf(dst, dstn); - return alloc(ctx, dst, src.len, *dstn, 1, alignof(char8_t)); + return resz(mem, dst, bufsz, *dstn); } #define WRITE(ch) *dstn += rtoucs(dst + *dstn, bufsz - *dstn, (ch)) void -decomp(char8_t *dst, size_t *dstn, size_t bufsz, rune ch, enum normform nf) +decomp(char8_t *dst, size_t *dstn, size_t bufsz, rune ch, normform_t nf) { if (uprop_get_hst(ch) != HST_NA) { int si = ch - SBASE; @@ -96,8 +99,8 @@ decomp(char8_t *dst, size_t *dstn, size_t bufsz, rune ch, enum normform nf) WRITE(v); if (t != TBASE) WRITE(t); - } else if (((nf & 0b10) && uprop_get_dt(ch) != DT_NONE) - || ((nf & 0b10) == 0 && uprop_get_dt(ch) == DT_CAN)) + } else if (((nf & 0b10) != 0 && uprop_get_dt(ch) != DT_NONE) + || ((nf & 0b10) == 0 && uprop_get_dt(ch) == DT_CAN)) { struct rview rv = uprop_get_dm(ch); for (size_t i = 0; i < rv.len; i++) @@ -170,12 +173,12 @@ compbuf(char8_t *dst, size_t *dstn) /* Try Hangul composition */ if (comp == 0) { if (BETWEEN(LBASE, L, LBASE + LCNT - 1) - && BETWEEN(VBASE, C, VBASE + VCNT - 1)) + && BETWEEN(VBASE, C, VBASE + VCNT - 1)) { comp = SBASE + ((L - LBASE) * NCNT + (C - VBASE) * TCNT); } else if (BETWEEN(TBASE, C, TBASE + TCNT - 1) - && BETWEEN(SBASE, L, SBASE + SCNT - 1) - && ((L - SBASE) % TCNT) == 0) + && BETWEEN(SBASE, L, SBASE + SCNT - 1) + && ((L - SBASE) % TCNT) == 0) { comp = L + (C - TBASE); } diff --git a/lib/unicode/string/u8title.c b/lib/unicode/string/u8title.c index 3a85f4d..c0637ff 100644 --- a/lib/unicode/string/u8title.c +++ b/lib/unicode/string/u8title.c @@ -2,6 +2,7 @@ #include #include "_attrs.h" +#include "alloc.h" #include "macros.h" #include "mbstring.h" #include "unicode/prop.h" @@ -18,11 +19,9 @@ uprop_ccc_0_or_230(rune ch) } char8_t * -u8title(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, - void *alloc_ctx) +u8title(size_t *dstn, u8view_t sv, caseflags_t flags, allocator_t mem) { ASSUME(dstn != nullptr); - ASSUME(alloc != nullptr); struct tcctx ctx_t; struct lcctx ctx_l; @@ -52,7 +51,7 @@ u8title(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, return nullptr; } - char8_t *dst = alloc(alloc_ctx, nullptr, 0, bufsz, 1, alignof(char8_t)); + char8_t *dst = new(mem, typeof(*dst), bufsz); while (u8next(&ch, &sv)) { if (sv.p > word.p + word.len) { @@ -134,5 +133,5 @@ u8title(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, } *dstn = n; - return alloc(alloc_ctx, dst, bufsz, n, 1, alignof(char8_t)); + return resz(mem, dst, bufsz, n); } diff --git a/lib/unicode/string/u8upper.c b/lib/unicode/string/u8upper.c index a77fcd8..ad10ef7 100644 --- a/lib/unicode/string/u8upper.c +++ b/lib/unicode/string/u8upper.c @@ -1,17 +1,16 @@ #include #include +#include "alloc.h" #include "macros.h" #include "mbstring.h" #include "unicode/prop.h" #include "unicode/string.h" char8_t * -u8upper(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, - void *alloc_ctx) +u8upper(size_t *dstn, u8view_t sv, caseflags_t flags, allocator_t mem) { ASSUME(dstn != nullptr); - ASSUME(alloc != nullptr); struct ucctx ctx = { .az_or_tr = flags & CF_LANG_AZ, @@ -25,7 +24,7 @@ u8upper(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, return nullptr; } - char8_t *dst = alloc(alloc_ctx, nullptr, 0, bufsz, 1, alignof(char8_t)); + char8_t *dst = new(mem, typeof(*dst), bufsz); rune ch; size_t n = 0; @@ -43,5 +42,5 @@ u8upper(size_t *dstn, u8view_t sv, enum caseflags flags, alloc_fn alloc, } *dstn = n; - return alloc(alloc_ctx, dst, bufsz, n, 1, alignof(char8_t)); + return resz(mem, dst, bufsz, n); } diff --git a/test/_brk-test.h b/test/_brk-test.h index 00b84ff..40098c3 100644 --- a/test/_brk-test.h +++ b/test/_brk-test.h @@ -7,7 +7,7 @@ #include #include -#include +#include #include #include #include @@ -57,14 +57,10 @@ test(u8view_t sv, int id) bool rv = true; size_t total = 0; - arena a = mkarena(0); - struct arena_ctx ctx = {.a = &a}; + arena_ctx_t ctx = {}; + allocator_t mem = init_arena_allocator(&ctx, nullptr); - typedef dynarr(char8_t) item; - dynarr(item) items = { - .alloc = alloc_arena, - .ctx = &ctx, - }; + char8_t **items = array_new(mem, typeof(*items), 64); rune op; u8view_t sv_cpy = sv; @@ -77,23 +73,26 @@ test(u8view_t sv, int id) total += w; if (op == U'÷') - DAPUSH(&items, ((item){.alloc = alloc_arena, .ctx = &ctx})); - DAEXTEND(&items.buf[items.len - 1], buf, w); + array_push(&items, array_new(mem, char8_t, 64)); + array_extend(items[array_len(items) - 1], buf, w); } size_t off = 0; - char8_t *p = bufalloc(nullptr, 1, total); - da_foreach (items, g) { - memcpy(p + off, g->buf, g->len); - off += g->len; + char8_t *p = malloc(total); + if (p == nullptr) + err("malloc:"); + for (ptrdiff_t i = 0; i < array_len(items); i++) { + char8_t *g = items[i]; + memcpy(p + off, g, array_len(g)); + off += array_len(g); } u8view_t buf = {p, total}; /* Assert the item count is correct */ - size_t items_got = CNTFUNC(buf); - if (items_got != items.len) { - warn("case %d: expected %zu %s(s) but got %zu: ‘%s’", id, items.len, + ptrdiff_t items_got = CNTFUNC(buf); + if (items_got != array_len(items)) { + warn("case %d: expected %zu %s(s) but got %zu: ‘%s’", id, array_len(items), STR(BRKTYPE_LONG), items_got, sv.p); rv = false; goto out; @@ -102,17 +101,17 @@ test(u8view_t sv, int id) /* Assert the individual items are correct */ u8view_t it1, buf_cpy = buf; for (size_t i = 0; ITERFUNC(&it1, &buf_cpy); i++) { - item it2 = items.buf[i]; - if (!ucseq(it1, ((u8view_t){it2.buf, it2.len}))) { + char8_t *it2 = items[i]; + if (!ucseq(it1, ((u8view_t){it2, array_len(it2)}))) { warn("case %d: expected %s ‘%.*s’ but got ‘%.*s’", id, - STR(BRKTYPE_LONG), (int)it2.len, it2.buf, SV_PRI_ARGS(it1)); + STR(BRKTYPE_LONG), (int)array_len(it2), it2, SV_PRI_ARGS(it1)); rv = false; goto out; } } out: - arena_free(&a); + deleteall(mem); free(p); return rv; } diff --git a/test/_case-test.h b/test/_case-test.h index 299f079..3230f18 100644 --- a/test/_case-test.h +++ b/test/_case-test.h @@ -58,24 +58,23 @@ test(const char8_t *line, int id) ucscut(&after, &sv, U";", 1); ucscut(&flags, &sv, U";", 1); - enum caseflags cf = ucseq(flags, U8("ẞ")) ? CF_ẞ - : ucseq(flags, U8("AZ")) ? CF_LANG_AZ - : ucseq(flags, U8("LT")) ? CF_LANG_LT - : ucseq(flags, U8("NL")) ? CF_LANG_NL - : 0; + caseflags_t cf = ucseq(flags, U8("ẞ")) ? CF_ẞ + : ucseq(flags, U8("AZ")) ? CF_LANG_AZ + : ucseq(flags, U8("LT")) ? CF_LANG_LT + : ucseq(flags, U8("NL")) ? CF_LANG_NL + : /* no flags */ 0; - arena a = mkarena(0); - mapped.p = FUNC(&mapped.len, before, cf, alloc_arena, &((struct arena_ctx){ - .a = &a, - })); + arena_ctx_t ctx = {}; + allocator_t mem = init_arena_allocator(&ctx, nullptr); + mapped.p = FUNC(&mapped.len, before, cf, mem); if (!ucseq(mapped, after)) { warn("case %d: expected ‘%.*s’ but got ‘%.*s’", id, SV_PRI_ARGS(after), SV_PRI_ARGS(mapped)); - arena_free(&a); + deleteall(mem); return false; } - arena_free(&a); + deleteall(mem); return true; } diff --git a/test/_norm-test.h b/test/_norm-test.h index 744bc93..e4da609 100644 --- a/test/_norm-test.h +++ b/test/_norm-test.h @@ -7,7 +7,7 @@ #include #include -#include +#include #include #include #include @@ -53,20 +53,14 @@ bool test(u8view_t sv, int id) { bool rv = true; - arena a = mkarena(0); - struct arena_ctx ctx = {.a = &a}; - - dynarr(u8view_t) columns = { - .alloc = alloc_arena, - .ctx = &ctx, - }; + arena_ctx_t ctx = {}; + allocator_t mem = init_arena_allocator(&ctx, nullptr); u8view_t column; + u8view_t *columns = array_new(mem, typeof(*columns), 64); + while (ucscut(&column, &sv, U";", 1) != MBEND) { - dynarr(char8_t) s = { - .alloc = alloc_arena, - .ctx = &ctx, - }; + char8_t *s = array_new(mem, typeof(*s), 64); rune _; u8view_t cp; @@ -76,10 +70,10 @@ test(u8view_t sv, int id) sscanf(cp.p, "%" SCNxRUNE, &ch); char8_t buf[U8_LEN_MAX]; int w = rtoucs(buf, sizeof(buf), ch); - DAEXTEND(&s, buf, w); + array_extend(s, buf, w); } while (_ != MBEND); - DAPUSH(&columns, ((u8view_t){s.buf, s.len})); + array_push(&columns, ((u8view_t){s, array_len(s)})); } for (size_t i = 0; i < 5; i++) { @@ -97,17 +91,16 @@ test(u8view_t sv, int id) err("invalid NORMTYPE ‘%s’", nt); u8view_t normd = {}; - normd.p = - ucsnorm(&normd.len, columns.buf[i], alloc_arena, &ctx, NORMTYPE); - if (!ucseq(columns.buf[base], normd)) { + normd.p = ucsnorm(&normd.len, columns[i], mem, NORMTYPE); + if (!ucseq(columns[base], normd)) { warn("case %d: expected c%zu to be ‘%.*s’ but got ‘%.*s’", id, - i + 1, SV_PRI_ARGS(columns.buf[base]), SV_PRI_ARGS(normd)); + i + 1, SV_PRI_ARGS(columns[base]), SV_PRI_ARGS(normd)); rv = false; goto out; } } out: - arena_free(&a); + deleteall(mem); return rv; } diff --git a/test/array-test.c b/test/array-test.c new file mode 100644 index 0000000..3eb955a --- /dev/null +++ b/test/array-test.c @@ -0,0 +1,82 @@ +#include +#include + +#include +#include +#include + +typedef struct { + allocator_t inner; + ptrdiff_t num_allocs, last_alloc_size; + bool didfree; +} dbg_ctx_t; + +static void *dbg_alloc(allocator_t, alloc_mode_t, void *, ptrdiff_t, ptrdiff_t, + ptrdiff_t, ptrdiff_t); + +int +main(int, char **argv) +{ + mlib_setprogname(argv[0]); + + dbg_ctx_t ctx = {.inner = init_heap_allocator(nullptr)}; + allocator_t mem = { + .alloc = dbg_alloc, + .ctx = &ctx, + }; + + int *xs = array_new(mem, int, 4); + if (ctx.num_allocs != 1) + err("ctx.num_allocs == %td\n", ctx.num_allocs); + /* Integers don’t need padding. It simplifies the test */ + if (ctx.last_alloc_size != sizeof(_mlib_arr_hdr_t) + sizeof(int) * 4) + err("ctx.last_alloc_size == %td\n", ctx.last_alloc_size); + + xs[0] = 1; xs[1] = 2; + xs[2] = 3; xs[3] = 4; + array_hdr(xs)->len = 4; + + for (int i = 4; i < 69; i++) { + array_push(&xs, i + 1); + if (stdc_count_ones((unsigned)i) == 1) { + /* Integers don’t need padding. It simplifies the test */ + if ((size_t)ctx.last_alloc_size + != sizeof(_mlib_arr_hdr_t) + sizeof(int) * i * 2) + { + err("ctx.last_alloc_size == %td\n", ctx.last_alloc_size); + } + } + } + for (int i = 0; i < 69; i++) { + if (xs[i] != i + 1) + err("xs[%d] == %d", i, xs[i]); + } + + if (array_len(xs) != 69) + err("array_len(xs) == %td", array_len(xs)); + + array_free(xs); + if (!ctx.didfree) + err("ctx.did_free == false"); + + return EXIT_SUCCESS; +} + +void * +dbg_alloc(allocator_t mem, alloc_mode_t mode, void *ptr, ptrdiff_t oldnmemb, + ptrdiff_t newnmemb, ptrdiff_t elemsz, ptrdiff_t align) +{ + dbg_ctx_t *p = mem.ctx; + switch (mode) { + case ALLOC_NEW: + case ALLOC_RESIZE: + p->didfree = false; + p->num_allocs++; + p->last_alloc_size = newnmemb * elemsz; + break; + case ALLOC_FREE: + case ALLOC_FREEALL: + p->didfree = true; + } + return p->inner.alloc(p->inner, mode, ptr, oldnmemb, newnmemb, elemsz, align); +} diff --git a/test/wbrk-human-test.c b/test/wbrk-human-test.c index 955cf4f..45dcaef 100644 --- a/test/wbrk-human-test.c +++ b/test/wbrk-human-test.c @@ -2,7 +2,8 @@ #include #include -#include +#include +#include #include #include #include @@ -49,30 +50,33 @@ test(u8view_t sv, int id) u8view_t src; ucscut(&src, &sv, U";", 1); + allocator_t mem = init_heap_allocator(nullptr); + u8view_t w; - dynarr(u8view_t) ws = {.alloc = alloc_heap}; + u8view_t *ws = array_new(mem, typeof(*ws), 64); while (ucscut(&w, &sv, U"|", 1) != MBEND) - DAPUSH(&ws, w); + array_push(&ws, w); if (w.len > 0) - DAPUSH(&ws, w); + array_push(&ws, w); /* Assert the word count is correct */ size_t n; - if ((n = ucswcnt_human(src)) != ws.len) { - warn("case %d: expected %zu words but got %zu", id, ws.len, n); + /* TODO: Fix return type and remove cast */ + if ((ptrdiff_t)(n = ucswcnt_human(src)) != array_len(ws)) { + warn("case %d: expected %tu words but got %zu", id, array_len(ws), n); return false; } /* Assert the individual words are correct */ for (size_t i = 0; ucswnext_human(&w, &src) != 0; i++) { - if (!ucseq(w, ws.buf[i])) { + if (!ucseq(w, ws[i])) { warn("case %d: expected word %zu to be ‘%.*s’ but got ‘%.*s’", id, - i, SV_PRI_ARGS(ws.buf[i]), SV_PRI_ARGS(w)); + i, SV_PRI_ARGS(ws[i]), SV_PRI_ARGS(w)); return false; } } - free(ws.buf); + array_free(ws); return true; } -- cgit v1.2.3