0

I can't seem to figure out how to allocate and free memory correctly when I'm using a linked list node (a pointer inside a struct). When I can get my code to run without error I am getting major memory leaks according to valgrind. The code for load() below gives me a Double free error on line 108 (where I am freeing the struct newword. I have tried lots of different things to fix it but I can't seem to free the memory properly.

Here's where I define the struct:

typedef struct node
{
    char word[LENGTH + 1];
    struct node* next;
}
node;

And two global variables:

node *hashtbl[HASHTABLESIZE];
unsigned int dictwords;

Now the code for load():

bool load(const char* dictionary)
{

//initialize hash table to null values
for (int i = 0; i < HASHTABLESIZE; i++)
{
hashtbl[i] = NULL;
}
//load the dictionary file
FILE *fp = NULL;
//need to add error checking whether file could be opened
fp = fopen(dictionary, "r");

char dictword[LENGTH + 1];
while(fscanf(fp, "%s", dictword) != EOF)
    {
    node* newword = malloc(sizeof(node));
    newword->next=malloc(LENGTH + 1);
    strcpy(newword->word, dictword);
    newword->next = NULL;
    unsigned int hashofkey;
    hashofkey = hash(dictword);
    if(hashtbl[hashofkey] == NULL)
    {
        hashtbl[hashofkey] = newword;
    }
    else if(hashtbl[hashofkey] != NULL)
    {
        newword->next = hashtbl[hashofkey];
        hashtbl[hashofkey] = newword;
    }
free(newword->next);
free(newword);
dictwords++;
}
    fclose(fp);
    return true;
}

The error occurs on the second free free(newword); And the error says:

#4  0xb7e9233a in malloc_printerr (action=<optimized out>, str=0xb7f850a0 "double free or corruption (fasttop)", ptr=0x804c170) at malloc.c:4996
#5  0xb7e92fad in _int_free (av=0xb7fc9420 <main_arena>, p=<optimized out>, have_lock=0) at malloc.c:3840
#6  0x0804928a in load (dictionary=0x8049492 "/home/cs50/pset5/dictionaries/large") at dictionary.c:108
#7  0x080487b6 in main (argc=2, argv=0xbffff184) at speller.c:45

All help is much appreciated!

1

I see a couple of problems here. First, in newword->next=malloc(LENGTH + 1);, 'newword->next' is a pointer to a node. You are allocating the space for newword->word, but not for the rest of the node, so sooner or later, you're not going to have enough space allocated to it. BUT, that's a moot point, because you'll never load anything into it. Instead, you've created a serious memory leak. Two lines later, you have newword->next = NULL; so the space that was allocated is leaked/lost forever. Simple solution - remove the malloc for newword->next. It is totally unnecessary.

Next, why are you freeing newword->next and newword in the load function? You are mallocing the space to newword and sometimes pointing newword->next at existing space, and then adding these memory spaces to the hashtbl[] tree. BUT, when you free nextword->next and nextword, you are freeing the memory that has been inserted into the tree! Essentially, you are deleting the word that you just added to the tree by freeing those spaces. When you free newword, you are freeing one of the root nodes at hashtbl[hashofkey], but leaving hashtbl[hashofkey] pointing at that memory.

There is no need to free newword and it's elements because the pointer contents will clear at the end of each loop through the while loop when they go out of scope and will be reinitialized in the next pass.

This shoud get you going. If this answers your question, please accept this answer to close the question. Let's keep up on forum maintenance. ;-)

7
  • Thanks, this helped a lot! I realized I am mallocing in a bunch of places that are unnecessary elsewhere too. I did have two questions. 1> Is it ever proper or necessary to malloc space for a pointer within a struct? I see alot of this elsewhere on the internet. 2> Is it ever necessary to initialize values that your pointer is pointing to when using malloc to allocate some memory? Specifically, it's critical that at the end of my linked list, the next value is NULL, right? So that my crawler knows its at the end? When I call malloc on *newworrd, am I guaranteed to get newword->next == NULL?
    – cam
    Jul 26 '15 at 14:27
  • When you malloc space for a structure, space is allocated for everything within that structure. When one of those elements is a pointer, the space for that pointer is allocated, but the pointer isn't pointing at anything valid. It will only contain random data that was in that memory location from the last time it was used. The best practice is to always initialize every pointer when created. It's common that you won't be ready to actually malloc space at that time, so it's really important to initialize it by setting it to NULL to reset the random data. When you are ready to use it.....
    – Cliff B
    Jul 26 '15 at 18:02
  • When you are ready to use the pointer, then yes, it's absolutely necessary to malloc the space for it. (And of course, if that's a pointer, same rules apply.) As you figured out, in this pset, the end pointer does need to point to NULL. If you start by setting node->next to NULL when node is malloc'd, then they will always be NULL until explicitly pointed at a new node by a malloc command. To be perfetly clear and to answer your last question, when you malloc newword, newword->next is NOT initialized. It contains random data. You must explicitly set it to NULL. Does all this make sense?
    – Cliff B
    Jul 26 '15 at 18:11
  • Hmm, I'm confused. Question 1: So I do need to assign newword->next = NULL? I get that if I do newword->next = malloc(..); and then newword->next = NULL I'm losing the memory address that my newly allocated memory is at, so its a leak. So should it be *newword->next = NULLso that I'm assigning the memory itself to NULL, not the pointer?. Question 2, do I actually need to malloc space for newword->next in the case of load? I will be directing newword->next at space that will have already been malloc'ed in the prior loop, correct? I ask bc I removed that and valgrind shows no leaks.
    – cam
    Jul 27 '15 at 1:05
  • Answer 1: Unless you are going to immediately malloc some space, you should always set a pointer to NULL. Otherwise, it contains random data and could potentially lead to runtime problems if later code tries to use the pointer for anything before a malloc or a null assignment. Answer 2: You are correct, no. In fact, you should definitely NOT malloc space for newword->next because you will assign an existing address to it. However, you should (and have) assigned NULL to it shortly after creating it.
    – Cliff B
    Jul 27 '15 at 1:22

You must log in to answer this question.

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