Spiegare list_for_each_entry e list_for_each_entry_safe

Question

Qualcuno può spiegare il funzionamento di list_for_each_entry e ... entry_safe loop in linux. E 'come

list_for_each_entry(type *cursor, struct list_head *list, member)

list_for_each_entry_safe(type *cursor, type *next, struct list_head *list,member)

Quali sono il ruolo di tutti questi parametri e come essi vengono utilizzati per attraversare la lista.

Grazie in anticipo

Answer 1

EDIT: mi dispiace, deve essere in ritardo, ho fatto un sacco di errori di battitura.

Sono puro divertimento! :) La differenza è che list_for_each_entry si interromperà se si elimina qualcosa mentre si itera l'elenco e list_for_each_entry_safe non (ovviamente, a spese di alcune istruzioni aggiuntive della CPU).

Il kernel ha optato per elenchi doppiamente collegati (che presumo tu abbia capito), sebbene in list.h ci sia un'implementazione di elenchi collegati singolarmente. L'elenco è solo:

struct list_head { 
    struct list_head *next; 
    struct list_head *prev; 
}; 

Si noti che lo stesso struct viene utilizzata sia per la "testa" della lista così come ogni nodo. Quando la lista è vuota, i membri della testata next e prev puntano semplicemente alla testa. Quindi, l'iterazione dell'elenco è solo un processo che inizia con il membro next della testata e che chiama un nodo, a meno che non sia lo stesso indirizzo di prev (quando ci si ferma). In caso contrario, viene invocato il corpo for ed è possibile utilizzare la macro container_of() per ottenere un puntatore alla struttura effettiva e giocare con esso. Quindi, nel terzo campo di for, passiamo semplicemente al prossimo next.

MODIFICA: whoops, mi scuso, hai chiesto una spiegazione dei parametri. Bene, vorrei controllare direttamente se fossi in te piuttosto che prendere la parola di qualcuno per questo. Per quelli, suggerirei lo stesso Kernel API docs, che almeno esiste per la libreria dell'elenco collegato. Sto cercando di ottenere un set di patch che li aggiunga anche alla libreria ad albero rosso-nero, ma far passare tutto questo può essere piuttosto un processo.

Anche di nota: http://kernelnewbies.org/FAQ/LinkedLists

Ecco un rapido esempio:

struct list_head my_actual_list; 
struct my_struct { 
    struct list_head node; 
    /* some other members */ 
}; 

/* in a function body somewhere... */ 
struct list_head *i; 
list_for_each(i, &my_actual_list) { 
    struct my_struct *obj = list_entry(i, struct my_struct, node); 
    // do something with obj 
} 

list_entry è solo un alias per container_of

EDIT # 2

OK, quindi in risposta alla tua domanda nei commenti, ho intenzione di espandere la mia risposta. Posso davvero apprezzare la difficoltà nell'afferrare questo concetto poiché contiene alcune strane cose rispetto ai contenitori C++ STL, array C, ecc., Ma una volta abituati agli idiomi, sembrerà del tutto naturale. Ancora in futuro, ti esorto davvero a iniziare a guardare la definizione di queste strutture, le funzioni & macros te stesso e cercare di mettere insieme una comprensione, quindi porre le domande.

Quindi, prima di tutto, ogni nodo nella vostra lista è una struttura che contiene un membro di tipo struct list_head e la lista sua auto è di tipo struct list_head. Quindi, chi è il contenitore e chi è il contenuto in questo caso, dipende semplicemente da come vengono utilizzati, ma in genere, sarà espresso nei nomi forniti da questi membri. Il tipo di iteratore è struct list_head *. Ecco un esempio e io sostituire il normale funzione & chiamate macro con il loro codice equivalente:

struct my_container { 
    struct list_head list; 
    int some_member; 
    /* etc. */ 
}; 

struct my_obj { 
    struct list_head node; 
    int some_member; 
    /* etc. */ 
}; 

void func() { 
    struct my_container container; 
    struct my_obj obj1, obj2; 
    struct list_head *i; 

    /* INIT_LIST_HEAD(&container.list); */ 
    container.list.next = &container.list; 
    container.list.prev = &container.list; 

    /* list_add_tail(&obj1.node); */ 
    container.list.prev = &obj1.node; 
    obj1.node.next = &container.list; 
    obj1.node.prev = &container.list; 
    container.list.next = &obj1.node; 

    /* list_add_tail(&obj2.node); */ 
    container.list.prev = &obj2.node; 
    obj2.node.next = &container.list; 
    obj2.node.prev = &obj1.node; 
    obj1.node.next = &obj2.node; 

    /* list_for_each(i, &container.list) { */ 
    for (i = container.list.next; i != &container.list; i = i->next) { 
     struct my_obj *obj = list_entry(i, struct my_obj, node); 
     /* do stuff */ 
    } 

} 

Now go read! :)