examples

commit 24dc1c3d7d56994467f93d6d9bda162f5ea3366c
parent a1208121a09689b2ea0905273ed0a5c3d759615e
Author: Henry Wilson <henry@henryandlizzy.uk>
Date:   Mon, 16 Oct 2023 11:33:44 +0100

xor-linked-list: add XOR linked list example

Diffstat:
A
src/xor-linked-list.c
 | 
88
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 88 insertions(+), 0 deletions(-)
diff --git a/src/xor-linked-list.c b/src/xor-linked-list.c
@@ -0,0 +1,88 @@
+#include <assert.h>
+#include <stdint.h>
+#include <stdio.h>
+
+struct node
+{
+	uintptr_t delta;
+	int data;
+};
+
+struct node* next_node(struct node* prev, struct node* current)
+{
+	assert(current);
+	return (struct node*)((uintptr_t)prev ^ current->delta);
+}
+
+
+void insert(struct node* p, struct node* c, struct node* n)
+{
+	if (c)
+	{
+		assert(!c->delta);
+		c->delta ^= (uintptr_t)p ^ (uintptr_t)n;
+
+	}
+	if (p)
+	{
+		p->delta ^= (uintptr_t)c ^ (uintptr_t)n;
+		assert(p->delta);
+	}
+	if (n)
+	{
+		n->delta ^= (uintptr_t)c ^ (uintptr_t)p;
+		assert(n->delta);
+	}
+}
+
+void append(struct node* p, struct node* c, struct node* n)
+{
+	assert(n);
+	assert(!n->delta);
+	assert(!next_node(p, c));
+	c->delta ^= (uintptr_t)n;
+	n->delta = (uintptr_t)c;
+}
+
+void extract(struct node* prev, struct node* get)
+{
+	assert(prev);
+	assert(get);
+
+	struct node* next = next_node(prev, get);
+	if (prev)
+		prev->delta ^= (uintptr_t)get ^ (uintptr_t)next;
+	if (next)
+		next->delta ^= (uintptr_t)get ^ (uintptr_t)prev;
+	get->delta = 0;
+}
+
+void advance(struct node** prev, struct node** current)
+{
+	struct node* p = *current;
+	*current = next_node(*prev, *current);
+	*prev = p;
+}
+
+static struct node nodes[5];
+static struct node stray = {0, 11};
+
+int main()
+{
+	for (unsigned i = 0; i < 5; ++i)
+		nodes[i].data = i;
+
+	append(NULL,    nodes+0, nodes+1);
+	append(nodes+0, nodes+1, nodes+3);
+	append(nodes+1, nodes+3, nodes+2);
+	append(nodes+3, nodes+2, nodes+4);
+	insert(nodes+2, &stray, nodes+4);
+	extract(nodes+1, nodes+3);
+
+	puts("Forward:");
+	for (struct node* current = nodes, *last = NULL; current; advance(&last, &current))
+		printf("  %p = %d\n", current, current->data);
+	puts("\nReverse:");
+	for (struct node* current = nodes+4, *last = NULL; current; advance(&last, &current))
+		printf("  %p = %d\n", current, current->data);
+}