__list_add vs list_add in linux 链表

Question

我很难理解 __list_add 与 list_add 的工作原理？我确实在这里阅读了一些答案，但听不懂。我在附件中提出了我的问题...请看一下并给我一些建议好吗？

谢谢

Answer 1

将 __list_add 内联函数合并到 list_add 的主体中会产生以下等价物：

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

这将在 head 和 head->next 之间插入 new 条目。通常，head指向双向链表的控制节点，new是要添加到双向链表前面的条目。

原始状态：

[oldheadprev]   [head]                       [oldheadnext]
    next ------> next -------------------------> next
    prev <------ prev <------------------------- prev

                                  [new]
                                  next
                                  prev

head->next->prev = new;之后：

[oldheadprev]   [head]                       [oldheadnext]
    next ------> next -------------------------> next
    prev <------ prev                         ,- prev
                                             /
                                  [new]     /
                                  next     /
                                  prev <--'

new->next = head->next;之后：

[oldheadprev]   [head]                       [oldheadnext]
    next ------> next --------------------> ,--> next
    prev <------ prev                      /  ,- prev
                                          /  /
                                  [new]  /  /
                                  next -'  /
                                  prev <--'

new->prev = head;之后：

[oldheadprev]   [head]                       [oldheadnext]
    next ------> next --------------------> ,--> next
    prev <------ prev <-,                  /  ,- prev
                         \                /  /
                          \       [new]  /  /
                           \      next -'  /
                            `---- prev <--'

head->next = new;之后：

[oldheadprev]   [head]                       [oldheadnext]
    next ------> next ----,                 ,--> next
    prev <------ prev <-,  \               /  ,- prev
                         \  \             /  /
                          \  \    [new]  /  /
                           \  `-> next -'  /
                            `---- prev <--'

即使列表为空，代码也能正常工作。在空列表中，控制节点（head）的next和prev指针指向自身：head->next = head; head->prev = head;.

原空列表状态：

          [head]              [new]
     ,---> next -----,        next
     |  ,- prev <-,  |        prev
     |  `---------'  |
     `---------------'

head->next->prev = new;之后：

          [head]              [new]
     ,---> next -----,        next
     |  ,- prev      |        prev <-,
     |  `------------|---------------'
     `---------------'

new->next = head->next;之后：

          [head]              [new]
 ,-> ,---> next -----,        next -----,
 |   |  ,- prev      |        prev <-,  |
 |   |  `------------|---------------'  |
 |   `---------------'                  |
 `--------------------------------------'

new->prev = head;之后：

          [head]              [new]
 ,-> ,---> next -----,        next -----,
 |   |  ,- prev <----|------- prev <-,  |
 |   |  `------------|---------------'  |
 |   `---------------'                  |
 `--------------------------------------'

head->next = new;之后：

          [head]              [new]
 ,-------> next ------------> next -----,
 |      ,- prev <------------ prev <-,  |
 |      `----------------------------'  |
 |                                      |
 `--------------------------------------'

__list_add vs list_add in linux 链表

__list_add Vs list_add in linux linked list

pointers

linux-kernel

doubly-linked-list