invalid free() in stack using linked list

Good afternoon. I'm trying to debug a stack. I think the problem has something to do with free(old_element) and free(data) but I tried to do some modifications (commenting one of them) without success.

list.h

Code:

 
/* 
 * File:   list.h
 * Author: thames
 *
 * Created on 11 de Janeiro de 2013, 11:46
 */

#ifndef LIST_H
#define    LIST_H

#include <stdlib.h>

typedef struct ListElmt_{
    
  void* data; 
  struct ListElmt_* next;   
    
} ListElmt;

typedef struct List_ {
   
    int size;
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    ListElmt *head;
    ListElmt *tail;

} List;

void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List* list);
int list_ins_next(List* list, ListElmt* element, const void* data);
int list_rem_next(List* list, ListElmt* element, void** data);

/* macros */

#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head? 1 : 0);
#define list_is_tail(element) ((element)->next == NULL? 1 : 0);
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)

#endif    /* LIST_H */

list.c

Code:

 
#include <stdlib.h>
#include <string.h>
#include "list.h"

void list_init(List *list, void (*destroy)(void* data))
{
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
    
    return;
}


void list_destroy(List* list) 
{
    void* data; 
    /* remove each element */
    while(list_size(list) > 0)
    {
       if(list_rem_next(list, NULL, (void**)&data) == 0 && list->destroy != NULL)
       {
           /* call a user-defined function to free dynamically allocated data.*/
           list->destroy(data);
       }    
    }    
    /* no operations are allowed now, but clear the structure as a precaution */
    memset(list, 0, sizeof(list));
    return;
}

int list_ins_next(List* list, ListElmt* element, const void* data)
{
    ListElmt* new_element;
    /* allocate storage for the element */
    if((new_element = (ListElmt*)malloc(sizeof(ListElmt))) == NULL)
     return -1;
    /* insert the element into the list */
    new_element->data = (void*) data;
    if(element == NULL)
    {
        /* handle insertion at the head of the list */
        if(list_size(list) == 0)
          list->tail = new_element;
        
        new_element->next = list->head;
        list->head = new_element;
    }    
    else { 
      /* handle insertion somewhere other than at the head */  
      if(element->next == NULL)
        list->tail = new_element;   
      
      new_element->next = element->next;
      element->next = new_element;
    }
    /* adjust the size of the list to account for the inserted element */
    list->size++;
    return 0;
}

int list_rem_next(List* list, ListElmt* element, void **data)
{
    ListElmt *old_element;
    /* don't allow removal from an empty list */
    if(list_size(list) == 0)
       return -1;   
    /* remove the element from the list */
    if(element == NULL)
    {
      /* handle removal from the head of the list */ 
      *data = list->head->data;
      if(list_size(list) == 1)
        list->tail = NULL;   
    }
    else 
    {
      /* handle removal from somewhere other than the head */
      if(element->next == NULL)
        return -1; 
      
      *data = element->next->data; 
      old_element = element->next;
      element->next = element->next->next;
      
      if(element->next == NULL)
        list->tail = element;   
    }
    
    /* free the storage allocated by the abstract datatype */
    free(old_element);
    /* Adjust the size of the list to account for the removed element. */
    list->size--;
    return 0;
}

Code:

/* 
 * File:   stack.h
 * Author: thames
 *
 * Created on 11 de Janeiro de 2013, 11:48
 */

#ifndef STACK_H
#define STACK_H 

#include <stdlib.h>
#include "list.h"

/* implement stacks as linked lists */ 

typedef List Stack;

/* stack_init is the function list_init declared in list.h */
#define stack_init list_init
/* stack_destroy is the function list_destroy declared in list.h */
#define stack_destroy list_destroy 

int stack_push(Stack* stack, const void* data);
int stack_pop(Stack* stack, void** data);

#define stack_peek(stack) ((stack)->head == NULL ? NULL : (stack)->head->data)
#define stack_size list_size

#endif

