Можно ли написать универсальную функцию обхода в C для различных структур списков, если они содержат поле «next»? - PullRequest
Новая
       13

Можно ли написать универсальную функцию обхода в C для различных структур списков, если они содержат поле «next»?

3 голосов
/ 21 ноября 2019

Впервые задаю вопрос, но я посмотрел вокруг Google и stackoverflow, чтобы увидеть, спрашивал ли кто-то что-то подобное раньше. В malloc, переделывая и освобождая , это выглядело так, как будто OP спросил что-то подобное, например. Но все было сложнее.

Мне было интересно, возможно ли создать универсальную функцию для структуры списка в C, которая пересекает список, учитывая, что вы знаете, что у различных типов структур всегда будет «next»field.

Например, учитывая эти две структуры типа списка: 

typedef struct _list1 {
    int value;
    list1 *next;
} list1;

typedef struct _list2 {
    int value;
    char *string;
    list2 *next;
} list2;

Можно ли создать общую функцию void freeList((void *) list) или что-то похожее на приведенное ниже? Я знаю, что написать две бесплатные функции для каждого отдельного списка очень просто. 

void freeList((void *) list) {
    // Included this because the structs would have different sizes
    // so I thought it would be possible to cast it in order to properly dereference the field.
    if (sizeof *list == sizeof list1)
        *list = (list1) list;
    else if (sizeof *list == sizeof list2)
        *list = (list2) list;

    if (!list) return;
    else {
        free(list->next);
        free(list);
    }
}

Пока что мои эксперименты с приведенным выше кодом не увенчались успехом, учитывая, что gcc будет жаловаться на разыменованиеvoid * указатель.

Ответы [ 3 ]

3 голосов
/ 21 ноября 2019

Создание гетерогенного списка может быть достигнуто путем использования тегового объединения или просто тега и приведением: 

struct list_item {
    struct list_item *next;
    enum datatype type;
    void *contents;
};

или 

struct list_item {
    struct list_item *next;
    enum datatype type;
    union {
       int some_int;
       char some_char;
    } contents;
};

Затем, просматривая список, выпросто нужно проверить тип, сохраненный в type, перед использованием содержимого элемента.

Эта проверка: 

if (sizeof *list == sizeof list1)
    *list = (list1) list;
else if (sizeof *list == sizeof list2)
    *list = (list2) list;

не работает, потому что sizeof являетсястатическая конструкция: ее значение определяется во время компиляции. Вы просто просите sizeof void.

1 голос
/ 21 ноября 2019

возможно ли создать универсальную функцию для структуры списка в C, которая пересекает список, если вы знаете, что различные типы структур всегда будут иметь поле "next".

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

typedef struct _list1 {
    list1 *next;
    int value;
} list1;

typedef struct _list2 {
    list2 *next;
    int value;
    char *string;
} list2;

Это не чистый код, потому что компилятор может переупорядочивать (и дополнять) поля структуры, но в целом это должно работать.

Возможно ли создать общую функцию void freeList ((void) * list) или что-то похожее на ...

Это возможно, если ваши структуры не относится к неправильной памяти;или они делают, но единообразным (и известным) способом (обратите внимание, что первый случай - это подслучай этого последнего).

Если структуры содержат указатели, указывающие на память, которая должна быть освобождена, фактическипри освобождении структуры функция freeList () также должна освободить указанную память. Несколько решений приходят мне на ум:

1 - Если все разные структуры содержат одинаковую структуру «указателей», процедура может освободить эти указатели единообразным образом, заранее зная, что делать. В таком сценарии можно также использовать поля указателя, которые используются не всеми структурами, а только некоторыми.

2 - Каждый отдельный экземпляр структуры может содержать некоторое вспомогательное поле, описывающеерасположение указателя. Например, сразу после поля «next» другое поле «mempntcnt» может указать, сколько указателей (которые должны быть освобождены) следуют за полем «next». Или этот «mempntcnt» может быть передан в качестве параметра freeList ().

3 - Эта проблема может решаться полностью отделенным механизмом, выходящим за рамки freeList (). Многое зависит от конечного использования: я имею в виду, что для данного (своего рода) связанного списка сначала вызовите процедуру, которая освобождает всю память, на которую ссылается сам список, , а затем освобождает список, вызывая общий список freeList(). В конце концов, если нужны разные структуры, то для них используются разные процедуры ...

Надеюсь, я достаточно ясен ...

0 голосов
/ 21 ноября 2019

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

typedef struct list1 {
    // next pointer must be first
    struct list1 *next;
    int value;
} list1;

typedef struct list2 {
    // next pointer must be first
    struct list2 *next;
    int value;
    char *string;
} list2;

void freeList(void *list) {
    if (list) {
        freeList(*(void**)list);
        free(list);
    }
}
...