Return to Answer

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.

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.

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

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.

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.

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.

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.