# 2019q1 Homework1 (list)
contributed by < `yiwei01` >
###### tags: `sysprog2019`
## 自我檢查清單
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
一般的 function call 會被 compiler 編譯成組合語言，並且把 function 的參數值、區域變數值以及返回位址 push 進 stack 中，然後再 change control flow 到該 function 所在的記憶體位址，上述過程會有多次的 memory access ,因此程式執行時速度較慢。此外， function 也會被做 type checking 。
macro 則會在 preprocessing 的時候被代換成相對應的程式碼，因此不需要 push function 的參數值、區域變數值以及返回位址進 stack ，也不需要 change control flow ，程式執行速度較快，因此這種會被大量運用的 linked list operation 以 macro 來實作能降低上述 function call 的 overhead 。
另外，inline function 能像 macro 一樣將 function 代換成相對應的程式碼, 但 inline function 是經由 compiler 來代換，所以如果該 inline function 的 code size 太大或為遞迴 function ，則 compiler 會把該 inline function 視為一般 function 。
值得一提的是，在 [Linux 核心設計：第一週作業 list (2019-02-25)](https://youtu.be/HlvvnRXzleQ?t=284) 中，老師強調了 「 static inline 放在 header file 的用法 」，再去參照 [編譯器和最佳化原理篇](http://hackfoldr.org/dykc/https%253A%252F%252Fhackmd.io%252Fs%252FHy72937Me) 後，我得出以下的結論：
1. static inline 放在 header file 的原因：
> 因為編譯器在編譯 .c 檔案時視為獨立的個體，所以如果將 inline function 放在某個 .c 檔裡會造成其他 .c 檔 unvisible 的情況，因此應該要放在 header file
2. 為什麼要加 static ：
> 因為如果沒加 static ， compiler 會認為可能有其他 source file 會 call 這個 function，因此不能被成功代換對應的程式碼到 caller 裡，因為其他 source file 可能也會 call 此 function ，因此沒加 static 的 function 會被 compiler 視為一般 function 編譯
>
> 其他參考 : [macro 與 function 的優缺比較](https://stackoverflow.com/questions/9104568/macro-vs-function-in-c) 、[inline function](https://gcc.gnu.org/onlinedocs/gcc/Inline.html)、[stackover flow 上的討論](https://stackoverflow.com/questions/34139737/inline-function-in-header-file-in-c)
:::warning
請用 compilation unit 和 symbol visibility 原理去解釋
:notes: jserv
:::
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
1. 在 [linux/init/main.c](https://github.com/torvalds/linux/blob/master/init/main.c) 中，可發現 linux 對於 module 的黑名單是透過 linked list 來紀錄，因為被加入黑名單的 module 數量會動態增刪，所以適合透過 linked list 這種資料結構。
```clike=
static bool __init_or_module initcall_blacklisted(initcall_t fn)
{
struct blacklist_entry *entry;
char fn_name[KSYM_SYMBOL_LEN];
unsigned long addr;
if (list_empty(&blacklisted_initcalls))
return false;
addr = (unsigned long) dereference_function_descriptor(fn);
sprint_symbol_no_offset(fn_name, addr);
/*
* fn will be "function_name [module_name]" where [module_name] is not
* displayed for built-in init functions. Strip off the [module_name].
*/
strreplace(fn_name, ' ', '\0');
list_for_each_entry(entry, &blacklisted_initcalls, next) {
if (!strcmp(fn_name, entry->buf)) {
pr_debug("initcall %s blacklisted\n", fn_name);
return true;
}
}
return false;
}
```
2. 在 [linux/kernel/sched/wait.c](https://github.com/torvalds/linux/blob/master/kernel/sched/wait.c) 中，可觀察到 linux 的排班是透過 linked list 來紀錄，因為排班是屬於動態增刪頻繁的行為，所以也適合用 linked list 這種資料結構，下方程式碼為某個 thread 被 block 在 waiting queue 的時間已完成，將其從 waiting queue 刪除的程式碼。
```clike=
void finish_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
unsigned long flags;
__set_current_state(TASK_RUNNING);
/*
* We can check for list emptiness outside the lock
* IFF:
* - we use the "careful" check that verifies both
* the next and prev pointers, so that there cannot
* be any half-pending updates in progress on other
* CPU's that we haven't seen yet (and that might
* still change the stack area.
* and
* - all other users take the lock (ie we can only
* have _one_ other CPU that looks at or modifies
* the list).
*/
if (!list_empty_careful(&wq_entry->entry)) {
spin_lock_irqsave(&wq_head->lock, flags);
list_del_init(&wq_entry->entry);
spin_unlock_irqrestore(&wq_head->lock, flags);
}
}
```
3. 因為 linux 的 memory 是採 paging 機制，所以在 [linux/mm/page_alloc.c](https://github.com/torvalds/linux/blob/master/mm/page_alloc.c) 中可發現大量的 linked list 使用，下方程式碼是在 page replacement 中 free 掉 unreferenced page 的實作方式。
```clike=
void free_unref_page_list(struct list_head *list)
{
struct page *page, *next;
unsigned long flags, pfn;
int batch_count = 0;
/* Prepare pages for freeing */
list_for_each_entry_safe(page, next, list, lru) {
pfn = page_to_pfn(page);
if (!free_unref_page_prepare(page, pfn))
list_del(&page->lru);
set_page_private(page, pfn);
}
local_irq_save(flags);
list_for_each_entry_safe(page, next, list, lru) {
unsigned long pfn = page_private(page);
set_page_private(page, 0);
trace_mm_page_free_batched(page);
free_unref_page_commit(page, pfn);
/*
* Guard against excessive IRQ disabled times when we get
* a large list of pages to free.
*/
if (++batch_count == SWAP_CLUSTER_MAX) {
local_irq_restore(flags);
batch_count = 0;
local_irq_save(flags);
}
}
local_irq_restore(flags);
}
```
### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
由 [doc](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 可知 typeof 的 argument 可為 expression 或是 type，在 linux 的 min/max macro 中被用來判別型別是否一致，範例程式碼如下
```clike=
#include<stdio.h>
#define min(x,y) ({ \
typeof(x) _x = (x); \
typeof(y) _y = (y); \
(void) (&_x == &_y); \
_x < _y ? _x : _y; })
int foo(){
return 100;
}
int main(){
typeof(foo()) a = 10; // 等價於 int a = 10;
printf("a = %d\n",a); // 印出 a = 10
char *b = "book";
typeof(b) t1, t2; // 等價於 char *t1, *t2;
t1 = "cat";
t2 = "dog";
printf("t1 = %s, t2 = %s\n",t1,t2); // 印出 t1 = cat, t2 = dog
typeof(double) k = 2.5; // 等價於 double k = 2.5;
printf("k = %.1f\n",k); // 印出 k = 2.5
printf("min(15,20) = %d\n",min(15,20)); // 印出min(15,20) = 15
}
```
### 解釋以下巨集的原理
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
寫這題前有先看到 [HexRabbit 的共筆](https://hackmd.io/s/BkyoqQ_L4) ，覺得很多地方寫得很清楚，不過後來看到 [這篇](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html) ，思考過後覺得在 [HexRabbit 的共筆](https://hackmd.io/s/BkyoqQ_L4) 中 ```offsetof``` 提到 __*「這裡的 &((TYPE \*)0)->MEMBER 並不是求值後取地址，struct 中的成員變數地址是相對於 struct 的初始地址的，並且編譯時期就可以確定也就沒必要在運行時求值了，所以在此得到的是 0 + offset of MEMBER in struct」*__ 這段話跟我的想法有點出入。
先逐一解釋程式碼：
- [\_\_extension\_\_](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html) :
- GCC uses the \_\_extension\_\_ attribute when using the -ansi flag to avoid warnings in headers with GCC extensions. This is mostly used in glibc with function declartions using long long
- [{}](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) :
- A compound statement enclosed in parentheses may appear as an expression in GNU C. This allows you to use loops, switches, and local variables within an expression. Recall that a compound statement is a sequence of statements surrounded by braces.
- The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct. (If you use some other kind of statement last within the braces, the construct has type void, and thus effectively no value.)
- This feature is especially useful in making macro definitions “safe” (so that they evaluate each operand exactly once).
- \_\_typeof\_\_ :
- [Alternate Keyword](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html) of typeof
探討 ```#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)```時，先確認一點：「structure 裡的 member 是從 structure 的起始位址開始存放」，測試程式如下：
```clike=
#include<stdio.h>
typedef struct student{
int id; // 4bytes
int bonus; // 4bytes
double score; // 8bytes
struct student *next; // 8bytes
}Node;
int main(){
Node node1;
node1.id = 1;
node1.bonus = 5;
node1.score = 88.6;
node1.next = NULL;
printf("node1 starting address = %p\n",&node1);
printf("&node1.id = %p\n",&node1.id);
printf("&node1.bonus = %p\n",&node1.bonus);
printf("&node1.score = %p\n",&node1.score);
printf("&node1.next = %p\n",&node1.next);
}
```
```
執行結果符合預期：
node1 starting address = 0x7ffe126e85d0
&node1.id = 0x7ffe126e85d0
&node1.bonus = 0x7ffe126e85d4
&node1.score = 0x7ffe126e85d8
&node1.next = 0x7ffe126e85e0
```
再來看 <font color="red">(TYPE *)0</font> 其實就是把 address 0 pointer to TYPE 型別，意味著 TYPE 的 starting address 就是從 0 開始，因此<font color="red"> &((TYPE \*)0)->MEMBER</font> 就是取 TYPE->MEMBER 的位址，也因為 TYPE 的 starting address 就是從 0 開始，所以 TYPE->MEMBER 的位址就等同於該 MEMBER 與 TYPE 的 starting address 之 offset，最後再將 TYPE->MEMBER 的 address cast 成 size_t 即為結果。
下方的程式碼對 ```offsetof``` 做了一些修改，其中 ```base_x_offsetof``` 是以 x 當 starting address ，所以所有 MEMBER 都比原本 ```offsetof``` 多了 x (本例中的 x 以 10 代入)，而 ```offsetof2``` 仍以 x 當 starting address ，不過在 cast 成 size_t 後會再減掉 x ，所以會得到與 ```offsetof``` 相同的結果。
```clike=
#include<stdio.h>
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define base_x_offsetof(x,TYPE, MEMBER) ((size_t)&((TYPE *)x)->MEMBER)
#define offsetof2(x,TYPE, MEMBER) ((size_t)&((TYPE *)x)->MEMBER) - x
typedef struct student{
int id;
int bonus;
double score;
struct student *next;
}Node;
int main(){
Node node1;
node1.id = 1;
node1.bonus = 5;
node1.score = 88.6;
node1.next = NULL;
printf("offsetof(Node,id) = %zu\n",offsetof(Node,id));
printf("offsetof(Node,bonus) = %zu\n",offsetof(Node,bonus));
printf("offsetof(Node,score) = %zu\n",offsetof(Node,score));
printf("offsetof(Node,next) = %zu\n",offsetof(Node,next));
printf("base_10_offsetof(Node,id) = %zu\n",base_x_offsetof(10,Node,id));
printf("base_10_offsetof(Node,bonus) = %zu\n",base_x_offsetof(10,Node,bonus));
printf("base_10_offsetof(Node,score) = %zu\n",base_x_offsetof(10,Node,score));
printf("base_10_offsetof(Node,next) = %zu\n",base_x_offsetof(10,Node,next));
printf("offsetof2(Node,id) = %zu\n",offsetof2(10,Node,id));
printf("offsetof2(Node,bonus) = %zu\n",offsetof2(10,Node,bonus));
printf("offsetof2(Node,score) = %zu\n",offsetof2(10,Node,score));
printf("offsetof2(Node,next) = %zu\n",offsetof2(10,Node,next));
}
```
```
執行結果如下：
offsetof(Node,id) = 0
offsetof(Node,bonus) = 4
offsetof(Node,score) = 8
offsetof(Node,next) = 16
base_10_offsetof(Node,id) = 10
base_10_offsetof(Node,bonus) = 14
base_10_offsetof(Node,score) = 18
base_10_offsetof(Node,next) = 26
offsetof2(Node,id) = 0
offsetof2(Node,bonus) = 4
offsetof2(Node,score) = 8
offsetof2(Node,next) = 16
```
最後再來看 ```container_of(ptr, type, member)``` ，這個 macro 用途在：「當現在只知道某個結構成員的 address ，但想取得整個 structure 的 starting address」時可以使用。
這個 macro 的原理是透過傳遞已知結構成員的 address 給 ptr ，再將 structure 傳給 type ，結構成員傳給 member。因此 \__pmember 會保存已知結構成員的 address ，再減掉該結構成員在 structure 中的 offset ，即可知道該 structure 的起始位址。
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
在 [linux/inlude/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中，一開始的註解提到：
```
/*
* Simple doubly linked list implementation.
*
* Some of the internal functions ("__xxx") are useful when
* manipulating whole lists rather than single entries, as
* sometimes we already know the next/prev entries and we can
* generate better code by using them directly rather than
* using the generic single-entry routines.
*/
```
有了 next/prev 的資訊，能寫出更簡便的程式碼，大大降低寫程式的負擔。
### `LIST_POISONING` 這樣的設計有何意義？
先看到 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中使用 `list_del()` 所刪除的 node，其實只是先將其從 linked list 中移除，但該 node 所佔的記憶體區段其實還沒被釋放，因此不該存取 node->prev 或是 node->next ，因為此 node 已經從 linked list 中被移除了，此 node 應被當作 uninitialized，附上 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中 `list_del()` 的程式碼如下：
```clike=
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
WRITE_ONCE(prev->next, next);
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
static inline void __list_del_entry(struct list_head *entry)
{
if (!__list_del_entry_valid(entry))
return;
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
```
再來看 [include/linux/poison.h](https://github.com/torvalds/linux/blob/master/include/linux/poison.h) 中的註解提到：
```clike=
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x200 + POISON_POINTER_DELTA)
```
LIST_POISONING 是將在一般情況下會造成 page faults 的 non-NULL pointers 指向特定的記憶體位址 (zeroed page)，目的是確保未被初始化的 list entries 不會被非法存取。
透過參考 [What is the role of LIST_POISON1 and LIST_POISON2?](https://lists.kernelnewbies.org/pipermail/kernelnewbies/2016-March/015879.html) 可知，藉由將 node->next 和 node->prev 指向 LIST_POISON1 及 LIST_POISON2 後，從 `list_del()` 移除的 node 就是一種會造成 page faults 的 non-NULL pointers，有了這樣的設計便可在 debug 時知道 : **當 error 發生時，若 node->next 與 node->prev 分別指向 LIST_POISON1 與 LIST_POISON2 的話，代表有 use after free 的情況發生**，像是 [lib/list_debug.c](https://github.com/torvalds/linux/blob/master/lib/list_debug.c) 便是 linux 中對應的除錯程式碼。
若沒有 LIST_POISONING 的設計，在 `list_del()` 時將 node->next 和 node->prev 都指向 NULL，在 debug 時便不知道此時的 NULL 代表的是 uninitialized 還是被 delete 之後 assign 的。
而不直接將 node free 掉的原因，可在 [Kernel Self-Protection](https://www.kernel.org/doc/html/latest/security/self-protection.html) 中 Memory poisoning 的部份得知：
> When releasing memory, it is best to poison the contents, to **<font color="#000">avoid reuse attacks that rely on the old contents of memory</font>**. E.g., clear stack on a syscall return (CONFIG_GCC_PLUGIN_STACKLEAK), wipe heap memory on a free. This frustrates many uninitialized variable attacks, stack content exposures, heap content exposures, and use-after-free attacks.
### linked list 採用環狀是基於哪些考量？
在 list.h 中定義了一系列的操作，都是基於環狀 linked list，[這篇](https://myao0730.blogspot.com/2016/12/linux.html)將 list.h 中的 linked list 的結構以圖示畫出來，十分清楚。因為整個 linked list 中的 head 指標其實不包含 data 的部份，因此對 linked list 的前端或尾端的操作都相當方便，像是「插入」的概念其實就是將 2 個 node 之間多連結 1 個新的 node ，因此 `list_add` 便是在 head 與 head->next 間插入，而 `list_add_tail` 則是在 head->prev 與 head 間插入(此處便是利用環狀 linked list 的好處之一)，`list_del` 也不須額外撰寫程式判斷 link list 的邊界情況。
此外， `list_add` 的行為其實就像是 stack 的 `push`，而 `list_add_tail` 的行為其實就像是 `enqueue` 。在 list.h 一系列的操作中，可以明顯感受到這類強大的資料封裝技巧。
### 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
在 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中可看見 `list_sort` 如下:
```clike=
/**
* list_sort - sort a list
* @priv: private data, opaque to list_sort(), passed to @cmp
* @head: the list to sort
* @cmp: the elements comparison function
*
* This function implements "merge sort", which has O(nlog(n))
* complexity.
*
* The comparison function @cmp must return a negative value if @a
* should sort before @b, and a positive value if @a should sort after
* @b. If @a and @b are equivalent, and their original relative
* ordering is to be preserved, @cmp must return 0.
*/
void list_sort(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b))
{
struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
-- last slot is a sentinel */
int lev; /* index into part[] */
int max_lev = 0;
struct list_head *list;
if (list_empty(head))
return;
memset(part, 0, sizeof(part));
head->prev->next = NULL;
list = head->next;
while (list) {
struct list_head *cur = list;
list = list->next;
cur->next = NULL;
for (lev = 0; part[lev]; lev++) {
cur = merge(priv, cmp, part[lev], cur);
part[lev] = NULL;
}
if (lev > max_lev) {
if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
printk_once(KERN_DEBUG "list too long for efficiency\n");
lev--;
}
max_lev = lev;
}
part[lev] = cur;
}
for (lev = 0; lev < max_lev; lev++)
if (part[lev])
list = merge(priv, cmp, part[lev], list);
merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
}
```
### 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
目前想到的是: Quick sort 若選擇第 (n/2) 大的元素作為 pivot ，便可以降低 worst case 發生的機率。
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
`list_for_each` 原始碼如下：
```clike=
/**
* 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` 原始碼如下：
```clike=
/**
* 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_safe` 額外用了 n 這個指向 struct list_head 的 pointer 來紀錄 pos->next ，需要額外用 n 紀錄 pos->next 的理由如下：
考慮透過 `list_for_each` 搭配 `list_del` 來將整條 linked list 的 node 移除的情況：
因 `list_del` 會在移除 node 後，將 node->next 及 node->prev 指向 LIST_POISON 的位址，因此在 `list_for_each` 的 update statement(pos = pos->next) 便會將 pos 更新為 LIST_POISON 的位址，導致 iteration 無法繼續。(存取 LIST_POISON 位址發生 use after free 的 error)
而 `list_for_each_safe` 額外用了 n 這個指向 struct list_head 的 pointer 來紀錄 pos->next ，所以 for-loop 的 update statement 執行 pos = n 後，能繼續走訪下一個 node 。
### for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
python `for` 的用法如下 :
```python=
# Python 的 for 用法
for val in array:
print(val)
```
用 C 寫的話 :
```clike=
// C 的 for 用法
for(int i = 0; i < n; ++i)
printf("%d",array[i]);
```
兩者的比較 :
| 比較項目 | python | c |
|:------:|:-----------:|:-----------:|
| array 長度 | 不須考慮 | 須考慮 (上例中的 n )|
| 走訪方式 | 直接走訪物件 | 須透過額外的 index 變數 (上例中的 i ) |
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
[Doxygen](http://www.doxygen.nl/) 能從 source code 的註解產生相對應的文件說明檔，@ 後面為註解命令，例如：@brief 提供一行對於此 function 的簡短描述、@param 作為 function 的參數說明、@return 作為 function 的 return value 的說明等 ...。
用法如下：
```clike=
/*
* @param num1 the integer to be added
* @param num2 the other integer to be added
* @return sum of two integer
*/
int sum(int num1, int num2){
return num1 + num2;
}
```
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
對 include/list.h 提供的 list operation 進行測試，確認各種 list operation 正確執行。
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
---
## merge-sort with linux-like double-linked list 開發記錄
- 閱讀相關檔案
- include/list.h 基本上就是 linux-like double-linked list 相關的 operation ，回答完上述自我檢查清單後，便快速可以掌握該檔案。
- private/common.h 的程式碼，`random_shuffle_array` 能產生測資，而 listitem 是作為 double-linked list 的 node 。
- quick-sort.c 及 insert-sort.c 示範了 linux-like double-linked list 的應用，這兩個檔案的 `main` 函式大致一樣，皆是透過 `qsort` 排序後的 values 與排序後的 list 進行比對，若有結果不一致則會產生 assertion failure 。
- 程式碼撰寫思路
之前寫 merge-sort 是透過陣列儲存資料，所以會將陣列 divide 成前 (n/2) 個及後 (n/2) 個，不過這次的資料結構是 double-linked list，如果要分成前 (n/2) 個及後 (n/2) 個，我目前想到的方法有三種：
1. 透過一個變數 count 來紀錄 list 的資料數，然後在 `list_for_each` 走訪的時候判斷：如果走訪不超過 count/2 ，就 add 到 list_left ，否則就 add 到 list_right 。
```clike=
static void list_mergesort(struct list_head *head, size_t count)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head list_left, list_right;
struct listitem *item = NULL, *is = NULL;
INIT_LIST_HEAD(&list_left);
INIT_LIST_HEAD(&list_right);
size_t i = 0;
list_for_each_entry_safe (item, is, head, list) {
if (i < count / 2) {
list_move_tail(&item->list, &list_left);
} else {
list_move_tail(&item->list, &list_right);
}
i++;
}
list_mergesort(&list_left, count / 2);
list_mergesort(&list_right, count - count / 2);
list_merge(&list_left, &list_right, head);
}
```
2. 設計兩個 iterator ，一個持續往 head->next 方向前進，將走訪過的 node move 進 list_left 的 tail ; 另一個持續往 head->prev 方向前進，將走訪過的 node move 進 list_right，直到原 list 變成 empty。
```clike=
static void list_mergesort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head list_left, list_right;
struct listitem *item = NULL, *is = NULL;
INIT_LIST_HEAD(&list_left);
INIT_LIST_HEAD(&list_right);
short add_to_left = 1;
while (!list_empty(head)) {
if (add_to_left) {
list_move_tail(head->next, &list_left);
} else {
list_move(head->prev, &list_right);
}
add_to_left = !add_to_left;
}
list_mergesort(&list_left);
list_mergesort(&list_right);
list_merge(&list_left, &list_right, head);
}
```
3. 一個 iterator 持續往 head->next 方向前進，奇數個放進 list_left ，偶數個放進 list_right，這樣的方法雖然不是將 list divide 成前 (n/2) 跟後 (n/2) ，但也是符合 divide and conquer 的精神，能將資料不斷地剖半處理。
```clike=
static void list_mergesort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head list_left, list_right;
INIT_LIST_HEAD(&list_left);
INIT_LIST_HEAD(&list_right);
short add_to_left = 1;
while (!list_empty(head)) {
list_move_tail(head->next, (add_to_left) ? &list_left : &list_right);
add_to_left = !add_to_left;
}
list_mergesort(&list_left);
list_mergesort(&list_right);
list_merge(&list_left, &list_right, head);
}
```
Sign in with Wallet
Connect another wallet