Code:

#include <stdlib.h>
#include "stack.h"
#include "list.h"

int stack_push(Stack* stack, const void* data) 
{ 
   return list_ins_next(stack, NULL, data);    
}

int stack_pop(Stack* stack, void** data) 
{ 
   return list_rem_next(stack, NULL, data);       
}

Code:

/*****************************************************************************
*                                                                            *
*  ex-1.c                                                                    *
*  ======                                                                    *
*                                                                            *
*  Description: Illustrates using a stack (see Chapter 6).                   *
*                                                                            *
*****************************************************************************/

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

#include "list.h"
#include "stack.h"


/*****************************************************************************
*                                                                            *
*  ------------------------------ print_stack -----------------------------  *
*                                                                            *
*****************************************************************************/

static void print_stack(const Stack *stack) {

ListElmt           *element;

int                *data,
                   size,
                   i;

/*****************************************************************************
*                                                                            *
*  Display the stack.                                                        *
*                                                                            *
*****************************************************************************/

fprintf(stdout, "Stack size is %d\n", size = stack_size(stack));

i = 0;
element = list_head(stack);

while (i < size) {

   data = (int*) list_data(element);
   fprintf(stdout, "stack[%03d]=%03d\n", i, *data);
   element = list_next(element);
   i++;

}

return;

}

/*****************************************************************************
*                                                                            *
*  --------------------------------- main ---------------------------------  *
*                                                                            *
*****************************************************************************/

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

Stack              stack;

int                *data,
                   i;

/*****************************************************************************
*                                                                            *
*  Initialize the stack.                                                     *
*                                                                            *
*****************************************************************************/

stack_init(&stack, free);

/*****************************************************************************
*                                                                            *
*  Perform some stack operations.                                            *
*                                                                            *
*****************************************************************************/

fprintf(stdout, "Pushing 10 elements\n");

for (i = 0; i < 10; i++) {

   if ((data = (int *)malloc(sizeof(int))) == NULL)
      return 1;

   *data = i + 1;

   if (stack_push(&stack, data) != 0)
      return 1;

}

print_stack(&stack);

fprintf(stdout, "Popping 5 elements\n");

for (i = 0; i < 5; i++) {

   if(stack_pop(&stack, (void **)&data) == 0)
     free(data);
   else
      return 1;

}

print_stack(&stack);

fprintf(stdout, "Pushing 100 and 200\n");

if ((data = (int *)malloc(sizeof(int))) == NULL)
   return 1;

*data = 100;

if (stack_push(&stack, data) != 0)
   return 1;

if ((data = (int *)malloc(sizeof(int))) == NULL)
   return 1;

*data = 200;

if (stack_push(&stack, data) != 0)
   return 1;

print_stack(&stack);

if ((data = (int*) stack_peek(&stack)) != NULL)
   fprintf(stdout, "Peeking at the top element...Value=%03d\n", *data);
else
   fprintf(stdout, "Peeking at the top element...Value=NULL\n");

print_stack(&stack);

fprintf(stdout, "Popping all elements\n");

while (stack_size(&stack) > 0) {

   if (stack_pop(&stack, (void **)&data) == 0)
      free(data);
   
}

if ((data = (int*) stack_peek(&stack)) != NULL)
   fprintf(stdout, "Peeking at an empty stack...Value=%03d\n", *data);
else
   fprintf(stdout, "Peeking at an empty stack...Value=NULL\n");

print_stack(&stack);

/*****************************************************************************
*                                                                            *
*  Destroy the stack.                                                        *
*                                                                            *
*****************************************************************************/

fprintf(stdout, "Destroying the stack\n");
stack_destroy(&stack);

return 0;

}

Code:

