Verwendung von Doppelzeigern in der Linux-Kernel-Hash-Listen-Implementierung

Ich versuche, die Linux-Kernel-Implementierung von verknüpften Listen und Hash-Tabellen zu verstehen. Einen Link zur Umsetzung finden Sie hier. Ich habe die Implementierung der verknüpften Liste verstanden. Aber ich bin etwas verwirrt darüber, warum Doppelzeiger in hlist (**pprev) verwendet werden. Link für hlist ist hier. Ich verstehe, dass hlist bei der Implementierung der Hash-Tabelle verwendet wird, da der Kopf der Liste nur einen Zeiger benötigt und Platz spart. Warum kann dies nicht mit einem einzelnen Zeiger erfolgen (nur *prev wie die verknüpfte Liste)? Bitte helfen Sie mir.

Antworten:

Der Grund ist in einem der Kommentare zu finden:

 547/*
  548 * Double linked lists with a single pointer list head.
  549 * Mostly useful for hash tables where the two pointer list head is
  550 * too wasteful.
  551 * You lose the ability to access the tail in O(1).
  552 */
 

Wenn Sie *prev anstelle von **pprev hatten und weil wir versuchen, Speicher zu sparen, fügen wir *prev nicht in den Kopf ein, dann sieht unsere Hlist-Implementierung so aus:

struct hlist_head {
   struct hlist_node *first = null;
 };
 struct hlist_node {
   struct hlist_node *next;
   struct hlist_node *prev;
 };
 

Beachten Sie, dass prev Zeiger darf nicht auf den Kopf oder head->first zeigen (im Gegensatz zu **pprev ). Dies verkompliziert die hlist-Implementierung, wie Sie sehen werden, wenn wir hlist_add_before() implementieren :

void
 hlist_init(struct hlist_head *head) {
   head->first = null;  
 }
 void
 hlist_add_head(struct hlist_head *head, struct hlist_node *node) {
   struct hlist_node *next = head->first;
   head->first = node;
   node->next = next;
   node->prev = NULL;
   if (next) {
     next->prev = node;
   }
 }
 

Beachten Sie, dass prev hat in der obigen Implementierung von hlist_add_head() nichts zu zeigen . Also, jetzt, wenn Sie hlist_add_before() implementieren sieht so aus:

void
 hlist_add_before(struct hlist_head *head,
                  struct hlist_node *node,
                  struct hlist_next *next) {
   hlist_node *prev = next->prev;
   node->next = next;
   node->prev = prev;
   next->prev = node;
   if (prev) {
     prev->next = node;
   } else {
     head->first = node;
   }
 }
 

Beachten Sie, dass wir jetzt head übergeben müssen sowie zu hlist_add_before() , was einen zusätzlichen push erfordert Anweisung zum Drücken von head auf dem Stapel. Außerdem gibt es eine zusätzliche Bedingungsprüfung in der Implementierung, die die Dinge weiter verlangsamt.

Versuchen Sie nun, andere hlist-Operationen mit *prev zu implementieren statt **pprev , und Sie werden feststellen, dass Ihre Implementierung langsamer sein wird als das, was Sie im Linux-Kernel gesehen haben.