带有免费功能的C lang“过滤器映射”实现

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

实现有什么问题。

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

因为最初是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)。