0

I have been trying to create a trie for storing my dictionary, and the code looks like it ought to work. However, when I run Valgrind on it, I get a number of read/write errors (mostly of size 4). In particular, I initialise my nodes as follows:

dictionary.h

typedef struct node
{
    bool is_word;
    struct node* children[27];  
}
node;

dictionary.c

struct node* root;

bool load(const char* dictionary)
{
    // create our dictionary initialiser
    root = malloc(sizeof(struct node));

    // check if memory available
    if (root == NULL)
    {
        printf("Not enough memory to create dictionary");
        return false;
    }

    // initialise the values
    for (int i = 0; i < 27; i++)
    {
        root->children[i] = NULL;
    }
    root->is_word = false;

    // create a temporary storage for tracking down the trie later
    struct node* current = root;

But then later in my code, when I try to use current->is_word = true; I get the following from Valgrind:

==9802== Invalid write of size 1
==9802==    at 0x8049191: load (dictionary.c:137)
==9802==    by 0x80486F5: main (speller.c:45)
==9802==  Address 0x41f5258 is 0 bytes inside a block of size 112 free'd
==9802==    at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==9802==    by 0x804926E: load (dictionary.c:161)
==9802==    by 0x80486F5: main (speller.c:45)

And further, when I try to use if (current->children[index] == NULL), I get the following:

==9802== Invalid read of size 4
==9802==    at 0x80491C3: load (dictionary.c:145)
==9802==    by 0x80486F5: main (speller.c:45)
==9802==  Address 0x41f525c is 4 bytes inside a block of size 112 free'd
==9802==    at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==9802==    by 0x804926E: load (dictionary.c:161)
==9802==    by 0x80486F5: main (speller.c:45)

This last error, I receive each time I try to access any part of current->children[index] (both read and write errors).

When I just try to run my code, I get a seg fault:

jharvard@appliance (~/Dropbox/pset5): ./speller ~cs50/pset5/texts/autinpowers.txt
Could not open /home/cs50/pset5/texts/autinpowers.txt.
Segmentation fault (core dumped)

I haven't included all of the code, as I'm not sure how much of it I can provide. However, if you need it, please let me know and I will upload it all. I have tried looking for solutions on various questions on here, but I can't seem to find anything that is relevant - most of the solutions I had already implemented.

I was originally using calloc(1, sizeof(node)) instead of malloc, but I have tried malloc to see if that was the problem - it hasn't made a difference.

EDIT - Code now removed to comply with academic honesty policy

2
  • From that, it's hard to tell, since there's not much your code shows. I don't think the problem will be there, since all you did there was mallocing for one node, and setting all the children to NULL. But it would seem like you're calling free in your load function somewhere? I should look at the rest of the load function, to see how the actual dictionary is being loaded. – Irene Aug 30 '15 at 22:33
  • Thanks Irene! Having run the code without the typo (oops!) I think that the seg fault I was getting is in my unload function, which I have added above. I still can't get my code to work though, and I can't see why, so I have included it, and will remove it once it has been solved (I hope this is ok with the academic honesty policy!). – Gemma Down Aug 31 '15 at 8:15
0

First of all, posting the code that is relevant to your problem is acceptable.

It isn't clear what your problem is here. Does the program not work or are you trying to resolve memory leaks? You shouldn't be working on memory leak issues until you have the program working correctly. And since you're getting a seg fault and are failing to open the input file, you have more work to do to get it working.

The reason that you couldn't open the input file is that you misspelled the file name. However, it should have simply printed an error message and terminated the program. It should not have had a seg fault, so there's a problem there - possibly no return command when the error was processed.

When you get to the point that the program works and need help resolving memory issues, please show the code that relates to the leaks. Indicate which line valgrind is having a problem with. For example, which lines are 137 and 145 in your code above?

If this answers your question, please click the check mark to accept this and remove the question from the unanswered pool. Let's keep up on forum maintenance. ;-)

3
  • Thanks for spotting the typo! The return error comes after trying to unload the dictionary which is what must be causing the seg fault. The code doesn't work, in that it just prints out every word as being a misspelling, but I haven't been able to work out why that is, so I was looking at Valgrind to see where the seg fault happened, and also if it had any other errors that might be causing it to not work. But the errors described above are all that I found and haven't helped. – Gemma Down Aug 31 '15 at 8:12
  • First of all, you should understand that valgrind doesn't really help you with logic errors. All it does is inspect memory management - to tell you if you're losing track of memory in your program. It's not going to be terribly helpful to find and fix seg faults. As indicated in the class material, you really need to resolve all of the logic problems first. But I'll try to take a look at the code you just posted. – Cliff B Aug 31 '15 at 8:21
  • Ahh thanks Cliff! When I was googling how to find seg faults, most of the solutions pointed me to Valgrind as the best way of finding them. – Gemma Down Aug 31 '15 at 10:38
0

Thanks both Cliff and Irene, I have managed to work out the issue with it. Besides the spelling error originally:

jharvard@appliance (~/Dropbox/pset5): ./speller ~cs50/pset5/texts/autinpowers.txt

there were a couple of nitty-gritty errors that I spotted. I have now removed my original code above where these are in relation to, but hopefully this might help others in a similar situation:

1) After I had created a temporary node, I was accidentally making all of the root children NULL.

2) I was originally freeing a temporary node after I had created it, but forgetting that this would essentially wipe the node I was wanting to keep. I had done the following:

// Create a new node
        if (current->children[index] == NULL)
        {
            // create temporary node, and signpost current one to it
            node* temp = malloc(sizeof(struct node));
            if (temp == NULL)
            {
                printf("Not enough memory to create dictionary");
                return false;
            }
            for (int i = 0; i < 27; i++)
            {
                // ERROR 1
                root->children[i] = NULL;
            }
            temp->is_word = false;
            current->children[index] = temp;
            current = current->children[index];
            // ERROR 2
            free(temp);
        }

3) I had put a ; after my if statement in unload, so it was trying to free memory that wasn't being signposted to:

/**
 * Unloads the current branch of the trie from memory
 */

void unloadbranch(node* cursor)
{
    for (int i = 0; i < 27; i++)
    {
        if (cursor->children[i] != NULL);
        {
            unloadbranch(cursor->children[i]);
        }
    }
    free(cursor);
}

All 4 (including the typo) were very frustrating, but thankfully now sorted!

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .