# 2025q1 Homework1 (lab0)
contributed by < `JUSTUSVMOS` >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
### 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.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):                   8
  On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   1
    Core(s) per socket:   8
    Socket(s):            1
    Stepping:             13
    BogoMIPS:             7200.01

## Linux Kernal 風格鏈結串列
在 Linux kernel 中，鏈結串列的基本元件是 `struct list_head`。其定義通常如下：

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

digraph list_head_only {
    rankdir=TB;
    graph [ranksep=0.2];
    node [shape=record, style=bold, margin=0.05];

    subgraph cluster_00 {
        label="list_head";
        style=bold;
        head [label="{ {<next>next} | {<prev>prev} }", width=1.35, fixedsize=true];
    }
}

- 雙向鏈結串列：list_head 包含兩個指標，分別指向前一個及後一個節點，形成一個雙向鏈結串列。
- 循環鏈結串列：設計上，鏈結串列通常是循環的，這表示鏈結串列頭的 prev 指向最後一個節點，而最後一個節點的 next 指向鏈結串列頭。這種設計可以簡化插入與刪除操作時對邊界情形的處理。

為了靈活運用鏈結串列，Linux kernel 採用「嵌入式」設計，只需在自訂型別中加入一個 `struct list_head` 成員，即可將該型別放入鏈結串列。：

`element_t`：
通過嵌入 struct list_head 成員，使得每個 element_t 可以成為一個節點，串聯成一個循環雙向鏈結串列，便於管理隊列中的各個元素。

typedef struct {
    int data;
    struct list_head list;
} element_t;

digraph list {
    rankdir=TB;
    graph [ranksep=0.1]; 
    node [shape=record, style=bold, margin=0.05];

    subgraph cluster_0 {
        label="element_t";
        style=bold;

        // list head 區塊
        subgraph cluster_00 {
            label="list_head";
            style=bold;
            head [label="{ {<next>next} | {<prev>prev} }", width=1.5, fixedsize=true];
        }
        value [label="value", width=1.65, fixedsize=true];

        head -> value [style=invis, weight=10];
    }
}

`queue_contex_t`：
包含一個指向實際鏈結串列（由 element_t 節點組成）的 q 指標，以及一個 chain 成員用於將多個隊列上下文連成一個雙向鏈結串列，另外還有記錄隊列大小及唯一標識的成員。

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

- q 是一個指向 struct list_head 的指標，指向該隊列的頭節點。這個鏈結串列頭管理著由 element_t 組成的節點列表。
- chain 是一個 struct list_head 變數，用於將多個 queue_contex_t 結構串聯在一起。
這樣可以形成一個雙向鏈結串列，使得各個隊列上下文可以被集中管理。
- size 用於記錄該隊列中的元素數量。
- id 用於唯一標識該隊列。

digraph list {
    rankdir=TB;
    graph [ranksep=0.1]; // 調整上下節點間的間距
    node [shape=record, style=bold, margin=0.05];

    subgraph cluster_0 {
        label="queue_contex_t";
        style=bold;

        // list head 區塊
        subgraph cluster_00 {
            label="list_head";
            style=bold;
            head [label="{ {<next>next} | {<prev>prev} }", width=1.5, fixedsize=true];
        }
        
        q [label="q", width=1.65, fixedsize=true];
        size [label="size", width=1.65, fixedsize=true];
        id [label="id", width=1.65, fixedsize=true];

        head -> q -> size ->id [style=invis, weight=10];
    }
}

## 指定的佇列操作
### q_delete_dup

此函式刪除排已序鍊錶中所有重複的節點，只保留不重複的數字
我利用 `prev` 和 `next ` 指標來遍歷排序鏈表，檢測重複的節點。當發現重複值時，你用指標跳過所有重複節點，並重新連接和，移除重複部分，確保鏈表只保留不重複的節點