thames@semath ~/NetBeansProjects/CStack $ valgrind ./a.out
==3304== Memcheck, a memory error detector
==3304== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==3304== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==3304== Command: ./a.out
==3304== 
Pushing 10 elements
Stack size is 10
stack[000]=010
stack[001]=009
stack[002]=008
stack[003]=007
stack[004]=006
stack[005]=005
stack[006]=004
stack[007]=003
stack[008]=002
stack[009]=001
Popping 5 elements
==3304== Conditional jump or move depends on uninitialised value(s)
==3304==    at 0x4C2A6EC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x400CB8: list_rem_next (list.c:92)
==3304==    by 0x4006C7: stack_pop (stack.c:12)
==3304==    by 0x40083E: main (stackapp.c:102)
==3304== 
==3304== Invalid free() / delete / delete[] / realloc()
==3304==    at 0x4C2A739: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x400CB8: list_rem_next (list.c:92)
==3304==    by 0x4006C7: stack_pop (stack.c:12)
==3304==    by 0x40083E: main (stackapp.c:102)
==3304==  Address 0x4ea1cdd is in the Text segment of /lib/x86_64-linux-gnu/libc-2.15.so
==3304== 
==3304== Invalid free() / delete / delete[] / realloc()
==3304==    at 0x4C2A739: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x40084E: main (stackapp.c:103)
==3304==  Address 0x51f15e0 is 0 bytes inside a block of size 4 free'd
==3304==    at 0x4C2A739: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x40084E: main (stackapp.c:103)
==3304== 
Stack size is 5
==3304== Invalid read of size 4
==3304==    at 0x400721: print_stack (stackapp.c:45)
==3304==    by 0x400870: main (stackapp.c:109)
==3304==  Address 0x51f15e0 is 0 bytes inside a block of size 4 free'd
==3304==    at 0x4C2A739: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x40084E: main (stackapp.c:103)
==3304== 
stack[000]=010
stack[001]=009
stack[002]=008
stack[003]=007
stack[004]=006
Pushing 100 and 200
Stack size is 7
stack[000]=200
stack[001]=100
==3304== Invalid read of size 4
==3304==    at 0x400721: print_stack (stackapp.c:45)
==3304==    by 0x400932: main (stackapp.c:129)
==3304==  Address 0x51f15e0 is 0 bytes inside a block of size 4 free'd
==3304==    at 0x4C2A739: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x40084E: main (stackapp.c:103)
==3304== 
stack[002]=010
stack[003]=009
stack[004]=008
stack[005]=007
stack[006]=006
Peeking at the top element...Value=200
Stack size is 7
stack[000]=200
stack[001]=100
==3304== Invalid read of size 4
==3304==    at 0x400721: print_stack (stackapp.c:45)
==3304==    by 0x4009A1: main (stackapp.c:136)
==3304==  Address 0x51f15e0 is 0 bytes inside a block of size 4 free'd
==3304==    at 0x4C2A739: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x40084E: main (stackapp.c:103)
==3304== 
stack[002]=010
stack[003]=009
stack[004]=008
stack[005]=007
stack[006]=006
Popping all elements
==3304== Conditional jump or move depends on uninitialised value(s)
==3304==    at 0x4C2A6EC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x400CB8: list_rem_next (list.c:92)
==3304==    by 0x4006C7: stack_pop (stack.c:12)
==3304==    by 0x4009D4: main (stackapp.c:142)
==3304== 
==3304== Invalid free() / delete / delete[] / realloc()
==3304==    at 0x4C2A739: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x400CB8: list_rem_next (list.c:92)
==3304==    by 0x4006C7: stack_pop (stack.c:12)
==3304==    by 0x4009D4: main (stackapp.c:142)
==3304==  Address 0x4ea1cdd is in the Text segment of /lib/x86_64-linux-gnu/libc-2.15.so

Useful valgrind flag

--db-attach=no|yes start debugger when errors detected? [no]

The first 3 errors from valgrind gave you this stack trace:

Code:

==3304==    at 0x4C2A6EC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x400CB8: list_rem_next (list.c:92)
==3304==    by 0x4006C7: stack_pop (stack.c:12)
==3304==    by 0x40083E: main (stackapp.c:102)

