I'm trying to implement a "stack" type, and the professor provided the stack.h file and most of the reverse.c code , and my job was to implement stack.c and complete reverse.c. Valgrind says that some memory is leaking but I can't find the error. The code is as follows:
stack.h
/**
* @file stack.h
* @brief TAD Stack definition
*/
#ifndef __STACK_H__
#define __STACK_H__
#include <stdbool.h>
/**
* @brief Stack type definition
*/
typedef struct _s_stack *stack;
/**
* @brief Stack elements type definition
*/
typedef int stack_elem;
/**
* @brief Creates an empty stack
* @return An empty stack
*/
stack stack_empty();
/**
* @brief Inserts an element at the top of the stack
* @param s A stack
* @param e An element to push into the stack
* @return The new stack with 'e' at the top
*/
stack stack_push(stack s, stack_elem e);
/**
* @brief Removes the element at the top of the stack
* @param s A stack
* @return The new stack with the top element removed
* @note Only applies to non-empty stacks
*/
stack stack_pop(stack s);
/**
* @brief Returns the size of the stack
* @param s A stack
* @return The size of the stack
*/
unsigned int stack_size(stack s);
/**
* @brief Returns the element at the top of the stacks
* @param s A stacks
* @return The element at the top of the stack
* @note Only applies to non-empty stacks
*/
stack_elem stack_top(stack s);
/**
* @brief Check if the given stack is empty
* @param s A stack
* @return true if the stack is empty, false otherwise
*/
bool stack_is_empty(stack s);
/**
* @brief Creates an array with all the elements of the stack
* @param s A stack
* @return An array containing all the elements of the stack. The stack top element
* becomes the rightmost element of the array. The size of the resulting
* array is determined by 'stack_size(s)'
*/
stack_elem *stack_to_array(stack s);
/**
* @brief Destroys the stack
* @param s A stack
* @note All memory resources are freed
*/
stack stack_destroy(stack s);
#endif
stack.c
#include <stdlib.h>
#include <assert.h>
#include "stack.h"
typedef struct _n_node *node;
struct _n_node
{
stack_elem elem;
node next;
};
struct _s_stack {
node first;
unsigned int size;
};
static node create_node(stack_elem e) {
node new_node=malloc(sizeof(struct _n_node));
assert(new_node!=NULL);
new_node->elem = e;
new_node->next = NULL;
return new_node;
}
static node destroy_node(node kill) {
kill->next=NULL;
free(kill);
kill=NULL;
return kill;
}
stack stack_empty() {
stack new_stack;
new_stack = malloc(sizeof(struct _s_stack));
new_stack->size = 0;
new_stack->first = NULL;
return new_stack;
}
stack stack_push(stack s, stack_elem e) {
node new_node = create_node(e);
new_node->next=s->first;
s->first=new_node;
s->size++;
return s;
}
stack stack_pop(stack s) {
assert(s->first!=NULL);
node killme = s->first;
s->first=s->first->next;
s->size--;
killme = destroy_node(killme);
return s;
}
unsigned int stack_size(stack s) {
return s->size;
}
stack_elem stack_top(stack s) {
assert (s->first!=NULL);
return s->first->elem;
}
bool stack_is_empty(stack s) {
return (s->first==NULL);
}
stack_elem *stack_to_array(stack s) {
stack_elem *array = NULL;
array = (stack_elem*)calloc((s->size), sizeof(struct _n_node));
for (int i = ((s->size)-1); i >= 0; --i) {
array[i]=stack_top(s);
s->first=s->first->next;
}
return array;
}
stack stack_destroy(stack s) {
node i=s->first;
while (i!=NULL)
{
node killme=i;
i=i->next;
killme=destroy_node(killme);
}
free(s);
s=NULL;
return s;
}
reverse.c
/* First, the standard lib includes, alphabetically ordered */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
/* Then, this project's includes, alphabetically ordered */
#include "array_helpers.h"
#include "../stack.h"
/* Maximum allowed length of the array */
static const unsigned int MAX_SIZE = 100u;
void print_help(char *program_name) {
/* Print the usage help of this program. */
printf("Usage: %s <input file path>\n\n"
"Sort an array given in a file in disk.\n"
"\n"
"The input file must have the following format:\n"
" * The first line must contain only a positive integer,"
" which is the length of the array.\n"
" * The second line must contain the members of the array"
" separated by one or more spaces. Each member must be an integer."
"\n\n"
"In other words, the file format is:\n"
"<amount of array elements>\n"
"<array elem 1> <array elem 2> ... <array elem N>\n\n",
program_name);
}
char *parse_filepath(int argc, char *argv[]) {
/* Parse the filepath given by command line argument. */
char *result = NULL;
if (argc < 2) {
print_help(argv[0]);
exit(EXIT_FAILURE);
}
result = argv[1];
return (result);
}
int main(int argc, char *argv[]) {
char *filepath = NULL;
/* parse the filepath given in command line arguments */
filepath = parse_filepath(argc, argv);
/* create an array of MAX_SIZE elements */
int array[MAX_SIZE];
/* parse the file to fill the array and obtain the actual length */
unsigned int length = array_from_file(array, MAX_SIZE, filepath);
printf("Original: ");
array_dump(array, length);
/* my code: */
int *new_array=NULL;
stack s = stack_empty();
for (int i=length; i>0; --i) {
s = stack_push (s, array[i-1]);
}
new_array = stack_to_array(s);
printf("Reversed: ");
array_dump(new_array, length);
stack_destroy(s);
free(new_array);
/* end of my code */
return (EXIT_SUCCESS);
}
When running through valgrind, I get the following transcript:
$ valgrind -s --leak-check=full ./reverse ./input/example-easy.in
==81== Memcheck, a memory error detector
==81== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==81== Using Valgrind-3.21.0 and LibVEX; rerun with -h for copyright info
==81== Command: ./reverse ./input/example-easy.in
==81==
Original: [1, 2, 3, 4, 5]
Reversed: [5, 4, 3, 2, 1]
==81==
==81== HEAP SUMMARY:
==81== in use at exit: 80 bytes in 5 blocks
==81== total heap usage: 10 allocs, 5 frees, 5,768 bytes allocated
==81==
==81== 80 (16 direct, 64 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==81== at 0x484880F: malloc (vg_replace_malloc.c:431)
==81== by 0x1092E1: create_node (stack.c:19)
==81== by 0x1093B8: stack_push (stack.c:42)
==81== by 0x1097F0: main (reverse.c:61)
==81==
==81== LEAK SUMMARY:
==81== definitely lost: 16 bytes in 1 blocks
==81== indirectly lost: 64 bytes in 4 blocks
==81== possibly lost: 0 bytes in 0 blocks
==81== still reachable: 0 bytes in 0 blocks
==81== suppressed: 0 bytes in 0 blocks
==81==
==81== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)```
The problem exists due to this invalid function
stack_elem *stack_to_array(stack s) {
stack_elem *array = NULL;
array = (stack_elem*)calloc((s->size), sizeof(struct _n_node));
for (int i = ((s->size)-1); i >= 0; --i) {
array[i]=stack_top(s);
s->first=s->first->next;
}
return array;
}
For starters there is no need to allocate the array with the element size equal to sizeof(struct _n_node) because you are storing in the array elements
array[i]=stack_top(s);
of the type stack_elem that is an alias of the type int
typedef int stack_elem;
The second problem is that due to this statement
s->first=s->first->next;
the data member first is changed and pointers to allocated nodes are lost but nodes themselves in the stack are not deleted that results in numerous memory leaks. You need to use an auxiliary pointer variable to traverse the stack.
For example the function can look the following way
stack_elem * stack_to_array( stack s )
{
stack_elem *array = NULL;
if ( !stack_is_empty( s ) )
{
array = calloc( s->size, sizeof( stack_elem ) );
if ( array != NULL )
{
node current = s->first;
for ( int i = s->size ; i-- != 0; )
{
array[i] = current->elem;
current = current->next;
}
}
}
return array;
}