Бесплатный двойной список в 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-> данные указатель на другую структуру, которая сама содержит указатели. В моем случае я использую один и тот же код для хранения двух разных структур.

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

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

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

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

Answer 3

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

Answer 4

Хммм: создайте функцию 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); 
} 

---

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

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

Answer 5

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

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

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

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

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

Answer 6

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

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

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

Answer 7

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

Это хорошее упражнение и стоит делать только для обучения.

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

Answer 8

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

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

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