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

Question

我试图了解链接列表和哈希表的Linux内核实现.这里是实现的链接.我理解链表实现.但我很困惑为什么在hlist(**pprev)中使用双指针.hlist的链接在这里.我知道hlist用于哈希表的实现,因为列表的头只需要一个指针,它节省了空间.为什么不能使用单个指针(只是*像链表一样)？请帮我.

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,在上面的imeplementation中没有任何指示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在堆栈中.此外,在实现中还有一个额外的条件检查,这进一步减慢了速度.

现在,尝试实现其他hlist操作,*prev而不是**pprev,你会发现你的实现将比你在linux内核中看到的要慢.