Можно ли вообще освободить память связанных списков в C

Если у меня есть несколько связанных структур в C, например: 

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

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

И я динамически выделяю память следующим образом: 

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));

Всегда ли я должен освобождать его для каждого типа структуры следующим образом: 

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);
}

Или есть какое-то общее решение? Я предполагаю, что другого решения нет, потому что процедура free() должна знать, сколько байтов должно быть освобождено. Но, может быть, я ошибаюсь, и кто-то может научить меня лучше.

3 2
malloc linked-list

3 ответа:

Стандартный способ состоит в том, чтобы сделать "часть списка" первым элементом структуры, и пусть каждая производная структура имеет тот же префикс. Поскольку первый элемент гарантированно будет помещен на нулевое смещение, это будет работать. Пример фрагмента: 

#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;
}

Это более или менее метод, используемый в ядре linux, но там используется гораздо больше магии препроцессора. (и там, очевидно, нет Маллока)

5

Поскольку free() принимает указатели на void * и structA и structB оба имеют одинаковый размер, вы можете передать оба типа указателей.

Это, однако, не является оптимальным с точки зрения элегантности. Вы должны подумать о следующих вопросах: Почему у вас есть две разные структуры с одинаковыми членами?

Почему у вас нет универсального типа элемента списка, например: 

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

На самом деле, это очень интересный вопрос. Часть верно, что вы должны free() каждый тип struct индивидуально, так как они были malloc()-ed индивидуально, и каждый блок памяти был выделен специально для этого типа.Кроме того, в некоторых системах char и int имеют разные размеры хранилища, но вы можете попробовать решение, подобное предложенному Филиппом. Для получения дополнительной информации, прочитайте оDoom memory engine . На боковой ноте, Пожалуйста, не бросайте malloc() в C. Самое смешное, что однажды программа завершается, операционная система восстанавливает память, поэтому, если вы только освободите структуры ближе к концу программы, когда они вам больше не нужны, может не потребоваться free() их

2