# 2024q1 Homework1 (lab0)
contributed by < `LULser0204` >

### Reviewed by `mervin0102`
關於 ascend 與 descend ，如果佇列的走訪方向從節點 `node` 走訪至 `node->next` 稱為正向走訪，可以將迴圈的移動從 ` safe = current->next;` 改為 `safe = current->prev;` ，讓迴圈反向走訪佇列，也就是走訪方向從節點 `node` 走訪至 `node->prev`，可以省略開頭與結尾的 `q_reverse` ， 增進函式效能。
> 在環狀且雙向的鏈結串列中，什麼叫做「反向」？需要明確的定義。又，「模型」是什麼？ :notes: jserv

在 `list.h` 中，函式 `list_move` 就包含 `list_del` 與 `list_add` ， `q_swap` 的實作可以<s>考</s> 使用 `list_move` 使函式更為精簡。

### 開發環境

$ lsb_release -a
No LSB modules are available.
Distributor ID:	Ubuntu
Description:	Ubuntu 22.04.3 LTS
Release:	22.04
Codename:	jammy

$ 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) Xeon(R) CPU E3-1231 v3 @ 3.40GHz
    CPU family:          6
    Model:               60
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6799.97

## 佇列實作

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

> 收到
:::
在開始之前，我先觀察 `list.h` 檔裡面所定義的結構

雙向鏈結串列

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

以及在 `queue.h` 檔案第 23~26 行裡面所定義的鏈結串列元素

typedef struct {
    char *value;
    struct list_head list;
} element_t;

### q_new

:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::

建立新的「空」佇列

根據老師 `lab0` 的教材可以得知「空」佇列的定義
> 「空」 (empty) 的佇列是指向有效結構，但開頭 (head) 的值為 NULL;

我使用 `malloc` 配置記憶體空間，若成功配置足夠空間，則讓 `new` 的 prev 和next 指向自身，否則返回 `NULL`

