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 .