C lang "filter map"实现与免费

Question

我正在尝试编写非常简单的函数，该函数可以在过滤(并释放)某些元素的同时更新链表的元素。我已经能够导出这个实现，尽管根据 valgrind 它包含无效的空闲以及内存泄漏。我想知道实现有什么问题。

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

typedef struct List {
  int head;
  struct List *tail;
} List;

List *cons(int h, List *tail)
{
  List *list = malloc(sizeof(List));
  list->head = h;
  list->tail = (struct List*) tail;

  return list;
}

bool is_odd(int val)
{
  return val % 2 != 0;
}

int square(int val)
{
  return val * val;
}

void print_list(List *l)
{
  while (l) {
    printf("item: %d, ", l->head);
    l = (List*) l->tail;
  }

  printf("\n");
}

List *square_odd(List *list)
{
  List *new_head = NULL;
  List *prev_head = NULL;

  while (list != NULL) {
    List *next = (List *) list->tail;
    if (is_odd(list->head)) {
      if (new_head == NULL) new_head = list;
      if (prev_head != NULL) prev_head->tail = (struct List*) list;
      list->head = square(list->head);
      prev_head = list;
    } else {
      if (next == NULL) {
        prev_head->tail = NULL;
      }
      free(list);
    }

    list = next;
  }

  return new_head;
}

int main()
{
  List *t = NULL;
  List init = {100, NULL};
  t = &init;
  t = cons(1, t);
  t = cons(2, t);
  t = cons(3, t);
  t = cons(4, t);
  t = cons(5, t);
  t = cons(6, t);
  t = cons(7, t);
  t = cons(8, t);

  t = square_odd(t);

  List *tmp = NULL;
  print_list(t);

  while(t->tail != NULL) {
    tmp = t;
    t = (List*) t->tail;
    if (tmp != NULL) free(tmp);
  }

  return 0;
}

valgrind 输出为:

==17692== Memcheck, a memory error detector
==17692== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==17692== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==17692== Command: ./main
==17692== 
==17692== Invalid free() / delete / delete[] / realloc()
==17692==    at 0x4835948: free (in /nix/store/wrj8cjkfqzi0qlwnigx8vxwyyfl01lqq-valgrind-3.15.0/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17692==    by 0x40127D: square_odd (in /tmp/linked/main)
==17692==    by 0x401371: main (in /tmp/linked/main)
==17692==  Address 0x1ffeffeac0 is on thread 1's stack
==17692==  in frame #2, created by main (???:)
==17692== 
item: 49, item: 25, item: 9, item: 1, 
==17692== 
==17692== HEAP SUMMARY:
==17692==     in use at exit: 16 bytes in 1 blocks
==17692==   total heap usage: 9 allocs, 9 frees, 1,152 bytes allocated
==17692== 
==17692== LEAK SUMMARY:
==17692==    definitely lost: 16 bytes in 1 blocks
==17692==    indirectly lost: 0 bytes in 0 blocks
==17692==      possibly lost: 0 bytes in 0 blocks
==17692==    still reachable: 0 bytes in 0 blocks
==17692==         suppressed: 0 bytes in 0 blocks
==17692== Rerun with --leak-check=full to see details of leaked memory
==17692== 
==17692== For lists of detected and suppressed errors, rerun with: -s
==17692== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Answer 1

what is wrong with the implementation.

您正在将 init 的地址传递给 free。 init 是一个具有自动存储期限的变量，未使用 malloc 分配，因此您无法释放它。

因为最初t = &init，然后在第一次调用cons时，您执行了new_t->tail = t，您实际上执行了 >new_t->tail = &init.因此，在所有 cons 调用链中的最后一个元素指向 &init 后。

 t->tail-> ... ->tail->tail == &init

在循环内，将 &init 的地址传递给 free 函数。

我想说，实现实际上是可以的，第一个元素的分配是错误的。

我建议，只需删除 init 并使用 malloc 创建第一个链:

int main() {
   List *t = cons(100, NULL);
   t = cons(1, t);
   // the rest unchanged

free(NULL) 不执行任何操作。您可以将 if (tmp != NULL) free(tmp); 替换为 free(tmp)。