I have a C program to implement of Trie in which each not stores some data (see below). The trie should use strings in it's branches to arrange data (ie as keys) with integer data at each terminating point in the tree.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRIE_LIMIT 26
#define TRIE_DATA_TYPE int
#define TRIE_DATA_DEFAULT -1
#define TRIE_NODE_NULL NULL
#define TRIE_START_CHAR 'a' // Defines the 'zero' of the tree, can use (e.g.) '0' for searches including numbers
struct trie_node {
TRIE_DATA_TYPE data;
struct trie_node * nodes[TRIE_LIMIT];
};
struct trie_node * make_node_data(TRIE_DATA_TYPE data) {
struct trie_node* new_node = (struct trie_node*)malloc(sizeof(struct trie_node*));
if (new_node != NULL) {
new_node->data = malloc(sizeof(TRIE_DATA_TYPE));
new_node->data = data;
for (int i = 0; i < TRIE_LIMIT; i++) {
new_node->nodes[i] = NULL; // TRIE_NODE_NULL;
}
}
return new_node;
}
struct trie_node * make_node_default() {
return make_node_data(TRIE_DATA_DEFAULT);
}
void insert_trie(struct trie_node * root, char * val, TRIE_DATA_TYPE data) {
// Based off of my solution to HackerRank "1 Week Preparation kit": "No Prefix Set"
// Modified from:
// https://www.digitalocean.com/community/tutorials/trie-data-structure-in-c-plus-plus
// https://www.techiedelight.com/trie-implementation-insert-search-delete/
struct trie_node * current = root;
int length = strlen(val);
for (int i=0; i < length; i++) { // Can replace with search for '\0'
int index = val[i] - TRIE_START_CHAR;
if (current->nodes[index] == NULL) {
// Node does not yet exist in tree, append
//printf("Making node for letter %s\n", val[i]);
current->nodes[index] = make_node_default();
}
else {
// Can do something else
}
current = current->nodes[index];
}
// Reached the final branch, can add our data here.
if (current->data == TRIE_DATA_DEFAULT) {
current->data = data;
}
else {
// Handle case were data already exists at node;
}
current = root;
return;
}
TRIE_DATA_TYPE find_data(struct trie_node* root, char* val) {
// Searches a tree for val.
// returns TRIE_DATA_TYPE if it doesn't exist
// returns current->node
// Modified from:
// https://www.digitalocean.com/community/tutorials/trie-data-structure-in-c-plus-plus
// https://www.techiedelight.com/trie-implementation-insert-search-delete/
struct trie_node* current = root;
int length = strlen(val);
for (int i = 0; i < length; i++) { // Can replace with search for '\0'
int index = val[i] - TRIE_START_CHAR;
if (current->nodes[index] == NULL) {
// Node does not yet exist in tree, return TRIE_DATA_DEFAULT
//printf("Can't find val in root, i=%d returning...\n", i);
current = root;
return TRIE_DATA_DEFAULT;
}
else {
// Node exists in tree, continue
current = current->nodes[index];
}
}
// Got to the end of the tree, returning value stored
// Can check if there are daughter nodes, etc
TRIE_DATA_TYPE data = current->data;
current = root;
return data;
}
void print_find(struct trie_node* root, char * val) {
TRIE_DATA_TYPE trie_val = find_data(root, val);
if (trie_val == TRIE_DATA_DEFAULT) {
printf("'%s' not in root!\n", val);
}
else {
printf("Data at '%s': %d\n", val, trie_val);
}
return;
}
int main() {
struct trie_node* root = make_node_default();
insert_trie(root, "abc", 5);
insert_trie(root, "abcd", 6);
print_find(root, "abc"); // Should print: Data at abc: 5
print_find(root, "abcd");// Should print: Data at abcd: 6
print_find(root, "trie");// Should print: trie not in root!
free(root);
return 0;
}
Using the debugger and examining the values in the 'root' trie at runtime, what we see is that the tree appears to initialize correctly (data is -1, and all values in the nodes are NULL). But eventually (sometimes the first "insert" step, sometimes the second, sometimes during the "print_find"), the values take on some "nonsense" values for some of the values that should remain NULL (example below; [0] is correct, the rest should be NULL; taken on a breakpoint located on the first "print_find" step).
*Note that this is an example, and each time I run the application, I get slightly different results, sometimes I make it all the way through, but usually I hit some nonsense value of data and it claims that the value at 'trie' is -7600000 or something.
I've tried cleaning and rebuilding, as well as different ways of allocating (malloc, vs calloc, vs nothing).
What I was expecting is that the values would remain NULL during runtime and I could use checks for NULLs to progress through the trie; instead I often end up with garbage as it finds non-NULL values and returns those values of data. This looks like the memory is allocated correctly, but then reused by other processes or something during runtime, but I'm not sure how to prevent such behaviour.
