Trie for SO qn http://stackoverflow.com/questions/17758452/t

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

#define NRALPHA 26
#define VEC_INIT_SZ 64

struct Vec {
    char *buf;
    int nrChars;
    int capacity;
};

struct Vec *vec_new()
{
    struct Vec *v = (struct Vec *)calloc(1, sizeof(struct Vec));
    v->buf = (char *)calloc(VEC_INIT_SZ, sizeof(char));
    v->capacity = VEC_INIT_SZ;
    return v;
}

void vec_free(struct Vec *v)
{
    if (v) {
        if (v->buf) {
            free(v->buf);
        }
        free(v);
    }
}

int vec_increase_size(struct Vec *v)
{
    int newCap;
    char *tmpbuf;
    if (v->nrChars+1 >= v->capacity) {
        newCap = v->capacity * 2;
        tmpbuf = (char *)realloc(v->buf, newCap);
        if (!tmpbuf) {
            return 0;
        }
        v->buf = tmpbuf;
        v->capacity = newCap;
        return 1;
    } else {
        return 1;
    }
}

void vec_print(struct Vec *v)
{
    if (v->nrChars >= 0) {
        v->buf[v->nrChars] = 0;
        printf("%s\n", v->buf);
    }
}

void vec_put_char(struct Vec *v, char ch)
{
    v->buf[v->nrChars++] = ch;
}

void vec_pop_char(struct Vec *v)
{
    if (v->nrChars > 0) {
        v->nrChars--;
    }
}

void vec_clear(struct Vec *v)
{
    v->nrChars = 0;
}

struct trie {
    int val;
    struct trie *alpha[NRALPHA];
};

struct trie *trie_new()
{
    return (struct trie *)calloc(1, sizeof(struct trie));
}

struct trie *trie_insert(struct trie *root, char *input)
{
    int idx;
    if (!input) {
        return root;
    }
    if (root == NULL) {
        root = (struct trie *)calloc(1, sizeof(struct trie));
    }
    if (*input == '\0') {
        // leaves have root->val set to 1
        root->val = 1;
    } else {
        // carry on insertion
        idx = *input - 'a';
        root->alpha[idx] = trie_insert(root->alpha[idx], input+1);
    }
    return root;
}

// deletes the entire trie from root
void trie_free(struct trie *root)
{
    int i;
    if (root) {
        for (i = 0; i < NRALPHA; i++) {
            trie_free(root->alpha[i]);
        }
        free(root);
    }
}

// prints the trie depth first
void trie_print(struct trie *root, struct Vec *v)
{
    int i;
    if (root) {
        // reach a string, just print
        if (root->val) {
            vec_print(v);
        }
        if (!vec_increase_size(v)) {
            // out of memory
            return;
        }
        for (i = 0; i < NRALPHA; i++) {
            if (root->alpha[i]) {
                vec_put_char(v, 'a' + i);
                trie_print(root->alpha[i], v);
                vec_pop_char(v);
            }
        }
    } else {
        return;
    }
}

struct trie *trie_delete(struct trie *root, char *s)
{
    int i, idx, reap = 0;
    if (!root || !s) {
        return root;
    }
    if (!*s && root->val) {
        // delete this string, and mark node as deletable
        root->val = 0;
        reap = 1;
    } else {
        // more characters carry on
        idx = *s - 'a';
        if (root->alpha[idx]) {
            root->alpha[idx] = trie_delete(root->alpha[idx], s+1);
            if (!root->alpha[idx]) {
                // child node deleted, set reap = 1
                reap = 1;
            }
        }
    }
    // We can delete this if both:
    // 1. reap is set to 1, which is only possible if either:
    //    a. we are now at the end of the string and root->val used
    //       to be 1, but is now set to 0
    //    b. the child node has been deleted
    // 2. The string ending at the current node is not inside the trie,
    //    so root->val = 0
    if (reap && !root->val) {
        for (i = 0; i < NRALPHA; i++) {
            if (root->alpha[i]) {
                reap = 0;
                break;
            }
        }
        // no more children, delete this node
        if (reap) {
            trie_free(root);
            root = NULL;
        }
    }
    return root;
}

int main()
{
    struct Vec *v = vec_new();
    struct trie *root = trie_new();
    // NOTE: max 120 chars including "ins " and "del "
    char buf[121];
    while (fgets(buf, sizeof(buf), stdin)) {
        buf[strlen(buf)-1] = '\0';
        if (!strncmp(buf, "ins ", 4)) {
            root = trie_insert(root, buf+4);
        } else if (!strncmp(buf, "del ", 4)) {
            root = trie_delete(root, buf+4);
        }
        vec_clear(v);
        printf("words in trie:\n");
        trie_print(root, v);
    }
    trie_free(root);
    vec_free(v);
    return 0;
}