# 2025q1 Homework1 (lab0)
contributed by <`I-Ying-Tsai`>

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ uname -a
Linux i-ying-tsai-G5-KF5 6.11.0-17-generic #17~24.04.2-Ubuntu SMP PREEMPT_DYNAMIC Mon Jan 20 22:48:29 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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.

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ ldd --version
ldd (Ubuntu GLIBC 2.39-0ubuntu8.4) 2.39
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.
Written by Roland McGrath and Ulrich Drepper.

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ 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):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                GenuineIntel
  Model name:             13th Gen Intel(R) Core(TM) i7-13620H
    CPU family:           6
    Model:                186
    Thread(s) per core:   2
    Core(s) per socket:   10
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   33%
    CPU max MHz:          4900.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5836.80

## 實作 queue.[ch]

### q_new [a31f615](https://github.com/sysprog21/lab0-c/commit/a31f6155c8a6e303294987806a839636e264bb84)

**目的**
建立並初始化一個 `Linux Kernel` 風格的雙向鏈結串列（doubly linked list）頭節點。

1. 請求 `head` 大小的記憶體空間(透過 `malloc`)。
2. 檢查記憶體配置 (memory allocation) 是否成功，若是失敗，則返回 `NULL`。
3. 使用 `INIT_LIST_HEAD` 初始化該節點，使其的 `prev` 和 `next` 都指向自己。
4. 返回該 `head` 地址。

---

### q_free [a31f615](https://github.com/sysprog21/lab0-c/commit/a31f6155c8a6e303294987806a839636e264bb84)

**目的**
釋放整個鏈結串列佔用的記憶體，避免記憶體洩漏 (memory leak)。

1. 若 `head` 為 `NULL`，則直接返回，避免無效操作。
2. **使用 `list_for_each_safe` 進行走訪**，確保在刪除節點時不影響遍歷順序。
- 若使用 `list_for_each`，則刪除當前節點後，`next` 指標將指向已被釋放的記憶體，可能導致 **迷途指標 (dangling pointer) 或 segmentation fault**。
- `list_for_each_safe` 會預先存儲 `next` 節點，確保刪除當前節點後，能繼續正確遍歷。
3. 使用 `list_entry` 取得 `element_t` 結構，確保可以正確存取 `value`。
4. 使用 `list_del` 將節點從鏈結串列中移除。
5. 釋放 `element_t->value`，確保字串記憶體被回收。
6. 釋放 `element_t` 本身，確保節點記憶體被回收。
7. 釋放 `head` 本身，確保鏈結串列頭部的記憶體也被回收。

---

### q_insert_head [fce1b7c](https://github.com/sysprog21/lab0-c/commit/fce1b7c1a90117b0543ffcbd7c75cacf241c7341)

**目的**
在鏈結串列的頭部插入一個新的元素。

1. 檢查 `head` 和 `s` 是否為 `NULL`，確保鏈結串列有效。
2. 分配 `element_t` 節點的記憶體，確保成功分配。
3. 使用 `strdup` 為 `value` 分配記憶體，確保成功存儲字串。
4. 使用 `list_add` 將該節點插入 `head` 之後，確保新節點成為新的頭部
5. 返回 `true` 表示成功，或 `false` 表示失敗。

---

### q_insert_tail [6d84b0c](https://github.com/sysprog21/lab0-c/commit/6d84b0c7360836ee02f11cfdc0a928e201786ad5)

**目的**
在鏈結串列的尾端插入一個新的元素。

1. **檢查 `head` 和 `s` 是否為 `NULL`**，確保鏈結串列有效，避免無效操作。
2. **分配 `element_t` 節點的記憶體 (`malloc`)**，確保成功分配，避免 `NULL` 指標操作。
3. **使用 `strdup` 為 `value` 分配記憶體**，確保字串內容獨立，不受外部變更影響。
- 若 `strdup` 失敗，則釋放 `element_t` 節點，避免記憶體洩漏。
4. **使用 `list_add_tail` 插入節點至 `head` 之前**，確保新節點成為尾部節點。
5. 返回 `true` 表示成功，或 `false` 表示失敗。

