2025q1 Homework1 (lab0)

contributed by < lumynou5 >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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 字元

事前準備

我決定繼續上次未完的開發，首先將上次的提交重定基底到 master 分支，並修改提交訊息符合新的規範。

不要打錯專案的名稱。

根據 Gerrit 文件最後一節，只要在提交訊息後加上 Change-Id（由於 master 上的提交已經有了，不需要自己加），其後續的提交便會自動加上，但我發現這不適用於重定基底，因為 pick 不會觸發提交掛鉤程式。解決方法是使用 reword 重新編輯提交訊息，正好需要移除訊息中的 backtick。若不需要修改提交訊息，可以使用 git -c rebase.instructionFormat='%s%nexec git commit --amend --no-edit' rebase master，利用修補使之視為新提交。

過程中我發現程式碼靜態分析無法通過，輸出

queue.c:28:5: error: There is an unknown macro here somewhere. Configuration is required. If list_for_each_entry_safe is a macro then please configure it. [unknownMacro]
    list_for_each_entry_safe (entry, safe, head, list)
    ^

原因是 list.h 中的條件編譯，導致 Cppcheck 認為巨集可能（--force 選項會檢查每種情況）不存在（#210）：

#if __LIST_HAVE_TYPEOF
#define list_for_each_entry_safe(entry, safe, head, member)            \
    for (entry = list_entry((head)->next, typeof(*entry), member),     \
        safe = list_entry(entry->member.next, typeof(*entry), member); \
         &entry->member != (head); entry = safe,                       \
        safe = list_entry(safe->member.next, typeof(*entry), member))
#endif

解決方法有:

1. 不使用 --force，並加上 -D__LIST_HAVE_TYPEOF，只檢查有 typeof 的情況。但如此影響太大。
2. 使用 #error 導引。但如此就沒必要存在 __LIST_HAVE_TYPEOF，因為若以沒有 typeof 的實作編譯便會報錯，程式碼強制依賴於 typeof。
3. 加上一個 #else 分支定義假巨集。如此在沒有 typeof 的情況，不使用 list_for_each_entry 等巨集的部分仍可編譯。（#211）
4. 給這些巨集加上 type 參數，就像 list_entry 等巨集。如此這些巨集便不再依賴於 typeof，但更改了介面。

#error 是 preprocessor directives，注意用語！

已改譯為「導引」，和 command 與 instruction 區別。 Lumynous

cppcheck-suppress-macro 註解可以抑制使用巨集的地方產生的錯誤，但因為此例巨集根本沒定義，自然也就不能用了。

在 #211 合併後有同學回報 Cppcheck 2.13.0（即 Ubuntu 24.04 LTS 提供的版本）會出現 Label 'int' is not used. [unusedLabel] 的錯誤，這是 Cppcheck 的 bug 導致的誤報（false positive，在其 bug 回報中常縮寫為 FP），於 #215 修復。後者錯誤地刪除了指派值給 safe 的程式碼，導致 Cppcheck 可能會抱怨變數未初始化，於 #228 修復。

其他

#213 Refine trace command descriptions

不知道為什麼被老師提及了，並提了一些意見。這個 PR 針對 trace 的描述做出改善，補上所有會呼叫的函式，當測試不通過時便知道是哪些函式中有錯誤。

#226 Remove similar trailer keys from commit hook

我注意到 #214 中加入的尾標鍵有些重複，Close 和 Closes 是同一個詞，Bug 與其也沒什麼差異。

另外，GitHub 將 PR 連結到 issue 的功能不確定能不能在動詞和 issue 編號間加入冒號，文件中寫的語法只有如「KEYWORD #ISSUE-NUMBER」的形式，範例亦皆僅以空格分隔，後來經過測試 GitHub 能夠辨識尾標格式的連結 issue。現在這項資訊能夠在官方文件中找到了：github/docs#36607。

#242 Introduce EditorConfig

