# 2024q1 Homework1 (lab0)
contributed by < `vestata` >

### Reviewed by `Vincent550102`
1. 善用已存在的巨集，如 `list_for_each`，以 `q_swap` 為例。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;
    struct list_head *li;
    element_t *e1, *e2;
    list_for_each (li, head) {
        e1 = list_entry(li, element_t, list);
        if (li->next == head)
            break;
        e2 = list_entry(li->next, element_t, list);
        char *tmp = e1->value;
        e1->value = e2->value;
        e2->value = tmp;
        li = li->next;
    }
}

2. 中英文間須有空白，與減少中英文交錯使用。 (#q_swap)
> 直觀的用for loop去travers鏈結串列，直到遇到 head 為止

建議更改為

> 直觀地用迴圈走訪整個環狀鏈結串列，直到遇到頭部為止

:::warning
1. 剛開始時對 LIST API 的熟悉程度不高，將針對此進行改善。改善完成後將會再進行記錄。
2. 謝謝你的建議，已更正。
> [name=vestata]
:::

### Reviewed by `weihsinyeh`
1. `q_sort` 中 graphviz 指標的線要整理，優點讓讀者清楚閱讀，好溝通。
2. 運用 Valgrind 排除 qtest 執行時的記憶體錯誤中，「沒有遇到奇怪的問題」更換用詞能更好溝通。缺點：讀者參考後，遇到問題不能確定這個問題是否較正常，已達到跟你一樣的效果。
3. 「當時為了在會更動串列順序的 traverse 一直出錯」提升漢語表達的能力。
4. 優點：有紀錄自己的所學。參考別人的程式碼會跟自己比較。
5. 比較 timsort, list_sort 的實驗中設計的測試資料Sparse，說明設計的由來。
6. 有些commit 有說明，有些沒有舉例 [commit f4eb110](https://github.com/vestata/lab0-c/commit/f4eb110fec611877a7be422e3bc8b91a6246e3ac) 。

:::warning
1. graphviz 當初撰寫過於混亂，會將此充新整理。
2. 謝謝你的建議，已更正。
3. 針對提出的句子，已更正，其他漢語表達缺失會再更正。
4. 謝謝你。
5. 由於另一組測試資料是 3/4 排序好的，其亂數部分集中在後 1/4，我希望透過 sparse 測試資料來觀察亂數在排序好的測試資料中平均分布的情形。目前的測試資料不夠全面，應該借鑑其他排序算法的測試設計，並加入最壞情況（worst case）的比較。改進完成後將進行更新。
6. 初期的 git commit 訊息未按規範撰寫，將在執行 `git rebase` 之後重新記錄。已更正。
> [name=vestata]
:::

## 實驗環境

$ 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:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  24
  On-line CPU(s) list:   0-23
Vendor ID:               GenuineIntel
  Model name:            13th Gen Intel(R) Core(TM) i7-13700
    CPU family:          6
    Model:               183
    Thread(s) per core:  2
    Core(s) per socket:  16
    Socket(s):           1
    Stepping:            1
    CPU max MHz:         5200.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4224.00

## 進度紀錄

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
> 收到
> [name=vestata]
:::

首先先明白整個 queue 的結構與其鏈結串列的結構。所依先著手於詳閱 ```list.h``` 裡面的內容，還有 ```queue.h``` 裡面的結構。
發現 ```queue.h``` 裡面有關於每一個函式的詳細介紹。按照敘述完成程式。

:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::

## 實作queue.c過程
### `q_new`
配置記憶體並將其 prev 跟 next 指向自己，可以直接使用 ```list.h``` 裡面的 ```INIT_LIST_HEAD``` 直接完成。

### `q_free`
將 queue 所佔用空間釋放掉，我閱讀文件看到 ```list_for_each_entry_safe``` 這是我第一次看到這種 ```macro``` (<s>才疏學淺</s>)，研究了一下發現是跟 ```for loop``` 一樣的用法，並在 traverse 鏈結串列式時，有 ```safe``` 這個指標，確保不會再 current node 被 remove 時不會出錯。這邊使用 ```list_for_each_entry_safe``` 來完成。並直接使用 ```queue.h``` 中的 ```q_release_element``` 來釋放串列中的記憶體。
最後再把 ```head pointer``` 釋放掉。

:::danger
改進你的漢語表達。
:::

void q_free(struct list_head *l)
{
if (!l)
return;

element_t *tmp, *safe;
list_for_each_entry_safe (tmp, safe, l, list) {
q_release_element(tmp);
}

free(l);
return;
}

### `q_insert_head`

input為 ```char``` 的陣列 ```s``` 所以要

bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;

element_t *tmp = malloc(sizeof(element_t));
if (!tmp)
return false;

tmp->value = s;
list_add(&tmp->list, head);
return true;
}

### `q_insert_head_tail`

bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;

element_t *tmp = malloc(sizeof(element_t));
if (!tmp)
return false;

tmp->value = malloc(strlen(s) + 1);
if (!tmp->value) {
free(tmp);
return false;
}

strcpy(tmp->value, s);
list_add_tail(&tmp->list, head);
return true;
}

看文件內容說明，他需要將 ```char s``` 的內容複製到 ```element->value``` 中
更新完之後 ```q_insert_head``` 加上 ```q_insert_head``` 合併後 ```make test``` 為36/100
在 ```git commit``` 時發生問題，說明中提到 ```strcpy``` 不會確認 buffer 長度，容易對記憶體受傷害。

:::danger
留意術語的使用：
1. string 的翻譯是「字串」
2. character 的翻譯是「字元」
3. allocate 的翻譯是「配置」
4. pointer 的翻譯是「指標」
5. null-terminator 的翻譯是「(字串) 結尾字元」
:::

改為使用 ```strndup``` 以下是期說明： ```strndup``` 會根據提供的<s>字符串</s> s 的長度分配足夠的記憶體空間（包括<s>空字符</s> 字串結尾字元），並返回一個指向新<s>分配</s> 配置記憶體的指標。如果記憶體分配失敗， ```strndup``` 會返回 ```NULL```

bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;

element_t *tmp = malloc(sizeof(element_t));
if (!tmp)
return false;

INIT_LIST_HEAD(&tmp->list);
tmp->value = strndup(s, strlen(s));
if (!tmp->value) {
free(tmp);
return false;
}

list_add_tail(&tmp->list, head);
return true;

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;

element_t *tmp = malloc(sizeof(element_t));
if (!tmp)
return false;

INIT_LIST_HEAD(&tmp->list);
tmp->value = strdup(s);
if (!tmp->value) {
free(tmp);
return false;
}

