EDIT: So, it turns out that 'index' was not being returned to 0. Well then. That fixed one segfault. But still getting a different segfault. Working on it.
node* new_node(void){
node* ptr = malloc(sizeof(node));
for (int i = 0; i<27; i++) {
ptr->next[i] = NULL;
}
return ptr;
}
bool load(const char* dictionary)
{
FILE* dict = fopen(dictionary, "r");
node* ptr = new_node;
char word[LENGTH+1];
int index = 0;
for (int c = fgetc(dict); c!=EOF; c = fgetc(dict)){
if(c!='\n'){
word[index]=c;
index++;
}
else {
for(int x=0; x<=index; x++){
int ch = (word[x] == '\'') ? 26 : tolower(word[x])-'a';
if (ptr->next[ch] == NULL){
ptr->next[ch] = new_node;
}
ptr = ptr->next[ch];
}
ptr->end=true;
}
}
return true;
}
I'm trying to implement a trie data structure for a dictionary but my program seems to segfault somewhere in this function. I can't seem to pin it down even with the help of GDB, so can someone give me a hand?
Node is defined as such:
typedef struct node{
bool end;
struct node* next[27];
} node;
Dictionary file:
a
aaa
aaas
aachen
aalborg
aalesund
aardvark
aardvark's
aardvarks
aardwolf
(...)
You have many issues in your code:
When you allocate memory with malloc
, it is uninitialised. initialise it directly after allocating it, so that NULL
pointers really are null. (calloc
, a cousin of ´malloc´, initialises all memory to zero.)
When you loop over the word, you should nor include index
:
for (int x = 0; x < index; x++) ...
When you have found the end of a word, you must reset the index
to 0. Otherwise, you will append to the old word and overflow the buffer. (You should probably also enforce the upper bound of ´index´.)
Likewise, when you insert a word into the trie, you must reset your pointer for trie traversal to the trie's root. You need two pointers here: A root node pointer and an auxiliary pointer for traversing the trie.
As is, your trie is local to your function. Return the root node, so that other functions can use the trie, or NULL
on failure.
Fix these, and you will have a non-crashing function. (It still leaks memory and may not construct the trie properly.)
node *load(const char *dictionary)
{
FILE *dict = fopen(dictionary, "r");
node *head = calloc(1, sizeof(node));
char word[LENGTH + 1];
int index = 0;
for (int c = fgetc(dict); c != EOF; c = fgetc(dict)) {
if (c != '\n') {
word[index] = c;
index++;
} else {
node *ptr = head;
for (int x = 0; x < index; x++) {
int ch = (word[x] == '\'') ? 26 : tolower(word[x]) - 'a';
if (ptr->next[ch] == NULL) {
ptr->next[ch] = calloc(1, sizeof(node));
}
ptr = ptr->next[ch];
}
ptr->end = true;
index = 0;
}
}
return head;
}