Avoiding a double free() error when deleting separate Linked Lists that contain the same object-CodePudding

I am working on a personal project and have run into a conceptual problem. How should I go about deleting multiple dynamically created linked lists that could have references to the same dynamically created object?

I have some function that returns a dynamically created linked list that houses dynamically created objects.

List* generate_list() {
  Object* object_address = create_object();
  List* list = create_list();
  list_append_end(list, object_address);
  return list;
}

I have another function that deletes the linked list and recursively deletes the objects stored inside the linked list by providing a delete function.

List* list = generate_list();
delete_list(list, delete_object_function);

Now, I run into a problem with this approach when trying to delete multiple linked lists that hold references to the same object.

Object* object_address = create_object();
List* list = create_list();
List* another_list = create_list();
list_append_end(list, object_address);
list_append_end(another_list, object_address);
delete_list(list, delete_object_function);
delete_list(another_list, delete_object_function); // Double free() would occur here

I could obviously just not delete one of the two lists to avoid a double free() error, but that could create a memory leak later down the line.

My actual code is much more involved than this, but I tried to make a simplified example. Not sure how to avoid this situation.

CodePudding user response：

Just use reference counting. Whenever a new owner is added to the object, one must increment the refcouter with get_object(). When ownership is released with put_object() reduce the counter.Free the objects only when the counter reaches 0.

struct {
...
int refcount;
} Object;

Object* create_object(void) {
  ...
  obj->refcount = 1;
  return obj;
}

Object* get_object(Object* obj) {
  assert(obj->refcount > 0);
  obj->refcount  ;
  return obj;
}

void put_object(Object* obj) {
  assert(obj->refcount > 0);
  obj->refcount--;
  if (obj->refcount == 0) {
    delete_object(obj);
  }
}

It's safe because get_object() can only be called when the caller owns the object. Thus object's refcount would be non-zero.

When the refcount reaches 0 then there can be no other owner of the object, so no one can call get_object().

now the usage could look like:

Object* obj = create_object();
List* list = create_list();
List* another_list = create_list();
// let `list` own the object
list_append_end(list, get_object(obj));
// let `another_list` own the object as well
list_append_end(another_list, get_object(obj));
delete_list(list, put_object);
delete_list(another_list, put_object);
put_object(obj); // release ownership because `obj` goes out of scope

Note that the last three operations can be executed in any order.

BTW. It's a good practice is set a pointer to an object to NULL after releasing the ownership.

In the original generate_list() function there is no need to add extra get_object/put_objects calls because the ownership of object pointed by object_address can be implicitly passed from object_address variable to the returned list.