Hinweise zur Verwendung der verknüpften Liste des Linux-Kernel-Gerätetreibers

/********************
 * Anwendung von verknüpften Listen im Kernel************************/

(1) Einleitung

Im Linux-Kernel werden zahlreiche verknüpfte Listenstrukturen zum Organisieren von Daten verwendet, darunter Gerätelisten und die Datenorganisation in verschiedenen Funktionsmodulen. Die meisten dieser verknüpften Listen verwenden eine recht schöne verknüpfte Listendatenstruktur, die in include/linux/list.h implementiert ist.

Die Definition der Datenstruktur der verknüpften Liste ist einfach:

Struktur list_head {
 Struktur list_head *next, *prev;
};

Die list_head-Struktur enthält zwei Zeiger prev und next, die auf die list_head-Struktur zeigen. Die Datenstruktur des Kernels ist normalerweise in einer doppelt zirkulären verknüpften Liste organisiert.

Anders als bei dem zuvor vorgestellten Modell der doppelt verketteten Listenstruktur verfügt der Listenkopf hier über keine Datendomäne. In verknüpften Listen des Linux-Kernels sind die verknüpften Listenknoten nicht in der Datenstruktur enthalten, sondern in der Datenstruktur. wie:

Struktur meine_Struktur{
 Struktur list_head-Liste;
 unsignierter langer Hund;
 ungültig *Katze;
};

Die verknüpfte Liste in Linux hat keinen festen Header und der Zugriff kann von jedem beliebigen Element aus beginnen. Um eine verknüpfte Liste zu durchlaufen, müssen Sie nur bei einem Knoten beginnen und dem Zeiger folgen, um zum nächsten Knoten zu gelangen, bis Sie zum ursprünglichen Knoten zurückkehren. Jeder einzelne Knoten kann als Kopf einer verknüpften Liste bezeichnet werden.

(2) Initialisierung der verknüpften Liste

a. Statisch

Wenn Sie eine verknüpfte Liste statisch zur Kompilierzeit erstellen und direkt darauf verweisen, gehen Sie folgendermaßen vor:

Struktur mein_Struktur mein={
 .lost = LIST_HEAD_INIT(mine.list);
 .Hund = 0,
 .cat = NULL
};
//oder statischer LIST_HEAD(fox);
/*Gleich zu struct list_head fox = LIST_HEAD_INIT(fox); */

b. Dynamisch

Struktur meine_Struktur *p;
p = kmalloc(GFP_KERNEL, Größe von(meine_Struktur));
p->Hund = 0;
p->Katze = NULL;
INIT_LIST_HEAD(&p->Liste);

(3) Operationsliste

Der Kernel bietet eine Reihe von Funktionen zum Bedienen verknüpfter Listen.

Beachten! Diese Funktionen verwenden alle einen oder mehrere Zeiger der Struktur „list_head“ als Parameter. Definiert in <linux/list.h>

a. Knoten hinzufügen

list_add(Struktur list_head *new, 
     Struktur list_head *head);
//Fügen Sie nach dem Kopfknoten der angegebenen verknüpften Liste einen neuen Knoten ein

b. Fügen Sie den Knoten am Ende der verknüpften Liste hinzu

list_add_tail(Struktur list_head *new, 
     Struktur list_head *head);
//Füge einen neuen Knoten vor dem Kopfknoten der angegebenen verknüpften Liste ein

c. Löschen Sie einen Knoten aus der verknüpften Liste

list_del(Struktur list_head *eintrag);
// Eintrag aus der verknüpften Liste entfernen

d. Verschieben Sie einen Knoten von einer verknüpften Liste in eine andere

list_move(Struktur list_head *list, 
     Struktur list_head *head);

Entfernen Sie ein Listenelement aus einer verknüpften Liste und fügen Sie es nach dem Kopf ein

e.list_empty(Struktur list_head *head);

Wenn die verknüpfte Liste leer ist, wird ein Wert ungleich Null zurückgegeben, andernfalls 0.

f. Verknüpfte Listen zusammenführen

list_splice(Struktur list_head *list, 
      Struktur list_head *head);
//Beachten! Die neue verknüpfte Liste enthält nicht den Listenknoten

(4) Durchlaufen der verknüpften Liste

Die verknüpfte Liste selbst ist nicht wichtig. Wichtig ist der Zugriff auf die Struktur, die die verknüpfte Liste enthält.

a. Holen Sie sich den Zeiger auf die Struktur, die die verknüpfte Liste enthält, vom Zeiger der verknüpften Liste

list_entry(Struktur list_head *ptr,
      Strukturtyp, 
      Feldname);

• ptr: list_head-Zeiger
• type_of_struct: der Strukturtyp, der ptr enthält
• field_name: der Name des verknüpften Listenfelds in der Struktur

wie:

meine_Struktur *p = (Listenkopf *ptr, meine_Struktur, Liste);

b. Durchlaufen Sie die verknüpfte Liste

list_for_each(Struktur list_head *cursor,
       Struktur list_head *list);
//Wird oft in Verbindung mit list_entry verwendet//Hinweis! Beim Durchlaufen mit list_for_each wird der Kopfknoten nicht einbezogen

c. Holen Sie sich den Zeiger auf die große Struktur während der Durchquerung

Liste_für_jeden_Eintrag(Typ *Cursor, 
      Struktur list_head *list,
      Mitglied);

d. Geben Sie beim Durchlaufen der verknüpften Liste jeden durchlaufenen Knoten frei

Liste_für_jeden_Eintrag_sicher(Typ *Cursor, 
     Typ *tmp;
     Struktur list_head *list,
     Mitglied);

Zusammenfassen

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels einen gewissen Lernwert für Ihr Studium oder Ihre Arbeit hat. Vielen Dank für Ihre Unterstützung von 123WORDPRESS.COM. Wenn Sie mehr darüber erfahren möchten, schauen Sie sich bitte die folgenden Links an