---
tags: Linux核心設計與實作
---
# lib/list_sort.c sort執行流程
起始狀態
且設A\<B\<C
```c
A = 0x555555566eb8;
B = 0x555555566f68;
c = 0x555555567018;
```
---
count = 0;
```
// queue的第一格節點
pending = NULL
list = 0x555555566eb8 // A
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] pending [label="pending"]
node [shape=box] list [label="list"];
list -> a;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:prev:c -> head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:next:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```
list->prev = pending // A->prev = NULL
pending = list // A
list = list->next // B
pending->next = NULL // A->next = NULL
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] pending [label="pending"];
node [shape=box] list [label="list"];
pending -> a;
list -> b;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:next:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
---
count = 1
```
tail = &pending; // pending point to A
// enter for loop
tail = &(*tail)->prev // tail point to pending->prev (0x555555566eb8)
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] pending [label="pending"];
node [shape=box] list [label="list"];
tail -> pending;
pending -> a;
list -> b;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:next:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```
list->prev = pending // B->prev = A (nothing change)
pending = list // pending = B
list = list->next // list = C
pending->next = NULL // B->next = NULL
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] pending [label="pending"];
node [shape=box] list [label="list"];
tail -> pending;
pending -> b;
list -> c;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
---
count = 2
```
// ready for merge
a = *tail // B
b = a->prev // A
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] pending [label="pending"];
node [shape=box] list [label="list"];
node [shape=box] newA [label="a"]
node [shape=box] newB [label="b"]
tail -> pending;
pending -> b;
list -> c;
newA -> b;
newB -> a;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
merging
```
head = NULL
tail = &head
*tail = a; // head = A
tail = &a->next // tail = NULL (go to next term)
a = a->next // a = NULL (go to next term)
*tail = b // A->next = B
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] headPtr [label="head"];
node [shape=box] tail [label="tail"];
node [shape=box] newA [label="a"]
node [shape=box] newB [label="b"]
newB -> b;
headPtr -> a;
tail -> b;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
after merge
```
// 被合併的list會由head到tail接好
// 尚未被合併的list會由tail利用prev一路往前接
// 此處應該是在處理順序調換後和原本list相接的部分
a->prev = b->prev // nothing change
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] pending [label="pending"];
node [shape=box] list [label="list"];
node [shape=box] newA [label="a"]
node [shape=box] newB [label="b"]
tail -> pending;
pending -> a;
list -> c;
newA -> a;
newB -> a;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```
list->prev = pending // C->prev = A
pending = list // pending = C
list = list->next // list = NULL (到底了)
pending->next = NULL
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] pending [label="pending"];
node [shape=box] list [label="list"];
tail -> pending;
pending -> c;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```
list = pending // list = C
pending = pending->prev // pending = A (要併進去的list頭)
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] pending [label="pending"];
node [shape=box] list [label="list"];
list -> c;
tail -> pending;
pending -> a;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
prepare for merge remain nodes
```
// 盡可能地往前合併
next = pending->prev // next = NULL (沒東西能再併了)
// 跳出for loop
```
merge final
```
// 將所有剩餘節點合併並串起來
tail = head
count = 0
// 第一次迴圈
// cmp(a,b) < 0
// 重建double linked結構
tail->next = a
a->prev = tail
tail = a
// a轉到下一項
a = a->next
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] newA [label="a"]
node [shape=box] newB [label="b"]
tail -> a;
newA -> b;
newB -> c;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:prev:c -> head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```
// 第二次迴圈
// cmp(a,b) < 0
// 重建double linked結構
tail->next = a // tail->next = B (A->next = B)
a->prev = tail // B->prev = A
tail = a // tail = B
// a轉到下一項
a = a->next // a = NULL
跳出迴圈
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] newA [label="a"]
node [shape=box] newB [label="b"]
tail -> b;
newB -> c;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:prev:c -> head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```
// 合併剩下還沒被併進去的節點
tail->next = b // B->next = C (直接把剩下還沒合併的接起來)
// enter while loop
// 重建 double linked 結構
b->prev = tail // C->prev = B
tail = b // tail = C
b = b->next; // b = NULL (後面沒東西併了)
跳出迴圈
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] newA [label="a"]
node [shape=box] newB [label="b"]
tail -> c;
newB -> c;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:prev:c -> head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:next:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```
// 完成tail和head的link
tail->next = head // C->next = head
head->prev = tail // head->prev = C
```
```graphviz
digraph foo {
rankdir=LR;
node [shape=record]
head [label="{<prev> | head | <next> }"];
a [label="<value> A | {<prev> | <next>}"];
b [label="<value> B | {<prev> | <next>}"];
c [label="<value> C | {<prev> | <next>}"];
node [shape=box] tail
node [shape=box] newA [label="a"]
node [shape=box] newB [label="b"]
tail -> c;
newB -> c;
head:next:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head:prev:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:next:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
a:prev:c -> head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:prev:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:next:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:prev:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:next:c -> head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
Sign in with Wallet
Connect another wallet