# 2025q1 Homework1 (lab0)
contributed by < [HeLunWu0317 ](https://github.com/HeLunWu0317)>

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

 $ uname -a
Linux lun-ThinkBook-14-G7-IML 6.11.0-19-generic #19~24.04.1-Ubuntu SMP PREEMPT_DYNAMIC Mon Feb 17 11:51:52 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

$ 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.

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   18
  On-line CPU(s) list:    0-17
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) Ultra 5 125H
    CPU family:           6
    Model:                170
    Thread(s) per core:   2
    Core(s) per socket:   14
    Socket(s):            1
    Stepping:             4
    CPU(s) scaling MHz:   36%
    CPU max MHz:          4500.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5990.40

## 針對佇列操作的程式碼實作
在開始實作前,應該先了解程式相關 header ,首先是與 `queue.c` 相關的 header `queue.h` 詳細了解每一題的程式的需求以及限制,而不是馬上埋頭苦幹,接下來是 linked list 相關之header `list.h` ,詳細了解每一個程式碼的意義及使用方法,才可在正式寫`queue.c` 時,少走彎路。
### q_new
在 `q_new` 的實作中，我們需要建立一個代表 queue 的 `head` 節點，並使用 `malloc` 分配記憶體來存放這個 `head`：

`struct list_head *head = malloc(sizeof(struct list_head));`
接著，使用 list.h 中的` INIT_LIST_HEAD()` 來初始化 head，確保它作為雙向鏈結串列（doubly linked list）的起始節點：
`INIT_LIST_HEAD(head);`
在確認 head 建立成功後，我們需要完成 head 在雙向鏈結串列中的初始化，主要包括：
* 將 head->next 指向自身
* 將 head->prev 指向自身

這樣可以確保 queue 初始時是一個空的環狀鏈結串列，準備好進行後續的插入和刪除操作。
### q_free
在 `q_free` 的實作中，首先確認 queue 的 `head` 是否存在，避免對 `NULL` 指標進行操作：
` if (!head)`
接著，使用 list.h 中的 list_for_each_safe 來尋訪 queue，確保在刪除節點時不影響尋訪過程。這個函式的特點是使用兩個指標，其中一個 (next) 會提前儲存下一個節點的位置，確保當前節點 (now) 被刪除後，尋訪仍能正常進行。

刪除過程中，必須先將節點從鏈結串列中移除 (list_del)，再釋放 element_t 本身的記憶體：

element_t *get = list_entry(now, element_t, list);
            if (get->value) {
                free(get->value);
            }
            list_del(now);
            free(get);

參考C99規格書中，關於`free()`函式:
> 7.20.3.2 The free function
> The free function causes the space pointed to by ptr to be deallocated, that is, made
available for further allocation. If ptr is a null pointer, no action occurs.

釋放後，該記憶體區域可能會被系統回收或重複使用，因此任何對它的存取行為都是未定義的，也就是先執行會導致後續list_del()存取已釋放的記憶體。

此說法也可在C99規格書中參考:
> C99 6.5.3.2 4. The unary * operator denotes indirection. If the operand points to a function, the result is
a function designator; if it points to an object, the result is an lvalue designating the
object. If the operand has type ‘‘pointer to type’’, the result has type ‘‘type’’. If an
invalid value has been assigned to the pointer, the behavior of the unary * operator is
undefined.
### q_insert_head
q_insert_head 用於在 queue 的`head`插入新的 node，並設置對應的字串資料。
透過 malloc 取得適當的記憶體空間，並建立 element_t 結構：
`element_t *new_data =
malloc(sizeof(element_t));`
確保 `new_data` 成功分配記憶體後，才能繼續進行資料填充:
1. 先前的做法是直接使用 strdup 複製字串：

    new_data->value = strdup(s); 

此舉造成 make test 中，時間複雜度非常數，查詢相關資料，在IEEE Std 1003.1-2017中，關於 string.h 部分:

    char *strdup(const char *s);
    char *strndup(const char *s, size_t size);