list_add_tail(&tmp->list, head);
return true;
}

我在這邊原本是使用 ```tmp->value = strndup(s, strlen(s))``` ，後來執行程式一直~~報錯~~ ```Attempted to free unallocated block.``` 花了很多時間 debug ，最後是參照 [vax-r](https://github.com/vax-r/lab0-c)的程式，改為使用 ```strdup``` 程式便正常執行了！
:::warning
為何 ```strndup``` 會~~報錯~~而 ```strdup``` 得原因待補。
:::


### `q_remove_head`
選擇直接調用 ```list.h``` 裡面的 ```list_empty``` 跟 ```list_del``` 發現 ```make test``` 效果超差...

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (list_empty(head))
return NULL;

element_t *tmp = list_first_entry(head, element_t, list);
list_del(&tmp->list);

return tmp;
}

回去看文件發現原來要把東西複製進去 ```*sp``` 裡面，重新修正程式碼。因為有相對應的緩衝區容量，所以直接使用 ```strncpy```

element_t *tmp = list_first_entry(head, element_t, list);
list_del(&tmp->list);

+ if (sp != NULL && bufsize > 0) {
+ strncpy(sp, tmp->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
}

這次error是 ```Attempted to free unallocated block.``` ，但是我這一段程式碼沒有free任何東西，目前還不知道問題出在哪，先繼續往下作答。(此問題為 ```q_insert_tail``` 的問題，已修正)

到現在 ```make test``` 的機制還有點沒有用明白，但是最優先需要解決 ```Attempted to free unallocated block.``` 的問題，應該從 ```q_free``` 下手：
    
### `q_size`
使用直觀的 ```list_for_each_safe``` 對該queue進行 ```traverse``` ，並宣告一 ```count``` 計數。

if (!head)
return 0;
struct list_head *tmp, *safe;
int count = 0;
list_for_each_safe (tmp, safe, head) {
count++;
}
return count;

### `q_delete_mid`
使用的是 ```jserv``` 上課所提過的 ```pointer to pointer``` 技巧去實作，並翻閱 ```2095. Delete the Middle Node of a Linked List Solved Medium Topics Companies``` 

使用一個 ```element_t *tmp``` 去指向 ```list_entry``` 所找到的記憶體位置。

花了一點時間將它實踐出來。相對於使用 ```pointer``` 節省了一個指標的使用量。

bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;

struct list_head **ind = &head->next;
for(struct list_head *fast = head; fast != head && fast->next != head; fast = fast->next->next)
ind = &(*ind)->next;

element_t *tmp = list_entry(*ind, element_t, list);
list_del(*ind);
free(tmp->value);
free(tmp);

return true;
}

使用 ```q_release_element```

element_t *tmp = list_entry(*ind, element_t, list);
list_del(*ind);
- free(tmp->value);
- free(tmp);
+ q_release_element(tmp);

### `q_delete_dup`
Implemented q_delete_dup using pointer-to-pointer technique, incorporating a jump pointer for skipping over duplicate entries. Node comparison is facilitated by a cmp function to assess values within nodes. Functionality is verified in qtests; however, a segmentation fault occurs during make test.

bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;

struct list_head **tmp = &head->next;
struct list_head *jump = (*tmp)->next;
while (*tmp != head) {
if (cmp(*tmp, jump) == 0) {
while (cmp(*tmp, jump) == 0) {
jump = jump->next;
}
*tmp = jump;
}
tmp = &(*tmp)->next;
jump = (*tmp)->next;
}
return true;
}

接下來針對 segmentation fault 去偵錯。
發現在 [1 1 1 1] 時會出現 segmentation fault. 
應該直接叫 list api ，鏈結沒有處理好。

