C lang "карта фильтра" реализация с бесплатным - PullRequest
Новая
       44

C lang "карта фильтра" реализация с бесплатным

0 голосов
/ 10 января 2020

Я пытаюсь написать очень простую функцию, которая обновляет элементы связанного списка на месте, отфильтровывая (и освобождая) некоторые элементы. Я смог вывести эту реализацию, хотя в соответствии с 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)

1 Ответ

1 голос
/ 10 января 2020

что не так с реализацией.

Вы передаете адрес от init до free. init - это переменная с продолжительностью автоматического хранения, не выделенной с malloc, поэтому вы не можете free ее.

Поскольку сначала t = &init, то внутри первого вызова cons вы делаете new_t->tail = t вы эффективно делаете new_t->tail = &init. Таким образом, после того, как все cons вызовет последний элемент в вашей цепочке, будет указывать на &init. 

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

Внутри вашего l oop, тогда вы передадите адрес &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).

...