Use of double pointer in linux kernel Hash list implementation

Question

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.

Answer 2

There are two type of lists: regular list_head type, and hash list(hlist). "list_head" type has only one struct, i.e. "struct list_head". But hlist has two struct,"struct hlist_head" and "struct hlist_node". So for hlist, when trying to point to previous element, the element can be either of type "hlist_head" or "hlist_node". We cannot use one common pointer type to point to both element types. (of course, we can use void* but it is not a good type of pointer and need type cast before actually using it) So the solution is to let the "prev" pointer point to a common struct type, which is "struct hlist_node *". This common type is shared by field "first" in hlist_head and also field "next" in hlist_node. Therefore "prev" pointer becomes "struct hlist_node **" that can point to both hlist_head.first and hlist_node.next.