在Linux内核哈希列表实现中使用双指针

Question

我试图了解链表和哈希表的Linux内核实现。实现的链接在这里。我了解链表的实现。但是我对为什么在hlist（*
pprev）中使用双指针感到困惑。hlist的链接在这里。我知道hlist用于实现哈希表，因为列表的头仅需要一个指针，并且可以节省空间。为什么不能使用单个指针（就像链接列表一样

prev）来完成？请帮我。

Answer 1

原因可以在以下注释之一中找到：

 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而不是 pprev，并且由于我们试图节省内存，则我们不将 prev包含在头部，那么我们的hlist实现如下所示：

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

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

请注意，prev指针不能指向头部，或head->first（不同于**pprev）。正如我们在实现时所看到的那样，这会使hlist的实现复杂化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;
  }
}

请注意prev，在上述的实现中，没有什么可指的hlist_add_head()。因此，现在实现时，hlist_add_before()它看起来像这样：

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

注意，现在我们还需要传递head给hlist_add_before()，这需要额外的push指令来压head入堆栈。此外，在实现中还有一个额外的条件检查，这会进一步降低速度。

现在，尝试使用*prev而不是来实现其他hlist操作，**pprev您会发现您的实现将比linux内核中看到的要慢。