Общая функция управления списком в C?

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

typedef struct list_item list_item;

struct list_item
{
    list_item *next;
    ...data for node...
};

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

Иногда «...data for node...» будет просто «void *»; то есть элементы списка будут содержать указатели на следующий узел в списке (или NULL, если следующего узла нет) и указатели на данные.

typedef struct list list;

struct list
{
    list *next;
    void *data;
};

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

Вы спрашиваете об «универсальной» функции списка, но, вероятно, не существует единого универсального дизайна с одной функцией, и уж точно не простого. Существует ряд возможных наборов функций, которые могут создавать общие функции списков. Один набор, вдохновленный Lisp, будет состоять из:

void *car(list *lp);    // Return the data for the first item on the list
list *cdr(list *lp);    // Return the tail of the list
list *cons(list *lp1, list *lp2);   // Construct a list from lists lp1 and lp2

list *cond(list *lp, void *data);  // Append data item to list

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

Одно хорошее изложение, по общему признанию, на C++, можно найти в "Размышления о C++" Кенига. Идеи могут быть адаптированы в C довольно легко - это не так уж сложно (хотя управление хранилищем в C сложнее, чем в C++).

В C нет концепции «общих» указателей или объектов - самое близкое, что вы можете получить, - это использование указателя void*. Если вы хотите, чтобы один фрагмент кода мог обрабатывать любой тип данных, вам в значительной степени придется использовать указатели void*. Для типов данных, размер которых не превышает указателя, можно использовать приведение между типом и void*; для больших типов данных вам придется использовать динамическую память и указать члену void* на динамическую память. Только остерегайтесь утечек памяти!

typedef struct list_node {
  struct list_node *next;
  void *data;
} list_node;

void list_insert(list_node *node, void *data) {
  // ...
}

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

#define DEFINE_LIST(type) \
  typedef struct list_node_##type { \
    struct list_node_##type *next; \
    type data; \
  }

#define IMPLEMENT_LIST_INSERT(type) \
  void list_##type##_insert(list_node_##type *node, type data) { \
    ... \
  }

DEFINE_LIST(int);     // defines struct list_node_int
DEFINE_LIST(double);  // defines struct list_node_double
IMPLEMENT_LIST_INSERT(int);    // defines list_int_insert
IMPLEMENT_LIST_INSERT(double); // defines list_double_insert

В ядре Linux есть интересная реализация общего связного списка на языке C в заголовке linux / list.h. Это двусвязный список с головным узлом, который используется следующим образом:

struct mystruct {
    ...
    /* Contains the next and prev pointers */
    struct list_head mylist;
    ...
    /* A single struct can be in several lists */
    struct list_head another_list;
    ...
};

struct list_head mylist_head;
struct list_head another_list_head;

Некоторые интересные вещи в этом небольшом примере:

• Узел списка встроен в целевую структуру и не требует указателя данных.
• Узел списка не обязательно должен стоять в начале целевой структуры.
• Одна структура может быть одновременно в нескольких связанных списках.
• Указатели next и prev в списке указывают на struct list_head, а не на целевую структуру (в приведенном выше примере они указывают на &(foo->mylist) для первого списка и &(foo->another_list) для второго списка).

Все функции управления списком принимают указатели на struct list_head (и большинство из них вообще не заботится о том, является ли это отдельным головным узлом или одним из встроенных узлов). Чтобы перейти от struct list_head к целевой структуре, вы используете макрос list_entry (который аналогичен макросу containter_of из заголовка linux / kernel.h), который расширяется до простого вычитания указателя.

Поскольку это двусвязный список с головным узлом, вы можете в O(1):

• Проверьте, пуст ли список или нет узла ни в одном списке.
• Получите узел после или перед любым другим узлом (если узел является головным, вы получите первый или последний элемент списка).
• Вставьте узел после или перед любым другим узлом (если узел является головным, вы вставляете его в начало или конец списка).
• Удалите узел из списка (для этого вам понадобится только указатель на сам узел).
• Несколько других операций.

C и его стандартная библиотека не предлагают никаких функций, специфичных для списка.

Но есть библиотеки с множеством полезных функций для C, которые поддерживают типы данных, известные из других языков программирования: http://library.gnome.org/devel/glib/2.18/glib-data-types.html

Как упоминалось выше, я попытался использовать подход MACROS для создания функций управления списком. Легко создать процедуру операции INSERT, но сложно создать операции удаления и перемещения. За ним следует структура списка и подпись процедуры INSERT:

#define LIST_DEFINE(type) \
    struct list_node_##type \
    { \
        type *data; \`
        struct list_node_##type *next; \
   };

LIST_INSERT(&ListHead,&Data, DataType);

Где: ListHead - Глава связанного списка Data - Данные, для которых будет создан новый узел, и данные будут вставлены в узел. DataType - Тип данных переданных данных

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

Теперь, когда создается процедура LIST_DELETE, узел, который необходимо удалить, будет идентифицирован с использованием уникального идентификатора в данных. Этот идентификатор также передается в подпрограмме MACRO как ключ, который будет заменен в расширении MACRO. Обычная подпись может быть:

LIST_DELETE(&ListHead, DataType, myvar->data->str, char*);

Где: ListHead - Глава связанного списка DataType - Тип данных для данных myvar->data->str - Уникальный ключ char* - Тип ключа

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

if ((keytype)ListHead->data->key == (keytype)key)

Он расширяется до

ListHead->data->myvar->data->str == myvar->data->str

А вот такой переменной вроде: ListHead->data->myvar->data->str нет

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

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

Для моих учений я пришел к разработке этого «общего» модуля списка, вероятно, упрощенной версии модуля ядра Linux, с дополнительными, хотя и неоткрытыми ошибками, и который использует расширения gcc ... Любые комментарии приветствуются!

#ifndef _LISTE
#define _LISTE
#include <stdlib.h>
typedef struct liste_s {
  struct liste_s * suivant ;
} * liste ;


#define newl(t) ( (liste) malloc ( sizeof ( struct liste_s ) + sizeof ( t ) ) )
#define elt(l,t) ( * ( ( t * ) ( l + 1 ) ) )

#define liste_vide NULL
#define videp(l) ( l == liste_vide )
#define lvide() liste_vide
#define cons(e,l) \
  ({ liste res = newl(typeof(e)) ;      \
     res->suivant = l ; \
     elt(res,typeof(e)) = e ;           \
    res ; }) 

#define hd(l,t) ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; elt(res,t) ; })
#define tl(l)   ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; res->suivant ;})


#endif

Я пробовал что-то другое. Это еще один взгляд на то, как решить проблему

Если у нас есть следующая структура:

typedef struct token {
    int id;
    char *name;
    struct token *next;
} Token;

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

void* tail(void* list, void* (*f)(void *)) {
    void *head = list;

    while(f(head) != NULL) {
        head = f(head);
    }

    return head;
}

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

void* nextToken(void *a) {
    Token *t = (Token *) t;
    return (void *) (a->next);
}

Наконец, мы можем просто использовать:

Token *listTokens;
(...)
Token *lastToken = tail(listTokens, nextToken);