commit 2717ef88f823bb149b803ef530c22d48202f9f94
Author: Jack Mordaunt <jackmordaunt.dev@gmail.com>
Date: Thu, 18 May 2023 13:16:12 +0800
Squashed 'vendor/growable-buf/' content from commit 6ad7b3d
git-subtree-dir: vendor/growable-buf
git-subtree-split: 6ad7b3dcc1f22edb79e0e33be0e79c17859febff
Diffstat:
| A | .gitignore | | | 1 | + |
| A | Makefile | | | 15 | +++++++++++++++ |
| A | README.md | | | 92 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | UNLICENSE | | | 24 | ++++++++++++++++++++++++ |
| A | buf.h | | | 112 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | tests.c | | | 209 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
6 files changed, 453 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+tests
diff --git a/Makefile b/Makefile
@@ -0,0 +1,15 @@
+.POSIX:
+CFLAGS = -std=c99 -Wall -Wextra -O3 -g3
+
+tests: tests.c buf.h
+ $(CC) $(LDFLAGS) $(CFLAGS) -o $@ tests.c $(LDLIBS)
+
+test: check
+check: tests
+ ./tests
+
+bench: tests
+ ./tests 558d2750ae0e0887
+
+clean:
+ rm -f tests
diff --git a/README.md b/README.md
@@ -0,0 +1,92 @@
+# Growable Memory Buffers for C99
+
+This C99 header library provides a simple, portable interface to
+growable buffers of homogeneous values of any type, similar to a
+std::vector in C++. The user need not use any particular struct, and the
+buffer need only initialize to NULL.
+
+Each "function" in the interface is actually a macro, and its usage is
+reflected by these hypothetical prototypes:
+
+```c
+/* Returns the number of elements in the buffer (for push and pop).
+*/
+size_t buf_size(type *v);
+
+/* Returns the total capacity of the buffer.
+*/
+size_t buf_capacity(type *v);
+
+/* Destroy and free the buffer, effectively resetting it.
+ * Potentially assigns a new V pointer.
+*/
+void buf_free(type *v);
+
+/* Append an element E to the end of the buffer, growing if necessary.
+ * Potentially increases the capacity and assigns a new V pointer.
+*/
+void buf_push(type *v, type e);
+
+/* Remove an element E from the end of the buffer.
+ * Neither the capacity nor the V pointer will change. Popping when the
+ * size is zero has undefined results.
+ */
+type buf_pop(type *v);
+
+/* Increase buffer capactity by N elements.
+ * Potentially assigns a new V pointer while also returning it.
+ */
+type *buf_grow(type *v, ptrdiff_t n);
+
+/* Set buffer capactity to exactly N elements.
+ * Potentially assigns a new V pointer while also returning it. A
+ * negative capacity has undefined results.
+ */
+type *buf_trunc(type *v, ptrdiff_t n);
+
+/* Set buffer size to zero.
+ * Only affects push and pop. The capacity and buffer contents are
+ * unchanged.
+ */
+void buf_clear(type *v);
+```
+
+Note: `buf_push()`, `buf_grow()`, `buf_trunc()`, and `buf_free()` may
+change the buffer pointer, and any previously-taken pointers should be
+considered invalidated. This has important consequences that must be
+considered.
+
+The `BUF_INIT_CAPACITY` determines the initial capacity for buffers
+receiving their first push.
+
+The `BUF_ABORT` macro is evaluated when the system runs out of memory.
+It defaults to `abort()`, but you may override it to run your own abort
+code instead.
+
+Example usage:
+
+```c
+float *values = 0;
+
+/* Append 25 values */
+for (size_t i = 0; i < 25; i++)
+ buf_push(values, rand() / (float)RAND_MAX);
+
+/* Access 25 values using the normal [] operator */
+for (size_t i = 0; i < buf_size(values); i++)
+ printf("values[%zu] = %f\n", i, values[i]);
+
+/* Destroy/reset the buffer */
+buf_free(values);
+```
+
+## Purpose
+
+This library is inspired by [stb `stretchy_buffer.h`][sb]. The
+difference is that it's written in C99 so that it doesn't need to rely
+on undefined behavior. This does so by using a flexible array member and
+the `offsetof()` macro. It also checks for integer overflows before
+allocating any memory, making it safer.
+
+
+[sb]: https://github.com/nothings/stb/blob/master/stretchy_buffer.h
diff --git a/UNLICENSE b/UNLICENSE
@@ -0,0 +1,24 @@
+This is free and unencumbered software released into the public domain.
+
+Anyone is free to copy, modify, publish, use, compile, sell, or
+distribute this software, either in source code form or as a compiled
+binary, for any purpose, commercial or non-commercial, and by any
+means.
+
+In jurisdictions that recognize copyright laws, the author or authors
+of this software dedicate any and all copyright interest in the
+software to the public domain. We make this dedication for the benefit
+of the public at large and to the detriment of our heirs and
+successors. We intend this dedication to be an overt act of
+relinquishment in perpetuity of all present and future rights to this
+software under copyright law.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+OTHER DEALINGS IN THE SOFTWARE.
+
+For more information, please refer to <http://unlicense.org/>
diff --git a/buf.h b/buf.h
@@ -0,0 +1,112 @@
+/* buf.h --- growable memory buffers for C99
+ * This is free and unencumbered software released into the public domain.
+ *
+ * buf_size(v) : return the number of elements in the buffer (size_t)
+ * buf_capacity(v) : return the total capacity of the buffer (size_t)
+ * buf_free(v) : destroy and free the buffer
+ * buf_push(v, e) : append an element E to the end
+ * buf_pop(v) : remove and return an element E from the end
+ * buf_grow(v, n) : increase buffer capactity by (ptrdiff_t) N elements
+ * buf_trunc(v, n) : set buffer capactity to exactly (ptrdiff_t) N elements
+ * buf_clear(v, n) : set buffer size to 0 (for push/pop)
+ *
+ * Note: buf_push(), buf_grow(), buf_trunc(), and buf_free() may change
+ * the buffer pointer, and any previously-taken pointers should be
+ * considered invalidated.
+ *
+ * Example usage:
+ *
+ * float *values = 0;
+ * for (size_t i = 0; i < 25; i++)
+ * buf_push(values, rand() / (float)RAND_MAX);
+ * for (size_t i = 0; i < buf_size(values); i++)
+ * printf("values[%zu] = %f\n", i, values[i]);
+ * buf_free(values);
+ */
+#include <stddef.h>
+#include <stdlib.h>
+
+#ifndef BUF_INIT_CAPACITY
+# define BUF_INIT_CAPACITY 8
+#endif
+
+#ifndef BUF_ABORT
+# define BUF_ABORT abort()
+#endif
+
+struct buf {
+ size_t capacity;
+ size_t size;
+ char buffer[];
+};
+
+#define buf_ptr(v) \
+ ((struct buf *)((char *)(v) - offsetof(struct buf, buffer)))
+
+#define buf_free(v) \
+ do { \
+ if (v) { \
+ free(buf_ptr((v))); \
+ (v) = 0; \
+ } \
+ } while (0)
+
+#define buf_size(v) \
+ ((v) ? buf_ptr((v))->size : 0)
+
+#define buf_capacity(v) \
+ ((v) ? buf_ptr((v))->capacity : 0)
+
+#define buf_push(v, e) \
+ do { \
+ if (buf_capacity((v)) == buf_size((v))) { \
+ (v) = buf_grow1(v, sizeof(*(v)), \
+ !buf_capacity((v)) ? \
+ BUF_INIT_CAPACITY : \
+ buf_capacity((v))); \
+ } \
+ (v)[buf_ptr((v))->size++] = (e); \
+ } while (0)
+
+#define buf_pop(v) \
+ ((v)[--buf_ptr(v)->size])
+
+#define buf_grow(v, n) \
+ ((v) = buf_grow1((v), sizeof(*(v)), n))
+
+#define buf_trunc(v, n) \
+ ((v) = buf_grow1((v), sizeof(*(v)), n - buf_capacity(v)))
+
+#define buf_clear(v) \
+ ((v) ? (buf_ptr((v))->size = 0) : 0)
+
+
+static void *
+buf_grow1(void *v, size_t esize, ptrdiff_t n)
+{
+ struct buf *p;
+ size_t max = (size_t)-1 - sizeof(struct buf);
+ if (v) {
+ p = buf_ptr(v);
+ if (n > 0 && p->capacity + n > max / esize)
+ goto fail; /* overflow */
+ p = realloc(p, sizeof(struct buf) + esize * (p->capacity + n));
+ if (!p)
+ goto fail;
+ p->capacity += n;
+ if (p->size > p->capacity)
+ p->size = p->capacity;
+ } else {
+ if ((size_t)n > max / esize)
+ goto fail; /* overflow */
+ p = malloc(sizeof(struct buf) + esize * n);
+ if (!p)
+ goto fail;
+ p->capacity = n;
+ p->size = 0;
+ }
+ return p->buffer;
+fail:
+ BUF_ABORT;
+ return 0;
+}
diff --git a/tests.c b/tests.c
@@ -0,0 +1,209 @@
+#include <stdio.h>
+#include <stdint.h>
+#include <setjmp.h>
+
+static jmp_buf escape;
+
+static void
+test_abort(void)
+{
+ longjmp(escape, 1);
+}
+
+#define BUF_ABORT test_abort()
+#include "buf.h"
+
+#if _WIN32
+# define C_RED(s) s
+# define C_GREEN(s) s
+#else
+# define C_RED(s) "\033[31;1m" s "\033[0m"
+# define C_GREEN(s) "\033[32;1m" s "\033[0m"
+#endif
+
+#define TEST(s, x) \
+ do { \
+ if (x) { \
+ printf(C_GREEN("PASS") " %s\n", s); \
+ count_pass++; \
+ } else { \
+ printf(C_RED("FAIL") " %s\n", s); \
+ count_fail++; \
+ } \
+ } while (0)
+
+static uint32_t
+pcg32(uint64_t *s)
+{
+ uint64_t m = 0x5851f42d4c957f2d;
+ uint64_t a = 0x8b260b70b8e98891;
+ uint64_t p = *s;
+ uint32_t x = ((p >> 18) ^ p) >> 27;
+ uint32_t r = p >> 59;
+ *s = p * m + a;
+ return (x >> r) | (x << (-r & 31u));
+}
+
+static unsigned long
+bench(uint64_t *rng)
+{
+ unsigned long r = 0;
+ uint32_t n = 1000000 + pcg32(rng) % 4000000;
+ float *buf = 0;
+
+ for (uint32_t i = 0; i < n; i++)
+ buf_push(buf, pcg32(rng) / (double)UINT32_MAX);
+
+ float threshold = pcg32(rng) / (double)UINT32_MAX;
+ for (uint32_t i = 0; i < n; i++)
+ r += buf[i] > threshold;
+
+ buf_free(buf);
+ return r;
+}
+
+#ifdef _WIN32
+#include <windows.h>
+uint64_t
+uepoch(void)
+{
+ FILETIME ft;
+ GetSystemTimeAsFileTime(&ft);
+ uint64_t tt = ft.dwHighDateTime;
+ tt <<= 32;
+ tt |= ft.dwLowDateTime;
+ tt /=10;
+ tt -= UINT64_C(11644473600000000);
+ return tt;
+}
+#else
+#include <sys/time.h>
+uint64_t
+uepoch(void)
+{
+ struct timeval tv;
+ gettimeofday(&tv, NULL);
+ return 1000000LL * tv.tv_sec + tv.tv_usec;
+}
+#endif
+
+int
+main(int argc, char **argv)
+{
+ /* Benchtest? */
+ if (argc > 1) {
+ uint64_t rng = strtoull(argv[1], 0, 16);
+ unsigned long r = 0;
+ uint64_t start = uepoch();
+ for (int i = 0; i < 300; i++)
+ r += bench(&rng);
+ double t = (uepoch() - start) / 1e6;
+ printf("%.6gs : actual %lu, expect 428859598\n", t, r);
+ return 0;
+ }
+
+ /* volatile due to setjmp() / longjmp() */
+ volatile int count_pass = 0;
+ volatile int count_fail = 0;
+
+ if (setjmp(escape))
+ abort();
+
+ /* initialization, buf_free() */
+ float *a = 0;
+ TEST("capacity init", buf_capacity(a) == 0);
+ TEST("size init", buf_size(a) == 0);
+ buf_push(a, 1.3f);
+ TEST("size 1", buf_size(a) == 1);
+ TEST("value", a[0] == (float)1.3f);
+ buf_clear(a);
+ TEST("clear", buf_size(a) == 0);
+ TEST("clear not-free", a != 0);
+ buf_free(a);
+ TEST("free", a == 0);
+
+ /* Clearing an NULL pointer is a no-op */
+ buf_clear(a);
+ TEST("clear empty", buf_size(a) == 0);
+ TEST("clear no-op", a == 0);
+
+ /* buf_push(), [] operator */
+ long *ai = 0;
+ for (int i = 0; i < 10000; i++)
+ buf_push(ai, i);
+ TEST("size 10000", buf_size(ai) == 10000);
+ int match = 0;
+ for (int i = 0; i < (int)(buf_size(ai)); i++)
+ match += ai[i] == i;
+ TEST("match 10000", match == 10000);
+ buf_free(ai);
+
+ /* buf_grow(), buf_trunc() */
+ buf_grow(ai, 1000);
+ TEST("grow 1000", buf_capacity(ai) == 1000);
+ TEST("size 0 (grow)", buf_size(ai) == 0);
+ buf_trunc(ai, 100);
+ TEST("trunc 100", buf_capacity(ai) == 100);
+ buf_free(ai);
+
+ /* buf_pop() */
+ buf_push(a, 1.1);
+ buf_push(a, 1.2);
+ buf_push(a, 1.3);
+ buf_push(a, 1.4);
+ TEST("size 4", buf_size(a) == 4);
+ TEST("pop 3", buf_pop(a) == (float)1.4f);
+ buf_trunc(a, 3);
+ TEST("size 3", buf_size(a) == 3);
+ TEST("pop 2", buf_pop(a) == (float)1.3f);
+ TEST("pop 1", buf_pop(a) == (float)1.2f);
+ TEST("pop 0", buf_pop(a) == (float)1.1f);
+ TEST("size 0 (pop)", buf_size(a) == 0);
+ buf_free(a);
+
+ /* Memory allocation failures */
+
+ volatile int aborted;
+
+ {
+ int *volatile p = 0;
+ aborted = 0;
+ if (!setjmp(escape)) {
+ size_t max = (PTRDIFF_MAX - sizeof(struct buf)) / sizeof(*p) + 1;
+ buf_grow(p, max);
+ buf_grow(p, max);
+ } else {
+ aborted = 1;
+ }
+ buf_free(p);
+ TEST("out of memory", aborted);
+ }
+
+ {
+ int *volatile p = 0;
+ aborted = 0;
+ if (!setjmp(escape)) {
+ buf_trunc(p, PTRDIFF_MAX);
+ } else {
+ aborted = 1;
+ }
+ buf_free(p);
+ TEST("overflow init", aborted);
+ }
+
+ {
+ int *volatile p = 0;
+ aborted = 0;
+ if (!setjmp(escape)) {
+ buf_trunc(p, 1); /* force realloc() use next */
+ buf_trunc(p, PTRDIFF_MAX);
+ } else {
+ aborted = 1;
+ }
+ buf_free(p);
+ TEST("overflow grow", aborted);
+ }
+
+ printf("%d fail, %d pass\n", count_fail, count_pass);
+ return count_fail != 0;
+}
