cs50 pset5 load tries not enough memory

Question

I think I need help with my load function in pset5. I want to use tries and it generaly works fine (for small dictionaries). Moreover it checks words correctly but still I'm doing something choribly wrong because for large dictionary after loading aproximately 12500 words my rpogiram is killed and I receive massage:

Child terminated with signal = 0x9 (SIGKILL) GDBserver exiting

and above is information that the program hit the memory limit.

I understand the core of the problem - Program wants to use more memory that it has. Although I don't know where am I loosing this memory. One node is 224Bytes (I have check with sizeof) there is 150000 words in the dictionary, everyword can have more then 40 letters but it is obvious that most of them wont have more then 10. So even if every letter was creating a node (but it's not - when the pointer is not NULL the new node is not created) then it should be enough of memory. I don't know where I'm making mistake (I repeat, that for small dictionaries it warks fine).

bool load(const char *dictionary)
{
n_words = 0;
// open a dictionary file
FILE *fd = fopen (dictionary, "r");
// break if can't load dictionary file
if (fd == NULL)
{
    printf ("Could not open %s.\n", dictionary);
    return 1;
}
//creat root node (first node)
root = (malloc (1 * sizeof (node)));
    //if can't allocate memory - break and unload a file
    if (root == NULL)
    {
        return 1;
        fclose (fd);
    }
//creat array for a word from dictionary (probably +1 is not necessery here...)
char word[LENGTH + 1];

//read word's from the dictionary file as long as EOF
while (fscanf (fd, "%s", word) != EOF)
{

    //count number of letters in the word
    int n_letters = strlen (word);

    //create copy of the root node to avoid loosing root
    nextNode = root;

    //memorizing letters from the word
    for (int i = 0; i<=n_letters; i++) //do it as long until we reach last letter in the word + 1 to write end of the word
    {
        // checking number of the current letter in the array of pointers
        int index = ((int) word[i] - 'a');

        //if current letteri "'" then we give to it the last place in the array of pointers
        if (((int) word[i]) == 96) index = 27;

        //if we reach end of the word + 1, then we setting bool is_word as true (we have reach and of the current word in the dictionary)
        if (i == n_letters)
        {
            nextNode->is_word = true;
            n_words = n_words + 1;


        }
        else
        {
            //if we didn't reach end of the word, then we are checking if in corresponding fild in array of pointers there is a pointer to next node - if not we are creating it
            if (nextNode->children [index] == NULL)
            {
                nextNode->children[index] = (calloc (1 * sizeof (node), sizeof (node)));

                // if we couldn't allocate memory for another node, we break
                if (nextNode->children[index]==NULL)
                {
                    return 1;
                    fclose (fd);
                }
            }
            //we change the nextNode pointer to point for a new node created in the array of pointers and we go back to check next letter of the word
            nextNode = nextNode->children[index];
        }
    }
}
//we close dictionary file
fclose (fd);
return true;

Answer 1

The problem stems from here:

int index = ((int) word[i] - 'a');

        //if current letteri "'" then we give to it the last place in the array of pointers
        if (((int) word[i]) == 96) index = 27;

ascii 96 is a backtick or backquote character

`

apostrophe ' is ascii 39. When the program encounters apostrophe, index is 39 - 'a', a negative number, and will probably crash here if (nextNode->children [index] == NULL). The small dictionary does not contain apostrophe.

Make sure index = 27 is what you want when you process an apostrophe. Depending on how your node is defined, index 27 may be beyond "the last place in the array of pointers".