# 2024q1 Homework1 (lab0)
contributed by < [wu81177](https://github.com/wu81177/lab0-c) >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
CPU family: 6
Model: 140
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 1
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 5606.40
```
## 指定的佇列操作
### `q_new`
實作 `q_new` 過程中，我學習到 `list.h` 中 `list_head` 和 `INIT_LIST_HEAD` 的部份
#### `LIST_HEAD`
從結構成員可以發現 `list_head` 組成的佇列是雙向佇列，同時我也理解到 `list_head` 除了獨立當作佇列的頭，也會嵌入佇列成員結構體中，佇列成員在這份作業中為 `element_t`
#### `INIT_LIST_HEAD`
此<s>函數</s> 函式是用來初始化已存在的 `list_head` ，如果要同時宣告並初始化可用 `LIST_HEAD（）`
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
### q_free
`list_for_each_safe` 和 `list_for_each_entry_safe` 都能確保釋放當前節點不會遺失下一個節點，然而後者有使用 `list_entry` ，選用它就能輕鬆獲得元素的指標並釋放成員
迴圈中使用 `q_release_element` 來釋放空間，最後再釋放 head
:::danger
改進你的漢語表達。
:::
而在運行 `q_test` 的時候發現有問題因此使用 Valgrind 檢查，以下為檢察結果 :
```
ERROR: Attempted to free unallocated block. Address = 0x4b8e850
==31792== Invalid read of size 8
==31792== at 0x10F43C: find_header (harness.c:98)
==31792== by 0x10F43C: test_free (harness.c:181)
==31792== by 0x10F72E: q_release_element (queue.h:120)
==31792== by 0x10F72E: q_free (queue.c:30)
...
```
發現少檢查 head 為空的情況
```diff
void q_free(struct list_head *head)
{
+ if (!head)
+ return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list)
q_release_element(entry);
free(head);
}
```
### q_insert_head & q_insert_tail
原先 `value` 是直接使用 `s` 的空間，後來參考別人的發現應該使用 `strdup` ，因為 `s` 可能會被改動
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
- e->value = s;
+ e->value = strdup(s);
list_add(&e->list, head);
return true;
}
```
使用 `list_add` 可以將新元素放置在 head 後面， `list_add_tail` 則可以放到 head 前面
發現應該要檢查 `strdup` 是否成功，如果失敗應該要釋放當前元素，如下
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
+ if(!e->value){
+ free(e);
+ return false;
+ }
list_add(&e->list, head);
return true;
}
```
### q_remove_head & q_remove_tail
從 `list.h` 中可以發現 `container_of` 和 `list_entry` 的功能完全相同，我選擇了前者來獲取 `element_t` 的指標
移除元素有 `list_del` 和 `list_del_init` 可用，我選用後者，否則再次使用已移除的元素時可能會出錯
* 發現沒有排除佇列為空的情況，原先的程式在下列第四行會出錯
```diff
- if (!head)
+ if (!head || list_empty(head))
return NULL;
element_t *e = container_of(head->next, element_t, list);
```
### q_size
使用 `list_for_each` 走訪佇列並且計數
### q_delete_mid
我使用的方法是從鏈結串列頭 head 出發，同時使用兩個指標進行走訪，一個指標順行，另一個指標則逆行，直到它們相遇（奇數個元素情況）或者在交會前一步（偶數個元素情況）再刪除順行指標所指向的元素
* 發現使用 `q_release_element` 後再用 `free` 釋放元素內容是多餘的
```diff
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *forward = head->next;
struct list_head *backward = head->prev;
while (forward != backward && forward->next != backward) {
forward = forward->next;
backward = backward->prev;
}
element_t *e = container_of(forward, element_t, list);
list_del(forward);
q_release_element(e);
- free(forward)
return true;
}
```
:::danger
:warning: 留意詞彙的使用：
* [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
* [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
:::
### q_delete_dup
使用兩層迴圈比對，原本都想用 `list_for_each` ，後來發現會重複比對，改成以下這樣
```diff
list_for_each (outer, head) {
- list_for_each(inner, head){
+ for (inner = (outer)->next; inner != (head); inner = inner->next) {
...
}
}
```
發現當沒有元素或單元素應該 return true
```diff
- if (!head || head->prev == head->next) {
+ if (!head)
return false;
+ if (head->prev == head->next)
+ return true;
```
原先的寫法一直無法順利運作
<s>
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || head->prev == head->next) {
return false;
}
struct list_head *outer, *inner, *tmp;
element_t *outer_ele, *inner_ele;
for (outer = (head)->next; outer != (head)->prev; outer = outer->next) {
for (inner = (outer)->next; inner != (head);) {
outer_ele = container_of(outer, element_t, list);
inner_ele = container_of(inner, element_t, list);
if (strcmp(outer_ele->value, inner_ele->value) == 0) {
tmp = inner->next;
list_del(inner);
q_release_element(inner_ele);
inner = tmp;
} else {
inner = inner->next;
}
}
}
return true;
}
</s>
:::danger
明確標注同學的 GitHub 帳號名稱
:::
於是換了寫法，經過<s>同學</s> [kkkkk1109](https://github.com/kkkkk1109/lab0-c) 提醒發現輸入的佇列是已排序的，因此改用他的寫法
:::danger
你的洞見和檢討呢？
:::
原先針對為排序的串列要使用兩層迴圈檢查有沒有重複，但由於輸入串列已排序，相同的鍵值一定會相鄰，因此只需要檢查相鄰的節點，如果和前者相同即刪除，如此一來可以將時間複雜度降低 N 倍
### q_reverse
使用 `list_for_each_safe` 走訪佇列，沿途使用 `list_move` 將元素移至首位，如此一來就能倒轉順序
原先想將 `q_reverse` 視為 `q_reverseK` 的特例，後來覺得在 `q_reverseK` 中呼叫 `q_reverse` 比較好實作
* 多檢查空元素和單元素的情況以提早退出
```diff
- if (!head)
+ if (!head || head->prev == head->next)
return;
```
### q_reverseK
使用 `list_cut_position` 剪下子佇列，用 `q_reverse` 倒序後再用 `list_splice` 接回去
`list_cut_position(head_to, head_from, node)` 剪下的部份並不包含 `head_from` 和 `node` 兩個節點
### q_swap
視為 `q_reverseK` k 為2的特例
### q_ascent
從 head 逆向走訪佇列，如果下一個元素大於當前元素則使用 `list_del` 刪除下個元素，如此一來就能留下遞增元素
學會 `strcmp ()` 怎麼用，此函數會開始比較每一個字串的第一個字元。 如果它們彼此相等，會繼續往下進行配對，直到字元不同或到達較短字串的結尾
### q_descent
從 head 逆向走訪佇列，如果下一個元素小於當前元素則使用 `list_del` 刪除下個元素，如此一來就能留下遞減元素
### q_sort
由於我在 `q_merge` 中會使用這個函式，在使用的前一步它已經是分段排序的佇列，這時候如果用 merge sort 會有不錯的效果，所以我選擇用 merge sort實作之
用來合併兩以排序佇列的函式我定義為 `merge_two` ，在裡面原先判斷是否遞減和兩元素比較大小的部份使用兩層 `if` ，後來改為以下較緊湊的寫法
```diff
while (!list_empty(l1) && !list_empty(l2)) {
element_t *ele_l1 = list_first_entry(l1, element_t, list);
element_t *ele_l2 = list_first_entry(l2, element_t, list);
- if(descend){
- if(strcmp(ele_l1->value, ele_l2->value) < 0)
- list_move_tail(l2->next, &tmp_head);
- else
- list_move_tail(l1->next, &tmp_head);
- } else {
- if(strcmp(ele_l1->value, ele_l2->value) < 0)
- list_move_tail(l1->next, &tmp_head);
- else
- list_move_tail(l2->next, &tmp_head);
- }
+ if (descend == (strcmp(ele_l1->value, ele_l2->value) < 0)) {
+ list_move_tail(l2->next, &tmp_head);
+ } else {
+ list_move_tail(l1->next, &tmp_head);
+ }
}
```
而在 `q_sort` 中，使用先前 `q_delete_mid` 函式中的方法找到中點，再使用 `list_cut_position` 剪下後半段，用遞迴的方式分別排序前後兩段再用 `merge_two` 合併
### q_merge
我首先去理解 `queue_contex_t` 的運作原理
每個 `queue_contex_t` 代表了一個佇列，其中 `q` 會指向佇列的頭，而 `chain` 則是用來連接不同的 `queue_contex_t`
在這個函式中，我將所有的佇列使用 `list_splice` 拼接到第一個佇列，並且使用 `list_del_init` 移除已合併的佇列，最後再使用 `q_sort` 排序
* 取第一個佇列時誤用 `list_entry`，後來使用 `list_first_entry`
```diff
-queue_contex_t *first_q = list_entry(&head->next, queue_contex_t, chain);
+queue_contex_t *first_q = list_first_entry(head, queue_contex_t, chain);
```
有時會出現 merge 完佇列消失的情況
```
l = [c r z]
cmd> merge
l = []
```
後來發現在清空佇列後不移除當前 `queue_contex_t` 就好了
```diff
list_for_each_entry_safe (curr, safe, head, chain) {
if (curr == first_q)
continue;
first_q->size += curr->size;
list_splice_init(curr->q, first_q->q);
- list_del_init(&curr->chain);
}
```
### 結果
使用 `make test` 測試，只剩 trace-17 無法通過
```
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
--- trace-17-complexity 0/5
--- TOTAL 95/100
make: *** [Makefile:60: test] Error 1
```
可以看到唯 `it` 和 `ih` 無法通過，有時候 `it` 會通過，分數為95
最後經由底下[修改 lab0/dudect](https://hackmd.io/D8_dNDEwTHi7RHGinG0bPQ?view#%E4%BF%AE%E6%94%B9-lab0dudect) 後可以得到100分
## 使用 Valgrind 檢查錯誤
先前使用 Valgrind 發現了實作 `q_free` 的暇疵，而最後我也嘗試使用它來找出 `trace-17` 中 `it` 和 `ih` 無法通過的原因，使用過程如下
```
$ valgrind -q --leak-check=full ./qtest
cmd> option simulation 1
cmd> it
Probably constant time
cmd> ih
Probably constant time
cmd> rh
Probably constant time
cmd> rt
Probably constant time
cmd> option simulation 0
cmd> quit
Freeing queue
```
Valgrind 沒有找到記憶體使用問題，同時也發現可能在通過邊緣，上面單獨測試`it` 和 `ih` 沒問題
## 實作 Shuffle
在 `queue.c` 中加上 `q_shuffle` 函式， `q_test` 中加上 `do_shuffle` 函式檢查是否為空或單節點，還有 `console_init` 中加上 `ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");`
```diff
* void q_shuffle(struct list_head *head) {
if (!head || head->next == head->prev)
return;
for (int len = q_size(head)-1; len > 0; len--) {
int random = 1 + rand() % len;
struct list_head *old = NULL, *new = NULL;
int j = 1;
struct list_head *pos;
list_for_each(pos, head) {
if (j == random) {
old = pos;
}
if (j == len + 1) {
new = pos;
break;
}
j++;
}
struct list_head *pre_new = new->prev;
struct list_head *pre_old = old->prev;
if(old->next == new){
list_del(old);
list_add(old,new);
+ } else {
+ list_del(new);
+ list_del(old);
+ list_add(new, pre_old);
+ list_add(old, pre_new);
}
}
}
```
:::danger
使用 `git diff` 或 `diff -u` 來產生程式碼之間的變異清單，不要憑感覺填入，注意位移量。
:::
首先在外層迴圈把 len 減少，裡面抽出要交換的 index 後用 `list_for_each` 找到要交換的 `old` 和 `new` ，最後交換節點
，交換的部份原先的寫法沒考慮到兩節點相鄰的狀況
### 實驗結果
測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖，可以看到結果很平均
---
## 改進 lab0-c 的 constant time test
### 閱讀 [〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
檢查程式是否為常數運行時間很重要是因為如果不是，有機會受到時序攻擊，資安上存在疑慮
而作者提出了 dudect 工具來測試程式是否為 constant time ，且相較於其他常見工具， dudect 不需要對硬體行為進行建模，也使用了 cropping 預處理，捨棄掉大於 p percentile 的資料，避免離群值過分影響統計結果，而 t value 的計算是使用 Welch’s t 檢定法。
### 修改 lab0/dudect
檢查 `fixture.c` 發現沒有進行 cropping ，因此從作者的原始碼以 percentile 為關鍵字找到 `percentile` 和 `prepare_percentiles` 函式，接著將前述兩個函式和他們會使用到的函式複製到 `fixture.c` 裡面，再修改 data type 就可以通過 trace-17-complexity，得到滿分
```
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
---
## Linux 核心鏈結串列排序
研讀 Linux 核心原始程式碼的 [lib/list_sort.c (commit b5c56e)](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) ，首先覺得陌生的就是` __attribute__((nonnull())) `，後來了解到` __attribute__ ` 是 gcc 中用來附加屬性給函式或結構的用法，提供編譯器額外的訊息，而 `nonnull(2,3,4,5)` 是用來表示函式內的第 2,3,4,5 個參數不能為空，如此一來就不用在函式內檢查，接下來逐一記錄研讀 `list_sort.c` 中函式的心得。
:::danger
不要「舉燭」，你該質疑 Linux 核心開發者「如果不這樣做，會怎樣？」
:::
### `merge`
此函式是用來合併已排序鏈結串列，過程中走訪兩個傳入的串列並且使用 `cmp(priv, a, b)` 來比較 a, b 節點中 `priv` 的大小，決定誰要排在前面，最後回傳合併的串列
值得注意的是，根據註解的說法，此函式回傳的是單向並且非環狀的串列，這樣比較適合多次合併使用。
### `merge_final`
```clike=
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
```
前面的 for 迴圈中，除了將兩個串列合併之外，也建立了雙向的連接，然而就算是 b 先結束， a 剩下部份的開頭也統一改名為 b
```clike=
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
```
這段主要是將 b 剩下的部份改成雙向串列，並且在最後將頭尾相接使其形成環狀，但 `if (unlikely(!++count))` 這段看不懂，經過查找資料後了解 `unlikely` 是一個巨集被定義為 `# define unlikely(x) __builtin_expect(!!(x), 0)` ，其中 `!!(x)` 會確保輸入值轉變為布林值 ，而 `__builtin_expect` 是 gcc 的內建函式，查看[手冊](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)中 Built-in Function: long __builtin_expect (long exp, long c) 舉例：
```
if (__builtin_expect (x, 0))
foo ();
```
當 `foo ()` 被執行的情況很罕見的時候可以這樣寫，幫助編譯器最佳化
而在 `merge_final` 中 `count` 增加，就會變非 0 ，執行 `cmp(priv, b, b)` ，但我還是不知道為什麼要執行 `cmp(priv, b, b)` 比較 b 自己，而且由於 ++ 是在前面，所以在執行第一次的時候 `count` 就會是非 0
### `list_sort`
```clike=
/* 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;
```
for 迴圈會逐位尋找二進位 `count` ，直到遇到第一個 0 結束迴圈，接下來判斷如果剩餘的位數存在 1 就進行合併，這樣做相當於當 count+1 不為 $2^k$ 時合併，參考[何時合併](https://hackmd.io/@sysprog/linux2024-lab0-e#%E4%BD%95%E6%99%82%E5%90%88%E4%BD%B5)的表格：
| 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 |
| 7 $\to$ 8 | 0111 $\to$ 1000 | no（$2^3$） | 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 |
| 8 $\to$ 9 | 1000 $\to$ 100==1== | yes | 4 $\gets$ 2 $\gets$ (2) $\gets$ 1 |
| 9 $\to$ 10 | 1001 $\to$ 10==1==0 | yes | 4 $\gets$ (4) $\gets$ 1 $\gets$ 1 |
| 10 $\to$ 11 | 1010 $\to$ 101==1== | yes | 4 $\gets$ 4 $\gets$ (2) $\gets$ 1 |
| 11 $\to$ 12 | 1011 $\to$ 1==1==00 | yes | (8) $\gets$ 2 $\gets$ 1 $\gets$ 1 |
| 12 $\to$ 13 | 1100 $\to$ 110==1== | yes | 8 $\gets$ 2 $\gets$ (2) $\gets$ 1 |
| 13 $\to$ 14 | 1101 $\to$ 11==1==0 | yes | 8 $\gets$ (4) $\gets$ 1 $\gets$ 1 |
| 14 $\to$ 15 | 1110 $\to$ 111==1== | yes | 8 $\gets$ 4 $\gets$ (2) $\gets$ 1 |
| 15 $\to$ 16 | 1111 $\to$ 10000 | no（$2^4$） | 8 $\gets$ 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 |
而整個函式會逐一把原始串列 `list` 的節點移到待處理串列 `pending` ， 而 `pending` 中已排序的子串列會以前段提到的規則合併，直到原始 `list` 輸入完，接著在最後的 for 迴圈中會繼續合併 `pending` 中子串列，在這個階段是取最後一個和倒數第二個子串列合併成一個，直到只剩兩個子串列就結束迴圈，執行 `final_merge` 完成全部的合併
### 閱讀 [< BOTTOM-UP MERGESORT A Detailed Analysis > ](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5260)
Merge sort 可分成 bottom-up 和 top-down ， top-down 為課本典型的演算法，將待排序序列分成左右兩個子序列，左右又繼續分裂直到子序列長度是一再合併，適合遞迴處理; bottum-up 則是將待排序序列元素逐一處理，在適當的時機合併，適合非遞迴實作，[commit b5c56e](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 屬於 bottom-up 的一種變形，也是逐一將元素讀入，差別在於合併的時機不同。
下表為 bottom-up 和 top-down 的性能較比較：
| Case | Best Case | Average Case | Worst Case |
|------------|-----------|----------------------|--------------------|
| Top-Down | 1 | 2N lg N - 0.146N | N lg N - 1.248N | N lg N - 0.943N |
| Bottom-Up | 1 | 2N lg N - 0.146N | N lg N - 0.965N | N lg N - 0.701N |
雖然 bottom-up 的最差情況效能略輸 top-down ， 但是 bottom-up 不需要預先知道序列長度，適合 link-list 實作的序列，這點使得它的實用性大於 top-down。
### 閱讀 [Queue-Mergesort](https://doi.org/10.1016/0020-0190(93)90088-q)
這篇文章主要介紹一種合併排序的變體稱為 Queue Mergesort ，使用佇列存放待合併序列，先將每個元素單獨作為一個待排序序列存放於佇列，之後不斷從頭部取出兩個進行合併後放到尾部，直到佇列中剩下一個序列即完成排序。
作者也證明這種方法是 optiml mergesort ，也就是對任何待排序元素個數 N ，最差情況下比較次數不比其他 mergesort <s>算法</s> 演算法多
:::danger
algorithm 是「演算法」，而「算法」是 the way you calculate，也就是你在國中小學數學測驗卷上的「計算過程」，二者不同。
:::
### 閱讀 [The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules](https://doi.org/10.1006/jagm.1998.0986)
當兩個要合併的序列長度比值是2的冪時，也就是使用 power-of-2 rules ，有機會使得整體的時間複雜度隨著 N 變大時線性成長，既使合併兩序列的複雜度是超線性，因此相較於 half-half rules ，使用 power-of-2 rules 可以在 N 很大的時候顯著降低運算時間，而在 [commit b5c56e](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 中選用合併序列長度比值上限為 2 是因為不論 N 多少每一步合併都能限制在這個比值以下。
### 引入 lib/list_sort.c 到 lab0-c
經過了上面的理解，我意識到自己之前實作 `q_sort` 的方法是多麼天真且愚蠢，因此我引入 lib/list_sort.c 的<s>算法</s> 演算法到 lab0-c [(commit 9837691)](https://github.com/sysprog21/lab0-c/commit/98376912f884a6766f0adb9e28eb3de656549ba6)。
過程中做了一些改寫，為了簡化實作，刪去了編譯器優化的部份`__attribute__((nonnull())`, `likely` 和 `unlikely` ，還有以 `strcmp` 取代 `cmp` 函式，因此也刪減了有關函式的傳入參數 `prev`, `cmp` 。
Sign in with Wallet
Connect another wallet