2025q1 Homework1 (lab0)

contributed by < eleanorLYJ >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

Reviewed by `gawei1206`

測試分數的部分有提到偶爾會有95分的情況，想請問你知道這個問題發生在哪個部分，有對這個問題做出相對應的改善嗎

謝謝建議，目前嘗試讀懂〈Dude, is my code constant time?〉與檢測常數時間的程式碼但還未參透 eleanorLYJ

Reviewed by `fatcatorange`

部份 commit message 可以更加詳述

謝謝建議，已新增敘述了 eleanorLYJ

Reviewed by `BennyWang1007`

如 fatcatorange 提到，提交訊息有很多可以改善
另外，看起來此實作與倉庫皆為去年的作業，今年新增的如 linux_listsort、tiny-web-server、dudect等皆未看到，也並未包含作業要求的 commit 4a2ff9f。

開發環境

$ 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):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12450H
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  8
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            4992.00
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   320 KiB (8 instances)
  L1i:                   384 KiB (8 instances)
  L2:                    7 MiB (5 instances)
  L3:                    12 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-11
Vulnerabilities:

針對佇列操作的程式碼實作

得分: 100/100 (偶爾 95/100)

`q_new`

commit 21e3c61

對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 time 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。

\to

資訊科技詞彙翻譯

函數函式目的:
建立空的佇列，回傳指標
實作:
為了回傳指向有效結構的指標，考慮到使用 malloc 函式配置記憶體時，當配置失敗，函式會回傳 NULL 指標，為了避免出現初始化佇列發生未定義行為 (Undefined Behavior)，因此在此有多做判斷。
發現 list.h 中有 INIT_LIST_HEAD(struct list_head *head)，該函式會將head 的prev 與 next 指向 head 完成初始化。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

commit message 中應可更詳細描述作法和想法
fatcatorange

新增敘述的 Commit 8e11a

`q_free`

將佇列所佔據的記憶體都釋放

list_for_each_safe 允許在迭代中刪除節點。
閱讀 Linux 核心原始程式碼巨集: container_of 理解container_of 的用法，在此函式中，用於尋找佇列中的各個 element_t。
在我完成 q_insert_head() 與 q_insert_tail() 兩個函式後，使用make check 發現佔據的記憶體反而比在完成上述兩個函式時變多了，因此才發現我未在q_free() 中將 struct element_t 中的 char *value釋放。
參考 2024 年 Linux 核心設計/實作課程作業 —— lab0 (A) 的圖片:

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

因此我將程式碼改成以下

     list_for_each_safe (node, next, l) {
         element_t *ele = container_of(node, element_t, list);
+        free(ele->value);
         free(ele);
     }
     free(l);

然後，我發現 queue.h 中有 q_release_element() ，可以避免如以上撰寫時的粗心並且增加整體的可讀性。

q_insert_head()

未修改結尾空终止字元: commit c4b77a2

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

在佇列開頭插入給定的新節點
閱讀 strncpy 的使用方式
在完成 insert_head() 與 q_remove_head() 後，發現make test的結果，並未通過主要測試 insert_head 與 remove_head 兩函式的 trace-01-ops。因此我找 /scripts 中 trace-01-ops.cmd，根據 trace-01-ops.cmd 裡的命令，逐一找出未通過測試的答案。

$./qtest
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih gerbil
l = [gerbilU���]
cmd> ih bear
l = [bearU��� gerbilU���]
cmd> rh dolphin
Removed bearU��� from queue
ERROR: Removed value bearU��� != expected value dolphin
l = [gerbilU���]

結果出現非預期的 "��"亂碼，這時我才發現複製字串的結尾缺少了結尾空终止~~字符串~~ 字串 (null-terminated string)。在複製的字串最後加上'/0'後，便通過 trace-01-ops 的測試。

string 的翻譯是「字串」

+    copyStr[len] = '\0';
     strncpy(copyStr, s, len);
     newNode->value = copyStr;
     list_add(&newNode->list, head);

列出對應的 GitHub commit 超連結即可，不用張貼完整程式碼。僅在需要討論時，才列出關鍵程式碼。

q_insert_tail

在佇列尾端插入給定的新節點
與 q_insert_head()邏輯相似

q_remove_head()

在佇列開頭移去給定的節點
實作過程發現忘記檢查 bufsize，之後又在補上。

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

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

關於靜態分析

避免非必要的英語和漢語交雜書寫，若你想用英語書寫開發紀錄，則整份都該以英語書寫，反之亦然。

問題1

queue.c:53:24: error: syntax error [syntaxError]
    copyStr[len] = '\0';
                       ^

Fail to pass static analysis.

+    strncpy(copyStr, s, len);
+    copyStr[len] = '\0';
-    copyStr[len] = '\0';
-    strncpy(copyStr, s, len);

