# 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

### Cppcheck

Cppcheck 自 [2.11](https://github.com/danmar/cppcheck/releases/tag/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](https://github.com/lumynou5/lab0-c/commit/82fd3954a69c4ad689311f4739b8cf6a1f30e927)

抑制 `queue.c` 的 `constParameterPointer` 檢查，因為其會誤判。
> commit [6609844](https://github.com/lumynou5/lab0-c/commit/660984473407d55482a48ea1ba13e8acecacb21b)

## 指定的佇列操作

佇列結構：
使用沒有「container」、獨立存在的 `struct list_head` 作為鏈結串列的「開頭」：這是實作串列常見的手法，如此在長度為 0 時便不會出現分支。
環狀雙向串列。

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

### `q_new`

配置並初始化一個 `struct list_head`。如上所述，串列的開頭應該是一個沒資料的節點，這點可以從 `list_entry` 和 `list_last_entry` 等窺見一二。

### `q_free`
> commit [bc4ba52](https://github.com/lumynou5/lab0-c/commit/bc4ba5277fc8e797e81afd2d16f9332143a4cb6e)

「遍歷」在[《教育部重編國語辭典修訂本》的釋義](https://dict.revised.moe.edu.tw/dictView.jsp?ID=19003)為「各處都到過」，因此我認為在此處使用該詞能正確表達意思，這只是自然語言。而「走訪」意為「拜見、往訪」，並沒有「各處」的含意（反而看起來像「access」的中國翻譯「訪問」），若要使用「走訪」一詞，應該改成「走訪每個節點」而非「走訪整個串列」。
> 「走訪」本來就沒有「存取各處資源」的寓意，一如 "traverse" 沒有意味著要經過所有的地點或單位。「遍」與「所有」擺在一起更是造成理解的困難，到底前者抑或後者是贅詞？「遍歷」這詞還是留做 Ergodic 的翻譯就好。

> 不過也許沒有哪個是贅詞？在古文中也有「遍歷各山」的用法（見前文連結），說明以前「遍歷」一詞也是如此使用的，儘管「遍」本身就有這樣的意思（不過我沒有使用「所有」或「各」這樣的詞）。但確實，相同的翻譯有可能造成誤會。

利用 `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](https://github.com/lumynou5/lab0-c/commit/926938b4c9939dcc01abb013436c0d0ff1981776)

利用 `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`，為空時不用，不知道是不是誤植。
:::warning
提交 pull request 吧！
:notes: jserv
:::
> [#174](https://github.com/sysprog21/lab0-c/pull/174)

### `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` 下對產生的組合語言沒有影響。