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

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 году (до появления шаблонов).

---

(ПРАВКА) Историческая справка - для болезненно любопытных, Дьюхерст и Старк Программирование на C++ который пытался стать своего рода K & R для C ++, подробно описывает, как использовать макросы для эмуляции (все еще спекулятивного на момент написания) поведения шаблона, которым мы сейчас наслаждаемся.Большинство принципов естественным образом будут перенесены обратно на "C".

Answer 2

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

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 3

Если все ваши структуры Node объявлены с указателем 'next' как первый " member " ;, таким образом:

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 4

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

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 5

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

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, если * a < * b, 0, если * a == * b, и 1, если * a > * b, где a и b были преобразованы из 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;
}

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

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

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

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

Answer 6

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

Answer 7

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

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

Если вы действительно не можете этого сделать, вы можете собрать мусор для бедного человека, поместив подсчитывающие ссылки оболочки вокруг ваших указателей. Посмотрите & Quot; умные указатели & Quot ;. Но это гораздо больше проблем, чем управляемая память.