cheney copying collector

3 files changed, 189 insertions, 0 deletions

diff --git a/include/cheney_c89.h b/include/cheney_c89.h
new file mode 100644
index 0000000..32f379a
--- /dev/null
+++ b/include/cheney_c89.h
@@ -0,0 +1,33 @@
+/* Copyright (C) 2024 Peter McGoron
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program. If not, see
+ * <https://www.gnu.org/licenses/>.
+*/
+
+#ifndef UNS_CHENEY_C89_H
+#define UNS_CHENEY_C89_H
+
+#include "uns.h"
+
+/* Cheney copying collector in pure portable C89. */
+
+void uns_cheney_c89_deinit(struct uns_gc *gc);
+int uns_cheney_c89_init(struct uns_gc *gc);
+int uns_cheney_c89_collect(struct uns_gc *gc);
+void *uns_cheney_c89_alloc(struct uns_gc *gc, size_t bytes);
+void *uns_cheney_c89_alloc_record(struct uns_gc *gc, size_t records);
+
+const extern size_t uns_cheney_c89_ctx_size;
+
+#endif
diff --git a/include/internal/c89_relo.h b/include/internal/c89_relo.h
new file mode 100644
index 0000000..5347aa8
--- /dev/null
+++ b/include/internal/c89_relo.h
@@ -0,0 +1,52 @@
+#ifndef UNS_FORMAT_C89_H
+#define UNS_FORMAT_C89_H
+/* Copyright (C) 2024 Peter McGoron
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program. If not, see
+ * <https://www.gnu.org/licenses/>.
+*/
+
+#include "uns.h"
+
+/* This is a strictly C89+ header format with relocation pointers and
+ * lengths.
+ *
+ * Forwarding pointers need to be stored in the header because in strict
+ * C, arithmetic on pointers is undefined for pointers not pointing into
+ * the same object.
+ *
+ * The length of the string is limited to "len" bytes and is stored as
+ * a `uns_sword`. If the word is negative, then the region is a record,
+ * and if the number is positive then the region is just bytes.
+ */
+
+struct uns_c89_relo_hdr {
+	void *relo;
+	uns_sword len;
+};
+#define uns_c89_relo_get_hdr(p)((struct uns_c89_relo_hdr *)(p) - 1)
+
+size_t uns_c89_relo_get_len(void *p);
+size_t uns_c89_relo_get_record_len(void *p);
+
+#define uns_c89_relo_get_relo(p) (uns_c89_relo_get_hdr(p)->relo)
+#define uns_c89_relo_set_relo(p, v) (uns_c89_relo_get_relo(p) = (v))
+#define uns_c89_relo_is_record(p) (uns_c89_relo_get_hdr(p)->len < 0)
+
+void *uns_c89_relo_init(void *p, size_t len_size, int is_record);
+
+void uns_c89_relo_record_set(void *rec, size_t i, void *v);
+void *uns_c89_relo_record_get(void *rec, size_t i);
+
+#endif
diff --git a/include/uns.h b/include/uns.h
new file mode 100644
index 0000000..1277b32
--- /dev/null
+++ b/include/uns.h
@@ -0,0 +1,104 @@
+#ifndef UNIVERSAL_SERVICE_H
+#define UNIVERSAL_SERVICE_H
+/* Copyright (C) 2024 Peter McGoron
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program. If not, see
+ * <https://www.gnu.org/licenses/>.
+*/
+
+#include <stddef.h>
+#if !defined(UNS_WORD) && __STDC_VERSION__ >= 199101L
+# include <stdint.h>
+# include <limits.h>
+# define UNS_WORD uintptr_t
+# define UNS_SIGNED_WORD intptr_t
+# define UNS_WORD_MAX UINTPTR_MAX
+# define UNS_SWORD_MAX INTPTR_MAX
+# define UNS_SWORD_MIN INTPTR_MIN
+#elif !defined(UNS_WORD)
+# include <limits.h>
+# define UNS_WORD unsigned long
+# define UNS_WORD_MAX ULONG_MAX
+# define UNS_SIGNED_WORD long
+# define UNS_SWORD_MAX LONG_MAX
+# define UNS_SWORD_MIN LONG_MIN
+#endif
+
+typedef UNS_WORD uns_word;
+typedef UNS_SIGNED_WORD uns_sword;
+
+/** Doubly linked list used to
+  *
+  * 1) Store roots of the GC,
+  * 2) Store GC pointers used in C and possibly not pointed-to anywhere
+  *    else in GC space,
+  * 3) Preserve the location of a pointer after it moves.
+  *
+  * A root that is not a part of any GC MUST have ``prev`` and ``next``
+  * set to NULL.
+  */
+struct uns_root_list {
+	struct uns_root_list *prev;
+	void *p;
+	struct uns_root_list *next;
+};
+
+struct uns_gc {
+	void *ctx;
+
+	/* The collector only changes the pointer values of "p".
+	 *
+	 * * The collector never adds or removes roots.
+	 * * The collector never rearranges the order of the container structures.
+	 *
+	 * The roots list can have repeated values.
+	 */
+	struct uns_root_list *roots;
+	size_t next_alloc;
+	void (*oom)(struct uns_gc *);
+	void (*after_gc)(struct uns_gc *);
+
+	size_t before_collection;
+	size_t after_collection;
+	long collection_number;
+
+	void (*deinit)(struct uns_gc *);
+
+	/* These functions, and only these functions, may invalidate
+	 * pointers by either moving them or freeing them.
+	 */
+	int (*collect)(struct uns_gc *);
+	void *(*alloc)(struct uns_gc *, size_t);
+	void *(*alloc_record)(struct uns_gc *, size_t);
+
+	/* These functions MUST NOT cause collections. */
+
+	/* This function is optional. It is only provided if the GC can
+	 * calculate the length of the pointer quickly.
+	 */
+	size_t (*len)(void *);
+
+	void (*record_set_ptr)(void *, size_t, void *);
+	void *(*record_get_ptr)(void *, size_t);
+};
+
+/** Add a root to the GC. The root must point to valid memory, or NULL. */
+void uns_root_add(struct uns_gc *gc, struct uns_root_list *root);
+
+/** Remove a root from the GC. It is OK to remove a root that is not a
+  * part of any GC using this function (the call will have no effect).
+  */
+void uns_root_remove(struct uns_gc *gc, struct uns_root_list *root);
+
+#endif