c 链表 - 是否可以创建一个独立于有效负载的迭代器函数？

所有，在我的应用程序中，我有许多正在创建的链接列表。例如，一个（struct record）保存具有数百个节点（文本行）的转录文本，而第二种类型的链接列表（struct srch_results）保存使用 strstr() 搜索第一个列表的搜索结果。应用程序中每个列表可以有多个列表。问题是我发现自己为每个列表类型重新创建每个正向/反向迭代器，这基本上是复制代码并更改列表的结构类型。例如，一组遍历struct record的函数和一组遍历struct srch_results的函数是：

// Simple structure to use as the base for depo double linked list
struct record
{
char *line;
int lineno;
int linetype;
struct record *prev;
struct record *next;
};

typedef struct record rec;

// Simple structure to use as the base for search results double linked list
struct srch_results
{
char *lineptr;
struct record *node;
struct srch_results *prev;
struct srch_results *next;
};

typedef struct srch_results srchres;

// general functions to operate on 'rec' type

void
rec_prn_node (rec *node) {
fprintf (stdout, "%s()  prev: %p  cur: %p  next: %p\n", __func__, node->prev, node, node->next);
}

void
rec_prn_payload (rec *node) {
fprintf (stdout, "%s() lineno: %d, linetype: %d line: %s\n",
    __func__, node->lineno, node->linetype, node->lineptr);
}

void
rec_iterfwd (void fnc (srchres *list), srchres *list) {

rec *iter = list;   // second copy to iterate list

if (iter ==  NULL) {
    fprintf (stdout,"%s(), The list is empty\n",__func__);
} else {
    do {
    fnc (iter);
    iter = iter->next;
    } while (iter != list);
}
}

// general functions to operate on 'srchres' type

void
srch_prn_node (srchres *node) {
fprintf (stdout, "%s()  prev: %p  cur: %p  next: %p\n", __func__, node->prev, node, node->next);
}

void
srch_prn_payload (srchres *node) {
fprintf (stdout, "%s() node: %p lineptr: %s\n", __func__, node->node, node->lineptr);
}

void
srch_iterfwd (void fnc (srchres *list), srchres *list) {

srchres *iter = list;   // second copy (set to last) to iterate list

if (iter ==  NULL) {
    fprintf (stdout,"%s(), The list is empty\n",__func__);
} else {
    printf ("in %s()\n", __func__);
    do {
    fnc (iter);
    iter = iter->next;
    } while (iter != list);
}
}

有没有办法创建可以在任一列表上操作的通用 void 迭代器类型？一些通用迭代器和通用 typedef 允许传递回调函数和列表地址，以便迭代器遍历给定列表，调用每个节点上提供的函数？

所有结构都具有结构地址和地址->下一个、地址->上一个。我尝试根据其他一些利用回调的 void 迭代器函数来定义 void * 函数，但我似乎不是在我传递的列表中迭代地址，而是从堆栈中获取地址。 （即 list->prev 是堆栈上前一个列表的地址，而不是列表中前一个节点的地址）。好消息是，通缉列表地址实际上最终出现在回调中，只是不是以我想要的可用方式。

// generic linked-list-iterator struct to hold (prev: cur: next:) pointers
struct lliterator
{
struct lliterator *prev;
struct lliterator *next;
};

typedef struct lliterator lliter;

void *
srch_prn_node (lliter *node) {
fprintf (stdout, "%s()  prev: %p  cur: %p  next: %p\n", 
    __func__, node->prev, node, node->next);
return NULL;
}

void iterator (void *fnc (void *list), void *list) {

lliter *iter = list; // second copy (set to last) to iterate list

if (iter ==  NULL) {
    fprintf (stdout,"%s(), The list is empty\n",__func__);
} else {
    do
    {
    fnc (iter);
    iter = iter->next;
    } while (iter != list);
}
}

// called in the code as

iterator ((void *)srch_prn_node2, (void *)sresults);

这可能是不可能的，但目的是将现有结构地址作为 void 传递，然后使用 typedef 结构迭代器对该地址进行操作，该迭代器包含与传递的每个列表中包含的成员等效的 ->next 和 ->prev 成员。上面的示例可以编译，但运行时，当回调到达堆栈上的最后一个列表时，它会出现段错误。 （即，创建一个结构体记录和一个结构体 srch_results 后，它将迭代两次，在出现段错误之前为每个列表提供地址。这样的事情是否可能，或者是否缺少我能够找到答案的示例？

你有多种选择。

1）使用TAILQ宏see here.

2) 创建一个包含指向数据的通用指针的节点链表：

typedef struct Node {
    struct Node *prev;
    struct Node *next;
    void *data;
} Node;

然后您可以迭代列表Nodes，并投射data指向您认为列表包含的任何类型的指针。在这种情况下，Node必须独立于数据进行分配。另外，如果您从其他指针访问数据，您将无法找到关联的数据Node除非数据指向Node.

3）创建一个没有数据指针的节点，并将其嵌入到您的数据结构中。

typedef struct Node {
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct DataA {
    char something;
    Node node;
    int whatever;
} DataA;

typedef struct DataB {
    char dunno;
    Node node;
    int noclue;
} DataB;

然后您可以从指针转换为Node通过向后移动指针来指向指向封闭数据的指针：

DataA *p = (DataA*)((uintptr_t)pNodeA - offsetof(DataA, node));
DataB *p = (DataB*)((uintptr_t)pNodeB - offsetof(DataB, node));

请注意，如果您将Node在数据开始时，您不需要调整指针的值，因此您可以简单地从Node* to DataA* or DataB*.

在这种情况下，每条数据都有自己的Node，并且你不需要Node和数据相互指向。