正确的方式加入两个双链表 [英] Correct way to join two double linked list

问题描述

在Linux内核源代码，在 list_splice 与 __ list_splice 实施

In the Linux kernel source, the list_splice is implemented with __list_splice:

static inline void __list_splice(const struct list_head *list,
                                 struct list_head *prev,
                                 struct list_head *next)
{
        struct list_head *first = list->next; // Why?
        struct list_head *last = list->prev;

        first->prev = prev;
        prev->next = first;

        last->next = next;
        next->prev = last;
}

不是列表已经指向链表的头？
为什么我们需要获取列表 - ＆GT;接下来而不是

Isn't the list already pointing to the head of a linked list? Why do we need to fetch list->next instead?

推荐答案

在Linux内核的双链表API实现为循环链表的抽象。在这个简单的方案头节点的不的包含任何有效载荷（数据），并明确用于保持首发名单点。由于这样的设计是非常简单的一）检查，如果该列表是空的，和b）调试列表中，因为未使用的节点被分配到所谓的解毒的 - 神奇的数字仅针对在列表指针整个内核。

The double linked list API in the Linux kernel is implemented as an abstraction of circular list. In that simple scheme the HEAD node does not contain any payload (data) and used explicitly to keep starting point of the list. Due to such design it's really simple to a) check if the list is empty, and b) debug list because unused nodes have been assigned to the so called POISON — magic number specific only to the list pointers in the entire kernel.

1）的非初始化的列表

1) non-initialized list

+-------------+
|    HEAD     |
| prev | next |
|POISON POISON|
+-------------+

2）空列表

+----------+-----------+
|          |           |
|          |           |
|   +------v------+    |
|   |    HEAD     |    |
+---+ prev | next +----+
    | HEAD   HEAD |
    +-------------+

3）名单与一个元素

3) list with one element

+--------------+--------------+
|              |              |
|              |              |
|       +------v------+       |
|       |    HEAD     |       |
|   +---+ prev | next +--+    |
|   |   |ITEM1   ITEM1|  |    |
|   |   +-------------+  |    |
|   +--------------------+    |
|              |              |
|       +------v------+       |
|       |    ITEM1    |       |
+-------+ prev | next +-------+
        |    DATA1    |
        +-------------+

4）在列表中两项

4) two items in the list

      +----------+
      |          |
      |          |
      |   +------v------+
      |   |    HEAD     |
   +------+ prev | next +----+
   |  |   |ITEM2   ITEM1|    |
   |  |   +-------------+    |
+----------------------------+
|  |  |          |
|  |  |   +------v------+
|  |  |   |    ITEM1    |
|  |  +---+ prev | next +----+
|  |  |   |    DATA1    |    |
|  |  |   +-------------+    |
|  +-------------------------+
|     |          |
|     |   +------v------+
|     |   |    ITEM2    |
+---------+ prev | next +----+
      |   |    DATA2    |    |
      |   +-------------+    |
      |                      |
      +----------------------+

在锁算法少，只有对的下次的指向是一致的保证。担保并非总是如此。在提交41071d65e11b 介绍吧。

In the lock less algorithm there is a guarantee only for next pointer to be consistent. The guarantee wasn't always the case. The commit 41071d65e11b introduces it.

这篇关于正确的方式加入两个双链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！