# 2025q1 Homework1 (lab0)
contributed by <`As7r1d`>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 10
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
```
## 開發過程
### q_new
- **功能：** 根據作業要求建立新的空佇列。
- **透過程式碼可以觀察到:**
- NULL queue 表示佇列未成功初始化，Empty queue 表示佇列已初始化但無元素。而 q_new 函式是要求建立一個 Empty queue 。
- 空佇列 （Empty queue） 結構：
- 1 個 head 指標去指向空佇列
- head 所指向的 next (head->next) 指向 head 自己
- head 所指向的 prev (head->prev) 指向 head 自己
- **實作內容：**
- 從 [list.h](https://github.com/As7r1d/lab0-c/blob/master/list.h) 標頭檔中發現有許多已定義 API 可用，所以我使用`INIT_LIST_HEAD` 達成該函式要求，並且使用 `malloc` 配置記憶體區塊給 head。
- **程式碼：**[Commit 20e2f3d](https://github.com/sysprog21/lab0-c/commit/20e2f3d97f778da75ce37ac50fabd7da4d0e47ad)
- **qtest 執行：**
```
./qtest
cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> ih c
l = [c b a]
cmd> free
l = NULL
```
### q_free
- **功能：** 釋放佇列所佔用的記憶體。
- **想法:**
- 追蹤 [queue.h](https://github.com/As7r1d/lab0-c/blob/master/queue.h) 標頭檔中，發現定義 `element_t` ，`element_t` 表示鏈結串列中之元素。
- q_free 函式釋放 `element_t` 所佔據的空間。
- element_t
- 結構：
- 指向字元陣列
- 雙向鏈結串列之節點
- **實作內容：**
- 先檢查 head 是否為 NULL。
- 使用 [list.h](https://github.com/As7r1d/lab0-c/blob/master/list.h) 中 `list_for_each_safe` 來遍歷佇列中 `element_t` 並刪除節點。
- 使用 [list.h](https://github.com/As7r1d/lab0-c/blob/master/list.h) 中 [`list_del`](https://github.com/As7r1d/lab0-c/blob/0c90a5c1abf1460ab750f915efaa2c48429c4e48/list.h#L144) 從鏈結串列中移除該節點。
- free(entry->value)：如果 value 指標指向的記憶體不為 NULL，則釋放。
- free(entry)：釋放 `element_t` 節點本身。
- 釋放 head
- **程式碼：**[Commit 20e2f3d](https://github.com/sysprog21/lab0-c/commit/20e2f3d97f778da75ce37ac50fabd7da4d0e47ad)
- **qtest 執行：**
```
./qtest
cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> free
l = NULL
```
### q_insert_head 和 q_insert_tail
- **功能：**
- q_insert_head：在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)。
- q_insert_tail ：在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)。
- 想法:
- 這兩個函式的核心概念相同，主要差異在於插入的位置不同
- 會使用到 `strdup()` 為一個字串分配新的記憶體，並把原始字串的內容複製過去。這樣就不會跟原始字串共用同一塊記憶體。
- 實作內容：
- 檢查 head 是否為 NULL ，如果 head 為 NULL，直接回傳 false。
- `malloc(sizeof(element_t))` 動態配置記憶體空間給新節點。
如果 malloc 失敗，回傳 false。
- `strdup(s)` 為 value 配置記憶體並存入字串內容，複製字串 s 並存入 value。
```c
new_element->value = strdup(s);
if (!new_element->value) {
free(new_element);
return false;
}
list_add(&new_element->list, head);
```
- 將新節點加入佇列
- q_insert_head：用 `list_add(&new_element->list, head)` 把新節點加到佇列開頭。
- q_insert_tail：用 `list_add_tail(&new_element->list, head)` 把新節點加到佇列尾端。
- 成功插入後回傳 true
- **程式碼：**[Commit d0eaa19](https://github.com/sysprog21/lab0-c/commit/d0eaa19b91504f6331f4032fee95ce37bd722e3c)
- **qtest:**
```
cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> it c
l = [b a c]
cmd> it d
l = [b a c d]
```
### q_remove_head 和 q_remove_tail
- **功能：**
- q_remove_head：在佇列開頭 (head) 移去 (remove) 給定的節點。
- q_remove_tail：在佇列尾端 (tail) 移去 (remove) 給定的節點。
- 這兩個函式會回傳被移除的 element_t 節點，但不會幫你 free()。
- **實作內容：**
- q_remove_head：取 head->next 第一個節點。
- q_remove_tail：取 head->prev 即最後一個節點。
- 使用 `list_entry(node, type, member)` 從 `struct list_head *` 回推到 `type *（element_t *）`。
```c
if (!head || list_empty(head)) {
return NULL;
}
struct list_head *first = head->next;
element_t *element = list_entry(first, element_t, list);
```
- 如果 `sp` 不是 NULL，就複製字串內容
- 為了確保不會超過緩衝區的大小，把 element->value 複製到 `sp`，但最多只會複製 `bufsize - 1` 個字元
- 加上 `\0` ，確保字串結束。
```c
if (sp != NULL && bufsize > 0) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
```
- 程式碼： [Commit 5eb769f](https://github.com/sysprog21/lab0-c/commit/5eb769f1e62c79ef610e4e921df0151de3db4aa3)
- **qtest:**
```
l = [c b a]
cmd> rh
Removed c from queue
l = [b a]
cmd> rt
Removed a from queue
l = [b]
```
### q_size
- **功能：**計算目前佇列的節點總量
- **實作內容：**就是透過 while 迴圈遍歷整個鏈結串列，從 head->next 開始，沿著 next 一直走，直到回到 head 為止，每走一個節點就讓 count 加 1，最後回傳總數。
- **程式碼：**[Commit 189849e](https://github.com/sysprog21/lab0-c/commit/189849eb8991aa6a8094ea15684ee2904f0e66c2)
- **qtest:**
```
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> ih c
l = [c b a]
cmd> size
Queue size = 3
l = [c b a]
```
### q_delete_mid
- **功能：** 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
- **實作內容：** 使用快慢指針的方式找到中間點，slow 指標一次前進 1 步，fast 指標一次前進 2 步。當 fast 走到底時，slow 剛好走到中間節點。
```c
while (fast->next != head && fast->next->next != head) {
slow = slow->next;
fast = fast->next->next;
}
element_t *element = list_entry(slow, element_t, list);
list_del(slow);
```
- **程式碼：**[Commit 9795cc0](https://github.com/sysprog21/lab0-c/commit/9795cc08915f6c861a48a24c6889d204545e8a6a)
- **qtest:**
```
cmd> size
Queue size = 3
l = [c b a]
cmd> dm
l = [c a]
```
### q_delete_dup
- **功能：** 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
- **實作內容：**
`current` 代表目前正在檢查的節點。從佇列的第一個有效節點開始，不包含 head。一一比對 current 和後面的所有節點，找出重複的字串。
```c
struct list_head *current = head->next;
```
`strcmp()` 比對兩個字串，如果相等，表示找到重複的節點
```c
if (strcmp(current_element->value, compare_element->value) == 0)
```
如果 found_duplicate 為 true，代表 current 這個節點也有重複，直接刪掉。如果沒有重複，current 就繼續往下一個節點移動。
```c
if (found_duplicate) {
list_del(current);
}
```
- **程式碼：** [Commit 9795cc0](https://github.com/sysprog21/lab0-c/commit/9795cc08915f6c861a48a24c6889d204545e8a6a)
- **qtest:**
```
l = [c b c c a]
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [b a]
```
由於會出現上述error，目前還在修正。
### q_swap
- **功能：** 交換佇列中鄰近的節點。
- **實作內容：**
- 如果佇列長度<= 1，不需要交換，直接返回。
- 取得 current（第一個節點）和 current->next（第二個節點），刪除 second 節點，然後將它插入到 first 之前。更新current節點繼續進行交換下一對節點
```c
struct list_head *first = current;
struct list_head *second = current->next;
list_del(second);
list_add(second, first->prev);
current = first->next;
```
- **程式碼：** [Commit d9a5993](https://github.com/sysprog21/lab0-c/commit/d9a59930cfa7a3cd623090b507f60cbcd2305836)
- **qtest:**
```
l = [h g f e d c b a]
cmd> swap
l = [g h e f c d a b]
cmd>
```
### q_reverse
- **功能：** 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點。
- **實作內容：**
- 遍歷整個佇列並交換 next 和 prev
```c
while (current != head) {
temp = current->next;
current->next = current->prev;
current->prev = temp;
current = temp;
}
```
`temp = current->next` ：暫存 current->next，確保反轉後能找到下一個節點。
`current->next = current->prev` ：讓 next 指向原本的 prev。
`current->prev = temp` ：讓 prev 指向原本的 next
- **程式碼：**[Commit a745816](https://github.com/sysprog21/lab0-c/commit/a74581604150ec22fcc01b31c0efbb4df6729d1e)
- **qtest:**
```
l = [g h e f c d a b]
cmd> reverse
l = [b a d c f e h g]
```
### q_reverseK
- **功能：** 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group
- **實作內容：**
`list_cut_position()` 這個函式，它能夠直接將前 k 個節點切割出來形成一個新的鏈結。當 k 個節點被切割出來後，接下來反轉。這裡直接利用了 q_reverse()，因為它已經能夠有效地反轉整個雙向鏈結串列，所以不需要再手寫反轉邏輯，這樣可以讓程式碼更模組化，提升可讀性。
反轉後的 k 個節點需要拼接回結果，因此使用 `list_splice_tail()` 來將反轉後的區塊加到一個新的 result 鏈結。
最後，處理剩餘不足 k 的節點時，直接將它們拼接到 result，不做任何反轉。
- **程式碼：** [Commit a745816](https://github.com/sysprog21/lab0-c/commit/a74581604150ec22fcc01b31c0efbb4df6729d1e)
- **qtest:**
```
l = [j i b a d c f e h g]
cmd> reverseK 2
l = [i j a b c d e f g h]
```
### q_sort
- **功能：** 以遞增順序來排序鏈結串列的節點。
- **實作內容：**
- 選擇 Merge Sort 來實現
- 將鏈結串列拆成兩半，這樣可以遞迴地對較小的部分進行排序，最終再合併回去，然後再使用快慢指標來找出鏈結串列的中間點（ slow 一次走 1 步，fast 一次走 2 步，fast 到達尾端時，slow 剛好在中間點）
- 透過 `list_cut_position(&left, head, slow)` 將 head 後半段的節點分割成 left，這樣 head 和 left 各自代表原來的前半段和後半段。
```c
struct list_head left;
struct list_head *fast, *slow;
INIT_LIST_HEAD(&left);
slow = head->next;
fast = head->next->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_cut_position(&left, head, slow);
q_sort(&left, descend);
q_sort(head, descend);
```
- 要合併排序後的兩個部，去比較 left 和 head 的第一個節點，根據 strcmp() 的結果來決定排序方式，使用 `list_del(chosen)` 從原來的鏈結中移除這個節點，`list_add_tail(chosen, &result)` 將選出的節點加入 result。重複這個過程，直到 left 或 head 其中一個先變空。
- 程式碼：[Commit 4d3fa7e](https://github.com/sysprog21/lab0-c/commit/4d3fa7e85249af19f20dc527ac810e69b6bd2b6d)
- 執行 make test 時發現排序是unstable：
```
# Test of insert_head and remove_head
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
# Test of insert_head, insert_tail, remove_head, reverse and merge
# Test of insert_head, insert_tail, size, swap, and sort
ERROR: Not stable sort. The duplicate strings "bear" are not in the same order.
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
ERROR: Not stable sort. The duplicate strings "bear" are not in the same order.
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
ERROR: Not stable sort. The duplicate strings "gerbil" are not in the same order.
# Test of truncated strings
# Test operations on empty queue
# Test remove_head with NULL argument
# Test operations on NULL queue
# Test of malloc failure on insert_head
# Test of malloc failure on insert_tail
# Test of malloc failure on new
# Test performance of insert_tail, reverse, and sort
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Not stable sort. The duplicate strings "vujqm" are not in the same order.
ERROR: Not stable sort. The duplicate strings "vujqm" are not in the same order.
ERROR: Not stable sort. The duplicate strings "iwkui" are not in the same order.
ERROR: Not stable sort. The duplicate strings "iwkui" are not in the same order.
ERROR: Not stable sort. The duplicate strings "cqson" are not in the same order.
Error limit exceeded. Stopping command execution
# Test performance of insert_tail
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Testing insert_tail...(0/10)
```
因此修改如下，使排序成為stable：
```diff
- if ((descend && cmp > 0) || (!descend && cmp < 0))
+ if ((descend && cmp >= 0) || (!descend && cmp <= 0))
```
- **qtest:**
```
l = [i j a b c d e f g h]
cmd> sort
l = [a b c d e f g h i j]
```
### q_descend 和 q_ascend
- **功能：**
- q_ascend：移除所有右側有更小值的節點，最後只保留從左到右遞增的節點。
- q_descend：移除所有右側有更大值的節點，最後只保留從左到右遞減的節點。
- **實作內容：**
這兩個函式的目標類似，一開始的思路是左到右遍歷並檢查右側的節點，但當節點過多時對於較大的鏈結串列會很慢。因此參考 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/description/) 。直接從左到右遍歷並檢查右側的節點，如果我們先反轉鏈結串列，從右側開始往左掃描，那麼右側的節點已經是處理過的，這樣我們只需要單向遍歷一次，時間複雜度變成 O(n)。
反轉鏈結串列：
```c
q_reverse(head);
```
這樣我們從左到右遍歷時，其實是從原本的最右側往左掃描。
遍歷 cur，確保 cur 是目前掃描到的最大(最小)值。next_node 負責檢查 cur 之後的節點。針對 q_ascend，如果 next_node 有比 cur 小 的值，就刪除 next_node;針對 q_descend，如果 next_node 有比 cur 大的值，就刪除 next_node。最後透過 list_del() 安全移除 next_node，並釋放記憶體。
```c
struct list_head *cur = head->next;
while (cur != head) {
struct list_head *next_node = cur->next;
while (next_node != head) {
element_t *cur_element = list_entry(cur, element_t, list);
element_t *next_element = list_entry(next_node, element_t, list);
struct list_head *next_next = next_node->next;
if (strcmp(cur_element->value, next_element->value) < 0) {
list_del(&next_element->list);
free(next_element->value);
free(next_element);
}
next_node = next_next;
}
cur = cur->next;
}
```
- **程式碼：** [Commit 4d3fa7e](https://github.com/sysprog21/lab0-c/commit/4d3fa7e85249af19f20dc527ac810e69b6bd2b6d)
- **qtest:**
```
l = [b a d c f e h g j i]
cmd> ascend
l = [a c e g i]
```
```
l = [h d b a c e g i]
cmd> descend
l = [i]
```
### q_merge
- **功能：**合併所有已排序的佇列，並合而為一個新的已排序佇列
- **實作內容：**
當在構思 q_merge 這個函式時，要將多個已排序的鏈結串列合併為一個，並且根據 descend 參數來選擇升序或降序排序。不需要頻繁地比較和插入，而是透過 list_splice_tail() 一次性合併所有鏈結串列，再進行一次排序。
取出 head 內的第一個 queue_contex_t：
```c
queue_contex_t *first_ctx = list_entry(head->next, queue_contex_t, chain);
struct list_head *result_queue = first_ctx->q;
```
queue_contex_t 是一個封裝鏈結串列的結構，其中 q 存放具體的鏈結串列。first_ctx->q 會作為合併後的最終結果。
遍歷 head 內的所有 queue_contex_t，將所有鏈結串列合併：
```c
struct list_head *chain_node = head->next->next;
while (chain_node != head) {
queue_contex_t *current_ctx = list_entry(chain_node, queue_contex_t, chain);
struct list_head *current_queue = current_ctx->q;
if (!list_empty(current_queue)) {
list_splice_tail(current_queue, result_queue);
first_ctx->size += current_ctx->size;
INIT_LIST_HEAD(current_queue);
current_ctx->size = 0;
}
chain_node = chain_node->next;
}
```
遍歷 head 內的所有 queue_contex_t，取得 current_queue（當前佇列）。如果 current_queue 不是空的，將 current_queue 透過 list_splice_tail() 併入 result_queue，然後更新 first_ctx->size，因為 result_queue 現在包含了更多節點。清空 current_queue，避免重複計算。繼續遍歷 head 內的下一個 queue_contex_t。
最後對 result_queue 進行排序
```c
q_sort(result_queue, descend);
```
最終合併後的大小
```c
return first_ctx->size;
```
- **程式碼：**[Commit 4d3fa7e](https://github.com/sysprog21/lab0-c/commit/4d3fa7e85249af19f20dc527ac810e69b6bd2b6d)
- **qtest:**
```
l = [f d c b a]
cmd> new
l = []
cmd> ih g
l = [g]
cmd> ih h
l = [h g]
cmd> ih a
l = [a h g]
cmd> ih b
l = [b a h g]
cmd> merge
l = [a a b b c d f g h]
```
## 論文〈Dude, is my code constant time?〉
## 以 Valgrind 分析記憶體問題
Sign in with Wallet
Connect another wallet