nserver

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs | LICENSE

commit 7b87d0d194f428ee1e9d32c5022c1ea9620a9f84
parent 6df55dc3b463b9e9017abb0461c861a6890ec195
Author: rsiddharth <s@ricketyspace.net>
Date:   Tue, 28 Jan 2020 20:21:58 -0500

nserver: Add tstree.h

Diffstat:
nserver/src/tstree.c | 257+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
nserver/src/tstree.h | 30++++++++++++++++++++++++++++++
2 files changed, 287 insertions(+), 0 deletions(-)

diff --git a/nserver/src/tstree.c b/nserver/src/tstree.c @@ -0,0 +1,257 @@ +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include <dbg.h> +#include <tstree.h> + +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 @@ -0,0 +1,30 @@ +#ifndef _TSTree_h +#define _TSTree_h + +#include <stdlib.h> +#include <darray.h> + +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