Added basic queue implementation

3 files changed, 85 insertions, 2 deletions

diff --git a/inc/queue.h b/inc/queue.h
new file mode 100644
index 0000000..5a704b4
--- /dev/null
+++ b/inc/queue.h
@@ -0,0 +1,24 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef SHARING_QUEUE_H
+#define SHARING_QUEUE_H
+
+#include <stddef.h>
+
+struct queue_node {
+	void *data;
+	struct queue_node *next;
+};
+
+struct queue {
+	struct queue_node *head;
+	struct queue_node *tail;
+};
+
+struct queue *queue_new(void);
+void queue_free(struct queue *queue);
+void queue_push(struct queue *queue, void *data);
+void *queue_pop(struct queue *queue);
+
+#endif
diff --git a/inc/term.h b/inc/term.h
index 0dd472f..3bc94eb 100644
--- a/inc/term.h
+++ b/inc/term.h
@@ -6,12 +6,15 @@
 
 #include <stddef.h>
 
+#include <queue.h>
+
 typedef enum { INV, ABS, APP, VAR } term_type_t;
 
 struct term {
 	term_type_t type;
-	size_t refs;
-	size_t depth;
+	struct term *canonic;
+	char building;
+	struct queue *queue;
 	union {
 		struct {
 			struct term *term;
diff --git a/src/queue.c b/src/queue.c
new file mode 100644
index 0000000..5f30717
--- /dev/null
+++ b/src/queue.c
@@ -0,0 +1,56 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <stdlib.h>
+
+#include <queue.h>
+#include <log.h>
+
+struct queue *queue_new(void)
+{
+	struct queue *queue = malloc(sizeof(*queue));
+	if (!queue)
+		fatal("out of memory!\n");
+	queue->head = 0;
+	queue->tail = 0;
+	return queue;
+}
+
+void queue_free(struct queue *queue)
+{
+	while (queue->head) {
+		struct queue_node *node = queue->head;
+		queue->head = node->next;
+		free(node);
+	}
+	free(queue);
+}
+
+void queue_push(struct queue *queue, void *data)
+{
+	struct queue_node *node = malloc(sizeof(*node));
+	if (!node)
+		fatal("out of memory!\n");
+	node->data = data;
+	node->next = 0;
+	if (queue->tail) {
+		queue->tail->next = node;
+		queue->tail = node;
+	} else {
+		queue->head = node;
+		queue->tail = node;
+	}
+}
+
+void *queue_pop(struct queue *queue)
+{
+	if (!queue->head)
+		return 0;
+	struct queue_node *node = queue->head;
+	queue->head = node->next;
+	if (!queue->head)
+		queue->tail = 0;
+	void *data = node->data;
+	free(node);
+	return data;
+}