Segmentation Fault While Checking Pointer

Question

I am writing a program that reads a dictionary file (text file, one word per line), and inserts it into a structure consisting of a "linked list" of arrays, where the word is recursively forwarded to the [first letter - 'a'] entry of an array (which is another array, that processes the next letter). When the whole word is "consumed", it inserts the word (unchanged) in a regular linked list of words. The program successfully processes first 15 words, but at 16-th it throws segmentation fault.

It looks like the segmentation fault occurs in add() method in the following snippet:

struct LinkedList * new = (struct LinkedList *) calloc(1,
                                       sizeof(struct LinkedList));
            if (!new) {
                perror("Not enough memory!"); // Error here
                exit(2);
            }

(Hopefully) Relevant code:

void addList (struct LinkedList * list, char * word) {
    if (!list->next)
    {
        struct LinkedList * new = malloc(sizeof(struct LinkedList));
        if (!new) {
            perror("Not enough memory!");
            exit(2);
        }

        char * new_word = malloc(strlen(word) * sizeof(char));
        if (!new_word) {
            fprintf(stderr, "Not enough memory!");
            exit(2);
        }


        new->next = 0;
        strcpy(new_word, word);
        new->word = new_word;
        list->next = new;
    }
    else
    {
        addList(list->next, word);
    }
}


void add(struct HashTree * root, char * word, char * word_sorted, int length) {

    if (length == 0)                                     // Found the correct place
    {

        if (!root->words)                                // If words are not allocated
        {
            // Create list node
            struct LinkedList * new = calloc(1, sizeof(struct LinkedList));
            if (!new) {
                perror("Not enough memory!");
                exit(2);
            }

            char * new_word = malloc(strlen(word) * sizeof(char));
            if (!new_word) {
                fprintf(stderr, "Not enough memory!");
                exit(2);
            }

            new->next = 0;

            strcpy(new_word, word);

            new->word = new_word;
            root->words = new;
        }   

        else                                            // Add to the Linked List
        {
            addList(root->words, word);
        }
    }

    else 
    {
        // printf("Length_add = %d\n", length);
        if (!root->next)                                 // If the array was not allocated yet
        {

            struct HashTree * new = malloc(27 * sizeof(struct HashTree *));
            if (!new) {
                perror("Not enough memory!");
                exit(2);
            }


            root->next = new;
        }


        add(&(root->next[ word_sorted[0] - 'a' ]), 
            word, (char *) (word_sorted +1), (length-1));  // Use the next letter.

    }


}

To save the space, Here is the link to the full code.

Here is the output of gdb core and backtrace:

    Program terminated with signal SIGSEGV, Segmentation fault. 

100 perror("Not enough memory!"); 

Full GDB output

I implemented a similar algorithm in Java before, and the algorithm seems to be correct. I am pretty new to C, and don't understand what might be wrong. I would really appreciate any help!

EDIT: Deleted sort, clean and cleanWords methods (they does not greatly affect the adding of the word to the structure). Segmentation occurred while processing the second word, line 125:

perror("Dictionary file not found!");

Link to code -
Link to sample dictionary

Valgrind output

Answer 1

In the main else clause of add(), you allocate some memory, but don't initialize it. You then use the uninitialized memory in the next recursive call to add(). At minimum, use calloc() in place of malloc() there. You're also allocating only enough space for 27 pointers to your structures, but you're using it as though you allocated 27 structures.

Wrong:

struct HashTree * new = malloc(27 * sizeof(struct HashTree *));

Right:

struct HashTree *new = calloc(27, sizeof(struct HashTree));

Or:

struct HashTree *new = calloc(27, sizeof(*new));

Also, in both addList() and add(), you are not allocating enough space for the string; you forgot the trailing null.

Wrong:

char *new_word = (char *) malloc(length * sizeof(char));

Right:

char *new_word = (char *) malloc(length + 1);

I don't use C++ keywords in my C code, so I'd use new_hash or thereabouts instead of just new. Many would castigate you for the casts on the allocations.

With those changes, the code ran to completion for me. It leaked like fury, but that was totally expected.

Answer 2

for errors like this the problem is almost always an issue with fopen. If I am right you may have forgotten to add the extension to a file or perhaps it is an issue with the file-paths you are using.

My advice:

use ctrl+f to locate all instances of fopen then verify that they reference the correct file.

EDIT pay special attention to line 184. I suspect that "/usr/share/dict/words" should be "/usr/share/dict/words.txt"

EDIT 2:

instead of (line 200):

while(fgets(word, sizeof(word), dict) != NULL) {

try fscanf:

while(!feof(dict)) {
    fscanf(dict, "%*[^']", MAX_WORD_LENGTH, word);

EDIT

Thank you @JonathanLeffler I would still recommend fscanf

int fscanf( FILE *restrict stream, const char *restrict format, ... );

If you use it right, fscanf can be very useful when reading formatted data.

fscanf(dict, "%*s", MAX_WORD_LENGTH, word);
fscanf(dict, "'", MAX_WORD_LENGTH, word);//get rid of the delimiter