我多次rebase 此commit 的基礎，但它無法正常工作。 Cppcheck不斷告訴我靜態分析失敗。

問題 2

queue.c:85:1: error: Unmatched '{'. Configuration: ''. [syntaxError]
{
^
queue.c:85:1: error: Unmatched '{'. Configuration: 'INTERNAL'. [syntaxError]
{
^
queue.c:85:1: error: Unmatched '{'. Configuration: 'LIST_POISONING'. [syntaxError]
{
^
queue.c:85:1: error: Unmatched '{'. Configuration: '__GNUC__;__clang__'. [syntaxError]
{
^

Fail to pass static analysis.

我只是加了{}，然後它就通過了靜態分析。太奇怪了。

-    if (!head || list_empty(head))

+    if (!head || list_empty(head)) {
        return NULL;
+    }

你可能找到 Cppcheck 的錯誤，確認最新的 Cppcheck 是否存在同樣的問題。

查閱第一手材料，例如 C 語言規格，不要把自己專業的成長交給大語言模型。

`q_size`

commit 86e6406

計算目前佇列的節點總量

q_delete_mid

移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List

使用快慢指標（Fast-slow Pointers）找到中間節點
為了省略指向中間節點的前一個節點的指標，因此我慢指針的型態為指標的指標。
為了讓快指標走完單向鏈結串列時，讓慢指標停在中間節點的前一個節點，因此慢指標從下一個指向head的dummy開始移動。

沒必要先用 C++ 程式語言撰寫，直接以 C 語言開發。

後來想到只要讓快指標提前移動，就不需要 dummy 節點了。
程式碼 version 2

        if(!head || !head->next) return NULL;
-        ListNode *dummy =  new ListNode(0, head); 
-        ListNode *fast = head, **slow = &dummy;
+        ListNode *fast = head->next->next, **slow = &head;
        // find the middle node
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = &((*slow)->next);
        }
-        if (fast != head)
+        ListNode* tmp = (*slow)->next;

善用 diff，列出存在差異的程式碼。

回到倉儲（Repository），想起意識到自己 leetcode 僅是移除 (remove) 非刪除 (delete)。
又回到 leetcode 上，將程式碼改成釋放記憶體的版本:
程式碼 version 3

+       delete(tmp);
        return head;
    }

然而作業中不同於 leetcode 題目中是處理單向鏈結串列，而是實作環狀雙向鏈結串列，想想只需要快慢指標的想法就可以完成這個函式。
commit 1e0fc45

針對環狀雙向鏈結串列，能否提出更快的程式碼？

todo: 嘗試將一指標從頭向後，另一指標從尾向前移動找中間節點，這樣是否會更快

`q_delete_dup`

用指標的指標cur指向確定不重複的節點。
迭代過程中的 ptr 與 ptr2

前者的值為是否重複的基準
後者是要找到不同於基準的值的節點

同樣地，我在 leetcode Remove Duplicates from Sorted List II上使用 C 驗證以上想法

沒必要用 C++，強化 C 語言程式設計。

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (!head) return head;

    struct ListNode *newhead;
    struct ListNode **curr = &newhead; 
    struct ListNode *ptr = head;
    
    while (ptr) {
        bool isDup = false;
        struct ListNode *ptr2 = ptr->next;
        // Check for duplicates while there are next nodes
        while (ptr2 && ptr->val == ptr2->val) {
            isDup = true;
            ptr2 = ptr2->next;
        }

        if (!isDup) {
            *curr = ptr;
            curr = &(*curr)->next;
        }
        else if (!ptr2) {
            *curr = NULL;
        }
        ptr = ptr2;
    }
    return newhead;
}

q_swap:

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

交換佇列中鄰近的節點
1. 記錄當前節點對的尾節點。
2. 反轉當前節點對的順序。
3. 如果有前一組交換節點對，則將其與當前組連接。
4. 更新兩個變數，指向代表前一對尾的指標 (prevPairEnd) 和指向該對開始的指標 (currPairStart) ，為迭代到下一對節點做準備。

注意用語。

我先在 leetcdoe 24. Swap Nodes in Pairs 上使用 C 驗證想法。

struct ListNode* swapPairs(struct ListNode* head) {
    if (!head) return NULL;
    
    struct ListNode *currPairStart = head;
    struct ListNode *prevPairEnd = NULL;
    struct ListNode *newHead = head; 

    if (head->next) {
        newHead = head->next;
    }

    while (currPairStart && currPairStart->next) {
        struct ListNode *pairEnd = currPairStart->next;
        currPairStart->next = pairEnd->next;
        pairEnd->next = currPairStart;

        if (prevPairEnd) {
            prevPairEnd->next = pairEnd;
        }

        prevPairEnd = currPairStart;
        currPairStart = currPairStart->next;
    }

    return newHead;
}

~~寫得很醜，有改進空間~~

因為以上用了兩個if判斷head，希望能夠減少if的使用

因為寫以上程式的時候，靠著leetcode測試，不斷修改，因此整個迭代邏輯是用拼湊的

接著想看其他人是用什麼邏輯寫完這題

具體說明哪邊要改進，而非籠統的「寫得很醜」。

沒必要看上面這些實作不佳的討論，你可以做更好！

新的嘗試，雖然不符合 leetcode 題意，但若作業只追求兩兩翻轉的效果就可以用以下程式碼

說好的空白字元呢？

指標 cur指向每一對 pair 的第一個節點
將 pair 值用 XOR swap 作交換，每次迭代移動兩步，直到 cur 指向的pair內不足兩個節點，便停止迭代

struct ListNode* swapPairs(struct ListNode* head)
{
    if (!head) 
        return NULL;
    for (struct ListNode* cur = head; cur&&cur->next; cur=cur->next->next) {
        struct ListNode *first = cur;
        struct ListNode *second = cur->next;
        // swap the value
        first->val ^= second->val;
        second->val ^= first->val; 
        first->val ^= second->val;
    }
    return head;
}

使用作業規範的程式碼縮排風格。

作業內的實作也是 XOR Swap
Commit d72248

用 uintptr_t 將 char * 轉成整數型別

the following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:
uintptr_t
(C99 7.18.1.4)

查閱辭典關於 assign 的解釋，考慮到漢語的書寫慣例，不該偷懶用「賦值」，本處應為「指派」之義。

然後發現，賦值指派表達式中的左運算元不可以是 lvalue

An assignment operator stores a value in the object designated by the left operand. An assignment expression has the value of the left operand after the assignment, but is not an lvalue. (C99 6.5.16)

        first->value =
            (char *) ((uintptr_t) first->value ^ (uintptr_t) second->value);
        second->value =
            (char *) ((uintptr_t) first->value ^ (uintptr_t) second->value);
        first->value =
            (char *) ((uintptr_t) first->value ^ (uintptr_t) second->value);

為什麼要用 xor 運算判斷 cur == head 以及 cur->next == head 呢？一方面可讀性偏低，優化也應交由編譯器來完成？
此外，通常在swap節點時應該是交換節點指向其他節點的指標（prev, next等）而不是直接更改 element。
BennyWang1007

q_reverse

以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

參考影片 Reverse a Doubly Circular Linked List中的作法:
將每個節點的 prev 與 next交換，最終將 head 指向原鏈結串列的tail

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *currNode = head;
    struct list_head *nextNode = currNode->next;

    while (nextNode != head) {
        nextNode = currNode->next;

        // Swap the current node's next and prev pointers
        currNode->next = currNode->prev;
        currNode->prev = nextNode;
        
        currNode = nextNode;
    }
    head = currNode->next;
}