In list.c, line 92 you call free(old_element), but old_element doesn't refer to memory that was allocated, hence the error. Remember, in C, local variables have garbage data from the stack if left uninitialized. Take a look at the list_rem_next function, and see if you can figure out how you're getting to that free call without giving old_element a value. Note, initializing old_element to something like NULL is not the solution.

I forgot, there were two problems:

Code:

==3304== Invalid read of size 4
==3304==    at 0x400721: print_stack (stackapp.c:45)
==3304==    by 0x400870: main (stackapp.c:109)
==3304==  Address 0x51f15e0 is 0 bytes inside a block of size 4 free'd
==3304==    at 0x4C2A739: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3304==    by 0x40084E: main (stackapp.c:103)

Those are because your head is not correct after you pop (remove the first) element. So when you fix the above error, make sure you also correctly update the head of your list to reflect the new list.

Take a look at the list_rem_next function, and see if you can figure out how you're getting to that free call without giving old_element a value. Note, initializing old_element to something like NULL is not the solution.

I think I understood this problem: I'm passing NULL as an element for popping and pushing. If you look to the usual implementation of the stacks, this is incorrect since you need to pass the current element (after all, I'm pushing after the current node and removing after the current node. Now I'm trying to figure out how to do this. I tried to use the head of the stack list But, as I suspected, I don't get anywhere because I'm not moving the pointers.

Your remove function removes the node after the node pointed to by element. So what do you pass if you want to remove the first node of the list? There's no node before it (it's the first), so you can't pass in an element which has the first node after it. That is why you pass in NULL to remove the first (head) element. Thus, old_element needs to be set to list->head (what you're removing), and list->head needs to be updated to point to it's next element.

Originally Posted by anduril462

.That is why you pass in NULL to remove the first (head) element.

Now I'm a bit lost. How can the head be the top (the first popped element) of the stack?

EDIT: The stupid syntax highlighter for the code tags is removing leading white space. If you clidk the "To plain text" button, everything will line up properly

Your stack_push funciton uses list_ins_next as the list insert function, and passes NULL as the second parameter, 'element'. In list_ins_next:

Code:

    if(element == NULL)
    {
        /* handle insertion at the head of the list */
        if(list_size(list) == 0)
          list->tail = new_element;


        new_element->next = list->head;
        list->head = new_element;
    }

See that comment? That is telling you what the function does when element == NULL. It inserts it at the beginning, and makes list->head point to the new element inserted. I'll run through a couple stack_push calls so you can see. Then, you will know how to trace such code on your own when you need to understand or debug something.

Start with an empty list:

Code:

list->head ---> NULL
list->tail ---> NULL
list->size = 0

Now you insert an element

Code:

stack_push(stack, data);  // assume data is 1
// this is really just a call to
list_ins_next(stack, NULL, data);

So working our way through the list_ins_next function, we allocate a node, and set the data element

Code:

                    +---+
new_element ------> | 1 | ----------> (uninitialized, pointing to garbage)
                    +---+   (next)

element is NULL, so we enter that if-block
list->size is 0, so we also enter that if block, and set tail to point to our new element

Code:

                    +---+
new_element ------> | 1 | ----------> (uninitialized, pointing to garbage)
                    +---+   (next)
                       ^
list->head ---> NULL   |
list->tail ------------+
list->size = 0

now, we update new_element->next to point to whatever list->head is pointing to (NULL)

Code:

                    +---+
new_element ------> | 1 | ----------> NULL
                    +---+   (next)
                       ^
list->head ---> NULL   |
list->tail ------------+
list->size = 0

next line updates list->head to point to the new element

Code:

                    +---+
new_element ------> | 1 | ----------> NULL
                    +---+   (next)
                     ^ ^
list->head ----------+ |
list->tail ------------+
list->size = 0

we're done with the if block, so drop below the else, update list->size, and return (new_element drops out of scope here)

