linux 内核链表的 list_add 函数如何工作？

Question

我一直在努力弄清楚 __list_add 函数在链表的 linux 内核实现中是如何工作的。

宏和数据结构如下：

#define LIST_HEAD_INIT(name) { &(name), &(name) } /* Assign the next and prev pointers to itself */

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

struct list_head {
    struct list_head *next, *prev;
};

struct mystruct {
    int data ;
    struct list_head mylist;
};

这是我感到困惑的功能。

static inline void list_add(struct list_head *new, struct list_head *head) { 
    __list_add(new, head, head->next); 
}

static inline void __list_add(struct list_head *new, 
                  struct list_head *prev, 
                  struct list_head *next) { 
    next->prev = new; 
    new->next = next; 
    new->prev = prev; 
    prev->next = new; 
}

这是我正在尝试的代码运行。

int main(void) {
    LIST_HEAD(mylinkedlist);
    struct mystruct first = {
                 .data = 10,
                 .mylist = LIST_HEAD_INIT(first.mylist)
    };
    list_add(&first.mylist,  &mylinkedlist);
    return 0;
}

所以基本上，我只是想向这个链表添加一个元素。我感到困惑的部分是它如何通过 list_add 函数中的 __list_add 传递参数。我理解前两个参数，new 和 head。但是，为什么 head->next 作为第三个参数传递？在第一个语句 next->prev = new; 中的 __list_add 函数中对我来说没有意义。这不是说它在技术上是在做(head->next)->prev = new吗？为什么你会得到 next 的 prev 并将其分配给 new？我试着把它画出来，但它并没有加起来。你不想做 head->prev = new 吗？谢谢。

Answer 1

假设您有一个包含很多成员的列表，每个成员都有一个对应于他们想要的位置的编号。

假设您的列表中已有成员 _3 和 _5（由于尚未添加 _4，该成员现在位于位置 4，紧挨着 _3），但您仍未添加会员_4.

现在您想在成员 _3 之后和成员 _5 之前插入 _4。

list_add(_4, _3); 会将节点添加到正确的位置。

它实际上会执行 __list_add(_4, _3, _3->next); 计算结果为 __list_add(_4, _3, _5);，然后执行以下操作：

_5->prev = _4;
_4->next = _5;
_4->prev = _3;
_3->next = _4;

我希望这已经够清楚了:)

linux 内核链表的 list_add 函数如何工作？

How does the list_add function for linux kernel linked lists work?

c

linked-list

linux-kernel