1
\$\begingroup\$

This code review will require somewhat a more indepth look at the code operation (at least it did for me) to understand the two word deletion areas and the node rotation and frees I'm most concerned with in this review.

This started as part of an editor project where I began working on implementint word completion. The normal type word-completion, (the user types 3 keys and up pops a list of words to choose from). There are several ways to approch this problem with Trie trees (very memory hungry), Radix/Trie compresions on the full Tri header width requirement, a flat array of struct (which can be indexed and minimize storage and provide comparable search and prefix matching for say 1000 or less words. The best choice I found was Ternary tree, which itself is somewhat of a hightly compressed Tri for word handling. There is a durth of information and examples around, so I checked the normal sites, the apple source, etc. and then extended the ternary node to hold a refcnt (reference count) for the number of times a word occurs in the buffer which is used to prevent delete of a word from the tree where other occurrences remain.

The challenge associated with the word-suggestion implementation, users delete words, so you need a way to delete words from the tree as they are deleted by the user in the edit buffer. Since you need a way of knowing if additional occurrance of the words remain, a reference count was added to each ternary node, and incremented if a word already in the buffer if added again (and decremented on delete until a refcnt of 0 is reach where the word is then removed from the tree.

This review concerns deletion of words from a ternary tree. More narrownly for this code review, concerns the two cases where the victim node, whose eqkid (equal key ID - middle) node has been reached by deleting/freeing all nodes in the tree below this node. In the parent node, both a lokid (low key ID -- left node) pointer and a *hikid (hi key ID -- right) node pointer as well requiring a small rotation of nodes (similar to RedBlack or AVL rotations to balance the nodes.

The answer to this question algorithm - How to delete a node in Ternary Tree? is simply wrong. You can only make the rotation of the lokid node in place of the victim if a hikid (victim->lokid->hikid) does not exist in the victim->lokid pointer, or vice versa if the in the victim hikid size has no lokid, you can rotate that node. You cannot simply traverse down the left side and find the highest, as there is no guarantee that several nodes down, the key holding the hikid pointer is not larger that the victim->hikid->key (given the way word inserts work in this type of tree).

You also cannot simply set the mid or eqkid pointer NULL when lokid and hikid pointers are also present on that node without leaving a node in a "neither added or deleted" state. The tree will continue to parse correctly with the leftover victim in place, but since it is no longer a terminating node, it (or some node that is the consequence of leaving it) will not be freed on a recursive free. In this case the node is just left with a NULL pointer hanging off the eqkid (mid) pointer -- which is what started this whole trip "down the rotation rabbit hole."

So what are we talking about? A basic ternary tree node can be represented as follows:

                          o
                          |-key
                          |-refcnt
              ------------+------------
              |lokid      |eqkid      |hikid
              o           o           o

in code:

/** ternary search tree node. */
typedef struct node_tst {
    char key;               /* char key for node (null for node with string) */
    unsigned refcnt;        /* refcnt tracks occurrence of word (for delete) */
    struct node_tst *lokid, /* ternary low child pointer */
                    *eqkid, /* ternary equal child pointer */
                    *hikid; /* ternary high child pointer */
} node_tst;

Where each allocated node contains a key (which corresponds to the character it represents in the search tree), or the nul-character indicating that it is a terminating node and that its eqkid pointer will be cast to char* and hold the allocated word (or pointer to word in exteral storage) which greatly simplifies prefix searching, etc., (but does add the storage for the word as a memory requirement for the tree).

Each node above is also joined to parent nodes and the children (or leaf) nodes can also have siblings. For the purpose of the code review, will be considering deletion of the victim below and will be rotating either victim->hikid to victim->lokid->hikid and replacing victim with victim low (or vice versa on the other side). That case begins like the following where all nodes from "string" have been deleted until the first lokid or hikid node is encountered in the parent:

                          o
                          |-key
                          |-refcnt
              ------------+------------
              |lokid      |eqkid      |hikid
              o           o           o
              |           | nul       |
              |           | >0        |  
          ----+----   ----+----   ----+----
          |   |   |   |   |   |   |   |   |
                          o
                       "string"

At which point, the node that contained the string and any parents without lokid/hikid would have been deleted and victim then set to the node containing both lo/hikid and its parent popped from the stack that contains the node-history for the delete. That leaves us with this setup to consider in looking at the delete and reordering code -- that is the main point of this review, e.g.:

              o
              |
              |parent
          ----+------------
          |   |           |
                          o
                          |
                          |victim
              ------------+------------
              |lokid      |eqkid      |hikid
              o           x           o
              |          NULL         |
              |                       |  
          ----+----               ----+----
          |   |   |               |   |   |

The code below consists of the ternary tree code (and its header file) and a test program for adding/deleting/prefix-searching of the tree. While you can of course provide comment on all of the code, the only code it was my intent to have reviewed was the tst_del_word() function. The others are necessary to provide a MCVE as this code, (at least for me) has to be understood in the whole to have any chance of understanding the suble issues that can occur in tst_del_word() on node rotation. (this is one that will put you to sleep a couple of times before you get through it)

My goal with the review is to see if there may not be a better way to handle each of the two if (victim->lokid && victim->hikid) cases. As mentioned, in both cases, they can simply be set to return NULL; and leave the tree dirty, and the only problem with that is the failure to delete a couple of nodes resulting in a small leak. With the rotations, there are no leaks, even using /usr/share/dict/words as the input file with all its 305089 words (inlcuding possessives and plural possessives with apostrophies. You can just take the first 1000 or so words from the file on your system if you want, or use the entire thing (which will take ~37M to load). (I'm happy to post an example file on paste-bin if you do not have a words file on your system -- just let me know)

The code is a bit long just given the subject matter. This was consciously cut down to make a MCVE. Just posting the function wouldn't have done much good.

ternary_st.c

#include "ternary_st.h"

/** max word length to store in ternary search tree, stack size */
#define WRDMAX 128
#define STKMAX (WRDMAX * 2)

/** ternary search tree node. */
typedef struct node_tst {
    char key;               /* char key for node (null for node with string) */
    unsigned refcnt;        /* refcnt tracks occurrence of word (for delete) */
    struct node_tst *lokid, /* ternary low child pointer */
                    *eqkid, /* ternary equal child pointer */
                    *hikid; /* ternary high child pointer */
} node_tst;

/** struct to use for static stack to remove nodes. */
typedef struct tst_stack {
    void *data[STKMAX];
    size_t idx;
} tst_stack;

/** stack push/pop to store node pointers to delete word from tree.
 *  on delete, store all nodes from root to leaf containing word to
 *  allow word removal and reordering of tree.
 */
static void *tst_stack_push (tst_stack *s, void *node)
{
    if (s->idx >= STKMAX)
        return NULL;

    return (s->data[(s->idx)++] = node);
}

static void *tst_stack_pop (tst_stack *s)
{
    if (!s->idx) return NULL;

    void *node = s->data[--(s->idx)];
    s->data[s->idx] = NULL;

    return node;
}

/** delete current data-node and parent, update 'node' to new parent.
 *  before delete the current refcnt is checked, if non-zero, occurrences
 *  of the word remain in buffer the node is not deleted, if refcnt zero,
 *  the node is deleted. root node updated if changed. returns NULL
 *  on success (deleted), otherwise returns the address of victim
 *  if refcnt non-zero.
 */
static void *tst_del_word (node_tst **root, node_tst *node, tst_stack *stk)
{
    node_tst *victim = node,            /* begin deletion w/victim */
             *parent = tst_stack_pop (stk); /* parent to victim */

    if (!victim->refcnt) {              /* if last occurrence */
        if (!victim->key)               /* check key is nul   */
            free (victim->eqkid);       /* free string (data) */

        /* remove unique suffix chain - parent & victim nodes
         * have no children. simple remove until the first parent
         * found with children.
         */
        while (!parent->lokid && !parent->hikid &&
               !victim->lokid && !victim->hikid) {
            parent->eqkid = NULL;
            free (victim);
            victim = parent;
            parent = tst_stack_pop (stk);
            if (!parent) {              /* last word & root node */
                free (victim);
                return (void*)(*root = NULL);
            }
        }

        /* check if victim is prefix for others (victim has lo/hi node).
         * if both lo & hi children, find highest node under low with
         * children and make parent->eqkid equal highest, free victim.
         */
        if (victim->lokid && victim->hikid) {   /* victim has both lokid/hikid */
            if (!victim->lokid->hikid) {        /* check for hikid in lo tree */
                /* rotate victim->hikid to victim->lokid->hikid, and 
                 * rotate victim->lokid to place of victim.
                 */
                victim->lokid->hikid = victim->hikid;
                if (!parent)
                    *root = victim->lokid;
                else if (victim == parent->lokid)
                    parent->lokid = victim->lokid;
                else if (victim == parent->hikid)
                    parent->hikid = victim->lokid;
                else
                    parent->eqkid = victim->lokid;
                free (victim);
                victim = NULL;
            }
            else if (!victim->hikid->lokid) {   /* check for lokid in hi tree */
                /* opposite rotation */
                victim->hikid->lokid = victim->lokid;
                if (!parent)
                    *root = victim->hikid;
                else if (victim == parent->lokid)
                    parent->lokid = victim->hikid;
                else if (victim == parent->hikid)
                    parent->hikid = victim->hikid;
                else
                    parent->eqkid = victim->hikid;
                free (victim);
                victim = NULL;
            }
            else    /* can't rotate, return, leaving victim->eqkid NULL */
                return NULL;
        }
        else if (victim->lokid) {   /* only lokid, replace victim with lokid */
            parent->eqkid = victim->lokid;
            free (victim);
            victim = NULL;
        }
        else if (victim->hikid) {   /* only hikid, replace victim with hikid */
            parent->eqkid = victim->hikid;
            free (victim);
            victim = NULL;
        }
        else {  /* victim - no children, but parent has other children */
            if (victim == parent->lokid) {      /* if parent->lokid - trim */
                parent->lokid = NULL;
                free (victim);
                victim = NULL;
            }
            else if (victim == parent->hikid) { /* if parent->hikid - trim */
                parent->hikid = NULL;
                free (victim);
                victim = NULL;
            }
            else {  /* victim was parent->eqkid, but parent->lo/hikid exists */
                parent->eqkid = NULL;               /* set eqkid NULL */
                free (victim);                      /* free current victim */
                victim = parent;                    /* set parent = victim */
                parent = tst_stack_pop (stk);       /* get new parent */
                /* if both victim hi/lokid are present */
                if (victim->lokid && victim->hikid) {
                    /* same checks and rotations as above */
                    if (!victim->lokid->hikid) {
                        victim->lokid->hikid = victim->hikid;
                        if (!parent)
                            *root = victim->lokid;
                        else if (victim == parent->lokid)
                            parent->lokid = victim->lokid;
                        else if (victim == parent->hikid)
                            parent->hikid = victim->lokid;
                        else
                            parent->eqkid = victim->lokid;
                        free (victim);
                        victim = NULL;
                    }
                    else if (!victim->hikid->lokid) {
                        victim->hikid->lokid = victim->lokid;
                        if (!parent)
                            *root = victim->hikid;
                        else if (victim == parent->lokid)
                            parent->lokid = victim->hikid;
                        else if (victim == parent->hikid)
                            parent->hikid = victim->hikid;
                        else
                            parent->eqkid = victim->hikid;
                        free (victim);
                        victim = NULL;
                    }
                    else
                        return NULL;
                }
                /* if only lokid, rewire to parent */
                else if (victim->lokid) {
                    if (parent) {   /* if parent exists, rewire */
                        if (victim == parent->lokid)
                            parent->lokid = victim->lokid;
                        else if (victim == parent->hikid)
                            parent->hikid = victim->lokid;
                        else
                            parent->eqkid = victim->lokid;
                    }
                    else            /* we are new root node, update root */
                        *root = victim->lokid;  /* make last node root */
                    free (victim);
                    victim = NULL;
                }
                /* if only hikid, rewire to parent */
                else if (victim->hikid) {
                    if (parent) {   /* if parent exists, rewire */
                        if (victim == parent->lokid)
                            parent->lokid = victim->hikid;
                        else if (victim == parent->hikid)
                            parent->hikid = victim->hikid;
                        else
                            parent->eqkid = victim->hikid;
                    }
                    else            /* we are new root node, update root */
                        *root = victim->hikid;  /* make last node root */
                    free (victim);
                    victim = NULL;
                }
            }
        }
    }
    else    /* node->refcnt non-zero */
        printf ("  %s  (refcnt: %u) not removed.\n",
                (char*)node->eqkid, node->refcnt);

    return victim;  /* return NULL on successful free, *node otherwise */
}

/** tst_insert_delete() insert or remove 's' in/from ternary search tree.
 *  insert all nodes required for 's' in tree, with allocation for storage
 *  of 's' at eqkid node of leaf. increment refcnt, if 's' already exists
 *  (to be used for del). 0 for 'del' inserts, 1 for 'del' deletes. returns
 *  address of 's' in tree on successful insert (or on delete if refcnt non-
 *  zero on delete), NULL on allocation failure on insert, or on successful
 *  removal of 's' from tree.
 */
void *tst_insert_delete (node_tst **root, const char *s, const int del)
{
    int diff;
    const char *p = s;
    tst_stack stk = { .data = {NULL}, .idx = 0 };
    node_tst *curr, **pcurr;

    if (!root || !s) return NULL;           /* validate parameters */
    if (strlen (s) + 1 > STKMAX / 2)        /* limit length to 1/2 STKMAX */
        return NULL;                        /* 128 char word lenght is plenty */

    pcurr = root;                           /* start at root */
    while ((curr = *pcurr)) {               /* iterate to insertion node  */
        diff = *p - curr->key;              /* get ASCII diff for >, <, = */
        if (diff == 0) {                    /* if char equal to node->key */
            if (*p++ == 0) {                /* check if word is duplicate */
                if (del) {                  /* delete instead of insert   */
                    (curr->refcnt)--;       /* decrement reference count  */
                    /* chk refcnt, del 's', return NULL on successful del */
                    return tst_del_word (root, curr, &stk);
                }
                else
                    curr->refcnt++;         /* increment refcnt if word exists */
                return (void *)curr->eqkid; /* pointer to word / NULL on del  */
            }
            pcurr = &(curr->eqkid);         /* get next eqkid pointer address */
        }
        else if (diff < 0) {                /* if char less than node->key */
            pcurr = &(curr->lokid);         /* get next lokid pointer address */
        }
        else {                              /* if char greater than node->key */
            pcurr = &(curr->hikid);         /* get next hikid pointer address */
        }
        if (del)
            tst_stack_push (&stk, curr);    /* push node on stack for del */
    }

    /* if not duplicate, insert remaining chars into tree rooted at curr */
    for (;;) {
        /* allocate memory for node, and fill. use calloc (or include
         * string.h and initialize w/memset) to avoid valgrind warning
         * "Conditional jump or move depends on uninitialised value(s)"
         */
        if (!(*pcurr = calloc (1, sizeof **pcurr))) {
            fprintf (stderr, "error: tst_insert(), memory exhausted.\n");
            return NULL;
        }
        curr = *pcurr;
        curr->key = *p;
        curr->refcnt = 1;
        curr->lokid = curr->hikid = curr->eqkid = NULL;

        if (!*root)         /* handle assignment to root if no root */
            *root = *pcurr;

        /* Place nodes until end of the string, at end of stign allocate
         * space for data, copy data as final eqkid, and return.
         */
        if (*p++ == 0) {
            const char *eqdata = strdup (s);
            if (!eqdata)
                return NULL;
            curr->eqkid = (node_tst *)eqdata;
            return (void*)eqdata;
        }
        pcurr = &(curr->eqkid);
    }
}

/** tst_search(), non-recursive find of a string internary tree.
 *  returns pointer to 's' on success, NULL otherwise.
 */
void *tst_search (const node_tst *p, const char *s)
{
    const node_tst *curr = p;

    while (curr) {                          /* loop over each char in 's' */
        int diff = *s - curr->key;          /* calculate the difference */
        if (diff == 0) {                    /* handle the equal case */
            if (*s == 0)    /* if *s = curr->key = nul-char, 's' found */
                return (void *)curr->eqkid; /* return pointer to 's' */
            s++;
            curr = curr->eqkid;
        }
        else if (diff < 0)                  /* handle the less than case */
            curr = curr->lokid;
        else
            curr = curr->hikid;             /* handle the greater than case */
    }
    return NULL;
}

/** fill ptr array 'a' with strings matching prefix at node 'p'.
 *  the 'a' array will hold pointers to stored strings with prefix
 *  matching the string passed to tst_matching, ending in 'c', the
 *  nchr'th char in in each matched string.
 */
void tst_suggest (const node_tst *p, const char c, const size_t nchr,
                    char **a, int *n, const int max)
{
    if (!p || *n == max)
        return;
    tst_suggest (p->lokid, c, nchr, a, n, max);
    if (p->key)
        tst_suggest (p->eqkid, c, nchr, a, n, max);
    else if (*(((char*)p->eqkid) + nchr - 1) == c)
            a[(*n)++] = (char *)p->eqkid;
    tst_suggest (p->hikid, c, nchr, a, n, max);
}

/** tst_matching fills 'a' with words prefixed with 's'.
 *  once the node containing the first prefix matching 's' is found
 *  tst_suggest is called to travers the ternary_tree beginning
 *  at the node filling 'a' with pointers to all words that contain
 *  the prefix upto 'max' words updating 'n' with the number of word
 *  in 'a'. a pointer to the first node is returned on success
 *  NULL otherwise.
 */
void *tst_matching (const node_tst *root, const char *s,
                    char **a, int *n, const int max)
{
    const node_tst *curr = root;
    const char *start = s;

    if (!*s) return NULL;

    for (; *start; start++) {}              /* get length of s */
    const size_t nchr = start - s;

    start = s;
    *n = 0;

    /* Loop while we haven't hit a NULL node or returned */
    while (curr) {

        int diff = *s - curr->key;          /* calculate the difference */
        if (diff == 0) {                    /* handle the equal case */

            if ((size_t)(s - start) == nchr - 1) {
                tst_suggest (curr, curr->key, nchr, a, n, max);
                return (void*)curr;
            }
            if (*s == 0)
                return (void *)curr->eqkid;

            s++;
            curr = curr->eqkid;
        }
        else if (diff < 0)                  /* handle the less than case */
            curr = curr->lokid;
        else
            curr = curr->hikid;             /* handle the greater than case */
    }
    return NULL;
}

/** print_word(), function for tst_traverse_fn, print each word. */
void print_word (const void *node, void *data)
{
    printf ("%s\n", (char *)((node_tst *)node)->eqkid);
    if (data) {}
}

/** tst_traverse_fn(), traverse tree calling 'fn' on each word.
 *  prototype for 'fn' is void fn(const char *).
 */
void tst_traverse_fn (const node_tst *p, void(fn)(const void *, void *), void *data)
{
    if (!p)
        return;
    tst_traverse_fn (p->lokid, fn, data);
    if (p->key)
        tst_traverse_fn (p->eqkid, fn, data);
    else
        fn (p, data);
    tst_traverse_fn (p->hikid, fn, data);
}

/** free the ternary search tree rooted at p, data storage internal. */
void tst_free_all (node_tst *p)
{
    if (p) {
        tst_free_all (p->lokid);
        if (p->key)
            tst_free_all (p->eqkid);
        tst_free_all (p->hikid);
        if (!p->key)
            free (p->eqkid);
        free (p);
    }
}

/** access functions tst_get_key(), tst_get_refcnt, & tst_get_string().
 *  provide access to struct members through opague pointers availale
 *  to program.
 */
char tst_get_key (const node_tst *node)
{
    return node->key;
}

unsigned tst_get_refcnt (const node_tst *node)
{
    return node->refcnt;
}

char *tst_get_string (const node_tst *node)
{
    if (node && !node->key)
        return (char*)node->eqkid;

    return NULL;
}

Out of ternary_st.c above I am most interested in your thoughts over the following two areas of code. I feel there has to be a better way to handle these two sections. I'm happy with how they work, but I never assume the code I write can't be done 10x better somehow:

    /* check if victim is prefix for others (victim has lo/hi node).
     * if both lo & hi children, find highest node under low with
     * children and make parent->eqkid equal highest, free victim.
     */
    if (victim->lokid && victim->hikid) {   /* victim has both lokid/hikid */
        if (!victim->lokid->hikid) {        /* check for hikid in lo tree */
            /* rotate victim->hikid to victim->lokid->hikid, and 
             * rotate victim->lokid to place of victim.
             */
            victim->lokid->hikid = victim->hikid;
            if (!parent)
                *root = victim->lokid;
            else if (victim == parent->lokid)
                parent->lokid = victim->lokid;
            else if (victim == parent->hikid)
                parent->hikid = victim->lokid;
            else
                parent->eqkid = victim->lokid;
            free (victim);
            victim = NULL;
        }
        else if (!victim->hikid->lokid) {   /* check for lokid in hi tree */
            /* opposite rotation */
            victim->hikid->lokid = victim->lokid;
            if (!parent)
                *root = victim->hikid;
            else if (victim == parent->lokid)
                parent->lokid = victim->hikid;
            else if (victim == parent->hikid)
                parent->hikid = victim->hikid;
            else
                parent->eqkid = victim->hikid;
            free (victim);
            victim = NULL;
        }
        else    /* can't rotate, return, leaving victim->eqkid NULL */
            return NULL;
    }

and this section, which is basically the same, after finding a parent with lo/hikid and then making that parent the victim and popping a new parent from the stack.

        else {  /* victim was parent->eqkid, but parent->lo/hikid exists */
            parent->eqkid = NULL;               /* set eqkid NULL */
            free (victim);                      /* free current victim */
            victim = parent;                    /* set parent = victim */
            parent = tst_stack_pop (stk);       /* get new parent */
            /* if both victim hi/lokid are present */
            if (victim->lokid && victim->hikid) {
                /* same checks and rotations as above */
                if (!victim->lokid->hikid) {
                    victim->lokid->hikid = victim->hikid;
                    if (!parent)
                        *root = victim->lokid;
                    else if (victim == parent->lokid)
                        parent->lokid = victim->lokid;
                    else if (victim == parent->hikid)
                        parent->hikid = victim->lokid;
                    else
                        parent->eqkid = victim->lokid;
                    free (victim);
                    victim = NULL;
                }
                else if (!victim->hikid->lokid) {
                    victim->hikid->lokid = victim->lokid;
                    if (!parent)
                        *root = victim->hikid;
                    else if (victim == parent->lokid)
                        parent->lokid = victim->hikid;
                    else if (victim == parent->hikid)
                        parent->hikid = victim->hikid;
                    else
                        parent->eqkid = victim->hikid;
                    free (victim);
                    victim = NULL;
                }
                else
                    return NULL;
            }
        <snip>

ternary_st.h

#ifndef _tst_search_tree_h_
#define _tst_search_tree_h_  1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* forward-reference ternary search tree node and typedef */
struct node_tst;
typedef struct node_tst node_tst;


/** tst_insert_delete() insert or remove 's' in/from ternary search tree.
 *  insert all nodes required for 's' in tree, with allocation for storage
 *  of 's' at eqkid node of leaf. increment refcnt, if 's' already exists
 *  (to be used for del). 0 for 'del' inserts, 1 for 'del' deletes. returns
 *  address of 's' in tree on successful insert (or on delete if refcnt non-
 *  zero on delete), NULL on allocation failure on insert, or on successful
 *  removal of 's' from tree.
 */
void *tst_insert_delete (node_tst **root, const char *s, const int del);

/** tst_search(), non-recursive find of a string internary tree.
 *  returns pointer to 's' on success, NULL otherwise.
 */
void *tst_search (const node_tst *p, const char *s);

/** fill ptr array 'a' with strings matching prefix at node 'p'.
 *  the 'a' array will hold pointers to stored strings with prefix
 *  matching the string passed to tst_matching, ending in 'c', the
 *  nchr'th char in in each matched string.
 */
void tst_suggest (const node_tst *p, const char c, const size_t nchr,
                    char **a, int *n, const int max);

/** tst_matching fills 'a' with words prefixed with 's'.
 *  once the node containing the first prefix matching 's' is found
 *  tst_suggest is called to travers the ternary_tree beginning
 *  at the node filling 'a' with pointers to all words that contain
 *  the prefix upto 'max' words updating 'n' with the number of word
 *  in 'a'. a pointer to the first node is returned on success
 *  NULL otherwise.
 */
void *tst_matching (const node_tst *root, const char *s,
                    char **a, int *n, const int max);

/** print_word(), function for tst_traverse_fn, print each word. */
void print_word (const void *node, void *data);

/** tst_traverse_fn(), traverse tree calling 'fn' on each word */
void tst_traverse_fn (const node_tst *p, void(fn)(const void *, void *), void *data);
// void tst_traverse_fn (const node_tst *p, void(fn)(const void *, void *));

/** free the ternary search tree rooted at p, data storage internal. */
void tst_free_all (node_tst *p);

/** access functions tst_get_key(), tst_get_refcnt, & tst_get_string().
 *  provide access to struct members through opague pointers availale
 *  to program.
 */
char tst_get_key (const node_tst *node);
unsigned tst_get_refcnt (const node_tst *node);
char *tst_get_string (const node_tst *node);

#endif

Short driver program that takes the file to read (one-word-per-line) from as the first argument and gives time required for each operation. Printing the tree to the screen only works for trees of 100 or less words:

tst_test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "ternary_st.h"

/** constants insert, delete, max word(s) & stack nodes */
enum { INS, DEL, WRDMAX = 256, STKMAX = 512, LMAX = 1000 };

/* timing helper function */
double tvgetf (void)
{
    struct timespec ts;
    double sec;

    clock_gettime(CLOCK_REALTIME,&ts);
    sec = ts.tv_nsec;
    sec /= 1e9;
    sec += ts.tv_sec;

    return sec;
}

void rmcrlf (char *s) {
    size_t len = strlen (s);
    if (len && s[len - 1] == '\n')
        s[--len] = 0;
}

int main (int argc, char **argv) {

    char word[WRDMAX] = "",
        *sgl[LMAX] = {NULL};
    node_tst *root = NULL, *res = NULL;
    int rtn = 0, idx = 0, sidx = 0;
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;
    double t1, t2;

    if (!fp) {  /* validate file open for reading */
        fprintf (stderr, "error: file open failed '%s'.\n", argv[1]);
        return 1;
    }

    t1 = tvgetf();
    while ((rtn = fscanf (fp, "%s", word)) != EOF) {
        if (!tst_insert_delete (&root, word, INS)) {
            fprintf (stderr, "error: memory exhausted, tst_insert.\n");
            return 1;
        }
        idx++;
    }
    t2 = tvgetf();
    if (fp != stdin) fclose (fp);     /* close file if not stdin */
    printf ("ternary_tree, loaded %d words in %.6f sec\n\n", idx, t2-t1);

    for (;;) {
        printf ("\n p  print words in tree\n"
                " a  add word to the tree\n"
                " f  find word in tree\n"
                " s  find words matching prefix\n"
                " d  del word from the tree\n"
                " q  quit, freeing all data\n\n"
                "choice: ");
        fgets (word, sizeof word, stdin);

        switch (*word) {
            case 'p' :  printf ("\nprinting all words in tree.\n\n");
                        if (idx > 100) {
                            fprintf (stderr, "no. of words exceeds 100 (%d), skipped.\n", idx);
                            break;
                        }
                        else
                            tst_traverse_fn (root, print_word, NULL);
                        break;
            case 'a' :  printf ("enter word to add: ");
                        if (!fgets (word, sizeof word, stdin)) {
                            fprintf (stderr, "error: insufficient input.\n");
                            break;
                        }
                        rmcrlf (word);
                        t1 = tvgetf();
                        res = tst_insert_delete (&root, word, INS);
                        t2 = tvgetf();
                        if (res) {
                            idx++;
                            printf ("  %s - inserted in %.6f sec. (%d words in tree)\n",
                                    (char*)res, t2 - t1, idx);
                        }
                        else
                            printf ("  %s - already exists in list.\n", (char*)res);
                        break;
            case 'f' :  printf ("find word in tree: ");
                        if (!fgets (word, sizeof word, stdin)) {
                            fprintf (stderr, "error: insufficient input.\n");
                            break;
                        }
                        rmcrlf (word);
                        t1 = tvgetf();
                        res = tst_search (root, word);
                        t2 = tvgetf();
                        if (res)
                            printf ("  found %s in %.6f sec.\n", (char*)res, t2-t1);
                        else
                            printf ("  %s no found.\n", word);
                        break;
            case 's' :  printf ("find words matching prefix (3 chars): ");
                        if (!fgets (word, sizeof word, stdin)) {
                            fprintf (stderr, "error: insufficient input.\n");
                            break;
                        }
                        rmcrlf (word);
                        t1 = tvgetf();
                        res = tst_matching (root, word, sgl, &sidx, LMAX);
                        t2 = tvgetf();
                        if (res) {
                            printf ("  %s - searched prefix in %.6f sec\n\n", word, t2 - t1);
                            for (int i = 0; i < sidx; i++)
                                printf ("suggest[%d] : %s\n", i, sgl[i]);
                        }
                        else
                            printf ("  %s - not found\n", word);
                        break;
            case 'd' :  printf ("enter word to del: ");
                        if (!fgets (word, sizeof word, stdin)) {
                            fprintf (stderr, "error: insufficient input.\n");
                            break;
                        }
                        rmcrlf (word);
                        printf ("  deleting %s\n", word);
                        t1 = tvgetf();
                        res = tst_insert_delete (&root, word, DEL);
                        t2 = tvgetf();
                        if (res)
                            printf ("  delete failed.\n");
                        else {
                            printf ("  deleted %s in %.6f sec\n", word, t2 - t1);
                            idx--;
                        }
                        break;
            case 'q' :  tst_free_all (root);
                        return 0;
                        break;
            default  :  printf ("error: invalid selection.\n");
                        break;
        }
    }

    return 0;
}

If anyone thinks it useful, I have another set of these headers that contain additional debug information and another driver that is basically a torture test that reads all words into the tree, saves an array of the words, shuffles the word array and then sequentially deletes each word from the tree while simultaneously executing a find on all words that remain after each deletion to validate all are still reachable and there are no pointer problems. Let me know if that is wanted as an addition.

\$\endgroup\$
  • \$\begingroup\$ Consider a user's view of this code will not see the the long discussion, but may only see the *.h file. "tst_insert_delete() insert or remove 's' in/from ternary search tree." mis-leads. Code never inserts s in the tree. It inserts a copy of the string pointed to by s in the tree. \$\endgroup\$ – chux Sep 17 '17 at 3:39
  • \$\begingroup\$ Yes, that is just a description, unfortunately, left-over from the version that uses external storage for the strings. Which I see application for, but it has no application to an edit buffer where the location of the words change. (you critique of the description is entirely correct here). The access times for data in this type tree are excellent, but try searching for good information (other than theoretical timings, etc..) for a good removal and rotating procedure :) \$\endgroup\$ – David C. Rankin Sep 17 '17 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.