Freeing memory allocated in simple linked list - C

Question

I'm having a problem freeing the memory allocated in a simple linked list implementation in C. Valgrind is telling me I have not freed everything but I am unable to figure out where the problem lies. My code and valgrind output is below:

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

typedef struct node {
    int value;
    struct node *next;
} node_t;

void insert(node_t *head, int num) {

    // Create new node to insert
    node_t *item = malloc(sizeof(node_t));
    item = malloc(sizeof(node_t));
    if (item == NULL) {
        exit(2);
    }
    item->value = num;

    // Insert new node at end of list
    node_t *cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = item;
}

int main(int argc, char *argv[]) {

    // Create head or root node
    node_t *head;
    head = malloc(sizeof(node_t));
    head->value = 0;
    head->next = NULL;

    // Insert nodes to end of list
    insert(head, 1);


    // Traverse list and print out all node values
    node_t *cur = head;
    while (cur != NULL) {
        printf("%d\n", cur->value);
        cur = cur->next;
    }

    // Free the list
    cur = head;
    node_t *previous;
    while (cur != NULL) {
        previous = cur;
        cur = cur->next;
        free(previous);
    }

    return 0;

}

// EOF

Valgrid shows the following error

    ==9054== Memcheck, a memory error detector
    ==9054== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
    ==9054== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
    ==9054== Command: ./linkedlist
    ==9054== 
    0
    1
    ==9054== Conditional jump or move depends on uninitialised value(s)
    ==9054==    at 0x100000ED0: main (in ./linkedlist)
    ==9054==  Uninitialised value was created by a heap allocation
    ==9054==    at 0x100008EBB: malloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==9054==    by 0x100000E03: insert (in ./linkedlist)
    ==9054==    by 0x100000EBF: main (in ./linkedlist)
    ==9054== 
    ==9054== Conditional jump or move depends on uninitialised value(s)
    ==9054==    at 0x100000F0E: main (in ./linkedlist)
    ==9054==  Uninitialised value was created by a heap allocation
    ==9054==    at 0x100008EBB: malloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==9054==    by 0x100000E03: insert (in ./linkedlist)
    ==9054==    by 0x100000EBF: main (in ./linkedlist)
    ==9054== 
    ==9054== 
    ==9054== HEAP SUMMARY:
    ==9054==     in use at exit: 26,456 bytes in 193 blocks
    ==9054==   total heap usage: 274 allocs, 81 frees, 32,608 bytes allocated
    ==9054== 
    ==9054== 16 bytes in 1 blocks are definitely lost in loss record 5 of 65
    ==9054==    at 0x100008EBB: malloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
    ==9054==    by 0x100000DF0: insert (in ./linkedlist)
    ==9054==    by 0x100000EBF: main (in ./linkedlist)
    ==9054== 
    ==9054== LEAK SUMMARY:
    ==9054==    definitely lost: 16 bytes in 1 blocks
    ==9054==    indirectly lost: 0 bytes in 0 blocks
    ==9054==      possibly lost: 0 bytes in 0 blocks
    ==9054==    still reachable: 0 bytes in 0 blocks
    ==9054==         suppressed: 26,440 bytes in 192 blocks
    ==9054== 
    ==9054== For counts of detected and suppressed errors, rerun with: -v
    ==9054== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 18 from 18)

Answer 1

While you are free to allocate for head outside of insert as you have done, you will generally pass the address of head to insert instead, so that head can be allocated and assigned in insert and have the pointer value retained and visible to main.

Basic issue. When you pass a pointer to a function, the function receives a copy of the pointer with its very own (and very different) address. In order to allocate the first node (e.g. head), you must pass the address of head to insert, otherwise you allocate memory and assign the address for the memory block to the copy of head in insert and on return to main, the original pointer for head remains NULL.

The prototype for insert passing the address of head would become, e.g.

void insert (node_t **head, int num)

and you would call insert from main as:

    insert (&head, tmp);

(this is only a problem for the first node, because after head is allocated, the copy of the pointer received by insert may have its own address, but it contains the very same address for the first node in either main or insert)

If you are allocating for the first node in a function and you are not returning the node address for assignment in the caller, you generally want to pass the address of the list to your insert function.

Other issues

When inserting values into a linked-list you must handle two conditions. (actually 3 if you want to optimize out an unnecessary call to the loop). Those are insertion of the first node and insertion of all others. (you can check for insertion of the second node as there is no need to set up a traversal of nodes in that case). To handle all three cases, your insert would something look like the following:

void insert (node_t **head, int num)
{
    /* Create new node to insert */
    node_t *node = calloc (1, sizeof *node);
    if (node == NULL) {
        fprintf (stderr, "error: virtual memory exhusted.\n");
        exit (2);
    }
    node->value = num;
    node->next = NULL;

    /* Insert node at end */
    if (!(*head))               /* handle first node */
        *head = node;
    else if (!(*head)->next)    /* handle second     */
        (*head)->next = node;
    else {                      /* handle remaining  */
        node_t *cur = *head;
        while (cur->next)
            cur = cur->next;
        cur->next = node;
    }
}

