Added ternary tree implementation and a simple test program for it

3 files changed, 147 insertions, 0 deletions

diff --git a/tern.c b/tern.c
new file mode 100644
index 0000000..c0d3abf
--- /dev/null
+++ b/tern.c
@@ -0,0 +1,98 @@
+#include "tern.h"
+#include <stddef.h>
+#include <stdlib.h>
+
+tern_node * tern_insert(tern_node * head, char * key, tern_val value)
+{
+	tern_node ** cur = &head;
+	while(*key)
+	{
+		if (*cur) {
+			while(*cur && (*cur)->el != *key)
+			{
+				if (*key < (*cur)->el) {
+					cur = &(*cur)->left;
+				} else {
+					cur = &(*cur)->right;
+				}
+			}
+		}
+		if (!*cur) {
+			*cur = malloc(sizeof(tern_node));
+			(*cur)->left = NULL;
+			(*cur)->right = NULL;
+			(*cur)->straight.next = NULL;
+			(*cur)->el = *key;
+		}
+		cur = &((*cur)->straight.next);
+		key++;
+	}
+	while(*cur && (*cur)->el)
+	{
+		cur = &(*cur)->left;
+	}
+	if (!*cur) {
+		*cur = malloc(sizeof(tern_node));
+		(*cur)->left = NULL;
+		(*cur)->right = NULL;
+		(*cur)->el = 0;
+	}
+	(*cur)->straight.value = value;
+	return head;
+}
+
+int tern_find(tern_node * head, char * key, tern_val *ret)
+{
+	tern_node * cur = head;
+	while (cur)
+	{
+		if (cur->el == *key) {
+			if (*key) {
+				cur = cur->straight.next;
+				key++;
+			} else {
+				*ret = cur->straight.value;
+				return 1;
+			}
+		} else if (*key < cur->el) {
+			cur = cur->left;
+		} else {
+			cur = cur->right;
+		}
+	}
+	return 0;
+}
+
+intptr_t tern_find_int(tern_node * head, char * key, intptr_t def)
+{
+	tern_val ret;
+	if (tern_find(head, key, &ret)) {
+		return ret.intval;
+	}
+	return def;
+}
+
+tern_node * tern_insert_int(tern_node * head, char * key, intptr_t value)
+{
+	tern_val val;
+	val.intval = value;
+	return tern_insert(head, key, val);
+}
+
+void * tern_find_ptr(tern_node * head, char * key)
+{
+	tern_val ret;
+	if (tern_find(head, key, &ret)) {
+		return ret.ptrval;
+	}
+	return NULL;
+}
+
+tern_node * tern_insert_ptr(tern_node * head, char * key, void * value)
+{
+	tern_val val;
+	val.ptrval = value;
+	return tern_insert(head, key, val);
+}
+
+
diff --git a/tern.h b/tern.h
new file mode 100644
index 0000000..0c5935a
--- /dev/null
+++ b/tern.h
@@ -0,0 +1,28 @@
+#ifndef TERN_H_
+#define TERN_H_
+
+#include <stdint.h>
+
+typedef union {
+	void     *ptrval;
+	intptr_t intval;
+} tern_val;
+
+typedef struct tern_node {
+	struct tern_node *left;
+	union {
+		struct tern_node *next;
+		tern_val         value;
+	} straight;
+	struct tern_node *right;
+	char             el;
+} tern_node;
+
+tern_node * tern_insert(tern_node * head, char * key, tern_val value);
+int tern_find(tern_node * head, char * key, tern_val *ret);
+intptr_t tern_find_int(tern_node * head, char * key, intptr_t def);
+tern_node * tern_insert_int(tern_node * head, char * key, intptr_t value);
+void * tern_find_ptr(tern_node * head, char * key);
+tern_node * tern_insert_ptr(tern_node * head, char * key, void * value);
+
+#endif //TERN_H_
diff --git a/testtern.c b/testtern.c
new file mode 100644
index 0000000..6898371
--- /dev/null
+++ b/testtern.c
@@ -0,0 +1,21 @@
+#include "tern.h"
+#include <stdio.h>
+#include <stddef.h>
+
+int main(int argc, char ** argv)
+{
+	tern_node * tree = tern_insert_ptr(NULL, "foo", "bar");
+	tree = tern_insert_ptr(tree, "foobar", "baz");
+	tree = tern_insert_ptr(tree, "goobar", "qux");
+	tree = tern_insert_int(tree, "foobarbaz", 42);
+	tree = tern_insert_int(tree, "goobarbaz", 21);
+	printf("foo: %s\n", (char *)tern_find_ptr(tree, "foo"));
+	printf("foobar: %s\n", (char *)tern_find_ptr(tree, "foobar"));
+	printf("goobar: %s\n", (char *)tern_find_ptr(tree, "goobar"));
+	printf("foob: %s\n", (char *)tern_find_ptr(tree, "foob"));
+	printf("foobarbaz: %d\n", (int)tern_find_int(tree, "foobarbaz", 0));
+	printf("goobarbaz: %d\n", (int)tern_find_int(tree, "goobarbaz", 0));
+	printf("foobarb: %d\n", (int)tern_find_int(tree, "foobarb", 0));
+	return 0;
+}
+