双指针在linux内核哈希表实现中的应用
回答 2
Stack Overflow用户
发布于 2010-06-17 11:06:52
原因可以在其中一条评论中找到：
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;
};请注意，与**pprev不同，prev指针不能指向head或head->first。这会使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;
}
}请注意，在上面的hlist_add_head()实现中，prev没有什么可指向的。所以，现在当你实现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内核中看到的要慢。
Stack Overflow用户
发布于 2021-05-23 01:55:00
有两种类型的列表:常规列表类型和散列列表( list_head )。“结构”类型只有一个结构，即“list_head list_head”。但是hlist有两个结构，“struct hlist_head”和"struct hlist_node“。因此，对于hlist，当尝试指向前一个元素时，元素可以是"hlist_head“或"hlist_node”类型。我们不能使用一个共同的指针类型同时指向两个元素类型。(当然，我们可以使用空*，但它不是一个好的指针类型，需要在实际使用它之前进行类型转换)，所以解决方案是让"prev“指针指向一个通用的结构类型，即"struct hlist_node *”。此公共类型由hlist_head中的字段"first“和hlist_node中的字段"next”共享。因此，"prev“指针变成了可以同时指向hlist_head.first和hlist_node.next的”结构hlist_node **“。
https://stackoverflow.com/questions/3058592
复制相似问题