Your free is likewise a bit awkward as you generally check whether ->next is allocated to make a decision regarding the current node and then clean up the straggler outside of the loop. (this is largely up to you, I just present the alternative below, my iter is your cur and my victim is your previous)

    /* Free the list */
    iter = head;
    while (iter->next) {
        node_t *victim = iter;
        iter = iter->next;
        free (victim);
    }
    if (iter) free (iter);

Finally, with valgrind you may get the error regarding basing a jump on an uninitialized valued when using malloc (your options are to use malloc then memset, or simply use calloc -- which both allocates and sets the new memory to 0/NULL)

Putting all the pieces together, you could do something like the following to resolve the issues:

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

typedef struct node {
    int value;
    struct node *next;
} node_t;

void insert (node_t **head, int num)
{
    /* Create new node to insert */
    node_t *node = calloc (1, sizeof *node);
    if (node == NULL) {
        fprintf (stderr, "error: virtual memory exhusted.\n");
        exit (2);
    }
    node->value = num;
    node->next = NULL;

    /* Insert node at end */
    if (!(*head))               /* handle first node */
        *head = node;
    else if (!(*head)->next)    /* handle second     */
        (*head)->next = node;
    else {                      /* handle remaining  */
        node_t *cur = *head;
        while (cur->next)
            cur = cur->next;
        cur->next = node;
    }
}

int main (void) {

    int tmp;
    node_t *head = NULL, *iter = NULL;

    /* Insert nodes to end of list (from stdin) */
    while (scanf (" %d", &tmp) == 1)
        insert (&head, tmp);

    /* Traverse list and print out all node values */
    iter = head;
    while (iter) {
        printf ("%d\n", iter->value);
        iter = iter->next;
    }

    /* Free the list */
    iter = head;
    while (iter->next) {
        node_t *victim = iter;
        iter = iter->next;
        free (victim);
    }
    if (iter) free (iter);

    return 0;
}

Example Input Data

$ cat ../dat/10int_nl.txt
8572
-2213
6434
16330
3034
12346
4855
16985
11250
1495

Example Use/Output

$ valgrind ./bin/llvalgrind <../dat/10int_nl.txt
==31935== Memcheck, a memory error detector
==31935== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==31935== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==31935== Command: ./bin/llvalgrind
==31935==
8572
-2213
6434
16330
3034
12346
4855
16985
11250
1495
==31935==
==31935== HEAP SUMMARY:
==31935==     in use at exit: 0 bytes in 0 blocks
==31935==   total heap usage: 10 allocs, 10 frees, 160 bytes allocated
==31935==
==31935== All heap blocks were freed -- no leaks are possible
==31935==
==31935== For counts of detected and suppressed errors, rerun with: -v
==31935== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 1 from 1)

Look over all the solutions, and let me know if you have any questions.

Answer 2

Inside your insert():

// Create new node to insert
node_t *item = malloc(sizeof(node_t));
item = malloc(sizeof(node_t));

you call malloc() twice on item, causing the first piece of memory allocated to be forever lost..

With that I mean that you haven't keep track of that memory chunk now, so at the end of your program, which is the last chance of freeing the memory you don't so, which results in memory being allocated, but never freed!

Imagine that the OS handles all the memory of your computer. Your program comes into play and asks for some memory. The OS gives you a pointer to that piece of memory it allocated for you (you have to release it when you do not need it anymore). That pointer has a value that we do not know apriori.

What you do with calling malloc() for the second time and assigning its return value to item, is to overwrite that unique pointer value (the address of the memory that you were given) and got a new address, pointing to the newly allocated memory.

So now you requested two memory chunks, but you only know the address of the second memory chunk. So how can you free the first chunk of memory when you don't know it's address?

You can't! And that's wrong, since it will result in a memory leak, as you show.

_{An analogy would be that the memory is a theater (like Epidaurus) and every seat is a cell of memory. The OS is the seat manager of the theater. You request a seat, the manager gives you one ID of the seat he assigned to you, and you write it down to an e-note. Then you request one more seat, the manager checks if there are still available seats in the theater, yes there are, so he gives one seat and of course a corresponding ID. You mistakenly write it over the e-note you had written the previous ID. So now you you know only the second ID, thus the 2nd seat and not the first ID, thus you are not aware where that seat is (the theater is large and you do not know much about it).}

---

However, this is not your only problem, when you "create" item, you assign a value, but you do not assign something to next. Go ahead and do:

item->value = num;
item->next = NULL;

---

After all that, you should be able to produce the following output:

C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall main.c
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out
0
1

Answer 3

You have two mallocs for each node. You only want one. You can leave the one in the declaration and drop the following line that duplicates the malloc and overwrites the first one.

Answer 4

In function insert, you allocate the structure twice:

node_t *item = malloc(sizeof(node_t));
item = malloc(sizeof(node_t));

The first one gets lost as you overwrite the pointer in item with the next allocation.

Furthermore, you do not initialize the next member of the newly allocated node, which causes the warnings issued by valgrind as you are dereferencing data that was not initialized.