# 2025q1 Homework1 (lab0)
contributed by <`Huadesuwa`>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ uname -a
Linux hua-GV72-8RD 6.11.0-17-generic #17~24.04.2-Ubuntu SMP PREEMPT_DYNAMIC Mon Jan 20 22:48:29 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ 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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU(s) scaling MHz: 33%
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
```
## 指定的佇列操作
### q_new
> commit： [5e8635d](https://github.com/Huadesuwa/lab0-c/commit/5e8635d056c6d245c8ac03f82d54cb9a657ce5c5)
**目的**
提供建立空佇列的統一介面
1. 請求 `head` 大小的記憶體空見(透過 `malloc` )
2. 檢查記憶體配置是否成功，並在失敗時返回 `NULL`
3. 若檢查成功，則使用 `INIT_LIST_HEAD` 初始化 `struct list_head`
> 記錄!：用Graphviz畫個list_head包裹的示意圖
### q_free
> commit： [5e8635d](https://github.com/Huadesuwa/lab0-c/commit/5e8635d056c6d245c8ac03f82d54cb9a657ce5c5)
**目的**
釋放佇列已配置的所有元素 ( `element_t` ) 記憶體空間，釋放的順序依序為字串陣列 ( `value` 指向的地址) 與佇列節點 ( `element_t` ) ，以及佇列 ( `head` )
**`ERROR`**
原先的程式碼只會釋放 ( `head` ) 的記憶體空間，然而 `head` 就 但這是錯誤的，導致執行後仍有尚未釋放的記憶體空間被提醒錯誤：
> `There is no queue, but 4 blocks are still allocated.`
**改進**
> commit： [aad9894](https://github.com/Huadesuwa/lab0-c/commit/aad9894b5ade8199a324f3e13c54c53488220d9e)
使用 Linux 核心 API `list_for_each_safe` 逐步走訪整個鏈結串列，並連帶釋放其記憶體空間:
```diff
+ if (!head)
+ return;
+ if (list_empty(head)) {
+ free(head);
+ return;
+ }
+ element_t *entry, *safe;
+ list_for_each_safe (entry, safe, head, list)
+ q_release_element(entry);
free(head);
```
### q_insert_head & q_insert_tail
> commit： [0a7aebb](https://github.com/Huadesuwa/lab0-c/commit/0a7aebb43b3ca73675249b73b5c5279538bd061c)
**目的**
1. 建立新的佇列元素 ( `element` ) ，將給定的字符串複製至 `value`
2. 將配置並賦值完的元素 ( `element` ) 插入至 `head` 與 `head->next` 之間
3. 若為插入佇列尾巴，則將配置並賦值完的元素插入至 `head` 與 `head->prev` 之間
> 佇列使用的鏈結串列為雙向環狀鏈結串列
**特殊狀況**
* 當透過 `malloc` 申請配置失敗時: 返回false
* 當傳入的佇列是 `NULL` : 返回 `false`
**實作流程**
1. 配置記憶體流程: 配置佇列元素、字元陣列 -> 確保皆有效 -> 將佇列元素的 `value` 指向字元陣列。
2. 配置失敗發生時，要將已配置的記憶體空間釋放。
**`ERROR`**
進行測試時，發現在佇列中新增兩個 `element` 後，當要釋放出去時，產生了錯誤，與記憶體分配有關。
> `ERROR`：Corruption detected in block with address 0x6271a022e290 when attempting to free it.
使用 Valgrind 來進一步調查，問題如下：
```shell
$ make valgrind
# Test of malloc failure on insert_head
==12268== Invalid write of size 1
==12268== at 0x10FE6F: q_insert_head (queue.c:58)
==12268== by 0x10CEDB: queue_insert (qtest.c:234)
==12268== by 0x10D0AC: do_ih (qtest.c:282)
==12268== by 0x10E74D: interpret_cmda (console.c:181)
==12268== by 0x10ED12: interpret_cmd (console.c:201)
==12268== by 0x10EFA1: cmd_select (console.c:593)
==12268== by 0x10F87F: run_console (console.c:673)
==12268== by 0x10DB3C: main (qtest.c:1444)
==12268== Address 0x0 is not stack'd, malloc'd or (recently) free'd
```
問題出現在使用 `malloc` 配置的記憶體空間是錯誤的，依照題目敘述，應當分配的是輸入 `string` 大小的記憶體空間才對。
調整為正確的記憶體分配：
> commit： [7f06702](https://github.com/Huadesuwa/lab0-c/commit/7f067020e7feba5ea79b094e455b04db62a85b7b)
```diff
- char *str_copy = (char *) malloc(sizeof(char));
+ node->value = malloc(strlen(s) + 1);
```
### q_remove_head & q_remove_tail
> commit： [afefac4](https://github.com/Huadesuwa/lab0-c/commit/afefac4142354861ef4e0cfaa72baf695e59123c)
**目的**
1. 移除佇列第一個/最後一個元素，並返回該元素的地址
2. 若使用者給定一有效字元，且 **目的(1)** 已完成，則複製移出的元素值到 `sp` 中，能夠允許的最大長度為 `buffsize - 1` 並確保字串結尾總是 `/0`。
**`ERROR`**
執行 `make test` 發現的錯誤：
```shell=
$ make test
CC queue.o
LD qtest
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
`ERROR`: Removed value gerbil != expected value bear
`ERROR`: Removed value meerkat != expected value gerbil
`ERROR`: Removed value bear != expected value meerkat
--- trace-02-ops 0/6
```
在測試 `Remove` 操作時，發現實際移除的節點與預期要移除的節點不一致。從 `qtest` 可見，`rh` 和 `rt` 命令的後續參數 `str` 是可選的。由此可推斷，錯誤的原因在於 `rh` 命令從佇列頭部移除節點時，結果與預期值不符。
在對 [traces/trace-02-ops.cmd](https://github.com/Huadesuwa/lab0-c/blob/master/traces/trace-02-ops.cmd) 中的命令進行圖形化呈現時，發現執行錯誤的原因是 `delete_middle` 功能尚未實作，導致整段命令無法正常運行。
> 只有正確刪除中間的節點時，第9行後的命令在執行時才會正確
**insert of head & tail**
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 -> node1;
node0 [label="{<prev> | head | <next>}", image="
"];
node1 [label="{<prev> | dolphin | <next>}"];
node2 [label="{<prev> | bear | <next>}"];
node3 [label="{<prev> | gerbil | <next>}"];
node4 [label="{<prev> | meerkat | <next>}"];
node5 [label="{<prev> | bear | <next>}"];
node6 [label="{<prev> | gerbil | <next>}"];
node7 [label="{<prev> | tiger | <next>}"];
node8 [label="{<prev> | head | <next>}"];
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
node5 -> node6;
node6 -> node7;
node7 -> node8;
}
```
**remove tail - tiger**
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 [label="{<prev> | head | <next>}"];
node1 [label="{<prev> | dolphin | <next>}"];
node2 [label="{<prev> | bear | <next>}"];
node3 [label="{<prev> | gerbil | <next>}"];
node4 [label="{<prev> | meerkat | <next>}"];
node5 [label="{<prev> | bear | <next>}"];
node6 [label="{<prev> | gerbil | <next>}"];
node7 [label="{<prev> | head | <next>}"];
node0 -> node1;
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
node5 -> node6;
node6 -> node7;
}
```
**delete mid twice**
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 [label="{<prev> | head | <next>}"];
node1 [label="{<prev> | dolphin | <next>}"];
node2 [label="{<prev> | bear | <next>}"];
node3 [label="{<prev> | gerbil | <next>}"];
node4 [label="{<prev> | bear | <next>}"];
node5 [label="{<prev> | gerbil | <next>}"];
node6 [label="{<prev> | head | <next>}"];
node0 -> node1;
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
node5 -> node6;
}
```
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 [label="{<prev> | head | <next>}"];
node1 [label="{<prev> | dolphin | <next>}"];
node2 [label="{<prev> | bear | <next>}"];
node3 [label="{<prev> | bear | <next>}"];
node4 [label="{<prev> | gerbil | <next>}"];
node5 [label="{<prev> | head | <next>}"];
node0 -> node1;
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
}
```
**insert tail - meerkat**
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 [label="{<prev> | head | <next>}"];
node1 [label="{<prev> | dolphin | <next>}"];
node2 [label="{<prev> | bear | <next>}"];
node3 [label="{<prev> | bear | <next>}"];
node4 [label="{<prev> | gerbil | <next>}"];
node5 [label="{<prev> | meerkat | <next>}"];
node6 [label="{<prev> | head | <next>}"];
node0 -> node1;
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
node5 -> node6;
}
```
**rh dolphin、bear、bear、gerbil、meerkat**
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 [label="{<prev> | head | <next>}"];
node2 [label="{<prev> | bear | <next>}"];
node3 [label="{<prev> | bear | <next>}"];
node4 [label="{<prev> | gerbil | <next>}"];
node5 [label="{<prev> | meerkat | <next>}"];
node6 [label="{<prev> | head | <next>}"];
node0 -> node1;
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
}
```
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 [label="{<prev> | head | <next>}"];
node3 [label="{<prev> | bear | <next>}"];
node4 [label="{<prev> | gerbil | <next>}"];
node5 [label="{<prev> | meerkat | <next>}"];
node6 [label="{<prev> | head | <next>}"];
node0 -> node3;
node3 -> node4;
node4 -> node5;
node5 -> node6;
}
```
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 [label="{<prev> | head | <next>}"];
node4 [label="{<prev> | gerbil | <next>}"];
node5 [label="{<prev> | meerkat | <next>}"];
node6 [label="{<prev> | head | <next>}"];
node0 -> node4;
node4 -> node5;
node5 -> node6;
}
```
```graphviz
digraph DoublyCircularLinkedList {
rankdir=LR;
node [shape=record, fontsize=30, width=3, height=1.5];
node0 [label="{<prev> | head | <next>}"];
node4 [label="{<prev> | gerbil | <next>}"];
node5 [label="{<prev> | meerkat | <next>}"];
node6 [label="{<prev> | head | <next>}"];
node0 -> node4;
node4 -> node5;
node5 -> node6;
}
```
### q_size
> commit： [e3ea447](https://github.com/Huadesuwa/lab0-c/commit/e3ea447c6294078d6c6735b673962f4a724467b0)
**目的**
逐步走訪整個佇列，以統計目前佇列的元素數量
**特殊狀況**
若 `head` 指向 `NULL` : 返回 `0`
**實作流程**
透過 `list_for_each` 逐步走訪整個佇列中的所有元素的，每當其與 `head` 地址不同，就將佇列大小加上 `1` ，直到再次碰見 `head` 。
### q_delete_mid
> commit: [c424903](https://github.com/Huadesuwa/lab0-c/commit/c424903f3e995c2a2e62645a1458b7adbc00448a)
**目的**
刪除(含記憶體)佇列中第$\lfloor n + 1 \rfloor$個元素，以$0^{th}$作為元素的第一個索引。
**特殊狀況**
`head` 是 `NULL` 或空佇列：返回 `false`
**實作流程**
1. 使用快慢指標( `fast` 、 `slow` ) 指向 `head->next` 、 `head->next>next` 作為起點，朝前移動。
2. 當快指標( `fast` )跑完一圈時，慢指標( `slow` )正好會在中間($\lfloor n + 1 \rfloor$)。
> 記錄!：以圖來表達快慢指標的前進方式
### q_delete_dup
> commit: [aeb064c](https://github.com/Huadesuwa/lab0-c/commit/aeb064ca93aea2449ba9445a9d4d0034eb63d273)
**目的**
比較佇列元素與兩側的字串是否重複，如果重複就刪除。
**特殊狀況**
1. 若 `head` 指向 `NULL` 或空佇列: 返回 `false`
2. 當下一個元素的 `list` 就是 `head` : 判斷字串是否重複，會用到下個元素的成員 value 。
**實作流程**
1. `list_for_each_entry_safe` 的停止條件是當當前元素的 `list` 與 `head` 地址相同時。
2. 若目前元素的字串和下個元素的字串相同，則先移出當前元素，並釋放其記憶體。
3. 同時記住當前元素是否已經是重複元素，若是，則移動至下一個元素前要先刪除該元素。
```c
list_for_each_entry_safe (entry, safe, head, list) {
bool cur = (&safe->list != head && !strcmp(entry->value, safe->value));
// head -> A -> A -> A -> B -> C -> ... -> head
// head -> A(entry, last) -> A -> B -> C -> ... -> head
// head -> A -> B -> C -> ... -> head
if (cur || last) {
list_del(&entry->list);
q_release_element(entry);
last = cur;
}
}
```
### q_swap
> commit: [dbd0b19](https://github.com/Huadesuwa/lab0-c/commit/dbd0b19206be4ec780386351dfff8bb043e7653b)
**目的:**
以兩個元素為一組交換位置，完成後換下一組，直到下一個元素是未成對節點或是佇列的 `head`。
**特殊狀況:**
`head` 指向 `NULL` 、空佇列或 `singular` 時: 直接返回。
**實作流程:**
`list_for_each_entry_safe` 的停止條件是當當前元素的 `list` 與 `head` 地址相同時。
1. 檢查當前節點指向的下一節點( `safe` )的地址不是 head，否則結束。
2. 將當前節點指向的下一節點( `safe` )，移到當前節點的前方 `each->prev`
3. 此時佇列的順序為 `safe -> each -> ...`
4. 接著將 `safe` 指向 `each` 後面繼續下一循環
```c
// head(each->prev) -> each -> safe -> ... -> head
// head -> safe -> each -> ... -> head
list_head *each, *safe;
list_for_each_safe (each, safe, head) {
if (safe != head) {
list_move(safe, each->prev);
safe = each->next;
}
}
```
### q_reverse
> commit： [5d1a49f](5d1a49f5f75827ff9b15e6ddd0bbdb2ebc51946e)
**目的:**
反轉佇列內所有元素的順序。
**特殊狀況:**
若 `head` 是 `NULL`，或元素數量是 `0` 或者 `1`: 直接返回。
**實作流程:**
我們知道只要最後一個元素的 `list` 地址 ( `tail` )，就能通過 `list_for_each_safe` 重複將節點移動到 `tail` 的下一個元素就好了。
```c
// head -> A -> B -> ... -> Z(tail) -> head
// head -> Z(tail) <- ... <- B <- A <- head
const struct list_head *tail = head->prev;
for (each = head->prev, safe = each->prev; each != head;
each = safe, safe = each->prev) {
if (each == tail)
continue;
list_move_tail(each, head);
}
```
### q_reverseK
> commit: [e932a9a](https://github.com/Huadesuwa/lab0-c/commit/e932a9a79371f1b4d0bbef1cf3a5f533df3afc50)
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
int turn = q_size(head) / k;
list_head *front = head->next->next;
list_head *last = head->next;
for (size_t i = 0; i < turn; i++) {
list_head *ll = last->prev;
// Head -> A(last) -> B(front) -> C -> D -> E -> F -> Head
// Head <- B(front) <- A(last) <- Head
for (size_t j = 0; j < k; j++) {
last->next = last->prev;
last->prev = front;
front = front->next;
last = last->prev;
}
list_head *ff = last;
last = ll->next;
front = ff->prev;
last->next = ff;
ff->prev = last;
front->prev = ll;
ll->next = front;
last = ff;
front = ff->next;
}
}
```
### q_ascend
> commit: [1f0dbff](https://github.com/Huadesuwa/lab0-c/commit/1f0dbffc08545af065ce4524ccbca3da5ccc6016)
**目的**
透過刪除佇列中的元素達到升冪排列，並釋放被刪除節點所配置的記憶體空間。
**特殊狀況**
1. 前一個元素須嚴格小於後面所有的元素，以符合題幹:
> has a node with a strictly less value anywhere to the right side of it.
表示要有嚴格小於當前元素的值才需刪除當前節點。換句話說，若右邊的值與當前值相同，不用刪除。
2. 若 `head` 指向 `NULL` 或空佇列，直接返回 `0` ;若是單一元素佇列返回 `1` 。
**實作流程**
1. 根據++特殊狀況(1)++，透過 `list_for_each_entry_safe ` 來逐步走訪整個佇列
2. 若當前節點( `each` ) 大於下一個節點( `safe` ) 就刪除 `safe` 。
```c
element_t *each, *safe;
list_for_each_entry_safe (each, safe, head, list) {
count++;
if (&safe->list != head && strcmp(each->value, safe->value) > 0) {
list_move(&safe->list, pending);
safe = each;
count--;
}
}
q_free(pending);
```
### q_descend
> commit: [1f0dbff](https://github.com/Huadesuwa/lab0-c/commit/1f0dbffc08545af065ce4524ccbca3da5ccc6016)
**目的:**
要求前一個元素不可++小於++後面任一元素
**特殊狀況:**
若 `head` 指向 `NULL` 或空佇列，直接返回 `0` ;若是單一元素佇列返回 `1` 。
**實作流程:**
根據++目的++，我們應該從佇列的尾巴( `prev` )開始，於迴圈中逐步向前搜尋。當目前節點( `prev` )的值大於下一節點( `prev->prev` )，則移除 `prev->prev` 。
1. 初始化 `prev` 為佇列的尾巴，以及 `pending` 用來保存即將被刪除的節點。
2. 迴圈的中止條件為下一節點( `prev->prev` )不是 `head`
3. 若下一節點( `prev->prev` )不是 `head` ，則透過 `strcmp` 比較其與目前節點( `prev` )大小
4. 當下一節點( `prev->prev` )小於目前節點( `prev` )，就將其移至 `pending` 並刪除；否則繼續向前移動。
```c
if (strcmp(list_entry(prev, element_t, list)->value,
list_entry(prev->prev, element_t, list)->value) > 0) {
pending = prev->prev;
list_del(pending);
element_t *str = list_entry(pending, element_t, list);
q_release_element(str);
} else {
prev = prev->prev;
}
```
### q_merge_two
> commit: [a19e22a](https://github.com/Huadesuwa/lab0-c/commit/a19e22a0131c567697b28617d6313c13af07d8dc)
**目的**
該函式是 `q_sort` 與 `q_merge` 的輔助函式，專注於合併兩個佇列，並確保返回時，是第一個佇列擁有所有元素。
**特殊狀況**
在 `qtest.c` 中可以看到在合併佇列時，需要注意排序的穩定性：
> ERROR: Not stable sort. The duplicate strings \"%s\ are not in the same order.
**實作流程**
1. 不允許heap allocation
* 檢查要合併的兩個佇列是否為 `NULL` 或空佇列
* 如果其中一個是或者皆是，則直接返回，並回傳佇列大小
```c
if (!ll1 || !ll2)
return q_size(ll1 ? ll1 : ll2);
// {ll1, ll2} = 2'b00, 2'b01, 2'b10
if (list_empty(ll1) || list_empty(ll2)) {
if (list_empty(ll1))
list_splice(ll2, ll1);
return q_size(ll1);
}
```
2. 透過 `for` 迴圈取得要合併的佇列元素，停止條件為當任一佇列為空時。
* `descend` 判斷合併後佇列以++升冪++還是++降冪++排列
* 根據++特殊狀況++使用三元條件運算子，判斷 `strcmp` 比較兩佇列內的元素結果:
* 首先，判斷是否為 `0` ，若兩佇列元素相等，則維持其輸入結果
* 其次，判斷 `descend` ，決定++升冪++或++降冪++排列
```c
element_t *entry = list_first_entry(ll1, element_t, list);
element_t *safe = list_first_entry(ll2, element_t, list);
int cmp = strcmp(entry->value, safe->value);
element_t *next = !cmp ? entry
: (descend ? (cmp > 0 ? entry : safe)
: (cmp > 0 ? safe : entry));
list_move_tail(&next->list, &dummy);
```
### q_sort
> commit: [a19e22a](https://github.com/Huadesuwa/lab0-c/commit/a19e22a0131c567697b28617d6313c13af07d8dc)
**目的**
排序給定佇列，順序依照 `descend` 的值決定。
**特殊狀況**
1. 時間複雜度須在 $O(n \log n)$ 級別以通過 `100, 000` 個元素的測試。
2. 若 `head` 指向 `NULL`、空佇列、或 `singular` : 直接返回。
3. 為了穩定性而使用merge sort
**實作流程**
由於已經實作了 `q_merge_two` 用來合併兩個佇列。我們能基於此函式實作 merge sort
流程如下:
1. 使用快慢指標方式找到佇列的中間節點，並以 `list_cut_position` 將佇列的一半切給 `left`
2. `right` 則以 `list_splice_init` 獲取佇列剩餘的一半，並以 `INIT_LIST_HEAD` 初始化 `head`
3. 接著，透過遞迴將佇列的節點逐一切分成 `singular` ，此時會觸發++特殊狀況(2)++ 返回
4. 使用 `q_merge_two` 函式合併兩個佇列(`left` 、 `right`) ，並以 `descend` 決定最終排列方式
5. 最後，將`left` 合併移至 `head` 裡，並返回
### q_merge
> commit: [a19e22a](https://github.com/Huadesuwa/lab0-c/commit/a19e22a0131c567697b28617d6313c13af07d8dc)
**目的**
將 `head` 所指向的佇列鏈 (queue chain) 中所有的佇列，按給定的規則 (升/降冪) 合併至該佇列鏈的第一個佇列中。佇列鏈中所有元素都被++保證++是依給定的規則排列。
**特殊狀況**
1. 若佇列鏈中佇列個數 ( q_contex_t 實例個數) 為 1，則直接返回該佇列的元素個數。
2. 若 `head` 指向的是 `NULL` 或空佇列: 直接返回 0。
3. 需統計合併完後的總元素數量，並返回。
```c
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return q_size(list_first_entry(head, queue_contex_t, chain)->q);
```
**實作流程**
`q_merge` 可以使用 `q_merge_two` 函式將兩佇列給合併。
```c
list_head *first = head->next;
queue_contex_t *first_q = list_entry(first, queue_contex_t, chain);
for (list_head *next = first->next; next != head; next = next->next) {
queue_contex_t *next_q = list_entry(next, queue_contex_t, chain);
count = q_merge_two(first_q->q, next_q->q, descend);
}
```
## 新增 shuffle 命令與 prng 選項
在本節中，預計達成以下目標:
* 新增 `shuffle` 命令，使當前佇列進行洗牌。
* 新增 `prng` 選項，讓使用 `ih RAND xx` 時，使用者可選擇調用預設的 syscall
* 或是分析不同 `PRNG` 對 `ih RAND` 指令的影響，指標可使用香農熵 (Shannon entropy) 評估。
以下先探討 lab0-c 如何新增命令，接著探討 Fisher–Yates shuffle 和 PRNG，並了解目前 lab0-c 預設的隨機字串是如何產生的。了解後研討如何設計相關介面來達成上述目標，最終透過香農熵輔以其他統計手段分析結果與差異性。
### 如何在 lab0-c 增加新的命令?
在 `console.h` 中，提供了 `ADD_COMMAND` 巨集用於新增命令，並對應至 `add_cmd` 函式，其宣告如下：
```c
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
關鍵在於 `operation` ，透過連接運算子 `##` 會自動展開為 `do_<cmd>` 。因此，一旦事先提供 `do_*` 函式，並在 `console_init` 中呼叫 `add_cmd("<instruction>", <do_*>, "<documentation>")` ，即可增加新命令！
`cmd_func_t` 的定義是:
```c
typedef bool (*cmd_func_t)(int argc, char *argv[]);
```
命令的解析與執行由 `interpret_cmd` 負責，其中實際調用 `do_*` 的部分則由 `interpret_cmda` 處理。 `interpret_cmda` 會在 `cmd_list` 鏈結串列中搜尋對應的命令並執行。
### Fisher–Yates shuffle
Fisher-Yates 演算法最初於 1938 年提出，並在 1964 年針對計算機應用進行改良。隨後，它以 Algorithm P 的形式收錄於《 [The Art of Computer Programming](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming) 》。該演算法的設計目標是確保所有排列結果的機率均勻且一致。
以長度為 `n` 的陣列 `a` 為例，演算法步驟如下：
1. 初始化變數 `i = n - 1`，並隨機產生索引 `j`，範圍介於 `0` 到 `i` 之間，作為交換對象。
2. 交換 `a[i]` 和 `a[j]`，將選出的元素 `a[i]` 移至陣列尾端。
3. 將 `i--`，然後重複步驟 1，直至 `i < 0` 為止。
需要注意的是，Wiki 中的範例是以陣列為例進行說明。然而，在鏈結串列中，訪問第 `n` 個節點的時間複雜度為 $O(n)$ ，而陣列僅為 $O(1)$ 。因此，基於鏈結串列的洗牌演算法，其時間複雜度為 $O(n^2)$ 級別。
### [從大數法則理解訊息熵 (Entropy) 的數學意義](https://hackmd.io/@8dSak6oVTweMeAe9fXWCPA/ryoegPgw_#%E5%8F%83%E8%80%83%E8%B3%87%E6%96%99)
熵可以這樣解釋：對於某個在 $1$ 附近的下界 $1-\epsilon$，我們都可以找到一個 **$\epsilon$-high-probability set**，這是一個字元集 $S^n$ 的子集，使得在 $S^n$ 中，根據特定機率分佈選取的序列落入該集合的機率大於 $1-\epsilon$。
選擇該集合的方法是基於函數 $ \log∘P$（其中 $\log$ 以 $2$ 為底，而 $P$ 是機率質量函數）。根據 **弱大數法則**，如果一個函數從 $S$ 映射到實數，且對於特定機率分佈的期望值為有限實數，那麼當取樣數量 $n$ 趨近無限時，該函數的樣本平均值會趨近於期望值。
因此，對於任意的 $\delta$，總能找到一個 $n_0$，使得當 $n \geq n_0$ 時，$\log∘P$ 的樣本平均值與 $\mathbb{E}[f(S)]$ 的距離小於 $\delta$ 的機率大於 $1-\epsilon$。
#### 為何使用 $\log∘P$ 來選擇集合？
這是因為 **獨立事件的機率是相乘的**，如果對個別的機率取對數再取平均，則相乘關係轉換為加法，這剛好對應於從字元集 $S$ 取長度為 $n$ 的字串 $s^n$ 出現的機率。
\begin{align}
\mathbb{E}[\log P(s)] - \delta \leq \frac{1}{n} \sum_{i} \log P(s_i) = \frac{1}{n} \log \left(\prod_{i} P(s_i)\right) = \frac{1}{n} \log P(s^n)
\end{align}
#### 變數說明
* $s$：一個從字元集 $S$ 以機率質量函數 $P$ 分佈的隨機變數。
* $P(s_i)$：特定變數 $s_i$ 出現的機率，即 $P(s = s_i)$。
* $P(s^n)$：長度為 $n$ 的字串 $s^n$ 出現的機率。
#### 訊息壓縮與解碼準確性的權衡
當資料表達過度簡化時，可能會導致解碼困難。例如，若將字母 a、b、c 均編碼為 $0$，其餘字母編碼為 $1$，則 "cat" 的編碼結果為 $001$。然而，由於 "bar" 也會得到相同的編碼，解碼器將無法正確區分這兩個單詞，最終導致訊息還原錯誤。
因此，我們可以得出兩點結論：
1. **當訊息呈現某種規則或模式時，資料是可能被壓縮的**。
1. **訊息壓縮的程度與還原準確性之間存在 trade-off，過度壓縮可能會影響解碼的準確性**。
這與熵的概念密切相關——**熵描述的是最優壓縮的極限，而避免過度壓縮則確保了訊息能夠準確還原**。
---
#### 結論
這個證明說明了兩點：
1. **如何選擇 $\epsilon$-high-probability set**：對於 $S^n$ 中的某個元素，如果它的每個字元經過 $ \log∘P$ 處理後的平均值與 $\mathbb{E}[f(s)]$ 的距離小於 $\delta$，則它屬於 $\epsilon$-high-probability set，並且這樣選取的集合確實符合該集合的定義。
2. **熵作為單位資訊量的極限**：
* 從 $S^n$ 中隨機選擇一個字串時，特定字串出現的機率，當 $n$ 足夠大時，會接近 $2^{n \mathbb{E}[\log P(s)]}$。
* 如果假設所有結果的機率相等，則總共有 $2^{-n \mathbb{E}[\log P(s)]}$ 種可能的結果。
* 換句話說，$n$ 個字元總共的資訊量是 $-n \mathbb{E}[\log P(s)]$ 位元，因此 **單個字元的資訊量為**
\begin{align}
\mathbb{E}[\log P(s)] = -\sum_i P(s_i) \log P(s_i)
\end{align}
這 **正是 Shannon entropy 的定義公式**！
#### 直覺解釋
1. **高機率出現的序列占據大部分總機率，因此壓縮時應優先考慮這些序列**。
- 這樣的作法，比起
3. **熵描述的是「資訊的平均不確定性」或「最優壓縮極限」**：
- 如果某個字元的出現機率較為平均（例如公平擲骰子），則熵較高，需要更多位元來表示。
- 如果某些字元明顯比其他字元常見（例如英文文本中的 "e" 出現頻率較高），則熵較低，可以用較少位元來表示常見字元。
4. **大數法則提供了數學基礎，說明當序列長度夠大時，實際樣本的行為會趨近於 Shannon entropy 的理論極限**。
---
### 實作
隨機數產生功能獨立封裝至 `random.[ch]` ，使其與主程式分離。這樣一來，`q_shuffle` 和隨機字串生成函式 `fill_rand_string` 皆可重複使用，減少程式碼冗餘。可選的實作方式目前包含預設方法與 Xorshift。此外，所有隨機數函式的接口應統一為：
```c
typedef int (*rand_func_t)(uint8_t* buf, size_t len);
```
此接口與現有的 randombytes 保持一致（亦相容於 getrandom），提升兼容性，並允許未來擴展以支援不同的 PRNG 選項：
```c
extern int randombytes(uint8_t *buf, size_t len);
const rand_func_t prng_func[] = {&randombytes, &xorshift, ...};
```
> commit: [62b173f](https://github.com/Huadesuwa/lab0-c/commit/62b173f96b0a16341df698c82de72df68729d57f)
**Shuffle**
> commit: [41157a5](https://github.com/Huadesuwa/lab0-c/commit/41157a54b3ac3382ae2d5c14aa74b52471a670a8)
**目的**
對佇列中所有節點進行洗牌 (shuffle) 操作
**實作方法**
以 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modern_method) 演算法完成
同時，為確保 `q_shuffle` 能夠放在 `queue.h`，更新了 `chechsum.sh` 中 `queue.h` 的 `sha1sum`。
**PRNG**
> commit: [62b173f](https://github.com/Huadesuwa/lab0-c/commit/62b173f96b0a16341df698c82de72df68729d57f)
目前可透過 `option prng 1` 設定為 Xorshift，`0` 則為預設模式，使用 `getrandom`。並未修改原程式中的 `randombytes`，因此不受 `prng` 設定影響。該選項僅影響 `fill_rand_string` 和 `q_shuffle` 的行為。
### 統計方式驗證 shuffle
這裡使用範例所提供的 python 程式碼進行實驗，分析 4 個元素進行 shuffle 是否符合 Uniform distribution，也就是分佈是平均的。首先提出須假說：
- $𝐻_0$ （虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
- $𝐻_1$ （對立假說）: shuffle 的結果發生的機率至少有一個不同
此為資料適合度分析，測試資料是否符合某種比例:
1. 先計算 chi-squared test statistic $X^2$
\begin{align}
X^2 = \sum_{i=1}^n {(O_i - E_i)^2 \over E_i}
\end{align}
其中，$𝑂_𝑖$ 表示的是此種結果的實際觀察值， $𝐸_𝑖$ 表示的是在假設的比例上，此種結果數量的期望值。
這裡是做了 1000000 次 shuffle 後，所得到的期望值與卡方值：
```shell
Expectation: 41666
Observation: {'1234': 41741, '1243': 41591, '1324': 41783, '1342': 41839, '1423': 41720, '1432': 41518, '2134': 41748, '2143': 41752, '2314': 41360, '2341': 41598, '2413': 41552, '2431': 41628, '3124': 41767, '3142': 41554, '3214': 41992, '3241': 41523, '3412': 41662, '3421': 41653, '4123': 41858, '4132': 41443, '4213': 41813, '4231': 41579, '4312': 41436, '4321': 41890}
chi square sum: 13.80046080737292
```
總共有 $4!$ 種結果，可以發現 $41666$ $實際上就是 $\lfloor \frac{1000000}{4!} \rfloor$ 。
對於 $N$ 個隨機樣本，自由度為 $N - 1$。在隨機排列 4 個數字時，共有 $4!$ 種排列方式，因此自由度為 23。以顯著水準 0.05 查表可得 $\chi^2_{23, 0.05} = 35.1725$，而 $13.8005 < 35.1725$，所以不拒絕虛無假說 $H_0$
從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的。
## 閱讀 〈 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 〉
為了防範 Timing Attack，必須測試程式對不同輸入的執行時間穩定性，以避免資訊透過執行時間洩漏。傳統的分析方式通常需要對硬體建模，然而這並不容易。因此，本文提出了一種基於洩漏測試與統計分析的方法，以評估執行時間的穩定性。
1. **定義 Fix 與 Random 類別**
- **Fix**：一種極端特例，輸入固定不變。
- **Random**：輸入為隨機值，每次測量皆不同。
2. **時間測量與預處理**
- 測量執行時間，並去除受外部因素中斷或執行時間過長的數據。
- 使用 **higher-order pre-processing** 技術提高數據的次方數，使其非線性化。
3. **去除異常數據**
- 依據某個百分位數 $p$ 去除右尾的數據，以減少外部因素（如背景程序）對結果的影響。
- 使用不同的 $p$ 值進行測試，以評估結果的穩健性。
4. **統計**
- **虛無假設 $H_0$**: 兩組數據的分佈相同，執行時間無資訊洩漏。
- **對立假設 $H_1$**: 兩組數據的分佈不同，存在潛在資訊洩漏。
- 由於兩組數據為獨立樣本，且僅知道樣本標準差，因此使用 **t-test** 進行檢定。
這種方法透過統計分析來評估 Timing Attack 風險，避免繁瑣的硬體建模，並提供更直觀的評估方式。
### 程式碼分析
在 `trace-17-complexity` 中，首先輸入 `option simulation 1`，啟用該選項後，即可使用 GDB 進行動態分析。在 `simulation 1` 模式下，設置斷點於 `interpret_cmda`，並執行 `it` 命令。
```shell
(gdb) break console.c:204
Breakpoint 1 at 0x6ae2: file console.c, line 205.
(gdb) run
cmd> option simulation 1
(gdb) continue
Continuing.
cmd> it
214 ok = next_cmd->operation(argc, argv);
```
程式會持續執行，直到執行 `next_cmd->operation`，接著依序執行 `do_it` 和 `queue_insert`。在 `simulation 1` 模式下，會呼叫 `is_insert_tail_const`，
> 顯然，`is_insert_tail_const` 的目的即在驗證 `q_insert_tail` 的執行時間是否為 $O(1)$。
在裡面會去呼叫 `test_const`，第一個參數是 `"insert_tail"` 字串，第二個參數是 `1`
```shell
► 0x57fdbab0a13b <is_insert_tail_const+20> call test_const <test_const>
rdi: 0x57fdbab0d725 ◂— 'insert_tail'
rsi: 1
```
在 `constrant.h` 中，定義了:
```c
#define DUT_FUNCS \
_(insert_head) \
_(insert_tail) \
_(remove_head) \
_(remove_tail)
#define DUT(x) DUT_##x
enum {
#define _(x) DUT(x),
DUT_FUNCS
#undef _
};
```
在 `fixture.c` 中定義了：
```c
#define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) { return test_const(#op, DUT(op)); }
#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _
```
展開後等同於:
```c
bool is_insert_head_const(void) { return test_const("insert_head", 0); }
bool is_insert_tail_const(void) { return test_const("insert_tail", 1); }
bool is_remove_head_const(void) { return test_const("remove_head", 2); }
bool is_remove_tail_const(void) { return test_const("remove_tail", 3); }
```
接下來是 `doit` 中呼叫的函式：
* `measure`：執行程式，測量開始與結束時間
* `differentiate`：計算執行時間
* `update_statistics`：更新各類別資料
* `report`: 進行統計
這裡來看看拿來統計的函數 `t_push` 和 `t_compute` 是怎麼計算的。
首先是 `t_push`，這個平均數更新的方式實際上就是將每個變數減掉原本的平均數後，做平均，再把舊的平均數加回來，這樣的好處是原本的數在計算時能變 0：
\begin{align}
\overline{X}_{new}=\overline{X}_{old} + \frac{0\times n_{old} + (x-\overline{X}_{old})}{n_{new}}
\end{align}
```c
double delta = x - ctx->mean[clazz];
ctx->mean[clazz] = ctx->mean[clazz] + delta / ctx->n[clazz];
ctx->m2[clazz] = ctx->m2[clazz] + delta * (x - ctx->mean[clazz]);
```
> 而 m2 指的就是離均差平方和 $S_{XX}$
然後是 t_compute，可以發現，t 值是$\frac{\overline{X_1}-\overline{X_2}}{\sqrt{\frac{S_1^2}{n_1} + \frac{S_2^2}{n_2}}}$
```c
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
```
### make test
最終結果： 通過 trace-01-ops ~ trace-16-perf ，未通過 trace-17-complexity，得分： 95/100 ([回歸測試結果](https://github.com/Huadesuwa/lab0-c/actions/runs/13737971706/job/38423902017))。
在 3/18 的課堂問答中，老師與 `BennyWang1007` 討論了本文及其程式碼，並提及在原先 `lab0` 專案的實作中，函式 `percentiles` 已被移除。
檢視 `update_statistics` 時可以發現，`lab0` 中的 `update_statistics` 並未執行 `crop` 和 `second-order test`，但在 `GitHub` 上的專案中卻包含了這些步驟。此外，`ttest_ctxs` 在 `GitHub` 專案中包含多組資料，包括：
1. **未經任何預處理的數據**
2. **經過 `crop` 預處理的數據（共 `DUDECT_NUMBER_PERCENTILES` 組）**
3. **完成 `second-order test` 的數據**
根據作業提示：
> 注意：現有實作存在若干致命缺陷，請討論並提出解決方案。
> 在 `oreparaz/dudect` 的程式碼中具備 `percentile` 處理，但在 `lab0-c` 中則無。當你改進後，可提交 `pull request`，並務必提供對應的數學分析。
### 原始實作的問題
最初的實作將所有測量數據納入統計，但由於中斷（interrupt）、分頁錯誤（page fault）、I/O 延遲、CPU 排程等因素，可能會出現異常值，導致錯誤判定，使程式看起來不像常數時間（constant-time）實作。
### 改進方式
為解決此問題，在測量初始化時新增了一個 `percentiles[NUM_PERCENTILES]` 陣列，用於儲存應捨棄的百分位數。隨著測量進行，我們應逐漸減少捨棄的數據，因此使用以下公式來判定是否納入統計：
\begin{align}
\text{threshold}(x) = 1 - \left( 0.5 \right)^{\frac{10 \cdot x}{NUM\_PERCENTILES}}
\end{align}
其中，`NUM_PERCENTILES` 設為 100，得到以下曲線：
> 來源: [2025-03-18 問答簡記](https://hackmd.io/EFs_Nfs6TOmIA5ldA_tZsQ#BennyWang1007)
**同樣地，我注意到 [`rota1001`](https://hackmd.io/@rota1001/linux2025-homework1#%E7%A8%8B%E5%BC%8F%E7%A2%BA%E6%94%B9%E5%96%84) 和 [`weiso131`](https://hackmd.io/@weiso131/linux2025-homework1#q_insert_headq_insert_tail-%E9%9D%9E%E5%B8%B8%E6%95%B8%E6%99%82%E9%96%93%E5%95%8F%E9%A1%8C) 也進行了相關實驗與討論。
從結果來看，可以推斷 **CPU cycle 較長的部分，其比例差異主要來自環境因素**（如中斷（interrupt）、分頁錯誤（page fault）、I/O 延遲、CPU 排程等）。此外，由於兩者在 **CPU cycle 較短的部分呈現明顯相似的分佈**，因此我們可以透過 **排除某個百分位數以上的數據來進行比較**。
然而，若依照文中的方法，較大的差異將導致更高的 **t 值**，最終選取的 **t 值** 會對應到較高的 **p 值**，使得 **右尾數據保留較多**。因此，我選擇 **取 50 百分位數作為閾值**。在此情境下，即便是 `do_nothing` 也開始出現分叉，顯示 **環境因素已經對執行時間產生影響**。
由此可見，**對異常值進行過濾是相當必要的**。此外，藉由這次測試，我也成功獲得了一隻卡比。
## Linux 核心的鏈結串列排序
首先，我們來理解 Linux 中的 `list_sort` 是怎麼做的:
### 操作流程
陣列 `pending` 一開始是空的，每次 `count+1`，即每新增一個元素時，$count$ 會遞增。當 $count$ 遞增至 $2^k$ 時，對應的位元會從 0 變為 1。然而，只有在 **第一次** 遞增到 $2^k$ 時，我們不進行合併，而是等待更多元素的加入。
隨著 $count$ 進一步增長，當它達到 **$3 \times 2^k$** 時，代表目前有 **三個大小為 $2^k$ 的子列表**。此時，我們合併前兩個 $2^k$ 的子列表，使其成為一個大小為 $2^{k+1}$ 的子列表，而 **第三個 $2^k$ 的子列表則保持不變**。
這樣的機制確保了合併與不合併始終維持 **2:1 的比例**，又可以避免 cache thrashing 的風險。以下舉例子：
| $count$ 變化 | $count$ 二進位 | merge | pending 上的節點 |
| --- | --- | --- | --- |
| 0 $\to$ 1 | 0000 $\to$ 0001 | no（$2^0$） | 1 |
| 1 $\to$ 2 | 0001 $\to$ 0010 | no（$2^1$） | 1 $\gets$ 1 |
| 2 $\to$ 3 | 0010 $\to$ 001==1== | yes | (2) $\gets$ 1 |
| 3 $\to$ 4 | 0011 $\to$ 0100 | no（$2^2$） | 2 $\gets$ 1 $\gets$ 1 |
| 4 $\to$ 5 | 0100 $\to$ 010==1== | yes | 2 $\gets$ (2) $\gets$ 1 |
| 5 $\to$ 6 | 0101 $\to$ 01==1==0 | yes | (4) $\gets$ 1 $\gets$ 1 |
| 6 $\to$ 7 | 0110 $\to$ 011==1== | yes | 4 $\gets$ (2) $\gets$ 1 |
如何快速確認當前應該合併的元素？我們可以利用**二進位的特性**，將合併策略轉換為以下規則，假設 $count$ 代表當前陣列數字的總和，給定一個合併前的陣列與 $count$，我們遵循以下步驟：
1. **檢查 $count$ 是否為 2 的冪次**
- 若 **count** 為 $2^k$，則不進行合併。
2. **否則檢查 $count$ 的 lowbit（最低位的 1）是否為 $2^k$**
- 若 **lowbit** = $2^k$，則合併兩個 $2^k$，形成 $2^{k+1}$。
以下以範例說明上述合併策略：
| $count$ | 合併前 | 合併後 | 解釋 |
| --- | --- | --- | --- |
| 1 | 1 | 1 | $cou𝑛t=2^0$ ，所以不合併 |
| 2 | 1, 1 | 1 $\gets$ 1 | $count=2^1$ ，所以不合併 |
| 3 | 1, 1, 1 | (2) $\gets$ 1 | $count$ 的 lowbit 是 $2^0$ ，所以合併兩個 $2^0$ 為 $2^1$ |
| 4 | 2, 1, 1 | 2 $\gets$ 1 $\gets$ 1 | $count=2^2$ ，所以不合併 |
| 5 | 2, 1, 1, 1 | 2 $\gets$ (2) $\gets$ 1 | $count$ 的 lowbit 是 $2^0$ ，所以合併兩個 $2^0$ 為 $2^1$ |
| 6 | 2, 2, 1, 1 | (4) $\gets$ 1 $\gets$ 1 | $count$ 的 lowbit 是 $2^1$ ，所以合併兩個 $2^1$ 為 $2^0$ |
從 [rota001](https://hackmd.io/@rota1001/linux2025-homework1#%E6%93%8D%E4%BD%9C%E6%B5%81%E7%A8%8B) 獲得更深的啟發，整理如下:
### 針對不同 lowbit 情況的分析
#### 當第 $0$ 位元（lowbit = $2^0$）為 $1$ 時
這種情況相對簡單，因為此時 $count$ 必定是奇數。此外，只要有 3 個或以上的 $1$ ，它們就會在之前的步驟中被合併，因此不會出現 5 個或以上的 $1$ 。
每次合併兩個 $1$ 會產生一個 $2$，因此當額外獲得一個 $1$ 時，除非從未合併過 $2$ ，否則必然會出現**恰好 3 個 $1$** 的情況。
- 若 **未曾合併過 $2^1$**，且第 0 位為 $1$，則可能的數值有：
- $count$ $= 1$，這是 2 的冪次，無須合併。
- $count$ $= 3$，這裡明顯包含 3 個 $1$。
因此，**當 lowbit = $2^0$ 時，若 $count \neq 1$，則可將兩個 $2^0$ 合併為 $2^1$**。
#### 當 lowbit = $2^k$（ $k > 0$ ）時
假設 **所有低於 $2^k$ 的狀況均正確**，我們考慮第一次出現 **lowbit = $2^k$** 的情況：
- 當 $count$ $= 2^k$ 時，陣列內有一個 $1$ 和一些小於 $2^k$ 的數字，因此 **無法對 $2^k$ 進行合併**。
- 若 $count$不是 2 的冪次，且 lowbit 為 $2^k$，則上一次的 lowbit 必然是 $2^{k-1}$。
- 但 $count$ 在這種情況下，不可能正好等於 $2^{k-1}$，它必定是 $2^k + 2^{k-1}$ 或之後的數字，所以必定會**合併出一個 $2^k$**。
#### 狀態循環與合併過程
我們可以透過二進位觀察 $2^k$ 這個數的合併過程。由於高位不影響合併邏輯，因此用 `Y` 來表示不重要的部分，而 `X` 代表一個長度為 `k-1` 的全 0 序列。
| 狀態 | lowbit | 說明 |
|------------|--------|-------------------------|
| `Y10X` | $2^k$ | 第一次出現 lowbit 為 $2^k$，代表 $count$ $= 2^k$，無須合併。 |
| `Y11X` | $2^{k+1}$ | 兩個 $2^{k-1}$ 合併為 $2^k$，此時有一個 $2^k$。 |
| `Y01X` | $2^{k+1}$ | 由於 $2^{k-1}$ 進位，$2^k$ 也跟著進位，此時又會合併出一個 $2^k$。 |
| `Y10X` | $2^k$ | 此時存在兩個 $2^k$，可合併為 $2^{k+1}$。 |
| `Y11X` | $2^{k+1}$ | 等同於狀態 2。 |
從這個分析可以得出結論：**對於所有非 2 的冪次且 lowbit = $2^k$ 的 $n$，它們都會進入狀態 4，意謂著都可合併兩個 $2^k$ 為 $2^{k+1}$。**
### 實作方式
#### list_sort
```c
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
- priv: 從 `merge` 函式可以看到 priv 會被當作 `cmp` 的參數傳入，在其他地方不會用到。
- head: 傳入指向 `struct list_head` 的指標
- cmp: compare function ，以 function pointer 的型別傳入
這樣做考慮到通用性，但會增加 function call 的成本
程式的第一步是將 list 指向 `head` 的第一個節點，並將 `pending` 設為 `NULL`。隨後檢查：
* 如果鏈結串列為空或是只有一個元素，則直接返回，無需排序。
* 否則，將雙向 linked-list 變成單向。
這個程式最巧妙的一點是:
> 它利用了雙向鏈結串列在變成單向鏈結串列使用時沒用到的 `prev`，將它變成另一個維度的鏈節串列的 `next`，並且將一大堆鏈結串列連起來。
```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);
```
在 **count** 尚未更新前，從最低位開始尋找第一個 **不是 1** 的位元，這個位元代表當 **count++** 之後的 **lowbit**。同時，**tail** 也會隨之移動。
### tail 的角色與 pending 鏈結串列
`tail` 是一個 **間接指標**，它最初指向 `pending`。
在 `pending` 中，儲存的是在做這次插入之前，所有已經被插入的 linked-list，並且按照 **數量由小到大** 排列。
假設 **count = 5**，那麼 **pending** 可能會包含以下鏈結串列：
\begin{align}
1 \rightarrow 2 \rightarrow 2
\end{align}
因為 `pending` 最初指向的是這個鏈結串列的第 **0 個元素**。
> 這裡我們約定使用 **0-index**
### lowbit 與 tail 的移動
如果 `count++` 之後的 **lowbit** 為 $2^0$（即 1）且 **不是 2 的冪次** 時：
- **tail 不會移動**（即移動 0 步）。
- 在這種情況下，`*tail` 和 `(*tail)->prev` 剛好指向要合併的兩個元素。
當 `count++` 之後的 **lowbit** 為 $2^k$，其中 $k > 0$ 時：
- 這代表 **只有一個 1**，且在低於$k$ 的所有位元位置上，每個值都只有 **1 個**（這一點已經在前述證明中說明過）。
- **tail 會移動 k 步**，此時 `*tail` 和 `(*tail)->prev` 也剛好指向要合併的兩個元素。
### 合併與鏈結更新
- 當找到要合併的兩個元素後，將它們合併。
- 接著，將合併後的結果 **重新插入**，並接在 **tail** 的前面，以維持鏈結串列的正確順序。
這個過程確保了新的插入元素可以按照規則正確地排列，從而保持整體結構的有序性。
```c
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
```
最後，將在 pending 裡面的東西全部接起來，然後把雙向鏈結串列的性質重新維護好
### 效能比較
#### 比較原本的 top-down 實作與模仿 list_sort 的實作
由於差距明顯，不使用 t-test 去檢定平均是否不同
在作業說明中有提到， top-down mergesort 雖然會需要遞迴或額外的記憶體做 user stack，但它有最少的 average case、worst case 的 comparison 次數
而 list_sort 的實作屬於 Bottom-up mergesort，有著各種變形中最多的比較次數
#### merge 使用 linux 核心的實作
`merge_final` 的作法是在合併的同時維護 `prev`，並使用 `tail` 來儲存最後一個被維護的節點。最終，`prev` 會從 `tail` 開始向後維護。
相比於**合併後額外執行一次來還原 `prev` 鏈結串列**的方法，這樣的作法能夠減少對節點的重新存取次數。在鍊結串列較長的情況下，若等到合併完成後才重新存取節點來維護 `prev`，可能會因為**節點資料已經被驅逐出快取**，導致**cache miss**，進而影響效能。
透過 `perf` 工具，可以觀察該方法在減少 cache miss 方面的影響，進一步評估其效能優勢。
Sign in with Wallet
Connect another wallet