小编典典

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

linux

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

prev)来完成?请帮我。


阅读 500

收藏
2020-06-07

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

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

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

2020-06-07