or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
你所不知道的 C 語言: linked list 和非連續記憶體
Copyright (慣C) 2018, 2022 宅色夫
直播錄影
前言
「你所不知道的 C 語言」講座致力於引導學員思索專業的程式開發議題,「linked list 和非連續記憶體操作」探討以下:
無論是作業系統核心、C 語言函式庫內部、程式開發框架,到應用程式,都不難見到 linked list 的身影,包含多種針對效能和安全議題所做的 linked list 變形,又還要考慮到應用程式的泛用性 (generic programming),是很好的進階題材。
從 Linux 核心的藝術談起
Linus Torvalds 在 TED 2016 的訪談

Linus Torvalds 在 TED 訪談中提及自己的思維模式、性格與 Linux 和 Git 背後的心路歷程。
於 14:10 時,他提到程式設計的 "good taste" 為何。
對照 CMU 教材 Linked Lists

以下的討論不涵蓋 list is empty 和 node is not in the list 的狀況
原本的程式碼 (10 行)
直觀的寫法會有特例,也就是第一筆資料與中間的資料的移去操作不同。
若要移去的是第一筆資料,那就需要把指標指向第一個節點;而若是要移除中間的資料,則須要把指標指向目標的前一個節點。
Linus Torvalds 換個角度來思考,藉由指標的指標 (或稱「間接指標」,即 indirect pointer) 來操作,如此一來,上面的特例就不存在。
依據中華民國教育部《重編國語辭典修訂本》,「雙」作為量詞時,指計算成對物品的單位,因此間接指標不該被稱為「雙」指標:一個指標指向到另一個指標,在記憶體存取的角度來看,實屬階層 (hierarchy) 關係,而非「成對」或「對等」的存在
Linus Torvalds 的解說:
在 15:25 時,他說:
重點是有時候我們可以從不同的角度來詮釋問題,然後重寫,那麼例外就會消失,這樣就是好的程式。
原本的方式是,有個指向前一元素的指標、另一個目前位置的指標,再利用

while
敘述逐一走訪鏈結串列,找到target
時停下來。這會有個分支判斷prev
是否為NULL
,若為NULL
就代表 target 是鏈結串列的 head,因此需要把鏈結串列的 head 指向下個元節點;若非NULL
就把前個節點的next
設為目前的下一個節點。而 Linus Torvalds 的想法則是拿一個指標指向「節點裡頭指向下個節點 的指標」,以「要更新的位址」為思考點來操作。
有個指標的指標