:::info
目前還是卡住，先跳過
:::
觀摩 [nosba0957](https://github.com/nosba0957/lab0-c/blob/master/queue.c) 同學的實作手法。
我在實作時遇到的問題是當有遇到 duplicate 時，在刪除第一個 duplicate 遇到很多困難，這迫使我添加了多個錯誤處理條件，結果導致了段錯誤（segmentation fault），同學使用一個 bool dup 很好的解決我的問題。故我用原本 list 的結構實作相同的手法。


### `q_swap`
剛好 ```24. Swap Nodes in Pairs``` 是以前寫過的題目
直觀地用迴圈走訪整個環狀鏈結串列，直到遇到頭部為止。

for (one = head->next, two = one->next; one != head && two != head;
one = two, two = two->next)

剩下就是將 ```one``` , ```two``` 前後的節點交錯接上，便完成 swap 的動作。

### `q_reverse`
回去翻閱 ```list.h``` 發現 ```list_for_each_safe``` 裡面的 node , safe 的宣告與 ```q_reverse``` 所要求的 traverse 形式類似，所以直接調用 ```list_for_each_safe``` 這個函式。

struct list_head *tmp, *safe;
list_for_each_safe(tmp, safe, head) {
tmp->next = tmp->prev;
tmp->prev = safe;
}

所以在這邊直接將 tmp 的 next 指向 prev , tmp 的 prev 指向 next (在這邊是 safe )
 loop 執行完， tmp 會指到 head 的位置。
完成 head 鏈結到第一個 node ，便完成此函式

### `q_reverse_k`
按照文件先排除 queue 為 NULL 或是空，還有只有單節點的情況

1. 宣告一個 tail 去找第 k 個 element
2. 對這一段做 q_reverse
3. 將這一段的尾端銜接好
4. 去找下一段

:::warning
TODO: 運用 List API，撰寫更精簡的程式碼。
:::

再回去詳閱 list.h 的內容，一開始遇到的問題是如何去從原本鏈結串列去切割出要做 reverse 的段落，原本是使用 pointer to pointer 的方式去找起始點，並往後找切割之 tail ，之後在看 [2023 年 Linux 核心設計/實作課程第一次作業檢討](https://hackmd.io/@sysprog/linux2023-lab0-review) ，看到<s>同學的方法</s> [yanjiew1
](https://github.com/yanjiew1/lab0-c) 實在很好，所以直接放棄原本的作法...

:::danger
清楚標註你參照的 GitHub 帳號名稱
> 收到，已修正
> [name=vestata]
:::

其中修補我原本的程式的地方有三個主要重點：
1. 

list_for_each_safe(tmp, safe, head) {
if (--count)
continue;

當時因為在會改變串列順序的遍歷過程中出錯，所以直接使用 `list_for_each_safe`，並透過 `if` 語句加上 `continue`，來彌補我原先所寫的 for 迴圈的不足。這個技巧值得深入了解並記住。
2. 
使用 LIST_HEAD 直接初始節點，之後對它直接做 list_cut_position 剛好直接調用到 cut, tmp 一開始我認為 tmp 因為 reverse 會換到該 reverse 的起點，然回頭看 list_for_each_safe 其中他的 ```node = safe, safe = node->next``` 就會可以確保 tmp 在反轉串列的下一個繼續 traverse。是一開始讀 list.h 沒有想到的點，銘記在心，獲益良多。
之後變進行 `q_reverse` 跟 `list_splice` ，最後再使用 `cut = safe->prev;` 更新下一個反轉串列的起始位置。

:::danger
段落中的程式碼標示應使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個
> 收到，已更正
> [name=vestata]
> 沒做到的事，不要輕易宣稱，繼續改！
:::


### `q_sort`

:::danger
本處你指涉者是「測試項目」(test item)，而非廣義的「資料」，工程人員說話要精準。
> 收到
> [name=vestata]
:::

想要先觀察 ```make test``` 的<s>測資</s> 測試項目，實作一個 bubble sort

digraph ele_list {
rankdir=LR
node[shape=record]

head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
current[color="white"]
next[color="white"]

head:right:e -> node4:w
node4:left:w -> head:e
node4:right:e -> node3:w[color="white"]
node4:right:e -> node2:w[color="red"]
node3:left:w -> node4:e[color="white"]
node3:left:w -> head:e[color="red"]
node3:right:e -> node2:w
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
current -> node4:n
next -> node3:n

}

void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;

struct list_head *tmp;
for (tmp = head->next; tmp != head; tmp = tmp->next){
// 以下是bubble sort 內迴圈
struct list_head *tmp2;
for (tmp2 = head->next; tmp2->next != head;
tmp2 = tmp2->next) {
struct list_head *current = tmp2;
struct list_head *next = current->next;
element_t *currElem = list_entry(current, element_t, list);
element_t *nextElem = list_entry(next, element_t, list);
// 做swap
if (strcmp(currElem->value, nextElem->value) > 0) {
current->prev->next = next;
current->next = next->next;
next->prev = current->prev;
current->prev = next;
next->next->prev = current;
next->next = current;
}
}
}
return;
}

一開始這樣做的時候沒有考慮到用 for loop 他在 swap 完兩個節點之後他的順序會亂掉，所以這邊不能使用 for loop，會報錯 Segmentation fault occurred 

void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;

struct list_head **tmp;

- for (tmp = head->next; tmp != head; tmp = tmp->next){
+ for (tmp = &head->next; *tmp != head; tmp = &(*tmp)->next){
// 以下是bubble sort 內迴圈
struct list_head *current;

for (current = *tmp; current->next != head;
current = current->next) {
struct list_head *next = current->next;
if (next == head)
break;
element_t *currElem = list_entry(current, element_t, list);
element_t *nextElem = list_entry(next, element_t, list);
// 做相鄰swap
if (strcmp(currElem->value, nextElem->value) > 0) {
current->prev->next = next;
current->next = next->next;
next->prev = current->prev;
current->prev = next;
next->next->prev = current;
next->next = current;

current = current->prev;
}
}
}
return;
}

:::danger
使用 `git diff` 或 `diff -u` 命令來產生程式碼之間的變異列表，不要憑感覺填入，注意位移量。
:::

改為使用 pointer to pointer 並在觸發 swap 時加上 current = current->prev ;維持順利順序
最後還是出現 error

ERROR: Not sorted in ascending order
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient

發現在邏輯上實作 bubble sort 出錯，但是目前無力更改，應該依照老師引導使用```lib/list_sort.c```的

:::danger
文字訊息請避免用圖片來表示，否則不好搜尋和分類
> 收到，已更正
> [name=vestata]
:::


以下直接在 lab0 中實作 ```lib/list_sort.c```
1. 將 ```priv``` 移除
文件中指出： ```@priv: private data, opaque to list_sort(), passed to @cmp```
在 lab0 實作我認為不會使用到 ```priv``` 故先將它移除
2. 從 ```list_sort.h``` 擷取以下程式碼

typedef int __attribute__((nonnull(1,2))) (*list_cmp_func_t)(
const struct list_head *, const struct list_head *);

3. 從 ```/include/linux/compiler.h``` 擷取 likely 的巨集宣告
4. 撰寫 compare function : 依照文件中的意思是比較兩個節點中的字串去做比較，所以使用 strcmp

int cmp(const struct list_head *a, const struct list_head *b)
{
    element_t *a_ele = container_of(a, element_t, list);
    element_t *b_ele = container_of(b, element_t, list);
    return (strcmp(a_ele->value, b_ele->value));
}

5. 引入 merge(), merge_final(), list_sort()
6. 完成 q_sort()

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    list_sort(head, cmp);
    return;
}

### `q_ascend`
由於限定函式回傳 int ，所以只能 in-place 完成的個操作。

繼續完成這部分，為了想壓在 $O(N)$ 所以弄巧成拙，一直出現 segmentation fault ，先用兩個 while loop 使用 $O(N^2)$的時間複雜度實作出來！

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    struct list_head *first = head->next;
    struct list_head *second = head->next->next;

    while (first != head) {
        while (second != head) {
            element_t *one = list_entry(first, element_t, list);
            element_t *two = list_entry(second, element_t, list);
            if (strcmp(one->value, two->value) < 0) {
                list_del(second);
                second = first->next;
            } else {
                second = second->next;
            }
        }
        first = first->next;
        second = first->next;
    }
    return q_size(head);
}

參考了 YouTube 頻道 [Programming Pathshala](https://www.youtube.com/watch?v=SicFs7BGDyY&ab_channel=ProgrammingPathshala) 提出的算法，我採用了一個新的策略來處理升序（ascend）和降序（descend）的問題。此方法的核心思想是先對 queue 進行反轉，這樣做可以讓我們更容易地按照升序或降序的要求來刪除不符合條件的節點。

以下是以值為整數（integer）進行降序排序的示例步驟：

1. 初始隊列狀態：5 -> 2 -> 13 -> 3 -> 8
2. 首先，對隊列進行反轉：8 -> 3 -> 13 -> 2 -> 5
3. 在反轉後，我們可以將隊列視為每個節點都是其後所有節點中最大值的表示形式：8 -> 8 -> 13 -> 13 -> 13
4. 接著，刪除不滿足降序要求的節點：8 -> 13
5. 最後，再次對隊列進行反轉以恢復到其原始順序，得到最終的降序隊列：13 -> 8
透過這種方法，能夠有效地解決了在單次遍歷中進行升序或降序排序的問題。

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;
    if(list_is_singular(head))
        return 1;

    q_reverse(head);
    struct list_head *tmp=head->next;
    while (tmp->next!=head){
        if(cmp(tmp, tmp->next) > 0){
            element_t *ptr = list_entry(tmp->next, element_t, list);
            list_del(tmp->next);
            q_release_element(ptr);
        }else{
            tmp = tmp->next;
        }
    }
    q_reverse(head);
    
    return q_size(head);
}

