Uso del doppio puntatore nell'implementazione della lista hash del kernel Linux

Sto cercando di capire l'implementazione del kernel Linux dell'elenco collegato e della tabella hash. Un link all'implementazione è qui. Ho capito l'implementazione dell'elenco collegato. Ma sono un po' confuso sul motivo per cui i doppi puntatori vengono utilizzati in hlist (** pprev). Il link per hlist è qui. Comprendo che hlist viene utilizzato nell'implementazione della tabella hash poiché l'intestazione dell'elenco richiede solo un puntatore e consente di risparmiare spazio. Perché non può essere fatto usando un puntatore singolo (solo *prev come l'elenco collegato)? Per favore aiutami.

Risposte:

Il motivo può essere trovato in uno dei commenti:

 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 */
 

Se avevi *prev invece di **pprev, e poiché stiamo cercando di risparmiare memoria, non includiamo *prev nell'intestazione, la nostra implementazione hlist sarà simile a questa:

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

Nota che il prev il puntatore non può puntare alla testa o a head->first (a differenza di **pprev ). Questo complica l'implementazione di hlist, come vedrai quando implementeremo hlist_add_before() :

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;
   }
 }
 

Nota che prev non ha nulla a che fare con la precedente implementazione di hlist_add_head() . Quindi, ora quando implementi hlist_add_before() si presenta così:

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;
   }
 }
 

Nota che ora dobbiamo passare head anche a hlist_add_before() , che richiede un ulteriore push istruzioni per spingere head sulla pila. Inoltre, c'è un ulteriore controllo condizionale nell'implementazione, che rallenta ulteriormente le cose.

Ora, prova a implementare altre operazioni hlist, con *prev invece di **pprev , e scoprirai che la tua implementazione sarà più lenta di quella che hai visto nel kernel Linux.