Erkläre list_for_each_entry und list_for_each_entry_safe

Question

Kann jemand die Funktionsweise von list_for_each_entry und ... entry_safe loop in Linux erklären. Es ist wie

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)

Was die Rolle all dieser Parameter sind und wie sie verwendet werden, um die Liste zu durchqueren.

Vielen Dank im Voraus

Answer 1

EDIT: sorry, muss es zu spät, ich habe eine Menge Fehler gemacht haben.

Sie sind purer Spaß! :) Der Unterschied ist, dass list_for_each_entry bricht, wenn Sie etwas während der Iteration der Liste löschen und list_for_each_entry_safe wird nicht (natürlich auf Kosten von einigen zusätzlichen CPU-Anweisungen).

Der Kernel hat sich auf doppelt verkettete Listen (von denen ich vermute, dass Sie das verstehen) entschieden, obwohl es in list.h eine singulär verknüpfte Listenimplementierung gibt. Ihre Liste ist nur:

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

Beachten Sie, dass die gleiche Struktur für verwendet wird, sowohl der „Kopf“ der Liste sowie jeden Knoten. Wenn die Liste leer ist, zeigen die Mitglieder des Kopfes next und prev nur auf den Kopf selbst. Daher ist das Iterieren der Liste nur ein Vorgang, bei dem mit dem Mitglied des Kopfes next gestartet wird und dieser Knoten aufgerufen wird, es sei denn, es ist die gleiche Adresse wie prev (wenn Sie anhalten). Andernfalls wird Ihr for Body aufgerufen und Sie können das Makro container_of() verwenden, um einen Zeiger auf Ihre tatsächliche Struktur zu erhalten und damit zu spielen. Dann, im 3. Feld der for, bewegen wir uns einfach zum nächsten next.

EDIT: Whoops, ich entschuldige mich, Sie fragten nach einer Erklärung der Parameter. Nun, ich würde es direkt überprüfen, wenn ich du wäre, anstatt jemandes Wort dafür zu nehmen. Für diese würde ich vorschlagen, die Kernel API docs selbst, die mindestens für die Linked-List-Bibliothek existieren. Ich versuche, einen Patch durchzusetzen, der sie auch für die Rot-Schwarz-Baum-Bibliothek hinzufügen wird, aber es kann ein ziemlicher Prozess sein, Dinge durchzubringen.

Auch der Hinweis: http://kernelnewbies.org/FAQ/LinkedLists

Hier ist ein kurzes Beispiel:

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 ist nur ein Alias ​​für container_of

EDIT # 2

OK, also in Antwort auf Ihre Frage in Kommentaren, werde ich nur meine Antwort erweitern. Ich kann die Schwierigkeit wirklich schätzen, dieses Konzept zu begreifen, da es ein paar seltsame Dinge im Vergleich zu C++ - STL-Containern, C-Arrays usw. hat, aber sobald Sie sich an die Idiome gewöhnt haben, wird es ganz natürlich erscheinen. Noch in der Zukunft, ich fordere Sie wirklich auf, die Definition für diese Strukturen zu betrachten, Funktionen & Makros selbst und versuchen, ein Verständnis zusammenzusetzen, dann stellen Sie die Fragen.

So zunächst einmal, jeder Knoten in der Liste ist eine Struktur, die ein Mitglied des Typs enthält struct list_head und die Liste seine Selbst von struct list_head Typ ist. Also, wer ist der Container und wer ist der Inhalt in diesem Fall, hängt einfach davon ab, wie sie verwendet werden, aber in der Regel wird es in den Namen diese Mitglieder ausgedrückt werden ausgedrückt. Der Typ des Iterators ist struct list_head *. Hier ist ein Beispiel, und ich werde die normalen Funktion & Makro Anrufe mit ihrem entsprechenden Code ersetzt werden:

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! :)