Is it possible to generically free linked lists' memory in C

Question

If I have several linked structures in C like:

struct structA {
    int a;
    int b;
    struct structA *next;
}

struct structB {
    char a;
    int b;
    struct structB *next;
}

and I dynamically allocate memory like this:

struct structA *mystructA = (struct structA*) malloc(sizeof(struct structA));
mystructA->next = (struct structA*) malloc(sizeof(struct structA));

struct structB *mystructB = (struct structB*) malloc(sizeof(struct structB));
mystructB->next = (struct structB*) malloc(sizeof(struct structB));

do I always have to free it for each struct type like this:

struct structA *p, *pNext;
for (p = mystructA; p != NULL; p = pNext) {
    pNext = p->next;
    free(p);
}

struct structB *p, *pNext;
for (p = mystructB; p != NULL; p = pNext) {
    pNext = p->next;
    free(p);
}

or is there any generic solution? I assume there is no other solution because the free() procedure must know how many bytes have to be freed. But maybe I'm wrong and someone can teach me better.

you must deallocate the structures one by one.

user2107435
– user2107435

2013-07-19 12:58:38 +00:00
Commented Jul 19, 2013 at 12:58 — user2107435
– user2107435, Commented Jul 19, 2013 at 12:58

wildplasser · Accepted Answer · 2013-07-19 13:56:46Z

5

The standard way is to make the "list part" the first element of the structure, and let each derived struct share this same prefix. Since the first element is guaranteed to be placed at offset zero this wil work. Example snippet:

#include <stdlib.h>
#include <string.h>

struct list {
    struct list *next;
    };
struct structA {
    struct list list;
    int a;
    int b;
    };

struct structB {
    struct list list;
    char a;
    int b;
    };

void *create_any(size_t size) 
{
    struct list *this;
    this = malloc (size);
    if (!this) return this;
    memset(this, 0, size);
    this->next = NULL;
    return this;
}


void free_all_any(struct list **lp) {
    struct list *tmp;
    while ((tmp = *lp)) { *lp = tmp->next; free(tmp); }
}
#define CREATE_A() create_any(sizeof(struct structA))
#define CREATE_B() create_any(sizeof(struct structB))
#define FREE_A(pp) free_any((struct list **) pp)
#define FREE_B(pp) free_any((struct list **) pp)

int main(void)
{
struct structA *ap;
struct structB *bp;

ap = CREATE_A ();
bp = CREATE_B ();

// some code here ...

FREE_A( &ap);
FREE_B( &bp);

return 0;
}

This is more or less the method used in the linux kernel, but a lot more preprocessor magic is used there. (and there is no malloc there, obviously)

edited Jul 19, 2013 at 13:56

answered Jul 19, 2013 at 13:31

wildplasser

44.5k9 gold badges72 silver badges116 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

arminb Over a year ago

Why did you define macros and why are you calling memset()?

wildplasser Over a year ago

Mainly as an illustration. The macros hide the casts and the sizeof. The memset is just to set the complete object to zeros. (NULL is not necessarily represented as all-zeros, so that has to be done separately anyway)

arminb Over a year ago

Okay, everything clear now thank you! Very good generic solution but maybe little confusing on the first look (because of the macros and memset() :-)

Philip · Accepted Answer · 2013-07-19 13:01:32Z

2

Since free() accepts pointers to void * and structA and structB both have the same size, you can pass both pointer types.

This is, however, not optimal in terms of elegance. You should think about the following questions:

Why do you have two different structs with the same members?

Why do you not have a generic list item type, such as the following:

struct list_node {
    void *data;
    struct list_node *next;
}

answered Jul 19, 2013 at 13:01

Philip

5,9753 gold badges40 silver badges69 bronze badges

1 Comment

arminb Over a year ago

They haven't same members and also not same size, have a closer look at my provided code. structA has 2 ints; structB has 1 char, 1 int

Community · Accepted Answer · 2017-05-23 10:25:34Z

2

Actually, this is a very interesting question. The part is true that you have to free() each struct type individually, as they have been malloc()-ed individually, and each memory block has been allocated specifically for that type.Also, on some systems char and int have different storage sizes, but you can try a solution like Phillip provided. For more info, read about the doom memory engine. On a side note, please don't cast malloc() in C. The funny thing is that once the program is terminated, the operating system will reclaim the memory, so if you only deallocate the structures near the end of the program, when you don't need them anymore, it may not be necessary to free() them

edited May 23, 2017 at 10:25

CommunityBot

11 silver badge

answered Jul 19, 2013 at 13:07

Binayaka Chakraborty

1,33510 silver badges14 bronze badges

2 Comments

Drew McGowen Over a year ago

"the OS will reclaim the memory" just be careful with this statement - it's not required that the OS does this, but it's just very unlikely that it won't.

Binayaka Chakraborty Over a year ago

Agreed, but the mainstream OS' windows and linux do, so I said :)

Collectives™ on Stack Overflow

Is it possible to generically free linked lists' memory in C

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related