# 2025q1 Homework1 (lab0)
contributed by <`Louis-Wup`>

{%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:             11th Gen Intel(R) Core(TM) i7-11370H @ 3.30GHz
    CPU family:           6
    Model:                140
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             1
    CPU(s) scaling MHz:   20%
    CPU max MHz:          4800.0000
    CPU min MHz:          400.0000
    BogoMIPS:             6604.80
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    192 KiB (4 instances)
  L1i:                    128 KiB (4 instances)
  L2:                     5 MiB (4 instances)
  L3:                     12 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-7

## Git 使用方法
我找到一個適合初學者的 git 教學網站
網站：https://www.runoob.com/git/git-tutorial.html

## 針對佇列操作的程式碼實作

:::info
在以下內容中， list_head 型態的變數與 element_t 型態的變數，都將稱為「節點」而非「元素」，因此即使使用如 list_for_each_entry_safe 等函式也會稱為「遍歷節點」，而非「遍歷元素」，而其 element_t 的 value 則稱為「節點內元素」或是「元素」。此外，注意所有佇列的實作皆為「雙向環狀鏈結串列」，因此若看到「遍歷佇列」等語句，其所指就是「遍歷鍊結串列」。不過，上述兩點配合前後文應能輕易理解其含意。
:::

### 了解佇列連接方式
在實做前建議先了解該題目佇列的連接方式，否則 `q_merge()` 有可能會不知如何下手

第一張圖是分別的樣子，以及指標的指向

第二張圖是佇列，也就是 element_t 串接的樣子

第三張圖是 queue_contex_t 串接的樣子 *特別注意 size 部分*

第四章就是完整的樣子

### 自行添加用以輔助的函式
- q_new_element()
- q_delete_element()
- q_strncmp()
- q_swap_two_node()
- q_bubble_sort()
- q_merge_sort()
- q_merge_two_lists()

### q_new()
> commit: [aad1da5
](https://github.com/sysprog21/lab0-c/commit/aad1da5845d9473e09aa716767a2caa54a427087)
#### 目標：建立空佇列
#### 想法與簡易流程：
1. 使用 `malloc` 分配記憶體空間並檢查是否成功
2. 使用 "list.h" 中的 `INIT_LIST_HEAD` 使其指標指向自身後回傳

### q_free()
>初始版本 commit: [aad1da5
](https://github.com/sysprog21/lab0-c/commit/aad1da5845d9473e09aa716767a2caa54a427087)
>修正版 commit: [9b6dcbc
](https://github.com/sysprog21/lab0-c/commit/9b6dcbc0739a604c1470b33ccbba43ec310c52a4)
#### 目標：釋放所有被佇列所佔用的記憶體空間
#### 想法與簡易流程：
1. 檢查佇列是否存在，若不存在則結束
2. 遍歷佇列中的所有節點，將其從佇列中移除後，使指標指向自身，並釋放記憶體
3. 釋放佇列頭部所佔的記憶體空間
#### 紀錄：
使用 "list.h" 的 `list_for_each_entry_safe` 時，因未正確理解變數 `entry` 與 `safe` 的功能，導致誤修改了錯誤的節點。實際上， `entry` 雖作為遍歷時的變數，仍可被修改，這是因為 `safe` 在 `entry` 變更前，已先記錄下一個要走訪的節點。如此，即使 `entry` 被刪除或修改，遍歷仍能透過 `safe` 賦值給 `entry` ，確保正確性。

- element_t *entry = NULL, *tmp = NULL;
- list_for_each_entry_safe (entry, tmp, head, list) {
-     list_del_init(&tmp->list);
-     q_release_element(tmp);

+ element_t *entry = NULL, *safe = NULL;
+ list_for_each_entry_safe (entry, safe, head, list) {
+     list_del_init(&entry->list);
+     q_release_element(entry);

### q_new_element()
>初始版本 commit: [773ef55
](https://github.com/sysprog21/lab0-c/commit/773ef5555caf180e15eeaed64e2278cf4ac9e90c)
>修正版 commit: [f0241e6
](https://github.com/sysprog21/lab0-c/commit/f0241e6c591c9ac4cb831d8dd8944ee291bb97c6)
#### 目標：生成新的佇列節點
#### 想法與簡易流程：
1. 使用 `malloc` 分配節點的記憶體空間並檢查是否成功
2. 使用 `malloc` 分配字串的記憶體空間並檢查是否成功，若失敗則 **釋放步驟 1 分配的記憶體**
3. 使用 `strncpy` 複製字串
4. 回傳指向該節點的指標
#### 紀錄：
一開始實作時忘記處理若 `malloc` 申請字串失敗時要釋放步驟 1. 分配的記憶體，導致在執行 `make test` 時，終端機出現錯誤。

TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 3 blocks are still allocated

之後查看檔案 "trace-11-malloc.cmd"，發現當 `malloc` 失敗後嘗試清空佇列時，會出現仍有節點未釋放的訊息。使用 Valgrind 檢查後，也確認問題發生在 `q_new_element` 函式。最終找出原因是當字串記憶體請求失敗時，忘記釋放節點步驟 1. 所佔用的記憶體空間，導致了這個記憶體洩漏的問題。

Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
==11558== 42 bytes in 1 blocks are definitely lost in loss record 1 of 2
==11558==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==11558==    by 0x10F90B: alloc (harness.c:146)
==11558==    by 0x10FA5E: test_malloc (harness.c:176)
==11558==    by 0x10FE61: q_new_element (queue.c:44)
==11558==    by 0x10FEEE: q_insert_tail (queue.c:75)
==11558==    by 0x10CF78: queue_insert (qtest.c:233)
==11558==    by 0x10D090: do_it (qtest.c:288)
==11558==    by 0x10E74D: interpret_cmda (console.c:181)
==11558==    by 0x10ED12: interpret_cmd (console.c:201)
==11558==    by 0x10F7FC: run_console (console.c:659)
==11558==    by 0x10DB3C: main (qtest.c:1444)
==11558== 
==11558== 64 bytes in 1 blocks are still reachable in loss record 2 of 2
==11558==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==11558==    by 0x10F90B: alloc (harness.c:146)
==11558==    by 0x10FA5E: test_malloc (harness.c:176)
==11558==    by 0x10FE48: q_new_element (queue.c:40)
==11558==    by 0x10FEEE: q_insert_tail (queue.c:75)
==11558==    by 0x10CF78: queue_insert (qtest.c:233)
==11558==    by 0x10D090: do_it (qtest.c:288)
==11558==    by 0x10E74D: interpret_cmda (console.c:181)
==11558==    by 0x10ED12: interpret_cmd (console.c:201)
==11558==    by 0x10F7FC: run_console (console.c:659)
==11558==    by 0x10DB3C: main (qtest.c:1444)
==11558== 

  new_node->value = (char *) malloc(strlen(str) + 1);
- if (!new_node->value)
+ if (!new_node->value) {
+     free(new_node);
      return NULL;
+ }

### q_insert_head() & q_insert_tail()
> commit: [067d4f6
](https://github.com/sysprog21/lab0-c/commit/067d4f6a9c626898e19d09473482386c7e549d98)
#### 目標：建立節點並插入佇列開頭 / 結尾
#### 想法與簡易流程：
1. 確認佇列是否存在
2. 使用 `q_new_element` 建立新節點並檢查是否成功
3. 使用 `list_add` / `list_add_tail` 將節點插入佇列頭部 / 尾部

### q_remove_head() & q_remove_tail()
> commit: [1774c2c
](https://github.com/sysprog21/lab0-c/commit/1774c2c6f5009143e164004cdce37df64cc1b2ab)
#### 目標：移除佇列開頭 / 結尾節點，並將內容複製到指定變數
#### 想法與簡易流程：
1. 確認佇列是否存在或為空
2. 使用 `list_first_entry` / `list_last_entry` 取得指向佇列中的第一個 / 最後一個節點的指標
3. 將該節點從佇列中移除，並讓其指標指向自身
4. 若該節點內元素非 `NULL` ，則使用 `strncpy` 將其複製到指定變數 `sp` 後回傳

### q_delete_element()
> commit: [b3a4024
](https://github.com/sysprog21/lab0-c/commit/b3a4024ac47bf3723817f38b6294f9d881898f61)
#### 目標：刪除特定節點
#### 想法與簡易流程：
1. 使用 `list_del_init` 將節點從佇列中移除，並讓其指標指向自身
2. 呼叫 `q_release_element` 釋放該節點佔用的記憶體空間

### q_delete_mid()
> commit: [aefa58c
](https://github.com/sysprog21/lab0-c/commit/aefa58c266d26150e668cea66bd4ad3b903f841b)
#### 目標：刪除佇列中央的節點
#### 想法與簡易流程：
1. 檢查佇列是否存在或為空，若是則回傳 `false`
2. 透過快慢指標的技巧，取得指向中央節點的指標
3. 透過 `q_delete_element` 刪除該節點
#### 紀錄：
一開始沒通過靜態程式分析

Running static analysis...
queue.c:146:28: style: Variable 'fast' can be declared as pointer to const [constVariablePointer]
    for (struct list_head *fast = head->next;

之後將 `const` 補上去以增加安全行後通過了。

  struct list_head *slow_mid = head->next;
- for (struct list_head *fast = head->next;
+ for (const struct list_head *fast = head->next;
       fast != head && fast->next != head; fast = fast->next->next) {
      slow_mid = slow_mid->next;
  }

### q_strncmp()
> commit: [7991e1e
](https://github.com/sysprog21/lab0-c/commit/7991e1eee77bf099f7722499bd19d5216e27c5c9)
#### 目標：比較節點內元素的大小
#### 想法與簡易流程：
1. 使用 `strlen` 取得兩個比較對象的字串長度
2. 將較長字串的長度作為參數傳遞給 `strncmp` 使用並回傳結果
#### 紀錄：
這個函式主要是為了提高程式的可讀性，降低自身出錯的機率，因為原本的 `q_delete_dup` 就因為可讀性實在太差，導致我疏忽，未更新 `strncmp` 中使用的字串長度限制，這種錯誤可能會有潛在的安全問題，且在特定類型的輸入下會直接導致結果出錯（詳細於q_delete_dup說明），因此我決定做出該函式。

此外，當我將程式上傳時，未通過靜態程式碼檢查，需要補上 const 來提升安全性。

  int q_strncmp(const struct list_head *a, const struct list_head *b)
  {
-     element_t *e_a = list_entry(a, element_t, list);
-     element_t *e_b = list_entry(b, element_t, list);
+     const element_t *e_a = list_entry(a, element_t, list);
+     const element_t *e_b = list_entry(b, element_t, list);
      ...
      return strncmp(e_a->value, e_b->value, n);
  }

### q_delete_dup()
> 初始版本 commit: [367ba63
](https://github.com/sysprog21/lab0-c/commit/367ba635050b17e42da72216ac167b4dca0af4a3)
> 修正版 commit: [04e95f0
](https://github.com/sysprog21/lab0-c/commit/04e95f04767a0d0b23bdf04b2de769fd550c8d4c)
#### 目標：若佇列內存在內容重複的節點，則將含有重複內容之節點全部刪除
#### 想法與簡易流程：
1. 檢查佇列是否存在或為空，或是只有一個節點
2. 使用兩個指標 `from` 和 `to` ，分別標記內容重複的起始與結束節點。遍歷佇列時，若遇到內容重複的節點，則將變數 `delete` 設為 `true` ，並繼續遍歷，直到找到內容不同的節點或佇列結束
3. 若 `delete` 為 `true` ，則將其重設為 `false` ，並刪除 `from` 到 `to` （含）的所有節點
4. 若遍歷結束則完成，否則回到步驟 2
#### 紀錄：
一開始我想使用 "list.h" 的 `list_for_each_entry_safe` 來遍歷佇列，不過這樣寫需要在遍歷的開頭檢查比較字串是否為空，因為一開始並沒有比較對象，像是

list_for_each_entry_safe(entry, safe, head) {
    if (!from)
        from = entry;
    else if(q_strncmp(from, entry))
        ...
}

而用 macro 又不能使第一個取得的節點變成 `head->next->next` 。因此，若每次迴圈開頭都必須執行一個除了第一次一定為 `false` 的 `if` 判斷，會對不具備分支預測，或者僅具備靜態分支預測（`if` 總是預測不會跳轉）的電腦造成大量時間浪費。於是我決定改為手動寫 `while` 迴圈來遍歷。

之後在上傳時沒通過靜態檢測，有兩部份要改，首先是要補上 `const` 增加安全性

queue.c:173:16: style: Variable 'e_from' can be declared as pointer to const [constVariablePointer]
    element_t *e_from = NULL, *e_to = NULL;
               ^
queue.c:173:32: style: Variable 'e_to' can be declared as pointer to const [constVariablePointer]
    element_t *e_from = NULL, *e_to = NULL;

- element_t *e_from = NULL, *e_to = NULL;
+ element_t const *e_from = NULL, *e_to = NULL;

接著是另一個問題，要將變數 `n` 放進迴圈內宣告

queue.c:174:9: style: The scope of the variable 'n' can be reduced. [variableScope]
    int n = 0;
queue.c:174:11: style: Variable 'n' is assigned a value that is never used. [unreadVariable]
    int n = 0;

- int n = 0;
  while (from != head && to != head) {
      e_from = list_entry(from, element_t, list);
      e_to = list_entry(to, element_t, list);
-     n = strlen(e_from->value) > strlen(e_to->value)
+     int n = strlen(e_from->value) > strlen(e_to->value)
                     ? strlen(e_from->value) + 1
                     : strlen(e_to->value) + 1;

這部分我有些疑慮，我是故意將變數 `n` 放在迴圈外宣告，這樣可以避免變數 `n` 一直被重複宣告，避免不必要的開銷，我認為這樣做可能會對效能有所幫助。因此，接下來我打算查找相關資料或進行實驗，來驗證這樣的處理是否真的會對效能產生影響。
`TODO` : 變數於迴圈內重複宣告是否有效能影響

後來我自己測試時發現原始版本還存在一個問題是在移動 `to` 指標時，未更新傳遞給 `strncmp` 的字串長度限制。雖然測試資料沒有出現問題，但存在著潛在的安全風險，以及可能導致錯誤的結果。因此，我決定一方面修掉該問題，一方面提高程式碼可讀性，將 `list_entry` 以及大量使用 `strlen` 的部分移到另一個函式 `q_strncmp` 中，這樣程式碼相比原本變得更加簡潔。

  while (from != head && to != head) {
-     e_from = list_entry(from, element_t, list);
-     e_to = list_entry(to, element_t, list);
-     int n = strlen(e_from->value) > strlen(e_to->value)
-                 ? strlen(e_from->value) + 1
-                 : strlen(e_to->value) + 1;
-     while (to != head && !strncmp(e_from->value, e_to->value, n)) {
+     while (to != head && !q_strncmp(from, to)) {
          delete = true;
          to = to->next;
-         e_to = list_entry(to, element_t, list);
      }

### q_swap_two_node()
> 原始版本 commit: [b4f7c6c
](https://github.com/sysprog21/lab0-c/commit/b4f7c6cf697523285d5072f74982929db3fe1626)
#### 目標：將傳入的兩節點互換位置
#### 想法與簡易流程：
1. 判斷是否為相鄰節點，若是則步驟 2 後結束，否則步驟 3 後結束
2. 先宣告變數紀錄 `left->prev` 和 `right->next` 後，處理 `left` 和 `right` 的指標，再處理 `left->prev` 和 `right->next`
3. 先宣告變數紀錄 `left->prev`, `left->next`, `right->prev` 以及 `right->next` 後，處理 `left` 和 `right` 的指標，再處理 `left->prev`, `left->next`, `right->prev` 以及 `right->next`
#### 紀錄：
該方法需要判斷傳入的兩節點是否相鄰，因此需要一個 `if-else` 的判斷式，但修改內容又有大部分雷同，因此嘗試使用教授上課教的間接指標把 `if-else` 去掉，不過沒有成功，因此後來又上網查找是否有方法把 `if-else` 判斷移除後，成功找到了，該方法也確實是透過間接指標來處理特例，以下是討論串連結。

Reference（最後一個回答） ： https://stackoverflow.com/questions/20095529/swapping-nodes-in-double-linked-list

### q_reverse()
> 原始版本 commit: [b82a4f3
](https://github.com/sysprog21/lab0-c/commit/b82a4f3a247321d930ab3e425a7b409f6803ffd8)
> 修正版 commit: [e89369e
](https://github.com/sysprog21/lab0-c/commit/e89369e11d3be873bd91555c3f9a989806274279)
#### 目標：將佇列反轉
#### 想法與簡易流程：
1. 檢查佇列是否存在、為空或僅有一個節點
2. 使用 `list_for_each_safe` 遍歷佇列，將每個節點的 `next` 指向原本的 `prev` ，並將 `prev` 指向原本的 `next`
3. 最後，同樣調整 `head` 的 `next` 和 `prev` ，完成整個佇列的反轉
#### 紀錄：
我的初始實作方法是透過兩個指標，一個正向、一個反向逐一走訪，並在每一步使用 `q_swap_two_node` 交換節點。為了確保正確性，我額外使用了兩個指標來記錄下一步要訪問的節點。然而，這種方法雖然直觀，但包含過多的 `if-else` 判斷與額外的指標變更，影響效率。

後來，我在網路上找到了一種更好的方式，不僅消除了 `if-else` 判斷與不必要的指標變動，還省去了 `q_swap_two_node` 的使用，更重要的是，這個方法同樣適用於單向鏈結串列的反轉。

以下是簡化的程式碼比對，詳細內容請參閱 [commit 9664572](<https://github.com/sysprog21/lab0-c/commit/96645725e821b91b3416402ad8c7227754276f09>)。

演算法 Reference: https://takeuforward.org/data-structure/reverse-a-doubly-linked-list/

github 內程式碼中並未移除 q_swap_two_node
此處的「移除」只是表示新的實作方法已經不再依賴該函式

- q_swap_two_node()
- {
-     if (l->next == r) {
-         ...
-     } else {
-         ...
-     }
- }

  q_reverse()
  {
-     while (l != r) {
-         ...
-         q_swap_two_node(l, r);
-         if (l->prev == r)
-             break;
-         ...
-     }
+     list_for_each_safe (entry, safe, head) {
+         entry->next = entry->prev;
+         entry->prev = safe;
+     }
+     ...
  }

### q_reverseK()
> commit: [fb0a58e
](https://github.com/sysprog21/lab0-c/commit/fb0a58eedfd3957c867817669d93ea9e8be91b33)
#### 目標：以 k 個節點為一組反轉
#### 想法與簡易流程：
這個函式的主要實做想法是一次將佇列前 k 個節點取出並反轉後，放入其他佇列尾部，不斷重複到整個佇列都完成反轉
1. 檢查佇列是否存在、為空、僅有一個節點或 k = 1
2. 建立兩個雙向環狀鍊結串列 `tmp_list` 和 `reverse_list` ，前者用於暫存從 `head` 移走的 k 個節點以便後續反轉，後者用於存放所有反轉後的節點
3. 遍歷佇列，每當走訪第 k 個節點時，使用 `list_cut_position` 將其移動至 `tmp_list` ，再使用 `q_reverse` 反轉，最後透過 `list_splice_tail_init` 將排序好的節點加入 `reverse_list`
4. 最後，使用 `list_splice` 將 `reverse_list` 併回 `head` ，完成以每 k 個節點為一組的整個佇列的反轉
#### 紀錄：
當時最一開始我的想法其實是使用 `list_cut_position` 以每 k 個節點為單位儲存到一個新型態的鍊結串列，這個鍊結串列每個節點都為一個雙向環狀鍊結串列與 `next` 指標，之後只要透過 `list_cut_position` 以每 k 個節點為一組組成鏈接串列後，每組反轉在串接即可，但準備實作後發現兩個問題，第一個是若 k 很小，則需要大量的而外空間，最差要 O(n) 的額外空間，第二個是該函式沒有回傳值，換言之該函式不能有失敗的風險，否則若失敗了自己也不會知道，因此不能使用含有 `malloc` 這類有可能失敗的函式。

### q_swap()
> commit: [fb0a58e
](https://github.com/sysprog21/lab0-c/commit/fb0a58eedfd3957c867817669d93ea9e8be91b33)
#### 目標：節點兩兩一組反轉
#### 簡易流程：
1. 將 k = 2 作為參數傳遞給 `q_reverseK`

### q_ascend() / q_descend()
> 原始版本 commit: [0941ff7
](https://github.com/sysprog21/lab0-c/commit/0941ff7e20d405f4bc656b5d9e469ca210bef21f)
> 修正版 commit: [a2de161
](https://github.com/sysprog21/lab0-c/commit/a2de161179698faec8573251aa2e864d8543a886)
#### 目標：將佇列從小到大 / 從大到小排列，若遇到順序錯誤的節點直接刪除
#### 想法與簡易流程：
1. 檢查佇列是否存在或為空，或僅有一個節點
2.
- q_ascend(): 使用兩個指標 `small` 和 `big` ，並分別初始化為 `head->next` 以及 `head->next-next` 後，一起從佇列**頭部向尾部**遍歷，途中若遇到順序錯誤的節點直接**刪除**，順序正確則計數器值加一
- q_descend(): 使用兩個指標 `big` 和 `small` ，並分別初始化為 `head->prev->prev` 以及 `head->prev` 後，一起從佇列**尾部向頭部**遍歷，途中若遇到順序錯誤的節點直接*刪除*，順序正確則計數器值加一
3. 回傳計數計值
#### 紀錄：
一開始我計算回傳值時犯了錯，原以為 `small` 和 `big` 指標都有指向節點，所以初始值應該為 2，但其實應該是 0，因為 while loop 還會比較一次。結果執行時出現了 `Segmentation fault` ，於是我使用 Valgrind 檢測程式後，得到了以下錯誤訊息：

==18817== Invalid read of size 1
==18817==    at 0x4850367: strcmp (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==18817==    by 0x10BD5F: do_ascend (qtest.c:755)
==18817==    by 0x10E74D: interpret_cmda (console.c:181)
==18817==    by 0x10ED12: interpret_cmd (console.c:201)
==18817==    by 0x10F7FC: run_console (console.c:659)
==18817==    by 0x10DB3C: main (qtest.c:1444)
==18817==  Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==18817== 
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer==18817=

發現是 `qtest` 裡面 `strcmp` 出問題，因此立刻想到是比較到不應該比較的部份，並發現是回傳大小出錯導致 `qtest` 裡面迴圈跑過頭。修正後，錯誤訊息轉變為有些節點未釋放，但 "queue.c" 以及 "queue.h" 該函式上方英文說明都為 remove ，因此我去仔細查看 "queue.h" 該函式的詳細說明後，發現其中有一行指出

 // Memory allocated to removed nodes must be freed.

因此，我將節點的移除操作改為刪除，變得可以成功執行了。最後，我還發現原本 lab0-c 的 repository 中已經有人提交了相關的 pull request ，只是尚未通過。

此外在實作 `q_descend` 函式時突然想到， LeetCode 中的題目是單向鍊結串列，所以無法直接反向搜尋，而一時之間又想不出好解法，我就去 LeetCode 找解法，找到一個跟上述 ascend 類似的作法（Reference裡面的第三種解法），它的時間複雜度是 O(n)，空間複雜度是 O(1)，不過最重要的是這個作者對他的解法提供了圖解，使人能夠輕鬆理解其邏輯。
Reference : https://leetcode.com/problems/remove-nodes-from-linked-list/solutions/5073124/remove-nodes-from-linked-list/

### q_bubble_sort()
> 原始版本 commit: [344417a
](https://github.com/sysprog21/lab0-c/commit/344417a20e957f415d1fabb238f98f0ec7dda92e)
> 修正版 commit: [a883983
](https://github.com/sysprog21/lab0-c/commit/a883983ada37253b591bd0fac264e1fc7689a38b)
#### 目標：將佇列從大到小 / 從小到大排序
#### 想法與簡易流程：
1. 宣告一個指標 `ptr_end` ，並將其設為 `head`
2. 透過指標 `ptr_a` 和 `ptr_b` 從佇列頭部開始，逐一向 `ptr_end` 走訪，直到遇到 `ptr_end` 。在這個過程中，若發現需要調整順序的節點，則使用 `q_swap_two_node` 函式進行交換
3. 在每一輪遍歷後，更新 `ptr_end` 為 `ptr_end->prev` ，並重複步驟 2 ，直到 `ptr_end` 指向 `head->next` 為止
#### 紀錄：
該函式一開始是實做在 `q_sort` ，想說只是 Bubble Sort 且之前已經實作過 `q_swap_two_node` ，所以可以簡單快速地實現這個排序。然而，結果還是出現了錯誤。第一個錯誤是在交換節點後，指標順序會對調，我忘記將指標復原成原來的順序。第二個錯誤是在 Bubble Sort 的內層迴圈中，我用來作為終止條件的指標指向的節點是可以交換的，因此當該節點被交換時，會導致終止條件出現錯誤。後來成功修復後因為效能考量（測試資料效能測試沒過），就將該函式移出 `q_sort` 獨自存在，並改用 Merge Sort 來實做 `q_sort` 。

後來測試時發現，我的作法雖然從小到大是穩定排序，但從大到小不是，因為我的作法是單純使用 `xor` 運算，等號的有無會造成其中一個方向的排序變成不穩定，還需要想有沒有除了 `if-else` 以外的解決方法。

  // 下方是 Bubble sort 使否交換的判斷
  if ((q_strncmp(ptr_a, ptr_b) > 0) ^ descend) {
      q_swap_two_node(ptr_a, ptr_b);
      ...
  }

`TODO:` 解決從大到小的不穩定排序。

### q_merge_sort()
> commit: [487a0c5
](https://github.com/sysprog21/lab0-c/commit/487a0c58de54d7cd06531f4aa30d6403f1aa1059)
#### 目標：將佇列從大到小 / 從小到大排序
#### 想法與簡易流程：
1. 檢查佇列是否為空或只有一個節點，若是，則直接回傳該佇列。
2. 使用快慢指標方法，找到 Merge Sort 的中間斷開點。
3. 宣告並建立新的佇列（注意，這裡我沒有使用 `malloc` ，而是直接宣告）。
4. 使用 `list_cut_position` 來將佇列一分為二。
5. 分別對這兩個子佇列遞迴呼叫 `q_merge_sort`。
6. 合併兩個已排序的佇列後回傳合併結果。
#### 紀錄：
這個函式不實作在 `q_sort` 內的原因是，原本使用 Bubble Sort 實作 `q_sort` ，但由於效率問題，測試資料無法通過，因此我改為使用 Merge Sort 實作。然而，我希望保留 Bubble Sort 的實作，因為未來可能還有使用的機會，所以我將 Bubble Sort 以及 Merge Sort 獨立出來，並讓 `q_sort` 決定應該呼叫哪個函式。至於步驟 3，我故意不使用 `malloc` 來產生新佇列，因為 `q_sort` 函式沒有回傳值，應盡量避免失敗的可能性，所以不使用可能會失敗的 `malloc` ，且這樣的宣告方式可以在函式結束時自動釋放記憶體空間，無需手動 `free` ，如此還避開了大量的 `malloc` 及 `free` 的使用。另外，雖然回傳值其實是可以省略的，我也注意過並測試過了，但不回傳似乎有些不太對勁，因此我還是保留了讓函式有回傳值。

### q_sort()
> 相關 commit 請移步到 q_bubble_sort() 以及 q_merge_sort()
#### 目標：將佇列從大到小 / 從小到大排序
#### 想法與簡易流程：
1. 呼叫 `q_merge_sort`

### q_merge_two_lists()
> 初始版本 commit: [58c552e
](https://github.com/sysprog21/lab0-c/commit/58c552e75a186fc38b8972e9e188468d1debdc03)
> 修正版 commit: [8f8acdd
](https://github.com/sysprog21/lab0-c/commit/8f8acdde5a8a8f4faf43dea2868af4ea4b59e965)
> 再修正版 commit: [05da83b
](https://github.com/sysprog21/lab0-c/commit/05da83bbce0a7f86222afc221eca9012ddf50bea)
#### 目標：將兩個排序過得佇列合併，並依然保持由大到小 / 由小到大排列
#### 想法與簡易流程：
實作方式是以 `head_a` 為開頭，依序串接節點，當其中一個佇列串接完畢後，直接將剩餘佇列銜接至尾部並回傳。
1. 宣告 `ptr` 指向 `head_a` ，用來指向需更新的位置
2. 宣告 `a` 和 `b` 分別指向 `head_a->next` 和 `head_b->next`
3. 使用 `a` 和 `b` 逐一走訪各自的佇列，並透過 `q_strncmp` 取得下一個應該加入的節點的指標給 `node` （指向 指向目標節點的指標）後更新指標，直到其中一個佇列遍歷完畢
4. 將剩餘的佇列直接串接到 `head_a` 的尾部，最後回傳 `head_a`
#### 紀錄：
一開始我的想法是額外宣告一個佇列，然後將要合併的佇列逐一加入該佇列裡，當有一個完成時，另一個直接串起來，最後在將整條合併後的佇列指派給 `head_a` 後回傳。不過後來發覺裡面有沒必要的操作，像是額外開一個佇列，以及把佇列還回去，我明明可以直接用 `head_a` 當開頭來串接其他節點，還有我想到在上課的 [linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list) 中有使用間接指標去減少 `if-else statement` 大括號裡面的程式碼的技巧，雖然我還需要查資料或做實驗了解為什麼要這麼做，明明一樣都是一個 `if-else` 的判斷加特定行數須執行，這些程式在 `if-else` 的大括號裡面跟外面執行究竟有沒有效能上的差異，還是只是因為這樣程式碼比較"乾淨"。
`TODO:` 實驗程式碼在 `if-else` 大括號裡面和外面對效能有無影響。

下方為部份差異，可以看到透過間接指標，將 `if-else` 大括號裡的程式碼提出來，使程式碼變比較乾淨，至於詳細改動請看 修正版 commit: [8f8acdd
](https://github.com/sysprog21/lab0-c/commit/8f8acdde5a8a8f4faf43dea2868af4ea4b59e965)

- INIT_LIST_HEAD(ptr);
- while (a != head_a && b != head_b) {
-     if ((q_strncmp(a, b) ^ descend) < 0) {
-         ptr->next = a;
-         a->prev = ptr;
-         a = a->next;
-     } else {
-         ptr->next = b;
-         b->prev = ptr;
-         b = b->next;
-     }
-     ptr = ptr->next;
- }
 
+ for (struct list_head **node = NULL; a != head_a && b != head_b;
+     *node = (*node)->next) {
+     node = (q_strncmp(a, b) ^ descend) < 0 ? &a : &b;
+     ptr->next = *node;
+     (*node)->prev = ptr;
+     ptr = (*node);
+ }

後來測試又發現上述程式碼有兩個問題，第一個是把運算順序打反了

- node = (q_strncmp(a, b) ^ descend) < 0 ? &a : &b;
+ node = ((q_strncmp(a, b) < 0) ^ descend) ? &a : &b;

按照之前的版本，這個 `descend` 根本無法對 `q_strncmp` 的結果造成什麼影響，除了 LSB 可能會差個一；改正後是再比較大小後，根據 `descend` 判斷是否選擇另一個節點。而另外一個問題則是跟 `q_bubble_sort` 一樣，因為對同大小處理的不同，在從大到小排序時會是不穩定排序，而有沒有除了 `if-else` 以外的解決方法目前仍在尋找中。
`TODO:` 解決從大到小的不穩定排序。

### q_merge()
> commit: [58c552e
](https://github.com/sysprog21/lab0-c/commit/58c552e75a186fc38b8972e9e188468d1debdc03)
#### 目標：將多個排序過得佇列合併，並依然保持由大到小 / 由小到大排列
#### 想法與簡易流程：
直接透過 `q_merge_two_list` 不斷頭尾合併，直到最後剩一個佇列即可
1. 取得一共有多少佇列，並判斷是否須往下執行
2. 使用雙層迴圈，外層負責判斷還須多少輪內層迴圈，內層迴圈負責頭尾佇列的合併。
3. 回傳 `q_size` 的結果
#### 紀錄：
一開始對於 `queue_contex_t` 的結構不是很了解，花了一堆時間使用 `printf` 來推測具體結構，終於推測出來，結果放在該區塊最一開始了，不過了解區塊架構後，剩下就簡單了，基本沒碰到什麼問題，就是對問題敘述有一個疑惑
`However, q_merge() is responsible for making the queues to be NULL-queue, except the first one.`
那到底要不要將 `q` 指向 `NULL` 呢，因為沒有那就不符合題目敘述，將 queues 變成 NULL-queue, 而是 Empty-queue, 但如果指向 `NULL` ，那那些 queue 的 head 不就沒有 `free` ，變成 memory-leak 嘛？目前（沒有 sync）我測試是有沒有指向 `NULL` 都會過就是了。

---

## 在 qtest 提供新的命令 shuffle
### 實做 q_shuffle()
> 原始版本 commit: [1702b1e
](https://github.com/sysprog21/lab0-c/commit/1702b1ec0a562c6ad605f017f3cc6c9f15b13bb8)
> 修正版 commit: [5980d4c
](https://github.com/sysprog21/lab0-c/commit/5980d4c4eb5b4348aad7a093b9f1ccf87659e454)

依照 [Fisher–Yates shuffle](https://ithelp.ithome.com.tw/articles/10337601) 演算法實做 `q_shuffle()` 很簡單，比較需要額外注意的是我們正常隨機取 0 ~ n-1 的整數時會直接對 `rand()` 後的結果模 n ，當佇列很小時，每個元素被選擇的機率基本還是維持均勻分佈，但當佇列大到一定程度時，分佈就不均勻了，每次被選擇的基本都將是 0 ~ `RAND_MAX` 的節點，因此我將取得變數的部份改成如下：

- struct list_head *ptr = head;
- for (int r = rand() % turn + 1; r; r -= 1) {
+ struct list_head *ptr = head->next;
+ int r = rand();
+ for (r = (int) ((float) r / ((unsigned) RAND_MAX + 1) * turn); r;
+      r -= 1) {
      ptr = ptr->next;
  }

不過即使是目前這種方法，當佇列遠遠大於 `RAND_MAX` 時，節點被選擇的機率仍舊不會是均勻分佈，每次選擇時都會有幾個節點是無法被選到的，這是因為我們的亂數相較於佇列長度有限，這裡舉個例子：
- 假設佇列長度為 100000 ， 而 `RAND_MAX` 為 32767 (C99 Standard 只保證 `RAND_MAX` 大於等於 32767)，則透過上面方法隨機出 r 為 32766 和 32767 時，對佇列的選擇會是節點 99993 和 99996 ，因為 $$ \lfloor 32766 / 32768 * 100000 \rfloor = 99993 $$ $$ \lfloor 32767 / 32768 * 100000 \rfloor = 99996 $$

可以發現不但跳過了 99994 和 99995 ，且 99997 ~ 99999 的節點根本不能被選到（假定32767已經是最大亂數），這是因為亂數小於佇列長度必然的限制，就像我們不能用 1 bit 表達 0, 1, 2 一樣，我們沒有足夠大的亂數可以去表達所有我們希望出現的數字，若非要表達只能產生第二個亂數。因此我們可以發現當佇列長度遠大於 `RAND_MAX` 時仍舊不會是均勻分佈（這裡注意隨著每次進行，乘上的數字會越來越小，所以真正從頭到尾無法被選到的數字只有最後幾個節點，至於其他節點則是輪流無法被選擇），但至少可以取得後面的節點，相較於直接取模仍舊好多了。

### 新增命令到 qtest
> commit: [1702b1e
](https://github.com/sysprog21/lab0-c/commit/1702b1ec0a562c6ad605f017f3cc6c9f15b13bb8)

基本上，參考其他命令（如 descend）就可以輕鬆加入 shuffle 命令。只需要宣告 `do_shuffle()` ，然後在 `console_init()` 中使用 `ADD_COMMAND()` 加入命令它即可。比較麻煩的是，因為作業規定不能修改 "queue.h" ，所以 `q_shuffle()` 直接放在 "queue.c" 裡時， "qtest.c" 會無法使用它。這是因為 "qtest.c" 只有 include "queue.h" ，而 "queue.h" 又沒有宣告 `q_shuffle()` 。

如果讓 "qtest.c" 直接 include "queue.c" 也是不應該的。最後，我找到了一個解決方案，使用 `extern` ，只需要在 `do_shuffle()` 上方加上：

extern void q_shuffle(struct list_head *head);

這樣 "qtest.c" 就能正確調用 "queue.c" 中的 `q_shuffle()` 了。

### 檢驗 q_shuffle() 的亂度品質