indirect
,一開始指向 head,之後一樣走訪 list,解指標看是不是我們要的 target,如果*indirect
就是我們要移去的元素,代表indirect
現在指向前一個節點裡面的next
指標,因此把*indirect
設為 target 的下個節點,即可完成整個操作:解說: Linked lists, pointer tricks and good taste
以下是拆解:我們先做一個指向 head 的指標:
Node **indirect = &list->head;
在走訪 list 時,先進行
*indirect
(dereferenceindirect
找出其指向的 node,此刻為 head), 接著(*indirect)->next
(找出它的->next
,這邊為 head 的 next,即node1
),然後indirect = &((*indirect)->next)
(將其 reference 存回indirect
,此刻indirect
就變更為指向node1
的指標):如此一來 head 從頭到尾都沒有動,直接回傳 head 就好。
從「要更新什麼位置的資料」思考,無論是 head 或者非 head,更新的是同一類型的資料,不用特別操作,自然省下額外的處理
延續上述討論,我們嘗試撰寫完整的 C 程式,過程中思考「如何撰寫更優雅的程式碼」。首先是結構定義:
要從給定的鏈結串列中,移走 (remove) 符合特定數值的節點時,可撰寫以下程式碼:
這段程式碼考慮到開頭的節點是否被移走,於是要有對應的程式碼來處理特例,最終回傳新的開頭節點。改進方式為,引入一個暫時節點,使其在給定的開頭節點之前,這樣就不用特別撰寫程式碼來處理特例:
不過這段程式碼依舊可改進,因為我們根本不用回傳新的開頭節點,相反的,可將函式原型改為
void remove(list_entry_t **head, int value)
,藉由間接指標來更動傳入的鏈結串列開頭節點。針對鏈結串列的新增節點的操作,考慮以下程式碼:
函式的參數列表中,之所以用
list_entry_t **head
,而非list_entry_t *head
,是因為原本傳入的head
可能會被變更,但 C 語言在參數傳遞時永遠都是傳遞數值 (副本),於是若接受list_entry_t *head
做為參數,那就要提供append
函式的傳回值,也就是說,該函式原型宣告變為:如此就不優雅且顯得累贅。運用上述 indirect pointer 的技巧,我們可重寫
append
函式如下:延伸閱讀:
案例探討: LeetCode 21. Merge Two Sorted Lists
LeetCode 21. Merge Two Sorted Lists 簡述:
直觀的做法是,提供一個暫時節點,依序將內含值較小的節點串上,最後回傳暫時節點指向的次個節點:
倘若我們想避免配置暫時節點的空間 (即上方程式碼中的
malloc
),該怎麼做?運用上述 indirect pointer 的技巧:觀察使用 indirect pointer 版本的程式碼,其中
if-else
的程式碼都是將 ptr 指向下一個要接上的節點,之後將節點更新到下一個,不過要為 L1 跟 L2 分開寫同樣的程式碼,該如何簡化?可以再使用一個指標的指標來指向 L1 或 L2。注意
node = L1->val < L2->val? &L1: &L2
不能寫成node = &(L1->val < L2->val? L1: L2)
,依據 C99 規格書6.5.15
的註腳:因此無法使用
&
(address of) 去取得L1->val < L2->val? L1: L2
的地址,只能分開取得 L1 和 L2 的地址。ptr = &head;
head
ptr
指向 headnode = &L1;
L1
L1
跟L2
後,node
指向L1
*ptr = *node;
head = L1;
head
*node = (*node)->next;
L1 = L1->next;
將節點更新到
next
ptr = &(*ptr)->next;
ptr = &(head)->next;
ptr
指向head->next
讓下一輪迴圈更新
head->next
LeetCode 23. Merge k Sorted Lists 則將 LeetCode 21. Merge Two Sorted Lists 指定的 2 個 linked list 擴充為 k 個的合併,其本質就是將分割好的 sorted lists 合併成一條,示意如下:
顯然在
merge
階段可延用上述mergeTwoLists
函式,至於 list 合併的方向就是演算法勝出的關鍵,可能的思路如下:直觀地用第一條串列接上剩下的串列,這樣會導致
lists[0]
愈來愈長,立即會遇到的問題是:多數的情況下合併速度會愈來愈慢。從固定第一條串列改成頭跟尾兩兩合併,直到剩一條為止,比起前一方法的每次都用愈來愈長的串列跟另一條串列合併,頭尾合併在多數的情況下兩條串列的長度比較平均,合併會比較快。
當合併完頭尾後,偶數長度會少一半,奇數長度則為
(listsSize + 1) / 2
,奇數更新的方式也可以用在偶數長度上。除了頭尾合併,還可以分段存取下個要合併的串列,分別合併
lists[i]
跟lists[i + interval]
,為確保內層迴圈不會重複存取,索引值i
會更新為i + interval * 2
,當內層迴圈合併完之後會把結果分別存到lists[interval*0]
,lists[interval*2]
,lists[interval*4]
,lists[interval*6]
, 等等,示意如下:因此,外層迴圈在更新 interval 時,也要變成 2 倍,以確保進入內層迴圈存取 lists 的正確位置。
由於 lists 中的串列已排序,可視為 sorted element,直接進行 merge sort:
案例探討: Leetcode 2095. Delete the Middle Node of a Linked List
Leetcode 2095. Delete the Middle Node of a Linked List 簡述:
若不考慮釋放掉中間的節點,可用指標的指標,搭配快慢指標的技巧來實作:
倘若要釋放中間的節點,可以再用一個指標