使用作業規範的程式碼縮排風格

上述程式碼中，要讓 head 指向原鏈結串列 tail 的地方，靜態檢查失敗。

queue.c:178:10: style: Variable 'head' is assigned a value that is never used. [unreadVariable]
    head = currNode->next;
         ^

Fail to pass static analysis.

回想起在你所不知道的C語言：指標篇看到的概念:

C 語言中，萬物皆是數值 (everything is a value)，函式呼叫當然只有 call-by-value。「指標的指標」(英文就是 a pointer of a pointer) 是個常見用來改變「傳入變數原始數值」的技巧。

使用指標的指標更改傳入函式的數值。

struct list_head **indirect = &head;
*indirect = currNode->next;

q_reverseK

commit db57db2

指定每 k 個節點為一組，進行反向順序排列
詳見 LeetCode 25. Reverse Nodes in k-Group

想法: 迭代過程,將每k個節點截斷成獨立的list，再呼叫q_reverse()，再將這k個節點接回原始lisr

實作參考yanjiew1

q_sort

commit fa03314

q_sort 呼叫 mergesort_list()

你如何確保目前的測試已涵蓋排序演算法最差的狀況？
如果不用遞迴呼叫，你該如何實作排序？

mergesort_list

遞迴呼叫 mergesort_list() , 使用快慢指標找到中間節點, 接著拆成兩個環狀串列, 直到把串列拆至只剩一個節點,接著呼叫 mergeTwoLists()

mergeTwoLists

此函式參數接受將兩個已排序的環狀雙向串列合併為一個環狀串列。
迭代將使用strcmp比較後確定的節點加到額外的空串列後, 直到把某一串列為空。
當一個串列用盡，使用 list_splice_tail_init 和 list_splice 追加另一個串列的剩餘節點。

測試 mergesort

結合作業2的 timsort 測試，小幅修改commit fa03314寫的遞迴版本 mergesort ，一併做測試

