在Linux内核中的哈希表实现使用双指针 [英] Use of double pointer in linux kernel Hash list implementation

问题描述

我想了解Linux内核实现链表和哈希表。要实施的链接是这里。我明白了链表实现。但我有点困惑，为什么在hlist（** P preV）正在使用的双指针。链接hlist是这里。据我所知，hlist在执行哈希表的使用，因为列表的头只需要一个指针，它节省了空间。为什么它不能使用单指针（只是* preV像链表）做些什么呢？请帮我。

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.

推荐答案

之所以可以在评论之一为：

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

如果你有* preV，而不是** P preV，因为我们正试图以节省内存，我们不包括在头部* preV，那么我们hlist实施样子这样的：

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

请注意， $ P $光伏指针不能指向头部，或流浆＆gt;首先（不像 ** p $ p $光伏）。这个复杂的hlist实施，你会看到当我们执行 hlist_add_before（）：

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

注意 $ P $光伏没有任何指向，在上述imeplementation hlist_add_head（）。所以，现在当你执行 hlist_add_before（）它看起来是这样的：

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

请注意，现在我们需要在头传递以及以 hlist_add_before（），这需要一个额外的推头堆栈上推指令。此外，还有在执行，这进一步减慢事物的额外条件检查。

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.

现在，尝试实现其他hlist操作，以 * $ P $光伏而不是 ** P $ P $光伏，你会发现你的实现将是比你在Linux内核中看到的要慢。

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.

这篇关于在Linux内核中的哈希表实现使用双指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！