5

I'm writing a Linked List in C.


list.h

typedef struct list_struct * List; /* Defined in list.c */

List create_list();
void destroy_list(List list);

void list_add(List list, void * item);
void list_remove(List list, int is_target(void *));

... /* Other handy functions like 'list_size', etc. */

list.c

typedef struct node_struct
{
  void * item;
  struct node_struct * next;
} * Node;

typedef struct list_struct
{
  Node head;
  ... /* Other handy things like size, tail, etc. */
} List;

void list_remove(List list, int is_target(void *))
{
  ... /* Find target node to delete. */
  free(target->item);
  ... /* Update links. */
  free(target);
}

... /* Other functions definitions. */

list_remove: When removing a Node (it's used behind the scenes in list.c), I need to obviously deallocate it (using free). However, before freeing the Node, should I also free the 'item' it contains?


My Take

Pro: The advantage to freeing the item so is that a client using this API would not have to keep track of the items he stores in a 'list'. Plus, he wouldn't have to worry about freeing the item himself.

Con: If the client wanted to use the item after deletion of the node, he can't because it was destroyed. So, that's why freeing the item could be a bad idea.

Solution: Change the function to void * list_remove(List list, int is_target(void *)) (note that it now returns void *). It returns the item in the node (the node itself is destroyed). So, if the client does decide that he doesn't need the item, he can just call free(list_remove(my_list, homework_that_dog_ate("HW 5")));. And, if he wants to keep it, he can Homework dog_food = list_remove(my_list, homework_that_dog_ate("HW 5"));.


Is my solution good? If not, where is it flawed? Is there a better approach?

14

In general (and especially when writing library code) you should be discouraged to free memory that someone else has allocated. Namely, you don't know which allocator they used to allocate it in the first place. (It may be on the stack, after all!) You also don't know if they need any additional destruction before deallocation.

That said, this is not to say that this rule cannot be broken in special cases, but if you must break it, make sure you explicitly state it in your documentation.

0

Another option is to separate out finding the node and removing it. If you have a find_node() function, then the caller first finds the node, then simply calls remove to take the pointer to the node out of the list. If they want to keep the thing in the list, it's up to them to do that before calling remove. Of course, this method of removal is much faster in a dually-linked list than a singly linked list.

0

For generic data structures in C, I've often found it useful to require a type size to be passed on construction, like so adapting your example:

List create_list(int type_size);

At which point when you do:

void list_add(List* list, const void* item);

You can allocate memory for the node and item (which you can do separately or together using a variable-length struct) using type_size and memcpy to copy the item's contents into the node, not a pointer to it.

When you do that, you allocated the memory for the node/element internally yourself and can thus free the memory when removing the node without risk of causing confusing problems for the client. And while that involves copying some bits and bytes here and there, it's pretty fast to memcpy data, especially as you're allocating the memory for a node.

Otherwise it gets hairy if you have the client allocate memory for an element, shallow copy a pointer to it, and then try to free the memory for the client even though you didn't allocate the memory. As user8734617 rightly points out, that can actually be undefined behavior when working across module boundaries even if the client used malloc to allocate his element.

Also as a side bonus, if you use variable-length structs to allocate node and element memory together in a contiguous block, list traversal can become more cache-friendly with an AoS pattern when you copy the element's contents into the list rather than pointing to memory allocated somewhere else (wherever the client allocated it).

Plus he might have just allocated the element on the stack at which point the element's memory might get freed from the stack before your list node storing the element is even removed. That's another reason to favor memcpying the element data into the list rather than shallow copying it. By allocating and copying the memory yourself, you can make sure that the element pointer will remain validated inside the list for as long as the element stays inside the list.

Edit: Non-Trivial Types

For non-POD types that require deep copying logic or non-trivial destruction, even memcpying their contents won't suffice if the container outlives their lifetime. In that case, a very generalized interface might be like this:

// Function signature to copy one element to another.
// Memory for 'dst' is allocated by the list.
typedef ListCopy(void* dst, const void* src);

// Function signature to destroy an element.
typedef ListDestroy(void* element);

// Creates a list storing types of the specified size.
// If 'copy' is specified, it will be invoked to copy
// elements to the list. Otherwise a 'memcpy' will be used.
// If 'destroy' is specified, it will be invoked prior
// to removing elements and freeing their memory.
List create_list(int type_size, ListCopy* copy, ListDestroy* destroy);

That will turn your list into a "resource owner" even for user-defined types that cannot be trivially copied and destroyed. The memcpy and omission of a destructor suffices for plain old data types, and if that's all that you need, you can do without these callbacks while still making your list a "resource owner".

  • 1
    Note memcpy() is not a deep copy - it is just one level deeper from copying a pointer. What if the structure itself has pointers to other structures? (Let alone if it also contains other resources - think of a mutex, condition variable, FILE pointer...) What if it contains pointer references to itself (e.g. a root of a double-linked list)? – user285148 Jan 18 '18 at 23:29
  • Ah yes, I think "pointee" copy might be the term I was looking for as opposed to "pointer" copy -- or how would you make the distinction? I'm often trying to make that pointee/pointer one, and I don't know the right words. My English is also degrading, I think -- been writing a lot but haven't spoken to anyone in English for years. – user204677 Jan 19 '18 at 3:25
  • 1
    I don't complain about the word you used but about the actual idea. What you call "memcpying" is really what is elsewhere called a "shallow copy", and my point is that often it is not satisfactory as some objects require a proper deep copy. Still, if the clients of the library all agree that their objects are "plain old data" (POD) structures, then this design can work. – user285148 Jan 19 '18 at 9:43
  • @user8734617 I see, yes. In my case I'm often working with PODs in containers since I use an ECS with duck typing. I'm kinda biased towards seeing most of the central data stored for the app as trivially constructible/destructible like a motion component here, a tree node there (which just indexes entities). I should probably add a mention for an interface that accepts function pointers for destructors or deep copying -- but it's at least a little less fragile than one which points to memory allocated by the client, no? – user204677 Jan 19 '18 at 10:03
  • 1
    Looks good. Now it is up to the OP to decide if they need this overhead - maybe all they need is a list of PODs, after all...!? – user285148 Jan 19 '18 at 10:12

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.