mateusz.burger mateusz.burger - 19 days ago 10x
C Question

Free generic linked list in C - segfault

I am writing a generic linked list in C (following Kyle Loudon's book),
but when it comes to free it, I got a segfault.

Data types used for the list definition:

typedef struct list_elem_
void *data;
struct list_elem_ *next;
} list_elem;

typedef struct link_list_
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
list_elem *head;
list_elem *tail;
} link_list;

Function that is used to destroy caller's data:

void destroy_data(void *data)


Destroy passed by a function pointer:

void list_init(link_list *list, void (*destroy)(void *data))
list->size = 0;
list->destroy = destroy;
list->head = NULL;
list->tail = NULL;


Free the list:

void list_destroy(link_list *list)
void* data;

while(list_size(list) > 0)
if(list_rem_next(list, NULL, (void**)&data) == 0 && list->destroy != NULL)



The segfault is triggered by the free in the destroy_data.

============== EDIT ====================

Remove a list element

int list_rem_next(link_list *list, list_elem *element, void **data)
list_elem *OldElement;

if(list_size(list) ==0)
return -1;

/* Remove the head */
if(element == NULL)
*data = list->head->data;
OldElement = list->head;
list->head = list->head->next;

if(list_size(list) == 1)
list->tail = NULL;

/* Remove other than head */
} else {
if(element->next == NULL)
return -1;

*data = element->data;
OldElement = element->next;
element->next = element->next->next;

if(element->next == NULL)
list->tail = element;



return 0;

=================== EDIT 2 ==========================

Inside main

link_list myList;
int i;
int *iptr;
char *chrPtr;

list_init(&myList, destroy_data);

for(i = 0; i < 4; i++)
iptr = malloc(sizeof(int));
*iptr = i;
list_ins_next(&myList, NULL, iptr);

chrPtr = malloc(sizeof("uno\0"));
chrPtr = "uno\0";

chrPtr = malloc(sizeof("stringa numero due\0"));
chrPtr = "stringa numero due\0";

chrPtr = NULL;
iptr = NULL;




In your code from main() you have:

chrPtr = malloc(sizeof("uno\0"));
chrPtr = "uno\0";
  1. Why the explicit \0 when C adds one after it automatically?
  2. Can you say 'memory leak'? You allocate memory; you immediately overwrite the only pointer to that allocated memory by assigning the address of the string literal to the same pointer.
  3. What happened to strcpy()?

As a result of this abuse, you are passing unallocated memory pointers to free(); in fact, you're passing pointers to string constants to free(). That's undefined behaviour and can very easily lead to crashes!

The problem wasn't in the code you showed at first; it was in the other code. That's also why the MCVE (Minimal, Complete, Verifiable Example) — aka SSCCE (Short, Self-Contained, Correct Example) mentioned by Greg Hewgill — is so important. There's no way for us to debug code you don't show — and it is unnecessarily hard work establishing that the problem isn't in the code you do show.

You could probably use:

chrPtr = strdup("uno"));
list_ins_next(&myList, NULL, chrPtr);

chrPtr = strdup("stringa numero due");

to avoid the trouble. Failing that, you could use:

chrPtr = malloc(sizeof("uno"));
strcpy(chrPtr, "uno");
list_ins_next(&myList, NULL, chrPtr);

chrPtr = malloc(sizeof("stringa numero due"));
strcpy(chrPtr, "stringa numero due");

Neither of these checks that the memory allocation succeeded; that too should be done in production code, and arguably in school assignments.

Note that sizeof("string literal") counts the null byte, so the length is correct. Note equally that strlen("string literal") does not count the null byte — be careful!

There could still be other problems in the code; I've not verified that everything is clean. But this part will be cleaner and more likely to work correctly.

The functions list_size() and list_ins_next() are not shown. The size can be guessed; the list_ins_next() is not so easy.

I also observe that the code inserts 4 integers and then 2 strings into the list. There's no way to know that's what was inserted after the fact. The code in main() is dreadfully non-general. The support code can handle it — but heterogeneous lists are tricky; don't try it until you don't run into this sort of problem. One list of integers; fine. One list of strings; fine. One list of integers and strings — dodgy!