Uso de doble puntero en la implementación de la lista Hash del kernel de Linux

Uso de doble puntero en la implementación de la lista Hash del kernel de Linux


Estoy tratando de entender la implementación del kernel de Linux de la lista vinculada y la tabla hash. Un enlace a la implementación está aquí. Entendí la implementación de la lista enlazada. Pero estoy un poco confundido de por qué se usan punteros dobles en hlist (** pprev). El enlace para hlist está aquí. Entiendo que hlist se usa en la implementación de la tabla hash ya 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.


Respuestas:


El motivo se puede encontrar 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 el encabezado, entonces nuestra implementación de hlist se verá así:


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

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

Observe que prev no tiene nada que señalar, en la implementación anterior de hlist_add_head() . Entonces, ahora cuando implementas 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;
}
}

Note que ahora necesitamos pasar head también a hlist_add_before() , que requiere un push adicional instrucciones para presionar 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 descubrirá que su implementación será más lenta de lo que vio en el kernel de Linux.