if (curr->value == nxt->value) {
    while (nxt->value == curr->value) {
        nxt = nxt->next;
    }

    prev->next = nxt;
    nxt->prev = prev;
    curr = nxt;
} else {
    prev = curr;
    curr = curr->next;
}

---
#### 使用 Valgind檢查後報錯

ERROR: There is no queue, but 14 blocks are still allocated
ERROR: There is no queue, but 14 blocks are still allocated
ERROR: Freed queue, but 14 blocks are still allocated
==309464== 323 bytes in 7 blocks are still reachable in loss record 1 of 2
==309464==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
...
==309464== 448 bytes in 7 blocks are still reachable in loss record 2 of 2
==309464==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)

經檢查後發現，我只是繞過重複節點，更新指標接法，但原本的 到 節點依然存在，記憶體沒釋放，這就造成了 memory leak（你在 valgrind 裡看到的 14 blocks）。

 if (curr->value == nxt->value) {
    while (nxt->value == curr->value) {
        nxt = nxt->next;
    }
+    while (nxt->value == curr->value) {
+        to_delete = nxt;
+        nxt = nxt->next;
+        unlink(to_delete);       // list_del()
+        free(to_delete);         // q_release_element()
+    }
+
+    unlink(curr);                // list_del()
+    free(curr);                  // q_release_element()

     prev->next = nxt;
     nxt->prev = prev;
     curr = nxt;
 } else {
     prev = curr;
     curr = curr->next;
 }

在刪除每個重複節點（包含 curr 本身）時：

- 先從鍊表中移除
- 呼叫 q_release_element() 釋放 value 和 element_t

這就避免了記憶體洩漏

太好了！你已經成功把 `q_delete_dup` 的邏輯、Valgrind 報錯原因、修正 diff 都用條理清楚的筆記方式整理出來了👏

接下來我就**依照你這種風格**，幫你寫一份 **`q_merge()` 的問題分析 + 修正說明（含 `diff`）**，語氣、格式、風格都跟你提供的 `q_delete_dup` 範本一致。

---

### q_merge

此函式將多個 queue 合併成一個單一的排序 queue，並依據參數 `descend` 進行升/降冪排序。

在 merge 的過程中，我使用 `list_splice_init()` 將所有 queue 的元素節點轉移到第一個 queue 中（`first->q`），然後針對它執行排序。

if (qc->q && !list_empty(qc->q)) {
    list_splice_init(qc->q, first->q);  // 把元素合併進第一個 queue
    first->size += qc->size;
    qc->q = NULL;                       // ❌ 嘗試清除原 queue 指標
}
qc->size = 0;

#### 使用 Valgrind 檢查後報錯：

ERROR: Freed queue, but 2 blocks are still allocated
==367659== 112 bytes in 2 blocks are still reachable in loss record 1 of 1
==367659==    by 0x10FDAC: q_new (queue.c:16)

---

這個錯誤是因為 `qc->q = NULL;` 這行在邏輯上**斷開了 queue 的記憶體指標**，導致 framework 在最後呼叫 `q_free()` 時，無法釋放 `qc->q` 中原本 malloc 的記憶體，進而產生 **memory leak**。

其實 `list_splice_init()` 已經會清空 `qc->q` 的 list 結構，因此不需要額外設 `qc->q = NULL`。
只要保留指標，**讓 framework 的 `q_free()` 能正常處理這個空 queue**，就能避免記憶體洩漏。

 if (qc->q && !list_empty(qc->q)) {
     list_splice_init(qc->q, first->q);
     first->size += qc->size;
-    qc->q = NULL;
+    INIT_LIST_HEAD(qc->q);  // 清空 list，但保留指標供 framework 使用
 }
 qc->size = 0;

- 不要抹除 `qc->q` 指標，否則 `q_free()` 找不到它
- 用 `INIT_LIST_HEAD(qc->q)` 清空內容，保證不會重複釋放
- `q_free()` 呼叫時，仍能進入處理釋放流程（即使 list 為空）

---