path: root/src/tstree.c

/* 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);
}