Segmentation fault loading dictionary into trie tree

Question

I'm making a program that reads a given dictionary into a trie tree, and then performs auto complete on a string inputted by the user. When I use the dictionary file that I am required to use (~100,000 words) I get a segmentation fault. I can't seem to figure out what is causing the segmentation fault. Any help would be appreciated.

typedef struct trieTree {
    int data;
    struct trieTree *array[26];
}trieTree;

insert function:

    trieTree* insert_tree(trieTree *t, char *s, int val)
{
    int i;
    trieTree *p;
    if (strlen(s) == 0)
    return t;
    if (t == NULL)
    t = new_tree(t);
    p = t;
    for (i = 0; i < strlen(s); ++i) {
        if (p->array[s[i] - 'a'] == NULL) 
        p->array[s[i] - 'a'] = malloc(sizeof (trieTree));
        p = p->array[s[i] - 'a'];
    }
    p->data = val;
    return t;
}

Filling the tree:

trieTree* load_tree(trieTree *t, char *file)
{
    char s[MAX];
    FILE *f = fopen(file, "r");
    if (f == NULL)
    printf("Error! File not found.");
    else 
    while (feof(f) == 0) {
        fscanf(f, "%s", s);
        t = insert_tree(t, s, 1);
    }
    return t;
}

Main function

int main()
{
    trieTree t;
    new_tree(&t);
    load_tree(&t, "dict.txt");
    char word[100];
    printf("Enter word: ");
    scanf("%s", word);
    char dat[100] = "";
    search_tree(&t, word, dat);
    return 0;
}


trieTree* new_tree(trieTree *t)
{
    int i;
    t = malloc(sizeof (trieTree));
    for (i = 0; i < 24; ++i)
    t->array[i] = 0;
    return t;
}

Answer 1

Your function new_tree() returns a pointer to allocated memory but the returned value is ignored. That's a memory leak, and your code continues to use an uninitialized variable. That's a problem!

int main()
{
    trieTree t;
    new_tree(&t);
    load_tree(&t, "dict.txt");
    …

trieTree* new_tree(trieTree *t)
{
    int i;
    t = malloc(sizeof(trieTree));
    for (i = 0; i < 24; ++i)
        t->array[i] = 0;
    return t;
}

The 24 in the function should be 26, of course. But the function allocates memory and assigns it to the local pointer (original set to point to t in main(), but the malloc() zaps that value). That pointer is returned, but the return is ignored. The variable t in main() is still uninitialized, but it is passed to the load_tree() function.

Frankly, you need:

int main()
{
    trieTree *tp = new_tree();
    load_tree(&t, "dict.txt");
    …

trieTree* new_tree(void)
{
    int i;
    trieTree *t = malloc(sizeof(trieTree));
    if (t == 0)
    {
        fprintf(stderr, "memory allocation failure\n");
        exit(EXIT_FAILURE);
    }
    for (i = 0; i < 26; ++i)
        t->array[i] = 0;
    return t;
}

Note that errors should be reported on the standard error channel; that is what it's for. And that every memory allocation should be checked, because if you don't check, it will fail and your program will crash.

There are probably a lot of other problems; I've not investigated them all. This should get you further before crashing.

This seems to work for me, though admittedly I only tested it on a 'dictionary' of 257 words.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { MAX = 1024 };

typedef struct trieTree
{
    int data;
    struct trieTree *array[26];
} trieTree;

static trieTree *new_tree(void)
{
    int i;
    trieTree *t = malloc(sizeof(trieTree));
    if (t == 0)
    {
        fprintf(stderr, "malloc for %zu bytes failed\n", sizeof(trieTree));
        exit(EXIT_FAILURE);
    }
    t->data = 0;
    for (i = 0; i < 26; ++i)
        t->array[i] = 0;
    return t;
}

static trieTree *insert_tree(trieTree *t, char *s, int val)
{
    int i;
    trieTree *p;
    if (strlen(s) == 0)
        return t;
    if (t == NULL)
        t = new_tree();
    p = t;
    int len = strlen(s);
    for (i = 0; i < len; ++i)
    {
        if (p->array[s[i] - 'a'] == NULL)
            p->array[s[i] - 'a'] = new_tree();
        p = p->array[s[i] - 'a'];
    }
    p->data = val;
    return t;
}

static trieTree *load_tree(trieTree *t, char *file)
{
    char s[MAX];
    FILE *f = fopen(file, "r");
    if (f == NULL)
    {
        fprintf(stderr, "Error! File not found.");
        exit(EXIT_FAILURE);
    }
    else
    {
        while (fscanf(f, "%s", s) == 1)
            t = insert_tree(t, s, 1);
        fclose(f);
    }
    return t;
}

static void print_trie(trieTree *t, char *pad)
{
    int len = strlen(pad);
    char space[len + 3];
    memset(space, ' ', len + 2);
    space[len + 2] = '\0';

    for (int i = 0; i < 26; i++)
    {
        if (t->array[i] != 0)
        {
            printf("%s%c\n", pad, i + 'a');
            print_trie(t->array[i], space);
        }
    }
}

static void free_trie(trieTree *t)
{
    if (t != 0)
    {
        for (int i = 0; i < 26; i++)
            free_trie(t->array[i]);
        free(t);
    }
}

int main(void)
{
    trieTree *tp = new_tree();
    if (tp != 0)
    {
        tp = load_tree(tp, "dict.txt");
        print_trie(tp, "");
        free_trie(tp);
    }
    return 0;
}

I believe it is leak free, too.

Note that this code will crash and burn if any of the input words contains any upper-case letters, or digits, or punctuation. It only handles lower-case and white space; anything else is an unchecked disaster waiting to devastate your program. That's because I've not done any substantive work in the insert_tree() function. You need to worry about 'invalid' characters in that function, probably by case-converting upper-case letters to lower-case and ignoring anything that's not a letter.