### `q_merge`
閱讀敘述，主要功能是將多個已排序的隊列合併成一個單一的隊列，並可以根據參數決定是按升序還是降序排列。
因為要求將所有隊列合併到第一個隊列中，所以我採取的策略是先將所有隊列加入到第一個隊列裡，然後直接使用 q_sort 進行排序，這樣可以省略合併過程中較為複雜的部分。雖然這種做法與傳統的合併演算法不完全對應，但它有效地簡化了程式撰寫的複雜度。

int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return q_size(list_entry(head->next, queue_contex_t, chain)->q);

    queue_contex_t *tmp = list_entry(head->next, queue_contex_t, chain);
    struct list_head *ptr = head->next->next;
    while(ptr!=head){
        queue_contex_t *tmp2 = list_entry(ptr, queue_contex_t, chain);
-        list_splice(tmp2->q, tmp->q);
+        list_splice_init(tmp2->q, tmp->q);
        ptr = ptr->next;
    }
    q_sort(tmp->q, descend);

    return q_size(tmp->q);
}

在合併過程中，若是要記得初始化加入的串列不然會出現 segmentation fault.

## 提供新的命令 `shuffle`

要新增新的指令 'shuffle' ，須完成以下步驟：
1. 新增 `q_shuffle` 於 `queue.q`
- 利用 Fisher–Yates shuffle 演算法
閱讀 [Fisher–Yates shuffle wiki](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Pencil-and-paper_method) 中依照他的 modern method 去進行實作。
用一個指標 back 指在串列最後一個，然後用一個 0~(size-1) 隨機數去找要 swap 的節點，將 cur, back 做 swap ，每一輪都會逐漸縮減 back 並減隨機數 % 的取值，以完成shuffle的實作。

void swap(struct list_head *node_1, struct list_head *node_2)
{
    if (node_1 == node_2)
        return;
    struct list_head *tmp1 = node_1->prev;
    struct list_head *tmp2 = node_2->prev;
    if (node_1->prev != node_2) list_move(node_2, tmp1);
    list_move(node_1, tmp2);
}

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    int len = q_size(head);
    int random;
    struct list_head *back = head->prev;
    struct list_head *cur = head->next;
    for(;len>0; len--){
        random = rand() % len;
        if(!random) continue;
        while(--random){
            cur = cur->next;
        }
        swap(cur, back);

        back = cur->prev;
        cur = head->next;
    }
}

2. 在 qtest.c 新增 `do_shuffle`

static bool do_shuffle(int argc, char *argv[])
{
    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();
    if (q_size(current->q) < 2)
        report(3, "Warning: Calling shuffle on single queue");
    error_check();
    if (exception_setup(true))
        q_shuffle(current->q);
    q_show(3);
    return !error_check();
}

3. 修改 qtest.c 的 console_init()

