HackMD
2024q1 Homework1 (lab0)
contributed by < lumynou5 >
開發環境與前置作業
$ gcc --version
gcc (GCC) 13.2.1 20230801
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 4700U with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 1
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU(s) scaling MHz: 71%
CPU max MHz: 2000.0000
CPU min MHz: 1400.0000
BogoMIPS: 3994.00
參見分支 impl-old。
Cppcheck
Cppcheck 自 2.11 加入了 --check-level 選項，預設值為 normal，避免花費太多時間檢查長函式。而 log2_lshift16（log2_lshift16.h:14）正好不在 normal 等級的檢查範圍內，必須要使用 --check-level=exhaustive。且關於檢查等級的提示訊息儘管分類為 information 卻仍然會判定為錯誤，造成靜態檢查得到失敗的結果，因此我在 scripts/pre-commit.hook 中加入 --check-level=exhaustive 將 log2_lshift16 納入檢查範圍。
commit 82fd395
抑制 queue.c 的 constParameterPointer 檢查，因為其會誤判。
commit 6609844
指定的佇列操作
佇列結構：
使用沒有「container」、獨立存在的 struct list_head 作為鏈結串列的「開頭」：這是實作串列常見的手法，如此在長度為 0 時便不會出現分支。
環狀雙向串列。
避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。
q_new
配置並初始化一個 struct list_head。如上所述，串列的開頭應該是一個沒資料的節點，這點可以從 list_entry 和 list_last_entry 等窺見一二。
q_free
commit bc4ba52
「遍歷」在《教育部重編國語辭典修訂本》的釋義為「各處都到過」，因此我認為在此處使用該詞能正確表達意思，這只是自然語言。而「走訪」意為「拜見、往訪」，並沒有「各處」的含意（反而看起來像「access」的中國翻譯「訪問」），若要使用「走訪」一詞，應該改成「走訪每個節點」而非「走訪整個串列」。
「走訪」本來就沒有「存取各處資源」的寓意，一如 "traverse" 沒有意味著要經過所有的地點或單位。「遍」與「所有」擺在一起更是造成理解的困難，到底前者抑或後者是贅詞？「遍歷」這詞還是留做 Ergodic 的翻譯就好。
不過也許沒有哪個是贅詞？在古文中也有「遍歷各山」的用法（見前文連結），說明以前「遍歷」一詞也是如此使用的。據《重編國語辭典修訂本》，「遍」為「沒有遺漏」之意，英語維基百科對「traversal」的解釋亦為「the process of visiting (checking and/or updating) each vertex in a graph」，儘管在程式中很可能不會真的造訪每一個節點，但這應該視為最佳化的結果，而最原始的模樣應該是沒有提早退出迴圈、沒有剪枝的。但確實，相同的翻譯有可能造成誤會。另外，「歷」作動詞是「經」的意思，不太符合「visit」的語意，也是「遍歷」不好的理由之一。不過如此一來要如何表達英語中如「tree traversal」等用法？我認為「樹的走訪」失去了「each」的含意。
利用 list_for_each_entry_safe 巨集可以簡單地走訪整個串列，最後記得 free(head)。
q_free 的註解特別提到，在 head 為 NULL 時沒有作用，因此應該加上檢查。
q_insert_head, q_insert_tail
插入到開頭相當簡單：配置一個 element_t，使用 strdup 重製（duplicate）字串 s 並指派給 element->value，最後用 list_add 將新節點加到串列開頭。並且在 head == NULL、記憶體配置失敗時回傳 false。
q_insert_tail 原本的實作和 q_insert_head 幾乎一樣，只是改用 list_add_tail。但我接著就想到，「將節點加到開頭的上一個節點後面」等同於「將節點加到開頭的前面」，且重複的程式碼是一種「壞味道」，因此我將其改寫為：
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
return q_insert_head(head->prev, s);
}
q_remove_head, q_remove_tail
commit 926938b
利用 list_first_entry 取得串列的第一筆資料，也就是 head->next 的容器，然後用 list_del 將節點從串列中移除，並將字串用 strncpy 複製到 sp 中。q_remove_tail 使用和 q_insert_tail 相似的手法，把 head->prev->prev 當作開頭時的第一個節點便是 head 的最後一個節點。
根據手冊，char *strncpy(char *dst, char const *src, size_t sz) 會將參數 src 所指向的字串複製到 dst 所指向的以 null 填充（null-padded）的字元序列。但如果 dst 大小不夠，字串會截斷且不會在結尾插入 null 字元。（即 sz 是不包含 null terminator 在內的「字串長度」，而非緩衝區大小，從手冊提供的可能實作和 strnlen 的描述也能看得出來。）
這時我的實作長這樣：
strncpy(sp, element->value, bufsize); // 這裡可以不需要減去 1。
sp[bufsize - 1] = '\0'; // 將最後一個 char 指派為 null terminator。
// 如果 sp 不夠大就必須要加上 null terminator，
// 如果 sp 夠大這行則不改變結果（該處本來就會是 null 字元），
// 因此可以無條件地執行這行，不需要分支。
接著我想到，stpncpy 的回傳值是指向字串之後的指標，因此可以改寫成：
*stpncpy(sp, element->value, bufsize - 1) = '\0';
不但程式碼更精簡，且使用的指令也較少。
以下比較針對 stpncpy 引入的效能比較。
編譯選項：
-O3 -S
原本的程式碼：
movq %rbx, %rdx
movq %rcx, %rdi
call strncpy@PLT
movb $0, -1(%rax,%rbx)
修改後：
subq $1, %rdx
call stpncpy@PLT
movb $0, (%rax)
q_delete_mid
利用「快慢指標」找到中間的節點。
q_delete_dup
和 q_delete_mid 不同，註解只說當 head 為 NULL 時回傳 false，為空時不用，不知道是不是誤植。
提交 pull request 吧！
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
q_swap
目前的實作可讀性較差，有改進空間。
q_reverse
使用 list_move 將每個節點移動至開頭便能原地反向之。
q_ascend, q_descend
兩者幾乎一樣，惟前者產生升序、後者產生降序，只有「比較」不同，可以將這部分邏輯抽出來，改成傳入函式指標來比較。
typedef bool element_cmp_t(element_t const *lhs, element_t const *rhs);
static inline int ascend_descend_impl(struct list_head *head, element_cmp_t *cmp)
{
// Real implementation...
}
int q_ascend(struct list_head *head)
{
return ascend_descend_impl(head, element_greater);
}
另外，透過 diff 比較檔案差異發現，ascend_descend_impl 是否加上 inline（或 __always_inline）在 -O3 下對產生的組合語言沒有影響。