> [commit ec46a29](https://github.com/LULser0204/lab0-c/commit/ec46a2920e405c4ad3c7f7f81d209f5867749c50)

後來實作 `q_free` 時，研究在 Linux 核心中 queue 的結構，點進去 [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) ，第一個就是 `void INIT_LIST_HEAD(struct list_head *list)` ，在 `list.h` 找到其定義後，回到 `q_new` 在程式碼中使用 API 實作

:::danger
詳閱作業說明，自 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) fork 再提交對應的 commits
> 收到，抱歉。已另外 fork 並且使用
> git format-patch HEAD~20..HEAD -- queue.c 將 patch 紀錄抓下來
> git am /path/to/patch/files/*.patch 將修改歷史套用上去
> "git pull origin master" "git push origin master"推送上去
:::

> 修改後的程式碼: [commit 9e38721](https://github.com/LULser0204/lab0-c/commit/9e38721f14dcfa513636657ad0d07204d4777945)

### q_free
> commit [3eee3a5](https://github.com/LULser0204/lab0-c/commit/3eee3a55cb0c9b18dece57a5150d5b7335438235)

:::danger
使用你 fork 後得到的 GitHub repository 對應的超連結，也就是以 https://github.com/LULser0204/lab0-c 開頭
> 已修改
:::

釋放佇列所佔用的記憶體

:::danger
文字訊息不要用圖片展現，而且上傳圖片要留意權限。
> 收到
:::

#### 實作:

在 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) 觀察佇列在 Linux 核心中的結構，先用 `list_for_each_safe` 走訪所有成員，而 `node` 紀錄該成員的位址，釋放該節點所指向的 `value` ，接著使用 [list_del函式](https://github.com/LULser0204/Linuxkernel/blob/master/list.h#L134) 移去 該節點，再釋放 `element_t` 。

最後也需要將 `head` 的 `list_head` 記憶體也釋放。

:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
> 收到
:::

### insert_head
> commit [8575d8a](https://github.com/LULser0204/lab0-c/commit/8575d8a9a50aa78a7b618af626ac5a4de1d316ec)

在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)

先檢查佇列是否為空，為空則 `return false`

接著先配置記憶體給新節點 `new_head` ，接著再配字記憶體給字串，如果配置成功，則用 strcpy 將內容複製到 `new_head` 。
最後在使用 [list_add](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) 將指定的節點插入佇列 `head` 的開頭

但我在 git 上去的時候，跳出這訊息

Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/vision/linux2024/lab0-c/queue.c
56:    strcpy(new_head->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml

[Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 提到:
> strcpy
The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.

所以我做了以下變更，使用了 `strncpy` 來避免 `buffer overflow` ，並手動增加 `'\0'` 字元以符合佇列的規範

:::danger
詳閱作業說明，自 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) fork 再提交對應的 commits
:::

### insert_tail

:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
> 收到
:::

在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)

概念上和 `insert_head` 相同，唯一不同的地方在於使用 [`list_add_tail`](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) 來將指定的節點插入 `head` 的尾端。

> [commit f151ea7](https://github.com/LULser0204/lab0-c/commit/f151ea7369de44536d1aec838cb835427e9fbd8e)

### remove_head

:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::

在佇列開頭 (head) 移去 (remove) 給定的節點

由於是雙向鏈結串列，所以 `head->next` 為佇列的第一個元素，只需要使用 [`list_del`](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) 移除第一個元素，之後透過 `list_entry` 將 `list_head` 的 `entry` 回傳即可。

但再我測試 [trace-08-robust](https://github.com/sysprog21/lab0-c/blob/master/traces/trace-08-robust.cmd) 顯示以下內容:

cmd>new
l = []
cmd> rh
Warning: Calling remove head on empty queue
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

但當我執行 `remove_tail` 時，卻沒這問題，所以我更改了判斷邏輯讓函式更明確的檢查鏈節列表是否為空。

> [commit ee38aaa](https://github.com/LULser0204/lab0-c/commit/ee38aaab9e6c8486b28404e37fb61deabe0e180c)
> [commit 6f13172](https://github.com/LULser0204/lab0-c/commit/6f13172155d47df32ec259402d825a6f2f5b6066)
> 後來使用了 `list_first_entry` 簡化了函式
> [commit 9a3c355](https://github.com/LULser0204/lab0-c/commit/9a3c35590a40fa15aed18e0f6d55cfa1df5ca8d1)

### remove_tail

:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::

在佇列尾端 (tail) 移去 (remove) 給定的節點，概念上和 `remove_head` 相似。

由於是雙向鏈結串列，所以 `head->prev` 為佇列的最後一個元素。只需要使用 [`list_del`](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) 移除第一個元素，之後透過 `list_entry` 將 `list_head` 的 `entry` 回傳即可。

詳細實作: [commit ee38aaa](https://github.com/LULser0204/lab0-c/commit/ee38aaab9e6c8486b28404e37fb61deabe0e180c)
> 後來使用了 `list_last_entry` 簡化了函式
> [commit 9a3c355](https://github.com/LULser0204/lab0-c/commit/9a3c35590a40fa15aed18e0f6d55cfa1df5ca8d1)

### delete_mid
> [commit e488d2a](https://github.com/LULser0204/lab0-c/commit/e488d2a0c2f6ac1d966006e0d39c3022be1cbe4c)

:::danger
修正上方超連結，對應到實際修改的 commit，而非 patch!
> 抱歉，已重用
:::

:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
> 已修改
:::

移走佇列中間的節點。

參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List)使用快慢指標來找出佇列的中點，迴圈結束後 `slow` 指向的正是中間節點，接著使用 `list_del` 刪除並釋放記憶點空間

:::danger
注意用語
> 收到
:::

原理: `fast` 指標每次移動兩個，而 `slow` 指標只移動一格，故結束後慢指標位置就會在中點

:::danger
考慮到環狀且雙向鏈結串列，你能否撰寫更快更精簡的程式碼？
> 能。因為是環狀的關係，所以可以讓兩個指標從不同方向前進。
> 現在有個環狀的串列有 9 個節點。假設 fast 指標逆時針移動， slow 指標順時針移動，則只需 3 輪便可找到中點；如果兩個指標都順時針移動的話，則需要 4 輪。
:::

### delete_dup

在佇列已經排序的狀況下，移走佇列中具備重複內容的節點。

使用 `list_for_each_entry_safe` 走訪每個節點，並且分別用 `before` 和 `tmp` 紀錄當前節點和下個節點是否相同

`flag` 來記錄當前節點是不是重複

用 `tmp` 來承擔被刪除與釋放空間的任務。我當時想說刪除 `before` (畢竟 `tmp` 記錄下一個節點的位置了)不會怎樣，結果一直觸發 "Segmentation fault" 問 `chatgpt` 才知道是什麼問題

但當我覺得這麼改會沒問題的時候， "Segmentation fault" 還是一直發生， `chatgpt` 告訴我釋放 `tmp` 後，嘗試存取它，可能會導致未定義行為，後來改用 `q_release_elememt` 來釋放節點。

:::danger
access 的翻譯是「存取」，而非「訪問」(visit)
> 已修正
:::

> 使用 `q_release_element` 確保正確釋放，並再釋放後不再存取它

詳細實作:[commit 536d842](https://github.com/LULser0204/lab0-c/commit/536d842a316b34de85c504abde45e11009712155)
修改好的實作:[commit 95c742b](https://github.com/LULser0204/lab0-c/commit/95c742bab9a76bc21d1a58610ed0e27d94028e2c)

### q_swap

交換佇列中鄰近的節點

交換兩個相鄰節點的位置 `(in pairs)`。直覺上想到的方法是先用 `nextnext` 紀錄下一輪的位置，再用 `cur` 和 `tmp` 分別記錄該輪數組 (兩兩一組)第一個元素及第二個元素，使用 [`list_add`](https://hackmd.io/@sysprog/c-linked-list#%E7%B0%A1%E5%8C%96%E7%9A%84%E5%AF%A6%E4%BD%9C) 和 [`list_del`](https://hackmd.io/@sysprog/c-linked-list#%E7%B0%A1%E5%8C%96%E7%9A%84%E5%AF%A6%E4%BD%9C) 完成交換位置

> [commit 3a7f681](https://github.com/LULser0204/lab0-c/commit/3a7f681133e06fdcc0e51dfbaf4308e76994124d)

### q_reverse
> [commit 7d7ee93](https://github.com/LULser0204/lab0-c/commit/7d7ee9380957c1dc96c3701678bc580e97b1d748)

以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點

經過 `q_swap` 的實作經驗後，反轉鏈結串列只需要用 `list_for_each_safe` 走訪每個結點，並將每個節點用 `list_del` 和 `list_add` 讓各個節點從頭加入佇列，就能達到反轉的效果

### q_reverseK
> [commit e976c76](https://github.com/LULser0204/lab0-c/commit/e976c76bd167674716f5722f2977e017a5e3dceb)

類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列

我直覺上的想法是用兩層迴圈，第一次跑的次數是有「幾組」節點用 `q_size(head)/k`，第二層則跑 k 次。
在最裡面那層迴圈的作法和將整個 `q_reverse` 相似，將這輪翻轉的子佇列先接在另一條佇列上，最後再將其用 `list_splice` 接回 head

### q_sort
> [commit 491cd41](https://github.com/LULser0204/lab0-c/commit/491cd410be88846fbe5f0ec9d094c103e3b26afc)

digraph G {
    node [shape=record, height=.1];
    
    subgraph cluster_0 {
        style=filled;
        color=lightgrey;
        node [style=filled, color=white];
        a0 [label="2 | 5 | 4 | 6"];
        a1 [label="8 | 1 | 7 | 3"];
        label = "unsorted list";
        color=cyan2;
    }

    subgraph cluster_1 {
        style=filled;
        color=lightgrey;
        node [style=filled, color=white];
        a2 [label="2 | 5"];
        a3 [label="4 | 6"];
        a4 [label="8 | 1"];
        a5 [label="7 | 3"];
        label = "divide";
        color=cyan2;
    }

    subgraph cluster_2 {
        style=filled;
        color=lightgrey;
        node [style=filled, color=white];
        a6 [label="2"];
        a7 [label="5"];
        a8 [label="4"];
        a9 [label="6"];
        a10 [label="8"];
        a11 [label="1"];
        a12 [label="7"];
        a13 [label="3"];
        label = "sorted lists";
        color=coral;
    }

    subgraph cluster_3 {
        style=filled;
        node [style=filled];
        b0 [label="2 | 5"];
        b1 [label="4 | 6"];
        b2 [label="1 | 8"];
        b3 [label="3 | 7"];
        label = "merge";
        color=darkolivegreen1;
    }

    subgraph cluster_4 {
        style=filled;
        node [style=filled];
        c0 [label="2 | 4 | 5 | 6"];
        c1 [label="1 | 3 | 7 | 8"];
        label = "merge";
        color=darkolivegreen1;
    }

    subgraph cluster_5 {
        style=filled;
        node [style=filled];
        d [label="1 | 2 | 3 | 4 | 5 | 6 | 7 | 8"];
        label = "final merge";
        color=darkolivegreen1;
    }
    a0 -> a2;
    a0 -> a3;
    a1 -> a4;
    a1 -> a5;
    
    a2 -> a6;
    a2 -> a7;
    a3 -> a8;
    a3 -> a9;
    a4 -> a10;
    a4 -> a11;
    a5 -> a12;
    a5 -> a13;
    
    a6 -> b0;
    a7 -> b0;
    a8 -> b1;
    a9 -> b1;
    a10 -> b2;
    a11 -> b2;
    a12 -> b3;
    a13 -> b3;

    b0 -> c0;
    b1 -> c0;
    b2 -> c1;
    b3 -> c1;

    c0 -> d;
    c1 -> d;
}

以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法

參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)提到的方法

將整個數列不停地拆成兩推，直到每堆只剩下一個元素，再兩兩合併直到合併成一個數列為止。我一開始想法是用前面使用前面的 `delete_mid` ，來將佇列分成兩段閉循環的佇列，但會一直觸發 `Segmentation fault occurred`　

後來，參考 [wanghanchi](https://hackmd.io/@wanghanchi/linux2023-lab0#q_sort) 學長採取將環狀鏈結串列斷開，子串列的結尾設為 NULL ，當成單向鏈結串列處理，如此一來也能在迭代的時候方便判斷是否抵達尾端。

`split` 函式:使用前面提到的快慢指針找到中點，再將其拆成兩半；

`mergeSort` 函式: `left` 和 `right` 逐一比較，但我那時候沒有考慮到一種情形：如果 `left` 都用完， `right` 還有兩個以上的情形，所以我測試的時候總是會有幾個元素消失

:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
> 當 mergeSort 函式內迴圈結束時，代表著 left 或 right 其中一個已為空。所以增加一個判斷式看哪條串列為空，沒空的串列接在合併的串列後面。藉由此判斷式，可以涵蓋演算法最差狀況。

> through 不該寫作「通過」，否則你如何區分 pass 的翻譯？
> 回去看 qtest 目前的隨機資料輸入，如何產生合併排序演算法會遇到的最差狀況的測試資料？ :notes: jserv
:::
:::info
我跑去看了 qtest 的隨機資料輸入，使用這一段生成

static void fill_rand_string(char *buf, size_t buf_size)
{
    size_t len = 0;
    while (len < MIN_RANDSTR_LEN)
        len = rand() % buf_size;

    randombytes((uint8_t *) buf, len);
    for (size_t n = 0; n < len; n++)
        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
    buf[len] = '\0';
}

參考 [stackoverflow](https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur) 這篇文章，合併排序演算法會遇到的最差狀況是 "需要進行最多比較的時候" ，也就是每對集合中都參與比較。
所以如果要產生最差狀況的測試資料，可以使用 q_sort 生成降序的字串。
:::

`q_sort` :把環狀結構斷開，以及最後將整個串列的環狀結構接回來

:::warning
函式 `q_sort` 不完整，請整合 `q_sort` 與 `mergesort`

:notes: marvin0102
:::

### q_ascend
> [commit 01bfcbf](https://github.com/LULser0204/lab0-c/commit/01bfcbf4afe166d1a597d061b15709f56ec35b2c)

參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)，在佇列中該「位置」的右邊不能有大於他的數字存在

:::danger
正確使用標點符號。
:::

我的想法是先用 `q_reverse` 翻轉整個佇列，接著從左往右走訪每個節點。假設一個變數 `max` 初始值為該佇列的第一個值，往右走訪的路上會有兩個情形:

1.如果碰到該節點的值比 `max` 還要小，則移去掉它
2.如果碰到該節點的值比 `max` 還要大，則更新 `max` 的值為該節點的值繼續走訪直到最後一個節點

最後，再將整個佇列翻轉回來並用 `q_size` 傳回佇列的長度

:::warning
如果調整刪去的條件，是否可以省略 `q_reverse` 的呼叫?

> ~~可以，除了調整刪去的條件以外，也能從右往左(因為是環狀且雙向)
[commit 5c4cfdb](https://github.com/LULser0204/lab0-c/commit/5c4cfdbd7bf0a8e94b2662792eb1062abac5ab90)~~

> 謝謝哥，我懂你的意思了
[commit fc05e7a](https://github.com/LULser0204/lab0-c/commit/fc05e7a633a92a10f2e89895a3a05793293b5289)

:notes: marvin010
:::

### q_descend
> [commit 7d3a25e](https://github.com/LULser0204/lab0-c/commit/7d3a25e2abd6ff79386cb803d8cc1a5d3cef13cb)

參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)，在佇列中該 "位置" 的右邊不能有小於他的數字存在

其作法和 `ascend` 概念相同，只是從找是否有"更大"的值變成找"更小"的值。

:::warning
既然 `q_decend`、`q_ascend` 概念相同，能否將兩函式整合，使程式更簡潔?

> 可以，如果 ascend 可以多帶進去一個參數( bool ascend )，判斷遞增還是遞減的排序，這樣就只需要在刪去條件那調整即可。

> 或者是用 q_reverse 翻轉串列，呼叫 q_ascend 然後再用 q_reverse 翻轉回來
[commit fc05e7a](https://github.com/LULser0204/lab0-c/commit/fc05e7a633a92a10f2e89895a3a05793293b5289)

:notes: marvin0102
:::

### q_merge
> [commit 15f08f4](https://github.com/LULser0204/lab0-c/commit/15f08f499ad0922d8f0ef6886e821b41a0d32cce)

合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/description/)

我一開始認為傳進來的會是多條佇列，所以我嘗試使用 `q_sort` 所使用到的 `mergesort` 函式，將其兩兩合併成一條，但失敗了。後來，參考 [ItisCaleb](https://hackmd.io/@ItisCaleb/linux2023-lab0#q_merge) 的作法，發現有 `queue_contex_t` 的存在，直接將 `queue_contex_t` google 搜尋會跳出 [SPFishcool](https://hackmd.io/@SPFishcool/r1r4u_26j) 所整理的架構圖!


:::danger
無效的超連結，檢查權限設定
> 改用 imgur 上傳，避免權限設定
:::

引用 [SPFishcool](https://hackmd.io/@SPFishcool/r1r4u_26j) 的內文。`queue_contex_t` 在紀錄每一條佇列的資訊，`*q `為 `pointer of queue head`，`size` 是佇列裡面 `element_t` 的數量，`chain` 為與其他 `queue_contex_t` 串連的 `list_head`，下面是其內容

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

> 在了解架構後，把每個 `list` 都接到第一個 `list` 後面，並且累加元素數量，然後再使用 `q_sort` 去排序

:::warning
為甚麼不直接將 `queue_contex_t` 中的陣列直接做 merge?
先將陣列連接起來再呼叫 `q_sort` ，在排序時又會經過拆分與合併，顯然有點多此一舉。

:notes: marvin0102
:::

### 實測結果:

+++ 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
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
---     trace-17-complexity     0/5
---	TOTAL		95/100

<s>測試結果不穩定</s> 。原因是 ascend 和 descend 有時候會誤刪節點，有時候則正常運作。
> 後來注意到是因為刪去條件原本是 `strcmp(max,tmp->value) > 0` ，但這樣會刪掉重複的節點&第一個節點，改成 >= 即可。

:::danger
查閱辭典，理解「穩定」的寓意，用字該精準 :notes: jserv
:::

~~很奇怪，我的 ascend 只有呼叫 descend 而已，結果功能是正常的???
我嘗試了很久，還是不知道為什麼這樣結果是對的。原本的想法是先把串列最後一個節點暫時移除，翻轉第 1~n-1 再接上移除的節點，之後呼叫 descend ，處理後的串列在重複前面的操作。~~

我搞錯了 ascend 的定義...以及輸入 [5,2,13,3,8] 之所以只輸出 [8]
是因為我前面都用 char ，所以 '13' 他比較的對象是字元 '1' 而不是數字 13

:::danger
linked list 為「鏈結串列」，可簡稱為 list (串列)，但不可稱「链表」，該資料結構不具備任何「表」的寓意，參見中華民國教育部重編國語辭典「[表](https://dict.revised.moe.edu.tw/dictView.jsp?ID=457)」，指「分格或分項以列記事物的文件」，而 linked list 作為資料結構，全然沒有「分格」和「分項」的意涵。

$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)

> 不小心把 ChatGPT 的文字寫上去= =
:::

從我的實作可以看到我的作法屬於是 `bad taste` 那種只考慮能不能動...，還需要磨練能力把學到的東西拿出來使用。
太過於依賴 Chatgpt 或是網路論壇上的解答

:::danger
你現在的問題不僅是 bad taste，亦有對細節的掌握不足。
:::

---

## 以 Valgrind 分析記憶體問題

## 整合 tiny-web-server

## 在 qtest 提供新的命令 shuffle

## 研讀 Linux 核心原始程式碼的 lib/list_sort.c

## 改進 dudect 實作