---

### q_remove_head [feef7ff](https://github.com/sysprog21/lab0-c/commit/feef7ff81266bab0e75f7ef511e35dd5415aea49)

**目的**
從鏈結串列的頭部刪除一個節點，並返回該節點的指標。

1. **檢查 `head` 是否為 `NULL` 或 `list_empty(head)`**，確保鏈結串列有效，避免無效操作。
2. **獲取 `head` 之後的第一個節點 (`head->next`)**，確保該節點可移除。
3. **使用 `list_del` 從鏈結串列中移除該節點**，確保鏈結完整且不影響其他節點。
4. **若 `sp` 非空，則複製 `value` 到 `sp`，並確保字串長度不超過 `bufsize`**，防止 `buffer overflow`。
5. **返回刪除的節點指標 (`element_t *`)**，由呼叫者負責釋放記憶體 (`free(node)`)。

**比較：**
- **使用 `list_del` 直接移除節點**，確保 `O(1)` 時間複雜度。

---

### q_remove_tail [feef7ff](https://github.com/sysprog21/lab0-c/commit/feef7ff81266bab0e75f7ef511e35dd5415aea49)

**目的**
從鏈結串列的尾部刪除一個節點，並返回該節點的指標。

1. **檢查 `head` 是否為 `NULL` 或 `list_empty(head)`**，確保鏈結串列有效，避免無效操作。
2. **獲取 `head` 之前的最後一個節點 (`head->prev`)**，確保該節點可移除。
3. **使用 `list_del` 將該節點從鏈結串列中移除**，確保鏈結完整且不影響其他節點。
4. **若 `sp` 非空，則複製 `value` 到 `sp`，並確保字串長度不超過 `bufsize`**，防止 `buffer overflow`。
5. **返回刪除的節點指標 (`element_t *`)**，由呼叫者負責釋放記憶體。

**比較：**
- **使用 `list_del` 直接移除尾部節點**，確保 **O(1) 時間複雜度**，不影響其他節點。

---

### q_delete_mid [3f716d0](https://github.com/sysprog21/lab0-c/commit/3f716d0eae414f5245ef0daab77af8096f11ca81)

**目的**
刪除鏈結串列的中間節點。

1. 若鏈結串列為空，則返回 `false`。
2. **使用快慢指標 (`slow` & `fast`) 找到中間節點**。
- 如果使用 `q_size` 計算長度，再走訪到 `n/2` 位置刪除，則時間複雜度為 **O(2n) = O(n)**。
- **快慢指標法只需 O(n) 時間，且無需額外變數**，更高效。
3. 使用 `list_del` 將該節點從鏈結串列中移除。
4. 釋放該節點的 `value` 及其記憶體，確保無記憶體洩漏。
5. 返回 `true` 表示刪除成功。

---

### q_delete_dup [3f716d0](https://github.com/sysprog21/lab0-c/commit/3f716d0eae414f5245ef0daab77af8096f11ca81)

**目的**
刪除鏈結串列中所有重複的節點，只保留唯一值的節點。

1. **檢查 `head` 是否為 `NULL` 或 `list_empty(head)`**，確保鏈結串列有效，避免無效操作。
2. **走訪鏈結串列，檢查相鄰節點是否擁有相同 `value`**。
3. **若發現重複值，則刪除所有具有該值的節點**，確保最終結果中該值完全消失。
4. **使用 `list_del` 移除節點**，並 `free` 該節點的 `value` 及其記憶體，防止記憶體洩漏。
5. **返回 `true` 表示至少刪除了一個重複節點，否則返回 `false`**。

---

### q_swap [5567955](https://github.com/sysprog21/lab0-c/commit/55679554dc38d1b67463050ddf49b07146f276fc)

**目的**
交換鏈結串列中每兩個相鄰的節點。

