C连接列表 - 是否有可能建立一个有效载荷独立迭代函数？ [英] c linked list - is it possible to create a payload independent iterator function?

问题描述

所有，在我的应用我有一些正在创建的链接列表。例如，一个（结构记录）拥有几百个节点（文本行）的记录文本，第二类链表（结构srch_results）从与搜索的的strstr第一个列表保存搜索结果（）。可以有各应用内的多个列表。问题是，我发现自己重新为它基本上复制code和更改列表中的结构类型，每个列表类型每个正向/反向迭代。例如，一组的遍历结构记录功能和横穿结构srch_results一组是：

All, in my application I have a number of linked lists that are being created. For example one (struct record) holds the transcript text with several hundred nodes (lines of text), and a second type linked list (struct srch_results) holds search results from searching the first list with strstr(). There can be multiple lists of each within the application. The issue is I find myself recreating each forward/reverse iterator for each list type which is basically duplicating the code and changing the struct type for the list. For example, one set of functions that traverse struct record and one set that traverses struct srch_results are:

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

有没有一种方法来创建既可以列表进行操作的通用空迭代器类型？一些通用的迭代和通用的typedef，将允许一个回调函数和列表的地址要传递这样的迭代器会遍历给定列表中呼吁每个节点上所提供的功能？

Is there a way to create a generic void iterator type that could operate on either list? Some generic iterator and generic typedef that would allow a callback function and list address to be passed such that the iterator would traverse the given list calling the provided function on each node?

所有结构具有结构体地址和寻址>下，地址 - > $ P $光伏。我已经定义基于一些，利用回调其他无效迭代函数void *的功能的尝试，但不是我通过列表中的地址进行迭代，我似乎从堆栈中获取地址。 （即列表 - > preV是previous名单栈上的地址而不是列表中的previous节点）。好消息是，通缉名单的地址实际上是在回调结束了，只是没有在使用的方式，我意。

All of the structures have the struct address and address->next, address->prev. I have made an attempt defining void * functions based on some of the other void iterator functions that utilize a callback, but instead of iterating addresses within the list I pass, I appear to be getting address from the stack. (i.e. list->prev is the address of the previous list on the stack instead of the previous node within the list). The good news is that the wanted list address is actually ending up in the callback, just not in the usable way I intended.

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

这是不可能的，但目的是通过在现有结构地址无效，然后用typedef结构迭代器，其中包含了地址进行操作 - >下一个和 - > $ P $光伏成员等同于包含在每个清单的传递。上述例子编译，但在运行时，它当回调达到什么样子堆栈上的最后一个列表出现segfaults。 （即一个结构的记录和一个结构srch_results创建的，它会遍历两次段错误之前，每个列表提供地址。是这样的可能，或者是缺乏的例子我能找到本身的答案吗？

This may not be possible, but the intent was to pass the existing struct address as void and then operate on that address with typedef struct iterator which contains both ->next and ->prev members equivalent to those contained in each of the lists passed. The above example compiles, but when run, it segfaults when the callback reaches what looks like the last list on the stack. (i.e., with one struct record and one struct srch_results created, it will iterate twice providing the address for each list before segfaulting. Is something like this possible, or is the lack of examples I was able to find an answer in and of itself?

推荐答案

您有几种选择。

1）使用TAILQ宏看到这里。

1) Use the TAILQ macros see here.

2）创建包含一个通用指针到数据节点的链接表

2) Create a linked-list of nodes that contain a generic pointer to the data:

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

您就可以遍历节点个名单，并投了数据指向任何类型您认为该列表中包含的内容。在这种情况下，节点必须分配独立的数据。另外，如果你来从其他指针数据，您将无法找到相关的节点，除非数据点回节点。

You can then iterate over a list of Nodes, and cast the data pointer to whatever type you think that list contains. In this case, the Node must be allocated independently of the data. Also, if you come to the data from some other pointer, you will not be able to find the associated Node unless the data points back to the Node.

3）创建无数据指针的节点，并嵌入到你的数据结构。

3) Create a node without a data pointer, and embed it into your data struct.

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;

然后，您可以从一个指针转换为节点通过向后移动指针的指针封闭的数据：

You can then convert from a pointer to a Node to a pointer to the enclosing data by moving the pointer backwards:

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

请注意，如果您将节点在数据的开始，你并不需要调整指针的值，这样你就可以简单地从投节点* 到数据A * 或数据B * 。

Note that if you place the Node at the start of the data, you don't need to adjust the value of the pointer, so you can simply cast from the Node* to DataA* or DataB*.

在这种情况下，每一个数据都带有自己的节点，你不需要节点和数据指向彼此

In this case, every piece of data comes with its own Node, and you don't need the Node and the data to point to one another.

这篇关于C连接列表 - 是否有可能建立一个有效载荷独立迭代函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！