結果在commit 3fe74

我測試資料設計成6種類別，分別為(0)全部隨機資料、(1)遞增資料、(2)遞減資料、(3)遞增資料並隨機交換3次、(4)遞增資料隨機交換7次、(5)每64個數字作為一個 run 組成的資料、(6)每64個數字作為一個 run 組成的資料並在同一個 run 以20％機率隨機交換 (7)全部資料以同一個隨機值組成

而此 commit fa03314能通過所有隨機資料的測試, 但在遞增資料時，mergeTwoLists 函式會進入無窮迴圈中。

TODO: 暫時我看不出來哪裡有問題，稍後用GDB看變數的變化

小幅修改 andy155224 的 mergeTwoLists 函式，仍然沒有通過全部測試

另外發現了幾個原本實作的缺陷

所有隨機的資料沒有排序成功。
資料個數調成2的冪, 然而發現我分割後的兩個串列大小不等大
mergeTwoList 跟 visitorckw 實作 timsort 的 merge 函式有相同目的, 我決定重複使用後者函式, 但要注意的 merge 函式考慮的是兩鏈結串列非環狀的並且沒有 dummy node

每一種資料測試的大小為 32788 =

2^{15} + 20

==== Testing recursive merge_sort ====
type == 0
  Elapsed time:   775
  Comparisons:    38661
  List is not sorted
type == 1
  Elapsed time:   692
  Comparisons:    28169
  List is sorted
type == 2
  Elapsed time:   1085
  Comparisons:    171629
  List is sorted
type == 3
  Elapsed time:   553
  Comparisons:    28169
  List is sorted
type == 4
  Elapsed time:   512
  Comparisons:    28169
  List is sorted
type == 5
  Elapsed time:   569
  Comparisons:    34963
  List is sorted
type == 6
  Elapsed time:   556
  Comparisons:    35834
  List is sorted
type == 7
  Elapsed time:   1066
  Comparisons:    199771
  List is sorted

以下每一種資料測試的大小仍為 32788 =

2^{15} + 20

==== Testing recursive merge_sort ====
type == 0
  Elapsed time:   4068
  Comparisons:    450115
  List is sorted
type == 1
  Elapsed time:   2191
  Comparisons:    246040
  List is sorted
type == 2
  Elapsed time:   1664
  Comparisons:    245820
  List is sorted
type == 3
  Elapsed time:   1871
  Comparisons:    273882
  List is sorted
type == 4
  Elapsed time:   2128
  Comparisons:    307399
  List is sorted
type == 5
  Elapsed time:   3277
  Comparisons:    404392
  List is sorted
type == 6
  Elapsed time:   3840
  Comparisons:    440152
  List is sorted
type == 7
  Elapsed time:   1808
  Comparisons:    246040
  List is sorted

q_descend

在 LeetCode 2487. Remove Nodes From Linked List 寫

天真的版本(導致超時)

ptr 為指向符合題意的節點, biggest 為每次迭代範圍中能找到的最大節點
從 head 開始迭代, 判斷最大節點 biggest, ptr 指向biggest, 下一次迭代的起點就是從biggest的下一節點開始, 直到把此鏈結串列的最後一節點加到 ptr 上

若鏈結串列上的值是遞減,最壞時間複雜度就會達

O (n^{2})

struct ListNode* removeNodes(struct ListNode* head) {
    struct ListNode *cur = head->next;
    struct ListNode *newHead = head;
    struct ListNode **ptr = &newHead;
    while (cur && cur->next) {
        struct ListNode *biggest = *ptr;
        while (cur) {
            if (cur->val > biggest->val) {
                biggest = cur;
            }
            cur = cur->next;
        }
        *ptr = biggest; 

        // next iteration
        cur = biggest->next;
        ptr = &((*ptr)->next);
    }
    return newHead;
}

移除 C++ 程式碼，除非你要彰顯 C++ 特有之語言特徵。

程式語言的標注是 cpp，而非 c++，後者不為 HackMD 所識別。
減少對 C++ 的參照，本作業要強化學員對 C 語言的掌握，過程中應適度查閱 C 語言規格書。

改用c語言與遞迴方式解這題
優點: 時間複雜度
$O (n)$
缺點: 空間變成複雜度
$O (n)$

**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNodes(struct ListNode* head) {
    if(!head || !head->next) {
        return head;
    }
    struct ListNode *ans = removeNodes(head->next);
    if(head->val >= ans->val) {
        head->next = ans;
        return head;
    }
    return ans;
}

作業實作

因為作業實作環狀鏈結串列，換個方向迭代就可以改善天真版的效率問題

反向迭代紀錄最小節點，串列尾端因為不需再跟下一節點故是當前最小，接著向前迭代，若當前最小節點比該比較節點大就刪除，反之更新當前最小節點
Commit 0a53875