1. 若鏈結串列為空或只有一個節點，則直接返回。
2. **走訪鏈結串列，成對交換相鄰的節點**。
3. **使用 `list_move` 進行交換**，確保鏈結關係正確。
- **如果直接交換節點內部的 `value`**，會降低時間複雜度，但不符合 **Linux 內核的鏈結串列設計**，因為節點通常存儲指標而非具體值。

---

### q_reverse [97d2cb0](https://github.com/sysprog21/lab0-c/commit/97d2cb07b0f9f4cf8118280d9c6ba498c86453f4)

**目的**
反轉鏈結串列的順序，使原本的頭節點變為尾節點，尾節點變為頭節點。

1. 若鏈結串列為空或只有一個節點，則直接返回。
2. **走訪鏈結串列，交換 `next` 和 `prev` 指標**。
3. **若使用 `list_move`**，可以逐個將節點移動到 `head` 之前，達到反轉效果，但時間複雜度較高。
4. **更好做法是直接修改 `next` 和 `prev` 指標**，時間複雜度為 O(n)。

---

### q_reverseK [3d95a49](https://github.com/sysprog21/lab0-c/commit/3d95a49892e3dd3b8ac20c5e4243df813f2826cc)

**目的**
將鏈結串列的節點按照 `k` 個為一組進行反轉。

1. 若 `k <= 1` 或鏈結串列長度小於 `k`，則無需反轉。
2. 計算鏈結串列的長度，確保至少有 `k` 個節點。
3. **使用 `list_for_each_safe` 遍歷鏈結串列，每 `k` 個節點作為一組進行反轉**。
4. **若使用 `q_reverse` 逐個處理 k 個節點**，則需要額外的子串列管理邏輯，但可以利用 `list_move_tail` 簡化操作。
5. **確保反轉後相鄰組之間的連接關係正確**，防止鏈結斷裂。

---

### q_sort [3d95a49](https://github.com/sysprog21/lab0-c/commit/3d95a49892e3dd3b8ac20c5e4243df813f2826cc)

**目的**
對鏈結串列內的元素進行排序（遞增或遞減），提升查詢效率。

1. 若 `head` 為 `NULL` 或為空，則直接返回。
2. **使用合併排序（merge sort）進行排序**，時間複雜度為 **O(n log n)**，適用於鏈結串列。
- 若使用C涵式庫中的快速排序（quick sort），則需頻繁變更指標，導致性能下降。
3. 透過 `merge_sort` 遞迴拆分鏈結串列，使用快慢指標 (`slow & fast`) 找到中間節點。
4. **使用預先寫好的 `merge` 涵式合併排序好的子鏈結串列**，並根據 `descend` 參數決定排序順序。
5. 重新建立 `head`，確保首尾節點連結正確。

---

### q_ascend [5cebf2f](https://github.com/sysprog21/lab0-c/commit/5cebf2fbf43f877871c2e2b82d574d57a124bf10)

**目的**
移除鏈結串列中 **左側值大於右側某個值** 的所有節點，使得最終結果呈現遞增順序。

1. 若 `head` 為 `NULL` 或為空，則直接返回 `0`。
2. **從鏈結串列尾部向前走訪**，確保右側的節點已確認。
3. **使用 `min_elem` 變數追蹤當前最小值**，若當前節點值大於 `min_elem`，則刪除該節點。
4. 使用 `list_del` 移除節點，並釋放該節點的 `value` 及其記憶體。
5. 更新 `head->prev` 以確保鏈結串列結構完整，最後返回剩餘節點數。

---

### q_descend [3d95a49](https://github.com/sysprog21/lab0-c/commit/3d95a49892e3dd3b8ac20c5e4243df813f2826cc)

**目的**
移除鏈結串列中 **左側值小於右側某個值** 的所有節點，使得最終結果呈現遞減順序。

1. 若 `head` 為 `NULL` 或為空，則直接返回 `0`。
2. **從鏈結串列尾部向前走訪**，確保右側的節點已確認。
3. **使用 `max_elem` 變數追蹤當前最大值**，若當前節點值小於 `max_elem`，則刪除該節點。
4. 使用 `list_del` 移除節點，並釋放該節點的 `value` 及其記憶體。
5. 返回剩餘的節點數量。

