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)
t = (List *)t->tail;. It's already the correct type. – Barmar Jan 9 at 23:14carandcdr? – Antti Haapala Jan 9 at 23:24&init, it wasn't allocated by malloc. – KamilCuk Jan 9 at 23:48