q_ascend

Commit 915e1c3

想法相似於 q_descend

q_merge

合併所有已排序的佇列，並合而為一個新的已排序佇列

失敗版本

想要使用 sortTwolists() 去實現頭尾相接的合併作法，但未得到預期結果

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return list_entry(head->next, queue_contex_t, chain)->size;
    int queueSize = q_size(head);
    queue_contex_t *context;

    while (queueSize > 1) {
        list_for_each_entry (context, head, chain) {
            queue_contex_t *tailContext = list_entry(head->prev, queue_contex_t, chain);
            if (context == tailContext)
                break;
            context->q = mergeTwoLists(context->q, tailContext->q, descend);
            // tailContext->size = 0;
            INIT_LIST_HEAD(tailContext->q);
            list_del_init(head->prev);
        }
        queueSize = (queueSize +1)/2;
    }

    return list_first_entry(head, queue_contex_t, chain)->size;
}

學習 GDB 工具，我中斷點設在 queue.c 裡的 q_merge() 處，希望執行下一行(step 或 next)，卻會跳去 harness.c 中exception_setup() 中的 sigsetjmp。

回頭看 qtest.c 呼叫 q_merge 的地方

    set_noallocate_mode(true);
    if (current && exception_setup(true))
        len = q_merge(&chain.head, descend);
    exception_cancel();
    set_noallocate_mode(false);

目前不清楚呼叫 q_merge 的下一步，為什麼會執行 if 條件句中的函式
TODO:
1. 釐清GDB 使用方式 -> 閱讀 GDB 文件
2. 理解 qtest 的執行過程 -> 以下紀錄理解過程

題目的要求: 不能把 queue_contex_t 的節點移除掉 0.0

另一版

參考 SPFishcool 寫法
想法簡單，將所有的串列相接再排序
Commit fa03314

考慮因素是什麼？量化表現如何？
拾人牙慧不難，但精準評判很難。

此 commit 的修改較多， commit message 描述應更詳細。
fatcatorange

新增敘述的 Commit 8f750

valgrind

$ make valgrind
沒有看到記憶體相關問題。

valgrind massif

閱讀 Massif: a heap profiler 與參考cymizer/

$ valgrind --tool=massif ./qtest -f traces/trace-01-ops.cmd
$ massif-visualizer massif.out.*

原始程式運行時配置的記憶體，約在執行 340000 ms 時 memory heap size 急速地降低，最終記憶體會歸 0。

TODO: 用其他方式表達

文字訊息不要用圖片展現！

然而我將 harness.c 中的 test_free() 的 free() 註解掉。最終記憶體並未歸0。

釐清 GDB 的 next 與 step

如果要 GDB 要執行的該行是函式呼叫 (function call)
執行 next，下一行會停在函式完成之後。
執行 step，下一行會停在被呼叫的函式的第一行

因此

step: 命令適合時機在於逐行檢查代碼，並且深入函式内部。
next: 命令適合時機用於快速跳過函式，關注主調用函式的執行流程。

理解 qtest 的流程

閱讀 lab0 的 qtest 命令直譯器的實作，期望解我在使用 GDB 執行我失敗版本的q_merge 時的疑惑。

從上述文章能得知，qtest執行順序

main → run_console → cmd_select → interpret_cmd → parse_args

因此我去找倉儲（Repository）中對應的程式碼，期望能找到與 harness.c 的exception_setup()相關的線索。

在 console.c 中的 interpret_cmd 函式負責解析參數，之後將參數傳給 interpret_cmda()中

char **argv = parse_args(cmdline, &argc);
bool ok = interpret_cmda(argc, argv);

interpret_cmda 函式目的是要在 cmd_list 找對應指令，接著執行指令。
next_cmd 的結構體為 cmd_element_t，而在 cmd_element_t 結構體裡有 operation 成員，這成員為指向函式的指標。

