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

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    |    |
      |   +-------------+    |
      |                      |
      +----------------------+

在无锁算法中，只有 next 指针是一致的。保证并非总是如此。提交 2f073848c3cc 介绍了它。

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

Correct way to join two double linked list

c

linked-list

linux-kernel