From 7b87d0d194f428ee1e9d32c5022c1ea9620a9f84 Mon Sep 17 00:00:00 2001 From: rsiddharth Date: Tue, 28 Jan 2020 20:21:58 -0500 Subject: nserver: Add tstree.h --- nserver/src/tstree.c | 257 +++++++++++++++++++++++++++++++++++++++++++++++++++ nserver/src/tstree.h | 30 ++++++ 2 files changed, 287 insertions(+) create mode 100644 nserver/src/tstree.c create mode 100644 nserver/src/tstree.h diff --git a/nserver/src/tstree.c b/nserver/src/tstree.c new file mode 100644 index 0000000..eee00b3 --- /dev/null +++ b/nserver/src/tstree.c @@ -0,0 +1,257 @@ +#include +#include +#include +#include +#include +#include + +static inline TSTree *TSTree_insert_base(TSTree *root, TSTree *node, + const char *key, size_t len, + void *value) +{ + if (node == NULL) { + node = (TSTree *) calloc(1, sizeof(TSTree)); + + if (root == NULL) { + root = node; + } + + node->splitchar = *key; + } + + if (*key < node->splitchar) { + node->low = TSTree_insert_base(root, + node->low, key, len, value); + } else if (*key == node->splitchar) { + if (len > 1) { + node->equal = TSTree_insert_base(root, node->equal, + key + 1, len -1 , value); + } else { + assert(node->value == NULL && "Duplicate insert into tst."); + node->value = value; + } + } else { + node->high = TSTree_insert_base(root, node->high, + key, len, value); + } + + return node; +} + +TSTree *TSTree_insert(TSTree *node, const char *key, size_t len, + void *value) +{ + return TSTree_insert_base(node, node, key, len, value); +} + +void *TSTree_search(TSTree *root, const char *key, size_t len) +{ + TSTree *node = root; + size_t i = 0; + + while (i < len && node) { + if (key[i] < node->splitchar) { + node = node->low; + } else if (key[i] == node->splitchar) { + i++; + if (i < len) + node = node->equal; + } else { + node = node->high; + } + } + + if (node) { + return node->value; + } else { + return NULL; + } +} + +void *TSTree_search_prefix(TSTree *root, const char *key, size_t len) +{ + if (len == 0) + return NULL; + + TSTree *node = root; + TSTree *last = NULL; + size_t i = 0; + + while (i < len && node) { + if (key[i] < node->splitchar) { + node = node->low; + } else if (key[i] == node->splitchar) { + i++; + if (i < len) { + if (node->value) + last = node; + node = node->equal; + } + } else { + node = node->high; + } + } + + node = node ? node : last; + + // traverse until we find the first value in the equal chain + // this is then the first node with this prefix + while (node && !node->value) { + node = node->equal; + } + + return node ? node->value : NULL; +} + +void TSTree_collect_keys(TSTree *node, char *key, size_t key_sz, DArray *array) +{ + if (!node) { + return; + } + + strcat(key, &node->splitchar); + + key_sz += 2; + key = (char *) realloc(key, key_sz); + + if (node->value) { + char *key_cpy = (char *) calloc(key_sz, sizeof(char)); + strcpy(key_cpy, key); + DArray_push(array, key_cpy); + } + + if (node->low) { + TSTree_collect_keys(node->low, key, key_sz, array); + } + + if (node->equal) { + TSTree_collect_keys(node->equal, key, key_sz, array); + } + + if (node->high) { + TSTree_collect_keys(node->high, key, key_sz, array); + } +} + +size_t TSTree_collect_keycat(char *key, size_t key_sz, char *c) { + // Expand key. + key_sz += 2; + key = (char *) realloc(key, key_sz); + check(key != NULL, "Unable to expand key"); + + // Concat. + key = strcat(key, c); + check(key != NULL, "key cat failed"); + + return key_sz; + error: + if (key) { + free(key); + } + return 0; +} + +DArray *TSTree_collect(TSTree *root, const char *key, size_t len) +{ + char *ckey = NULL; + + DArray *array = DArray_create(sizeof(void), 1); + check(array != NULL, "Unable to initialize DArray"); + + if (len == 0) + return array; + + TSTree *node = root; + TSTree *last = NULL; + size_t i = 0; + + size_t ckey_sz = 4; + ckey = (char *) calloc(ckey_sz, sizeof(char)); + check(ckey != NULL, "Unable to initialize ckey"); + ckey[0] = '\0'; + + while (i < len && node) { + if (key[i] < node->splitchar) { + node = node->low; + } else if (key[i] == node->splitchar) { + i++; + if (i < len) { + ckey_sz = TSTree_collect_keycat(ckey, ckey_sz, + &node->splitchar); + check(ckey_sz > 0, "keycat failed"); + + if (node->value) { + last = node; + } + node = node->equal; + } + } else { + node = node->high; + } + } + node = node ? node : last; + + while (node && !node->value) { + ckey_sz = TSTree_collect_keycat(ckey, ckey_sz, + &node->splitchar); + check(ckey_sz > 0, "keycat failed"); + + node = node->equal; + } + + if (node) { + TSTree_collect_keys(node, ckey, ckey_sz, array); + } + + // Clean up. + free(ckey); + + return array; + + error: + // Clean up. + if (array) { + DArray_destroy(array); + } + if (ckey) { + free(ckey); + } + return NULL; +} + +void TSTree_traverse(TSTree *node, TSTree_traverse_cb cb, void *data) +{ + if (!node) + return; + + if (node->low) + TSTree_traverse(node->low, cb, data); + + if (node->equal) { + TSTree_traverse(node->equal, cb, data); + } + + if (node->high) + TSTree_traverse(node->high, cb, data); + + if (node->value) + cb(node->value, data); +} + +void TSTree_destroy(TSTree *node) +{ + if (node == NULL) + return; + + if (node->low) + TSTree_destroy(node->low); + + if (node->equal) { + TSTree_destroy(node->equal); + } + + if (node->high) + TSTree_destroy(node->high); + + free(node); +} diff --git a/nserver/src/tstree.h b/nserver/src/tstree.h new file mode 100644 index 0000000..6defc39 --- /dev/null +++ b/nserver/src/tstree.h @@ -0,0 +1,30 @@ +#ifndef _TSTree_h +#define _TSTree_h + +#include +#include + +typedef struct TSTree { + char splitchar; + struct TSTree *low; + struct TSTree *equal; + struct TSTree *high; + void *value; +} TSTree; + +void *TSTree_search(TSTree *root, const char *key, size_t len); + +void *TSTree_search_prefix(TSTree *root, const char *key, size_t len); + +DArray *TSTree_collect(TSTree *root, const char *key, size_t len); + +typedef void (* TSTree_traverse_cb) (void *value, void *data); + +TSTree *TSTree_insert(TSTree *node, const char *key, size_t len, + void *value); + +void TSTree_traverse(TSTree *node, TSTree_traverse_cb cb, void *data); + +void TSTree_destroy(TSTree *root); + +#endif -- cgit v1.2.3