# 2024q1 Homework1 (lab0)
contributed by < `ShawnXuanc` >
### Reviewed by `SimonLee0316`
> 你的洞見呢？
### Reviewed by `SHChang-Anderson`
* `new_element` 實作中提到可以使程式碼更加簡潔，請提出改進的規劃。
* 檢視 commit 連結是否貼錯，`q_swap, q_ascend, q_descend` commit 連結點入皆為 `q_merge` 的實作。
* 嘗試使用 List API 如 : `list_move_tail` 或 `list_move` 透過不同順序移動節點達成 `q_swap` 實作。
> 收到非常感謝 會將內容進行修正並改進
> 已搭配 list_move 來修正 q_swap
> [name=shawn]
### Reviewed by `Shiang1212`
在[如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/) 有提到：內文每行最多 72 字。
> Git 不會把任何文字自動換行。當你在撰寫 commit message 內文的時候，你需要注意左邊的 margin，並且手動將超過 margin 的文字換到下一行。
如 [089c5e5](https://github.com/sysprog21/lab0-c/commit/089c5e58381f502d2a4d56548657ba5154e7c86b) 和 [909cd79](https://github.com/sysprog21/lab0-c/commit/909cd79542d5499677bee90cc870fdff3322612f) 皆沒有滿足要求。雖然只是簡單的換行，但能有效提高 commit message 的可讀性。
>已修改 commit 進行換行非常感謝
>修改後的 commit 為 [b14916f](https://github.com/sysprog21/lab0-c/commit/b14916fe852fc01427f1d2f1fa48ea69dc1bd8bd) 以及 [8d3be5a](https://github.com/sysprog21/lab0-c/commit/8d3be5a0f57be59e5a38484a0942b101c7e79736)
>[name=shawn]
## 開發環境
$ gcc --version
(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): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-7267U CPU @3.10GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
Stepping: 9
CPU max MHz: 3500.0000
CPU min MHz: 400.0000
BogoMIPS: 6199.99
由於使用的是 `macbook` ，當初在燒錄 `ubuntu` 時遇到了一些問題，在使用 balenaEtcher 時無法正確燒錄，在經過查詢之後發現使用下方<s>指令</s> 命令開啟燒錄軟體才能正常燒錄，若有遇到相同問題可以嘗試使用下方命令開啟
```shell
$ sudo /Applications/balenaEtcher.app/Contents/MacOS/balenaEtcher
```
在進行程式碼測試時可以善加利用 `qtest` 以及 `Valgrind` 來評估程式的正確性以及處理記憶體洩漏問題，這樣的方式有助於更深入理解問題發生得原因，幫助我們更加精確的理解問題的所在
通過使用 `qtest` 可以執行所撰寫的測試案例，確保程式行為符合預期，搭配使用 `Valgrind` 可以知道記憶體出現問題的地方，並搭配所提供的資料，找到出現問題的原因
在進行 `git commit` 時務必仔細閱讀 [How to write a git commit message](https://cbea.ms/git-commit/) 並遵守其中的七個步驟，如果不慎傳遞了錯誤的 `commit` 內容或是想修改先前的提交，可以使用 `git rebase <commit Id> -i` 來修改正確的內容，最後記得使用 `git push -f` 將修改過後的內容上傳
## 指定佇列的操作
### `q_size`
第一次接觸 `list_for_each` 這類型的巨集使用所以還不太習慣，但藉由<s>通過</s> 範例的練習，更加了解使用方式，並慢慢熟悉 linux 核心風格鏈結串列操作
:::danger
不該將 through 稱作「通過」，否則你如何區隔 pass (通過) 呢？
:::
> 了解，會對用詞更加注意
> [name=shawn]
### `q_free`
函式功能為釋放一個佇列，在釋放每個 `element_t` 時，需要先釋放結構中的字串，然後釋放結構本身，最後將作為 `head` 節點的記憶體空間釋放
### `q_insert_head` and `q_inset_tail`
> commit [e956281](https://github.com/sysprog21/lab0-c/commit/e95628137a25f8c0e5eb527126c4d4de395fa4ab)
:::danger
留意以下程式碼的縮排
:::
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
> 謝謝老師幫忙修正錯字
> [name=shawn]
> 會更加注意在中英文詞彙上的使用 謝謝老師[name=shawn]
函式功能為將新增的元素加到佇列時，要注意在複製字串內容<s>創建字串</s> 時要使用 `malloc` 來配置記憶體，為避免程式碼重複出現，使用一個新的函式 `new_element` 來省去重複的程式碼
如果是使用 `strcpy` 會有記憶體問題，因為 `strcpy` 不會事先檢查字串長度，所以改成使用 `strncpy`
:::warning
本處並非「創建字串」，充其量只是配置必要的記憶體空間並複製給定的字串內容。改進你的漢語表達。
:::
> 了解 謝謝老師[name=shawn]
### `new_element`
> commit [e956281](https://github.com/sysprog21/lab0-c/commit/e95628137a25f8c0e5eb527126c4d4de395fa4ab)
:::danger
不符合作業規範，請用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範。
:::
> 對此部份會再修改謝謝老師 [name=shawn]
```c
bool new_element(element_t **element, char *s)
{
if (!s)
return true;
int len = strlen(s) + 1;
(*node) = malloc(sizeof(element_t));
char *tmp_s = malloc(len);
if (!*node || !tmp_s) {
free(*node);
free(tmp_s);
return true;
}
strncpy(tmp_s, s, len);
(*node)->value = tmp_s;
INIT_LIST_HEAD(&(*node)->list);
return false;
}
```
在這段程式碼中，通過使用指標的指標，可以讓函式不用返回節點內容，而只返回條件的判斷結果，使得程式碼的實現更加容易
#### Todo: 可以更加簡潔
### `q_remove_head` and `q_remove_tail`
> commit [1238597](https://github.com/sysprog21/lab0-c/commit/12385973a431f5b5233fd19adc5516ee8d64be8a)
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
> 收到會將不必要的程式碼移除只列出關鍵程式碼[name=shawn]
再移除節點的過程中，兩個函式的功能分別為對 `head` 的前一個節點與後一個節點進行節點的移除
為了防止記憶體問題，同樣使用更加安全的 `strncpy` ，在過程中將要傳回的字串的最後一個位置設定為 `\0` ，以避免錯誤的結果
兩段程式碼不同之處僅在於要移除指標所指向的位置，為了減少重複的程式碼新增 `q_remove_list`，來重複利用相同的程式碼
> commit [b0375b1](https://github.com/sysprog21/lab0-c/commit/b0375b153acdff04b08f4c3b7fa7e8b416d918bf)
### `q_delete_dup`
一開始的想法是利用 `pre` 指標來紀錄重複的節點，同時使用 `dup` 指標來掃過所有重複節點，在過程中用 `tmp` 來釋放重複的節點，釋放完重複的節點後，釋放 `pre` 指向的節點並調整 `pre` 指標的位置
在處理過程中，若重複的節點是位在 `head->next` 時，在進行 `pre` 指標的移動結束後要將 `pre` 指標與 `dup` 指標指回正確的位置也就是 `head->next` 以及 `head->next->next`
可以發現上面這樣的想法會導致需要額外的特例處理，以及有太多重複的程式碼出現
經過修改之後使用 `list.h` 所提供的巨集，在走訪節點的過程中使用 `tmp` 來儲存重複的節點，當重複的節點為當前的最後一個時會需要藉由這樣的方式來將其刪除，
當走訪到最後時 `safe` 指標會指到 `head` 的位置，因為 list_entry 會發生錯誤在導致 `strcmp` 會判斷出記憶體洩漏的問題，需要特別處理這個例外的情況
發現記憶體洩漏問題是使用 `Valgrind` 進行偵測，可以看到在 `queue.c` 中 155 行時出現問題，除此之外也可以搭配 `qtest` 裡面的程式碼來進一步了解問題所在
==15908== Invalid read of size 1
==15908== at 0x484FBD7: strcmp (in/usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==15908== by 0x10FBBD: q_delete_dup (queue.c:154)
==15908== by 0x10C15E: do_dedup (qtest.c:464)
==15908== by 0x10E0F9: interpret_cmda (console.c:181)
==15908== by 0x10E6AE: interpret_cmd (console.c:201)
==15908== by 0x10F318: run_console (console.c:691)
==15908== by 0x10D4EB: main (qtest.c:1280)
==15908== Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==15908==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer==15908== 2 bytes in 1 blocks are still reachable in loss record 1 of 53
### `q_swap`
> commit [b9536b1](https://github.com/sysprog21/lab0-c/commit/56f7f98366e063d9e13989ef0be5ce76015d7856)
```diff
+ n2->next->prev = n1;
n1->next = n2->next;
n2->next = n1;
n2->prev = n1->prev;
n1->prev = n2;
+ pre->next = n2;
+ pre = n1;
```
交換節點的方式是通過使用兩個指標來指向要交換位置的節點，並將這兩個節點進行位置交換
在一開始撰寫時只考慮到將兩個節點進行交換的，疏忽了指向交換節點的另外兩個節點，導致錯誤的結果
最後在交換的過程中，需要將原先與兩節點相連的節點，即 `n1->prev` 以及 `n2->next` 指向交換完的節點
> commit [39bd60c](https://github.com/sysprog21/lab0-c/commit/39bd60c1e51e1a4338067c307258cad8c857151c)
```c
for (struct list_head *n1 = head->next->next, *pre = head;
n1 != head && n1->prev != head; n1 = pre->next->next) {
list_move(n1, pre);
pre = n1->next;
}
```
在經過 [SHChang-Anderson](https://hackmd.io/@ShchangAnderson/ryWsAyUna) 同學的 `review` 後收到建議，並使用 `list_move` 的方式來進行修改，這邊的想法是藉由讓 `n1` 往前移動到 `pre` 的下一個節點來更換位置，移動完後在更新 `n1` 以及 `pre` 的指標，藉由這樣的方式來交換兩個節點的位置，每次讓 `n1` 藉由 `pre` 來找到正確的位置
這邊要有一個比較特別的地方在於最後得判斷要判斷是否 `n1->prev` 為 `head` ，如果照著之前判斷 `n1->next != head` 則會導致當節點數量大於等於 `6` 時最後兩個節點會沒辦法交換，因為這時候 `n1->next` 即為 `head` 還未交換就離開迴圈了
```graphviz
digraph G {
rankdir = "LR"
h [label="head",shape="square"]
n1 [label="1", shape="square"]
n2 [label="2", shape="square"]
n3 [label="3", shape="square"]
n4 [label="4", shape="square"]
n5 [label="5", shape="square"]
{
rank=same
pre[label="pre", shape="plain", fontcolor="blue"]
pre->h
}
{
rank=same
n1_p[label="n1", shape="plain", fontcolor="red"]
n1_p->n2
}
h->n1->n2->n3->n4->n5
}
```
```graphviz
digraph G {
rankdir = "LR"
h [label="head",shape="square"]
n1 [label="2", shape="square"]
n2 [label="1", shape="square"]
n3 [label="3", shape="square"]
n4 [label="4", shape="square"]
n5 [label="5", shape="square"]
{
rank=same
pre[label="pre", shape="plain", fontcolor="blue"]
pre->n2
}
{
rank=same
n1_p[label="n1", shape="plain", fontcolor="red"]
n1_p->n4
}
h->n1->n2->n3->n4->n5
}
```
```graphviz
digraph G {
rankdir = "LR"
h [label="head",shape="square"]
n1 [label="2", shape="square"]
n2 [label="1", shape="square"]
n3 [label="4", shape="square"]
n4 [label="3", shape="square"]
n5 [label="5", shape="square"]
{
rank=same
pre[label="pre", shape="plain", fontcolor="blue"]
pre->n4
}
{
rank=same
n1_p[label="n1", shape="plain", fontcolor="red"]
n1_p->h
}
h->n1->n2->n3->n4->n5
}
```
### `q_reverseK`
想法是基於之前反轉串列的概念，使用將節點移動到環狀鏈結串列的 `head` 來進行反轉，不同之處在於要根據給定的 `k`值來更新反轉的起始位置
新的起始位置是 `head` 的下一個節點位置，但在經過翻轉之後會改變節點的位置，因此需要在最開始時先紀錄下來，這樣的話在經過反轉過後就不會獲得錯誤的位置
### `q_ascend` and `q_descend`
> commit [b9536b1](https://github.com/ShawnXuanc/lab0-c/commit/74540d6f70fc17057cffb8da5e2d7a4bff9607d9)
```c
for (safe = move->prev; move != head; move = safe, safe = move->prev) {
element_t *cur_ele = list_entry(cur, element_t, list);
element_t *move_ele = list_entry(move, element_t, list);
if (strcmp(cur_ele->value, move_ele->value) > 0) {
list_del(move);
q_release_element(move_ele);
} else {
cur = move;
count += 1;
}
}
```
對於 `q_descend`，使用原本的巨集 `list_for_each` 是往 `next`
的方向移動，而在這個問題上藉由往反方向移動的方式可以減少問題的困難度
通過這樣的方式讓問題簡化，只需要在遇到比當前節點更小的節點時將其刪除，而在遇到比當前節點更大的節點時再更新當前節點這樣，重複這個步驟，每次進行當前節點更新時，同時計算剩餘節點數量
相反的，對於`q_ascend` 遇到比當前節點大的節點時，將其刪除遇到比當前節點小時，更新位置，並計算剩餘節點數量
:::danger
減少非必要的項目縮排 (即 `* `)，使用清晰、明確，且流暢的漢語書寫。
:::
### `q_sort`
> commit [f4aad84](https://github.com/sysprog21/lab0-c/commit/f4aad84aa86fdde91f2389c934e2b1b5689add1b)
:::danger
減少非必要的項目縮排 (即 `* `)，使用清晰、明確，且流暢的漢語書寫。
:::
選擇使用 `Merge_sort` 而不是 `Quick sort` 的原因在特定的條件下如果選擇 `pivot` 不當 (選到集合裡面的最大最小值)，可能會導致整個排序的時間複雜度變成 O(N^2^)，所以選擇使用 `Merge sort`
參考了 `list_sort` 的方式，先將環狀鏈結串列的環狀狀態解除變成單向的，再將 `head->next` 作為參數傳遞給 `mergeSort` 來進行排序
```c
struct list_head *slow = head, *fast = head->next, *right;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
```
:::danger
減少非必要的項目縮排 (即 `* `)，使用清晰、明確，且流暢的漢語書寫。
:::
在這裡一開始先判斷 `head` 跟 `head->next` 的原因是因為已經將整個環狀鏈結串列變成單向的，在進行切割切時，最後會剩下單一節點，通過判斷節點是否還有相鄰連接，可以確認是否完成
使用快慢指標來切割整個鏈結串列時，在初始指標設定時將 `fast` 設定在 `head->next` － 藉由這樣的方式 `slow` 指標才可以取得原先會到達位置的前一個節點，從而正確的去做切割
:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
### `merge`
> commit [f4aad84](https://github.com/sysprog21/lab0-c/commit/f4aad84aa86fdde91f2389c934e2b1b5689add1b)
:::danger
不符合作業規範，請用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範。
:::
排序合併的方式是使用一個暫時節點，並將較小的節點往後接上，最後判斷是否有剩餘的節點，若有就將剩下的串列內容接續到之前排序好的鏈結串列上
```c
int cmp(const char *a, const char *b, bool descend)
{
if (descend)
return strcmp(b, a);
else
return strcmp(a, b);
}
```
:::danger
減少非必要的項目縮排 (即 `* `)，使用清晰、明確，且流暢的漢語書寫。
:::
－ 題目要求要能夠依據 `descend` 參數來判斷排序的方式，為了實現這樣的效果，可以利用 `cmp` 通過傳遞字串順序的不同來達成這樣的效果，使得程式碼看起來更加簡潔
```c
for (pre = head, node = head->next; node->next != NULL;
pre = node, node = node->next) {
node->prev = pre;
}
node->next = head;
head->prev = node;
```
回到 `q_sort` 時，由於之前有將鏈結串列的環狀結構截斷，因此在排序完成後，需要重新將鏈結串列恢復成正確的結構，使用這段 `for` 迴圈的方式將 `prev` 指標接上，最後更新 `head` 的指標
**Todo** 使用你所不知道的c語言 `linked list` 篇的技巧使 `merge` 更加簡潔
### `q_merge`
> commit [9bca09b](https://github.com/sysprog21/lab0-c/commit/9bca09bceec42f48bb5a6d117559a026cd287d0d)
:::danger
不符合作業規範，請用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範。
:::
```diff
while (move != head) {
queue_contex_t *tmp = list_entry(move, queue_contex_t, chain);
size += tmp->size;
tmp->q->prev->next = NULL;
mrg_q = merge(mrg_q, tmp->q->next, descend);
move = move->next;
+ INIT_LIST_HEAD(tmp->q);
}
```
在`merge` 這個問題中，因為使用的資料結構稍微有點不同，但是概念還是一樣的所以需要做一些許變化，在前面的問題中，都是使用 `head` 連接 `element_t` 的節點，在這邊 `head` 則是連接 `queue_contex_t` ，在 `queue_contex_t` 的結構中使用 `q` 指標來指向佇列的 `head` 節點
對於這個問題的想法是，使用一個暫時的節點，遍歷 `head` 所連接的每個佇列 <s>待補</s> 經由前面 `q_sort` 所使用到的 `merge` 函式來進行合併，將 `head->next` 作為開頭的佇列與一開始所宣告的暫時節點合併最後形成一個排序好的佇列
再一開始時，要藉由斷開串列的技巧讓串列變成單向，所以在最後要合併回去，在這裡有一個需要特別注意的地方，就是將各個佇列合併時，必須對原先指向合併佇列的節點進行初始化`INIT_LIST_HEAD`，否則會發生`Attempted to free unallocated block`的錯誤
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
## 使用 valgrind 偵測記憶體問題
使用下方命令，利用 [valgrind](https://valgrind.org/) 找出記憶體洩漏問題
```shell
$ valgrind -q --leak-check=full ./qtest
```
對 qtest 程式碼進行測試，查看是否存在記憶體的問題
以 q_merge 為例，因為沒有正確將使用過的串列節點進行初始化，使其在 qtest 中正確釋放，因此發生記憶體錯誤問題
```
==7908== Invalid read of size 8
==7908== at 0x10FA46: q_free (queue.c:29)
==7908== by 0x10BF89: do_merge (qtest.c:906)
==7908== by 0x10E2E0: interpret_cmda (console.c:181)
==7908== by 0x10E895: interpret_cmd (console.c:201)
==7908== by 0x10F4FF: run_console (console.c:691)
==7908== by 0x10D6D2: main (qtest.c:1330)
==7908== Address 0x4b8d120 is 48 bytes inside a block of size 64 free'd
==7908== at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==7908== by 0x10F7AE: test_free (harness.c:204)
==7908== by 0x10FA42: q_free (queue.c:31)
==7908== by 0x10BF89: do_merge (qtest.c:906)
==7908== by 0x10E2E0: interpret_cmda (console.c:181)
==7908== by 0x10E895: interpret_cmd (console.c:201)
==7908== by 0x10F4FF: run_console (console.c:691)
==7908== by 0x10D6D2: main (qtest.c:1330)
==7908== Block was alloc'd at
==7908== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
```
可以藉由 `valgrind` 得知發現錯誤的地方，在去查看可能出現問題的函式在哪邊，藉此判斷出原因
以這邊的錯誤訊息來查看就可以知道問題發生在使用 merge 時，藉由這樣的方式到 qtest 中查看可能的問題所在再去排除
```
--------------------------------------------------------------------------------
Command: ./qtest
Massif arguments: (none)
ms_print arguments: massif.out.7687
--------------------------------------------------------------------------------
KB
16.75^ ::
| ::@ :: ::# :
| : @ : : # :
| : @ : : # :
| : @ : : # :
| : @ : : # : :
| : @:: @:: #::: @:
| : @:: @:: #::: @:
| :: @:: @:: #::: @@
| :: @:: @:: #::: @@ :
| :: @:: @:: #::: @@ :
| :: @:: @:: #::: @@ :
| ::: @:: @:: #::: @@ :
| ::: @:: @:: #::: @@:::
| ::: @:: @:: #::: @@: :
| ::: @:: @:: #::: @@: :
| ::: @:: @:: #::: @@: :
| ::: @:: @:: #::: @@: :
| :::: @:: @:: #::: @@: :
| ::::: @:: @:: #::: @@: :
0 +----------------------------------------------------------------------->ki
0 381.8
Number of snapshots: 57
Detailed snapshots: [22, 29, 37 (peak), 47, 50]
```
可搭配 `massif` 工具，使用命令
```shell
$ valgrind --tool=massif ./qtest
```
獲得 `massif.out.<number>` 搭配下方命令獲得 `heap` 的時間變化量
```shell
$ ms_print massif.out.<number>
```
圖片意思為 heap 隨著測試時間的分配量變化
並使用視覺化工具 `massif-visualizer` 來進行記憶體查看
```shell
$ massif-visualizer massif.out.<number>
```
---
## 整合網頁伺服器
#### select()
讓當前程式可以監控多個 [file descriptors](https://stackoverflow.com/questions/5256599/what-are-file-descriptors-explained-in-simple-terms) 的狀態變化，直到一個或多個的 file descriptors 變成 `ready` 的狀態
#### fd_set
`file descriptior` 的集合
#### File descriptor sets
* FD_ZERO(): 用來清空集合
* FD_SET(): 將 `file descriptior` 加入集合
* FD_CLR(): 將 `file descriptior` 從集合中移除
* FD_ISSET()測試 `file descriptior` 是否在集合中
---
## 在 q_test 中提供新命令 `shuffle`
藉由 `Knuth shuffle` 演算法實作 `shuffle` 功能
這邊的想法是將 `tmp` 的節點由鏈結串列的最前端出發，藉由隨機值 `rand() % (len - i)` 選擇一個前進的步數來移動 `tmp`節點，將步數的範圍限制在 0 到 `len - i - 1` 之間
在進行節點交換的部份是先將要進行交換的兩個節點 `n1` 以 `n2` 分別先紀錄 `n1->next` 以及 `n2->prev` 作為連結的部份，這樣就可以不用考慮選到的兩個節點為相鄰節點的問題，而在每次交換完要記得將 `move` 的節點改為 `tmp` 不然可能會導致 `move` 的指標設定到 `tmp` 的位置，這樣才會符合原本的設定，使得下一輪開始的順序不會發生錯誤
完成 `shuffle` 的實作之後，就可以將 `shuffle` 的功能整合到 qtest 裡面，首先對照 qtest 內部的程式碼可以發現對每一個在 queue.c 中的功能在 qtest 中都有一個對應的 `do_<function>` 的函式，因此也對照實作`do_shuffle`，並且在 `console_init` 中新增命令 `ADD_COMMAND(shuffle, ...)` 這樣就可以在 qtest 中使用 `shuffle` 的功能
最後因為 `shuffle` 的標頭檔問題，由於不能修改 `queue.h` 的內容，所以要將 `shuffle.h` 另外撰寫，讓 `qtest` 使用
### 實驗
Expectation: 41666
observation: {'1234': 41675, '1243': 41995, '1324': 41572, '1342': 41870, '1423': 41560, '1432': 41585, '2134': 41718, '2143': 41686, '2314': 41310, '2341': 41333, '2413': 41562, '2431': 41705, '3124': 41486, '3142': 41684, '3214': 41619, '3241': 41648, '3412': 41781, '3421': 41702, '4123': 41980, '4132': 41759, '4213': 41958, '4231': 41493, '4312': 41777, '4321': 41542}
chi square sum: 17.509480151682425
根據老師提供腳本裡面的設定可以看到，會進行 `1000000` 次 `shuffle` ，總共會有 `24` 種組合，在進行亂數之後每個組合出現的數字都非常接近平均的 `41666` 次
最後在根據提供的繪圖方式來繪製可以看到最後的結果
## 閱讀〈Dude is my code constant time〉論文
### 方法
對兩個不同類別的資料進行執行時間的測試並且觀察兩個時間分佈的不同
#### step1 測量執行時間
使用 `fix-vs-random` 的偵測方式來偵測兩種不同的測試資料，將第一類分成固定的值，而第二類為隨機選擇
現代 `cpu` 具備時脈週期的計算功能，可以準確的計算時間
為了最小話環境變化的影響每個測量都會對應到一個隨機類別
#### step2 後處理
每個測試資料在統計分析之前會進行後處理
`crop` 將執行時間超過一定閥值的測量截斷或丟棄
根據所應用統計測試，進行高階的預處理
#### step3 應用統計資料
利用統計資料來反駁虛無假說
使用 `welch's t-test` 來檢驗時間分佈的均值是否相等，`welchl's t-test` 失敗時代表存在一定的洩漏問題
可使用非參數測試，因非參數測試會對底層分佈有較少的假設
### 結果
作者使用 C 語言實作 [dudect](https://github.com/oreparaz/dudect/blob/master/src/dudect.h)
對資料進行預處理，為了測試受限的資料分佈，將大於 `p` 百分位的資料丟棄，且也對沒進行預處理的資料進行測試
使用 `welch's t-test` 搭配 `welford's` 變異數計算來提升穩定
使用基於 `memcmp` 的 `16-byte` 記憶體比較函數測試，並設計兩種不同的洩漏檢測方式，在發現兩個類別的分佈明顯不同時即存在時間洩漏問題
### 查看 dudect 程式碼
在查看 `dudect` 的程式碼時可以發現在實作 `p` 值的這個部份是缺少的，
即在 `crop` 後處理部份的藉由閥值丟棄超過時間的測量部份因此我們需要去對照 `dudect` 中缺失的部份
可以看到 `dudect` 中的結構 `dudect_ctx_t` 這部份 `fixture` 內部的實作直接將結構的變數宣告在 `doit` 中使用但是少了 `percentiles` ，所以在這邊補上，並記得在最後使用完進行釋放
```diff
static bool doit(int mode)
{
...
+ int64_t *percentiles = calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));
...
+ free(percentiles)
}
```
新增完之後還要記得將 `first_time` 加入到 `do_it` 中並且加入 `if (first_time)` 來判斷使用 `prepare_percentiles`
```c
static int cmp(const int64_t *a, const int64_t *b){..}
static int64_t percentile(int64_t *a_sorted, double which, size_t size){..}
static void prepare_percentiles(int64_t *exec_times, int64_t *percentiles){..}
```
而缺失的部份還包含 `cmp`, `percentile` 以及 `prepare_percentiles` 將其補上
```c
for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES;
crop_index++) {
if (difference < percentiles[crop_index]) {
t_push(t, difference, classes[i]);
}
}
```
讓程式可以正常運作，在 `doit` 中加上對於 `first_time` 的判斷，來準備 `percentiles` 並且最後在 `update_statics` 的地方新增迴圈判斷 `percentiles` 的值來讓 `lab0-c` 可以在多項式時間內完成滿足要求的最後條件
---
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
參考 [Risheng1128](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view#%E5%BC%95%E5%85%A5-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A2%BC%E5%88%B0-lab0-c) 和 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#%E7%A0%94%E8%AE%80-list_sortc-%E4%B8%A6%E5%BC%95%E5%85%A5%E5%B0%88%E6%A1%88)
`list_sort` 一開始會先先判斷是否是單一節點，並且將鏈結串列的環狀結構斷開，變成以單向的方式來進行，而這邊使用了 pending 指標來指向一段子串列
在 `while` 中以判斷 count 的 `bit` 這樣的方式來確認目前子串列的數量，當 `count + 1` 的值是2的冪時就不進行合併的在 `for` 中將 `...111` 的 `1` 向右移清除成 `0` 來讓 `if` 判斷不會成立，而當 `count` 為其他值時則會進行合併
在進行 `if (likely(bit))` 判斷完後則會進行指標的移動將 `pending` 跟 `list` 都向前一個節點，再離開 `while` 之後將剩下的 `list` 進行合併，並在最後用 `final_merge` 將鏈結串列的環狀結構重新建立
在 `merge_final` 中會看到一段 `cmp(priv, b, b)` 的比較而為什麼這邊要進行自己跟自己的比較是因為在原始程式碼中的 cmp 中有一個 cond_resched() 的函式，當發生對於以排序好的串列內容要進行，就可以藉由呼叫 cond_resched() 讓 kerne 將 cpu 將給其他優先權更高的來使用
#### `likely` 巨集
巨集中使用到 `!!(x)` 來確保得到的值一定為 `1` 或 `0` 透過這樣的方式就可以讓編譯器在編譯時對組合語言分支指令進行最佳化
#### `__attribute__((..))`
在函式宣告前增加特性，增強編譯器的錯誤檢查功能包含可填寫參數包含
`packed` `aligned` `section` `unused` `nonnull`...
在 `list_sort` 之中會看到 `__attribute__((nonnull(1,2)))` 功能為用來判斷說第幾個參數不能為空這邊填入 `1`, `2` 也就是第 1 個以及第 2 個不能為空
### 將 `list_sort.c` 引入到專案中
原先打算建立新的 `list_sort.c` 以及 `list_sort.h` 到 `lab0-c` 中，在將 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 以及 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 的內容加入到新建立的 `.c` 以及 `.h` 檔之中
但是在將 `list_sort` 上傳到 github 階段發現在 commit 階段會產生錯誤訊息，而發生這樣問題的地方是在 cmp 函式中使用 strcmp 對 `list_entry(a, element_t, list)->value` 以及 `list_entry(b, element_t, list)->value` 進行比較時，在經過調查後發現是關於 `cppcheck-suppress nullPointer` 的問題，最後決定將 list_sort 放到 queue.c 中解決
```
list_sort.c:11:24: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
```
在引入 list_sort 一開始，先建立 `list_sort.h` 將所要內容加入包含缺少的 likely 相關巨集加入到其中
```diff
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
```
也會發現 `u8` 這個資料型態沒辦法使用，而為什麼 linux kernel 的程式碼使用 u8這個資料型態可以參考 [stackoverflow](https://stackoverflow.com/questions/30896489/why-is-u8-u16-u32-u64-used-instead-of-unsigned-int-in-kernel-programming)，要解決的這樣的問題可以 `#include <stdint.h>` 並使用 `uint8_t` 來取代，或是 `typedef uint8_t u8` 來解決這樣的問題
對於程式碼的部份，因為缺少 cmp 這個函式，而我在 queue.c 中原先就有宣告 cmp 所以我決定撰寫 ls_cmp 來取代，其內容為 strcmp(...) 的判斷，也因為在閱讀 list_sort 時發現 priv 這個指標只有 cmp 使用到，對於其他函式是沒有意義的，因此決定將其刪除
在新增完後再次編譯會發現 `EXPORT_SYMBOL(list_sort)` 出現問題，其功能為讓被 `EXPORT_SYMBOL` 定義的函式可以被 kernel 的其他 `modlue` 所使用
我在這邊選擇的方法為直接將其刪除，接下來就可以正常使用 `list_sort`了
```diff
- EXPORT_SYMBOL(list_sort);
```
### 比較所撰寫 `sort` 以及 linux 核心版本 `list_sort` 差異
:::danger
明確標示 GitHub 帳號名稱。
:::
在查閱參考筆記時發現，<s>筆記同學</s> [Risheng1128](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view#%E5%BC%95%E5%85%A5-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A2%BC%E5%88%B0-lab0-c) 同學是在使用 make check 時觀察到裡面的命令，並藉由這樣的方式來發現並去撰寫新的命令內容，讓我頗有啟發我原先都沒有想到可以藉由這樣的方式來了解內部檔案的使用
使用下方命令
```shell
$ ./qtest -f traces/<name>.cmd
```
來執行 lab0-c 中 traces 裡面所撰寫的測試檔，這邊是使用下方測試流程進行測試，並且更改 RAND 的值來比較兩個 sort之間的差異
```
new
ih RAND <times>
time
<sort>
time
```
### 時間比較
#### rand 100000
| q_sort | time | list_sort | time |
|:------:|:-----:|:---------:|:-----:|
| 1 | 0.086 | 1 | 0.078 |
| 2 | 0.092 | 2 | 0.078 |
| 3 | 0.092 | 3 | 0.078 |
| 4 | 0.094 | 4 | 0.073 |
| 5 | 0.088 | 5 | 0.080 |
#### rand 600000
| q_sort | time | list_sort | time |
|:------:|:-----:|:---------:|:-----:|
| 1 | 0.672 | 1 | 0.585 |
| 2 | 0.668 | 2 | 0.586 |
| 3 | 0.717 | 3 | 0.583 |
| 4 | 0.699 | 4 | 0.585 |
| 5 | 0.710 | 5 | 0.597 |
在時間效能上我使用的是 `top down` 版本的 `merge sort` 可以看到在時間上比起 list_sort 來的較慢，而且在對更多的字串進行排序時，`top dwon` 的這個版本在時間變化的幅度上也顯的較大
### 效能比較
利用 [perf](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 指令來比較兩個排序演算法的 cache miss, cache-refernece, instrcution, cycles
```shell
$ sudo perf stat -r <times> -e cache-misses,cache-references,instructions,cycles,page-faults,branches ./qtest -f ./traces/<name>.cmd
```
可以在 `<times>` 中填入要重複執行的次數， `<name>`中填入所要執行的指令檔名稱
下方比較會連續執行 `5` 次並且計算平均值， `RAND` 設定為 `600000`
#### q_sort
```
Performance counter stats for './qtest -f ./traces/sort.cmd' (5 runs):
7626,0285 cache-misses # 63.52% of all cache refs ( +- 0.30% )
1,2005,0783 cache-references ( +- 0.41% )
29,4979,5909 instructions # 0.66 insn per cycle ( +- 0.07% )
44,4143,2806 cycles ( +- 0.56% )
2,1170 page-faults ( +- 0.00% )
4,5792,7144 branches ( +- 0.07% )
1.4424 +- 0.0106 seconds time elapsed ( +- 0.74% )
```
#### list_sort
```
Performance counter stats for './qtest -f ./traces/sort.cmd' (5 runs):
6467,3448 cache-misses # 65.98% of all cache refs ( +- 0.25% )
9802,1660 cache-references ( +- 0.05% )
27,7722,6241 instructions # 0.68 insn per cycle ( +- 0.07% )
40,8011,8980 cycles ( +- 0.23% )
2,1170 page-faults ( +- 0.00% )
3,8986,9605 branches ( +- 0.08% )
1.33843 +- 0.00338 seconds time elapsed ( +- 0.25% )
```
在相同的數量下進行兩種排序後所產生的結果可以看到在自己所撰寫的 `q_sort` 在 `cache misses` 的次數上明顯比較多，而且可以看到有比較多次對於記憶體的參照，也對應到使用 `top down` 的 `merge sort` 會一直的進行 `partition` 導致記憶體內容不斷的更動造成了更多次的記憶體的參照
也因為記憶體內容會被不斷的更換，也會使得 `cache` 發生 `thrashing` 的機率變高，這樣就可以知道以 `list_sort` 這樣的方式來進行排序，除了<s>記憶體更加友善</s> 可以減少記憶體的參照之外在指令數上以及所使用的 `cycle` 都更少，在 `branch` 的使用上也是比起 `top dowm` 的版本來的較少
:::danger
用字該精準！
:::
> 了解！ 已更改
> [name=shawn]
---
## 整合 Timsort 並與上述排序演算法進行比較
將 quiz1 的 `Timsort` 整合進入 lab0-c 中，使用與上述加入 `list_sort` 相同步驟，將 `Timsort` 加入到 queue.c 中，加入之後會發現與有與 `list_sort` 相同且可以重複利用的部份，像是 `merge_final` 以及 `merge_at` 中使用到的 `merge` ，以及 cmp 的函式可以用與 `list_sort` 相同 `ls_cmp` 來進行字串的比較，同樣也將 `priv` 刪除
在這邊也發現到 `build_prev_link` 為最後將環狀鍊結串列結構重新建立的函式，在 timsort 中 `if (stk_size <= 1)` 這個判斷會使用到，原本想將 `list_sort` 的 `merge_final` 進行重建連結的部份用 `build_prev_link` 函式來重構，但是我覺得 `list_sort` 在 merge_final 重建的迴圈中藉由在判斷到排序好的陣列時自己與自己比較來把優先權交出去的這邊很有特色所以決定保留不去更動
```c
if (unlikely(!++count))
ls_cmp(b, b);
```
#### Timsort 相較於 mergesort 的優點
1. 降低 `cache miss`
2. 降低記憶體開銷
3. 降低比較次數
### 隨機資料
先以隨機資料作為測試資料計算兩種排序的比較次數、時間再用 perf 觀察記憶體
### 比較次數
使用測驗 1 的 main 進行比較測試 `RAND` 設定為 1000，使其重複五次，在 `RAND` 設定為 10000 時也是相同結果
```
Creating sample
==== Testing timsort ====
Comparisons: 9591
List is sorted
==== Testing list_sort ====
Comparisons: 8707
List is sorted
Creating sample
==== Testing timsort ====
Comparisons: 9640
List is sorted
==== Testing list_sort ====
Comparisons: 8686
List is sorted
Creating sample
==== Testing timsort ====
Comparisons: 9464
List is sorted
==== Testing list_sort ====
Comparisons: 8706
List is sorted
Creating sample
==== Testing timsort ====
Comparisons: 9286
List is sorted
==== Testing list_sort ====
Comparisons: 8709
List is sorted
Creating sample
==== Testing timsort ====
Comparisons: 9249
List is sorted
==== Testing list_sort ====
Comparisons: 8692
List is sorted
```
| Timsort | comparisons | list_sort | comparisons |
|:-------:|:-----------:|:---------:|:-----------:|
| 1 | 9591 | 1 | 8707 |
| 2 | 9640 | 2 | 8686 |
| 3 | 9464 | 3 | 8706 |
| 4 | 9286 | 4 | 8709 |
| 5 | 9249 | 5 | 8692 |
可以明顯看到 `Timsort` 對隨機資料進行排序，整體比較次數大於 `list_sort`，此結果
### 時間
#### rand 100000
| Timsort | time |
|:-------:|:-----:|
| 1 | 0.075 |
| 2 | 0.088 |
| 3 | 0.070 |
| 4 | 0.076 |
| 5 | 0.079 |
#### rand 600000
| Timsort | time |
|:-------:|:-----:|
| 1 | 0.609 |
| 2 | 0.617 |
| 3 | 0.631 |
| 4 | 0.612 |
| 5 | 0.646 |
在時間方面可以看到在 `100000` 筆測試資料時的時間跟 `list_sort` 相比相當接近，但到了 `600000` 筆時就顯得稍差，但由於目前是使用隨機資料跟 timsort 假設的資料都是大致排序好前提不相符
### 效能比較
下方皆為 `Timsort` 的結果
```
Performance counter stats for './qtest -f traces/sort.cmd' (5 runs):
6306,4027 cache-misses # 64.69% of all cache refs ( +- 0.99% )
9748,4643 cache-references ( +- 0.76% )
29,0396,2473 instructions # 0.69 insn per cycle ( +- 0.10% )
42,2630,9182 cycles ( +- 0.34% )
2,1172 page-faults ( +- 0.00% )
4,2581,7808 branches ( +- 0.14% )
1.38267 +- 0.00709 seconds time elapsed ( +- 0.51% )
```
```
Performance counter stats for './qtest -f traces/sort.cmd' (5 runs):
6658,0858 cache-misses # 65.81% of all cache refs ( +- 2.24% )
1,0116,4395 cache-references ( +- 1.82% )
29,0435,0597 instructions # 0.63 insn per cycle ( +- 0.11% )
46,0576,7540 cycles ( +- 4.18% )
2,1171 page-faults ( +- 0.00% )
4,2627,6138 branches ( +- 0.20% )
1.5017 +- 0.0593 seconds time elapsed ( +- 3.95% )
```
先以隨機資料與先前的 `q_sort` 以及 `list_sort` 作比較，我在進行第一次測試時得到了在 `cache-misses` 以及 `references` 上 `Timsort` 得到了比較好的結果，在指令數以及 `cycle` 上需要花費較多的成本，而 `brancches` 則較少因此讓我好奇如果多作幾次是否會得到一樣的結果，但經過多次之後發現以隨機資料而言， `references` 的數量以及 `cache misses` 的差異可以到達 `3000000` 多筆的差距，再回去看測驗 1 時可以看到最下面對 `Timsort` 的說明有提到 `Timsort` 在合併 run 時會藉由 `Galloping mode` 來進行處理
而此動作對於大致排序好的序列會有較好的合併結果，但對於隨機資料而言若使用此機制要逐步的合併可能會導致效果不好，所以目前 `Timsort` 版本尚未完整，也缺少了對於 `Galloping mode` 的啟動機制也就是何時要進行 `Galloping mode`，所以可以看到目前的結果仍有較大幅度的變動
### 部份排序好資料
使用 1000 筆資料並且用 `rand` 決定隨機的區段也就是每次介於 x 到 y 之間並且讓排序好的區段由隨機的方式加入到鏈結串列的頭跟尾來獲得部份排序好的資料，使用此資料進行 `Timsort` 以及 `list_sort` 進行比較次數的比較
```
Creating sample
==== Testing timsort ====
Comparisons: 1965
List is sorted
==== Testing list_sort ====
Comparisons: 5524
List is sorted
Creating sample
==== Testing timsort ====
Comparisons: 1652
List is sorted
==== Testing list_sort ====
Comparisons: 5354
List is sorted
Creating sample
==== Testing timsort ====
Comparisons: 1915
List is sorted
==== Testing list_sort ====
Comparisons: 5536
List is sorted
Creating sample
==== Testing timsort ====
Comparisons: 1931
List is sorted
==== Testing list_sort ====
Comparisons: 5503
List is sorted
Creating sample
==== Testing timsort ====
Comparisons: 1957
List is sorted
==== Testing list_sort ====
Comparisons: 5516
List is sorted
```
```c
interval = rand() % (max_part - min_part + 1) + min_part;
```
可以看到對於部份排序好的資料而言使用 `Timsort` 進行排序，與隨機資料相比下來使用比較少的比較次數即可完成排序，而對於部份排序好的資料而言，`list_sort` 就得花上較多的比較次數來完成排序，也由此可見在符合 `Timsort` 作者所假設的大部分的資料都是部分排序好的假設，`Timosrt` 可以發揮比較好的優勢
| Timsort | comparisons | list_sort | comparisons |
|:-------:|:-----------:|:---------:|:-----------:|
| 1 | 1965 | 1 | 5524 |
| 2 | 1652 | 2 | 5354 |
| 3 | 1915 | 3 | 5536 |
| 4 | 1931 | 4 | 5503 |
| 5 | 1957 | 5 | 5516 |
---
## 整合 Tic-Tac-Toe
#### negamax
為 [minimax](https://youtu.be/l-hh51ncgDI?si=4K93BFmnkjOxVWmS) 經過數學方式改良，將判斷 `min` `max` 的部份以負號的方式來做取代，每次只要藉由負號就不用在判斷是在 `min` 層還是 `max` 層
#### mcts
主要分為三個步驟執行包含 1.`select` 2. `expand` `rollout` 3.`backprobagate` ，在 `select` 時會藉由 `UCB` 公式計算每個節點的值然後選取較大的節點，`expand` 跟 `rollout` 會藉由判斷當前的節點狀態，若是新的節點則會執行 `rollout` 即會從當前的狀態進行模擬模擬之後的行為直到計算出結果，而 `expand` 則是會產生新的 `child` 節點，最後一步 `backprobagate` 則是會將當前節點的結果向上 (當前節點的 `parent` 往上直到 `root` ) 傳遞
### hlist
在 `hlist` 中使用了`READ_ONCE` `WROTE_ONCE` 這兩個巨集，而這兩個巨集在核心中的 `list.h` 程式碼中同樣也使用很多次可以對照到 `lab0-c` 中的 `list.h` 可以發現其實功能為進行讀取、寫入這兩件事，作用為防止編譯器對程式碼進行最佳化
因為在某些情況編譯器對程式碼的順序進行最佳化時可能就會打亂對共享變數存取的順序導致最後得到錯誤的值，
```c
#define READ_ONCE(var) (*((volatile typeof(var) *)(&(var))))
#define WRITE_ONCE(var, val) \
(*((volatile typeof(val) *)(&(var))) = (val))
```
而在使用 [volatile](https://lwn.net/Articles/233479/) 時即告訴編譯器每次讀取都是從記憶體位置讀取，不從暫存器讀取，來防止因優化而得到跟預料中不同的值
在進行 hlist 整合時配合 list.h 的風格來進行實現，將 `READ_ONCE` 以及 `WRITE_ONCE` 改為一般的讀取以及寫入， hlist_del 將 next 以及 pprev 指標指向無效位址的部份也指向 `0x00100100` 、 `0x00200200`
### 將 ttt 整合至 lab0-c
[commit 909cd79](https://github.com/sysprog21/lab0-c/commit/909cd79542d5499677bee90cc870fdff3322612f)
依據作業要求將 `ttt` 中的內容加入到 qtest 中成為新的功能，首先可以看到 main 中將 `ttt` 依造 `define` 的內容可以分為使用 `reinforce learning`、`monte carlo tree search` 以及 `negamax` 的方式來執行，從 main 中抽出 `mcts` 的內容成為 `mcts_ttt`
在將執行 mcts 時會用到檔案加入到 lab0-c 中在加入之後要到 `makefile` 修改 `OBJS` 並加入 `agents` 的資料夾內容
在進行編譯時會出現這些問題，要一一處理，這次一開始也同樣碰到了要處理 cppcheck 的問題，而根據上次的經驗會發現 queue 中有在 `cppcheck` 設置 `supress` 的內容，因此在這次作業中就依照 queue 的設置方式到 `pre-commit.hook` 中將有發生問題的檔案一一作設置
```
agents/mcts.c:147:21: warning: Possible null pointer dereference: best_node [nullPointer]
int best_move = best_node->move;
^
agents/mcts.c:139:30: note: Assignment 'best_node=NULL', assigned value is 0
struct node *best_node = NULL;
^
agents/mcts.c:142:31: note: Assuming condition is false
if (root->children[i] && root->children[i]->n_visits > most_visits) {
^
agents/mcts.c:147:21: note: Null pointer dereference
int best_move = best_node->move;
^
agents/mcts.c:67:10: style: The scope of the variable 'win' can be reduced. [variableScope]
char win;
^
game.c:74:28: style: Parameter 'table' can be declared with const [constParameter]
int *available_moves(char *table)
^
mt19937-64.c:83:9: style: The scope of the variable 'i' can be reduced. [variableScope]
int i;
^
mt19937-64.c:85:21: style: The scope of the variable 'mag01' can be reduced. [variableScope]
static uint64_t mag01[2] = {0ULL, MATRIX_A};
^
mt19937-64.c:85:21: style: Variable 'mag01' can be declared with const [constVariable]
static uint64_t mag01[2] = {0ULL, MATRIX_A};
^
zobrist.c:63:21: error: Null pointer dereference: (struct zobrist_entry_t*)0 [nullPointer]
entry = hlist_entry(hash_table[i].first, zobrist_entry_t, ht_list);
^
Fail to pass static analysis.
```
還有發現在 game.c 以及 mt19937-64.c 有要求要將特定的變數設定為 const，照著去設定即可解決
### 新增 ai vs ai 功能
[commit c72fcce](https://github.com/ShawnXuanc/lab0-c/commit/c72fcce9c78f0edd2eca9791539be525fede1fc0)
在 ttt 中新增 ai vs ai 功能使用兩種不同的演算法包含一開始使用的 `mcts` 以及 `negamax` 並使用 `ttt_mode` 讓 option 可以變更切換使用玩家對上 ai 還是 ai 對上 ai
並新增時間顯示，在 `ai` 對上 `ai` 每回合顯示棋盤之前使其暫停 1 秒否則會一瞬間就把結果顯示出來
### coroutine
[commit 8972f0c](https://github.com/sysprog21/lab0-c/commit/8972f0c8eacd50291a566dc0d30515c6324625c7)
使用 `coroutine` 實作 ttt 加入 qtest 命令中，將任務分成三個部份包含進行勝利判定的任務在某方取得勝利後列印出步數並將結果清空，以及執行演算法的任務使用 `mcts` 以及 `negamax` 進行對役，在過程中會間隔一秒並列印出時間
研讀 [〈並行程式設計：排程器原理〉](https://hackmd.io/@sysprog/concurrent-sched#coroutine-%E4%B8%A6%E9%9D%9E%E6%96%B0%E6%A6%82%E5%BF%B5) 根據 [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 中的 coro.c 實現 coroutine 的運行，任務會在初次執行 `setjmp` 時回傳 `0` 並藉由 `task_add` 將任務加入到 list 中進行排程，並根據 `jmp_buf` 的值跳回所屬的 `setjmp` 位置並將 `setjmp` 的回傳值修改成非 `0`這邊設定為 `1`
```c
void schedule(void)
{
static int i = 0;
setjmp(sched);
while (ntasks-- > 0) {
struct arg arg = args[i];
tasks[i++](&arg);
printf("Never reached\n");
}
task_switch();
}
```
`coro.c` 的運行方式為由 `schedule` 進入 `task` 再藉由 `task` 中的第一個 if 判斷將任務加入到 `list` 中並使用 `longjmp(sched, 1)` 跳回到 `schedule` 將不同的任務的先加入一份到 list 中進行初次的排程，之後藉由 `task_switch` 中的 `longjmp(t->env, 1)`的值回所屬任務，回到所屬任務後會從第一個 if 的 `setjmp` 位置開始執行，也因為是藉由 longjmp 跳回的關係，所以回傳值為 `1` 不執行 if 中的內容從 `task = cur_task` 往下執行
```c
void algotask(void *arg)
{
...
if (setjmp(task->env) == 0) {
task_add(task);
longjmp(sched, 1);
}
task = cur_task;
for (;;) {
if (setjmp(task->env) == 0) {
int move = task->ai_algo(table, task->turn);
if (move != -1) {
table[move] = task->turn;
record_move(move);
}
task_add(task);
task_switch();
}
task = cur_task;
}
longjmp(sched, 1);
}
```
當進入到 `for(;;)` 中再次執行 `setjmp` 初次呼叫回傳值為 `0` 進入 if 內開始執行任務並將任務再次加入到 list 中進行排程並藉由 `task_switch` 切換到下一個任務，藉由這樣的方式將任務分別加入到排程中使 ttt 的運行可以不斷持續下去
[commit 59aefc8](https://github.com/ShawnXuanc/lab0-c/commit/59aefc88078792b5941ed3ab08771d5faebf108c)
為了讓任務之間的差異可以更加明確，讓判定結果的任務進行判定以及結果顯示，而演算法任務專心執行相對應的演算法
Sign in with Wallet
Connect another wallet