HackMD
2025q1 Homework1 (lab0)
contributed by <lum1nar>
問題簡記
鏈結串列的設計
最初修改 queue.c 時，依循著先前學習鏈結串列的風格，很快就碰上了麻煩。其中，最感到疑惑的是內嵌於其他結構體的 list_head 爲何沒有宣告爲指標？
鏈結串列普遍結構如下, 如果不使用指標，結構體本身會陷入無限循環，無法確認大小。
struct node
{
int data;
struct node next;
/* field ‘next’ has incomplete type */
};
在 Linux Kernel 中，list_head 是內嵌在其他結構體中作使用，因此以下兩種宣告方式都成立。
struct my_data {
int value;
struct list_head list;
};
struct my_data {
int value;
struct list_head *list; /* 使用指標 */
};
以下推測 Linux Kernel 直接將 list_head 宣告成變數的原因。
- 減少記憶體配置的步驟
如果使用指標宣告，則每次都需要呼叫malloc()來配置list_head的記憶體。 - 使
list和value共享同一塊記憶體位置
如此一來， CPU 存取時的 Locality of reference 會比較好，減少 cache miss，提高效能。
註：Locality of reference - 應用程式在訪問記憶體的時候，傾向於訪問記憶體中較為靠近的值 - 避免 NULL 指標錯誤
避免忘記初始化指標的各種問題，提升程式的穩健性。 搭配 container_of
原本推測 container_of 無法搭配指標使用，但經過實測，發現宣告成指標，依舊能夠反推定位到外部 container。
目前推測，Locality of reference 對效能的衝擊不小，是 Linux Kernel 不使用指標的根本原因。後續再進一步實測。
後來再思考後，發現上述的推測並不合理，我完全忽視了 list_head 內部其實就是兩個指標。實際上宣告成指標更是我們能夠走訪鏈接串列的關鍵。我們能對鏈接串列進行排序等操作，是因爲我們能夠存取、修改 prev 、next 儲存的記憶體位置。結論來說，我們沒有理由把 list_head 宣告爲指標，畢竟我們不是使用 list_head 本身來走訪鏈接串列，而是內部的 prev 和 next。
爲何在標頭檔中包含實作細節呢？
在傳統 C 程式設計中，通常會這樣組織程式碼：
- header file (.h) 只宣告函式
- 一個 .c 檔案 定義函式
- 另一個 .c 檔案 使用該函式（透過 #include header）
這樣實作的好處是能夠避免函式重複定義，並且能夠隱藏實作細節。
在 Linux Kernel 中， 部分表頭檔則包含了函式的實作。
/* list.h */
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
最直接的好處就是不必再建立 .c 檔來實作，也不必編譯多個檔案。然而，如果在多個 Source File 引入同個表頭檔，會違反 One Definition Rule。需要引入 static 來限制函式生效的範圍。
同時，Linux Kernel 中的函式還搭配了 inline ，透過內聯，減少函式呼叫開銷，提升效能。一般函式庫只宣告，不包含實作，但某些高效能函式庫（如 Linux Kernel）會在表頭檔內直接實作小函式！
inline、static 的用途
使用 inline 修飾符時，編譯器會嘗試將函式的呼叫直接替換為函式內容，節省函式調用的開銷。
inline int multiply(int a, int b) {
return a * b;
}
/* 函式展開範例 */
int main(){
int x = 5, y = 10;
int sum = multiply(x, 2) + multiply(y, 3); /* 展開前 */
int sum = (x * 2) + (y * 3); /* 展開後 */
}
那麼，所有的函式都可以加上 inline 以提升效率嗎？ 不一定，內聯化函式的本質是將函式呼叫處的代碼替換為函式的內容，這樣會增加程式的程式碼大小。如果執行檔變大，會使得載入時間變長。內聯化後，函式的代碼會重複出現在多個地方。可能會降低 Locality of reference，因為相同的指令在記憶體中多次出現，而不是像常規函式集中於一個位置。
static 根據後方接的是函式、全域變數或區域變數，會有不同用途。在此僅針對搭配函式時的效用做討論。
當我們使用 static 定義函式時，主要目的是限制該函式的作用域，使函式只被各自的 Source File 使用。
#include <stdio.h>
/* 在 header file 中定義並實作函式，使用 static 修飾符 */
static void foo() {
printf("This is foo\n");
}
/* file1.c */
#include "foo.h"
int main() {
foo();
return 0;
}
/* file2.c */
#include "foo.h"
int main() {
foo(); /* 在 file2.c 中也可以正常使用 foo() */
return 0;
}
每個 Source File 獨立擁有自己的 foo 副本，所以每個 foo 都是獨立的，彼此不會相互影響，也不會有重複定義的問題。
隱藏實作細節
不過是區分表頭檔和源文件，對於封裝有什麼幫助呢？原來，要隱藏代碼，是透過不提供源檔案，只提供編譯後的檔案 .a 或 .so ，讓使用者透過表頭檔 .h 進行使用。
假設有一個數學函式庫 mathlib.h 和其實作 mathlib.c
/* mathlib.h (只提供函式宣告) */
int add(int a, int b);
double sqrt_custom(double x);
/* mathlib.c (內部實作，不提供給使用者) */
#include "mathlib.h"
#include <math.h>
int add(int a, int b) {
return a + b;
}
double sqrt_custom(double x) {
/* 實作細節 */
}
只提供 mathlib.h 和 mathlib.a 給使用者時，使用者只能透過 add() 和 sqrt_custom() 這些 API 來運行程式，但無法知道或修改它們的具體實作。
觀察到許多函式庫，如 stdlib.h 和 string.h 引用表頭檔即可使用，但沒看到 .a 檔，是在內部進行實作了嗎？其實內部僅宣告了函式，並不包含實作。實作位於編譯器或操作系統提供的 C 標準庫中，Linux 通常使用 glibc（GNU C Library）作為標準 C 庫實現。
offsetof 巨集 - 計算成員偏移量
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
輸入：
TYPE : 一個結構體類型 (struct)
MEMBER : 該結構體中的一個成員變數
輸出：
回傳 MEMBER 在 TYPE 結構體中 從起始位置 (0) 開始的偏移量，單位是 bytes。
實作原理： 將地址 0 轉型爲 TYPE* 並且存取內部的 MEMBER，回傳內部成員的地址，即爲偏移量。
struct A {
int a;
char b;
};
int main() {
printf("Offset of a: %zu\n", offsetof(struct A, a)); /* 0 （起始位置) */
printf("Offset of b: %zu\n", offsetof(struct A, b)); /* 4 假設 int 爲 4 byte*/
return 0;
}
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
container_of 巨集 - 從內部成員反推出結構體
以下提供較簡略的實作方式，方便理解原理
#define container_of(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))
輸入：
ptr：指向 type 結構體中的某個 member 的指標。
type：包含該 member 的結構體類型。
member：ptr 指向的成員名稱。
輸出：
回傳指向 type 結構體的指標。
實作原理： 將 ptr 指向的記憶體位置 扣除現在和起始位置的距離（成員偏移量），即可回到起始位置。
struct list_head{
struct list_head *next;
struct list_head *prev;
};
struct element {
int data;
struct list_head list;Optionally compare to expected value str
};
int main() {
struct element e;
e.data = 5;
struct element *container =
container_of(&e.list, struct element, list);
printf("e.data = %d\n", container->data); /* e.data = 5 */
}
爲何要將 ptr 轉型成 char* 呢？
因爲 offsetof 回傳的偏移量單位是 byte。而 char 型別的大小為 1 byte，所以當我們用 char * 做指標運算時，ptr + 1 真的就是「+1 byte」。
(char *)(ptr) - offsetof(type, member)
這裡 ptr 先被轉換成 char *，然後再減去 offsetof(type, member)，這樣就能確保偏移量是正確的 byte 位移。
commit 沒有 Changed-Id
根據 Homework 1 review 進行 rebase 後，執行 make test 時出現錯誤，提示最新的 commit 缺少 Change-Id。檢查後發現，lab0-c/git/hooks/commit-msg 第 631 行：
if (match(tolower(footer[line]), '"$TRAILERS_BY_REGEX"'))
發生錯誤，TRAILERS_BY_REGEX 被設置為 /()/，導致無效的正則表達式。進一步追查後，推測是第 189 行使用了不存在的變數名稱。將 DEFAULT_TRAILERS_BY 修正為 KNOWN_TRAILERS_BY 後，git commit 現已正常運作。在討論區分享後，由撰寫相關代碼的同學提交 PR 了 。
佇列功能實作
q_new:
Linux Kernel 採用環狀雙向鏈結串列。透過 malloc 分配記憶體，將 head->prev 和 head->next 都指向 head 來進行初始化。以上步驟可使用 INIT_LIST_HEAD 來完成。注意到，q_new 僅用於建立鏈接串列的開頭，在後續的 q_insert 中並沒有作用。
根據 C99 [7.20.3] 對於 malloc 的介紹
The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer is returned.
如果記憶體配置失敗，malloc 將回傳 NULL，我們使用 if head == NULL 或 if !head 來檢查是否有成功配置記憶體，並如 list.h 要求，在失敗時回傳 NULL。
依據 C99 [6.3.2.3] 及 C99 [7.20.3]
A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again.
The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated).
在成功配置記憶體後，malloc 會回傳 void* ，指向已配置記憶體的開頭。且確保回傳的指標具有適當的對齊方式， 因此 void* 能夠自動轉換成其他類型(Convert)，不需要顯式轉型（Explicit Casting)。
struct list_head* q_new()
{
- struct list_head *head =
- (struct list_head *) malloc(sizeof(struct list_head));
+ struct list_head *head = malloc(sizeof(struct list_head));
- head->prev = head;
- head->next = head;
+ INIT_LIST_HEAD(head);
}
在撰寫 commit message 時，想標示修改了哪一部分的函數，因此參照 Linux Kernel Repository 中在開頭標示名稱的做法。後來注意到，標註的實際上是子系統或是模組名稱，函式並不會標註在開頭。
commit msg : q_new: Reformat code to follow Linux kernel style 是不恰當的。
在使用 git rebase 修正訊息時，發現 Git hook 爆出了很多錯誤訊息，我推測是 commit-msg 中 read_commit_message() 把所有讀進來的 Commit Message 讀成標題了。爲此我去檢查了 COMMIT_MSG_LINES、COMMIT_SUBJECT 變數的內容，卻沒發現任何異狀。
至今爲止的 Commit 中，從沒有出現過錯誤訊息。經過如上的測試後，才發現執行 git commit -a 後，標題和內文根本沒有被讀取進來，然而 COMMIT_MSG_FILE 讀取的文件卻顯示是正確的。此時我才意識到一直以來 Commit Message 都寫錯位置了。最一開始的幾個 Commit 也因此沒有符合要求，待所有函式實作完成後再回去修正。
q_free:
第一次實作時，認爲只要釋放 list_head 即可，但要清除整個 queue ，需要透過存取 element_t 來釋放其字串。可以使用 list_for_each_entry_safe 走訪所有的節點，其中 safe 會記錄下個節點位置，釋放當前節點記憶體後，依然能夠存取下個節點。
最初誤會函式是用來刪除節點，加入了 list_del_init 來維護鏈接串列的結構，但其實 q_free 用於釋放包括 head 的整個鏈接串列，因此沒必要調整節點間的鏈接。
然而，結構體內部的鏈接串列需不需要使用 free 來釋放記憶體呢？ 其實是不用的！如同問題簡記中所敘述的，內部的鏈接串列並沒有宣告成指標，因此其生命週期也會結構體釋放結束。而如果宣告成指標的內部成員則需要 free 來釋放。
另外, entry 和 safe 在迴圈中他們會被初始化，不需要設爲 NULL。而在後續的 q_insert 和 q_insert_tail 中，確保了字串成功配置記憶體時，才會插入節點，不需要考慮字串未配置記憶體的問題，不必檢查 if entry->value。
list_for_each_entry_safe (entry, safe, head, list) {
- if (entry->value)
- free(entry->value);
+ element_t *entry, *safe;
+ list_for_each_entry_safe(entry, safe, head, list) {
+ free(entry->value);
- list_del_init(&entry->list);
+ free(entry);
+ }
+ free(head);
}
q_insert_head:
為 element->value 分配 strlen(s) + 1 大小的記憶體，以確保 包含字串結尾 \0。接著，使用 memcpy 複製字串內容，確保完整複製至 ele->value。
插入節點時，可使用 list_add 將節點插入到 head 之後，或使用 list_add_tail 將節點插入到 head 之前，依需求決定插入位置。
此外，strdup 也能達成上述操作，它會複製字串並回傳新分配的記憶體指標。如果記憶體分配失敗，strdup 會回傳 NULL ，因此需要適當的錯誤檢查來確保安全性。
bool q_insert_head(struct list_head *head, char *s)
{
- element_t *ele = (element_t *) malloc(sizeof(element_t));
+ element_t *ele = malloc(sizeof(element_t));
- ele->value = malloc(strlen(s) + 1);
- memcpy(ele->value, s, strlen(s) + 1);
+ ele->value = strdup(s);
+ if (!ele->value) {
+ free(ele);
+ return false;
+ }
- struct list_head *next = head->next, *node = &ele->list;
-
- next->prev = node;
- node->next = next;
- node->prev = head;
- head->next = node;
+ list_add(&ele->list, head);
}
q_insert_tail:
Commit 71056a2
要將新節點插入到 head->prev 和 head 之間， 我們可以重用 q_insert_head 函式並傳入 head->prev。鏈接串列只包含 head 時是否會出問題呢？不會， head->prev 指向 head， 而此時插入鏈接串列的第一個節點同時是 head->prev 也是 head->next。
return q_insert_head(head->prev, s);
q_remove_head:
Commit 0f6da3e
我們在取得頭部的 entry 後，使用 list_del_init 來移走節點。題目要求將刪除的節點放入 sp 中，但要注意字串的大小是否超過 buffer - 1 。保留一個 char 的位置是保留給 \0，strncpy 能夠複製 n 個字元，但要注意不會自動補上終止符號。
if (sp) {
size_t n = strlen(ele->value);
if (bufsize - 1 < n)
n = bufsize - 1;
strncpy(sp, ele->value, n);
sp[n] = '\0';
}
此處題目要求 "Remove" 節點皆可，因此不需要釋放記憶體。這些無法再存取到的節點該如何釋放記憶體呢？我們回顧 q_free 的實作，使用 list_for_each_entry_safe 走訪鏈接串列並釋放記憶體，因此沒辦法釋放 q_remove 移除的節點。
本來在想是否要新增一個陣列，記錄這些斷開的節點，呼叫 q_free 時一起處理，但總覺得這樣的設計很繁複，爲何不直接釋放掉呢？
後來發現，這個函式要求回傳釋放掉的節點，在 qtest.c 發現 q_remove 函式中， re 指標指向 q_remove_head 或 q_remove_tail 釋放的節點，用來檢查是否有成功刪除元素，並且在這之後，使用 q_release_element 來釋放掉了。
q_remove_tail:
Commit 6fbb228
要移除尾部，我們可以重用 q_remove_head 並且傳入 head->prev->prev。當鏈接串列只有一個節點時，head->prev->prev 指向 head 。而此時、移除開頭的節點相當於移除尾部的節點。
不過要注意，在傳入 head->prev->prev 之前，要確保 head 不爲 NULL ，因此加上了 if !head 的檢查。同時， q_insert_tail 也有相同的問題，也一起提交 Commit 46f6f79 修正了。
q_size:
實作方法如 預計目標 + 開發環境設定 - 牛刀小試 所述
使用 Linux Kernel API 提供的巨集 list_for_each 來走訪整個佇列並計算節點數量。
q_delete_mid:
Commit 4cff19c
原本使用快慢指針來尋找鏈接串列的中點，fast 每次會前進兩倍的距離，當 fast 再次抵達 head 時， slow 會位於中點。
但後來想到可以直接取得尾部的元素，因此使用 L、R 指向鏈接串列的兩端點，並且往對方走去，當兩人相會時，即走到了中點。Commit 1b2a8b4
兩者都可以實現刪除中間節點，但後者代碼更加簡潔，也更好判斷停止點。釋放 element_t 時，不必釋放內部成員 list ，它會隨結構體的釋放一起被釋放，僅有結構體內部的指標要額外釋放。
q_delete_dup:
本來實作是當 fast 和 slow 節點的值相同時，就移除當前 slow 節點，但最後 slow 只剩最後一個相同元素後，就無法移除了。後來改良成先尋找所有相同元素的範圍後，再逐一走訪刪除。Commit e4586f0
後來觀摩 vax-r 的代碼發現，我們的實作方向相同，而要解決上述的問題，其實只要多用一個變數 has_dup 記錄是否有相同元素出現，是的話將最後一個相同元素釋放掉即可。這個方法避免了走訪同樣的序列。 Commit ec83c31
原本認定只有一個節點的話不會進行刪除，因此直接回傳 false ，但在測試時出錯了，檢查 queue.h 才發現，只有在 head 不存在或者爲空時，才會回傳 false ，只有一個元素時要回傳 true。Commit 1d8ba22
element_t *L, *R;
bool has_dup = false;
list_for_each_entry_safe(L, R, head, list) {
if (&R->list != head && !strcmp(L->value, R->value)) {
has_dup = true;
list_del_init(&L->list);
free(L->value);
free(L);
} else if (has_dup) {
has_dup = false;
list_del_init(&L->list);
free(L->value);
free(L);
}
}
q_swap:
Commit 76bb26f
透過迴圈遍歷鏈結串列，依序交換每對相鄰節點。使用 L 和 R 標記當前的兩個相鄰節點，並調整它們的 next 和 prev 指標，將 R 移動至 L 前方。交換完成後，將 L 移動到下一個未處理的節點，直到遍歷完整個串列，最終完成所有相鄰節點的交換。
進行 q_reverseK 測試時發現 K==2 時和 q_swap 是一樣的功能，因此可以重用 q_reverseK。Commit 94e5937
q_reverse:
Commit a80d34d
從 head->next 開始走訪整個鏈接串列，並且將每個點的 prev 和 next 交換。最後再交換 head->next 及 head->prev 即可完成反向排列。
後續改良使用 list_for_each_safe 來走訪鏈接串列，減少了每次自行記錄 next 的操作。而 R 指標最後會停留在 head->next ，可以拿來交換 head->next 和 head->prev 用，之前多宣告了不少變數！Commit ede0002
查閱了 queue.h 確認 q_reverse 在只有一個節點時不應該直接 return。雖然執行後對排列沒有影響，但還是依據要求，把 list_is_singular 的檢查拿掉了。
struct list_head *L, *R;
list_for_each_safe(L, R, head) {
L->next = L->prev;
L->prev = R;
}
head->next = head->prev;
head->prev = R;
q_reverseK: (補上圖示)
Commit 36613e9
反向重新排列的方法如上，但由於無法確定鏈接串列的大小爲 K 的倍數，因此需要先計數，確保有足夠的節點進行反向排序，同時，爲了確保每一組節點的頭尾正確鏈接起來，我使用了 gtail、ghead 變數來保存當前組別的頭尾，一邊後續組別的鏈接。
上述的實作雖然結果是正確的，但代碼相當相對較長，並且沒有善加利用 kernel API。
後來參考了 vax-r 的做法。首先，我們先計算，總共有多少組節點需要反向排列，並透過 list_cut_position 將每一組節點移除並傳入到 rev_list ， 由於 rev_list 只存在當前的組別，因此我們能夠直接對整個 list 呼叫 q_reverse ，並把結果插入到 new_head 中。使用 list_splice_tail_init 能夠在前面操作結束後，將 rev_list 初始化，準備傳入下一組臨界串列。最後，我們需要把 new_head 插入到原本鏈接串列 head 的開頭，以確保不需要反向排列的節點在正確的位置。
圖示 (K == 2)
反向排列第一組
反向排列第二組
將所有排列好的組別放回原本鏈接串列
q_sort:
一開始在切割鏈接串列時，發現 dummy head 的存在非常礙事，左邊的節點會保留 dummy head 而右邊沒有，導致實作很困難，試圖將右邊的鏈接串列加上一個 dummy head 但結果也只是讓步驟更加複雜。再者，q_sort 本身沒有回傳值，所以改成使用迭代的方式來實作，但過程一直出錯，最後也是徒勞。
參考了 davidshiao55 的實作方法。首先我移除了鏈接串列的 head，讓串列變成非循環，就得以順利地切割成一半。再來，引入了 q_mergesort 和 q_mergelists 兩個函數，前者讓 mergesort 能夠回傳合併好的鏈接串列開頭，後者進行兩個鏈接串列的合併。排序完成後，再將 head 接上即可。降序排列則是排序完後，再進行 q_reverse 即可
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *listh = head->next, *listt = head->prev;
listh->prev = NULL;
listt->next = NULL;
listh = q_mergesort(listh);
}
進行 make test 時，發現沒有符合 stable sorting ，原因是相同元素的節點，在排列時變更了順序。只要稍微更改判斷式，讓相同元素以同樣的順序合併到鏈接串列中即可。
- if (strcmp(l->value, r->value) < 0) {
+ if (strcmp(l->value, r->value) <= 0) {
後來注意到測試一直沒有通過 Trace-test-14 ，我本來以爲和出現的警告訊息有關
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
但發現節點數爲 1000000 時，儘管有警告訊息，依然能夠順利通過才測試。後續留意到其實有發生 segmentation fault ，由於沒有較明顯的錯誤，因此推測是遞迴深度太深，佔用了太多記憶體空間，導致的錯誤。
後來參考了 rota1001 的代碼，將 mergesort 改成了迭代版本。
迭代版本方便在於，我們不必砍半鏈接串列，我們解除當前節點與後續節點的鏈接，並放入 stack 中就等於完成了分割的操作。當 stack 中最上面的兩組鏈接串列有相同節點數時，我們就可以依照數值大小合併，並放回 stak 之中。每一組放進去的鏈接串列都是排序好的，正滿足了 mergesort 的條件。當我們插入完所有節點後，將剩下的組別全部合併，最後再透過 list_add_tail 來將鏈接串列回覆成環狀雙向即可。Commit 4fc420f
struct list_head *stack[32], *node, *safe;
unsigned int size[32];
int it = 0;
list_for_each_safe(node, safe, head) {
node->next = NULL;
stack[it++] = node;
size[it - 1] = 1;
while ((it > 1) && (size[it - 1] == size[it - 2])) {
stack[it - 2] = q_mergelists(stack[it - 1], stack[it - 2]);
size[it - 2] *= 2;
it--;
}
}
it--;
while (it >= 1) {
stack[it - 1] = q_mergelists(stack[it], stack[it - 1]);
it--;
}
INIT_LIST_HEAD(head);
node = stack[0];
while (node) {
safe = node->next;
list_add_tail(node, head);
node = safe;
}
q_ascend
Commit a315198
要確保當前節點右邊沒有更小的值，我們可以從右方向左進行走訪，並且沿路記錄最小值，如果有節點的數值大於最小值，代表他的右方會有比他小的節點，我們將此節點刪除。如此一來就可以留下升序排列的鏈接串列。
測試時不斷出現鏈接串列大小不止爲零的錯誤， 原來最後要回傳刪除過後鏈接串列的大小。
其實不用沿路記錄最小值，我們比較兩個節點，如果左邊的不大於右邊，代表左邊一定會是新的最小值，我們不必透過判斷式來檢查，直接更新最小值即可。
if (strcmp(list_entry(R, element_t, list)->value,
list_entry(L, element_t, list)->value) > 0) {
L = L->prev;
R = R->prev; /* 直接更新最小值 */
}
另外，之前的 q_ascend 在運行時會報錯，原因是釋放 list 記憶體時應該要透過釋放 element_t 來同步釋放內部的鏈接串列， 但不留心直接釋放了鏈接串列導致了錯誤。
- free(li) /* 不要直接釋放內部鏈接串列 */
+ free(ele) /* 會把鏈接串列一起釋放 */
q_descend
Commit a315198
實作方法如上，從右方向左進行走訪，並且沿路記錄更新最大值，如果有節點的數值小於最小值，代表他的右方會有比他大的節點，我們將此節點刪除。如此一來就可以留下降序排列的鏈接串列。
q_merge:
Commit 45af3f3
再實作之前，沒有完整的閱讀 queue.h 中的內容，導致連 queue_contex_t 這個結構體都不清楚，一開始看到僅僅傳入 head ，完全沒有頭緒如何找到其他鏈接串列。
queue_contex_t 結構體將所有的鏈接串列鏈接了起來，而在 q_merge 傳入的 head 更是此結構體的開頭，而不是任意鏈接串列的開頭！因此要走訪下一個鏈接串列我們只需要使用 head = head->next 皆可。由於時間有限，我先採取了天真的實作方式，我將所有的鏈接串列接到第一個鏈接串列的後方，最後再進行 q_sort，將所有的鏈接串列合併在了一起。
參考文件
Linux 核心原始程式碼巨集: container_of
你所不知道的 C 語言: linked list 和非連續記憶體
