双指针在linux内核Hash列表实现中的使用

问题描述

我正在尝试了解链表和哈希表的 Linux 内核实现.实现的链接是这里.我理解链表实现.但是我对为什么在 hlist (**pprev) 中使用双指针有点困惑.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 而不是 **pprev，并且因为我们试图节省内存，我们不会在头部包含 *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;
};

注意prev 指针不能指向头部，或者head->first(不像**pprev).这使 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;
  }
}

注意 prev 在上面的 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;
  }
}

注意，现在我们还需要传入head以及hlist_add_before()，这需要额外的push指令来推送head 在堆栈上.此外，在实现中还有一个额外的条件检查，这进一步减慢了速度.

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 操作，使用 *prev 而不是 **pprev，你会发现你的实现会比什么慢你在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内核Hash列表实现中的使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！