在linux内核中如何使用双指针哈希列表?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (66)

我想了解Linux Kernel实现链表和哈希表。我了解链接列表的实现。但是我对hlist(** pprev)中使用双指针的原因感到困惑。我知道hlist用于执行散列表,因为列表的头部只需要一个指针并且节省了空间。为什么不能使用单个指针来完成(就像链表一样* prev)?

提问于
用户回答回答于

原因:

 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 */

如果你有*PRV而不是**因为我们试图节省内存,所以我们不包括*PRV在头中,那么我们的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堆上。此外,在实现中还有额外的有条件检查,这进一步减缓了速度。

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

扫码关注云+社区

领取腾讯云代金券