Uso de doble puntero en el kernel de Linux Implementación de la lista Hash

Question

Estoy tratando de comprender la implementación del Kernel de Linux de la lista vinculada y la tabla hash. Un enlace a la implementación es here. Entendí la implementación de la lista vinculada. Pero estoy un poco confundido de por qué se usan los dos puntos en hlist (** pprev). El enlace para hlist es here. Entiendo que hlist se usa en la implementación de la tabla hash dado que el encabezado de la lista requiere solo un puntero y ahorra espacio. ¿Por qué no se puede hacer usando un solo puntero (solo * anterior como la lista vinculada)? Por favor, ayúdame.

Answer 1

La razón puede encontrarse en uno de los comentarios:

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 tuviera * prev en lugar de ** pprev, y debido a que estamos tratando de ahorrar memoria, no incluimos * prev en la cabeza, entonces nuestra aplicación hlist se ve así:

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

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

en cuenta que el puntero prev no puede apuntar a la cabeza, o head->first (a diferencia de **pprev). Esto complica la implementación hlist, como se verá cuando aplicar 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; 
    } 
} 

en cuenta que prev no tiene nada que señalar, en el imeplementation encima de hlist_add_head(). Por lo tanto, ahora cuando se implementa hlist_add_before() se ve así:

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

en cuenta que ahora tenemos que pasar en head así a hlist_add_before(), que requiere una push instrucción adicional para empujar head en la pila. Además, hay una verificación condicional adicional en la implementación, lo que ralentiza aún más las cosas.

Ahora, intente implementar otras operaciones hlist, con *prev en lugar de **pprev, y verá que su implementación va a ser más lenta que la que vio en el kernel de Linux.