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

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

1 голос
/ 30 июля 2009

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

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

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

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

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

Ответы [ 7 ]

3 голосов
/ 30 июля 2009

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

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

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

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

3 голосов
/ 30 июля 2009

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

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);
    }
}
1 голос
/ 30 июля 2009

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

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);
  }
}
1 голос
/ 30 июля 2009

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

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() */
1 голос
/ 30 июля 2009

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

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) для любого списка, который следует этому шаблону.

0 голосов
/ 30 июля 2009

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

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

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

0 голосов
/ 30 июля 2009

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

...