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



typedef struct Trie Trie;

struct Trie {
    char key[16];
    int end;
    Trie *next;
    Trie *child;
};

static Trie *trie_create(const char *str)
{
    Trie *trie = malloc(sizeof(*trie));

    trie->next = NULL;
    trie->child = NULL;
    trie->end = 0;
    strcpy(trie->key, str);
    
    return trie;
}

void trie_add(Trie **trie, const char *str) 
{
    char buf[strlen(str) + 1];
    char *tok;
    int *p = NULL;
    
    strcpy(buf, str);

    tok = strtok(buf, ".");
    
    while (tok) {
        while (*trie) {
            if (strcmp((*trie)->key, tok) == 0) break;

            trie = &(*trie)->next;
        }

        if (*trie == NULL) {
            *trie = malloc(sizeof(**trie));
            
            (*trie)->next = NULL;
            (*trie)->child = NULL;
            (*trie)->end = 0;
            strcpy((*trie)->key, tok);
        }
        
        p = &(*trie)->end;
        trie = &(*trie)->child;

        tok = strtok(NULL, ".");
    }
    
    if (p) (*p)++;
}

void trie_delete(Trie *trie)
{
    while (trie) {
        Trie *t = trie;   
    
        trie_delete(trie->child);
        trie = trie->next;
        free(t);
    }
}

void trie_print(Trie *trie, int level)
{
    while (trie) {
        printf("%*s%s", level * 4, "", trie->key);
        if (trie->end) printf(" [%d]", trie->end);
        puts("");
    
        trie_print(trie->child, level + 1);
        trie = trie->next;
    }
}

int main()
{
    Trie *trie = NULL;
    
    trie_add(&trie, "foo.foo");
    trie_add(&trie, "foo.foo");
    trie_add(&trie, "foo.bar.foo.*");
    trie_add(&trie, "foo.baz.*");
    trie_add(&trie, "foo.*.bar");
    trie_add(&trie, "bar.foo.*.one");
    trie_add(&trie, "bar.foo.*.two");
    trie_add(&trie, "foo.foo");
    trie_add(&trie, "foo.foo");
    trie_add(&trie, "bar");

    trie_print(trie, 0);

    trie_delete(trie);
    
    return 0;
}