其描述:

> The strdup() function shall return a pointer to a new string, which is a duplicate of the string pointed to by s. The returned pointer can be passed to free(). A null pointer is returned if the new string cannot be created.

卻也沒有描述式如何實作字串計算以及內容複製，推測使用`strlen()` 計算字串長度，時間複雜度為 O(n) ，有了長度才使用`malloc()`做記憶體分配，最後做`strcpy()`複製字串內容，全部的時間複雜度至少 O(n) ，因此test無法通過。

目前改用以下方法

size_t length = strlen(s) + 1;
    new_data->value = (char *) malloc(length * sizeof(char));

手動設定好記憶體大小，雖然減少了可能的成本，但本質上仍與strdup()相同，因此仍有可能發生同樣情況，但是機率較低。
需找到更合適的方法。
### q_insert_tail
總體而言與 q_insert_head 相同，因此也有相同問題。

### q_remove_head
需要實作從 head 上 remove node，注意:
:::info
:information_source: &#34;delete&#34; 和 &#34;remove&#34; 看似都是「刪去某物」，在 Linux 核心的 [include/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中，這二個動作並存，但實際行為卻不同。[Difference between &#34;delete&#34; and &#34;remove&#34;](https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove) 其中的解釋可知：
* &#34;remove&#34; 這動作對於 linked list 來說，是斷開節點和節點的關聯，也就是說原本若是 A $\to$ B $\to$ C，在 `remove(B)` 操作完成後，就會變成 A $\to$ C 的節點關係。特別注意到 B 這個節點其實還存在於記憶體中，只是我們無法從節點間的關係看出來。於是 &#34;remove&#34; 可解讀為 &#34;take away&#34; (將某物帶走)
* &#34;delete&#34; 則有 &#34;erase&#34; 的涵義，若用於 linked list，則指某個節點將被「抹除」，對應的記憶體就會有變化
:::
在實作 `q_remove_head` 時，首先透過指標 `tmp` 指向 `head->next`，以獲取目標節點：

接著，透過 list_entry 宏來存取該節點的資料：

移除節點後，需要將該節點的資料複製到指定的 `sp`，字串複製方法選擇上：
在初始實作中，使用了 `strcpy()` 來完成此操作：
`strcpy(sp, get_data->value);`

然而，查閱 C99規格書後，發現 `strcpy()` 存在潛在的 buffer overflow 風險，因為它不會檢查目標緩衝區的大小。：
> 7.21.2.3 The strcpy function
> char *strcpy(char *restrict s1, const char *restrict s2);
> The strcpy function copies the string pointed to by s2 (including the terminating null
character) into the array pointed to by s1. If copying takes place between objects that
overlap, the behavior is undefined.

為了提高安全性，改用 `strncpy()`，並指定 bufsize - 1 作為複製的最大長度。`strncpy()`：
> 7.21.2.4 The strncpy function
> char *strncpy(char *restrict s1, const char *restrict s2, size_t n);
> The strncpy function copies not more than n characters from the array pointed to by s2 into the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined. If the array pointed to by s2 contains fewer than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written. If the array pointed to by s2 contains n or more characters, the result will not be null-terminated.

