blocks|key|1220519|text|原因可以在其中一条评论中找到：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1220520|+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+*/|code-block|syntax|javascript|1220521|如果您使用*prev而不是**pprev，并且因为我们试图节省内存，所以我们不在头部包含*prev，那么我们的hlist实现如下所示：|1220522|struct+hlist_head+{
++struct+hlist_node+*first+=+null;
};

struct+hlist_node+{
++struct+hlist_node+*next;
++struct+hlist_node+*prev;
};|1220523|请注意，与**pprev不同，prev指针不能指向head或head->first。这会使hlist实现变得复杂，正如您将在实现hlist_add_before()时看到的那样|offset|length|style|CODE|1220524|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;
++}
}|1220525|请注意，在上面的hlist_add_head()实现中，prev没有什么可指向的。所以，现在当你实现hlist_add_before()时，它看起来是这样的：|1220526|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;
++}
}|1220527|请注意，现在我们还需要将head传递给hlist_add_before()，这需要额外的push指令来将head推送到堆栈上。此外，在实现中有一个额外的条件检查，这进一步减慢了速度。|1220528|现在，尝试实现其他hlist操作，使用*prev而不是**pprev，您会发现您的实现将比您在linux内核中看到的要慢。|1220529|entityMap^0|0|0|0|0|5|7|F|4|U|B|1S|I|0|0|8|G|S|4|1E|I|0|0|C|4|J|I|18|4|1G|4|0|J|5|R|7|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|13|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|14|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|15|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|16|8|@$M|17|N|18|O|P]|$M|19|N|1A|O|P]|$M|1B|N|1C|O|P]|$M|1D|N|1E|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|D|7|1F|8|@]|9|@]|A|$E|F]]|$1|S|3|T|5|6|7|1G|8|@$M|1H|N|1I|O|P]|$M|1J|N|1K|O|P]|$M|1L|N|1M|O|P]]|9|@]|A|$]]|$1|U|3|V|5|D|7|1N|8|@]|9|@]|A|$E|F]]|$1|W|3|X|5|6|7|1O|8|@$M|1P|N|1Q|O|P]|$M|1R|N|1S|O|P]|$M|1T|N|1U|O|P]|$M|1V|N|1W|O|P]]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1X|8|@$M|1Y|N|1Z|O|P]|$M|20|N|21|O|P]]|9|@]|A|$]]|$1|10|3|-4|5|6|7|22|8|@]|9|@]|A|$]]]|11|$]]

The reason can be found in one of the comments:

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

If you had *prev instead of **pprev, and because we are trying to save memory, we don't include *prev in the head, then our hlist implementation looks like this:

<pre><code>struct hlist_head {
 struct hlist_node *first = null;
};

struct hlist_node {
 struct hlist_node *next;
 struct hlist_node *prev;
};
</code></pre>

Notice that the <code>prev</code> pointer cannot point to the head, or <code>head-&gt;first</code> (unlike <code>**pprev</code>). This complicates the hlist implementation, as you'll see when we implement <code>hlist_add_before()</code>:

<pre><code>void
hlist_init(struct hlist_head *head) {
 head-&gt;first = null; 
}

void
hlist_add_head(struct hlist_head *head, struct hlist_node *node) {
 struct hlist_node *next = head-&gt;first;

 head-&gt;first = node;
 node-&gt;next = next;
 node-&gt;prev = NULL;
 if (next) {
 next-&gt;prev = node;
 }
}
</code></pre>

Notice that <code>prev</code> has nothing to point to, in the above imeplementation of <code>hlist_add_head()</code>. So, now when you implement <code>hlist_add_before()</code> it looks like this:

<pre><code>void
hlist_add_before(struct hlist_head *head,
 struct hlist_node *node,
 struct hlist_next *next) {
 hlist_node *prev = next-&gt;prev;

 node-&gt;next = next;
 node-&gt;prev = prev;
 next-&gt;prev = node;

 if (prev) {
 prev-&gt;next = node;
 } else {
 head-&gt;first = node;
 }
}
</code></pre>

Notice that now we need to pass in <code>head</code> as well to <code>hlist_add_before()</code>, which requires an extra <code>push</code> instruction for pushing <code>head</code> on the stack. Besides, there's an extra conditional check in the implementation, which further slows down things.

Now, try implementing other hlist operations, with <code>*prev</code> instead of <code>**pprev</code>, and you'll find out that your implementation is going to be slower than what you saw in the linux kernel.

blocks|key|1006397|text|有两种类型的列表:常规列表类型和散列列表(+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+**“。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1006398|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

There are two type of lists: regular list_head type, and hash list(hlist). &quot;list_head&quot; type has only one struct, i.e. &quot;struct list_head&quot;. But hlist has two struct,&quot;struct hlist_head&quot; and &quot;struct hlist_node&quot;. So for hlist, when trying to point to previous element, the element can be either of type &quot;hlist_head&quot; or &quot;hlist_node&quot;. We cannot use one common pointer type to point to both element types. (of course, we can use void* but it is not a good type of pointer and need type cast before actually using it) So the solution is to let the &quot;prev&quot; pointer point to a common struct type, which is &quot;struct hlist_node *&quot;. This common type is shared by field &quot;first&quot; in hlist_head and also field &quot;next&quot; in hlist_node. Therefore &quot;prev&quot; pointer becomes &quot;struct hlist_node **&quot; that can point to both hlist_head.first and hlist_node.next.

I am trying to understand Linux Kernel implementation of linked list and hash table. A link to the implementation is <a href="http://lxr.linux.no/linux+v2.6.34/include/linux/list.h" rel="noreferrer">here</a>. I understood the linked list implementation. But i am little confused of why double pointers is being used in hlist (**pprev). Link for hlist is <a href="http://lxr.linux.no/linux+v2.6.34/include/linux/list.h#L554" rel="noreferrer">here</a>. I understand that hlist is used in implementation of hash table since head of the list requires only one pointer and it saves space. Why cant it be done using single pointer (just *prev like the linked list)? Please help me.

Use of double pointer in linux kernel Hash list implementation

Linux

我正在尝试理解Linux内核中链表和哈希表的实现。指向该实现的链接是。我理解链表的实现。但是我有点搞不懂为什么hlist (**pprev)中使用了双指针。hlist的链接是。我知道hlist用于实现哈希表，因为列表的头部只需要一个指针，而且它节省了空间。为什么不能使用单指针(就像链表一样的*prev )？请帮帮我。

问双指针在linux内核哈希表实现中的应用
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问双指针在linux内核哈希表实现中的应用EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问双指针在linux内核哈希表实现中的应用
EN