# 2025q1 Homework1 (lab0)
contributed by < [WavJaby](https://github.com/WavJaby/lab0-c) >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
<details><summary>開發環境</summary>
```shell
$ gcc --version
gcc (Ubuntu 14.2.0-4ubuntu2) 14.2.0
Copyright (C) 2024 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ 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) i7-12700KF
CPU family: 6
Model: 151
Thread(s) per core: 1
Core(s) per socket: 12
Socket(s): 1
Stepping: 2
BogoMIPS: 7219.20
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc cpuid tsc_kn
own_freq pni pclmulqdq ssse3 cx16 sse4_1 sse4_2 movbe popcnt aes rdrand hypervisor lahf_lm abm 3dnowprefetch ibrs_enhanced fsgsbase bmi1 bmi2 invpcid rdseed adx clflushopt sha_ni arat
md_clear flush_l1d arch_capabilities
```
</details>
---
<pre style="color:#67A37C; font-size:105%; font-weight:bold">
/**
* 以前只有寫過小專案，或是找好玩的小專案貢獻一下，
* 所以沒有寫過這麼正式的開發日誌或是commit，
* 希望我可以趁這個機會好好練習一下
* <font color="#F47067">@param</font> <font color="#DDD">homework</font> lab0
* <font color="#F47067">@param</font> <font color="#DDD">date</font> 2025/03/XX
* <font color="#F47067">@return</font> queue.c
*/
</pre>
## 實作 `queue.c`
首先學習[如何撰寫一個好的 commit message](https://blog.louie.lu/2017/03/21/如何寫一個-git-commit-message/)，我認為比較重要的是限制[標題最多只有 50 字元](https://blog.louie.lu/2017/03/21/如何寫一個-git-commit-message/#rules02)，之前都不知道有這個規則，只知道[以祈使句撰寫標題](https://blog.louie.lu/2017/03/21/如何寫一個-git-commit-message/#rules05)。
接著進行[牛刀小試](/@sysprog/linux2025-lab0-a/#牛刀小試)環節，並產生第一個 commit [85e9348](https://github.com/WavJaby/lab0-c/commit/85e93488996c495d52f13cc50a145775d5636708)。因為沒有使用過 Git hook 所以不知道 `Change-Id` 什麼時候會生成出來，怎麼生成出來。
俗話說得好
>Software and cathedrals are much the same – first we build them, then we pray.
-Sam Redwine
秉持著這個心情，按下 Enter 之後，`Change-Id` 成功的出現在我的 commit message 裡面。
終於可以開始寫程式了╰(\*°▽°\*)╯ <font style="font-size:70%;color:gray">這個不算emoji</font>。
</br>
### Implement `q_new`, `q_free` functions [6b7a573](https://github.com/WavJaby/lab0-c/commit/ef49dec9b29295bdbf963cc0c70556c903441836)
我在寫 <img style="height:1.6em;margin:-0.3em 0 0 0" src="https://upload.wikimedia.org/wikipedia/commons/1/18/C_Programming_Language.svg"> 的時候習慣把 new 和 free 一起寫，因為需要 new 的地方 就會需要 free ，不然到時候寫一寫忘記這東西到底怎麼 new 的，就又要回去看code，很累。
像是之前我寫了一個自己的 string 函式庫 [wjcl_string.h](https://github.com/WavJaby/WJCL/blob/main/string/wjcl_string.h) ，原因是因為平常取得字串長度都用 `strlen` ，每次都要遍歷字串的所有字元，感覺就慢得要死。
所以我想到一個在確保字串可以正常使用的前提下(例如可以直接丟到 `printf` 裡面)，儲存長度的方法，就是在創建字串時，多創建 8 byte 來存字串長度，然後回傳 `ptr + 8` 把那 8 byte 藏在字串的前面，需要 `free` 的時候再 `ptr - 8` 就好了。
缺點就是不能用內建的 `strcat` 之類的功能，長度就會跑掉，~~但這個就比較好用，我才不用內建的~~。
`q_new` 的部分，在 `malloc` 完後，先確認有沒有成功，然後使用 `INIT_LIST_HEAD` 初始化 list head。
`q_free` 的部分，使用 `list_for_each_entry_safe` 來遍歷整個鏈結串列，並使用 `q_release_element` 來釋放鏈結串列中的所有元素。
:::info
這邊不能使用 `list_for_each_entry` 是因為如果當前的元素已經釋放掉後，就無法取得下一個元素了，使用 `list_for_each_entry_safe` 會預先取得下一個元素，在下一輪迴圈時直接變更為當前元素，然後在預先取得下一個元素，這樣就避免了這個問題。
:::
### Implement `q_insert_head`, `q_insert_tail` functions [cfb2fae](https://github.com/WavJaby/lab0-c/commit/cfb2fae58cd9d44bae186d100874d33813567b57)
我同時實作了這兩個函式，因為他們都有一個相似處，就是要創建一個新的 `element_t` 並加入到鏈結串列中。
所以我另外實作了一個函式 `create_element` 來創建新的元素。
```c
static inline element_t *create_element(char *s)
{
element_t *element = malloc(sizeof(element_t));
if (!element)
return NULL;
element->value = strdup(s);
// If string copy failed, free the element
if (!element->value) {
free(element);
return NULL;
}
return element;
}
```
首先先確認 `element_t` 有沒有創建成功，接著複製字串。
這邊使用 `harness.h` 標頭檔中的 `strdup` 來複製字串，方便之後[追蹤記憶體配置和釋放的狀況](/@sysprog/linux2025-lab0-b/#追蹤記憶體配置和釋放的狀況)
如果字串複製失敗，要釋放剛剛創建好的 `element_t` 並回傳 `NULL`
接著只要呼叫 `create_element` 並且判斷有沒有創建成功後，
- `q_insert_head` 使用 `list_add(&entry->list)` 將節點插入頭
- `q_insert_tail` 使用 `list_add_tail(&entry->list)` 將節點插入尾
### Implement q_remove_head, q_remove_tail [c24fe3d](https://github.com/WavJaby/lab0-c/commit/c24fe3d853535001dcfbc5f47797a54bed20c888)
這兩個函式也有共通處，但我有點懶惰就沒有把他們拆出去了，主要差別在於一個使用 `list_first_entry` 另一個是 `list_last_entry`。
首先兩個函式都要先判斷鏈結串列中有沒有東西，如果是空的就直接跳出
```c
if (!head || list_empty(head))
return NULL;
```
接下來取得 `element_t` ，
- `q_remove_head` 使用 `list_first_entry` 取得鏈結串列中第一個元素
- `q_remove_tail` 使用 `list_last_entry` 取得鏈結串列中最後一個元素
`queue.h` 標頭檔中有註明 `If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)`
意思是如果有成功移除元素而且 `sp != NULL` ，要複製元素中的字串到 `sp` ，並且最大長度是 `bufsize - 1`，所以我使用 `strncpy` 複製字串，然後在大長度加上 null terminator。
```c
if (sp && bufsize) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
```
最後把這個元素從鏈結串列中移除，而且是"移除"，不是"刪除"，所以我使用 `list_del_init` ，僅將元素從鏈結串列移除，並且初始化元素中的 `list_head` ，最後回傳被移除的元素。
### Implement q_delete_mid [60e0295](https://github.com/WavJaby/lab0-c/commit/60e0295bf8a7b6c938abdf04e123cbb1187bfe5e)
因為之後會實作 merge sort 也會需要找中間值，所以我建立了一個新的函式 `_q_find_mid` ，我是用左右一起往中間夾的方式找中間的節點，
```c
static inline struct list_head *_q_find_mid(struct list_head *left,
struct list_head *right)
{
while (left != right) {
left = left->next;
// When there are an even number of nodes, select next first
if (right == left)
break;
right = right->prev;
}
return left;
}
```
如果是鏈結串列長度是偶數，優先去得靠左邊的節點 ，所以如果 `left->next == right` 的時候，就可以直接跳出迴圈。
有了這個函式後，在 `q_delete_mid` 中就可以呼叫這個函式拿到中間的節點，
```c
struct list_head *mid = _q_find_mid(head->next, head->prev);
list_del(mid);
q_release_element(list_entry(mid, element_t, list));
```
然後用 `list_del` 先將節點從鏈結串列中移除，然後用 `q_release_element` 釋放元素。
### Implement q_reverse [259dfbc](https://github.com/WavJaby/lab0-c/commit/259dfbc8193b3be0da67555518a3ba0a3f7219e6)
如果想要把整個鏈結串列反過來的話，只要遍歷每個節點，然後一個一個插入到鏈結串列的最前面就可以了，所以我用 `list_for_each_safe (node, safe, head)` 來取得每一個節點，然後用 `list_move(node, head)` 把每個節點都移到最前面。
### Implement q_swap [ed44ff8](https://github.com/WavJaby/lab0-c/commit/ed44ff8edbc2cb7ad7f0dfcca8cc28491970030f)
這個函式要把每兩個節點一組然後交換，一樣使用 `list_for_each_safe (node, next, head)` 取得兩個節點，然後用 `list_move(node, next)` 把 `node` 挪到 `next` 的下一個。
然後在挪動之前要先確保 `next != head` ，因為如果鏈結串列長度是奇數的話，最後一組的 `next` 會等於 `head`。
最後因為我們把 `node` 移到 `next` 後面了，所以我把 `next = node->next` 讓下個迴圈的 `node` 變成下一組。
### Implement q_ascend and q_descend [cabf09a](https://github.com/WavJaby/lab0-c/commit/cabf09a753034d56054322a45044a84902532e6f)
這兩個函式也是有共通點，所以我建立了一個函式 `_q_remove_not_in_order` 來找不符合順序的節點並且刪除它們。
因為要判斷兩個元素的順序(升序或降序)，所以我建立了一個函式 `_q_value_cmpare` ，來判斷兩個字串是否符合規則
```c
static inline int _q_value_cmpare(char *a, char *b, bool descend)
{
return descend ? strcmp(b, a) : strcmp(a, b);
}
```
接著實作`_q_remove_not_in_order` 這個函式會遍歷整個鏈結串列，並從每個元素開始，向前檢查前面的元素順序是否正確，如果發現有元素不符合指定的順序，就將其刪除。
```c
list_for_each_entry (curr, head, list) {
// 從last往前判斷順序
while (&last->list != head &&
// 判斷當前以及前面的元素順序
_q_value_cmpare(curr->value, last->value, descend) < 0) {
tmp = element_prev(last, list);
// 刪除不符合順序的元素
list_del(&last->list);
q_release_element(last);
// 往前一個元素
last = tmp;
}
// 紀錄最後一個元素，以供下次判斷
last = curr;
}
```
接著在在 `q_ascend` 以及 `q_descend` 中，判斷如果 鏈結串列大小 <= 1 就直接回傳，否則就要使用 `_q_remove_not_in_order` 來移除不符合順序的元素
- `q_ascend` 使用 `_q_remove_not_in_order(head, false)`
- `q_descend` 使用 `_q_remove_not_in_order(head, true)`
最後再使用 `q_size(head)` 回傳鏈結串列長度
### Implement q_delete_dup [fffd619](https://github.com/WavJaby/lab0-c/commit/fffd619aa0561ad49c8919b6484374b25499e23e)
因為牽涉到移除元素，所以需要使用 `list_for_each_entry_safe`
```c
if (&next->list != head && strcmp(curr->value, next->value) == 0) {
list_del(&curr->list);
q_release_element(curr);
dup = true;
}
```
先判斷 `curr` 是不是跟 `next` 一樣，如果一樣的話就刪除當前的元素，然後因為要移除所有有重複的元素，所以我用一個布林值 `dup` 紀錄有找到重複的值
```c
else if (dup) {
list_del(&curr->list);
q_release_element(curr);
dup = false;
}
```
最後重複直到找到不一樣的值，並且 `dup` 是 `true` 的話，也要刪除當前元素，因為他會是最後一個重複的元素。
### Implement q_reverseK [de50aac](https://github.com/WavJaby/lab0-c/commit/de50aac07eeff6a2dcb9635ebd396d0d467c8d4a)
使用 `list_for_each_safe` 遍歷鏈結串列
```c
list_for_each_safe (curr, next, head) {
if (++count != k)
continue;
```
如果 `count != k` 的話跳過這個迴圈，達到 `k` 時，使用 `q_reverse` 的方法，把鏈結串列反轉
```c
while (count--) {
next_element = element->next;
list_move(element, group_start);
element = next_element;
}
```
反轉後，更新 group_start 為組最後一節點。
```c
group_start = next->prev;
}
```
### Implement q_sort [743c731](https://github.com/WavJaby/lab0-c/commit/743c73194dc4b102291b68fcc8a7efa7d03d460b)
實作 merge sort 為了美觀，我另外新增了兩個函式，一個做切分遞迴 `_q_merge_sort` ，一個做合併 `_q_merge` ，其實切分遞迴可以用原本的函式就好了。
----
先介紹 `_q_merge`
```c
void _q_merge(struct list_head *l_head, struct list_head *r_head, bool descend)
```
目的是將兩個已經排序好的鏈結串列 `l_head` 和 `r_head` 合併成一個新的鏈結串列，並根據 descend 參數決定是升序還是降序。
我的做法是將右邊串列的第一個元素一個一個加到左邊串列，直到左邊串列頭碰到右邊串列頭，或是右邊串列的元素都被清空。
首先先取得左邊串列的第一個元素
```c
{
element_t *l = list_first_entry(l_head, element_t, list);
```
然後如果右邊串列不是空的的話，就重複迴圈，每次迴圈都先取得右邊串列第一個元素用於比較
```c
while (!list_empty(r_head)) {
element_t *r = list_first_entry(r_head, element_t, list);
```
接著這個內層循環會用前面定義的 `_q_value_cmpare` 來比較 `l` 以及 `r` 元素的值，如果輸出小於等於 0（根據 descend 決定順序），則表示 l 已經在正確位置，繼續移動 `l` 到下一個元素，直到找到需要插入 `r` 的位置或 `l` 回到了 `l_head` 。
```c
while (&l->list != l_head && _q_value_cmpare(l->value, r->value, descend) <= 0)
l = list_entry(l->list.next, element_t, list);
```
如果 `l` 回到了 `l_head` ，表示左右串列的所有元素都已經在正確位置。此時可以直接將右邊串列剩餘的部分追加到左邊串列的末尾，然後清空 `r_head` ，結束合併過程。這是一個優化步驟，能提升排序效率。
```c
if (&l->list == l_head) {
// Append right list to left list
l_head->prev->next = r_head->next;
r_head->next->prev = l_head->prev;
r_head->prev->next = l_head;
l_head->prev = r_head->prev;
INIT_LIST_HEAD(r_head);
break;
}
```
如果左編串列還有元素需要調整，將右鏈表的元素 `r` 插入到 `l` 的前面，完成一次合併操作。
```c
list_move_tail(r_head->next, &l->list);
}
}
```
----
接著介紹 `_q_merge_sort`
```c
void _q_merge_sort(struct list_head *head, bool descend)
```
這個函式通過遞迴從中細分串列直到當前陣列為單一元素，接著合併左右串列來完成整個串列的排序。
首先先判斷結束條件，用 `list_is_singular` 判斷當前的串列長度是否等於1，接著用之前定義過的函式 `_q_find_mid` 來取得串列的中間點；要切分的地方
```c
{
if (list_is_singular(head))
return;
struct list_head *l = head, *r = &(struct list_head) {},
*mid = _q_find_mid(head->next, head->prev),
*l_end = mid->prev;
```
從中間節點 `mid` 分割成兩個獨立的串列：左半部分以 `l` 為頭，右半部分以 `r` 為頭。
```c
r->next = mid;
mid->prev = r;
r->prev = l->prev;
l->prev->next = r;
l->prev = l_end;
l_end->next = l;
```
對左半部分和右半部分分別進行遞迴排序，直到每個子串列都成為單一元素。
```c
_q_merge_sort(l, descend);
_q_merge_sort(r, descend);
```
最後使用 `_q_merge` 將排序好的左半部分和右半部分合併成一個完整的排序串列。
```c
_q_merge(l, r, descend);
}
```
----
最後的最後 `q_sort` 只需要呼叫 `_q_merge_sort(head, descend)` ，就可以拿到排序好的串列。
### Implement q_merge [4e501c7](https://github.com/WavJaby/lab0-c/commit/4e501c756bd888e9daf5d9f2bfdcdc772fb0134f)
這個函式輸入了一個 `queue_contex_t` 的鏈結串列，我先拿了第一個元素當作要合併到的目標 `out`
```c
queue_contex_t *out = list_first_entry(head, queue_contex_t, chain), *node;
```
接著自訂一個迴圈從 `out` 的下一個元素開始，直到串列頭。
前面已經實作了 `_q_merge` ，就可以利用他將 `node->q` 鏈結串列追加到 `out->q`
```c
for (node = element_next(out, chain); &node->chain != head;
node = element_next(node, chain)) {
_q_merge(out->q, node->q, descend);
}
```
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
</br>
Sign in with Wallet
Connect another wallet