之前在改 scripts/ 目錄下的 hook 時，剛好看到有些地方縮排不對。在修正後，我決定引入 EditorConfig，其內建於多個編輯器中，因此不需要額外設定便能讓編輯器自動使用正確的縮排。

老師希望能夠自動檢查，但 EditorConfig 不同於 clang-format，旨在提供協作的開發者在不同編輯器上能夠簡單地有一致的程式碼樣式，就如它的名字，只是編輯器的設定，它沒辦法知道語法，也就無法針對 Bash here-document（有兩種語法，分別不能使用空格縮排和完全不能縮排）做出處理。因此其僅僅只是避免人為失誤造成像此提交之前的錯誤縮排（由於主流文字編輯器和 IDE 都支援之），而無法避免開發者蓄意加入錯誤的縮排，不過這也提供了彈性，讓開發者可以選擇對人類更可讀的格式，例如以空格對齊未完而分成兩行的命令引數。

#260 Improve aspell dictionary

我遇到一些縮寫 aspell 不認識想要加到自訂的字典時，發現裡面很亂，有些字還重複了兩次。如果字典經過排序的話，就能更好看出某個字是不是已經在裡面了，避免重複加入。

至於目前已經很亂的字典，可以利用 sort(1) 排序，並加上 -u 選項刪除重複項目。不過字典檔開頭有一行標頭，不應該被排序，我使用 bat 的 -r 選項來輸出檔案的特定範圍，再以管道傳給 sort。

$ bat -r 2: scripts/aspell-pws | sort -du

不過 bat 不是 coreutils 的工具，要加入到版本庫的 pre-commit.hook 不適合使用。我發現 tail(1) 也能從絕對行數開始輸出，因此改以 tail -n +2 替換。

值得注意的是，sort 會將排序過的字典輸出到標準輸出流，當然也可以加上 -o 選項輸出到檔案，不過這樣標頭會消失，可以用 sed -i '1ipersonal_ws-1.1 en 500' $file 或 cat 等方式在排序完之後將標頭加回第一行。

$ tail -n +2 scripts/aspell-pws | sort -duo scripts/aspell-pws && sed -i '1ipersonal_ws-1.1 en 500' scripts/aspell-pws

實作

q_sort

我選擇以快速排序（quick sort）實作，因其有優秀的時間複雜度

$O(n\log n)$。

注意是否有 stable sorting 的要求。

q_ascend、a_descend 最佳化

commit d559603

原本是由一個函式統一實作，透過分別傳入不同的比較函式（小於和大於），來達到不同的順序。由於老師上課時提到 retpoline，讓我意識到透過函式指標間接呼叫會有額外的成本（即便沒有額外安全機制，函式呼叫也讓程式多出跳轉），而且兩個函式實作幾乎重複也是一種壞味道。因此我將兩個比較函式整合成一個類似 C++ 三路比較運算子 <=>（俗稱「太空梭運算子」）的函式，回傳 -1 表示左運算元小於右運算元、0 表示等於、1 表示大於。

之所以將回傳值限制在這三個值，而不直接使用 strcmp 的回傳值是為了讓 ascend_descend_impl 的統一實作更簡單，只要判斷三路比較的結果是否等於傳入的 1 或 -1 即可。

實作為：

int x = strcmp(lhs->value, rhs->value);
return (x > 0) - (x < 0);

產生的組合語言（gcc 14.2.1 -O3）為：

movq    (%r14), %rbx
movq    (%r12), %rdi
movq    %rbx, %rsi
call    strcmp@PLT
xorl    %edx, %edx   ;; 歸零 %edx。
testl   %eax, %eax   ;; 如果 %eax（回傳值）……
setg    %dl          ;; 大於 0，將 %dl 設為 1。
shrl    $31, %eax    ;; 邏輯右移 %eax 31 位，變成 1 代表負數，反之為 0。
subl    %eax, %edx   ;; %edx -= %eax，現在 %edx 就是三路比較結果。
cmpl    $-1, %edx