cheney copying collector

1 files changed, 104 insertions, 0 deletions

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