Trie Data Structure Implemented in C language

trie.c

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


struct Pair {
    unsigned ok;
    int val;
};


struct Link {
    char token;
    struct Node *next;
};


struct Node {
    unsigned char used;
    int value;
    int nlink;
    struct Link **links;
};


int findLink(struct Node *node, char token) {
    int found = 0;
    int idx;
    for (idx = 0; idx < node->nlink; idx++){
        if (node->links[idx]->token == token){
            found = 1;
            break;
        }
    }

    if (!found) {
        return -1;
    } 

    return idx;
}


struct Node * addLink(struct Node *node, char token) {
    int idx = findLink(node, token);

    if (idx < 0) {
        if (node->nlink > 0) {
            idx = node->nlink;
            node->nlink = node->nlink + 1;
            node->links = (struct Link **) realloc(
                node->links, sizeof(struct Link *) * node->nlink
            );
        } else {
            idx = 0;
            node->nlink = 1;
            node->links = (struct Link **) malloc(sizeof(struct Link *));
        }

        struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
        new_node->used = 0;
        new_node->value = 0;
        new_node->nlink = 0;
        new_node->links = NULL;

        struct Link *new_link = (struct Link *) malloc(sizeof(struct Link));
        new_link->token = token;
        new_link->next = new_node;

        node->links[idx] = new_link;

        return new_node;
    }

    return node->links[idx]->next;
}


void storeValue(struct Node *node, char *key, int value) {
    int n = strlen(key);
    struct Node *next_node = node;
    for (int i = 0; i < n; i++) {
        next_node = addLink(next_node, key[i]);
    }

    next_node->used = 1;
    next_node->value = value;
}


struct Pair findKey(struct Node *node, char *key) {
    int n = strlen(key);
    struct Pair result;
    struct Node *next_node = node;
    for (int i = 0; i < n; i++) {
        int idx = findLink(next_node, key[i]);
        
        if (idx < 0) {
            result.ok = 0;
            return result;
        }

        next_node = next_node->links[idx]->next;
    }

    result.val = next_node->value;
    result.ok = next_node->used;
    return result;
}


struct Node * NewTrie() {
    struct Node *node = (struct Node *) malloc(sizeof(struct Node));
    node->used = 0;
    node->value = 0;
    node->nlink = 0;
    node->links = NULL;

    return node;
}


void deleteTrie(struct Node *node) {
    for (int i = 0; i < node->nlink; i++) {
        struct Link *link = node->links[i];
        deleteTrie(link->next);
        free(link);
    }

    free(node->links);
    free(node);
}


int main(){
    struct Node *trie = NewTrie();
    storeValue(trie, "abcd", 10);
    // storeValue(trie, "abce", 11);
    // storeValue(trie, "ab", 12);

    struct Pair pair = findKey(trie, "abcd");
    if (pair.ok) {
        printf("abcd = %d \n", pair.val);
    } else {
        printf("abcd = not found \n");
    }

    pair = findKey(trie, "abce");
    if (pair.ok) {
        printf("abce = %d \n", pair.val);
    } else {
        printf("abce = not found \n");
    }

    pair = findKey(trie, "ab");
    if (pair.ok) {
        printf("ab = %d \n", pair.val);
    } else {
        printf("ab = not found \n");
    }

    pair = findKey(trie, "afff");
    if (pair.ok) {
        printf("afff = %d \n", pair.val);
    } else {
        printf("afff = not found \n");
    }

    pair = findKey(trie, "abc");
    if (pair.ok) {
        printf("abc = %d \n", pair.val);
    } else {
        printf("abc = not found \n");
    }


    deleteTrie(trie);

    return 0;
}