A linked list containing other related lists and free

Question

I have a general implementation of linked lists with a node construct containing void * for data and a list structure that contains a link to head. Now here is my problem: a node in a linked list may contain a link to another linked list through its void *. This causes a memory leak when I free a larger list containing smaller lists. So I'm wondering if there is a way to check if void * points to another list, so I follow and release this as well or just the data.

If I add a key to the beginning of my structure, a magic number that I can check by dereferencing void * and finding out what the list is?

EDIT: Callers do not insert smaller lists, which they insert using my functions. I do not want the callers to deal with the redistribution of several lists, only those to which they contain a pointer.

Answer 1

This question really depends on whose responsibility it is to clear the entries in the list. If your structure is responsible for clearing the memory referenced by the void * fields, then you have a much bigger problem, namely, when specifying void * referring to any arbitrary block of memory, you will never know how to free it correctly . For example, if you have a dynamic array implementation along the lines of C ++ std::vector , then your void * may point to a structure that itself contains a pointer, and your list should know that it must go down to this structure in order to recursively release your dynamically allocated block. The case that you describe where you go into the nested list is just a special case of this more general problem.

If, on the other hand, the list is not responsible for clearing the memory referenced by void * that it stores, then you should not worry about this problem at all.

If your list has property semantics and you want to clear the memory for the items stored in it, I would strongly discourage you from using a magic number to determine if you have a nested list. Most likely, you should probably provide the client with a function pointer containing the maladaptation procedure to run the items inserted into the list. That way, your code can use a user-provided cleanup code to clear all the items stored in the list.

Answer 2

Not only your void* can point to a list. It can point to any dynamically allocated memory.

The way that GLib deals with this problem is to say that it is the responsibility of the caller to ensure that everything listed in the void *data list is freed. See http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html#g-list-free .

An alternative (which GLib also provides) is to create a function that takes a pointer to a function and calls it on every void *data when iterates through a list. Find g_list_free_full .

Answer 3

My advice would be, if at all possible, to simplify things a bit and just make sure that one linked list contains only one type of object.

If you cannot do this, I will probably have every node in the list hold not only some data, but also a pointer to a function that knows how to correctly release elements of this type. Inevitably, two weeks after you write your special code for the linked list, you will also decide that you need another magic number to store the dynamic array, etc.

Answer 4

To answer the question about wisdom, "If I add a key to the top of my structure, a magic number that I can check by dereferencing the void * and finding out what the list is?"

Yes, you can do it, but few recommend it. Just be sure that the “magical” meaning cannot happen otherwise. This is a pretty big question. You want to consider what else you could indicate, and what values ​​it could take if they are presented as something like unsigned integers. Remember that if you decide that this is a list, you are going to release it and, therefore, most likely a failure and burning, if you are mistaken.

The simplest effective solution is that if you need Node to know that it points to a list, specify a flag in Node that says so.

If you really want the list to be responsible for freeing all its contents, you need more than a flag, you need to know how to do each for free. It could be an identifier or something like a pointer to a function that frees its contents.