c linked list - is it possible to create a payload independent iterator function?

Question

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

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?

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

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?

Answer 1

You have several choices.

1) Use the TAILQ macros see here.

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

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.