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

我想了解Linux Kernel实现链表和哈希表。 这里是一个实现的链接。 我了解链表的实现。 但我有点困惑,为什么在hlist(** pprev)中使用双指针。 hlist的链接在这里 。 我知道hlist是用于实现散列表,因为列表的头部只需要一个指针,节省了空间。 为什么不能用单指针来完成(就像链表一样)? 请帮帮我。

原因可以在其中一个评论中找到:

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,或者head->first (不像**pprev )。 这会使hlist实现复杂化,正如您在实现hlist_add_before()时所看到的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推入堆栈。 另外,还有一个额外的条件检查在实施,这进一步减慢了事情。

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