c - linux内核哈希表实现中双指针的使用

Question

我正在尝试了解链表和哈希表的 Linux 内核实现。实现的链接是 here .我了解链表实现。但我对为什么在 hlist (**pprev) 中使用双指针感到困惑。 hlist 的链接是 here .我知道 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;
  }
}

请注意，在上述hlist_add_head() 的实现中，prev 没有任何指向。所以，现在当您实现 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 而不是 **pprev 实现其他 hlist 操作，你会发现你的实现会比原来的要慢你在 linux 内核中看到了。