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

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

原因可以在以下注释之一中找到：

 547

如果您使用的是 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()

：

voidhlist_init(struct hlist_head *head) {  head->first = null;  }voidhlist_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()

它看起来像这样：

voidhlist_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

而不是来实现其他hlist *** 作，

**pprev

您会发现您的实现将比linux内核中看到的要慢。