Utilisation du double pointeur dans l'implémentation de la liste de hachage du noyau Linux

Question

J'essaie de comprendre l'implémentation du noyau Linux de la liste chaînée et de la table de hachage. Un lien vers l'implémentation est here. J'ai compris l'implémentation de la liste chaînée. Mais je suis un peu confus de pourquoi les pointeurs doubles sont utilisés dans hlist (** pprev). Le lien pour hlist est here. Je comprends que hlist est utilisé dans l'implémentation de la table de hachage puisque la tête de la liste ne nécessite qu'un seul pointeur et économise de l'espace. Pourquoi ne peut-il pas être fait en utilisant un seul pointeur (juste * prev comme la liste liée)? Aidez-moi, s'il vous plaît.

Answer 1

La raison se trouve dans l'un des commentaires:

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

Si vous aviez * prev au lieu de ** pprev, et parce que nous essayons de sauver la mémoire, nous ne pas inclure * prev dans la tête, notre mise en œuvre de hlist ressemble à ceci:

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

struct hlist_node { 
    struct hlist_node *next; 
    struct hlist_node *prev; 
}; 

Notez que le pointeur prev ne peut pas pointer vers la tête ou head->first (contrairement **pprev). Cela complique la mise en œuvre de hlist, comme vous le verrez quand nous mettre en œuvre 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; 
    } 
} 

Notez que prev n'a rien à indiquer, dans le imeplementation ci-dessus hlist_add_head(). Donc, maintenant lorsque vous implémentez hlist_add_before() il ressemble à ceci:

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

Notez que maintenant nous devons passer head aussi bien à hlist_add_before(), ce qui nécessite une instruction push supplémentaire pour pousser head sur la pile. En outre, il y a un contrôle conditionnel supplémentaire dans la mise en œuvre, qui ralentit encore plus les choses. Maintenant, essayez d'implémenter d'autres opérations hlist, avec *prev au lieu de **pprev, et vous découvrirez que votre implémentation sera plus lente que ce que vous avez vu dans le noyau Linux.