Как написать функцию, которая получает связанный список любого типа узла и освобождает используемую им память?

Question

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

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

void free_list(T *p) 
{ 
    T *next; /* here */ 
    while (p != NULL) { 
     next = p->next; 
     free(p); 
     p = next; 
    } 
} 

где T является тип узла. Единственная разница между этими функциями - обозначенная строка.
Есть ли способ написать функцию/макрос, который получает указатель на голову любого связанного списка и освобождает его?

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

Answer 1

Учитывая ограниченность 'C', мой первый выстрел будет макрос-то вроде

#define FREE_LIST(T, p)\ 
do {\ 
    T *next;\ 
    while (p != NULL) {\ 
     next = p->next;\ 
     free(p);\ 
     p = next;\ 
    }\ 
} while(0) 

т. Е. То, как вам пришлось писать общий код C++ около 1990 года (перед шаблонами).

---

(EDIT) Историческая справка - для патологически любопытным, Dewhurst & Stark Programming in C++ который пытался быть своего рода K & R для C++ идет в подробности о том, как использовать макросы для эмуляции (по-прежнему спекулятивная в то время написания) поведения шаблонов, которыми мы теперь пользуемся. Большинство принципов, естественно, обратятся к «C».

Answer 2

Что вы хотите, это именно то, что предоставляют шаблоны на C++. В C вы застряли с неприятными вещами с указателями и макросами.

Answer 3

Вы можете создать структуру, как

struct my_item 
{ 
    void * item; // put pointer to your generic item here 
    struct my_item * next; // NULL = end of list 
}; 

А затем функция

void free_my_list (struct my_item * first) 
{ 
    struct my_item * cur = first; 
    while (cur != NULL) 
    { 
     cur = cur->next; 
     free(cur->item); 
     free(cur); 
    } 
} 

Answer 4

Если все Узлы структур объявлены с «следующим» указателем в качестве первого «члена», таким образом:

struct _Node{ 
    struct _Node *next; 
    /* more data */ 
}; 

, то вы можете иметь функцию, как этот

void free_list(void *p) 
{ 
    void *next; 
    while (p != NULL) { 
     /*getting the content of the first field, assuming that 
      sizeof(void*)==sizeof(unsigned long)*/ 
     next = (void*)*((unsigned long*)p); 
     free(p); 
     p = next; 
    } 
} 

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

Answer 5

Пока все ваши типы узлов начинаются с следующим указателем, вы можете создать обобщенную функцию освободив таким образом:

struct generic_node { 
    struct generic_node *next; 
}; 

void free_list(void *head) 
{ 
    struct generic_node *p = head, *next; 
    while (p != NULL) { 
     next = p->next; 
     free(p); 
     p = next; 
    } 
} 

struct t_node { 
    struct t_node *next; 

    /* members of thing t */ 
}; 

struct q_node { 
    struct q_node *next; 

    /* different members of thing q */ 
}; 

/* Can happily pass t_node or q_node lists to free_list() */ 

Answer 6

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

Lisp на ранней стадии разработал использование коллекции мусора, чтобы справиться с этим, и теперь, когда вы можете получить его в средах C/C#/Java, зачем возвращаться?

Если вы действительно не можете, вы можете сделать сбор мусора у бедняка, поставив обертки для ссылок на ваши указатели. Посмотрите «умные указатели». Но это намного больше проблем, чем память.

Answer 7

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

struct generic_node { 
    void    *data; 
    struct generic_node *next; 
}; 
struct generic_list { 
    struct generic_node head; 
    int (*cmp)(void * const a, void * const b); 
    void *(*cpy)(void * const); 
    void (*del)(void *); 
}; 

CMP указывает на функцию, которая будет возвращать -1, если * а * < Ь, 0, если * а * == Ь, и 1, если * а> * Ь, где А и В имеют были преобразованы из void * в соответствующие типы указателей. Например,

int compareInts(void * const a, void * const b) 
{ 
    int * const la = a; 
    int * const lb = b; 
    if (*a < *b) return -1; 
    if (*a == *b) return 0; 
    if (*a > *b) return 1; 
} 

int compareMyStruct(void * const a, void * const b) 
{ 
    struct myStruct * const la = a; 
    struct myStruct * const lb = b; 

    if (la->foo < lb->foo && strcmp(la->bar,lb->bar) < 0 && ...) return -1; 
    if (la->foo == lb->foo && strcmp(la->bar,lb->bar) == 0 && ...) return 0; 
    if (la->foo > lb->foo && strcmp(la->bar, lb->bar) > 0 && ...) return 1; 
} 

КПЮ указывает на функцию, которая делает глубокую копию входного параметра:

void *copyInt(void * const data) 
{ 
    int *theCopy = malloc(sizeof *theCopy); 
    *theCopy = *((int *) data); 
    return theCopy; 
} 

void *copyMyStruct(void * const data) 
{ 
    struct myStruct * const lData = data; 
    struct myStruct *newStruct = malloc(sizeof *newStruct); 
    newStruct->foo = lData->foo; 
    newStruct->bar = malloc(strlen(lData->bar) + 1); 
    strcpy(newStruct->bar, lData->bar); 
    ... 
    return newStruct; 
} 

И, наконец, дель указывает на функцию, которая освобождает элементы данных:

void delInt(void * data) 
{ 
    free(data); 
} 

void delMyStruct(void * data) 
{ 
    struct myStruct * lData = data; 
    free(lData->bar); 
    ... 
    free(lData); 
} 

Теперь вашим алгоритмам списка не нужно беспокоиться о поведении типа; они просто ссылаются на соответствующую функцию через указатель функции:

void listAdd(struct generic_list * const theList, void * const data) 
{ 
    struct generic_node *cur = &(theList->head); 
    struct generic_node *entry = malloc(sizeof *entry); 
    entry->data = theList->cpy(data); 
    while (cur->next != NULL && theList->cmp(cur->next->data, entry->data) < 0) 
    cur = cur->next; 
    entry->next = cur->next; 
    cur->next = entry; 
} 
/** */ 
void listClear(struct generic_list * const theList) 
{ 
    struct generic_node *cur = theList->head.next; 
    while (cur != NULL) 
    { 
    struct generic_node *entry = cur; 
    cur = cur->next; 
    theList->del(entry->data); 
    free(entry); 
    } 
}