if (sp) {
        strncpy(sp, get_data->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

根據 `strncpy()` 的行為，若 `s2` 的長度超過 `n`，則 `s1` 可能不會自動加上 \0，因此需要手動確保終止符：

如此設定 bufsize - 1，確保最多僅複製 bufsize - 1 個字元，並在 `sp[bufsize - 1]` 手動填入 \0，確保字串正確終止，避免 undefined behavior。
### q_remove_tail
q_remove_tail 整體作法與 q_remove_head 相同，只需更改目標節點位置即可：
`struct list_head *tmp = head->prev;`
設定為 queue 的尾巴。

### q_size
q_size 函式的目標是計算鏈結串列中的元素數量。首先，函式會檢查 head 是否為 NULL，若為 NULL，則直接回傳 0，避免對無效指標進行操作。

接著，透過 `list_for_each` 宏訪問 `head` 指向的鏈結串列，並使用變數 `len` 來記錄節點數量。

最後，函式回傳計算出的節點數量：

### q_delete_mid
實作 q_delete_mid，首先計算queue的大小，以變數`check`計算，得到中間節點的位置，以變數 `n` 儲存

list_for_each(
            now,
            head) {  
            check++;
        }
 int n = (check - 1) / 2;

接下來使用函式 `list_for_each_safe`，此函式允許在迴圈中移除節點釋放記憶體，當迴圈尋訪到第 n 次時，做刪除:

 list_for_each_safe(
            now, next,
            head) {  
            if (index == n) {
                list_del(now);
                element_t *get_data = list_entry(now, element_t, list);
                free(get_data->value);
                free(get_data);
                return true;
            }
            index++;
        }

### q_delete_dup
實作 q_delete_dup，使用巢狀迴圈，共兩層迴圈，第一層迴圈做每一個節點的尋訪，第二層迴圈確認目前節點是否在後續有重複，如果有，則都刪除，包含目前節點。
問題:

* 當我在迴圈直接做刪除，會發生 Segmentation fault occurred，推測是在刪除節點後，在後續的迴圈尋訪時又尋訪了已刪除節點，導致錯誤發生。
解決方案:
* 確認有重複後，將此節點的資料值修改為"NeedToDel"，視為標記，巢狀迴圈結束後，再設一個迴圈將值標記的節點刪除。

if (strcmp(now_data->value, check_data->value) == 0) {
                free(check_data->value);                  
                check_data->value = strdup("NeedToDel");  
                dup_check = true;
}

if (strcmp(now_check_data->value, "NeedToDel") == 0) {
            list_del(now_check);
            q_release_element(now_check_data);
}

解決方案多做了一個迴圈，以及當遇到值為"NeedToDel"時，會出錯，應該去解決 Segmentation fault occurred 問題。

### q_swap
q_swap 用於交換 queue 中的相鄰節點，實現方式是使用 `list_move()` 來移動節點位置，確保 `prev` 和 `next` 指標正確更新，以維持 queue 的正確連結。

1. 設置指標 `now`，從 `head->next` 開始遍歷 queue。
1. 設置指標 `safe`，存儲 `now->next->next`，確保下一次迴圈能正確運行，並防止因節點移動導致的無效訪問。
1. 使用 `list_move()` 交換 `now->next` 節點的位置，使其移動到 `now->prev` 的位置。
1. 更新 `now` 指標為 `safe`，繼續尋訪 `queue`，確保所有相鄰節點都能正確交換。

 while (now != head && now->next != head) {
        safe = now->next->next;           
        list_move(now->next, now->prev);  
        now = safe;                      
}

### q_reverse
q_reverse 的目標是將 queue 內的所有元素倒序排列。

在這之前要先檢查 queue 元素數量，當只有一個元素或是為空，則直接回傳，不進入函式。

 if (!head || list_empty(head) || list_is_singular(head)) {
        return;
}

reverse 方法與 q_swap 類似，但關鍵差異在於：

* q_swap 只交換相鄰節點，而 q_reverse 需要逐一將節點移動到 head 位置。
* `list_move(now, head)`：將當前節點 `now` 移動到 head 位置，使其成為第一個節點。
* safe = now->next 以確保當前節點被移動後，不影響後續遍歷

 while (now != head) {
        tmp_now = now->next;
        list_move(now, head);    
        now = tmp_now;
}

### q_reverseK
q_reverseK 的目標是將 queue 中每 K 個節點 作 區塊反轉，並保持整體 queue 的完整性。
我將處理階段分為以下幾點:
1. 計數:
* 遍歷 queue，確保當前小組內至少有 K 個節點。
* 若不足 K 個節點，則 直接結束。
* 在反轉前，使用 next_group 記錄第 K 節點的下一個節點。

while (!list_empty(head)) {
        int count = 0;  
        next_group = now->next;  
        // start counting
        while (count < k && next_group != head) {
            count++;
            next_group = next_group->next;
        }
        if (count < k) {
            break;
        }

3. 切割:在迴圈中，當計數到 k 個節點後，將從第 k 節點之前到小組 head(temp_head) 作分割成一組需要反轉的 queue 小組。
`list_cut_position(&temp_head, now, next_group->prev);`
5. 反轉:使用 q_reverse(&temp_head) 對 `temp_head` 內的節點執行反轉。
`q_reverse(&temp_head);`
7. 合併:小組反轉結束後，將此子queue合併回主 queue 中。
`list_splice_init(&temp_head, now);`
9. 更新指標:將 now 指向下一個尚未反轉的區塊。
`now = next_group->prev;`
> commit: [`d511daf`](https://github.com/sysprog21/lab0-c/commit/d511dafef8d69757ff588ea8f2d78da9e54f0a81)
> > commit: [`fa7d12c`](https://github.com/sysprog21/lab0-c/commit/fa7d12cd9a9f52051526dc67a88b0c8eaa562f13)

### q_sort
原先 q_sort 實作，暫時使用 insertion sort 進行排行，方便後續 test 測試，之後自行實作 merge sort，將程式碼分為三個部份：
1. q_sort()：`q_sort` 採用 Divide and Conquer（分治法）原理，負責呼叫 `list_merge()` 及 `list_split()`，並透過遞迴進行排序。。
* 分割：使用 `list_split()` 將鏈結串列（queue）一分為二`list_item_t *t2 = list_split(head);`
* 遞迴排序：對分割後的兩個子串列分別進行排序：

        head = list_merge_sort(head);
        t2 = list_merge_sort(t2);

* 合併：最後使用 list_merge() 合併排序後的兩個子串列 `list_merge(head, t2);`
2. list_split():此函式透過快慢指標法（Fast-Slow Pointer），將 queue 切成兩半，並回傳後半部分的頭節點 (t2)。

    list_item_t *slow = head;
    list_item_t *fast = head->next;

    while(fast->next && fast){
        slow = slow->next;
        fast = fast->next->next;
    }

3. list_merge():建立 `final queue` 來存放合併後的結果，並比較 `t1` 與 `t2` 的值，較小者先加入 final queue，再遞迴合併剩餘部分。

    if (t1->value <= t2->value) {
            final = t1;
            final->next = list_merge(t1->next, t2);
    } else {
        final = t2;
        final->next = list_merge(t1, t2->next);
    }

### q_sort(基於list_sort)
根據 Linux Kernel 的合併排序法，將其實做進入 `q_sort` 中，改進效能。
整體結構與一般 merge sort 相同，以 bottom-up 方式建造，並且透過 bit count 防止長時間 loop 佔據系統資源。
將整體程式碼分為3個結構：
1. q_merging()：將得到的兩個單向 queue (head1 & head2)做合併，這兩個 queue 皆是已排序的，而且依據 `descend` 參數（升冪）合併為一個新的 queue。
* 比較 `head1` 和 `head2` 值的大小，依序放入 `tail queue` 中

        if (((strcmp(str1, str2) <= 0) && !descend) || ((strcmp(str1, str2) >= 0) && descend)) {
            *tail = head1;
            tail = &head1->next;
            head1 = head1->next;
        } else {
            *tail = head2;
            tail = &head2->next;
            head2 = head2->next;
        }

2. q_merge_final()：由 `q_merging()` 得到的 queue 仍是單向鏈結串列，這個函式負責 改變 `prev` 指標，轉換為雙向環狀鏈結串列。
* 將兩個單向 queue 合併，這裡的邏輯與 `q_merging()` 類似，但額外設 `prev` 來改成雙向鏈結。

        if (((strcmp(str1, str2) <= 0) && !descend) || ((strcmp(str1, str2) >= 0) && descend)) {
            tail->next = a;
            a->prev = tail;
            tail = a;
            a = a->next;
        } else {
            tail->next = b;
            b->prev = tail;
            tail = b;
            b = b->next;
        }

* 將最後的 queue 轉為環狀鏈結串列：

        tail->next = head;
        head->prev = tail;

3. q_sort()：使用 bottom-up 方式進行 Merge Sort，會比 top-down更有效率。
* 將 queue 拆分為單向鏈結串列，以便後續做 bottom-up：

        head->prev->next = NULL;

* `count` 為二進制計數，控制合併順序。

* 每次從 list 取出一個節點，插入 `pending`（待合併的 queue）。

* 根據 `count` 進行合併，確保合併順序符合 2^k：

        do {
            size_t bits;
            struct list_head **tail = &pending;

            // 找到最右側的 0 bit
            for (bits = count; bits & 1; bits >>= 1) {
                tail = &(*tail)->prev;
            }

            // 若 bits != 0，則合併 a 和 `b`
            if (bits) {
                struct list_head *a = *tail;
                struct list_head *b = a->prev;
                a = q_merging(b, a, descend);
                a->prev = b->prev;
                *tail = a;
            }

            // 插入當前 list 節點到 pending
            list->prev = pending;
            pending = list;
            list = list->next;
            pending->next = NULL;
            count++;
        } while (list);

* 可以發現整段 bottom-up 都沒有使用遞迴，以及合併的次數也下降，提升效率，減少記憶體的使用。

### q_descend
q_descend 移除所有在其右側存在值更大的節點的節點。
實作方法:
* 設置 `now` 指標從最尾端開始尋訪節點，也就是 `head->prev`開始。
`struct list_head *now = head->prev;`
* 設置 `now` 指標指向之節點值為 `min` 。
`const element_t *min = list_entry(now, element_t, list);`
* 設置 `now->prev` 指標指向節點值為 check_value，並且做比較。
`element_t *check_value = list_entry(now->prev, element_t, list);`
* 當 `min > check_value`，也就是右側存在值更大的節點，則做 remove。否則更新 now 指標到下一個比較對象。

if (strcmp(check_value->value, min->value) < 0) {  
            struct list_head *tmp = now->prev;
            list_del(tmp);
            free(check_value->value);
            free(check_value);
        } else {
            now = now->prev;  
            continue;
        }

### q_ascend
整體做法與q_descend相同，只要改變比較值即可:

if (strcmp(check_value->value, max->value) < 0) { 
            now = now->prev;                     
            continue;
        } else {
            struct list_head *tmp = now->prev;
            list_del(tmp);
            free(check_value->value);
            free(check_value);
        }

### q_merge
q_merge 需要將多個 queue 做合併，並且排序完成。
將多個 queue 合併，根據標頭檔，需使用結構 queue_contex_t:

/**
 * queue_contex_t - The context managing a chain of queues
 * @q: pointer to the head of the queue
 * @chain: used by chaining the heads of queues
 * @size: the length of this queue
 * @id: the unique identification number
typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;
  */

原先想法:
將多個 queue 直接合併，而後直接做排序，也就是呼叫 q_sort 直接做排序。
時間複雜度過高，因此改變作法。
目前作法:
1. 設置主 queue 作為，最終完成排序以及合併的 queue:

    struct list_head *first_queue =
            list_entry(head->next, queue_contex_t, chain)->q;

2. 使用 `list_for_each_safe` 來遍歷 head 內的 queue list，確保合併時不會影響迴圈結構。
3. 兩個 queue 進行合併，以 Merge sort 的做法實作。
* 透過 strcmp 比較 first_queue 和 subqueue 的 value，按照 descend 來決定排序方向
* 若 descend = true，則較大的值優先移動到 final。
* 若 descend = false，則較小的值優先移動到 final。

    if ((descend && strcmp(elem_1->value, elem_2->value) > 0) ||
                    (!descend &&
                     strcmp(elem_1->value, elem_2->value) < 0)) {  
                    list_move_tail(first_queue->next,
                                   &final);  
                } else {
                    list_move_tail(subqueue->next, &final);
                }

使用 ~~`list_move`~~ 負責將較小或較大的元素移動到 final queue。
應該使用` list_move_tail()` 做移動，否則順序會錯誤。

4. 做完排序後，將 final queue 合併到 first queue，並且清空子 queue:

    list_splice(&final, first_queue);
    INIT_LIST_HEAD(subqueue);

> commit: [`d918b26`](https://github.com/sysprog21/lab0-c/commit/d918b26ba018e898f704a476017dd7596bea3300)

## 在 qtest 提供新的命令 shuffle
允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」。

### 什麼是 Fisher-Yates shuffle
透過一個迴圈對陣列做迭代陣列，為了保證每一個元素都有被隨機交換，其作法是每次從最後一個元素開始，每次都跟最後一個元素之前面一個隨機的元素交換位置，假設陣列 n 最後的值為n-1，從陣列第一項 0 到第 n-2 項中隨機選一數 j，將n-1與j做交換，之後繼續迭代。

for (int i = n - 1; i > 0; i--) {
    // 在範圍 [0, i] 中隨機選一個 j
    int j = rand() % (i + 1);

    // 交換 arr[i] 和 arr[j]
    swap(arr[i], arr[j]);
}

### 如何新增命令
觀察 q_test 關於各種命令架構，指令程式碼架構，以`do_指令()`對應到 `ADD_COMMAND(指令, "描述", "");`，因此，首先嘗試根據這樣的架構進行撰寫。

開始 make 後，得到錯誤回報：

qtest.c: In function ‘do_shuffle’:
qtest.c:1069:5: error: implicit declaration of function ‘q_shuffle’; did you mean ‘do_shuffle’? [-Werror=implicit-function-declaration]
 1069 |     q_shuffle(current->q);
      |     ^~~~~~~~~
      |     do_shuffle
cc1: all warnings being treated as errors

查詢資料後，發現沒有在標頭檔做對應函式的宣告，因此在編譯的時候，`q_test.c` 無從得知 `q_shuffle()`是什麼，修正後，可以順利執行 shuffle 。

執行 git commit -a 後，出現錯誤：

Following files need to be cleaned up:
qtest.c
queue.c
queue.h queue.c queue.h

[!] You are not allowed to change the header file queue.h or list.h

由此可知，不允許修改 queue.h 標頭檔，因此改成在 qtest.c 上做 forward_declare <
，以此解決問題。
> commit: [`7d68077`](https://github.com/sysprog21/lab0-c/commit/7d68077)

修正隨機不均勻問題，應該將`srand()`放入 `q_test()` 之 `main()` 中，才不會發生重複呼叫問題。
> commit: [`b92846f`](https://github.com/sysprog21/lab0-c/commit/b92846f)

### 驗證 shuffle 結果
測試次數：1000000次
測試樣本：排列[1,2,3,4]（共4!=24種可能）
期望值：根據測試次數，以及共有24種可能，期望值為41666

Expectation:  41666
Observation:  {'1234': 41347, '1243': 41740, '1324': 41706, '1342': 41542, '1423': 41581, '1432': 41755, '2134': 41613, '2143': 41621, '2314': 41731, '2341': 41628, '2413': 41734, '2431': 41801, '3124': 41566, '3142': 41608, '3214': 41443, '3241': 41615, '3412': 41430, '3421': 41563, '4123': 41867, '4132': 41706, '4213': 41889, '4231': 41496, '4312': 42067, '4321': 41951}
chi square sum:  16.017040272644362

將數據丟入 ChatGPT 進行分析：
實際觀察到的每種排列次數皆落在合理範圍（約 ±1% 內），計算得出的 卡方統計量為 16.02，自由度為 23。查閱卡方分布表得知，這個結果遠低於顯著水準 α = 0.05 下的臨界值 35.17。

##