Code:

                    +---+
new_element ------> | 1 | ----------> NULL
                    +---+   (next)
                     ^ ^
list->head ----------+ |
list->tail ------------+
list->size = 1

Now, let's push another element, 2, onto the stack. This will be the "fast forward version". We start with our existing list and allocate a new node

Code:

                 +---+                  +---+
new_element ---> | 2 | ---> (garbage)   | 1 | ----------> NULL
                 +---+                  +---+   (next)
                                         ^ ^
list->head ------------------------------+ |
list->tail --------------------------------+
list->size = 1

Again, element is NULL, so we enter the if block, but this time size is not 0, so we skip updating list->tail, it still points to node 1. The other two statements in that block do the following:

Code:

                 +---+             +---+
new_element ---> | 2 | ----------> | 1 | ----------> NULL
                 +---+   (next)    +---+   (next)
                   ^                 ^
list->head --------+                 |
list->tail --------------------------+
list->size = 1

Then we update list->size

Code:

                 +---+             +---+
new_element ---> | 2 | ----------> | 1 | ----------> NULL
                 +---+   (next)    +---+   (next)
                   ^                 ^
list->head --------+                 |
list->tail --------------------------+
list->size = 2

And we're all done. Run through a few more push and pop calls on paper, one line of code at a time, to see exactly how the list changes at each step.

wow thank you for the incredible effort to explain me stacks with linked lists. I'm also watching some videos on youtube about the subject.

You're welcome

I understood your explanation anduril. Many thanks.
I copied a code from the videos I watched (a simpler version of a linked stack):

Code:

 
/* 
 * File:   stack.h
 * Author: thames
 *
 * Created on 11 de Janeiro de 2013, 17:33
 */

#ifndef STACK_H
#define    STACK_H

#include <stdlib.h>
/* stack with linked list */

typedef struct Element_ { 
    
   struct Element_* next;  
   void* data; 

} Element;

int push(Element** stack, void* data);
int pop(Element** stack, void** data);
int createStack(Element** stack);
int deleteStack(Element** stack);

/* macros */

#define stack_data(stack) ((stack)->data)

#endif    /* STACK_H */

Code:

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

int createStack(Element** stack)
{
    *stack = NULL; 
    return 0;
}

int push(Element** stack, void* data) 
{ 
   Element* elem;
   if( (elem = (Element*) malloc(sizeof(Element))) == NULL)
     return 1;   
   
   elem->data = data;
   elem->next = *stack;
   *stack = elem;
   return 0;
}

int pop(Element** stack, void** data)
{
   Element* elem;
   elem = *stack;
   if(!elem)
      return 1;
   *stack = elem->next;
   *data  = elem->data;
   free(elem);
   return 0; 
}

int deleteStack(Element** stack)
{
    Element* next; 
    while(*stack)
    {
        next = (*stack)->next;
        free(*stack);
        *stack = next;
    }    
    return 0;
}

Code:

/* 
 * File:   stackapp.c
 * Author: thames
 *
 * Created on 12 de Janeiro de 2013, 09:48
 */

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

int main() {

    Element* stack;
    int i = 5;
    int* o; 
    
    createStack(&stack);
    if(push(&stack, &i) == 1)
      fprintf(stdout, "Can't push\n");
    if(pop(&stack, (void*) &o) == 1)
      fprintf(stdout, "Can't pop\n");
    
    printf("popped: %d\n", *o);
    return EXIT_SUCCESS;    
}

Also, I understood why we need to use pointers to pointers. We do that so we don't lose track of the stack when we're updating its nodes.

It seems you understand it.

When I was in first semester, we were introduced simple linked list with this program. It has many comments and I think it deserves a look. Now there is no indentation, so copy paste the code into your IDE. I will fix it hopefully. ( too bad is not my domain, so I can't apply much css on it).
I don't post the code here, because it might be a bit big.

Also, don't cast what malloc returns.

Now the code must be indented correct