двусвязный список освобождает ошибку памяти valgrind

Question

Привет, я пытаюсь освободить память, которая была выделена в двусвязном списке, но когда я проверяю ее с помощью valgrind, у меня возникает ошибка в функции free_all (я думаю), но я не знаю, как этого избежать .

Я думаю, что в функции free_all я неправильно использую указатель temp и указатель узла или мне нужно сначала выделить его, а затем использовать их, но когда я попробовал этот метод, valgrind все равно выдал мне ошибку.

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

/*
  to compile it:
  gcc -g -Wall -ggdb3  double_linkedlist2.c -o double_linkedlist
  to check for memory leak and error:
  valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes --verbose --log-file=valgrind-out.txt ./double_linkedlist
*/
typedef struct listitem
{
  struct listitem *next;    // pointer to next item
  struct listitem *prev;    // pointer to previous item
  int data;                 // some data
} ITEM;


int main (void)
{
  // prototype functions
  void free_all (ITEM *lst_ptr);


  // Variables
  ITEM *p_temp, *head;

  head = malloc (sizeof (ITEM));  // head will keep first and last element in its pointers
  head -> next = head;            // the last element in the list (at first head -> next and head -> prev will point to the head)
  head -> prev = head;            // the first element in the list


     for (int i = 0; i < 3; i++)
       {
         p_temp = malloc (sizeof (ITEM));     // allocate some memory for the new list item
         p_temp -> data = i;                  // set the list item's data to the loop count so that we can see where it is in the list
         p_temp -> next = head -> next;          // this will insert at the FRONT of the list
         head -> next = p_temp;                  // and set the list head to the newly created list item
         p_temp -> prev = head;              // this will insert at the BACK of the list
         p_temp -> next -> prev = p_temp;       // and set the list 'tail' to the newly created item
       }

     // now let's see what we got going forward
     printf ("Going forward\n");
     p_temp = head -> next;

     while (p_temp != head)
       {
         printf ("forward list item: current is %p; next is %p; prev is %p; data is %d\n", p_temp, p_temp -> next, p_temp -> prev, p_temp -> data);
         p_temp = p_temp -> next;
       }

     // now let's see what we got going backward
     printf ("Going backwards\n");
     p_temp = head -> prev;

     while (p_temp != head)
       {
         printf ("backward list item; current is %p; next is %p; prev is %p; data is %d\n", p_temp, p_temp -> next, p_temp -> prev, p_temp -> data);
         p_temp = p_temp -> prev;
       }

     printf ("\n");
     free_all (head);

     return 0;
}

void free_all (ITEM *head)
{
  ITEM *temp, *node;

  node = head;

  while (node != head -> prev)
    {
      temp = node;
      printf ("freed list item: current is %p; next is %p; prev is %p; data is %d\n", temp, temp -> next, temp -> prev, temp -> data);
      node = node -> next;
      free (temp);
    }
  free (node);
  free (head);
}

Answer 1

После этой модификации не было ошибок или утечки памяти в valgrind

void free_all (ITEM *head)
{
  ITEM *temp, *node = NULL;

  node = head -> next;

  while (node != head -> prev)
    {
      temp = node;
      printf ("freed list item: current is %p; next is %p; prev is %p; data is %d\n", node, node -> next, node -> prev, node -> data);
      node = node -> next;
      free (temp);
    }

  node = head -> prev;
  printf ("freed list item: current is %p; next is %p; prev is %p; data is %d\n", node, node -> next, node -> prev, node -> data);
  free (head);
  free (node);
}

Answer 2

Это сообщение было написано mevets как редактирование моего решения, но я подумал, что было бы лучше включить это в ветку:

mevets:

Я бы склонялся к чему-то вроде:

void Unlink(ITEM **head, ITEM *t) {
        if (t->next == t) {
                /* remove head */
                *head = NULL;
        } else {
                t->prev->next = t->next;
                t->next->prev = t->prev;
                if (t == *head) {
                        *head = t->next;
                }
        }
}

/*
   remove and return the element after head
*/
ITEM *Pop(ITEM **head) {
        ITEM *node;
        if ((node = *head) != NULL) {
                node = node->next;
                Unlink(head, node);
        }
        return node;
}


void free_all (ITEM *head) {
        ITEM *node;
        while ((node = Pop(&head)) != NULL) {
            free(node);
        }
}

, которая отделяет ведение списка (Unlink) от упорядочивания (Pop) и управления памятью (free_all). Это оставляет вам больше границ, где вы можете делать утверждения о списке, например, до и после отмены связи, список должен быть действительным и может быть проверен. Кроме того, если был одновременный доступ к списку, вы можете заключить Pop () в блокировку, чтобы минимизировать конфликт.

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

Answer 3

ваш free_all содержит как минимум две ошибки: условие while ссылается на head-> prev, но на первой итерации вы освобождаете голову (используйте после free). после выхода из цикла вы освобождаете голову, несмотря на то, что она была бесплатной в первой итерации. free_all () работает для случая одного элемента.