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