---

### q_merge [11bbebe](https://github.com/sysprog21/lab0-c/commit/11bbebebeae1399af01af0c83c919729f3ef6f06)

**目的**
將多個鏈結串列合併為一個有序鏈結串列（遞增或遞減）。

1. 若 `head` 為 `NULL` 或為空，則返回 `0`。
2. 取得第一個 `queue_contex_t` 作為主佇列 (`main_ctx`)，確保合併後仍有主鏈結串列存在。
3. **走訪所有子佇列 (`ctx->q`)**，將所有節點移動至 `main_ctx->q` 的尾部。
4. **使用 `q_sort` 重新對合併後的鏈結串列進行排序**，確保最終結果有序。
5. **確保所有子鏈結串列清空，並更新 `size` 記錄總元素數量**。
6. 返回合併後的鏈結串列大小。

**比較：**
- 若使用 **最小堆積 (min-heap) 進行合併**，則可降低排序開銷。

---

## 整合網頁伺服器

---

## 在 qtest 提供新的命令 shuffle

### **1. 介紹**
在 `qtest` 中新增了一個名為 `shuffle` 的命令，其功能是隨機排列 `queue` 中的元素。為了確保公平性，我們使用 **Fisher-Yates Shuffle** 演算法，使每個排列的機率相等。本報告將詳細描述 `q_shuffle` 的實作方式、測試方法以及測試結果。

---

### **2. `q_shuffle` 的實作**

#### **2.1 Fisher-Yates Shuffle**
Fisher-Yates Shuffle 是一種常用於 **均勻隨機打亂** 陣列的演算法，其原理如下：
1. 從 **最後一個元素** 開始，隨機選擇一個索引 `j`（0 ≤ j ≤ i）。
2. **交換** 當前元素 `arr[i]` 與 `arr[j]` 的位置。
3. 持續執行直到所有元素都已經處理。

我的 `q_shuffle` 函數實作如下：

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || head->next == head->prev) {
        return;
    }

    int len = q_size(head);
    element_t **arr = malloc(len * sizeof(element_t *));
    if (!arr)
        return;

    struct list_head *cur = head->next;
    for (int i = 0; i < len; i++, cur = cur->next) {
        arr[i] = list_entry(cur, element_t, list);
    }

    srand(time(NULL));

    for (int i = len - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        if (i != j) {
            list_move(&arr[i]->list, &arr[j]->list);
        }
    }

    q_show(3);
    free(arr);
}

#### **2.2 `shuffle` 命令的新增**

在 `qtest.c` 中，我新增了 `do_shuffle` 來呼叫 `q_shuffle`，並且報告執行結果。

static bool do_shuffle(int argc, char *argv[])
{
    if (!current || !current->q) {
        report(1, "No queue created");
        return false;
    }

    q_shuffle(current->q);
    return true;
}

並加上 `ADD_COMMAND(shuffle, "Shuffle elements in queue", "");` 來讓 `qtest` 支援 `shuffle` 命令。

### **3. 測試**

由[測試用的 Python 腳本](https://hackmd.io/@sysprog/linux2025-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) test_shuffle.py 測試，得出以下結果以及作圖。

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ python3 test_shuffle.py
Expectation:  41666
Observation:  {'1234': 41807, '1243': 41685, '1324': 41933, '1342': 41378, '1423': 41784, '1432': 41697, '2134': 41739, '2143': 41481, '2314': 41766, '2341': 42083, '2413': 41585, '2431': 41735, '3124': 41610, '3142': 41633, '3214': 41857, '3241': 41499, '3412': 41837, '3421': 41343, '4123': 41784, '4132': 41813, '4213': 41640, '4231': 41628, '4312': 41456, '4321': 41227}
Chi-Square sum:  21.61868189891038


在這個測試中，虛無假設 `H₀` 是：

`q_shuffle() 產生的所有排列是均勻分布的，且各種排列的機率相等。`

---

查表發現，在自由度為 23 的情況下，χ² = 21.6 對應的 p 值大於 0.10。

---

##