# 2024q1 Homework1 (lab0)
contributed by < [BrightCKC](https://github.com/BrightCKC) >

## 開發環境

$ 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:            Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5199.98
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   192 KiB (6 instances)
  L1i:                   192 KiB (6 instances)
  L2:                    1.5 MiB (6 instances)
  L3:                    12 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-11

## 實作指定的佇列操作

:::danger
改進你的漢語表達。台大電機系李宏毅教授對於 ChatGPT 的看法是，要善用人工智慧的成果，一旦人們得以善用，人類的書寫不該比 GPT 一類的語言模型差。 $\to$ [2023 年 Linux 核心設計/實作課程第一次作業檢討](https://hackmd.io/@sysprog/linux2023-lab0-review)

什麼叫做「[完善](https://dict.revised.moe.edu.tw/dictView.jsp?ID=161584)」？查詢辭典，可知：
* 完美、完好
* 完好無缺

以你的完成度來說，離上述境界太遠了，不要抬高自己身價。
:::

<s>在完善 queue.c 之前</s>
需要了解存在在 list.h 與 queue.h 當中結構體 list_head 與 element_t 之間的關係，如示意圖所示：
取自：[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)

從此圖能理解到 element_t 是類似於圖中 node 0、1、2 的結構體，其中有 char *value 來儲存字串，另外也嵌入了 list_head 用於管理儲存於 queue 的節點（element_t）之間的前後關係。

### q_new
> [commit ae38e7a](https://github.com/BrightCKC/lab0-c/commit/ae38e7a2903c846aa76878b4bc33199337316591)

:::danger
git commit message 並未依據 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 規範書寫，請詳閱作業說明，並使用 `git rebase -i` 更正。
:::

建立空的佇列。

:::danger
避免非必要的項目列表 (即 `* `)，用流暢清晰且明確的漢語書寫。
:::

### q_free
> [commit 69c8100](https://github.com/BrightCKC/lab0-c/commit/69c81000ef4b45dccb55ce7ee6058b7332baaf05)

:::danger
git commit message 並未依據 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 規範書寫，請詳閱作業說明，並使用 `git rebase -i` 更正。
:::

將所有儲存於佇列當中的節點刪除並釋放其記憶體空間，最後再釋放佇列的開頭。因為是釋放節點（element_t）而非是 list_head，因此需要 `container_of` 來得知該節點的位置。

### q_insert_head / q_insert_tail
> [commit aa07575](https://github.com/BrightCKC/lab0-c/commit/aa07575a54a49d947333d3768c25b9aacda36808)

:::danger
git commit message 並未依據 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 規範書寫，請詳閱作業說明，並使用 `git rebase -i` 更正。
:::

產生一個節點，對其賦值後將其插入在佇列的開頭 （q_insert_head）或是插入在佇列的結尾（q_insert_tail）。

### q_remove_head / q_remove_tail
> [commit 2a0b987](https://github.com/BrightCKC/lab0-c/commit/2a0b9870154d188aa72f4ba16bbb71236c9c4bb3)

:::danger
git commit message 並未依據 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 規範書寫，請詳閱作業說明，並使用 `git rebase -i` 更正。
:::

將佇列的節點移走（remove）。注意是 remove 不是 delete，因此須回傳節點。

:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::

### q_size
> [commit a26e6b7](https://github.com/BrightCKC/lab0-c/commit/a26e6b78ab49a09ce47fdeeca93d51ab5d205b30)

:::danger
git commit message 並未依據 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 規範書寫，請詳閱作業說明，並使用 `git rebase -i` 更正。
:::

回傳佇列的大小。

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

### q_delete_mid
> [commit 44a2454](https://github.com/BrightCKC/lab0-c/commit/44a24549b4a5f86e2532906f26e99effa521d57d)

:::danger
git commit message 並未依據 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 規範書寫，請詳閱作業說明，並使用 `git rebase -i` 更正。
:::

刪除佇列中間的節點，需要注意中間節點的[定義](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/)。

使用兩個指標 first、tail，first 指向第一個節點而 tail 指向最後的節點。接著 first 存取下一個節點而 tail 存取前一個節點。當 first 與 tail 指向同一個節點代表 first 與 tail 指向中間的節點，又或者 tail 指向的節點是 first 的前一個節點也就是說兩個指標已經錯開了，基於中間的節點的[定義](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) first 指向的節點正是中間的節點，以下為程式碼：

// head 為佇列的開頭
struct list_head *first = head->next, *tail = head->prev;
while ((first != tail) && (tail != first->prev)) {
    first = first->next;
    tail = tail->prev;
}

也可以依據 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)，當中有提到可以利用龜兔賽跑的概念，利用兩指標 fast 與 slow，fast 每次存取下下個節點而 slow 則只存取下個節點，那當 fast 以經存取到 queue 的開頭時，slow 就會存取到中間的節點，以下為程式碼：

// head 為佇列的開頭
struct list_head *fast = head->next, *slow = head->next;
while (fast != head && fast->next != head)
    slow = slow->next, fast = fast->next->next;

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

### q_merge
> [commit c4b1840](https://github.com/BrightCKC/lab0-c/commit/c4b184064a219e0fd66b52db86908697b91b4f95)

:::danger
git commit message 並未依據 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 規範書寫，請詳閱作業說明，並使用 `git rebase -i` 更正。
:::

:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

<s>實現</s> 將 k 個佇列，也可以理解為多次合併兩個佇列。

<s>實現兩個佇列從小到大合併，步驟如下：</s>
1. 初始化兩個指標 L1 和 L2 分別指向目標佇列 `tar_head` 和來源佇列 `src_head` 的第一個節點。
2. 在循環中，檢查 L1 和 L2 是否都沒有達到各自佇列的末端（即未到達 `tar_head` 和 `src_head`）。
3. 如果 L1 指向的節點值大於 L2 指向的節點值，則將 L2 的指標賦值給 cut_p，然後移動 L2 指向下一個節點。 接著將 cut_p 指向的節點插入到 L1 指向的節點之前。
4. 如果 L1 指向的節點值小於 L2 指向的節點值，則循環向後移動 L1 直到找到一個節點，其值大於 L2 指向的節點值，或直到到達 `tar_head`。
5. 當找到一個節點，其值大於 L2 指向的節點值時，執行步驟3；如果 L1 已經到達`tar_head`，表示目標佇列中的所有節點都比來源佇列中的節點小，此時將來源佇列中剩餘的節點移動到目標隊列的末尾。

### q_ascend/q_descend
> [commit a250a3b](https://github.com/BrightCKC/lab0-c/commit/a250a3b0d495fcfa1f09ec4cab9096de37a82878)

:::danger
git commit message 並未依據 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 規範書寫，請詳閱作業說明，並使用 `git rebase -i` 更正。
:::

工作是刪除節點，若該節點的右方(也就是 `list_head` 的成員 `next`)有比該節點值更大 (`q_descend`)或更小(`q_ascend`)的節點就刪除該節點。

因為提到該節點的右方，所以不如去反過來從左到右來尋訪節點(也就是不斷尋訪 `list_head` 的成員 `prev`)，在尋訪過程中不斷紀錄最小值(以 `q_ascend` 作舉例)，若該節點大於最小值就刪除該節點。
另外可以觀察到一個特性，就是不管是函式 `q_ascend` 或 `q_descend`，佇列中最右邊節點一定不會被刪除，因為沒有節點在它的右邊就不會出現有節點其值比它大或比它小的問題。