# 2024q1 Homework1 (lab0)
contributed by < [ranvd](https://github.com/ranvd) >
### Reviewed by Shawn531
* 開發紀錄中可以加入 commit 連結以便追蹤。
* 善用 `diff`
### Reviewed by `ShawnXuanc`
可以減少完整程式碼的張貼
程式碼有善用 list 巨集以及將重複的程式碼再利用
### Reviewed by `Shiang1212`
有幾份 commit 沒有撰寫 commit message。即便該 commit 只有簡單的程式更動，仍應該在 commit message 中描述程式碼更動的重點，加速其他開發人員理解這份程式更動的脈絡，進而提高專案的可維護性。
## 開發環境
```shell
$ uname -r
5.15.133.1-microsoft-standard-WSL2
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 10
Socket(s): 1
Stepping: 3
BogoMIPS: 5376.00
```
## 針對指定佇列操作的實作
### `q_new`
:::danger
改進你的漢語表達。
:::
一開始我沒有檢查 `malloc` 的回傳結果，因此當 `malloc` 失敗時回傳的 NULL 會導致在執行 `INIT_LIST_HEAD` <s>巨集</s> 內的程式碼時對 null pointer 取值，進而引發 segmentation fault。因此增加了以下程式碼檢查 `malloc` 是否成功。
:::danger
`INIT_LIST_HEAD` 不是巨集。
:::
```diff
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(new);
+ if (!new)
+ return NULL;
return new;
}
```
### `q_free`
因為 head 有可能是 null pointer，因此在執行 q_free 動作前應該先檢查 head 是否為 NULL，否則會觸發 segmentation fault。
```diff
void q_free(struct list_head *head)
{
element_t *e, *s;
+ if (!head)
+ return;
list_for_each_entry_safe (e, s, head, list) {
q_release_element(e);
}
free(head);
}
```
### `q_insert_head` 與 `q_insert_tail`
由於一開始沒注意到 `strdup` 也透過巨集的方式替換成專案內的實作，在 `make test` 時一直想不透為什麼檢查了 `malloc` 的回傳值後 `q_insert_head` 還會觸發 segmentation fault。在發現 `test_strdup` 內也使用到 `test_malloc` 後就增加下列程式碼，透過檢查 `new->value` 是否為 null pointer 來判斷 `strdup` 是否有執行成功。(`q_insert_tail` 也有相同的更動)
```diff
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
new->value = strdup(s);
+ if (!new->value) {
+ free(new);
+ return false;
+ }
list_add(&new->list, head);
return true;
}
```
閱讀 [alanjian85](https://hackmd.io/@alanjian85/lab0-2023) 時，看到老師在多處提醒應該盡量重複使用程式碼，因此以下將 `q_insert_tail` 改寫，重複使用 `q_insert_head` 中的程式碼。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
return q_insert_head(head->prev, s);
}
```
### `q_remove_head` 與 `q_remove_tail`
因為 strncpy 會將字串中的前 n 個字元複製到指定的空間，因此當要複製的字串超過 bufsize 時，會使得指定指定的空間中的字串沒有 `'\0'`，因此後續如果在執行 printf, strcpy 等函式的時候會出現錯誤。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *rm = head->next;
list_del(rm);
if (sp){
strncpy(sp, list_entry(rm, element_t, list)->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return list_entry(rm, element_t, list);
}
```
也在閱讀 [alanjian85](https://hackmd.io/@alanjian85/lab0-2023) 時，看到老師在多處提醒應該盡量重複使用程式碼，因此以下將 `q_remove_tail` 改寫，重複使用 `q_remove_head` 中的程式碼。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
return q_remove_head(head->prev->prev, sp, bufsize);
}
```
### `q_delete_mid`
使用快慢指標來找出佇列中的中間點。在重新閱讀自己的實作後，發現 `head == head->next` 應該使用 list.h 內的 `list_empty` 替代，以提高程式碼的可讀性。
```diff
bool q_delete_mid(struct list_head *head)
{
- if (!head || head == head->next)
+ if (!head || list_empty(head))
return false;
struct list_head *slow, *fast;
fast = head;
list_for_each (slow, head) {
if (fast->next == head || fast->next->next == head)
break;
fast = fast->next->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
### `q_reverse`
透過 list.h 提供的介面 `list_move` 與 `list_for_each_safe` 可以很方便的實作 q_reverse 的功能。
```c
void q_reverse(struct list_head *head)
{
struct list_head *li, *sa;
list_for_each_safe (li, sa, head)
list_move(li, head);
}
```
### `q_reverseK`
由於 q_reverseK 函式要求在佇列中每 K 個節點要進行反轉，因此我將每 k 佇列中的節點放到暫時的佇列 tmp 中，並透過上面提到的 q_reverse 函式將佇列反轉。反轉過後的佇列可以使用 list.h 中提供的介面 list_splice_tail 放到新的佇列 result 中，這樣可以避免一個一個加入節點。
```c
void q_reverseK(struct list_head *head, int k)
{
if (k <= 0)
return;
struct list_head result, tmp;
INIT_LIST_HEAD(&result);
INIT_LIST_HEAD(&tmp);
while (!list_empty(head)) {
struct list_head *p = head->next;
for (int i = 1; i < k && p != head; i++) {
p = p->next;
}
list_cut_position(&tmp, head, (p == head) ? p->prev : p);
if (p != head)
q_reverse(&tmp);
list_splice_tail(&tmp, &result);
}
list_splice(&result, head);
}
```
### `q_swap`
在閱讀 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_swap) 時，看到 yanjiew 的 `q_swap` 的實作後，發現 `q_swap` 要求每兩個節點相互交換位置，因此可以視為 `q_reverseK(head, 2)`，因此將實作改成以下方式。
```c
void q_swap(struct list_head *head)
{
q_reverseK(head, 2);
}
```
### `q_descend` 與 `q_ascend`
`q_descend` 與 `q_ascend` 要求剩下在佇列中的節點要符合嚴格的遞減/遞增序列，以下以 q_descend 作範例。由於 `q_descend` 要求佇列符合嚴格的遞減序列，因此可以得知，對於任意一個在佇列中的節點，其前面的節點必定要大於自己，且其後面的節點必定小於自己。因此可以從佇列的後面開始遍歷整個佇列，在過程中用指標 max 紀錄目前遇到的最大值的位置。如果在遍歷的過程中 max 有被更動即代表上個 max 與現在 max 的節點符合嚴格遞減序列的要求；反之，如果再遍歷的過程中 max 沒有被更動即代表 max 與現在走訪到的節點不符合嚴格遞減序列，因此要將目前走訪到的節點從佇列中移除。
```c
int q_descend(struct list_head *head)
{
struct list_head *n, *safe, *max = head->prev;
int size = 1;
for (n = max->prev, safe = n->prev; n != head;
n = safe, safe = safe->prev) {
if (strcmp(list_entry(n, element_t, list)->value,
list_entry(max, element_t, list)->value) > 0) {
size++;
max = n;
} else {
list_del(n);
q_release_element(list_entry(n, element_t, list));
}
}
return size;
}
```
`q_ascend` 與 `q_descend` 很像，只需將判斷式從 > 0 改成 < 0 即可，目前想到的重複利用程式碼的方式為使用巨集來做代換。不過這樣只有看起來程式碼比較少，實際上在巨集展開後是一樣的，因此目前沒有實作。
### `element_t_cmp`
因為後續 `q_sort` 與 `q_merge` 需要考慮到不同的排序方式(由 descned 變數控制)，因此實作一個比較函式來統一回傳的介面對後續的實作比較方便，程式也可以保持較高的可讀性。
根據 [man 3 strcmp](https://man7.org/linux/man-pages/man3/strcmp.3.html)
> The strcmp() and strncmp() functions return an integer less than, equal to, or greater than zero if s1 (or the first n bytes thereof) is found, respectively, to be less than, to match, or be greater than s2.
由敘述只能得知當兩個不同的字串 s1 與 s2 放到 strcmp 的結果可能是大於 0 或小於 0，並不能確定是否為 1 或 -1，因此此函式也會遵循這個規定。
首先分析可能發生的情況
* a > b 且 descend = 1：回傳一個大於 0 的數值
* a > b 且 descend = 0：回傳一個小於 0 的數值
* a == b：回傳 0
* a < b 且 descend = 1：回傳一個小於 0 的數值
* a < b 且 descend = 0：回傳一個大於 0 的數值
因此可以透過將 `descend << 31` 與 `strcmp` 的結果做 XOR 運算後做 `-` 運算來取得正確的會傳結果。例如 a < b 且 descned=1 時，回傳結果應該要小於 0，透過 `strcmp(a, b) ^ descend << 31`，使得最高位元因為 XOR 運算被設為 0，此時結果大於 0，最後加上 `-` 運算就可使結果小於 0。
```c
static int element_t_cmp(struct list_head *a, struct list_head *b, bool descend)
{
char *a_value = list_entry(a, element_t, list)->value;
char *b_value = list_entry(b, element_t, list)->value;
return -(strcmp(a_value, b_value) ^ (descend << 31));
}
```
### `q_sort`
在 `q_sort` 實作中採用部分 timsort 的想法與 buttom-up 的 merge sort 的合併方式，一開始會將佇列分成多個 run，每個 run 之間使用 prev 指標來連接，形成堆疊的結構，如下圖。每個 run 皆會符合 `descend` 變數中的要求，如果 `descend==1` 則 run 以遞減方式排列；反之，以遞增方式排列。當將所有佇列的節點分成不同的 run 後就會進行 run 之間的合併，合併的方式為每兩個連續的 run 一組，並以組為單位合併，以此方式不斷迭代直到堆疊中只剩下一個 run。
> 假設有 n 個 run，則在第一次迭代後會剩下 $\lceil {n\over 2}\rceil$ 個 run，第二次迭代剩下 $\lceil {n\over 4}\rceil$，以此類推直到剩下一個 run 在堆疊中。
```graphviz
digraph structs{
rankdir=BT
node[shape=record]
run1 [label="<p> run_1|..."];
run2 [label="<p> run_2|..."];
run3 [label="<p> ..."];
run4 [label="<p> run_n|..."];
run4:p -> run3;
run3 -> run2:p;
run2:p -> run1:p;
}
```
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return;
/* convert circular-linked list into linear-linked list */
struct list_head *list = head->next, *stk_ptr = NULL, *tmp;
list_del_init(head);
list->prev = list->prev->next = NULL;
int stk_size = 0;
while (list) {
tmp = find_run(&list, descend);
stk_size++;
tmp->prev = stk_ptr;
stk_ptr = tmp;
}
list = merge_force_collapse(stk_ptr, descend);
for (struct list_head *safe = list->next;;) {
list_add_tail(list, head);
list = safe;
if (!list)
break;
safe = safe->next;
}
}
```
在合併堆疊中的 run 的過程中，除了需要紀錄堆疊的開頭外，也需要將合併後的 run 放回堆疊中的正確位置，為了省去特殊情況的判斷，在連接 run 與紀錄堆疊的開頭時可以使用指標的指標來實作。
```c
static struct list_head *merge_force_collapse(struct list_head *stk,
bool descend)
{
while (stk && stk->prev) {
struct list_head **iptr = &stk;
while ((*iptr) && (*iptr)->prev) {
(*iptr) = merge_at(*iptr, descend);
iptr = &(*iptr)->prev;
}
}
return stk;
}
```
由於在開發 q_sort 過程中一直觸發 segmentation fault，因此使用 GDB 進行除錯。在過程中一直遇到 `ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient` 的問題。透過 GDB 的 `bt`、`up`、`down` 追蹤程式碼後發現是因為執行時間過長，導致系統發出 `SIGALRM` 的訊號。從 [GDB 5.4 Signals](https://sourceware.org/gdb/current/onlinedocs/gdb.html/Signals.html) 的手冊可以看到，GDB 可以針對不同的 Signal 做出不同的應對方式，在將 GDB 對 `SIGALRM` 的行為設定為 ignore 後就可以正常除錯。
不過在後續閱讀 [README.md](https://github.com/ranvd/lab0-c/blob/master/README.md) 的時候發現，文件已經告知使用 `./script/debug -d` 就可以直接正常的除錯。
### merge_list
用來合併兩個環狀鏈結串列，使用兩層迴圈，外層走訪鏈結串列 `from`，內層走訪鏈結串列 `to`，因為呼叫 `merge_list` 的前提是兩個鏈結串列是已經排序好的，因此內層的迴圈會透過先前提到的 `element_t_cmp` 函式來判斷 `cmp_ptr` 是否指向第一個 `list` 可以插入的位置，等到找到位置後將 `list` 從 `from` 中移出並加入插入至 `cmp_ptr` 前。當兩個迴圈都走訪完後，如果 `from` 還有節點沒有被放入 `to`，則將剩下的節點全部放入 to 的尾端。
```c
static void merge_list(struct list_head *to,
struct list_head *from,
bool descend)
{
struct list_head *list, *safe, *cmp_ptr = to->next;
if (list_empty(from))
return;
list_for_each_safe (list, safe, from) {
while (cmp_ptr != to && element_t_cmp(cmp_ptr, list, descend) > 0) {
cmp_ptr = cmp_ptr->next;
}
if (cmp_ptr == to)
break;
list_del(list);
list_add_tail(list, cmp_ptr);
}
list_splice_tail_init(from, to);
}
```
### q_merge
這裡的 merge 因為要求需要將所有的鏈結串列合併至第一個，因此這個實作並沒有太多的考量，而是以實作上方便做優先，直接將除了第一個以外的鏈結串列合併至第一個鏈結串列。
```c
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
struct list_head *f = head->next, *m = f->next;
for (; f != head && m != head; m = m->next) {
queue_contex_t *to = list_entry(f, queue_contex_t, chain);
queue_contex_t *from = list_entry(m, queue_contex_t, chain);
merge_list(to->q, from->q, descend);
}
return q_size(list_entry(f, queue_contex_t, chain)->q);
}
```
:::danger
既然你選擇合併排序演算法，你要如何確保輸入的資料涵蓋合併排序演算法的最差狀況呢？
:::
## 確保 linenoise 套件在 web 啟動時正常執行
> 目前只有使用 firefox 瀏覽器測試成功，使用 Chrome 會出現非預期錯誤，整個程式會卡在 web_recv，變成只剩下 web 功能，目前沒辦法解決。
原本在啟動 web 功能後 linenoise 的功能會因為 `use_linenoise` 被設定為 `false` 而關閉，因此我的想法是直接忽略這項變數，在 linenoise 內使用 [select](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫同時監控 socket file descriptor 與 stdin file descriptor，就如同[作業中的提示](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-f)。
為了能夠在不同的檔案中存取到 socket file descriptor，應將 web_fd 以一般變數的方式宣告。並且在執行 `interpret_cmd` 後應將建立的連線 (`web_connfd`) 關閉，防止 client 端無盡的等待。
```diff
-static int web_fd;
+int web_fd = -1;
bool run_console(char *infile_name)
{
... 略
if (!has_infile) {
char *cmdline;
- while (use_linenoise && (cmdline = linenoise(prompt))) {
+ while (cmdline = linenoise(prompt)) {
interpret_cmd(cmdline);
line_history_add(cmdline); /* Add to the history. */
line_history_save(HISTORY_FILE); /* Save the history on disk. */
line_free(cmdline);
while (buf_stack && buf_stack->fd != STDIN_FILENO)
cmd_select(0, NULL, NULL, NULL, NULL);
has_infile = false;
+ if (web_connfd){
+ close(web_connfd);
+ web_connfd = 0;
+ }
}
- if (!use_linenoise) {
- while (!cmd_done())
- cmd_select(0, NULL, NULL, NULL, NULL);
- }
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
}
```
接著是修改 linenoise 套件的內容，因為 stdin 與 socket 這兩邊的 file descriptor 隨時有可能有輸入，因此選擇使用 `select` 來等待可執行相應動作的 file descriptor。不過這兩個 file descriptor 的輸入行為有很大的區別，socket 這邊的輸入會是完整的<s>指令</s> 請求，不存在<s>指令</s> 命令只打到一半情況，例如使用 web 的方式執行 `new`，傳送過去的<s>指令</s> 命令就只能是 `new`，如果只傳了 `ne` 則會因為沒有辦再修改而直接跳出錯誤；反之，stdin 這邊的輸入可以在任何情況下針對目前還沒傳送出去的<s>指令</s> 命令做修改，且由於需要支援自動補齊，所以每當 stdin 有任何輸入時程式都應該做出相對應的反應。
:::danger
「指令」？
> 更正：command 的中文翻譯是命令
:::
因此我在 linenoise 中宣告了兩個新變數，第一個是 `struct line_state` 靜態全域結構 `g`，用來備份 stdin 輸入時的狀態；第二個是靜態 `bool` 變數 `need_swap` 用來紀錄上一次處理的資料是否是來自 socket 端，如果是的話 need_swap = 1。
```c
static struct line_state g;
static bool need_swap = 0;
```
如果當 stdin 輸入到一半時 socket 要求建立連線，就可以先將目前的狀態存至 `g` 中，並處理 socket 的請求。如果目前處理的是 socket 連線，則 `need_swap = 1`，這代表下一次在做 select 之前需要先將在 g 的資料寫回 l 作為目前的狀況。
```c
} else if (FD_ISSET(web_fd, &read_fds)) {
/* Copy l into g which is used for store current state*/
line_state_write(&g, &l);
need_swap = 1;
FD_CLR(web_fd, &read_fds);
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
...建立連線
```
在處理完 socket 的請求後，依據 `need_swap` 內的數值選擇是否要將 `g` 的資料寫回 `l`，即恢復被中斷前的狀態，且應該要將 `l.buf` 內的資料輸出至畫面中，讓使用者知道自己剛才打的指令內容，這樣即使輸入到一半被中斷，stdin 端的功能不會受影響。
```c
if (need_swap) {
need_swap = 0;
line_state_write(&l, &g);
if (write(l.ofd, l.buf, l.len) == -1)
;
}
...略
int result = select(nfds, &read_fds, NULL, NULL, NULL);
```
執行結果會如下面所展示。當使用者輸入 `my input buffer` 時，有一個 socket 端的請求，會先保存目前的狀態，並處理 socket 的執行內容。接著，恢復剛才 socket 進入前的狀態，並將 `l.buf` 的內容輸出至介面 (即 `my input buffer`)。
```shell
cmd> web
listen on port 9999, fd is 3
cmd> my input buffer
Warning: Calling insert head on null queue
l = NULL
cmd> my input buffer
```
:::danger
文字訊息避免用圖片來表示，否則不好搜尋和分類
> 收到
:::
<s>
</s>
:::danger
重新張貼「關鍵」程式碼。
:::
### 目前已知此實作的缺陷
除了在一開始提到程式無法在 chrome 瀏覽器上正常的執行外，當按下 tab 鍵使用自動補齊功能時，為了維持功能的正常運作，在 `complete_line` 函式中會再次讀取一個字元，作為後續動作的執行依據。因此當按下 tab 鍵時，網頁端的請求會被 block 住，要等到 stdin 再次按下除了 tab 以外的鍵才可以。
```c
static int complete_line(struct line_state *ls)
{
line_completions_t lc = {0, NULL};
char c = 0;
... 略
int nread = read(ls->ifd, &c, 1);
if (nread <= 0) {
free_completions(&lc);
return -1;
}
switch (c) {
case 9: /* tab */
i = (i + 1) % (lc.len + 1);
if (i == lc.len)
line_beep();
break;
case 27: /* escape */
/* Re-show original buffer */
if (i < lc.len)
refresh_line(ls);
stop = true;
break;
default:
/* Update buffer and return */
if (i < lc.len) {
int nwritten =
snprintf(ls->buf, ls->buflen, "%s", lc.cvec[i]);
ls->len = ls->pos = nwritten;
}
stop = true;
break;
... 略
}
```
## 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
> 以下當變數不為陣列時，使用 `count[k]` 表示第 k 個 bit；`count[k-1:0]` 表示第 k-1 到第 0 個 bits。
從以下註解可以得知 `list_sort` 為 2:1 balance merge sort。即意，在等待合併的鏈結串列中，有兩個長度為 $2^k$ 的鏈結串列時，且在這鏈結串列之後的資料個數總和如果等於 $2^k$ 時就將這兩個鏈結串列進行合併成長度為 $2^{k+1}$ 的鏈結串列。
```
* This mergesort is as eager as possible while always performing at least
* 2:1 balanced merges. Given two pending sublists of size 2^k, they are
* merged to a size-2^(k+1) list as soon as we have 2^k following elements.
```
`count` 為 `list_sort` 中用來記錄目前已經放入等待合併的資料個數。根據以下註解可以得知，當 `count` 數量增加，導致 `count[k]==1` 且 `count[k-1:0]==0` 時，代表有兩個長度為 $2^k$ 的鏈結串列可以被合併成 $2^{k+1}$。除了 `count[k]` 第一次等於 1 時例外 (即 `count` 為 2 的冪時)。
```
* Each time we increment "count", we set one bit (bit k) and clear
* bits k-1 .. 0. Each time this happens (except the very first time
* for each bit, when count increments to 2^k), we merge two lists of
* size 2^k into one list of size 2^(k+1).
```
註解中提到，需要透過 `count[k-1]` 與 `count[n:k+1]` 的資訊得知目前有幾個長度為 $2^k$ 的鏈結串列在等待合併。因此可以分為六種不同的情況，以下 `x` 代表任意的數值；`y` 代表不為 0 的數值，且如果 `k==0` 時 -1 bit 當作是 1。其中第五種情況 (`y01x`) 最為重要，因為代表有兩個長度為 $2^k$ 的鏈結串列在等待合併，當發生上面提到的 `count[k]==1` 且 `count[k-1:0]==0` 時就將兩個 $2^k$ 鏈結串列合併。考慮 `count` 為 (10101)~2~ 時，等待合併的鏈結串列為 8+8+2+2+1，此時同時在 k=3 與 k=1 的位置皆出現第五種 `y01x` 的情況，但再將 `count+1` 後 `count` 為 (10110)~2~ 這時只有 `k=1` 的位置發生了 `count[1]==1` 且 `count[0:0]==0` 的情況，因此將 $2^1$ 合併，等待合併的鏈結串列變成 8+8+(4)+1+1。
```
* The number of pending lists of size 2^k is determined by the
* state of bit k of "count" plus two extra pieces of information:
*
* - The state of bit k-1 (when k == 0, consider bit -1 always set), and
* - Whether the higher-order bits are zero or non-zero (i.e.
* is count >= 2^(k+1)).
*
* There are six states we distinguish. "x" represents some arbitrary
* bits, and "y" represents some arbitrary non-zero bits:
* 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
* 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
```
由上面的例子中可以知道，當有同時有兩個不同的數字 $k$ 與 $k'$ 使得正在等待合併的鏈結串列中分別有兩個 $2^k$ 與 $2^{k'}$ 時，會從小的數字開始合併。可以看到，list_sort 中透過 for 迴圈將最低位的 0 找出來後，就去判斷 bits 是否為 0，如果不為 0 就代表符合 `y01x` 的情況，因為 `count` 會在 while 迴圈最後時加一，使得 `count[k]==1` 且 `count[k-1:0]==0`，因此這邊可以先進行合併。
```c
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
當所有的節點都已經從 list 中拿出，代表所有的節點都已經在 pending 中等待合併。因此這時候需要將在 pending 上的多個鏈結串列合併成一個鏈結串列。這時會從長度最小的開始合併，同時因為一開始的限制 (當 $2^k$ 合併成 $2^{k+1}$ 時，合併與未合併的鏈結串列長度總和必須要有 $3\times2^k$)，使得在最差的情況下只會是兩個長度為 2:1 的鏈結串列做合併。
```c
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
### 論文閱讀
在 [Queue-Mergesort](https://www.sciencedirect.com/science/article/pii/002001909390088Q?via%3Dihub) 中利用 Huffman encoding 的方式證明了在最差的情況下，Queue-Mergesort 是 Optimal 的，且 Top-down mergesort 也是。接著在 [The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules](https://www.sciencedirect.com/science/article/pii/S0196677498909865?via%3Dihub) 中提到不同的 mergesort 的比較次數可以寫成 $f_n=f_{\tau(n)}+f_{n-\tau(n)}+g_n$ 的遞迴關係式，其中 $g_n$ 代表合併時所需的比較次數。根據不同的實作可以將 $\tau(n)$ 分成三種
- $\tau(x)=\lfloor{n\over2}\rfloor$：Top-down mergesort
- $\tau(x)=2^{\lceil log_2{n\over2}\rceil}$：Buttom-up mergesort
- $\tau(x)=2^{\lfloor log_2{2n\over3}\rfloor}$：Queue-mergesort
在論文中提到這個 $2^{\lfloor log_22n/3 \rfloor}$ 是一個特別的數字，可以使最差的情況下要合併的兩邊資料長度為 2:1，如果使用其他的數字就可能導致 $f_n$ 在分割時兩邊的差距過大。
> Note that $2^{\lfloor log_22n/3 \rfloor}$ is the unique power of two lying between $n/3$ and $2n/3$ and that the choice of rationals other than $2/3$ will not be more balanced. For example, if $2^{\lfloor log_2n/2 \rfloor}$ or $2^{\lfloor log_25n/9 \rfloor}$ then the sizes of two subproblems are $(2,5)$ for $n = 7$ while the balanced power-of-two gives $(3,4)$
因為 Queue-mergesort 可以表示成 Huffman Tree，因此在 [On the Optimality of Huffman Trees](https://epubs.siam.org/doi/10.1137/0131030) 的內容可以套用至 Queue-mergesort，論文中說明 Huffman Tree 的遞迴關係中的 k 是 $2^{\lfloor log_2{2n\over3}\rfloor}$ 而不是其他數字或 $\lfloor2n/3\rfloor$。
> $$F(n)=1-q^n+\min_{1\le k\le n-1}{F(k)+F(n-k)}$$ Since the function $f(n)=1-q^n$ is concave nondecreasing, the "power of 2" rule applies, and the optimal $k$ is the power of 2 satisfying $$n/3\le k\lt 2n/3$$
最後透過 Geogebra 觀察函式在不同 n 時的數值，下圖中 $f$ 代表 $2^{\lfloor log_22n/3 \rfloor}$，$h$ 與 $g$ 分別代表 $2n/3$ 與 $n/3$。可以看到確實 $f$ 會在 $h$ 與 $g$ 之間。這讓 mergesort 在合併兩個鏈結串列時可以維持在最差長度為 2:1 的情況。
不過論文中很多部分還不能理解，例如為什麼 Buttom-up mergesort 的數值是 $2^{\lceil log_2{n\over2}\rceil}$。還有許多推倒的過程不太能理解，只能記住結論而已。
###
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
Sign in with Wallet
Connect another wallet