Как освободить связанный список в C

Question

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

typedef struct node_ {
    int num;
    struct node_ *next;
    struct node_ *prev;
} element;


typedef struct list_ {
    element **first;
    element **last;
    int *e_count;
} list;

Вот моя проблема с освобождением списка. Этот код работает нормально:

void wipe(list l) {
    element *p = *l.first;
    element *t;

    while (p) {
        t = p;
        p = p->next;
        free(t);
    }

    *l.first = NULL;
    *l.last = NULL;
    *l.e_count = 0;
}

Но когда я пытаюсь использовать двойные указатели, я начинаю получать ошибку InvalidRead от valgrind:

void wipe(list l) {
    element **p = l.first;
    element **t = l.first;

    while (*p) { // InvalidRead here after "free(*t);"
        *t = *p;
        p = &(*p)->next;
        free(*t);
    }

    *l.first = NULL;
    *l.last = NULL;
    *l.e_count = 0;
}

Это ожидаетсяпотому что в этом случае t и p по существу указывают на один и тот же адрес, который затем используется free(). Мне интересно, как можно это исправить и будет ли это лучше, чем в первом случае с одиночными указателями.

Спасибо за вашу помощь!

Кодпример:

#include <stdlib.h>
#include <stdio.h>


typedef struct node_ {
    int num;
    struct node_ *next;
    struct node_ *prev;
} element;


typedef struct list_ {
    element **first;
    element **last;
    int *e_count;
} list;


list new_list();
void delete_list(list l);

element *alloc_element(int n);

int append(list l, int n);
void wipe(list l);


int main() {
    list l = new_list();
    append(l, 5);
    append(l, 7);
    delete_list(l);
}


list new_list() {
    element **first = malloc(sizeof(element*));
    element **last = malloc(sizeof(element*));
    int *n = malloc(sizeof(int));
    *first = NULL;
    *last = NULL;

    list list = {first, last, n};
    return list;
}


void delete_list(list l) {
    wipe(l);
    free(l.first);
    free(l.last);
    free(l.e_count);
}


element *alloc_element(int n) {
    element *e = malloc(sizeof(element));
    if (!e) {
        return NULL;
    }
    e->next = NULL;
    e->prev = NULL;
    e->num = n;
    return e;
}


int append(list l, int n) {
    element **p = l.first;
    element *e = alloc_element(n);
    if (!e) {
        return 1;
    }

    while (*p) {
        if (!(*p)->next) {
            e->prev = *p;
        }
        p = &(*p)->next;
    }

    *p = e;
    *l.last = e;
    ++*l.e_count;
    return 0;
}


void wipe(list l) {
    element *p = *l.first;
    element *t;

    while (p) {
        t = p;
        p = p->next;
        free(t);
    }

    *l.first = NULL;
    *l.last = NULL;
    *l.e_count = 0;
}

Answer 1

Поскольку вам нужны функции для изменения list, вам необходимо передать указатели на list для функций. Кроме того, в вашем коде, похоже, много путаницы в использовании двойных указателей, которых можно избежать. Вот приведенная в порядок версия кода, которая исправляет все ошибки:

#include <stdlib.h>
#include <stdio.h>


typedef struct node_ {
    int num;
    struct node_ *next;
    struct node_ *prev;
} element;


typedef struct list_ {
    element *first;
    element *last;
    int e_count;
} list;


list *new_list(void);
void delete_list(list *l);

element *alloc_element(int n);

int append(list *l, int n);
void wipe(list *l);


int main(void) {
    list *l = new_list();
    append(l, 5);
    append(l, 7);
    delete_list(l);
}


list *new_list(void) {
    list *l = malloc(sizeof(list));
    if (!l) {
        return NULL;
    }
    l->first = NULL;
    l->last = NULL;
    l->e_count = 0;
    return l;
}


void delete_list(list *l) {
    if (l != NULL) {
        wipe(l);
        free(l);
    }
}


element *alloc_element(int n) {
    element *e = malloc(sizeof(element));
    if (!e) {
        return NULL;
    }
    e->next = NULL;
    e->prev = NULL;
    e->num = n;
    return e;
}


int append(list *l, int n) {
    element *e = alloc_element(n);
    if (!e) {
        return 1;
    }
    if (l->last) {
        l->last->next = e;
    } else {
        l->first = e;
    }
    e->prev = l->last;
    l->last = e;
    ++l->e_count;
    return 0;
}


void wipe(list *l) {
    element *p = l->first;
    element *t;

    while (p) {
        t = p;
        p = p->next;
        free(t);
    }

    l->first = NULL;
    l->last = NULL;
    l->e_count = 0;
}