Я не могу найти, где мой код C имеет утечки памяти

Я пытаюсь реализовать тип «стек», и профессор предоставил файл stack.h и большую часть кода reverse.c, а моя работа заключалась в реализации stack.c и завершении reverse.c. Valgrind говорит, что какая-то утечка памяти, но я не могу найти ошибку. Код выглядит следующим образом:

стек.ч

/**
*  @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

стек.с

#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;
}

реверс.с

/* 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);
}

При запуске через valgrind я получаю следующую расшифровку:

$ 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)```

Вместо typedef struct _n_node *node; учитывайте typedef struct _n_node node; и не скрывайте, что node является указателем. Это упрощает понимание и поддержку кода.

chux - Reinstate Monica 01.06.2023 00:55
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
1
57
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Проблема существует из-за этой недопустимой функции

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;
}

Для начала нет необходимости выделять массив с размером элемента, равным sizeof(struct _n_node), потому что вы сохраняете в массиве элементы

array[i]=stack_top(s);

типа stack_elem, который является псевдонимом типа int

typedef int stack_elem;

Вторая проблема заключается в том, что из-за этого утверждения

s->first=s->first->next;

член данных first изменяется и указатели на выделенные узлы теряются, но сами узлы в стеке не удаляются, что приводит к многочисленным утечкам памяти. Вам нужно использовать вспомогательную переменную-указатель для обхода стека.

Например, функция может выглядеть следующим образом

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;
}

Я понимаю, что в примере решения используется array = calloc( s->size, sizeof( stack_elem ) );, чтобы сделать маленькие шаги в предложении решения для OP, но я бы предпочел array = calloc( s->size, sizeof array[0]);, поскольку его легче кодировать, проверять и поддерживать. УФ.

chux - Reinstate Monica 01.06.2023 01:07

Другие вопросы по теме