加入两个双链表的正确方法 [英] 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;
}

list 不是已经指向链表的头部了吗?为什么我们需要取list->next来代替?

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

推荐答案

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

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) 未初始化列表

+-------------+
|    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) 列表中的两个项目

4) two items in the list

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

在无锁算法中，只保证next 指针是一致的.保证并非总是如此.提交 2f07384a> 介绍一下.

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 2f073848c3cc introduces it.

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