Use of double pointer in linux kernel Hash list implementation

Question

Hi, I am trying to understand Linux Kernel implementation of linked list and hash table. A link to the implementation is here. I understood the linked list implementation. But i am little confused of why double pointers is being used in hlist (**pprev). Link for hlist is here. I understand that hlist is used in implementation of hash table since head of the list requires only one pointer and it saves space. Why cant it be done using single pointer (just *prev like the linked list)? Please help me.

Answer 1

The reason can be found in one of the comments:

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

If you had *prev instead of **pprev, and because we are trying to save memory, we don't include *prev in the head, then our hlist implementation looks like this:

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

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

Notice that the prev pointer cannot point to the head, or head->first (unlike **pprev). This complicates the hlist implementation, as you'll see when we implement 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;
  }
}

Notice that prev has nothing to point to, in the above imeplementation of hlist_add_head(). So, now when you implement hlist_add_before() it looks like this:

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

Notice that now we need to pass in head as well to hlist_add_before(), which requires an extra push instruction for pushing head on the stack. Besides, there's an extra conditional check in the implementation, which further slows down things.

Now, try implementing other hlist operations, with *prev instead of **pprev, and you'll find out that your implementation is going to be slower than what you saw in the linux kernel.