Thread: problem with implementing trie data structure with dynamic array

hi friends ,
i can't implement trie with dynamic array .
the problem is in this line i think :

Code:

childs_size = (node_p -> childs_value_p)[0] + 1;

here is my code :

Code:

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

struct trie_node {
    unsigned char *childs_value_p;    // pointer to an array of child nodes value
    struct trie_node **childs_ptp;    // pointer to an array of child nodes pointer
    struct trie_node *failure_node_p; // pointer to failure node
};

struct trie_node *init_trie_node();
struct trie_node *add_to_trie(struct trie_node *root_p, unsigned char *value_p);
struct trie_node *search_trie(struct trie_node *root_p, unsigned char *value_p);
int add_to_childs(struct trie_node *node_p, unsigned char value);
void shift_childs_to_right(struct trie_node *node_p, int value_index, int childs_size);
int specific_binary_search(unsigned char *list_p, unsigned char target, int low, int high);
int read_db(char *db_file_name, struct trie_node *root_p);

int count_nodes = 0;

#define SIGN_SIZE 16

#define V_INIT_SIZE 2
#define P_INIT_SIZE 1

void print_arr(char *arr)
{
    int i = 0;

    while(i <= arr[0] + 1)
    {
        if(i == 0)
            printf("%d, ", arr[i ++]);
        else
            printf("%c, ", arr[i ++]);
    }
    printf("\n");
}

int main()
{
    struct trie_node *root_p = NULL;

    root_p = init_trie_node();

//    read_db("my_db.txt", root_p);

    root_p = add_to_trie(root_p, "amir");
    root_p = add_to_trie(root_p, "amin");
    root_p = add_to_trie(root_p, "ali");
    root_p = add_to_trie(root_p, "all");
    root_p = add_to_trie(root_p, "mina");
    root_p = add_to_trie(root_p, "mitra");
    root_p = add_to_trie(root_p, "bita");
    root_p = add_to_trie(root_p, "melika");
    root_p = add_to_trie(root_p, "ahmad");

    getchar();

    printf("%.2f", (count_nodes * (sizeof(struct trie_node) + sizeof(char) + sizeof(struct trie_node *))) / (1000 * 1024 * 1.0));

    return 0;
}

struct trie_node *init_trie_node()
{
    struct trie_node *new_p = NULL;

    new_p = (struct trie_node *) malloc(sizeof(struct trie_node));
    if(new_p == NULL)
    {
        return NULL;
    }
    new_p -> childs_value_p = NULL;
    new_p -> childs_ptp = NULL;
    new_p -> failure_node_p = NULL;
    return new_p;
}


struct trie_node *add_to_trie(struct trie_node *root_p, unsigned char *value_p)
{
    int i = 0;
    struct trie_node *root_temp_p = root_p;
    int p_index = 0;
    unsigned char c = 0;

    while((c = value_p[i]) != '\0')
    {
        p_index = add_to_childs(root_temp_p, c);
//        if(p_index != -1)
//        {
//            if(i == 15)
//            {
//                free((root_temp_p -> childs_ptp)[p_index]);
//                free(root_temp_p -> childs_ptp);
//            }
//        }
//        else
//        {
//            continue;
//        }
//        print_arr(root_temp_p -> childs_value_p);
        root_temp_p = (root_temp_p -> childs_ptp)[p_index];
        i ++;
    }
    printf("\n");
    return root_p;
}

int add_to_childs(struct trie_node *node_p, unsigned char value)
{
    int childs_size = 0;
    int value_index = 0;
    unsigned char *new_childs_value_p = NULL;
    struct trie_node **new_childs_ptp = NULL;

    if(node_p -> childs_value_p == NULL)
    {
        new_childs_value_p = (unsigned char *) malloc(V_INIT_SIZE * sizeof(unsigned char));
        new_childs_ptp = (struct trie_node **) malloc(P_INIT_SIZE * sizeof(struct trie_node *));
        if(new_childs_value_p != NULL && new_childs_ptp != NULL)
        {
            count_nodes ++;
            node_p -> childs_value_p = new_childs_value_p;
            node_p -> childs_ptp = new_childs_ptp;
            (node_p -> childs_value_p)[0] = 0;
            (node_p -> childs_value_p)[1] = value;
            (node_p -> childs_ptp)[0] = init_trie_node();
            return 0;
        }
        return -1;
    }
    childs_size = (node_p -> childs_value_p)[0] + 1;
    value_index = specific_binary_search(node_p -> childs_value_p, value, 1, childs_size);
    if(value_index <= childs_size && (node_p -> childs_value_p)[value_index] == value)
    {
        return value_index - 1;
    }
    new_childs_value_p = (unsigned char *) malloc((childs_size + 2) * sizeof(unsigned char));
    new_childs_ptp = (struct trie_node **) malloc((childs_size + 1) * sizeof(struct trie_node *));
    if(new_childs_value_p != NULL && new_childs_ptp != NULL)
    {
        count_nodes ++;
        memcpy(new_childs_value_p, node_p -> childs_value_p, childs_size + 1);
        memcpy(new_childs_ptp, node_p -> childs_ptp, childs_size);
        free(node_p -> childs_value_p);
        free(node_p -> childs_ptp);
        node_p -> childs_value_p = new_childs_value_p;
        node_p -> childs_ptp = new_childs_ptp;
        shift_childs_to_right(node_p, value_index, childs_size);
        (node_p -> childs_value_p)[0] ++;
        (node_p -> childs_value_p)[value_index] = value;
        (node_p -> childs_ptp)[value_index - 1] = init_trie_node();
        return value_index - 1;
    }
    return -1;
}

void shift_childs_to_right(struct trie_node *node_p, int value_index, int childs_size)
{
    while(value_index <= childs_size)
    {
        (node_p -> childs_value_p)[childs_size + 1] = (node_p -> childs_value_p)[childs_size];
        (node_p -> childs_ptp)[childs_size] = (node_p -> childs_ptp)[childs_size - 1];
        childs_size --;
    }
}

int specific_binary_search(unsigned char *list_p, unsigned char target, int low, int high)
{
    int middle = 0;

    while(low <= high)
    {
        middle = (high + low) / 2;
        if(target <= *(list_p + middle))
        {
            high = middle - 1;
        }
        else
        {
            low = middle + 1;
        }
    }
    return low;
}

i can't debug it .
i could write this code with binary tree instead of dynamic array but need a large amount of memory for about 13000000 strings of length 16 .
is there any better solution with lower memory usage to implement trie ?
thanks a lot , good luck .

thanks a lot for your help ,
how i can edit my post ?

Huh, there's an example of this on Wikipedia but their structure takes up 216 bytes total. What does yours take up when it's fully malloc'd? I know it's 24 bytes as you have 3 pointers but how memory does your code use compared to this one: Trie - Wikipedia, the free encyclopedia

Originally Posted by MutantJohn

Huh, there's an example of this on Wikipedia but their structure takes up 216 bytes total. What does yours take up when it's fully malloc'd? I know it's 24 bytes as you have 3 pointers but how memory does your code use compared to this one: Trie - Wikipedia, the free encyclopedia

That example only save 26 alphabetic characters but I want to save all of the 256 ASCII characters .
My structures used 24 + (256 * 4) + 257 = 1305 when it is full .
Thanks a lot .

So, in that Wikipedia example, it looked like this was the sort of thing you could use as a dictionary. Is that what the purpose of creating this trie is?