commit 80a86b247739696fac607fb85a09f3a0ac50c4b4
parent 9769f561b8ca0bb35106780d0e2430a0edec7a3a
Author: MikoĊaj Lenczewski <mblenczewski@gmail.com>
Date: Sat, 12 Apr 2025 12:36:40 +0000
Add relative pointer implementation.
Diffstat:
| A | relptr.c | | | 108 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | relptr.h | | | 50 | ++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 158 insertions(+), 0 deletions(-)
diff --git a/relptr.c b/relptr.c
@@ -0,0 +1,108 @@
+#define HEADER_IMPL
+#include "relptr.h"
+
+#include <string.h>
+#include <stdio.h>
+
+/* defining a struct is guaranteed to introduce a new type, and allows us to
+ * have a semblance of strong-ish typing for relptrs. this avoids nasty bugs
+ * where you confuse two different relptr types with the same backing type.
+ */
+typedef struct mylist_relptr {
+ int64_t v;
+} mylist_relptr_t;
+
+/* our example type, a singly linked list using relative pointers.
+ */
+struct mylist {
+ int a;
+ mylist_relptr_t next;
+};
+
+static void
+mylist_append(struct mylist *restrict list, struct mylist *restrict node);
+
+static void
+mylist_print(struct mylist const *list);
+
+/* i like defining helper functions that give me a more compact way of using
+ * the RELPTR_XXX() macros. this also makes debugging slightly easier as you
+ * can step into the helper functions and inspect the relative pointer value
+ * and the absolute pointer value.
+ */
+static inline mylist_relptr_t
+mylist_abs2rel(void const *restrict base, struct mylist const *restrict absptr)
+{
+ mylist_relptr_t res = {
+ .v = RELPTR_ABS2REL(__typeof__ (res.v), base, absptr),
+ };
+
+ return res;
+}
+
+static inline struct mylist *
+mylist_rel2abs(void const *base, struct mylist_relptr relptr)
+{
+ void *res = RELPTR_REL2ABS(struct mylist *, __typeof__ (relptr.v), base, relptr.v);
+ return res;
+}
+
+/* a basic implementation to demonstrate usage of the relative pointer helpers.
+ */
+static void
+mylist_append(struct mylist *restrict list, struct mylist *restrict node)
+{
+ if (list->next.v != RELPTR_NULL) { /* have next element in list */
+ mylist_append(mylist_rel2abs(list, list->next), node);
+ } else { /* at end of list */
+ list->next = mylist_abs2rel(list, node);
+ }
+}
+
+static void
+mylist_print(struct mylist const *list)
+{
+ printf("mylist:\n");
+
+ size_t i = 0;
+ while (list) {
+ printf("\t%zu = { %p, { a: %d, next: %p, } }\n",
+ i++, list, list->a, mylist_rel2abs(list, list->next));
+ list = mylist_rel2abs(list, list->next);
+ }
+}
+
+int
+main(void)
+{
+ struct mylist buf[4], buf2[4];
+ struct mylist *foo = buf, *bar = buf + 1, *baz = buf + 2;
+
+ foo->a = 1;
+ bar->a = 2;
+ baz->a = 3;
+
+ /* with custom types for the relptr, this step is a little opaque...
+ */
+ foo->next.v = bar->next.v = baz->next.v = RELPTR_NULL;
+
+ printf("before appending to list...\n");
+ mylist_print(foo);
+
+ mylist_append(foo, bar);
+ mylist_append(foo, baz);
+
+ printf("after appending to list...\n");
+ mylist_print(foo);
+
+ /* with absolute pointers, copying the list to a different memory
+ * location would cause the list to break (it would still point to the
+ * old memory location).
+ */
+ memcpy(buf2, buf, sizeof buf);
+
+ printf("after copying to different memory location...\n");
+ mylist_print(buf2);
+
+ return 0;
+}
diff --git a/relptr.h b/relptr.h
@@ -0,0 +1,50 @@
+#ifndef RELPTR_H
+#define RELPTR_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+/* relative pointers allow pointers that can be copied around in memory whilst
+ * still remaning valid. they allow this by forcing the user to specify a "base"
+ * against which the pointer is calculated, as opposed to using the default
+ * base of 0 (when using traditional, absolute pointers).
+ */
+
+/* we would like our relative pointers to keep using 0 as a "null" value, for
+ * ergonomics reasons. this makes initialisation of a data structure using
+ * relative pointers identical to the same structure using absolute pointers.
+ */
+#define RELPTR_NULL (0)
+
+/* in a naive implementation of relative pointers: `(uintptr_t) base + offset`,
+ * using a RELPTR_NULL of 0 would result in a "null" pointer that points to
+ * itself. this might be undesirable, as we might want to represent recursive
+ * data structures that do indeed point to themselves. so, we "mask" our
+ * relative pointer before and after conversion from an absolute pointer, to
+ * set the "null value" to some unlikely to be used value.
+ */
+#define _RELPTR_MASK(ty_relptr) ((ty_relptr) 1 << ((sizeof(ty_relptr) * 8) - 1))
+
+/* we need to convert between a pointer offset and a relative pointer.
+ */
+#define _RELPTR_ENC(ty_relptr, ptroff) \
+ ((ty_relptr) ((ptroff) ^ _RELPTR_MASK(ty_relptr)))
+
+#define _RELPTR_DEC(ty_relptr, relptr) \
+ ((ty_relptr) ((relptr) ^ _RELPTR_MASK(ty_relptr)))
+
+/* these are our main helper macros, that convert between a base and an absolute
+ * pointer to a relative pointer, and between a base and a relative pointer back
+ * to an absolute pointer.
+ */
+#define RELPTR_ABS2REL(ty_relptr, base, absptr) \
+ ((absptr) \
+ ? _RELPTR_ENC(ty_relptr, (char *) absptr - (char *) base) \
+ : RELPTR_NULL)
+
+#define RELPTR_REL2ABS(ty_absptr, ty_relptr, base, relptr) \
+ (((relptr)) \
+ ? ((ty_absptr) ((char *) base + _RELPTR_DEC(ty_relptr, relptr))) \
+ : NULL)
+
+#endif /* RELPTR_H */
