From 7c7dd1a8b18b101e093df5eff6247acd94f25422 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Hugo=20H=C3=B6rnquist?= <hugo@lysator.liu.se>
Date: Sun, 3 Feb 2019 00:00:05 +0100
Subject: Rework makefile, made .inc into .inc.h.

---
 trie.inc.h | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)
 create mode 100644 trie.inc.h

(limited to 'trie.inc.h')

diff --git a/trie.inc.h b/trie.inc.h
new file mode 100644
index 00000000..50aeff29
--- /dev/null
+++ b/trie.inc.h
@@ -0,0 +1,113 @@
+#ifndef TYPE
+#error "Set TYPE before including this file"
+#else
+
+#include "err.h"
+
+int CONSTRUCTOR_DECL ( TRIE(TYPE) ) {
+	NEW(TRIE_NODE(TYPE), t, '\0');
+	this->root = t;
+	return 0;
+}
+
+int CONSTRUCTOR_DECL (TRIE_NODE(TYPE), char c) {
+	this->c = c;
+	this->value = NULL;
+	this->next  = NULL;
+	this->child = NULL;
+	return 0;
+}
+
+int CONSTRUCTOR_DECL (TRIE_NODE(TYPE),
+	char c,
+	TRIE_NODE(TYPE)* next,
+	TRIE_NODE(TYPE)* child )
+{
+	this->c = c;
+	this->next = next;
+	this->child = child;
+	return 0;
+}
+
+int TRIE_PUT(TYPE) ( TRIE(TYPE)* trie, char* key, TYPE* val ) {
+	TRIE_NODE(TYPE) *cur, *last;
+
+	last = trie->root;
+	cur = last->child;
+
+	char* subkey = key;
+	// --------------------------------------------------
+
+	while (1) {
+		if (cur == NULL) {
+			/* Build direct LL for remaining subkey */
+			for (char* c = subkey; c[0] != '\0'; c++) {
+				NEW(TRIE_NODE(TYPE), t, *c);
+				last->child = t;
+				last = t;
+			}
+			last->value = val;
+			return 0;
+		} else if (cur->c == subkey[0]) {
+			/* This node belongs to the key,
+			 * Decend further */
+			last = cur;
+			cur = cur->child;
+			subkey++;
+		} else if (subkey[0] == '\0') {
+			/* Key finished */
+			last->value = val;
+			return 0;
+		} else if (cur->next != NULL) {
+			/* This node was not part of the set, but it's sibling might */
+			cur = cur->next;
+			/* `last` not set since we aren't moving down */ 
+		} else {
+			/* No node on this level was part of the set, create a new
+			 * sibling and follow down that parse */
+			NEW(TRIE_NODE(TYPE), t, *subkey);
+			cur->next = t;
+			last = cur;
+			cur = t;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * TODO what happens when I give an invalid key?
+ */
+TYPE* TRIE_GET(TYPE) ( TRIE(TYPE)* trie, char* key ) {
+	TRIE_NODE(TYPE)* n = trie->root->child;
+	char* subkey = key;
+
+	while (n != NULL) {
+		if (subkey[1] == '\0') {
+			return n->value;
+		} else if (subkey[0] == n->c) {
+			n = n->child;
+			subkey++;
+		} else {
+			n = n->next;
+		}
+	}
+
+	ERR("Position not found");
+	return 0;
+}
+
+int TRIE_NODE_FREE(TYPE) ( TRIE_NODE(TYPE)* node ) {
+	if (node == NULL) return 0;
+	if (node->value != NULL) FFREE(TYPE, node->value);
+	if (node->next  != NULL) TRIE_NODE_FREE(TYPE)(node->next);
+	if (node->child != NULL) TRIE_NODE_FREE(TYPE)(node->child);
+	free (node);
+	return 0;
+}
+
+int TRIE_FREE(TYPE) ( TRIE(TYPE)* trie ) {
+	return TRIE_NODE_FREE(TYPE)(trie->root);
+}
+
+#endif /* TYPE */
-- 
cgit v1.2.3