cheney copying collector

5 files changed, 381 insertions, 0 deletions

diff --git a/examples/string/test_common.c b/examples/string/test_common.c
new file mode 100644
index 0000000..de12d93
--- /dev/null
+++ b/examples/string/test_common.c
@@ -0,0 +1,80 @@
+/* Copyright (c) 2024, Peter McGoron
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1) Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2) Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "uns.h"
+#include "cheney_c89.h"
+
+/* This file sets up the environment for a test.
+ *
+ * Each test is compiled as a separate program to isolate tests portably.
+ * A test suite is a shell script (or batch file or whatever you want...)
+ */
+
+static void oom(struct uns_gc *gc)
+{
+	(void)gc;
+	fprintf(stderr, "failed: OOM\n");
+	exit(1);
+}
+
+static void after_gc(struct uns_gc *gc)
+{
+	fprintf(stderr,
+	        "The garbage collector has run %ld times\n"
+	        "\tbefore collection: %lu\n"
+	        "\tafter collection: %lu\n",
+	        gc->collection_number,
+	        gc->before_collection,
+	        gc->after_collection
+	);
+
+	if (gc->after_collection >= gc->before_collection/2)
+		gc->next_alloc *= 2;
+}
+
+extern int test(struct uns_gc *gc);
+
+int main(void)
+{
+	static struct uns_gc gc;
+	int i;
+
+	gc.next_alloc = 1024;
+	gc.ctx = malloc(uns_cheney_c89_ctx_size);
+	gc.after_gc = after_gc;
+	gc.oom = oom;
+
+	if (!gc.ctx)
+		return 1;
+	if (!uns_cheney_c89_init(&gc))
+		return 2;
+	gc.next_alloc = 2048;
+
+	i = test(&gc);
+	gc.deinit(&gc);
+	return i;
+}
diff --git a/examples/string/test_large.c b/examples/string/test_large.c
new file mode 100644
index 0000000..dddbbff
--- /dev/null
+++ b/examples/string/test_large.c
@@ -0,0 +1,77 @@
+/* Copyright (c) 2024, Peter McGoron
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1) Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2) Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "uns.h"
+#include "uns_string.h"
+
+int test(struct uns_gc *gc)
+{
+	struct uns_root_list r = {0};
+	size_t i;
+
+	/* MistralAI 8x7B 0.1:
+	 * Prompt: "write a sonnet about garbage collectors (the memory management kind)"
+	 *
+	 * This string constant is larger than the standard's minimum. If
+	 * this test doesn't compile, get a better compiler.
+	 */
+	const char s[] =
+		"To the humble garbagemen of code's dark night,\n"
+		"Who tread through bits and bytes with steady hand.\n"
+		"They roam the heap, in dimly lit sight,\n"
+		"And rescue order from chaos unplanned.\n"
+
+		"With algorithms precise and swift they glide,\n"
+		"Through malloc'd arrays and pointers vast.\n"
+		"Their work essential to keep programs wide,\n"
+		"From crashing down upon us too soon passed.\n"
+
+		"Yet often left unsung are these brave knights,\n"
+		"Whose vigilance keeps our software clean.\n"
+		"In shadows cast by CPUs might,\n"
+		"Unseen forces that make sense of unseen.\n"
+
+		"So here's to you, dear Garbage Collectors all,\n"
+		"Thank you for keeping coding dreams enthralled.\n"
+	;
+
+	uns_string_alloc_into(&gc, &r);
+
+	/* generate lots of garbage */
+	uns_string_alloc_into(&gc, &r);
+	uns_root_add(&gc, &r);
+	for (i = 0; i < 100; i++)
+		uns_string_append_bytes(&gc, &r, s, sizeof(s) - 1);
+	uns_root_remove(&gc, &r);
+
+	/* Generate lots of garbage by being inefficient. */
+	uns_string_alloc_into(&gc, &r);
+	uns_root_add(&gc, &r);
+	for (i = 0; i < sizeof(s) - 1; i++)
+		uns_string_append_char(&gc, &r, s[i]);
+	uns_root_remove(&gc, &r);
+
+	return 0;
+}
diff --git a/examples/string/test_small.c b/examples/string/test_small.c
new file mode 100644
index 0000000..08b2ed2
--- /dev/null
+++ b/examples/string/test_small.c
@@ -0,0 +1,44 @@
+/* Copyright (c) 2024, Peter McGoron
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1) Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2) Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include "uns.h"
+#include "uns_string.h"
+
+int test(struct uns_gc *gc)
+{
+	struct uns_root_list r = {0};
+	const char s[] = "hello, world";
+
+	uns_string_alloc(gc, &r, 32);
+	uns_root_add(gc, &r);
+	uns_string_append_bytes(gc, &r, s, sizeof(s) - 1);
+
+	printf("%s\n", uns_string_cstring(gc, &r));
+
+	uns_root_remove(gc, &r);
+
+	return 0;
+}
diff --git a/examples/string/uns_string.c b/examples/string/uns_string.c
new file mode 100644
index 0000000..e510fcf
--- /dev/null
+++ b/examples/string/uns_string.c
@@ -0,0 +1,127 @@
+/* Copyright (c) 2024, Peter McGoron
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1) Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2) Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <string.h>
+#include "uns.h"
+#include "uns_string.h"
+
+enum {
+	ALLEN_IND = 0,
+	LEN_IND = 1,
+	BYTES_IND = 2,
+	NUMBER_OF_IND = 3
+};
+
+static size_t get_size_t(struct uns_gc *gc, struct uns_root_list *root, size_t i)
+{
+	size_t r;
+
+	void *p = gc->record_get_ptr(root->p, i);
+	memcpy(&r, p, sizeof(r));
+
+	return r;
+}
+
+static void set_size_t(struct uns_gc *gc, struct uns_root_list *root, size_t i, size_t val)
+{
+	void *p = gc->record_get_ptr(root->p, i);
+	memcpy(p, &val, sizeof(val));
+}
+
+#define set_allen(gc,root,val) set_size_t(gc, root, ALLEN_IND, val)
+#define set_len(gc,root,val) set_size_t(gc, root, LEN_IND, val)
+
+static size_t uns_string_allen(struct uns_gc *gc, struct uns_root_list *root)
+{
+	return get_size_t(gc, root, ALLEN_IND);
+}
+
+size_t uns_string_len(struct uns_gc *gc, struct uns_root_list *root)
+{
+	return get_size_t(gc, root, LEN_IND);
+}
+
+char *uns_string_ptr(struct uns_gc *gc, struct uns_root_list *root)
+{
+	return gc->record_get_ptr(root->p, BYTES_IND);
+}
+
+void uns_string_alloc(struct uns_gc *gc, struct uns_root_list *root, size_t start_len)
+{
+	root->p = gc->alloc_record(gc, NUMBER_OF_IND);
+
+	gc->record_set_ptr(root->p, ALLEN_IND, gc->alloc(gc, sizeof(size_t)));
+	set_allen(gc, root, start_len);
+
+	gc->record_set_ptr(root->p, LEN_IND, gc->alloc(gc, sizeof(size_t)));
+	set_len(gc, root, 0);
+
+	gc->record_set_ptr(root->p, BYTES_IND, gc->alloc(gc, start_len));
+}
+
+void uns_string_resize(struct uns_gc *gc, struct uns_root_list *root, size_t newlen)
+{
+	char *tmp;
+
+	tmp = gc->alloc(gc, newlen);
+	set_allen(gc, root, newlen);
+
+	if (newlen <= uns_string_len(gc, root))
+		set_len(gc, root, newlen);
+	memcpy(tmp, uns_string_ptr(gc, root), uns_string_len(gc, root));
+}
+
+void uns_string_ensure(struct uns_gc *gc, struct uns_root_list *root, size_t extent)
+{
+	size_t used = uns_string_len(gc, root);
+	size_t allen = uns_string_allen(gc, root);
+
+	if (used + extent > allen)
+		uns_string_resize(gc, root, used + extent);
+}
+
+void uns_string_append_bytes(struct uns_gc *gc, struct uns_root_list *to,
+                            const void *from, size_t bytes)
+{
+	size_t len = uns_string_len(gc, to);
+	uns_string_ensure(gc, to, bytes);
+	memcpy(uns_string_ptr(gc, to) + len, from, bytes);
+	set_len(gc, to, len + bytes);
+}
+
+void uns_string_append_char(struct uns_gc *gc, struct uns_root_list *root, char c)
+{
+	uns_string_append_bytes(gc, root, &c, 1);
+}
+
+char *uns_string_cstring(struct uns_gc *gc, struct uns_root_list *root)
+{
+	char *p;
+	uns_string_ensure(gc, root, 1);
+
+	p = uns_string_ptr(gc, root);
+	p[uns_string_len(gc, root)] = 0;
+	return p;
+}
diff --git a/examples/string/uns_string.h b/examples/string/uns_string.h
new file mode 100644
index 0000000..14ae812
--- /dev/null
+++ b/examples/string/uns_string.h
@@ -0,0 +1,53 @@
+#ifndef UNS_STRING_H
+#define UNS_STRING_H
+
+/* Copyright (c) 2024, Peter McGoron
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1) Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2) Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "uns.h"
+
+/* This code implements imperative strings. Imperative strings can be
+ * updated in-place. This requires storing the amount of memory left in
+ * the string, and the length of the string itself.
+ *
+ * String format:
+ * record: [slot 1]             [slot 2]   [slot 3]
+ *            |                    |          |
+ *         size_t                size_t     bytes
+ *        (allocated length)    (used)     (size of used)
+ */
+
+size_t uns_string_len(struct uns_gc *gc, struct uns_root_list *root);
+char *uns_string_ptr(struct uns_gc *gc, struct uns_root_list *root);
+
+/* The following functions may cause a collection. */
+void uns_string_alloc(struct uns_gc *gc, struct uns_root_list *root, size_t start_len);
+void uns_string_resize(struct uns_gc *gc, struct uns_root_list *root, size_t newlen);
+void uns_string_ensure(struct uns_gc *gc, struct uns_root_list *root, size_t extent);
+void uns_string_append_bytes(struct uns_gc *gc, struct uns_root_list *to,
+                            const void *from, size_t bytes);
+void uns_string_append_char(struct uns_gc *gc, struct uns_root_list *root, char c);
+char *uns_string_cstring(struct uns_gc *gc, struct uns_root_list *root);
+#endif