正确加入两个双链表的方法

Question

在Linux内核源代码中,list_splice实现了__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;
}

是不是list已经指向链表的头部了？为什么我们需要list->next取而代之？

Answer 1

Linux内核中的双链表API实现为循环列表的抽象.在该简单方案中,HEAD节点不包含任何有效载荷(数据)并且明确地用于保持列表的起始点.由于这样的设计,a)检查列表是否为空是非常简单的,并且b)调试列表,因为未使用的节点已被分配给所谓的POISON - 仅特定于整个内核中的列表指针的幻数.

1)非初始化列表

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

2)空列表

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

3)列出一个元素

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

4)列表中的两个项目

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

在无锁算法中,只保证下一个指针是一致的.保证并非总是如此.在commit 41071d65e11b介绍它.