# 2025q1 Homework1 (lab0)
contributed by < `TING0419` >
### Reviewed by `nyraa`
> 注意科技詞彙翻譯
* 鍊表->鏈結串列
* 創建->建立
> 注意排版上英文與中文之間需要有一個空白
### Reviewed by `liangchingyun`
> 需要進行 rebase
## 開發環境
```
$ uname -a
Linux ting-ASUS-TUF-Gaming-A15-FA506IU-FA506IU 6.8.0-52-generic #53~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Wed Jan 15 19:18:46 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
$ ldd --version
ldd (Ubuntu GLIBC 2.35-0ubuntu3.9) 2.35
$ 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: 44 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 4800H with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU max MHz: 2900.0000
CPU min MHz: 1400.0000
BogoMIPS: 5789.20
```
## 開發指定的佇列操作
### `q_new`
原版本：
> [Commit b453915](https://github.com/sysprog21/lab0-c/commit/b4539159f768755d5c31e7a2ac9b7e842085ef45)
使用記憶體分配來建立一個新的雙向鏈結的`head`。
該函數分配記憶體並初始化鏈表，將 `head->next` 和 `head->prev` 設置為指向自身。
如果記憶體分配失敗，返回 `NULL` 以防止空指標存取。
```c
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
head->next = head;
head->prev = head;
return head;
}
```
改進：
>[Commit e17b5df](https://github.com/sysprog21/lab0-c/commit/e17b5df9b256cc7c143b37b05a4bc9c2cc24cc4c)
使用 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)中提供的API改寫，使程式更為簡潔。
```c
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### `q_free`
>[Commit 52fd5d0](https://github.com/sysprog21/lab0-c/commit/52fd5d075f9cd59082b4e8b3b4052439532351a2)
在佇列的實現中，鏈結串列是通過在 `element_t` 中定義的 `list_head` 結構來連接的。因此，可以使用在 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)中定義的 `list_for_each_entry_safe` 遍歷佇列中的所有 element_t，並獲取每個 `element_t` 的位址以釋放其記憶體。此外，由於 `element_t `中的字串所指向的記憶體區塊也需要釋放，最後，還需要釋放 `head` 的 `list_head` 所指向的記憶體區塊。
```c
void q_free(struct list_head *head)
{
if (!head)
return;
if (list_empty(head)) {
free(head);
return;
}
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
element_t *current = list_entry(node, element_t, list);
q_release_element(current);
}
free(head);
}
```
### `q_insert_head`
原版本：
> [Commit a5405a3](https://github.com/sysprog21/lab0-c/commit/a5405a3cbd9782371bb6a600581997b950a02b81)
使用 `list_add` 實現 `q_insert_head()`，將新節點插入佇列的 `head` 。確保當 `element_t` 的值指向字串時，使用 `strdup()` 來分配並複製字串，以避免在測試過程中發生錯誤。
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new_node = (element_t *) malloc(sizeof(element_t));
if (!new_node) {
return false;
}
new_node->value = strdup(s);
list_add(&new_node->list, head);
return true;
}
```
改進：
>[Commit 4af6ea3](https://github.com/sysprog21/lab0-c/commit/e79a800a7b0e6e57230efe06d2db7273fab7fb30)
這段改進優化了記憶體管理和錯誤處理。首先，新增了對 `head` 和 `s` 是否為空指標的檢查，防止空指標錯誤。接著，將字串的記憶體分配方式改為手動分配並使用 `strncpy` 進行字串複製，以避免緩衝區溢出。最後，對記憶體分配失敗的情況做了處理，確保在失敗時釋放已分配的記憶體，防止記憶體洩漏。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
int s_len = strlen(s);
element->value = (char *) malloc((s_len + 1) * sizeof(char));
if (!element->value) {
free(element);
return false;
}
strncpy(element->value, s, (s_len + 1));
list_add(&element->list, head);
return true;
}
```
### `q_insert_tail`
原版本：
> [Commit 5c91773](https://github.com/sysprog21/lab0-c/compare/master...TING0419:lab0-c:master)
實現 `q_insert_tail` 函數，將元素插入佇列的尾部。
為新節點分配記憶體並使用 `strdup` 函數複製字串。
使用 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的API `list_add_tail()` 將新節點插入佇列的末尾。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new_node = (element_t *) malloc(sizeof(element_t));
if (!new_node) {
return false;
}
list_add_tail(&new_node->list, head);
new_node->value = strdup(s);
return true;
}
```
改進：
>[Commit b81c0ad](https://github.com/sysprog21/lab0-c/commit/b81c0ad42e8a3c884e62ba2e154d093cb5bae53e)
通過利用雙向鏈結串列的特性使用 `q_insert_head`。將新節點插入到 `head->prev` 位置，等同於將節點添加至尾部。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head || !s) {
return false;
}
return q_insert_head(head->prev, s);
}
```
### `q_remove_head`
>[Commit 4cc1204](https://github.com/sysprog21/lab0-c/commit/4cc1204e9cdabeff015ac0e0866db0f80a9b63f4)
實作 `q_remove_head` 以從佇列的頭部移除元素。 如果提供了有效的緩衝區 `buffer`，則將該元素的字串值複製到該緩衝區中，並確保不會超過緩衝區的大小。 使用 `memcpy` 進行字串複製，並正確處理緩衝區溢位，必要時會對字串進行截斷。 移除該元素並將其返回。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *tmp = list_entry(head->next, element_t, list);
if (sp && bufsize > 0) {
size_t len = strlen(tmp->value);
if (len < bufsize) {
memcpy(sp, tmp->value, len + 1);
} else {
memcpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
list_del(&tmp->list);
return tmp;
}
```
### `q_remove_tail`
>[Commit 45413a7](https://github.com/sysprog21/lab0-c/commit/45413a7c191700bbf5f48095dd4b731f28544b8d)
將 `queue` 中最後一個元素移除
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
return q_remove_head(head->prev->prev, sp, bufsize);
}
```
### `q_size`
> [Commit 35bb7b7](https://github.com/sysprog21/lab0-c/commit/35bb7b78124e1afda5410a65082c8599063d91db)
使用 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中的 `list_for_each` 來計算佇列的長度。
如果佇列為空，返回 0；否則，返回元素的數量。
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### `q_delete_mid`
> [Commit 1b2ad88](https://github.com/sysprog21/lab0-c/commit/1b2ad8830f5647fc6366713ad72696ae02779cb7)
使用兩個指標來刪除佇列中的中間節點。 一個指標每次移動一步，另一個指標則移動兩步。 當較快的指標再次回到佇列的頭部時，較慢的指標將會指向中間的節點。將這個中間節點從佇列中移除。
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head)) {
return false;
}
struct list_head *slow = head->next, *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_del(slow);
element_t *element = list_entry(slow, element_t, list);
q_release_element(element);
return true;
}
```
### `q_delete_dup`
>[Commit dbd101d](https://github.com/sysprog21/lab0-c/commit/dbd101d95a7a330a32b9356f4083771eecad8d0a)
移除佇列中所有具有重複字串值的節點。 使用 `list_for_each_entry_safe` 來遍歷佇列。 如果連續的節點具有相同的值，刪除第一個節點並追蹤重複的尾端。如果在重複節點之後出現唯一值，則也移除最後一個重複節點。
使用`list_del` 來解除節點鏈結，並使用 `q_release_element` 來釋放記憶體。 處理邊界情況，例如佇列為空或僅有一個元素的情況。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head) || list_is_singular(head))
return false;
element_t *node = NULL, *safe = NULL, *dup_tail = NULL;
list_for_each_entry_safe (node, safe, head, list) {
if (&safe->list != head && !strcmp(node->value, safe->value)) {
list_del(&node->list);
q_release_element(node);
dup_tail = safe;
} else {
if (dup_tail) {
list_del(&dup_tail->list);
q_release_element(dup_tail);
}
dup_tail = NULL;
}
}
return true;
}
```
### `q_swap`
>[Commit 1b3ebb9](https://github.com/sysprog21/lab0-c/commit/1b3ebb975d95d4e57789236d353f93d3cf038ee5)
使用 `list_move` 來交換佇列中每兩個相鄰的節點。 如果佇列為空或僅包含一個元素，則不進行交換。
使用兩個指標遍歷佇列： 將 `first` 指向第一個節點，`second` 指向下一個節點。 將 `second` 移動到 `first` 之前，然後更新指標以繼續交換下一對節點。
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *first = head->next, *second = head->next->next;
while (second != head && first != head) {
list_move(second, first->prev);
first = first->next;
second = first->next;
}
}
```
### `q_reverse`
>[Commit cd3fd5a](https://github.com/sysprog21/lab0-c/commit/cd3fd5abcc199c851eef9dac70ed9342f741a46f)
使用 `list_move` 來反轉佇列中元素的順序。 如果佇列為空或僅包含一個元素，則不進行任何變更。使用 `list_for_each_safe` 遍歷佇列， 將每個節點移動到佇列的頭部，以達成反轉效果。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head) {
list_move(node, head);
}
}
```
### `q_reverseK`
>[Commit 24d364c](https://chatgpt.com/g/g-p-67bf03cb29b08191a64a5a418eb6ad31-linux-kermel/c/67bf03d1-db30-8012-9c43-8f15e6e2089d)
使用 `list_move` 來將佇列中的節點按每組 k 個進行反轉。 如果 k 為 1 或者佇列長度小於 k，則不進行任何變更。遍歷佇列，每次移動 k 個節點來進行反轉。 每次反轉完一組後，更新下一組的參考點。當剩餘的節點少於 k 個時，過程停止。
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head) || list_is_singular(head) || k == 1)
return;
int len = q_size(head), cnt = 0;
struct list_head *node = NULL, *safe = NULL, *reverse_head = head;
if (len < k)
return;
list_for_each_safe (node, safe, head) {
list_move(node, reverse_head);
if (++cnt == k) {
if ((len -= k) < k)
return;
cnt = 0;
reverse_head = safe->prev;
}
}
}
```
### `q_sort`
>[Commit 70d5497](https://github.com/sysprog21/lab0-c/commit/70d54976dbca94e72b591ad037ee1c01f57cd97d)
使用合併排序演算法來對佇列進行排序。
該演算法首先將圓形雙向鏈結串列拆分成單向鏈結串列，然後使用輔助函式（`merge_sort_list` 和 `merge_sorted_lists`）遞迴進行排序，最後重建雙向鏈結串列的指標以恢復圓形結構。
此實作支援根據 `descend` 標誌進行升序或降序排序。
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *data_head = head->next, *node = NULL, *safe = NULL;
head->prev->next = NULL;
head->next = merge_sort_list(data_head, descend);
for (node = head, safe = head->next; safe->next;
node = safe, safe = node->next) {
safe->prev = node;
}
safe->next = head;
head->prev = safe;
}
```
此函式 `merge_sorted_lists` 負責以遞迴方式對單向鏈結串列進行合併排序。
採用快慢指標切割串列為兩半，遞迴排序後再透過 `merge_sorted_lists` 合併結果。排序方向由 descend 參數控制。
```c
static struct list_head *merge_sort_list(struct list_head *head, bool descend)
{
if (!head || !head->next)
return head;
struct list_head *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
struct list_head *second = slow->next;
slow->next = NULL;
head = merge_sort_list(head, descend);
second = merge_sort_list(second, descend);
return merge_sorted_lists(head, second, descend);
}
```
此函式 `merge_sorted_lists` 會合併兩個已排序的單向鏈結串列。
使用 `dummy` 節點與尾端指標 `tail`，以尾插法串接節點，並依 `descend` 參數決定是否採用升冪或降冪排序。此函式是整個 `Merge Sort`合併階段的核心。
```c
static struct list_head *merge_sorted_lists(struct list_head *left,
struct list_head *right,
bool descend)
{
LIST_HEAD(dummy);
struct list_head *tail = &dummy;
while (left && right) {
const char *lval = list_entry(left, element_t, list)->value;
const char *rval = list_entry(right, element_t, list)->value;
if ((!descend && strcmp(lval, rval) <= 0) ||
(descend && strcmp(lval, rval) >= 0)) {
tail->next = left;
left = left->next;
} else {
tail->next = right;
right = right->next;
}
tail = tail->next;
}
tail->next = left ? left : right;
return dummy.next;
}
```
### `q_ascend & q_descend`
>[Commit 0aa4a3b](https://github.com/sysprog21/lab0-c/commit/0aa4a3b6c3a34aada690434c5cd3b46f5dd087a6)
由於這兩個函式邏輯高度相似，因此引入共用的輔助函式 `purge`，透過布林參數 `descend` 區分升冪與降冪兩種情境。
刪除判斷依賴當前節點後方的元素，因此實作了反向的 `list_for_each_safe`，並在遍歷過程中追蹤目前的「極值」（最大或最小）作為基準，判斷每個節點是否應被移除。
儘管函式的主要目標為刪除節點，但在測試期間發現若未釋放記憶體，會導致錯誤發生。因此在移除節點的同時，明確執行記憶體釋放以避免記憶體洩漏。
```c
int purge(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return 1;
int cnt = 1;
struct list_head *node = NULL, *safe = NULL, *peak = head->prev;
for (node = head->prev->prev, safe = node->prev; node != head;
node = safe, safe = node->prev) {
const char *s1 = list_entry(peak, element_t, list)->value;
const char *s2 = list_entry(node, element_t, list)->value;
if ((!descend && strcmp(s1, s2) <= 0) ||
(descend && strcmp(s1, s2) >= 0)) {
list_del(node);
q_release_element(list_entry(node, element_t, list));
} else {
peak = node;
cnt += 1;
}
}
return cnt;
}
```
呼叫 `purge` 並傳入 `descend = false` ，表示執行升冪保留。
```c
int q_ascend(struct list_head *head)
{
return purge(head, false);
}
```
呼叫 `purge` 並傳入 `descend = true` ，表示執行降冪保留。
```c
int q_descend(struct list_head *head)
{
return purge(head, true);
}
```
### `q_merge`
>[Commit 1cf7897](https://github.com/sysprog21/lab0-c/commit/1cf78977df128588bdd1d0701a29652b9d91d867)
檢查輸入的佇列是否為空或為 `NULL`，再進行後續操作。
遍歷鏈結串列中的每個佇列，並將其合併為單一排序後的佇列。
初始化一個 `dummy` 節點以進行合併操作，並正確設置節點的 `next` 與 `prev` 指標。
若 `descend` 旗標為 `true`，則選擇性地對合併後的佇列進行反轉。
最後將排序完成的佇列合併回原始的 list 中。
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return 0;
int size = 0;
struct list_head *merge_queue = NULL, *iter = head->next;
while (iter != head) {
queue_contex_t *curr_queue = list_entry(iter, queue_contex_t, chain);
size += curr_queue->size;
curr_queue->q->prev->next = NULL;
merge_queue =
merge_sorted_lists(merge_queue, curr_queue->q->next, descend);
iter = iter->next;
INIT_LIST_HEAD(curr_queue->q);
}
LIST_HEAD(dummy_head);
dummy_head.next = merge_queue;
struct list_head *node = NULL, *safe = NULL;
for (node = &dummy_head, safe = dummy_head.next; safe->next;
node = safe, safe = node->next) {
safe->prev = node;
}
safe->next = &dummy_head;
dummy_head.prev = safe;
list_splice(&dummy_head, list_first_entry(head, queue_contex_t, chain)->q);
return size;
}
```
### `make test`
```c
+++ TESTING trace trace-17-complexity:
# Test if time complexity of 'q_insert_tail', 'q_insert_head', 'q_remove_tail', and 'q_remove_head' is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
## Valgrind + 自動測試程式
### [Valgrind ](https://en.wikipedia.org/wiki/Valgrind)
>參考 [Eric chou]((https://hackmd.io/@charliechiu/linux2025-homework1#Valgrind--%E8%87%AA%E5%8B%95%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F))
`Valgrind` 是一套運行於使用者層級（`user space`）的動態分析工具框架，可用來檢測程式執行期間的記憶體使用狀況與潛在錯誤。使用者層與核心層（`kernel space`）的主要差異，在於可存取的記憶體範圍受限於虛擬記憶體機制，從而隔離應用程式與作業系統，避免一般應用程式誤修改系統核心的資料。而當 `user space` 中的應用需要存取系統資源時，則必須透過 `system call` 呼叫進入 `kernel space`。
`Valgrind` 本身並非直接執行原始機器碼，而是運用 `just-in-time (JIT)` 編譯技術，將機器指令轉換為中介語言 `(Intermediate Representation, IR)`，並在特定區段插入對應分析工具的檢查邏輯，再重新轉譯成機器碼執行。這使得 `Valgrind` 可以在不中斷執行流程的情況下動態觀察記憶體使用狀況，但也導致效能下降，通常會比原程式慢上數倍。
### 觀察記憶體分配
為了分析程式在執行過程中對堆記憶體（heap memory）的使用狀況，我們使用 `Valgrind`工具套件中的子工具 `massif`。
`massif` 可提供程式在各個時間點的記憶體分配情況，並協助找出記憶體使用量高峰點或潛在的記憶體浪費問題。
這個工具可以載入 `massif` 產生的 `massif.out.<pid>` 檔案，讓你清楚看到記憶體分配的變化趨勢圖。
```
# 安裝可視化工具
# 我們可以使用 massif-visualizer 這個圖形介面工具來視覺化分析結果
$ sudo apt install massif-visualizer -y
```
在 `Makefile` 中新增以下目標 `check-massif`，目的是對 `qtest` 使用 `Valgrind` 的 `massif` 工具進行記憶體用量分析，並使用指定的輸入測資檔 `trace-06-ops.cmd` 執行測試。
```
check-massif: qtest
valgrind --tool=massif ./$< -v 3 -f traces/trace-06-ops.cmd
```
執行以下指令會產生一個檔案，例如：`massif.out.12345`
```
$ make check-massif
```
你可以使用以下指令以文字方式檢視記憶體使用歷程：
```
$ ms_print massif.out.12345
```
會得到像是以下的輸出
```
KB
15.24^ ##
| @ : # : :::::
| @ ::: # : :: :: ::
| @ ::: # :::: :: ::
| :@:@:: @::::: : # :::: @:::::
| @:@@:@ :: ::::@:::::::::@:@# :::: @:::::
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| ::::@ @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| : @ @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| : @ @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| : @ @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
| : @ @:@:@@:@ ::::::::@:::::::::@:@# :::: @:::@:
0 +----------------------------------------------------------------------->ki
0 835.4
```
也可以使用 GUI 工具：
```
$ massif-visualizer massif.out.12345
```
會得到像是以下的輸出
#### 分析上圖記憶體用量
```c
new // 建立新 queue，尚未分配記憶體
ih RAND 4 // 插入 4 筆隨機資料（insert head），記憶體用量小幅上升
it gerbil 3 // 插入 'gerbil' 到 tail，記憶體上升
it lion 2 // 插入 'lion' 到 tail，記憶體再次上升
it zebra 2 // 插入 'zebra' 到 tail，記憶體達到小波峰，堆區開始出現 malloc_or_fail 分配
sort // 對 queue 做排序，記憶體使用幾乎不變（應為 in-place 排序）
dedup // 刪除重複節點，觀察到部分記憶體釋放（queue_remove 出現，堆下降）
free // 釋放 queue，堆區記憶體幾乎歸零
new // 再次建立 queue，重新進入分配階段
ih a // 插入 a，記憶體開始重新配置
ih b
ih c
ih d
ih a // 插入重複節點 'a'
ih c // 插入重複節點 'c'，記憶體繼續增加（test_malloc 占主體）
descend // 降冪排列，記憶體維持原狀
rh d // 移除 head 'd'，記憶體出現 queue_remove，記憶體下降
rh c // 繼續移除
rh b
rh a // 每次移除都釋放一部分記憶體
free // 最後 queue 全部移除與釋放，回到初始狀態
new // 第三次建立 queue
ih a 3 // 插入 a (weight 3)，記憶體再次配置
ih b
ih c
ih d
ih e 2 // 插入 e (weight 2)
reverseK 3 // 每 3 個反轉一次，記憶體使用無明顯變化
rh d // 開始移除節點，queue_remove 出現，再次造成釋放
rh e
rh e // 嘗試移除已刪除的節點，記憶體未變
rh a
rh b
rh c // 持續釋放 queue 節點
rh a // 試圖移除空 queue 節點
rh a // 試圖移除空 queue 節點，最終記憶體幾乎歸零
```
0 ～ 約 310,000：
- 使用 `new`, `ih`, `it` 指令建立 queue 並插入多筆資料。
- `ih RAND 4` 插入隨機值，`it gerbil 3`, `it lion 2`, `it zebra 2` 插入具權重項目。
- 記憶體逐步增加，來源包括：
- `malloc_or_fail` 分配節點記憶體。
- `_IO_file_doallocate` 分配輸出緩衝區。
---
約 310,000：
- 執行 `sort` 與 `dedup`：
- 重複元素（如 zebra）被移除。
- `queue_remove` 開始釋放部分記憶體。
- 圖中出現第一次明顯的記憶體下滑。
---
約 310,000 ～ 350,000：
- 執行 `free` 釋放整個 queue，記憶體歸零。
- 接著再次執行 `new` 與多次 `ih` 指令插入：
- 插入 a、b、c、d 及重複的 a、c。
- 記憶體快速跳升，反映節點重新配置。
---
約 350,000 ～ 700,000：
- 執行 `descend` 排序後，連續呼叫 `rh`（remove head）：
- 順序移除 d, c, b, a。
- 每次 `rh` 對應圖中鋸齒狀記憶體下滑。
---
約 700,000 ～ 800,000：
- 第三次 `new` 建立 queue，插入 a、b、c、d、e。
- `reverseK 3` 對前三個元素做 group reverse：
- 造成短暫記憶體峰值（圖中達到 14.4 KiB）。
- 接著多次 `rh` 將所有元素移除。
---
約 850,000：
- 所有資料移除後，記憶體歸零。
- 程式正常結束，無記憶體殘留。
---
小結
- 圖中明顯的記憶體上升段落對應插入與 `reverseK` 操作。
- 鋸齒式下降對應 `remove` / `remove head` 操作。
- `free` 對應一次性大量釋放記憶體。
- 此圖可幫助開發者檢查記憶體分配策略與潛在洩漏點。
```c
bool q_insert_tail(struct list_head *head, const char *s, int order)
{
int len = strlen(s);
char *value_buf = malloc(len + 1);
if (!value_buf)
return false;
memcpy(value_buf, s, len + 1); // 拷貝 '\0'
element_t *elem = malloc(sizeof(element_t));
if (!elem) {
free(value_buf);
return false;
}
elem->value = value_buf;
elem->order = order;
list_add_tail(&elem->list, head);
return true;
}
```
```
user@ting:~/linux2025/lab0-c$ ./test_sort_standalone
Generating 10000000 random strings...
[Top-down] Sorting...
[Kernel bottom-up] Sorting...
[Top-down] Sorted: Correct, Time: 6.733542 sec
[Kernel bottom-up] Sorted: Correct, Time: 5.658984 sec
Are the sorted lists identical? Yes
First 10 elements after Top-down sort:
00(10954) 00(34809) 00(48758) 00(57181) 00(73406) 00(121297) 00(146560) 00(157486) 00(179901) 00(187963)
First 10 elements after Kernel bottom-up sort:
00(10954) 00(34809) 00(48758) 00(57181) 00(73406) 00(121297) 00(146560) 00(157486) 00(179901) 00(187963)
[Top-down] Average sorting time: 1.149401 sec
[Kernel bottom-up] Average sorting time: 0.591669 sec
```
Sign in with Wallet
Connect another wallet