# 2019q3 Homework3 (list)
contributed by < `kaeteyaruyo` >
## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list？ 一般的 function call 有何成本？
:::info
我看不太懂這個題目的敘述...請問這個問題的意思是
「為何 Linux 採用 macro （static inline function） 的方式實作有關 linked list 操作的函式？」
還是
「為何 Linux 採用 macro 的方式定義 linked list 的資料型態？」
以下回答為針對前者的回答。
:::
因為題目描述的是 function， 所以我想這裡說的 macro 應該是指同樣會在編譯時被展開的 [static inline function](https://gcc.gnu.org/onlinedocs/gcc-4.9.4/gcc/Inline.html)。節錄自文件中的開場白:
> By declaring a function inline, you can direct GCC to make calls to that function faster.
> One way GCC can achieve this is **to integrate that function's code into the code for its callers**.
> This makes execution faster by eliminating the function-call overhead;in addition, if any of the actual argument values are constant, their known values may permit simplifications at compile time so that not all of the inline function's code needs to be included.
> The effect on code size is less predictable; object code may be larger or smaller with function inlining, depending on the particular case.
簡單翻成中文：
> 當你把 function 宣告成 inline function， gcc 會想辦法讓你在 call 這個 function 的時候花更少的時間。
> 其中一個作法就是，**把這個 function 的程式碼內嵌到 call 他的地方。**
> 這可以免去一般的 function call 所需要的 overhead。此外，如果傳進這個 function 的參數是常數的話，還有可能在最佳化的時候，我們會直接算出這個函數代這個參數得到的值，使得程式碼可以不用完全內嵌進來。
> 但是這樣的作法對預處理後的檔案大小有何影響是難以預測的，根據案例的不同，檔案有可能會變大也可能變小。
inline function 既可重複利用、維持程式碼的簡潔與可讀性，亦可享有直接將函式內容內嵌在使用的地方的好處，甚至在某些情況下可以幫助最佳化的進行。以上優點都足說明為何 Linux kernel 選擇用 static inline function 實作 linked list 的相關操作。
而內文中也有提到，一般的 function call 成本或缺點，大概有以下這些：
* 配置一段空間讓 function 可以擺放他的 local variable
* function call 結束時，須要清理不需要的記憶體
* 將 function 的 return address 記錄到 call stack 上面
* 某些嵌入式系統或較小型的單晶片架構，可能無法支援太多層的 function call， [如 PIC16F877 的 call stack 只有八層](https://embeddedgurus.com/stack-overflow/2009/04/pic-stack-overflow/), PIC16C5X 系列甚至只有兩層
以上這些原因會造成時間與空間上的成本，甚至有引起例外的可能。
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
1. Process management
在 [linux/include/linux/sched.h](https://github.com/torvalds/linux/blob/master/include/linux/sched.h) 中搜尋 `struct list_head`， 總共可以找到 14 個結果。 `task_struct` 作為 Linux 中最複雜的一個資料結構，記錄了每個 process 的詳細資料。舉其中較容易理解的範例：
```cpp
/*
* Pointers to the (original) parent process, youngest child, younger sibling,
* older sibling, respectively. (p->father can be replaced with
* p->real_parent->pid)
*/
/* Real parent process: */
struct task_struct __rcu *real_parent;
/* Recipient of SIGCHLD, wait4() reports: */
struct task_struct __rcu *parent;
/*
* Children/sibling form the list of natural children:
*/
struct list_head children;
struct list_head sibling;
struct task_struct *group_leader
```
執行 [`pstree PID`](http://linux.vbird.org/linux_basic/0440processcontrol.php#pstree) 時，以 PID 為 root 的 process tree 會被列出來。 Linux 在管理這些 process 的樹狀結構時，使用了以上程式碼列出來的幾個 field 來記錄親屬關係。
其中，由於一個 process 通常會有一個以上的 sibling 以及 children，為了方便尋找或走訪這些親屬 process， 便使用了 `list_head` 結構來維護。由於 `list.h` 中有提供如 `list_add`, `list_del`, `list_entry`, `list_for_each` 等函數或 macro，這些在新增 process、 結束 process、查詢 process 其它欄位、走訪樹結構時都是很方便的工具。
2. Request queue
在 [linux/include/linux/blkdev.h](https://github.com/torvalds/linux/blob/master/include/linux/blkdev.h) 中，定義了許多跟 disk I/O 有關的資料結構和相關操作。其中，定義了一個 I/O request 的 `struct request` 結構，有著以下欄位：
```cpp
struct request {
struct request_queue *q;
struct blk_mq_ctx *mq_ctx;
struct blk_mq_hw_ctx *mq_hctx;
......
struct list_head queuelist;
......
}
```
在 [Understanding the Linux Kernel, Third Edition](http://140.120.7.21/LinuxRef/LinuxKernel/understandlk-chp-14.html) 14.3.2. Request Descriptors 處，有一段敘述簡單描述了 `struct list_head queuelist` 的功能:
> Essentially, a request queue is a doubly linked list whose elements are request descriptors (that is, request data structures; see the next section). The queue_head field of the request queue descriptor stores the head (the first dummy element) of the list, while the pointers in the queuelist field of the request descriptor link each request to the previous and next elements in the list.
也就是說，在管理 request queue 中的 request 順序時，也用到了 `struct list_head` 這樣的結構。
在 Linux 的 Repository 下[搜尋 "queuelist" ](https://github.com/torvalds/linux/search?utf8=%E2%9C%93&q=queuelist&type=)，即可觀察到其它使用到這個標頭檔的地方，在新增、刪除、走訪、排程等處，也都利用到了 `list.h` 中提供到的那些函式。
3. File system
[struct inode](https://github.com/torvalds/linux/blob/master/include/linux/fs.h)
### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？ 在程式碼中扮演什麼角色？
文件中的第一句話寫說：
> Another way to refer to the type of an expression is with typeof.
也就是說，`typeof` 的功能就是找出一個 expression 的 type。
他有兩種用法。若傳入的參數是一個合法的 C 的 expression （如： `typeof (x[0](1))`，其中`x`是一個函數指標的陣列），則 `typeof` 的值就會是那個 expression 的值的 data type；而如果傳入的直接就是一個 type 的名字的話（如： `typeof(int *)`）， `typeof` 的值就會是那個傳進去的 type。
在作業提供的 `list.h` 中，在兩種情況下有使用到 `typeof`:
* 在 `container_of` 這個 macro 當中，使用到了 `__typeof__` 來取得 member 的 type:
```cpp
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* 在呼叫 `list_entry` （其實就是 `container_of` 時），使用到了 `__typeof__` 來取得 enrty （就是包含著 `list_head` 的 container）的 type
```cpp
list_entry((head)->next, __typeof__(*entry), member);
```
### 解釋以下巨集的原理
```cpp
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
根據 `list.h` 中此巨集的註解，可以知道 `container_of` 的功能在於取得包含其參數 `ptr` 這個地址的容器的地址。一步一步解釋如下：
1. `__extension__` 標示了接下來的程式碼中有使用到非 ISO standard C 規範中的功能，以本例來說，是 `typeof` 運算子，以及包住整個 expression 的 `({})` (braced-group within expression)。其它 gcc 內建的 extension 可參照[本目錄](https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html)。
2. 巨集的第一行是在宣告一個常數指標變數 `*__pmember` ，其型態必須是欲查詢的 `member` 在其容器中的型態，我們利用 `__typeof__(((type *) 0)->member)` 來取得。其中， `(type *) 0` 的 `0` 代表的是 `NULL` 指標，這個寫法只是為了讓 `typeof` 中的 expression 符合 C 語言的文法而已。因為 C 語言中 `NULL` 指標實際上並沒有指到任何一個記憶體位址，而我們也只是要取得 `member` 的型態而已，並沒有要利用 `NULL` 指標進行取值（也就是說，這樣寫並不會對 `NULL` 進行 dereference），所以不會造成 segmentation fault。
3. 完成 `*__pmember` 的宣告後，我們將 `ptr` 存入其中。這個動作是在做 type checking。因為我們無法確保使用者真的會傳入正確型態的 `ptr` 進來，但是可以保證用 `__typeof__(((type *) 0)->member)` 取得的型態絕對是 `member` 正確的型態。因此，如果 `ptr` 傳進來的是不正確的型態，在編譯時期就會噴錯，是一個防呆的動作。
4. 在確認 `*__pmember` 是個正確型態的 `member` 的位址後,我們透過 `(char *) __pmember - offsetof(type, member)` 取得 container 的位址。其中，`(char *) __pmember` 是為了保證計算出來的位址會以 byte 為單位（因為 `offsetof` 算出來的單位是 byte），而 [`offsetof(type, member)`](http://man7.org/linux/man-pages/man3/offsetof.3.html) 是用來取得 `member` 跟container 的頭的位址差值，將 `__pmember` 減去這個差值就可以拿到 container 的位址了。
5. 最後，將取得的位址轉換成 container 的型態 `type`，就可以取得 container 了。
### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
`list.h` 中所提供的 function 和 macro 可以大致分類為以下幾個類別：
```cpp
// Initialization
#define LIST_HEAD_INIT(name)
#define LIST_HEAD(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
// Create
static inline void list_add(struct list_head *new, struct list_head *head)
static inline void list_add_tail(struct list_head *new, struct list_head *head)
// Read
#define list_entry(ptr, type, member)
#define list_first_entry(ptr, type, member)
#define list_last_entry(ptr, type, member)
#define list_first_entry_or_null(ptr, type, member)
#define list_next_entry(pos, member)
#define list_prev_entry(pos, member)
// Update
static inline void list_replace(struct list_head *old, struct list_head *new)
static inline void list_replace_init(struct list_head *old, struct list_head *new)
// Delete
static inline void list_del(struct list_head *entry)
static inline void list_del_init(struct list_head *entry)
// Test
static inline int list_is_last(const struct list_head *list, const struct list_head *head)
static inline int list_empty(const struct list_head *head)
static inline int list_empty_careful(const struct list_head *head)
static inline int list_is_singular(const struct list_head *head)
// Rotate
static inline void list_rotate_left(struct list_head *head)
// Cut and paste
static inline void list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry)
static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list, struct list_head *head)
// Join
static inline void list_splice(const struct list_head *list, struct list_head *head)
static inline void list_splice_tail(struct list_head *list, struct list_head *head)
static inline void list_splice_init(struct list_head *list, struct list_head *head)
static inline void list_splice_tail_init(struct list_head *list, struct list_head *head)
// For each (and their helper macros)
#define list_for_each(pos, head)
#define list_for_each_prev(pos, head)
#define list_for_each_safe(pos, n, head)
#define list_for_each_prev_safe(pos, n, head)
#define list_for_each_entry(pos, head, member)
#define list_for_each_entry_reverse(pos, head, member)
#define list_prepare_entry(pos, head, member)
#define list_for_each_entry_continue(pos, head, member)
#define list_for_each_entry_continue_reverse(pos, head, member)
#define list_for_each_entry_from(pos, head, member)
#define list_for_each_entry_safe(pos, n, head, member)
#define list_for_each_entry_safe_continue(pos, n, head, member)
#define list_for_each_entry_safe_from(pos, n, head, member)
#define list_for_each_entry_safe_reverse(pos, n, head, member)
#define list_safe_reset_next(pos, n, member)
```
* Initialization: 需要先初始化才能開始使用 list
* CRUD: 作為一個資料結構，對於資料的增刪查改基本上是必備的操作
* Test: 測試一個結點或是一整個 list 有沒有特殊屬性（為空、只有一個元素、在尾端...等），大多時候是用來做防呆或防錯的，或作為迴圈終止條件
* Rotate: 在 Linux kernel 中只有兩處被用到，看起來是放在for迴圈裏面用來代替 for each 的
* Cut and paste: 讓資料在不同 list 間移動的操作。目前想到的應用是在排程時將 process 在不同的 priority queue 中移動
* Join: 批次移動大量的資料，有設計成 stack 版本（LIFO）和 queue 版本（FIFO）的不同操作
* For each (and their helper macros): 走訪所有的結點對於無論何種資料結構來說都是很常做的操作（例如：要打印所有的資料、對所有的資料做相同的檢查動作、在所有的資料上新增一個新的欄位...等），然而 list 不像 array 一樣可以透過 index 簡單的走訪，且在不同的情況下需要不同的走訪方式，於是 `list.h` 提供了很多種類的 for each 操作，根據不同的需求，可以自行選擇一種合適的
由於 C 語言和其他的高階程式語言不同，並沒有原生的動態長度 array （如 C++ 中的 vector、 Python 中的 list、 Java 中的 ArrayList... 等）， `list.h` 中的這些操作，某種程度上模擬了這些高階語言提供的動態陣列功能。 List 被廣泛的使用在 Linux kernel 的各處，提供這些統一的 API 可以保持程式的精簡與可讀性，並且能保證這些對於 list 的操作的一致性和安全性。
### `LIST_POISONING` 這樣的設計有何意義？
在 [`poison.h`](https://github.com/torvalds/linux/blob/master/include/linux/poison.h) 中，定義了 `LIST_POISON1` 和 `LIST_POISON2` 兩個指標常數，上面的註解寫著：
> These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries.
作業提供的 `list.h`， 在使用到 poisoning 這個技巧的 `list_del()` 函式上方註解也解釋道：
> The node is only removed from the list. Neither the memory of the removed node nor the memory of the entry containing the node is free'd. ...Accessing the next or prev pointer of the node is not safe.
> LIST_POISONING can be enabled during build-time to provoke an invalid memory access when the memory behind the next/prev pointer is used after a list_del.
簡單來說，在執行 `list_del()` 後，被移除的節點僅僅是變得無法從原本的 list 中走訪到而已，其 container 所使用到的記憶體並沒有被釋放，此時透過別的方式來存取被移除的節點的 `next` 和 `prev` 是不安全的。
為了避免不小心存取到不該存取（但卻可以存取）的空間，在移除節點後須要額外將他的 `next` 和 `prev` 指向存取後會引起錯誤的地址。一般來說我們都會指向 `NULL`，而這裡指向 `POISON[1,2]` 是為了方便快速除錯，我們可以透過 `POISON` 地址的號碼快速知道在存取指標時是出了什麼問題，與眾多嵌入式系統中利用 [`DEADBEEF`](https://en.wikipedia.org/wiki/Hexspeak) 地址標示軟體崩潰或是死結的作法有異曲同工之妙。
### linked list 採用環狀是基於哪些考量？
環狀的 linked list 相較於非環狀的來說有一些好處：
* 沒有所謂「開頭」和「結尾」的節點，因此不需要針對他們做特殊處理，所有的節點一視同仁
* 因為採用 doubly linked list 的方式實作，如果不做成 circular 的話，需要額外儲存尾巴（另外一邊的頭）的 reference
* 要從最後一個節點回到第一個節點不需要大費周張的走過所有人，往前踏一步就行
* 可以從任意一個節點走到另一個任意的節點
在早期， Linux kernel 裏面有各式各樣的 linked list 實作，由於這種資料結構實在太常用到了，寫一個統一的版本可以避免大量擁有相似功能的 code。 而在各種用途當中，有些地方需要環狀的，有些不需要。既然環狀的版本可以 cover 非環狀的所有功能，那麼統一的版本當然實作成環狀的比較合理。
### 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
在 User space 中有許多需要用到排序的地方。由於排序後的資料較方便人們檢索查閱，所以任何需要打印出來的列表通常都是經過排序的，比如：
* `ls` 列出的目錄名稱
* `htop` 列出的所有進程（可按照記憶體使用量 / CPU使用量 / 存在時間等排序）
* `find` 找到的檔案（加上 `sort` 參數）
而在 Linux kernel 中，有提供內建的 list 排序的工具，定義在 [`list_sort.c`](https://github.com/torvalds/linux/blob/e9a83bd2322035ed9d7dcf35753d3f984d76c6a5/lib/list_sort.c) 裏面。裡頭的 `list_sort（）` 函式在檔案系統當中常常被用到，大部分的目的都是為了降低後續要 apply 在 list 上的操作的時間複雜度，如：
* [xfs_extent_busy.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/fs/xfs/xfs_extent_busy.h): 在 `xfs_extent_busy_sort()` 中，使用到了 `list_sort（）` 來排序 busy extent 的列表
* [bitmap.c](https://github.com/torvalds/linux/blob/a2d79c7174aeb43b13020dd53d85a7aefdd9f3e5/fs/xfs/scrub/bitmap.c): 在 `xfs_bitmap_disunion()` 函式中，使用到了 `list_sort（）` 來排序他的兩個參數 `bitmap` 和 `sub`。 這個函式的功能是從 `bitmap` 當中移除所有在 `sub` 裡有出現的元素，之所以要先將兩個列表都排序過，是為了在之後移除節點時只需要走訪過兩個 list 至多一次，以避免 $O（n^2）$ 的時間複雜度
* [fsmap.c](https://github.com/torvalds/linux/blob/ff8583d6e4e33fe3856a609095c683d5dbe39120/fs/ext4/fsmap.c): 在 `ext4_getfsmap_find_fixed_metadata()` 函式中，使用到了 `list_sort（）` 來排序 extent of fixed metadata。 其用意是為了讓 `ext4_getfsmap_merge_fixed_metadata()` 在合併相鄰的 extent 時，可以只要走訪過 list 一次
### 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
當 k = 1 時，相當於在找最大/最小的元素。很多情境下都會需要找最大/最小元素，例如：排程時需要[找到 priority 最高](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c)的任務、記憶體不足時需要找到[得分最高](https://github.com/torvalds/linux/blob/cbafe18c71028d5e0ee1626b4776fea5d5824a78/mm/oom_kill.c)（不是直接某個欄位第一大，是根據計算的公式得出來的第一大）的任務然後殺掉...等等。
至於 k 不為 1 的例子，在 Quick sort 演算法當中，我們知道如果每次挑選 pivot 都挑到最大或最小的那個，會導致最差的時間複雜度 $O(n^2)$。 如果可以在進行 Quick sort 時，每次都挑到整個子序列的中位數的話，就可以保證 Quick sort 能在 $O(nlogn)$ 的複雜度內完成了。此時就會用到第 k 大/小元素的演算法（$k \approx \frac{n}{2}$)。
若只是要找最大或最小值，直接走過整個 list 一次就可以找到最大/小的元素了，複雜度為 $O(n)$，若 list 是已排序的狀態，還可以用二元搜尋法加速到 $O(logn)$。
在用以加速 Quick sort 的時候，可以用 [Median of medians](https://en.wikipedia.org/wiki/Median_of_medians) 的算法粗略找到大約是中位數的數字，其運算複雜度為 $O(n)$。 順帶附上[我過去的實作](https://github.com/kaeteyaruyo/algorithm/blob/master/hw2_5.js)。
如果需要精確的找到第 k 大/小元素，我會選擇用時間複雜度在最平均與最差的情況下都是相同等級的[最大 / 最小堆積法](https://en.wikipedia.org/wiki/Min-max_heap)。
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
首先來觀察這兩個巨集的定義和註解：
```cpp
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
```
`list_for_each` 只用一個 `pos` 變數來走訪所有元素，而 `list_for_each_safe` 多加了一個 `n` 來暫存 `pos` 的下一個元素。根據 `list_for_each_safe` 的註解，說明了這種作法是為了在走訪的過程中有刪除節點的動作時也能正常運作。
在 `list_for_each` 的走訪過程中， `pos` 總是在 for 迴圈的內容做完了以後才更新成他的 `next`。在迴圈主體途中有刪除 `pos` 的狀況時，會將 `pos` 的 `next` 指向 `LIST_POISON`，這會導致 kernel panic；在迴圈主體途中有刪除並初始化 `pos` 的狀況時，會將 `pos` 的 `next` 指向自己，這會導致無窮迴圈。為了避免以上這兩種狀況發生， `list_for_each_safe` 會在開始迴圈主體前就先把 `pos->next` 暫存到 `n` 當中，確保無論接下來做了什麼，都可以取得 `pos` 的下一個人。
### for_each 風格的開發方式對程式開發者的影響為何？
[許多語言](https://en.wikipedia.org/wiki/Foreach_loop#Language_support)都支援 foreach 語句， 就使用習慣上來說， for loop 較常用來做計數（重複做同樣的事情 n 次），而foreach loop 較常用來（或者說：被設計用來）走訪過一個資料結構中所有的元素。
以 foreach 取代 for loop 來走訪資料結構的好處是：我們不再需要知道這個資料結構中總共有多少個元素，也可以進行走訪了，只要我們知道何時該停下來即可（像環狀 linked list 中我們只要走到開頭的地址就知道該停）。我們不再需要有一個 count 去維護 for loop 的停止條件，當資料結構內的元素有所增減時，也不用做額外的處理。
在較複雜的資料結構（如 list, vector, map, set...等）都是以 linked list 為基礎下去實作（而非像陣列一樣使用連續記憶體和 offset 進行定址）的情況下， foreach 風格較 for loop 更適合用來走訪這些結構。
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
在多人協做專案中，程式碼註解或文件是相當重要的。我很喜歡老師說過一句話:
> 即便一個人寫作業，其實是三人的參與：過去的你、現在的你，以及未來的你
有時為了快速開發，我們可能會只在一些較難以直觀理解的程式邏輯上方才寫上註解，卻忽略了對於整個函數的功能的簡述以及每個參數的功能或意義的說明。但其實後者才是對協作者來說最重要的資訊，就像是要用別人寫的 API 時，對方如何實作程式邏輯其實不是重點，用的人需要知道的只有**函數的功能**、**必要的參數**，以及**回傳值**而已。因此，以下形式的註解：
```cpp
/**
* function_name() - function description
* @parameter_name: parameter description
*
* Return: return value
*/
```
基本上已經完整描述一個 API 的所有所需資訊。
其中，加一個 `@` 在參數名稱前方，來源於 [Doxygen](http://www.doxygen.nl/) 這個為 C-like 語言自動產生文件的文件生成器的語法。在函式註解中加入`@param paraname parameter description` ，Doxygen 的 parser 就可以辨別的出來 `paraname` 是該函式的參數名稱，後面的文字是針對這個參數的敘述文字。
我曾經參與本系[新版系網頁](https://github.com/kaeteyaruyo/NCKU-CSIE-Website/tree/develop/static/src/js/components/about/faculty)的開發，在撰寫 JavaScript code時，我們也引用了類似的規範 ([JSDoc](https://devdocs.io/jsdoc/)) 來進行程式註解，以利未來自動產生文件，使得專案可以交由以後的學弟妹進行維護。
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
待補充
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
待補充
----
### 在 GitHub 上 fork [linux-list](https://github.com/sysprog21/linux-list) 並學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，進而實作出 merge sort
- [ ] 附上你的修改過程，也需要讓 `qtest` 得以支援
- [ ] 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入
- [ ] 思考提升排序效率的方法，需要做平均和最壞狀況的分析
待補充
## 參考資料
（部份出現在上文中的 URL 未列出）
* [簡介Linux Block I/O Layer (二) - 探討BIO (Block I/O) and Request 結構 - Blogger](http://adrianhuang.blogspot.com/2010/03/linux-block-io-layer-bio-block-io-and.html)
* [Why this 0 in ((type*)0)->member in C? - Stack Overflow](https://stackoverflow.com/questions/13723422/why-this-0-in-type0-member-in-c)
* [The (char *) casting in container_of() macro in linux kernel - Stack Overflow](https://stackoverflow.com/questions/20421910/the-char-casting-in-container-of-macro-in-linux-kernel)
* [你所不知道的C語言：技巧篇](https://hackmd.io/@sysprog/HyIdoLnjl?fbclid=IwAR3IDjfbHXcyB7m6Ch56h4KFtC_R823AyOu8CED18tLVyA3OD_JqVdCCKeo)
* [D05: list (by afcidk)](https://hackmd.io/@afcidk/Hk75lsjjM?type=view)
* [what is the meaning of 0xdead000000000000? - Stack Overflow](https://stackoverflow.com/questions/27801360/what-is-the-meaning-of-0xdead000000000000/27806246)
* [Why are all the linked lists circular in the Linux Kernel? - Quora](https://www.quora.com/Why-are-all-the-linked-lists-circular-in-the-Linux-Kernel?awc=15748_1571714001_bc77042e98ec2b7c767343e6e6a70a17&uiv=6&txtv=8&source=awin&medium=ad&campaign=uad_mkt_en_acq_us_awin&set=awin&pub_id=78888)
* [Why does the Linux kernel use circular doubly linked lists to store the lists of processes? - Stack Overflow](https://stackoverflow.com/questions/46089965/why-does-the-linux-kernel-use-circular-doubly-linked-lists-to-store-the-lists-of)
* [list_for_each()与list_for_each_safe()的区别 - CSDN博客](https://blog.csdn.net/Choice_JJ/article/details/7496732)
Sign in with Wallet
Connect another wallet