From 5d758f6938dc3c73e2c858255748f781aac17010 Mon Sep 17 00:00:00 2001 From: Mike Pavone Date: Tue, 9 Jul 2013 20:51:42 -0700 Subject: Added ternary tree implementation and a simple test program for it --- tern.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 98 insertions(+) create mode 100644 tern.c (limited to 'tern.c') 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 +#include + +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); +} + + -- cgit v1.2.3 From 122bf9de037f578cc4862b1dc775b6589d56057d Mon Sep 17 00:00:00 2001 From: Mike Pavone Date: Wed, 10 Jul 2013 22:48:17 -0700 Subject: Read key bindings from config file --- tern.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'tern.c') diff --git a/tern.c b/tern.c index c0d3abf..7e60a22 100644 --- a/tern.c +++ b/tern.c @@ -63,6 +63,23 @@ int tern_find(tern_node * head, char * key, tern_val *ret) return 0; } +tern_node * tern_find_prefix(tern_node * head, char * key) +{ + tern_node * cur = head; + while (cur && *key) + { + if (cur->el == *key) { + cur = cur->straight.next; + key++; + } else if (*key < cur->el) { + cur = cur->left; + } else { + cur = cur->right; + } + } + return cur; +} + intptr_t tern_find_int(tern_node * head, char * key, intptr_t def) { tern_val ret; -- cgit v1.2.3 From 2c302a78d201d9b594774cec505d14c22e03662c Mon Sep 17 00:00:00 2001 From: Mike Pavone Date: Tue, 10 Sep 2013 23:31:08 -0700 Subject: Added copyright notice to source files and added GPL license text in COPYING --- tern.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'tern.c') diff --git a/tern.c b/tern.c index 7e60a22..96a0985 100644 --- a/tern.c +++ b/tern.c @@ -1,3 +1,8 @@ +/* + Copyright 2013 Michael Pavone + This file is part of BlastEm. + BlastEm is free software distributed under the terms of the GNU General Public License version 3 or greater. See COPYING for full license text. +*/ #include "tern.h" #include #include -- cgit v1.2.3