Освободите двусвязный список в C

Question

У меня есть двусвязный список в C, и я не понимаю, как мне его освободить. Я понимаю, что я должен пройти список, освобождая каждый узел. В чем путаница, так это в том, что у каждого из моих узлов есть указатель на некоторые другие данные, и я не уверен, как мне это освободить.

Мой двусвязный список выглядит так:

typedef struct Node_ Node;
typedef struct List_ List;

struct Node_ {
    void *data;
    Node *next;
    Node *prev;
};

struct List_ {
    Node *firstNode;
    Node *lastNode;
};

Чтобы освободить список, я создал функцию List_free (), которая перебирает список, освобождая каждый узел с помощью Node_free (). Эти функции выглядят так:

void *List_free(List *list)
{
    Node *next = list->firstNode;

    while(next)
    {
        Node *node = next;
        next = node->next;
        Node_free(node);
    }

    free(list);
}

void Node_free(Node *node)
{
    free(node->data);
    free(node);
}

Где это будет падать, это где node-> data является указателем на другую структуру, которая сама содержит указатели. В моем случае я использую один и тот же код списка для хранения двух разных структур.

Как я вижу, у меня есть следующие варианты:

1. Создание списков, в которых узлы содержат определенные данные. Не очень многоразово.
2. Найдите другой способ отслеживать указатели в данных узла.

Я думаю по правильному пути или я пропустил что-то очевидное? Это моя первая попытка на C, поэтому я не удивлюсь, если все это будет совершенно неправильно.

Answer 1

Одним из решений является предоставление указателя на функцию, ответственного за правильное освобождение узла.

typedef void(*NodeDataFreeFn)(void*);

List_free модифицируется следующим образом:

void *List_free(List *list, NodeDataFreeFn data_free)
{
    Node *next = list->firstNode;

    while(next)
    {
        Node *node = next;
        next = node->next;
        (*data_free)(node->data);
        free(node);
    }
    free(list);
}

Пример data_free:

void data_free_fn(void* data_ptr) {
    // Add your custom stuff here.
    free(data_ptr);
}

Пример вызова List_free:

List_free(my_list, data_free_fn);

Если вы не хотите передавать указатель на функцию без данных в качестве аргумента, вы можете вместо этого сохранить его в структуре списка следующим образом:

struct List_ {
   Node *firstNode;
   Node *lastNode;
   NodeDataFreeFn data_free;
};

Отказ от ответственности: я не тестировал этот код, возможно, он глючит ...

Answer 2

Если приложение может хранить произвольные данные в вашем списке, приложение также несет ответственность за правильную очистку.
Это можно сделать двумя способами:

1. Перед вызовом List_free приложение должно очистить все элементы списка.

2. Вы добавляете еще один параметр к List_free (и Node_free), который является указателем на функцию удаления:

   
   typedef void (deleter_t*)(void*);</p>
   
   <p>void Node_free(Node* node, deleter_t deleter)
   {
       if (deleter) (*deleter)(node->data);
       free(node);
   }
   

   Для данных, которые не должны быть освобождены явно, приложение может передать NULL-удалитель, для данных, которые могут быть освобождены с помощью одного вызова free, эта функция может быть передана как удалитель. Для более сложных данных приложение должно передать функцию, которая делает правильные вещи.

Answer 3

Вы не ошибаетесь, это одна из проблем, "решаемых" ООП и, в частности, C ++.

Вы можете добавить указатель на член функции в вашей структуре, который будет использоваться для освобождения ее данных.В основном добавление деструктора C ++ вручную.Это сохранит универсальность без слишком большого дублирования.

Answer 4

Проблема не в том, что в списке есть prev указатели. Проблема заключается в том, что каждый тип Node имеет свой способ удаления своего содержимого.

Таким образом, должна быть общая подпрограмма Node_free (которая у вас есть), и она должна отправлять данные по типу узла. Таким образом, либо узел должен содержать код общего типа, либо он должен содержать указатель на процедуру деструктора, адаптированную для этого типа узла.

В любом случае, вы в основном делаете то, что C ++ делает для вас.

Answer 5

Как уже говорили другие, вы определили что-то, что является болью, которую нужно делать в C вручную, но это нужно сделать.Вы можете использовать указатели на функции, чтобы сделать механизм освобождения общим для ваших данных, но вам все равно нужно реализовать механизм, чтобы перейти вниз по иерархии данных в каждом узле, чтобы освободить все.упражнение и его стоит делать только для обучения.

Но есть и очень полезная библиотека, которая поможет вам со всем этим: talloc .Он отслеживает иерархию для вас, поэтому освобождение верхнего уровня автоматически освобождает все под ним.Это хорошо задокументировано.Он был разработан для самбы и до сих пор используется там, поэтому он очень хорошо поддерживается.

Answer 6

Один из подходов, которые вы можете попробовать, - реализовать пул памяти;что может быть особенно тривиально для реализации, если вы не планируете освобождать узлы по отдельности.

Просто malloc (или mmap, возможно, /dev/zero) большой кусок, а затем вы можете «выделить»msgstr "память для одного узла простым добавлением указателя.Отмена выделения всего списка - это вопрос free использования (или munmap) большого фрагмента.

Если все сделано правильно, это также может дать небольшое повышение производительности.

Answer 7

Хммм: создайте функцию Data_free и вызовите ее для ваших указателей данных.

void Data_free(void *ptr)
{
    /* first identify what data type ptr really is */
    /* and then deallocate memory used by ptr */
}

void Node_free(Node *node)
{
    /*free(node->data);*/
    Data_free(node->data);
    free(node);
}

---

Редактируйте: измените определение struct Node_, чтобы сделать его более похожимв класс C ++: -)

struct Node_ {
    void *data;
    void (*freedata)(void*);
    struct Node_ *next;
    struct Node_ *prev;
}

Answer 8

Ваша проблема не в двусвязном списке, как указывает вопрос, а скорее в сложных динамических структурах.Вот как работает ручное управление памятью: вы должны следить за тем, что вы выделили.Лучше всего каждый раз придерживаться того, чтобы узлы-> данные были одной и той же структуры, чтобы предопределенная подпрограмма могла их освободить.В качестве альтернативы используйте маркер на структуре и включите маркер во время выполнения, чтобы выбирать между подпрограммами освобождения для различных структур (или просто используйте указатель функции для имитации деструктора C ++).