Trie implementation for a data structure library in C

I'm implementing a trie structure for a library, as an exercise in data structures.

Details

The tree structure is represented as a doubly chained tree. A struct trie represents a node of the trie, and contains the following:

• key is the character represented by the node. Since keys are expected to be \0-terminated strings, a node with a key value of \0 is a leaf node.

• sibling is the next sibling of the node.

• child is the first child of the node.

• val at a leaf node is the value associated with the key string that terminates at that node. This is expected to be NULL on internal nodes.

The following methods are implemented:

-
trie_init initialises and returns a trie.

-
trie_insert inserts value val into trie t with key k.

-
trie_finsert makes a copy of the first size bytes after val to some new_val, then adds new_val to trie t with key k. If there is already a value associated with k, a destructor function f is called on the old value before it is overwritten.

-
trie_remove removes the value associated with key k from trie t.

-
trie_fremove calls f on the value associated with key k in trie t before removing it.

-
trie_seek searches trie t for a value associated with key k. Returns it if it is found, returns NULL otherwise.

-
trie_match searches trie t for all values associated with keys that have prefix k, and appends them to a vector v in alphabetic order (for instance, doing trie_match(t, “te”, v) on the trie in the example as it appears just before it is destroyed will add ”TWO” and ”EIGHT” to v, in that order.)

-
trie_list is just shorthand for trie_match(t, “”, v) and appends all the elements in t to v.

-
trie_dump prints the structure of the trie.

-
trie_dumps prints the structure of the trie, and also prints the values interpreting them as pointers to \0-terminated strings.

-
trie_free destroys a trie.

-
trie_ffree calls f

I have some observations that may help you improve your program.

Initialize all members

The trie_insert function does not initialize the child pointer. This is an error because later functions test that member for NULL and if the value hadn't been explicitly set, there's no reason to believe that uninitialized members will have any particular value. I'd recommend creating a function that does this, such as trie_new(char key, struct trie *sibling); That makes a few of the other suggestions below easier to implement as well.

Here's how it might be implemented with trie_init rewritten to use it:

struct trie* trie_new(char k, struct trie *sibling) {
    struct trie *t = malloc(sizeof(struct trie));
    if (!t) {
        fprintf(stderr, "error: trie_init: out of memory.\n");
        return NULL;
    }
    t->key = k;
    t->val = t->child = NULL;
    t->sibling = sibling;
    return t;
}

struct trie* trie_init(void) {
    return trie_new('\0', NULL);
}

Cleanly separate interface from implementation

The names of the functions such as trie_insert and internal_trie_insert suggest a nice neat separation between interface and implementation, but all of the function prototypes are in the same trie.h header file. Instead, it would probably be better to only put the public functions in the header file. Then, within the .c file, order the functions such that additional functions are not needed and make them static to prevent calling them externally.

Consider an alternative interface

While I can understand how passing a free function into the trie might be useful, as for using a custom allocator, I'd suggest that it might be better to pass it in once via the trie_init function rather than various other places in the interface. This would mean that only similarly allocated val types could be accomodated, but I would guess that use of heterogenous collections of val types would be unusual in actual practice (and not completely correctly supported in the current code). In that same vein, it seems unlikely to me that both trie_dump and trie_dumps are useful.

Handle out of memory conditions consistently

Usually, this would be the place I point out that malloc could fail and that you should check the return value for NULL, but I'm pleased instead to note that you've done it well and consistently. I don't believe that the code will get too cluttered if the code is structured well.

Provide complete code for review

This isn't really so much a criticism as an observation. Because the vector code was excised before posting for review, the remaining functions that use it have probably lost any real meaning or use. For that reason, I'd suggest that either suppling the missing code or completely excising the parts that rely on it would both be reasonable ways to handle this. Although you've explained the rationale in the question (and it's also entirely reasonable) it means that those parts of the code can't really be meaningfully reviewed.

Omit unused function parameters

Since argc and argv are unused within main, they can simply be omitted.

Omit return 0; in main

Modern C and C++ compilers will automatically supply the equivalent of return 0; at the end of main, so it's not necessary to write it.

StackExchange Code Review Q#162648, answer score: 2