0

I'm trying to write very simple function that updates elements of linked list in place while filtering out (and freeing) some of the elements. I've been able to derive this implementation though according to valgrind it contains invalid free as well as memory leak. I wonder what is wrong with the implementation.

#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 output is:

==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)
  • It would be helpful to share what valgrind has found. – kaylum Jan 9 at 23:07
  • @Marek Fajkus At least use normal names instead of these silly names of data members typedef struct List { int head; struct List *tail; } List; – Vlad from Moscow Jan 9 at 23:07
  • You don't need the typecast in t = (List *)t->tail;. It's already the correct type. – Barmar Jan 9 at 23:14
  • 1
    @vlad car and cdr? – Antti Haapala Jan 9 at 23:24
  • 1
    You are freeing &init, it wasn't allocated by malloc. – KamilCuk Jan 9 at 23:48
1

what is wrong with the implementation.

You are passing the address of init to free. init is a variable with auto storage duration not allocated with malloc, so you can't free it.

Because initially t = &init, then inside the first call to cons you do new_t->tail = t you effectively do new_t->tail = &init. So after all the cons calls the last element in your chain points to &init.

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

Inside your loop then you pass address of &init to the free function.

I would say the implementation is actually ok, the allocation of the first element is wrong.

I suggest, just remove the init and create the first chain with malloc too:

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

free(NULL) does nothing. You can replace if (tmp != NULL) free(tmp); with just free(tmp).

  • I've approved the answer as it indeed resolved the main thing that I missed which which was the free of the value allocated on stack within the main. Though even with these chages the vagrind still reports there is an leak of 16bytes. if you can spot the error @KamilCuk please let me know. Otherwise I still consider this to be the right answer given it resolves the major issue. – Marek Fajkus Jan 10 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.