Linked list containing other linked lists & free

Question

I have a generic linked list implementation with a node struct containing a void* to data and a list struct that holds a reference to head. Now here is my problem a node in the linked list may hold a reference to another linked list via its void*. This causes memory leaks when I free the bigger list containing smaller lists. So I am wondering is there a way to check if the void* is pointing to another list so I follow and free that also or to just data.

If i add a key to the beginning of my struct a magic number that I can check by dereferencing the void* and figure out it is a list?

EDIT: Callers don't insert the smaller lists they are inserted by my functions I do not want the callers to deal with relasing multiple lists just the one they hold a pointer to.

Answer 1

This question really depends on whose responsibility it is to clean up the entries in the list. If your struct is responsible for cleaning up the memory referenced by the void * fields, then you have a much bigger problem at hand here, namely that given a void * referencing some arbitrary block of memory you can never know what the right way to deallocate it is. For example, if you have an implementation of a dynamic array along the lines of the C++ std::vector, then your void * might point at a struct that itself contains a pointer, and your list will need to know that it has to descend into that struct to recursively free its dynamically-allocated block. The case you're describing, where you're leaking a nested list - is just a special case of this more general issue.

If, on the other hand, the list is not responsible for cleaning up the memory referenced by the void *s it stores, then you shouldn't worry about this problem at all.

If your list does have ownership semantics and is required to clean up the memory for the elements stored in it, I would strongly discourage you from using a magic number to determine whether you have a nested list. Rather, you should probably have the client provide you a function pointer containing a deallocation routine to run on the elements inserted into the list. That way, your code can use the user's provided cleanup code to ensure that any elements stored in the list are cleaned up.

Answer 2

It's not just that your void* could point to a list. It could point to any dynamically-allocated memory.

The way GLib handles this problem is to say that it's the caller's responsibility to ensure that anything pointed-to by the void *data of a list is freed. See http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html#g-list-free .

The alternative (which GLib also provides) is to make a function that takes a function pointer and calls that on each void *data as it traverses the list. Look up g_list_free_full.

Answer 3

My advice would be if at all possible to simplify things a bit, and simply ensure that one linked list only holds one type of object.

If you can't do that, I'd probably have each node in the list hold not only some data, but also a pointer to a function that knows how to properly free items of that type. Inevitably, two weeks after you write your special code for a linked list, you'll decide you also need another magic number to be able to hold a dynamic array, etc.

Answer 4

To answer the question of what is the wisdom of "If i add a key to the beginning of my struct a magic number that I can check by dereferencing the void* and figure out it is a list?"

Yes, you can do this, but few would recommend it. Just be really sure that the 'magic' value cannot possibly occur otherwise. That is a pretty big ask. You want to consider what else you might be pointing to and what values it might take when represented as something like an unsigned integer. Remember that if you decide it is a list, you are going to free it and hence will likely crash and burn if you are wrong.

The simplest effective solution is that if you need a Node to know that it points to a list, provide a flag in the node saying so.

If you really want the list to own responsibility for freeing all its contents, you need more than a flag, you need to know how to do each free. That might be an id or something like a pointer to the function which frees its contents.