Difference between free() function with or without malloc

Question

This is part of cs50 pset5 speller. Background is that I load a dictionary into a hash table with linked list and check word against the hash table to decide if that word is in the dictionary, after that I unload the hash table.

When I load the dictionary, I used malloc() and free() to insert a node into the linked list. The result of free() here is that it free the memory allocated to a pointer, but it will not remove the pointee (a node inserted into linked list in this case). Here is my code:

bool load(const char *dictionary)
{
    FILE *inputfile = fopen(dictionary, "r");
    if (inputfile == NULL)
    {
        return false;
    }

    char tempWord[LENGTH+1];

    while (fscanf(inputfile, "%s", tempWord) != EOF)
    {
        //create a tempNode and make sure
        node *tempNode = malloc(sizeof(node));
        if (tempNode == NULL)
        {
            return false;
        }

        strcpy(tempNode->word, tempWord);
        tempNode->next = NULL;

        //get the index of this word
        int index = hash(tempWord);

        //move tempNode to the next node in the linked list
        if (table[index]->next != NULL)
        {
            tempNode->next = table[index];
        }

        table[index]->next = tempNode;

        free(tempNode);

        word_count ++;
    }
    fclose(inputfile);

    return true;
}

When I unload the dictionary, I used free() again, but this time without calling malloc() at all. So the elements on the linked list can be freed one after another. The result of free() here is that it 'removes' the node from the linked list. Here is my code:

bool unload(void)
{
    for (int i = 0; i < N; i ++)
    {
        //freeing linked list, we need two tempNode in order to do this
        node *tempPtr = table[i];
        while (tempPtr != NULL)
        {
            node *deletePtr = tempPtr;
            tempPtr = tempPtr->next; //move the tempPtr to the next element, so we are note losing the linked list
            free(deletePtr); //once we moved the tempPtr to the next element, now we can delete where deletePtr is pointing at
        }
    }
    return true;
}

Although my code was compiled and can run without issue, I am very confused of why free() does different things here.

To summarize my questions:

(1)Am I correct to say that: in 'load', free(tempNode) does not 'erase' what tempNode is pointing to (which is a node in a linked list), but only free the memory allocated to tempNode; in 'unload', however, free(deletePtr) 'erase' both deletePtr and what deletePtr is pointing to (which is a node in a linked list)?

(2) If my observation in (1) is correct, why is free() doing different things here? Is that caused by the fact that load called malloc() and unload didn't?

(3) I understand I have to call free() if I called malloc(), but when malloc() isn't called, what does free() do?

================================= Edit: After more research, I realized that in load section, it is unnecessary to free() the memory assigned by malloc(). The reason is, in unload section, by free() each node, I will eventually be able to free the memory assigned before.

It's very straight forward. Every malloc has to have exactly one free. Not two, not zero, not anything else - exactly one. And the pointer passed to free must be the exact pointer returned by malloc. The malloc and the free don't need to be called in the same function or at the same time. But at some point in the program there should be one free for each malloc. — kaylum
free does not "remove the node from the list". Your program must remove the node from the list, and once you've done that you call free to tell the system that you are no longer using that memory. — William Pursell

John Bollinger John Bollinger · Accepted Answer · 2020-10-02T22:30:03

(1)Am I correct to say that: in 'load', free(tempNode) does not 'erase' what tempNode is pointing to (which is a node in a linked list), but only free the memory allocated to tempNode;

The object to which tempNode points is not meaningfully distinguished from the memory occupied by the object to which tempNode points. If that is a block of dynamically allocated memory then you must not attempt to access it after freeing it. Any attempt to do so produces undefined behavior.

The question is thus meaningless. There is no conforming way to tell whether the memory in question has been "erased", because you must not attempt to read it. If you do attempt to read it then the program might behave as if the memory had been overwritten in some way, or it might not. And it might do anything else within its power, too. Crashing the program (eventually) is a popular alternative, but by no means a guaranteed one.

in 'unload', however, free(deletePtr) 'erase' both deletePtr and what deletePtr is pointing to (which is a node in a linked list)?

See above.

(2) If my observation in (1) is correct [...]

Observation (1) is not correct.

(3) I understand I have to call free() if I called malloc(), but when malloc() isn't called, what does free() do?

The free() function has undefined behavior (see above) if it is passed a pointer value that is non-null and was not obtained from a memory allocation function, or one that has already been freed.

Difference between free() function with or without malloc

1 Answers