resueltos - c lista enlazada: ¿es posible crear una función de iterador independiente de la carga útil?

listas enlazadas ats

Question

Todos, en mi aplicación tengo una cantidad de listas enlazadas que se están creando. Por ejemplo, uno (registro de estructura) contiene el texto de la transcripción con varios cientos de nodos (líneas de texto) y una segunda lista vinculada de tipo (struct srch_results) mantiene los resultados de la búsqueda de la primera lista con strstr (). Puede haber múltiples listas de cada uno dentro de la aplicación. El problema es que me encuentro recreando cada iterador adelante / atrás para cada tipo de lista que básicamente está duplicando el código y cambiando el tipo de estructura para la lista. Por ejemplo, un conjunto de funciones que atraviesan el registro de estructura y un conjunto que atraviesa struct srch_results son:

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

¿Hay alguna manera de crear un tipo genérico de iterador vacío que pueda operar en cualquiera de las listas? ¿Algún tipo de iterador genérico y typedef genérico que permitiría pasar una función de devolución de llamada y una dirección de lista para que el iterador recorra la lista dada llamando a la función proporcionada en cada nodo?

Todas las estructuras tienen la dirección de estructura y dirección-> siguiente, dirección-> prev. Intenté definir las funciones void * en función de algunas de las otras funciones del iterador vacío que utilizan una devolución de llamada, pero en lugar de iterar las direcciones dentro de la lista que paso, parece que obtengo la dirección de la pila. (es decir, list-> prev es la dirección de la lista anterior en la pila en lugar del nodo anterior dentro de la lista). La buena noticia es que la dirección de la lista de los buscados realmente está terminando en la devolución de llamada, pero no de la manera que yo quería.

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

Esto puede no ser posible, pero la intención era pasar la dirección de estructura existente como nula y luego operar en esa dirección con typedef struct iterator que contiene tanto -> next y -> prev miembros equivalentes a los contenidos en cada una de las listas pasadas. El ejemplo anterior compila, pero cuando se ejecuta, segmenta cuando la devolución de llamada alcanza lo que parece ser la última lista en la pila. (es decir, con un registro struct y un struct srch_results creados, se repetirá dos veces proporcionando la dirección para cada lista antes de segfaulting. ¿Es posible algo así o es la falta de ejemplos que pude encontrar una respuesta en sí misma?

Answer 1

Tienes varias opciones.

1) Utilice las macros TAILQ ver aquí .

2) Cree una lista enlazada de nodos que contenga un puntero genérico a los datos:

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

Luego puede iterar sobre una lista de Node , y convertir el puntero de data al tipo que crea que contiene esa lista. En este caso, el Node debe asignarse independientemente de los datos. Además, si llega a los datos de otro puntero, no podrá encontrar el Node asociado a menos que los datos vuelvan al Node .

3) Cree un nodo sin puntero de datos e incrústelo en su estructura de datos.

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;

A continuación, puede convertir desde un puntero a un Node a un puntero a los datos adjuntos moviendo el puntero hacia atrás:

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

Tenga en cuenta que si coloca el Node al comienzo de los datos, no necesita ajustar el valor del puntero, por lo que simplemente puede convertir desde el Node* a DataA* o a DataB* .

En este caso, cada dato viene con su propio Node , y no es necesario que el Node y los datos se señalen entre sí.