Używanie podwójnego wskaźnika w jądrze Linuksa Implementacja listy skrótów

Question

Próbuję zrozumieć implementację jądra Linuksa z listą linków i tabelą mieszania. Łącze do implementacji to here. Zrozumiałem implementację listy powiązanej. Ale jestem trochę zdezorientowany, dlaczego podwójne wskaźniki są używane w hlist (** pprev). Link do hlist to here. Rozumiem, że hlist jest używany w implementacji tablicy mieszającej, ponieważ szef listy wymaga tylko jednego wskaźnika i oszczędza miejsce. Dlaczego nie można tego zrobić za pomocą pojedynczego wskaźnika (po prostu * prev jak połączona lista)? Proszę pomóż mi.

Answer 1

Powodem można znaleźć w jednym z komentarzy:

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

Jeśli miał * prev zamiast ** pprev i dlatego staramy się zaoszczędzić pamięć, nie zawierają w prev * głowica, wówczas nasza realizacja hlist wygląda następująco:

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

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

Zauważ, że wskaźnik prev nie może wskazywać na głowie, albo head->first (w przeciwieństwie **pprev). To komplikuje realizację hlist, jak zobaczysz gdy wdrożymy 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; 
    } 
} 

Zauważ, że nie ma nic do prev wskazywać, w powyższym imeplementation z hlist_add_head(). Więc teraz, kiedy wdrożyć hlist_add_before() wygląda to tak:

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

Zauważ, że teraz musimy przejść w head także do hlist_add_before(), co wymaga dodatkowego push dyspozycję popychanie head na stosie. Poza tym w implementacji jest dodatkowe sprawdzanie warunkowe, które dodatkowo spowalnia działanie.

Teraz spróbuj wdrożyć inne operacje hlist, z *prev zamiast **pprev, a przekonasz się, że twoja implementacja będzie wolniejsza niż to, co widziałeś w jądrze Linux.