我试图了解链表和哈希表的Linux内核实现。实现的链接在这里。我了解链表的实现。但是我对为什么在hlist(* pprev)中使用双指针感到困惑。hlist的链接在这里。我知道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 */
如果您使用的是 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():
prev
head->first
**pprev
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()它看起来像这样:
hlist_add_head()
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入堆栈。此外,在实现中还有一个额外的条件检查,这会进一步降低速度。
head
push
现在,尝试使用*prev而不是来实现其他hlist操作,**pprev您会发现您的实现将比linux内核中看到的要慢。
*prev