Search code examples
cpointerssegmentation-faulttrie

Can someone help me find the segfault here?


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

(...)


Solution

  • 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;
        }