更改之後使用 [lab0(D)](https://hackmd.io/@sysprog/linux2024-lab0-d#M01-lab0) 中的 python 腳本命名為 test_shuffle.py 的到以下結果：

Expectation: 41666
Observation: {'1234': 0, '1243': 0, '1324': 0, '1342': 0, '1423': 0, '1432': 0, '2134': 0, '2143': 0, '2314': 0, '2341': 0, '2413': 0, '2431': 0, '3124': 1000000, '3142': 0, '3214': 0, '3241': 0, '3412': 0, '3421': 0, '4123': 0, '4132': 0, '4213': 0, '4231': 0, '4312': 0, '4321': 0}
chi square sum: 23000368.0061441

在結果上有明顯的錯誤。使用 `./qtest` 也遇到 shuffle 結果一直重複的問題。

在 git commit 的過程中遇到不能修改 queue.h 的 checksum 限制，所以需要將在 qtest.c, queue.h 所修改的地方刪掉，這在測試的時候會相對複雜。
 - - -
問題依舊。測試在 shuffle 多次便會遇到 ```ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient```的錯誤。
再想辦法改進。
- - -
再次回頭檢查程式:針對 `swap()` 函式進行修改，發現在之前撰寫的 swap 函式有誤，以下已更正。

struct list_head *tmp1 = node_1->prev;
struct list_head *tmp2 = node_2->prev;
- if (node_1->prev != node_2)
- list_move(node_2, tmp1);
- list_move(node_1, tmp2);
+ if (node_1 != tmp2)
+ list_move(node_1, tmp2);
+ list_move(node_2, tmp1);

這邊發現 ```--random``` 的誤用，已更正

void q_shuffle(struct list_head *head)
int len = q_size(head);
struct list_head *back = head->prev;
struct list_head *cur = head->next;
- for (; len > 0; len--) {
+ while (len) {
int random = rand() % len;
- if (!random)
- continue;
- while (--random) {
+ while (random) {
cur = cur->next;
+ random--;
}

- 最後還是維持 [Fisher–Yates shuffle wiki](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Pencil-and-paper_method) 中提到的 modern method 去完成實作。

- 以下為 [lab0(D)](https://hackmd.io/@sysprog/linux2024-lab0-d#M01-lab0) 提供的 python 腳本所執行的結果。

Expectation: 41666
Observation: {'1234': 41317, '1243': 41362, '1324': 41596, '1342': 41267,
'1423': 41837, '1432': 41705, '2134': 41593, '2143': 41766, '2314': 41800,
'2341': 41568, '2413': 41735, '2431': 41452, '3124': 42133, '3142': 41792,
'3214': 41592, '3241': 41712, '3412': 41432, '3421': 41667, '4123': 41706,
'4132': 41504, '4213': 42024, '4231': 41953, '4312': 41758, '4321': 41729}
chi square sum: 25.192003072049154

![Figure_1](https://hackmd.io/_uploads/SkfsLRSCT.png)

> commit [dc22cf3](https://github.com/vestata/lab0-c/commit/dc22cf33ab7a5cc617d723b2f067128a807f8a93)


## 研讀 `lib/list_sort.c`

### 導讀
- 用 bottom up 實作 merge sort 對 cache 較友善，因為過程中就是一直合併，cache 使用機率很高。
- top down 做 partition 對 cache 不友善

:::warning
解釋為何對 cache 不友善。
:::

### 演算法
<s>
以下很多內容皆引用自[課程講義](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e)：
</s>

:::danger
專注在你的洞見。
:::

由 檢查```count+1``` 後是否為 $2^k$ 結尾
- 如果是的話就不合併
- 如果不是的話就合併

### merge

__attribute__((nonnull(2, 3, 4))) static struct list_head *
merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)
{
// cppcheck-suppress unassignedVariable
struct list_head *head, **tail = &head;

for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}

在這邊 ```cmp(priv, a, b) <= 0``` $\equiv$ ```a<=b```
這邊 ```else``` $\equiv$ ```a>b``` 
這便可以直接在 lab0 做修改

### merge_final



### list_sort

__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``` 使以 ```cmp``` 的參數傳入，如果在 ```lab0``` 的部份是不用用到的

所以在這一段，以 ```lab0``` 的角度，需要的 input 只有 ```head```

> list 指向 head 的第一個節點， pending 指向 NULL，先檢查是否沒有任何元素或只有一個元素
> [name=jserv]

**以上程式作到的，實作 q_sort 會遇到：**
- [ ] list 指向 head 的第一個節點，pending 指向 NULL
- [ ] 先檢查是否沒有任何元素或只有一個元素
- [ ] 然後將 head 前一個節點指向的下一個位置指向 NULL
- [ ] 將雙向 linked list 變成單向。

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);

以下著重分析這段程式碼：

for (bits = count; bits & 1; bits >>= 1)
            tail = &(*tail)->prev;

這一段 bitwise 操作可以理解為它根據 ```count``` 後面有多少0，讓 tail 要往 next 移多少。
往下：

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;
        }

:::danger
查閱 GCC 手冊和計算機組織/結構的教科書，從 branch prediction 的角度去闡述。
:::

但是關於 ```likely()``` 實作內容待補。

所以到了非$2^k$，便進行合併。

:::warning
這邊有一點點怪，要補一下
:::

### 圖解實作
用自己的腦袋過一遍。
#### count 0->1
- ```struct list_head *list = head->next```
- ```pending``` = NULL

digraph ele_list {
rankdir=LR
node[shape=record]

head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending[color="white"]
NULL[color="white"]

head:right:e -> node4:w
node4:left:w -> head:e
node4:right:e -> node3:w
node3:left:w -> node4:e
node3:right:e -> node2:w
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node4:n

pending -> NULL
}

進入while loop

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending[color="white"]
    NULL[color="white"]
    tail[color="white"]
   
    head:right:e -> node4:w
    node4:right:e -> node3:w
    node3:left:w -> node4:e
    node3:right:e -> node2:w
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node4:n
    
    tail -> pending -> NULL
}

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending[color="white"]
    tail[color="white"]
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:left:w -> node4:e
    node3:right:e -> node2:w
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node3:n
    
    tail -> pending -> node4
    
}

#### count 1->2
一樣的操作，所以直接貼上結果

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail[color="white"]
    
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:left:w -> node4:e
    node3:right:e -> node2:w[color="white"]
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node2:n
    tail -> pending -> node3:n
}

#### count 2->3
會進行 merge

digraph ele_list {
rankdir=LR
node[shape=record]

head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail[color="white"]
a[color="white"]
b[color="white"]

head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:left:w -> node4:e
node3:right:e -> node2:w[color="white"]
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node2:n
tail -> pending -> node3:n
a -> node3:n
b -> node4:n
}

呼叫 ```merge``` 

digraph ele_list {
rankdir=LR
node[shape=record]

head [label="head|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
pending [label="pending", style="normal", color="white"]
tail[color="white"]
a[color="white"]
b[color="white"]

head:right:e -> node4:w
node4:right:e -> node3:w[color="white"]
node3:left:w -> node4:e
node3:right:e -> node2:w[color="white"]
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node2:n
pending -> node3:n
tail -> node3:right
a -> node2:n
b -> node4:n
}

:::warning
這邊呼叫merge就看不懂了...先直接實作看看
:::

:::danger
1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
2. 留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)及[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
3. 改進你的漢語表達
4. 避免說「報錯」，改用其他更明確的詞彙
5. 不要說「才疏學淺」，誠實面對自己，不用自憐
> 收到
> [name=vestata]
:::

## 運用 Valgrind 排除 qtest 執行時的記憶體錯誤

:::danger
摘錄關鍵訊息即可。
> 收到
> [name=vestata]
:::

test 1~16 沒有出現記憶體錯誤，容易出錯的地方是 test 17 ，在本地電腦跑有時後會過有時候不會過，檢查一下哪裡出錯。
先推斷是 strdup ，嘗試改為 strncpy 以縮小複製的 buffsize.

在 github 的 make test 依然過不了。 95/100

執行完 `make valgrind` 除了 test trace-17-complexity 這邊有出現錯誤 （<s>要修正 dudect</s> 已修正 dudect 的錯誤），其他的地方沒有發現錯誤。

### 透過 Massif 視覺化 "simulation" 過程中的記憶體使用量

選用 `traces/trace-eg.cmd` 
輸入以下命令以生成 massif 檔案：

valgrind --tool=massif ./qtest -f traces/trace-eg.cmd

會生成 `massif.out.<num>` 的檔案
使用 `massif-visualizer` (需要下載)查看檔案：
![t](https://hackmd.io/_uploads/rJutsAICa.png)


---

##  論文〈Dude, is my code constant time?〉

:::danger
注意用語，以你的認知書寫你在這篇論文得到的啟發。
$\to$ [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
> 好的收到，馬上更正
> [name=vestata]
:::

> [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)

這篇論文從時間攻擊去做介紹，利用程式執行時間的差異來提取密碼等重要資料。所以介紹 dudect 的個方法已檢測程式是否在常數時間（constant time）完成。

在 Approuch 解釋其實作方法：
1. 取 2 種 input data type , fix-vs-random
    - 在固定對比隨機的測試中，第一類輸入數據被固定為一個常數值，而第二類輸入數據則在每次測量時隨機選擇。
2. Apply post-processing
    1. Cropping
        - 典型的執行時間分佈可能正偏斜，這種偏斜可能由測量誤差、操作系統或其他外部活動中斷主進程造成。在這種情況下，丟棄那些超過某個固定、與類別無關的閾值的測量數據。
3. Apply statistical test
    - 使用 `Welch’s t-test` 與 cropping 完的結果去比對時間分佈是否相等。

### 修正 `lab0` 中的 dudect

- 在 [作業要求](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-f) 中提到
> 在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。

- 首先先去檢測在 [oreparaz / dudect](https://github.com/oreparaz/dudect.git) 中 percentile 負責處理什麼東西。

- 發現在 `dudect.h` 大量使用到 `percentile` ，用於實現測量數據的 cropping，。裁剪過程的目的是移除那些異常大的計時值，這些可能由於操作系統中斷或其他非程序本身的活動造成的。這樣的測量值可能會扭曲統計分析的結果。
- 在 `lab0-c/dudect/` 中分別找到 `constant.c`, `fixture.c`, `ttest.c` 分別對應到上面 approach 提到的三個實作方法。主要目標為將 percentile 加入 `fixture.c` 之中。

- 將 percentile 加入 `lab0-c/dudect/fixture.c`:
1. 加入 percentile 

#define ENOUGH_MEASURE 10000
+#define DUDECT_NUMBER_PERCENTILES (100)
#define TEST_TRIES 10

-static t_context_t *t;
+/* perform this many tests in total:
+ - 1 first order uncropped test,
+ - DUDECT_NUMBER_PERCENTILES tests
+ - 1 second order test
+*/
+#define DUDECT_TESTS (1 + DUDECT_NUMBER_PERCENTILES + 1)
+
+static t_context_t *t[DUDECT_TESTS];

2. 在 `dudect.h` 中它將 `dutect_ctx_t` 中的資料打包，而在 `lab0-c` 是分開撰寫的，所以先針對每個對應的變數添入更新的
3. 加入 `cmp`, `percentile`, `prepare_percentiles`
4. 修改 `update_statistics` 
5. 新增 `max_test()` 以獲取差距最大的樣本
6. `doit()` 相對於 `oreparaz / dudect` 中的 `dudect_main`，這邊填入相對應的參數，並會放棄第一批資料作為暖身。

bool ret = measure(before_ticks, after_ticks, input_data, mode);
+ bool first_time = percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
differentiate(exec_times, before_ticks, after_ticks);
- update_statistics(exec_times, classes);
- ret &= report();
+ if (first_time) {
+ // throw away the first batch of measurements.
+ // this helps warming things up.
+ prepare_percentiles(percentiles, exec_times);
+ } else {
+ update_statistics(exec_times, classes, percentiles);
+ ret &= report();
+ }

> commit [3fcd442](https://github.com/vestata/lab0-c/commit/3fcd442c9f6cff5b9caa8a160df79c925f275b0b)

## 比較 timsort, list_sort

本次實驗的場合設定在 [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1) 所提供的 timsort 程式碼基礎上。考慮到這邊有已撰寫好的 compare 程式，該函數已實現比較次數的記錄，且可以使用已寫好的 designated initializers 佈置實驗比較。且由於我在 `lab0-c` 的實作方法直接採用 `list_sort` 所以只針對 timsort, list_sort 做比較。

1. 將 `list_sort` 整合進去
2. 修改 main 程式

test_t tests[] = {
{.name = "timesort", .impl = timsort},
+ {.name = "list_sort", .impl = list_sort},
{NULL, NULL},
};

3. 加入 argc 與 argv 參數以方便比較兩個排序方法

- while (test->impl) {
- printf("==== Testing %s ====\n", test->name);
...
- test++;
+ for (test_t *test = tests; test->impl != NULL; test++) {
+ if (strcmp(argv[1], test->name) == 0) {
...
+ break;
+ }

在 `perf list` 中選擇查看要比較的項目，選出 cache-misses, cpu-cycles, branch-misses, task-clock 作為比較項目。
接下來使用 `perf stat --repeat=10 -e cache-misses,cpu-cycles,branch-misses,task-clock ./main timsort` 對其做比較 （先放上來紀錄，等等會整理）

Performance counter stats for './main timsort' (10 runs):

331,9122 cpu_core/cache-misses/ ( +- 2.89% )
<not counted> cpu_atom/cache-misses/ ( +-100.00% ) (0.00%)
21,7076,8570 cpu_core/cpu-cycles/ # 5.146 GHz ( +- 1.21% )
<not counted> cpu_atom/cpu-cycles/ ( +-100.00% ) (0.00%)
1924,3092 cpu_core/branch-misses/ ( +- 0.20% )
<not counted> cpu_atom/branch-misses/ ( +-100.01% ) (0.00%)
421.86 msec task-clock # 0.999 CPUs utilized ( +- 1.19% )

0.42223 +- 0.00501 seconds time elapsed ( +- 1.19% )

以下比較省略詳細資訊，皆已 10 runs , 每 run 1000000 筆資料作為比較。

> commit [213ab43](https://github.com/vestata/timsort/commit/213ab43e7a41e248cd5ca404d79dc36dac76dcbf)

### 比較

#### random

| -          | timsort      | list_sort    |
| ----------------- | ------------ | ------------ |
| cache-misses      | 331,9122     | 303,7609     |
| cpu-cycles        | 21,7076,8570 | 19,3518,8604 |
| branch-misses     | 1924,3092    | 1933,1920    |
| task-clock        | 421.86 msec  | 378.49 msec  |
| comparisons(avg.) | 20535167     | 18687602     |

在這裡我們發現，在隨機數據條件下，`timsort` 的排序效能低於 `list_sort`。`timsort` 的適用場景更偏向於大部分數據已經排序好的情形。另外，在 [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1) 提供的 `timsort` 實現中，缺少了二分插入排序（binary insertion sort）和 galloping mode，這些遺漏是造成性能不佳的原因。

- 故在以下新增 2 種新的測資(皆 1000000 筆):


#### Partial_ordered
- partial : 四分之三的資料是已排序好的，四分之一為亂數
    
| -                 | timsort     | list_sort   |
| ----------------- | ----------- | ----------- |
| cache-misses      | 300,6993    | 264,6626    |
| cpu-cycles        | 5,9107,1787 | 7,6476,5017 |
| branch-misses     | 434,3442    | 435,1108    |
| task-clock        | 115.91 msec | 149.41 msec |
| comparisons(avg.) | 6224795     | 12120568    |

在部分有序（partial_ordered）的實驗中，可以觀察到 timsort 在已經排序好的數據集上具有明顯的優勢，尤其在比較次數上，timsort 相較於 list_sort 只需約一半的比較量。
comparisons 與其他性能指標（如 cache-misses、cpu-cycles、branch-misses、task-clock）的主要差異在於，它直接反映了排序算法在運行過程中進行元素比較的次數，而不是測量硬體層面或執行時間的指標。反映了算法本身的特性，獨立於執行它的硬件環境。

#### Sparse
- sparse : 每 20 個元素會有一個亂數

| -                 | timsort     | list_sort   |
| ----------------- | ----------- | ----------- |
| cache-misses      | 282,4802    | 265,1732    |
| cpu-cycles        | 6,3614,9481 | 7,0134,8841 |
| branch-misses     | 95,3924     | 119,3419    |
| task-clock        | 125.14 msec | 138.07 msec |
| comparisons(avg.) | 16916065    | 18079052    |

在 sparse 資料的實驗中，我們可以看到，由於每 20 筆數據中就有一筆受到隨機數的影響，sparse 資料與部分有序（partial_ordered）資料相比，在沒有特別設計 minrun 的情況下，`timsort` 的排序優勢不明顯。因此，在比較 `timsort` 和 `list_sort` 的結果時，兩者表現相近。在比較效能、硬體層面以及執行時間的指標上，`timsort` 略優於 `list_sort`。

> commit [b01df5c](https://github.com/vestata/timsort/commit/b01df5cd9a2a98ce8647a683f5a3cd9abb453419)

:::info
TODO 
實驗使用的是 [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1) 所提供的 timsort 版本，尚有缺陷。需再引入以下：
binary insertion sort, galloping mode
才可以比較出真實 timsort 與 list_sort 的效能差距
:::

## 整合 tic-tac-toe
### 整合 hlist.h

擷取自 [2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2) 中 leetcode 105, leetcode 146 與 hlist 相關的程式碼抽出，成為 hlist.h

> commit [02ddb0e](https://github.com/vestata/lab0-c/commit/02ddb0e771fe9cf7e3e08939bb004ebad64b8e86)

### 整合進 qtest

回去觀摩 [lab0-b](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-b) 裡面新增 hello 的步驟，在這邊使用相同的方式將 ttt 加入 qtest 之中。

對 qtest 程式進行了修改，新增了一個名為 'ttt' 的命令。這項改動涉及將 jserv/ttt 的 main.c 文件的內容整合到 qtest 的 do_ttt() 函數中。這樣的修改使得 Tic-Tac-Toe 遊戲能夠在 qtest 環境中執行。

> commit [86fd20f](https://github.com/vestata/lab0-c/commit/86fd20fc97c7062c5ccc2479563261ee46bed971)

#### 使用 MCTS 算法

在 `jserv/ttt` 專案的 main.c 中，有三種算法可供選擇編譯。採用 MCTS 算法，因此將其他算法相關的程式先行刪除。接下來的任務是修改 `lab0-c/makefile` 以成功編譯 mcts.c 和 mcts.h。由於之前步驟中移除了其他算法，相關的編譯標誌（flag）也從 `jserv/ttt/makefile` 中刪除了。

為了確保 git commit 能通過 cppcheck 檢查，對 mcts.c 進行了必要的修正。

> commit [d0a7104](https://github.com/vestata/lab0-c/commit/d0a7104eca35681428d5efc27c754d90e94ac68a)

:::info
TODO
對 makefile 理解不足，在這邊依照 dudect 的步驟撰寫。建立一個 .agents 目錄
**待理解**
:::

#### 定點數取代浮點數運算

首先著手修正 `calculate_win_value`、`simulate`、和 `backpropagate` 這些函式，並且修改 `uct_score` 和 `exploration_factor`，將其中的 `double` 類型運算更改為 `int` 類型。定點數運算中的 `SCALE_FACTOR` 暫定設為 1000。

:::info
TODO
1. 討論 `SCALE_FACTOR` 應該定義為多少。
2. 目前尚無法驗證浮點數與定點數運算的性能差異。預計在完成電腦對戰電腦的模式後，將收集的測試資料寫入 `/trace` 目錄，再進行效能比較測試。
3. 應該透過 `fixed_power_int` 函式來進行定點數運算的理解和實現。
:::

> commit [ff0e896](https://github.com/vestata/lab0-c/commit/ff0e896961d7181e7cf3ece011c32a6a97b58cef)

### 擴充 `ttt` 命令
在 qtest 引入新的 option
- 新增 Human vs. Computer 命名為 hc，Computer vs. Computer 命名為 cc（初始模式為 hc）。
- 目前設定為每下一步都會將將步驟顯示在棋盤上。

> commit [75fa689](https://github.com/vestata/lab0-c/commit/75fa689d098fef99643592450ae449afa5202b6d)

- 多次使用 `ttt cc` 命令，會出現步法相同的情況，所以在 `mcts.c` 新增 `time.h` 作為隨機種子。

> commit [c0ca984](https://github.com/vestata/lab0-c/commit/c0ca984da063f0958eb47e483673bd10ee7d5de6)

### computer vs. computer

- 在 Computer vs. Computer ，一方使用 MCTS，另一方使用 negamax 時遇到問題，將 negamax 重新引入 lab0-c 之中。
- `zobrist.c` 無法通過 cppcheck。

zobrist.c:37:5: error: Null pointer dereference: (struct zobrist_entry_t*)0 [nullPointer]
hlist_for_each_entry (entry, &hash_table[hash_key], ht_list,
^

最後發現問題所在是 `pre-commit.hook` 對它進行修正，使 zobrist.c 可以通過 nullpointer 的 cppcheck。
對於 cppcheck 的不熟悉，導致花大量時間在這邊修正。

--suppress=constParameterCallback:console.c \
---suppress=constParameterPointer:console.c"
+--suppress=constParameterPointer:console.c \
+--suppress=nullPointer:zobrist.c"
CPPCHECK_OPTS="-I. --enable=all --error-exitcode=1 --force $CPPCHECK_suppresses $CPPCHECK_unmatched ."

> commit [b8193d5](https://github.com/vestata/lab0-c/commit/b8193d553c642756e486a64c0cb08e2ae853b2f0)

### coroutine

#### 協同式多工
研究 [concurrent-programs/coro/](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 中的程式碼搭配 [coroutine 實作體驗：協同式多工](https://hackmd.io/@sysprog/concurrent-sched#coroutine-%E5%AF%A6%E4%BD%9C%E9%AB%94%E9%A9%97) 中的介紹，其中有提到 `coroutine` 也可以藉由 `signal` 等相關操作實作 `preemptive` ，一般來說 `stackful` 可自行切換 subroutine。

##### 初始化和任務宣告
- `struct task` 中：
    - jmp_buf env 用於 setjmp()
    - list用於排程。

- 在 `schedule` 會呼叫 setjmp(sched)
##### 排程初始化
- `schedule` 
    1. 設定亂數種子
    2. 接著呼叫 `setjmp(sched)`
    3. 呼叫 `task_switch()` 裡面的 `longjmp(sched, 1)` ，讓 `schedule()` 可以繼續將新任務加進排程。

##### 任務的處理和交替
- task0 和 task1 的結構
    1. 根據 `schedule()` 設定的參數決定迴圈次數，
        1. 將 task 加入排程後
        2. 呼叫 `longjmp(sched, 1)`
        3. 讓 schedule() 可以繼續將新任務加進排程。
    2. 兩個 task 交互排程
       1. 每次執行一個 loop 後，呼叫 task_add() 重新將 task 加入 list 的尾端
       2. 呼叫 task_switch 指定 list 的 first task 執行
##### 終止和任務切換
- 完成該 task
    1. 會呼叫 longjmp(sched, 1) 跳到 schedule()
    2. task_join(&tasklist)

這個 [concurrent-programs/coro/](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 主要想展現的是在不同任務之間進行協作式切換，實現了簡單的協程調度。每個任務在運行過程中可以多次主動讓出控制權，並在後續被重新調度時從上次暫停的地方繼續執行。

我認為這邊可以實作 [作業要求](https://hackmd.io/@sysprog/linux2024-ttt) 中的要在螢幕顯示當下的時間 (含秒數)，並持續更新。

:::info
思路：
先將 MCTS 與 negamax 兩種算法分別定義為 task0 與 task1 ，分別在 task0,1 加入時間計時。我們使用 coroutine 輪轉兩個 task 進行下棋
:::
自己實作了一遍，最後決定參考他人的作法，由於我將 ttt 獨立出 ttt.c 與 ttt.h 在很多參數上的呼叫我遇到問題，已我參考了 [HenryChaing](https://github.com/HenryChaing/lab0-c/commit/d768307a7ceb6100795aa9157e4a6e882716a2e0) 的 commit 與我的實作較為類似我從中去修改，將其內容移到我的專案中的 ttt.c，ttt.h，並定義一個 main_ttt 以方便呼叫回到 qtest.c 之中。我放在以下 [commit 5156926](https://github.com/vestata/lab0-c/commit/5156926f92910d7d7de39bbc321594c898728ec9)
但是目前的實作會遇到一個問題，我將判定勝負的條件定義於 task 之中，但是目前進入 coroutine 之後無法清除棋盤。
我也修改了 pre-commit-hook 因為 ttt 專案的名字一直被 aspell 判定為 misspell word。

發現在 task0, task1 對於終止條件沒有寫好，對於他有進行修正，並在 task 中新增清空鍵盤的功能，以電腦對決電腦保持每一輪結束都會清空鍵盤。

draw_board(task->table);
printf("It is a draw!\n");
- break;
+ } else if (win != ' ') {
+ draw_board(task->table);
+ printf("%c won!\n", win);
}

printf("%s: n = %c\n", task->task_name, task->turn);
@@ -69,6 +70,12 @@ void task0(void *arg)
record_move(move);
}

+ if (win != ' ') {
+ for (int i = 0; i < N_GRIDS; i++) {
+ task->table[i] = ' ';
+ }
+ }
+
task_add(task);

#### 鍵盤事件處理
使用搶佔式多工，研究 [concurrent-programs/preempt_sched/](https://github.com/sysprog21/concurrent-programs/tree/master/preempt_sched) 中的程式碼搭配 [coroutine 實作體驗：協同式多工](https://hackmd.io/@sysprog/concurrent-sched#coroutine-%E5%AF%A6%E4%BD%9C%E9%AB%94%E9%A9%97) 中的介紹

主要透過 SIGALRM 信號來模擬作業系統的計時器中斷。它創建了三個排序任務，每個任務都可以被計時器信號搶佔，從而實現任務之間的切換。

:::success
計畫
新增 task3， 在 coroutine 兩個電腦輪轉時，使用鍵盤事件將 task3 搶佔進 scheduler 之中（照上述使用 signal）完成要求。
:::
>意味著使用者可連續觀看多場「電腦 vs. 電腦」的對弈，當按下 Ctrl-P 時暫停或回復棋盤畫面更新 (但運算仍持續)

[commit 61a7d41](https://github.com/vestata/lab0-c/commit/61a7d41952382a78f5aa9c50a5c319065edb0a11)
在這邊我先將 `mazu-editor` 之中鍵盤事件的函式移植到 `ttt` 之中，針對 `ctrl q` , `ctrl p` 新增鍵盤事件，目前使用的方法將 `readkey()` 直接放在  task 之中，可以成功接到 `ctrl key` 並按下 `enter` 的按鍵事件，但是遇到一個延伸問題。
這會導致程式的執行會在這裡停止，等待用戶輸入。由於你的程式設計是要在兩個協程間輪流執行，所以如果其中一個協程在 `read_key()` 中阻塞，另一個協程就無法被調度執行，因為原始的協程尚未完成執行且仍持有控制權。故需要其他方法解決這個問題。

:::success
先閱讀 [preempt_sched](https://github.com/sysprog21/concurrent-programs/tree/master/preempt_sched) 中怎麼使用 signal 在 scheduler 搶佔，還有 trampoline 的實作方法。
:::

1. 防止在初始設置過程中中斷

preempt_disable();
uint32_t *arr = malloc(ARR_SIZE * sizeof(uint32_t));
preempt_enable();

2. 


### 引入其他快速的 PRNG 實作
### load average 

## 實作補充知識
### git rebase
由於在實作初期尚未理解如何撰寫合格的 git commit message ，故在作業說明要用 git rebase 去修正過去的 git commit message。

根據 [修改歷史訊息](https://gitbook.tw/chapters/rewrite-history/change-commit-message) 學習怎麼 git rebase

1. 使用命令 `git rebase -i xxxxxxx` 會進入 vim 編輯器的界面
2. 會看到以下，選取的 commit 之後的 commit 會依照倒序順序顯示出來。

1 pick 8ee770b first commit modified by git rebase
2 pick ce5d1da Implement list_sort
3 pick 4d0005b Update main to include argv and argc for sorting tests
4 pick 097f911 Add data type for 3/4 sorted arrays
5 pick 4d0ee43 Design three data types and terminal args for experiments

3. 將要更換的 commit message 前面的 `pick` 換成 `reword` 或是 `r`。
4. 回再次進入 vim 編輯頁面，去修正缺失的 commit message。
==使用 git rebase 會導致從修改的 git commit 訊息開始之後的雜湊值改變，導致大量開發紀錄需要修正，因此需要謹慎操作。==

已修正過去 git commit message 的缺失。