How to write a function that gets a linked list of any node type and frees the memory used by it?

Question

I'm sure some of you already experienced it. I have two linked lists of different types and I have two distinct functions that free the memory used by them. Those two functions are identical except for one thing.

Generally a function that frees a list would looks like this:

void free_list(T *p)
{
    T *next;    /* here */
    while (p != NULL) {
        next = p->next;
        free(p);
        p = next;
    }
}

where T is the node type. The only difference between these functions is the marked line.
Is there a way to write a function/macro that gets a pointer to the head of any linked list and frees it?

I tried several ideas, but I'll spare them from you because they were wrong and failed and not to burden with details.

Answer 1

What you want is exactly what C++ templates provide. In C, you are stuck with doing nasty things with void pointers and macros.

Answer 2

You can create a structure like

struct my_item
{
    void * item; // put pointer to your generic item here
    struct my_item * next; // NULL = end of list
};

And then have function

void free_my_list (struct my_item * first)
{
    struct my_item * cur = first;
    while (cur != NULL)
    {
         cur = cur->next;
         free(cur->item);
         free(cur);
    }
}

Answer 3

Given the limitations of 'C', my first shot would be a macro something like

#define FREE_LIST(T, p)\
do {\
    T *next;\
    while (p != NULL) {\
        next = p->next;\
        free(p);\
        p = next;\
    }\
} while(0)

i.e. the way you had to write C++ generic code back around 1990 (before templates).

---

(EDIT) Historical note -- for the morbidly curious, Dewhurst & Stark Programming in C++ which attempted to be a sort of K&R for C++ goes into great detail about how to use macros to emulate the (still speculative at the time of writing) template behaviour we now enjoy. Most of the principles will back-port naturally to 'C'.

Answer 4

If all of your Node structs are declared with the 'next' pointer as the first "member", this way:

struct _Node{
    struct _Node *next;
    /* more data */
};

then you can have a function like this

void free_list(void *p)
{
    void *next;
    while (p != NULL) {
        /*getting the content of the first field, assuming that
          sizeof(void*)==sizeof(unsigned long)*/
        next = (void*)*((unsigned long*)p); 
        free(p);
        p = next;
    }
}

this way you can call free_list(head_of_list) for any list that following this pattern.

Answer 5

As long as all your node types start with a next pointer, you can create a generic freeing function like so:

struct generic_node {
    struct generic_node *next;
};

void free_list(void *head)
{
    struct generic_node *p = head, *next;
    while (p != NULL) {
        next = p->next;
        free(p);
        p = next;
    }
}

struct t_node {
    struct t_node *next;

    /* members of thing t */
};

struct q_node {
    struct q_node *next;

    /* different members of thing q */
};

/* Can happily pass t_node or q_node lists to free_list() */

Answer 6

If you are using linked lists, believe me you want to use managed memory. The effective way to use linked lists is structure sharing - and as your programs get more complex, you will end up with millions of shared and partially shared lists. Lists will be constructed that share parts of many other lists ... it's messy.

Lisp early on developed the use of garbage collection to deal with this, and now that you can get it in C/C#/Java environments why go back?

If you really can't then you can do a poor man's garbage collection by putting reference-counting wrappers around your pointers. Look up "smart pointers". But this is a lot more trouble than manged memory.

Answer 7

I'd like to suggest a different approach. Instead of creating multiple list types for different kinds of data and using casting or macro gymnastics to apply the same algorithm to them, create a single generic list type that delegates type-specific behavior to different functions and attach those functions to the list type with function pointers. For example:

struct generic_node {
  void                *data;
  struct generic_node *next;
};
struct generic_list {
  struct generic_node head;
  int   (*cmp)(void * const a, void * const b);
  void *(*cpy)(void * const);
  void  (*del)(void *);
};

cmp points to a function that will return -1 if *a < *b, 0 if *a == *b, and 1 if *a > *b, where a and b have been converted from void * to the proper pointer types. For example,

int compareInts(void * const a, void * const b)
{
  int * const la = a;
  int * const lb = b;
  if (*a < *b) return -1;
  if (*a == *b) return 0;
  if (*a > *b) return 1;
}

int compareMyStruct(void * const a, void * const b)
{
  struct myStruct * const la = a;
  struct myStruct * const lb = b;

  if (la->foo < lb->foo && strcmp(la->bar,lb->bar) < 0 && ...) return -1;
  if (la->foo == lb->foo && strcmp(la->bar,lb->bar) == 0 && ...) return 0;
  if (la->foo > lb->foo && strcmp(la->bar, lb->bar) > 0 && ...) return 1;
}

cpy points to a function that makes a deep copy of the input parameter:

void *copyInt(void * const data)
{
  int *theCopy = malloc(sizeof *theCopy);
  *theCopy = *((int *) data);
  return theCopy;
}

void *copyMyStruct(void * const data)
{
  struct myStruct * const lData = data;
  struct myStruct *newStruct = malloc(sizeof *newStruct);
  newStruct->foo = lData->foo;
  newStruct->bar = malloc(strlen(lData->bar) + 1);
  strcpy(newStruct->bar, lData->bar);
  ...
  return newStruct;
}

And finally, del points to a function that deallocates the data items:

void delInt(void * data)
{
  free(data);
}

void delMyStruct(void * data)
{
  struct myStruct * lData = data;
  free(lData->bar);
  ...
  free(lData);
}

Now your list algorithms don't have to worry about type-specific behavior; they just invoke the appropriate function via the function pointer:

void listAdd(struct generic_list * const theList, void * const data)
{
  struct generic_node *cur = &(theList->head);
  struct generic_node *entry = malloc(sizeof *entry);
  entry->data = theList->cpy(data);
  while (cur->next != NULL && theList->cmp(cur->next->data, entry->data) < 0)
    cur = cur->next;
  entry->next = cur->next;
  cur->next = entry;
}
/** */
void listClear(struct generic_list * const theList)
{
  struct generic_node *cur = theList->head.next;
  while (cur != NULL)
  {
    struct generic_node *entry = cur;
    cur = cur->next;
    theList->del(entry->data);
    free(entry);
  }
}