prev
跟隨於indir
之後,當迴圈走訪完,indir
會指向鏈結串列中間的節點,之後prev
再指向indir
的下個節點,整個執行流程如下:對應的程式碼:
上述的程式碼看似正確,一旦提交後則會被 Leetcode 內建的 Address Sanitizer 偵測到 heap-use-after-free。
考慮給定的鏈結串列為
[1, 3, 4, 7, 1, 2, 6]
,上述的程式碼在迴圈結束後,*indir
會指向內容為7
的節點 (以下記做 node7),prev
緊隨其後指向內容為4
的節點 (以下記做 node4),換言之,prev->next
就是*indir
。找出
indir
跟prev
所指向的節點與關係後,可知prev->next = (*indir)->next;
相當於(*indir) = (*indir)->next;
,即*indir
從 node4 指向 node1。查閱 C99 規格書 6.2.4.2
因此
free(*indir)
會釋放 node1 對應的記憶體,因此在驗證階段時,會被偵測到 heap-use-after-free。若要修正這個問題,可藉由新的指標
next
來保存(*indir)->next
,方可在indir
釋放掉後再以next
更新。倘若要釋放中間的節點,需額外用一個指標記錄欲釋放的物件。執行完 for 迴圈後,鏈結串列和
indir
如下圖。其中indir
指向的是指向 node7 的指標 (即 node4 的next
指標):當我們要從鏈結串列中移去並釋放 node7,只要用一個指標
del
指向 node7 (即del = *indir
),並將 node4 的next
指標更改為指向 node1 (即*indir = (*indir)->next
),示意圖如下:最後再釋放 node7 所在的空間,對應的程式碼如下:
案例探討: LeetCode 86. Partition List
例如輸入為
[1, 4, 3, 2, 5, 2]
, x = 3輸出
[1, 2, 2, 4, 3, 5]
直觀的做法是配置兩個暫時節點分別保存「節點的數值小於
x
」和「節點的數值大於等於x
」的鏈結串列,分割後再以前者 (即節點數值均「小於x
」的鏈結串列) 合併另一者。注意,「大於等於
x
」的鏈結串列要將最後一個節點的next
指向NULL
,例如範例的 node5 的下個節點指向 node2,如果沒有將 node5 的下一個指向NULL
,會在執行時期陷入無窮迴圈,從而被 LeetCode 驗證系統判定為超時。我們可運用上述間接指標的技巧,分別指向兩條要合併的串列,從而避免動態記憶體配置:
不難發現,在
if-else
中的 p1 跟 p2 是一樣的操作,且 p1 跟 p2 都是指標的指標,可否進一步精簡程式碼?這時又可利用「指標的指標的指標」來簡化程式碼,但要注意 dereference 的型態是「指標」,抑或是「指標的指標」。宣告「指標的指標的指標」
indir
指向要被更新節點,如p1
,再 dereference 兩次 (**indir
) 就會得到指標型態的p1
所指向的節點並將node
指派到p1
。更新 p1 到下個節點前,應進行 dereference (
*indir
) 以取得指標的指標 p1,再透過 dereference indir 兩次並取得 next 後用 address-of 運算子得到指標的指標,再指派回 p1 即可完成更新。***indir = &p1;
p1
node->val
跟x
,indir
指向p1
**indir = node;
(*p1) = node;
p1
*indir = &(**indir)->next;
p1 = &(*p1)->next;
p1
指向p1->next
讓下輪迴圈更新p1
circular linked list
環狀鏈結串列 (circular linked list) 是鏈結串列的最後一個節點所指向的下一個節點,會是第一個節點,而不是指向

