From eb823898c385bb3a58c9641a988e6260a7d45176 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Hugo=20H=C3=B6rnquist?= <hugo@lysator.liu.se>
Date: Tue, 22 Jan 2019 11:41:52 +0100
Subject: Add trie data structure.

---
 trie.c   |   1 +
 trie.h   |  49 ++++++++++++++++++++++++++++
 trie.inc | 110 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 160 insertions(+)
 create mode 100644 trie.c
 create mode 100644 trie.h
 create mode 100644 trie.inc

diff --git a/trie.c b/trie.c
new file mode 100644
index 00000000..aa83f622
--- /dev/null
+++ b/trie.c
@@ -0,0 +1 @@
+#include "trie.h"
diff --git a/trie.h b/trie.h
new file mode 100644
index 00000000..9d8b1ec0
--- /dev/null
+++ b/trie.h
@@ -0,0 +1,49 @@
+#ifndef TRIE_H
+#define TRIE_H
+
+#include "macro.h"
+
+#define TRIE(T) TP(trie__, T)
+#define TRIE_NODE(T) TP(trie_node__, T)
+
+#define TRIE_INIT(T)      CONSTRUCTOR_GEN(trie, T, 0)
+#define TRIE_NODE_INIT(T) CONSTRUCTOR_GEN(trie_node, T, 0)
+
+#define TRIE_FREE(T) TP(trie_free__, T)
+#define TRIE_NODE_FREE(T) TP(trie_node_free__, T)
+
+#define TRIE_PUT(T) TP(trie_put__, T)
+#define TRIE_GET(T) TP(trie_get__, T)
+
+#endif /* TRIE_H */
+#ifdef TYPE
+
+typedef struct TRIE_NODE(TYPE) {
+	char c;
+	TYPE* value;
+	struct TRIE_NODE(TYPE)* next;
+	/* child == NULL means leaf? */
+	struct TRIE_NODE(TYPE)* child;
+} TRIE_NODE(TYPE);
+
+typedef struct {
+	TRIE_NODE(TYPE)* root;
+} TRIE(TYPE);
+
+
+int CONSTRUCTOR_DECL ( TRIE(TYPE) );
+
+int CONSTRUCTOR_DECL (TRIE_NODE(TYPE), char c);
+
+int CONSTRUCTOR_DECL (TRIE_NODE(TYPE), 
+	  char c, TRIE_NODE(TYPE)* next, TRIE_NODE(TYPE)* child );
+
+int TRIE_PUT(TYPE) ( TRIE(TYPE)* trie, char* key, TYPE* val );
+
+TYPE* TRIE_GET(TYPE) ( TRIE(TYPE)* trie, char* key );
+
+int TRIE_NODE_FREE(TYPE) ( TRIE_NODE(TYPE)* node );
+
+int TRIE_FREE(TYPE) ( TRIE(TYPE)* trie );
+
+#endif /* TYPE */
diff --git a/trie.inc b/trie.inc
new file mode 100644
index 00000000..96765c2f
--- /dev/null
+++ b/trie.inc
@@ -0,0 +1,110 @@
+#ifndef TYPE
+#error "Set TYPE before including this file"
+#else
+
+#include "err.h"
+
+int TRIE_INIT(TYPE) ( TRIE(TYPE)* trie ) {
+	NEW(TRIE_NODE(TYPE), t, '\0');
+	trie->root = t;
+	return 0;
+}
+
+int CONSTRUCTOR_DECL (TRIE_NODE(TYPE), char c) {
+	this->c = c;
+	this->next = NULL;
+	this->child = NULL;
+	return 0;
+}
+
+// int TRIE_NODE_INIT(TYPE) (
+// 	TRIE_NODE(TYPE)* node,
+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;
+}
+
+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) free (node->value);
+	if (node->next  != NULL) TRIE_NODE_FREE(TYPE)(node->next);
+	if (node->child != NULL) TRIE_NODE_FREE(TYPE)(node->child);
+	return 0;
+}
+
+int TRIE_FREE(TYPE) ( TRIE(TYPE)* trie ) {
+	return TRIE_NODE_FREE(TYPE)(trie->root);
+}
+
+#endif /* TYPE */
-- 
cgit v1.2.3