// in static bool interpret_cmda(int argc, char *argv[])
    while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
        next_cmd = next_cmd->next;
    if (next_cmd) {
        ok = next_cmd->operation(argc, argv);

執行的指令就會對應 qtest.c 中的 do_*

接下來我看 qtest.c 的 do_merge 函式，因為我對 q_merge 函式有興趣。找到對 do_merge 中其中一段程式碼:

    set_noallocate_mode(true);
    if (current && exception_setup(true))
        len = q_merge(&chain.head, descend);
    exception_cancel();
    set_noallocate_mode(false);

在執行 q_merge 前會呼叫 exception_setup() 函式。
而我中斷點設q_merge 函式內，執行run 與 next 命令後，卻也會停在exception_sepup()上。

bool exception_setup(bool limit_time)
{
    if (sigsetjmp(env, 1)) {
        /* Got here from longjmp */
        jmp_ready = false;
        // 省略
        return false;
    }

    /* Got here from initial call */
    jmp_ready = true;
    // 省略
    return true;
}

接著查 sigsetjmp 是甚麼?

int sigsetjmp(sigjmp_buf env, int savesigs);
sigsetjmp的功能: 負責處理錯誤與中斷。保存env 中堆疊(stack)的內容/環境(context/environment)。而若 savesigs 非零, 會把行程(process)的 signal mask 也存進 env中

疑問signal mask是甚麼?

The collection of signals that are currently blocked is called the signal mask. Each process has its own signal mask.

sigsetjmp 的回傳值，只分 0 與非 0。回傳 0代表是直接使用，而回傳非 0 代表是 siglongjmp 跳躍到此處。

因此，我使用 GDB 觀察到執行 exception_setup 的部分，假設是因為執行到 q_merge.c if 判斷式內中使用的 exception_sepup 函式，那我預期在 GDB 中執行 next 後就會停在jmp_ready = true; 行。並非如此，反而是停在jmp_ready = false;

cmd> merge

Breakpoint 1, q_merge (head=head@entry=0x5555555664c0 <chain>, descend=false) at queue.c:395
395     {
(gdb) next
0x000055555555b5ce in exception_setup (limit_time=<optimized out>) at harness.c:255
255         if (sigsetjmp(env, 1)) {
(gdb) next
257             jmp_ready = false;

因此這說明是因為 siglongjmp 而執行到了 if (sigsetjmp(env, 1))

搜尋整個 harness.c 找 siglongjmp，只有 trigger_exception 函式有用到 siglongjmp。從函式註解得知，該函式是要返回最近的異常設置 (exception setup)。

因此是異常(exception) 造成我 GDB 觀察的結果。然而這部分是什麼異常造成，我目前不知道。這部分我應該再學其他GDB使用方式。

shuffle

shuffle 命令

在 qtest.c 新增 shuffle 命令與 do_shuffle 函式後，在 queue.h 新增 q_shuffle prototype

+void q_shuffle(struct list_head *);

開始在 queue.c 撰寫 q_shuffle 函式
q_shuffle實作Fisher–Yates shuffle 演算法

先用 q_size 取得 queue 的大小 len。

隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。

隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。

然後當我想要寫 commit message 時，被 pre-commit.hook 擋下來了

[!] You are not allowed to change the header file queue.h or list.h

所以最後我拿掉在 queue.h 的改動。

拿掉後是否需要額外的動作來完成此函式？若沒有為何一開始要改動 queue.h?
fatcatorange

最終完成的commit 2a66a61

列出程式碼的主要目的是討論和檢討，若你沒有這舉措，就不該列出程式碼。

在 ./qtest 測試命令效果

cmd> new
l = []
cmd> ih RAND 10
l = [cnnsqxu ogdecp oirgbrjka hrcegl uckygdnfh okmdyiq bgsalbdq idzzlyu yefynyg crelx]
cmd> shuffle
l = [hrcegl oirgbrjka cnnsqxu ogdecp idzzlyu bgsalbdq uckygdnfh okmdyiq yefynyg crelx]

統計方法驗證 shuffle

虛無假說為

$H_{0}$ （虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution

使用 lab0(D) 提供的測試程式，計算 chi-squared test statistic

X^{2}

以下 shuffle 的結果明顯只4種組合，在 q_shuffle 函式印出亂數值，在./qtest 手動測試 q_shuffle 函式值，就明顯感覺亂數重複。

dict_values([11251, 0, 0, 0, 0, 38749, 0, 0, 0, 0, 0, 0, 0, 0, 18179, 0, 31821, 0, 0, 0, 0, 0, 0, 0])  len: 24
Expectation:  4166
Observation:  {'1234': 11251, '1243': 0, '1324': 0, '1342': 0, '1423': 0, '1432': 38749, '2134': 0, '2143': 0, '2314': 0, '2341': 0, '2413': 0, '2431': 0, '3124': 0, '3142': 0, '3214': 18179, '3241': 0, '3412': 31821, '3421': 0, '4123': 0, '4132': 0, '4213': 0, '4231': 0, '4312': 0, '4321': 0}
chi square sum:  613167.409505521

更改程式碼

    for (last = head->prev; last != head && len;
         len--, ptr = head->next, last = last->prev) {
-        time_t t;
-        srand((unsigned) time(&t));
        int r = rand() % len;

計算 chi-squared test statistic

X^{2}

就降低至18.8

dict_values([4120, 4181, 4203, 4174, 4164, 4089, 4239, 4237, 4116, 4157, 4157, 4181, 4235, 4297, 4132, 4130, 4218, 4125, 4114, 4189, 4036, 4108, 4177, 4221])  len: 24
Expectation:  4166
Observation:  {'1234': 4120, '1243': 4181, '1324': 4203, '1342': 4174, '1423': 4164, '1432': 4089, '2134': 4239, '2143': 4237, '2314': 4116, '2341': 4157, '2413': 4157, '2431': 4181, '3124': 4235, '3142': 4297, '3214': 4132, '3241': 4130, '3412': 4218, '3421': 4125, '4123': 4114, '4132': 4189, '4213': 4036, '4231': 4108, '4312': 4177, '4321': 4221}
chi square sum:  18.810849735957753

自由變換的變數只有 24 個，我自由度選擇 23。
因為

X^{2}

為 18.8，P value介於 0.10 至 0.9

因為 P value（0.1~0.9）> alpha（0.05），統計檢定的結果不拒絕虛無假說（

H 0

)

圖片來源: 卡方分布表

查閱文件得知 rand, srand, time 用法

rand 函式用途於計算出 0 到 RAND_MAX 的偽隨機整數。

The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.
(C99 7.20.2.1)

而 RAND_MAX 在規格書上寫至少有32767。

The value of the RAND_MAX macro shall be at least 32767.

srand 函式的參數會作為 rand 函式計算時的亂數種子。

The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. (C99 7.20.2.2)

time 函式用途於得知當前時間。

The time function returns the implementation’s best approximation to the current calendar time

然而在 linux 上才有定義 time 函式的單位是秒數。

time() returns the time as the number of seconds since the Epoch,
1970-01-01 00:00:00 +0000 (UTC).

因此原本以為在迴圈中重新指派當前時間當亂數種子就能每次獲得亂數，然而這樣看來，迴圈跑得速度太快，所以在同一秒中內的所有亂數都會相同啊。

ttt

新增hlist 與 ttt 命令

將 Linux 核心的 linux/list.h 標頭檔與 hlist 相關的程式碼抽出，成為 hlist.h 並修改 qtest 程式，使其新增 ttt 命令
Commit 0667a9f

擴充引用 ttt 命令

新增 option 中 mode 的這個變數。若 mode 為 0，代表允許使用者切換「人 vs.電腦」， mode 為 1 指「電腦 vs. 電腦」的對弈，最後 mode 2 為引入 coroutine ，並且處理鍵盤事件，當按下 'p' 能夠暫停或回復棋盤畫面，按下'q' 能夠中止當局電腦與電腦的對弈。

TODO:

處理 mode 非 0, 1, 2 的情況
鍵盤事件改處理 Ctrl + p 與 Ctrl + q

引入 coroutine 與處理鍵盤事件之前，我先理解了三個專案

協同式多工的 coro
搶佔式多工的 preempt_sched
mazu editor

coro

看懂此專案，最核心的大概就是每次 setjmp 或 longjmp，該會到程式碼的哪裡。

首先會在 main() 先初始化好變數與確定任務( task )的執行順序，之後就進入 schedule()。
一進入 schedule()，就會用 setjmp 設跳轉點。 tasks 是存函式指標的陣列，在此函數的第 9 行，就會運行指定函式。假設這裡的 tasks 為 {task0, task1}，ntasks 為 2 ，那麼首先執行 task0 函式。














void schedule(void)
{
    static int i;

    setjmp(sched);

    while (ntasks-- > 0) {
        struct arg arg = args[i];
        tasks[i++](&arg);
        printf("Never reached\n");
    }

    task_switch();
}

INIT_LIST_HEAD(&task->list); 是要創建 task0 的節點。執行到函式的第 11 行的 setjmp()，設置一個跳轉點，並且由於是直接呼叫 setjmp，所以進入 if 判斷式中，將此任務的插入到存有全部任務的串列(tasklist)，之後做 longjmp，跳回 schedule() 第 5 行，並接續執行 task1 函式。而 task0 與 task1 的結構相似，同樣會在會進入 if 判斷式之後，又再次回到 schedule()的第 5 行的 setjmp。





























void task0(void *arg)
{
    struct task *task = malloc(sizeof(struct task));
    strcpy(task->task_name, ((struct arg *) arg)->task_name);
    task->n = ((struct arg *) arg)->n;
    task->i = ((struct arg *) arg)->i;
    INIT_LIST_HEAD(&task->list);

    printf("%s: n = %d\n", task->task_name, task->n);

    if (setjmp(task->env) == 0) {
        task_add(task);
        longjmp(sched, 1);
    }

    task = cur_task;
    for (; task->i < task->n; task->i += 2) {
        if (setjmp(task->env) == 0) {
            long long res = fib_sequence(task->i);
            task_add(task);
            task_switch();
        }
        task = cur_task;
        printf("%s: resume\n", task->task_name);
    }

    printf("%s: complete\n", task->task_name);
    longjmp(sched, 1);
}

將 tasks 裡的任務都執行完了，就不會再進入 while 迴圈，此時做 task_switch()，從 tasklist 取得目前第一個任務，並且執行。目前這任務就是 task0，longjmp 會跳至 task0 的第 11 行，但不會進入 if 判斷式中，之後，執行到 task0 的 18 行又存下當下的 env，並將該任務的節點又加入 tasklist 中，之後又換 task1 的 if 判斷式處，之後處理 task1 的任務內容 …。

結果就會是 task0 ，從數字從 i 開始，每次加 2 直到達於n為止，每次將數字算斐波那契數列後，控制權就會轉給task1。因此 task0 就會與 task1 交錯執行。

static void task_switch()
{
    if (!list_empty(&tasklist)) {
        struct task *t = list_first_entry(&tasklist, struct task, list);
        list_del(&t->list);
        cur_task = t;
        longjmp(t->env, 1);
    }
}

preempt_sched

todo: 解釋

static int preempt_count = 0;
static void preempt_disable(void)
{
    preempt_count++;
}
static void preempt_enable(void)
{
    preempt_count--;
}
static void timer_handler(int signo, siginfo_t *info, ucontext_t *ctx)
{
    if (preempt_count) /* once preemption is disabled */
        return;
    /* We can schedule directly from sighandler because Linux kernel cares only
     * about proper sigreturn frame in the stack.
     */
    schedule();
}
static void local_irq_save(sigset_t *sig_set)
{
    sigset_t block_set;
    sigfillset(&block_set);
    sigdelset(&block_set, SIGINT);
    sigprocmask(SIG_BLOCK, &block_set, sig_set);
}
static void local_irq_restore(sigset_t *sig_set)
{
    sigprocmask(SIG_SETMASK, sig_set, NULL);
}

ualarm - schedule signal after given number of microseconds

useconds_t ualarm(useconds_t usecs, useconds_t interval);

The ualarm() function causes the signal SIGALRM to be sent to the invoking process after (not less than) usecs microseconds. The delay may be lengthened slightly by any system activity or by the time spent processing the call or by the granularity of system timers.
Unless caught or ignored, the SIGALRM signal will terminate the process.

-> usecs：第一次触发SIGALRM信号的时间 interval：第一次触发SIGALRM信号之后每隔 interval 微秒再觸發一次SIGALRM信号以微秒为单位

mazu edit

todo: 加解釋

void disable_raw_mode()
{
    if (tcsetattr(STDIN_FILENO, TCSAFLUSH, &ec.orig_termios) == -1)
        panic("Failed to disable raw mode");
}

void enable_raw_mode()
{
    if (tcgetattr(STDIN_FILENO, &ec.orig_termios) == -1)
        panic("Failed to get current terminal state");
    atexit(disable_raw_mode);
    struct termios raw = ec.orig_termios;
    raw.c_iflag &= ~(BRKINT | ICRNL | INPCK | ISTRIP | IXON);
    raw.c_oflag &= ~(OPOST);
    raw.c_cflag |= (CS8);
    raw.c_lflag &= ~(ECHO | ICANON | IEXTEN | ISIG);
    raw.c_cc[VMIN] = 0;
    raw.c_cc[VTIME] = 1;
    open_buffer();
    if (tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw) == -1)
        panic("Failed to set raw mode");
}

定點數

TODO

閱讀 The perfect patch 修改 commit message

2025q1 Homework1 (lab0)

Reviewed by gawei1206

Reviewed by fatcatorange

Reviewed by BennyWang1007

開發環境

針對佇列操作的程式碼實作

q_new

q_free

q_insert_head()

q_insert_tail

q_remove_head()

關於靜態分析

問題1

問題 2

q_size

q_delete_mid

q_delete_dup

q_swap:

q_reverse

q_reverseK

q_sort

mergesort_list

mergeTwoLists

測試 mergesort

q_descend

q_ascend

q_merge

失敗版本

另一版

valgrind

valgrind massif

釐清 GDB 的 next 與 step

理解 qtest 的流程

shuffle

shuffle 命令

統計方法驗證 shuffle

查閱文件 得知 rand, srand, time 用法

ttt

新增hlist 與 ttt 命令

擴充引用 ttt 命令

引入 coroutine 與 處理鍵盤事件之前，我先理解了三個專案

coro

preempt_sched

mazu edit

定點數

TODO

Read more

看 valkey 的資料結構

2025q1 Homework5 (assessment)

2025q1 Homework2 (quiz1+2)

2025q1 Homework1 (ideas)

Reviewed by `gawei1206`

Reviewed by `fatcatorange`

Reviewed by `BennyWang1007`

`q_new`

`q_free`

`q_size`

`q_delete_dup`

查閱文件得知 rand, srand, time 用法

引入 coroutine 與處理鍵盤事件之前，我先理解了三個專案