NULL
:其優點為:
NULL
這樣特別的記憶體地址 (在沒有 MMU 的 bare metal 環境中,(void *) 0
地址空間存取時,沒有特別的限制)用「龜兔賽跑」(Floyd's Cycle detection) 來偵測是否有 cycle 產生。
有 3 種狀態需要做討論
我們需要求得 a, b, c 三點位置,才能進行處理。
假設 \(\overline{ac}\) 距離為 \(X\) ,這代表 tortoise 行經 \(X\) 步,那麼 hare 走了 \(2X\) 步,\(X\) 數值為多少並不重要,只代表要花多少時間兩點才會相遇,不影響求出 \(\mu\) 和 \(\lambda\)。
接下來要分成三個步驟來處理
如果只需要判斷是否為 circular linked list,那麼只要執行上述的第 1 部分。
除了計算 \(\mu\) 和 \(\lambda\),還需要記錄整個串列的長度,若不記錄,會影響到後續進行 sorting 一類的操作。
LeetCode 相關題目:
Merge Sort 的實作
Merge sort 是經典排序演算法,以串列為例,將串列分割成排序好的子串列,再將所有排序好的子串列合併在一起。
採用遞迴呼叫,搭配前述 slow-fast 指標將串列左右對半切分,直到分割成單一節點再合併成排序好的串列,對應實作如下:
非遞迴的實作
如何將上述 merge sort 從遞迴轉成迭代?可善用之前探討過的 merge K Lists 程式碼。
naive 是將單一節點逐個合併,速度非常慢,所以改成將分割好的節點存進指標陣列 lists 改成頭尾合併來改善效能。
觀察初步改進後的實作,可將迭代版 merge sort 拆成分割階段與合併階段來實作並持續改進,進而延伸出各種組合,接下來分別探討兩種階段的實作。
回顧 merge sort 的概念,將串列分割成排序好的子串列,再將所有排序好的子串列合併在一起。
Linked list 在 Linux 核心原始程式碼
linux/list.h 是 Linux 核心中相當實用的 circular doubly-linked list (雙向環狀鏈結串列,以下簡稱
list
) 封裝,只要在自定義的結構中加入struct list_head
,就可以搭配 Linux 中一系列的 linked list 操作 (詳見 The Linux Kernel API - List Management Functions) 來建立自定義結構的 linked list。在 Linux 行程 (process) 管理的相關實作中可見到應用,例如 sched.h 中約出現 20 處,程式碼部分摘錄如下:list 的關鍵概念是,將結構體

list_head
嵌入到所需的結構體中,再藉由稍後會提及的container_of
巨集得知 list 個別節點的地址。示意如下圖:自
Head
開始,鏈結 list 各節點,個別節點皆嵌入list_head
結構體,不過Head
是個特例,無法藉由container_of
巨集來找到對應的節點,因為後者並未嵌入到任何結構體之中,其存在是為了找到 list 整體。好處在於,只要

list_head
納入新的結構體的一個成員,即可操作,且不用自行維護一套 doubly-linked list。圖解如下:
list_head
結構體list_head
物件簡化為下圖:
LIST_HEAD - Declare list head and initialize it
list_entry() - Calculate address of entry that contains list node
list_for_each - iterate over list nodes
Linux 核心的
list
也在 hash table 的實作中出現,詳見 List, HList, and Hash Table。簡化的實作
Linux 核心原始程式碼變動快,為了後續探討方便,我們自 Linux 核心抽離出關鍵程式碼,建立 sysprog21/linux-list 專案,讓學員得以理解箇中奧秘並進行相關實驗。
container_of()
為了提升程式碼的可攜性 (portability),C89/C99 提供 offsetof 巨集,可接受給定成員的型態及成員的名稱,傳回「成員的位址減去 struct 的起始位址」。示意如下:

offsetof 定義於
<stddef.h>
。巨集

container_of
則在 offsetof 的基礎上,擴充為「給定成員的位址、struct 的型態,及成員的名稱,傳回此 struct 的位址」,示意如下圖:在
container_of
巨集出現前,程式設計的思維往往是:container_of
巨集則逆轉上述流程,例如list_entry
巨集利用container_of
巨集,從struct list_head
這個公開介面,「反向」去存取到自行定義的結構體開頭地址。LIST_HEAD()
/INIT_LIST_HEAD()
初始化
struct list_head
,先將next
和prev
都指向自身。head
指向的結構體之中的next
成員表示 linked list 結構的開頭,而prev
則指向結構體的結尾。list_add
/list_add_tail
將指定的
node
插入 linked listhead
的開頭或者結尾。list_del
本函式將
node
從其所屬的 linked list 結構中移走。注意node
本體甚至是包含node
的結構所分配的記憶體,在此皆未被釋放,僅僅是將node
從其原本的 linked list 連接移除。亦即,使用者需自行管理記憶體。LIST_POISONING
巨集一旦定義,將讓已被移走的node
節點再存取時,觸發作業系統的例外狀況:對於next
或者prev
的存取,會觸發執行時期的 invalid memory access (若系統禁止 predefined memory access)。list_del_init
以
list_del
為基礎,但移除的node
會額外呼叫INIT_LIST_HEAD
把prev
和next
指向自身。list_empty
檢查
head
的next
是否指向自身,確認 list 是否為 empty 狀態。list_is_singular
若
head
非 empty 狀態且prev
和next
是同一個節點,表示 linked list 只有一個節點。list_splice
/list_splice_tail
將
list
的所有 node 都插入到head
的開始 / 結束位置中。注意list
本身仍維持原貌。list_splice_init
/list_splice_tail_init
這二個函式類似
list_splice
及list_splice_tail
,但移除的list
會額外呼叫INIT_LIST_HEAD
把prev
和next
指向自身。list_cut_position
將從
head_from
的第一個節點到node
間的一系列節點都移動到head_to
上。head_to
必須是 empty 狀態 (next
和prev
都指向自己),否則可能發生 memory leak。list_move
/list_move_tail
將
node
從原本的 linked list 移動到另一個 linked listhead
的開頭或尾端。list_entry
container_of
等價的包裝,符合以list_
開頭的命名慣例,此處的 entry 就是 list 內部的節點。list_first_entry
/list_last_entry
取得 linked list 的開頭或者結尾的 entry。
list_for_each
走訪整個 linked list。注意:
node
和head
不能在迴圈中被更改 (可能在多工環境中出現),否則行為不可預期。list_for_each_entry
走訪包含
struct list_head
的另外一個結構之 entry。entry
和head
不能在迴圈中被更改,否則行為不可預期。typeof
之限制,只能在 GNUC 下使用list_for_each_safe
/list_for_each_entry_safe
透過額外的
safe
紀錄每個迭代 (iteration) 所操作的節點的下一個節點,因此目前的節點可允許被移走,其他操作則同為不可預期行為。Linux 核心風格 Linked List 應用案例
從一些範例來看 Linux 核心風格 linked list 實際的使用方式。
Quick sort (遞迴版本)
sysprog21/linux-list 專案中的 quick-sort.c 程式碼。
先確認
head
所承載的 linked list 有兩個以上 entry,否則就返回,不用排序。以INIT_LIST_HEAD
初始化另外兩個 list 結構,它們分別是用來插入 entry 中比 pivot 小或者其他的節點。藉由
list_first_entry
取得第一個 entry 選為 pivot:list_del
將該 pivot entry 從 linked list 中移除cmpint
回傳兩個指標中的值相減的數值,因此小於0
意味著item->i
的值比pivot
的值小,加入list_less
,反之則同理藉由遞迴呼叫將
list_less
和list_greater
排序。在list_for_each_entry_safe
中,list_move_tail
會將所有原本在head
中的節點移出,因此首先list_add
加入pivot
,再把已經排好的list_less
放在 pivot 前,list_greater
放在 pivot 後,完成排序。Quick sort (非遞迴)
參考 Optimized QuickSort: C Implementation (Non-Recursive),嘗試實作非遞迴的 quick sort。
begin
和end
表示在 linked list 中的排序目標的開頭和結尾,因此最初是整個 linked list 的頭至尾。begin
和end
的效果類似 stack,會填入每一輪要處理的節點開頭至結尾 ,因此先取出該輪的頭尾至L
和R
。接著,以最開頭的節點作為 pivot。
i == MAX_LEN - 1
的目的是額外檢查這輪如果填入begin
和end
是否會超出原本給定的陣列大小,因為我們所給予的空間是有限的否則的話,從結尾的點(
R
)一直往prev
前進,找到比pivot
值更小的節點的話就將其值移到開頭的L
去。同理,從開頭的點(L
)一直往next
前進,找到比pivot
值更大的節點的話,就將其值移到結尾的R
去L != R
則負責判斷當L
往next
而R
往prev
移動碰在一起時,當L == R
時,不再做上述的操作,離開迴圈此時
L
所在地方是pivot
的值應在的正確位置,因此將pivot
的值填入L
。此時需要被處理的排序是pivot
往後到結尾的一段,兩個點分別是L
的next
,和這輪的end[i]
pivot
以前從原本的begin[i]
到L
一段如果
L == R
或者&begin[i]->list == head
,表示此段 linked list 已經不需要再做處理,i--
類似於 pop stack 的操作。Linux 核心原始程式碼
對比 sysprog21/linux-list 與 linux/list.h 的實作,會發現最大的差異在於
WRITE_ONCE
巨集的使用。我們可以比較
list_add
來探討差異的細節乍看之下,若將
WRITE_ONCE(prev->next, new)
替換成prev->next = new
,兩者一樣嗎?WRITE_ONCE
定義在 linux/tools/include/linux/compiler.h 路徑下,我們可以從註解中對其作用進行理解:藉由
WRITE_ONCE
和READ_ONCE
的使用,可以避免編譯器合併、切割、甚至重排特定的記憶體讀寫操作。下面是WRITE_ONCE
的定義:我們可以再次看到 statement expression 技巧的應用。此外,可以看到
WRITE_ONCE
把val
寫入 union 結構中,使其與一個char __c[1]
共享空間。藉由以 union 為基礎的type-punning
技巧,可避免違反 strict aliasing 規則,使得__c
能作為這個 union 的指標來使用,從而允許編譯器最佳化。需注意 type punning 的方式有不同類型,而在 gcc 中,使用 union 進行 type punning 的方式被作為語言的擴展並合法(詳見 gcc: nonbugs),該方式不會違反 gcc 的 strict aliasing 規則。但在其他編譯器中則可能因為違反規則導致 undefined behavior。
關鍵的
__write_once_size
的任務則是把__val
寫入至x
中,但通過巧妙的設計避免編譯器將其做錯誤的最佳化,細節請見下面的__write_once_size
說明在深入
__write_once_size
之前,先來看看這個型別定義。首先需要了解何謂 aliasing: 其所指為同一個位置可被多個 symbol 存取時,這種情形會造成編譯器最佳化的限制。根據 Options That Control Optimization,
-fstrict-aliasing
參數會讓編譯器假設程式撰寫者不會將相似類型 (例如int
和unsigned int
) 以外的指標予以指向同一塊記憶體空間,以允許做更激進的最佳化,該參數在-O2
,-O3
,-Os
下會預設開啟。但我們可根據 Specifying Attributes of Types 中所提到,使用
__may_alias__
告知編譯器此型別允許 aliasing 的發生,避免激進的最佳化導致非預期的程式行為,至於 Linux 這裡特別定義*_alias_t
的目的可以參考註解:對於 1, 2, 4, 8 位元組的變數,可直接搭配
volatile
提示編譯器不要最佳化這個寫入操作。volatile
所考慮的情境在於: 變數的值即使從程式中乍看不會改變,在每一次存取時實際則有可能被更動 (例如該變數可能指向某個 memory mapped I/O,會被硬體更動,或者被 signal handler 和主程式共用的全域變數),因此可避免寫入操作被錯誤最佳化。對於其他長度的變數,則可以透過 memory barriers 搭配
memcpy
的方法來寫入。barrier()
如同其名稱是個屏障,告訴編譯器不能barrier()
前的 load/store 移動到barrier()
後,反之亦然。值得一提的是,Linux 中採用這種 "volatile access" 而非直接將 object 標註為 volatile 屬性,在 doc: volatile considered evil 中有提及後者可能隱藏的問題。
延伸閱讀:
Linux 核心的
list_sort
實作在 linux/list_sort.c 中,可見 Linux 特別針對系統層級的考量所設計的 linked list sort。接下來,嘗試探討其中的設計原理和可能的考量。
先探討其中的實作內容。首先是需要的三個參數:
priv
是一個 pointer,可以用來傳輸cmp
需要的參數head
要被排序的 listcmp
是比較自定義大小的 function pointer註解中說明了在比較
a
b
時,如果a
需置於b
的之後,則cmp
需回傳大於 0 的值。list_sort 是 stable sort,所以不必區分小於或等於 0 的分別。最後則展示一個簡單的 multi-word comparision。
接著,註解中提到這裡的 merge sort 實作重點。方法會保持兩個要被 merge 的 list 至少是
2 : 1
的狀態 (較大的 list 至多是較小者的 2 倍),這可有效的降低比較的次數。list_sort 與一般的 fully-eager bottom-up mergesort 方法不同,後者只要出現兩個 \(2^k\) 大小的 list,就會立刻被合併。而前者的方法是在出現兩個 \(2^k\) 大小的 list 的時候,不立即合併,反之,一直等到下一個 \(2^k\) 的 list 被蒐集起來時,前者的這兩個 linked list 才會被合併起來。只要這2 : 1
的 list 可以完全被放到 cache 裡,就可避免 cache thrashing。在 lib/list_sort: Optimize number of calls to comparison function 可看到更完整的敘述。
那麼前述的規則該怎麼維持呢? 方法中會透過一個
count
來紀錄 pending 的節點數量。當目前的 count + 1 後,會設置第 \(k\) 個 bit 為 1,\(k-1\) 至 0 bit 為 0 時(除了count
為 \(2^k - 1\) 的情境),我們就把兩個 \(2^k\) 長度的 list 做合併。細節在後面探討程式碼時會再嘗試說明得更清楚。對照程式碼的部份解釋:
首先破壞掉 linked list 的 circular 結構,最後的節點(
head->prev
) 的next
指向 NULL。__attribute__((nonnull))
讓 compiler 可以對指定位置的 pointer 是 NULL 時發出警告我們可先來觀察
count
與 merge 的進行之規律。注意到這裡的格式中,左邊是在該 count 的 iter 開始時的狀態,右邊則是經可能的 merge 後把自己加入 pending list 後的狀態。可觀察到,
count
的最小位元的0
假設在位置 k,根據規則就要 merge 出 \(2^{k+1}\) 的 list (除了count
為 \(2^k - 1\))。而後面為 1 的 bit k - 1, k - 2 … 0 可以代表 pending 裡有 \(2^{k-1}, 2^{k-2} ...... 2^0\) 大小的 Llist 各一個,且因為*tail
一開始就指向 \(2^0\) 的那個 list,所以*tail
往 prev 走 k 步就會找到 \(2^k\) 大小的 list A,而 A 的prev
是另一個 \(2^k\) 大小的 list B,我們要把兩者 merge 在一起。回到程式碼,for 迴圈中透過
count
最低位元的連續1
找到此輪要 merge 的兩個 list,且 bits 若不為0
剛好會等同於我們提到要 merge 的count
。最後。每一輪的 list 會把自己的next
設為NULL
而prev
指向 pending,並更新成原本的next
所指向的下一個 node 繼續流程。下面來看
merge
具體的實作:merge 接受參數的兩個
list_head
形態的 a 和 b 後,tail
初始時指向一個 dummy pointer。然後 for 迴圈比較 a 和 b。若 a 應該在 b 之前,則*tail
改指向 a,且tail
被更新以指向「指向 a 的下個節點的指標」,這個步驟等同把 a 加到一個新的 linked list 中,然後下一次改成比 a 的next
和 b,反之也是類似道理。直到a
或b
的next
為 NULL 時,把另一個加入*tail
則完成。繼續來看
list_sort
的實作:當所有的節點都被加入 pending 後,把所有的 pending 都 merge 在一起。刻意留下 pending 中的其一
pending
和其他的 pending merge 在一起的list
去做merge_final
,後者的目的是因為merge
只有做單向(next
)的鏈結,需要把prev
也接去正確的點上,並且回復至 circular linked list 的狀態。Fisher–Yates shuffle
Fisher–Yates shuffle 是用來將一段有限的數列做隨機排序(排列的結果是等概率的) 的演算法。
Pencil-and-paper method
最原始的方法是由 Ronald Fisher 和 Frank Yates 手寫,大致概念如下:
34 5Modern method
考慮到在計算機上的使用,Richard Durstenfeld 提出改進。因為原始方法「從左開始數的第 n 個數字」這個過程涉及對原始陣列的額外調整,所以時間複雜度會是 \(O(n^2)\),這裡的時間複雜度則是 \(O(n)\)。此外,不需另外產生一個儲存的序列(inplace),而是透過 swap 的方式達到同等的效果。
這裡的時間複雜度是以相鄰記憶體儲存的前題,考慮到資料結構的差異可能也會有複雜度的差異,必須思考自己使用的資料結構給出最恰當的演算法。
3
,將原始序列從左開始數的第 3 個數字和最後 1 個數字對調實作
new
作為新的 linked list 的 dummy nodenew_head
總是指向新 linked list 的頭,這是為了回傳時更新 headnew_tail
總是指向新 linked list 的尾端,這是為了重新 append 的時候不需要從頭找起n
,找到第n
個 node,拆下來 append 到新的 linked list 上len == 0
開放原始碼專案中的實作
《Linux Device Drivers》第 3 版的第 11 章有 linked list 相關內容
struct list_head
,使用者需自行管理記憶體glist.h, glist.c
void *
), glib 內部以struct Glist
表示節點, 用法接近 C++ std::list待整理