diff options
Diffstat (limited to 'src/tstree.c')
| -rw-r--r-- | src/tstree.c | 256 |
1 files changed, 256 insertions, 0 deletions
diff --git a/src/tstree.c b/src/tstree.c new file mode 100644 index 0000000..92c7b5e --- /dev/null +++ b/src/tstree.c @@ -0,0 +1,256 @@ +/* SPDX-License-Identifier: BSD-3-Clause */ +/* + * Copyright © 2010, Zed A. Shaw. + * Copyright © 2020 rsiddharth <s@ricketyspace.net> + */ + +#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->value; + } + node = node->equal; + } + } else { + node = node->high; + } + } + + return last; +} + +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); +} |