Verkettete Listen

Betriebssystem-Kernel benötigen wie viele andere Programme oft Listen von Datenstrukturen. Im Linux-Kernel hat es manchmal mehrere Implementationen verketteter Listen gegeben. Um die Menge doppelten Codes zu reduzieren, haben sich die Kernel-Entwickler auf eine Standardimplementation ringförmiger, doppelt verketteter Listen geeignet; alle, die Listen verarbeiten müssen, sollten diese Funktionalität verwenden, die mit dem Kernel 2.1.45 eingeführt wurde.

Um diesen Listenmechanismus zu verwenden, muß Ihr Treiber die Datei <linux/list.h> einbinden. Diese Datei definiert eine einfache Datenstruktur des Typs list_head:


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

In richtigem Code verwendete verkettete Listen bestehen fast immer aus irgendeiner Struktur, die jeweils einen Eintrag in der Liste beschreibt. Um die Listen-Funktionalität in Linux in Ihrem Code zu verwenden, müssen Sie nur einen list_head in den Strukturen einbauen, aus denen die Liste besteht. Wenn Ihr Treiber etwa eine Liste zu erledigender Dinge verwaltet, dann könnte die Deklaration folgendermaßen aussehen:


struct todo_struct {
    struct list_head list;
    int priority; /* treiberspezifisch */
    /* ... andere treiberspezifische Felder */
};

Der Kopf der Liste muß eine alleinstehende list_head-Struktur sein. Listen-Köpfe müssen vor der Verwendung mit dem Makro INIT_LIST_HEAD initialisiert werden. Der Kopf einer “Todo-Liste” könnte wie folgt deklariert und initialisiert werden:


struct list_head todo_list;

INIT_LIST_HEAD(&todo_list);

Alternativ dazu können Listen auch zur Kompilierzeit initialisiert werden:


LIST_HEAD(todo_list);

In <linux/list.h> sind mehrere Funktionen definiert, die auf Listen arbeiten:

list_add(struct list_head *new, struct list_head *head);

Diese Funktion fügt den Eintrag new unmittelbar nach dem Listenkopf ein — normalerweise am Anfang der Liste. Auf diese Weise können Stacks aufgebaut werden. Beachten Sie aber, daß head nicht der nominelle Kopf der Liste sein muß. Wenn Sie eine list_head-Struktur übergeben, die sich zufällig irgendwo mitten in der Liste befindet, dann gelangt der neue Eintrag unmittelbar dahinter. Weil Linux-Listen zirkulär sind, unterscheidet sich der Kopf der Liste nicht weiter von anderen Einträgen.

list_add_tail(struct list_head *new, struct list_head *head);

Fügt einen neuen Eintrag unmittelbar vor dem angegebenen Listenkopf ein — also am Ende der Liste. list_add_tail kann also zum Aufbau von FIFOs verwendet werden.

list_del(struct list_head *entry);

Der angegebene Eintrag wird aus der Liste entfernt.

list_empty(struct list_head *head);

Gibt einen von Null verschiedenen Wert zurück, wenn die Liste nicht leer ist.

list_splice(struct list_head *list, struct list_head *head);

Diese Funktion verknüpft zwei Listen durch Einfügen von list unmittelbar hinter head.

Die list_head-Strukturen sind für die Implementierung einer Liste von gleichartigen Strukturen geeignet, aber das aufrufende Programm ist oft mehr an den größeren Strukturen interessiert, die die Liste insgesamt ausmachen. Es gibt ein Makro namens list_entry, das einen Zeiger auf eine list_head-Struktur auf einen Zeiger auf die enthaltene Struktur abbildet. Dieses Makro wird folgendermaßen aufgerufen:


list_entry(struct list_head *ptr, type_of_struct, field_name);

wobei ptr ein Zeiger auf die verwendete struct list_head ist. type_of_struct ist der Typ der Struktur, die den ptr enthält, und field_name ist der Name des Listenfeldes in der Struktur. In unserer todo_struct-Struktur würde das Listenfeld einfach list heißen. Wir würden also einen Listeneintrag mit folgender Zeile in seine enthaltene Struktur konvertieren:


struct todo_struct *todo_ptr =
    list_entry(listptr, struct todo_struct, list);

An das Makro list_entry muß man sich erst gewöhnen, aber so schwierig zu verwenden ist es gar nicht.

Die Traversierung verketteter Listen ist einfach: Man muß einfach nur den Zeigern prev und next folgen. Nehmen wir als Beispiel an, daß wir die Liste der todo_struct-Elemente in der Reihenfolge absteigender Wichtigkeit sortieren wollen. Eine Funktion zum Einfügen eines neuen Eintrags würde dann etwa so aussehen:


void todo_add_entry(struct todo_struct *new)
{
    struct list_head *ptr;
    struct todo_struct *entry;

    for (ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next) {
        entry = list_entry(ptr, struct todo_struct, list);
        if (entry->priority < new->priority) {
            list_add_tail(&new->list, ptr);
            return;
        }
    }
    list_add_tail(&new->list, &todo_struct)
}

Die Datei <linux/list.h> definiert auch ein Makro namens list_for_each, das zu der for-Schleife expandiert, die in diesem Code verwendet wurde. Sie können sich wahrscheinlich schon denken, daß Sie vorsichtig mit dem Verändern der Liste während der Traversierung sein müssen.

Abbildung 10-1 zeigt, wie die einfache struct list_head zur Verwaltung der Liste von Datenstrukturen verwendet wird.

Abbildung 10-1. Die Datenstruktur list_head

Weil nicht alle Features, die list.h in Linux 2.4 bereitstellt, auch in älteren Kerneln zur Verfügung stehen, füllt sysdep.h die Lücke, indem es Makros und Funktionen zur Verwendung in älteren Kerneln deklariert.