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

### Reviewed by `allenliao666`

- 開發紀錄中有多處句尾沒有句號，應統一使用句號
- `q_insert_tail` 段落描述程式碼版本間差異可使用 git diff ，以方便閱讀
- `q_delete_dup` 錯誤使用縮排
:::success
謝謝同學，已修正問題。
:::

## 開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12500H
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  12
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4500.0000
    CPU min MHz:         400.0000
    BogoMIPS:            6220.80

## 開發過程
在把更改過的檔案更新至 Github 的時候跳出下圖的結果
> -- Capitalize the subject line

發現沒注意到標題首字需要大寫，故回去看如何寫註解的規則。

根據[如何寫一個-git-commit-message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)可以知道規則有以下：
1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. **標題開頭要大寫**
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how

## 針對佇列操作的程式碼實作
### q_new()
使用 `malloc` 來配置 `struct list_head` 大小的記憶體空間給最初的節點，為了避免 `head` 指標為 NULL 而導致 `malloc` 無法成功配置記憶體空間的情況，所以使用 if-statement 判斷此節點是否為 NULL，若不為 NULL 則使用 `list.h` 的函式 `INIT_LIST_HEAD` 進行節點的初始化。

struct list_head *q_new()
{  
    struct list_head *head =  malloc(sizeof(struct list_head));
    if (head)
        INIT_LIST_HEAD(head);
    return head;
}

### q_free()

:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::

根據要求，需要把全部佇列所配置的記憶體釋放掉。
首先會檢查 `list_head` 是否為空，如果是空的話，就直接離開這個函式。接下來，會使用 `list.h` 中的 `list_for_each_entry_safe` 來安全地走訪所有節點。這個函式會先刪除 `list_head`，然後使用`q_release_element` 函式來移除 `element_t` 裡的結構。最後釋放 `list head` 中的 `head`。

確保了在遍歷並刪除所有節點之後，進行資源釋放。

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

void q_free(struct list_head *head) {
    if (!head)
        return;
    
    element_t *entry, *safe;
    list_for_each_entry_safe(entry, safe, head, list) {
        list_del(&entry->list);
        q_release_element(entry);
    }
    free(head);
}

### `q_insert_head`
根據要求，在佇列開頭(head)插入給定的新節點。

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

沒做到的事，不要輕易宣稱。以下行文是否流暢？你如何展現學了二十餘年的漢語呢？
:::

檢查 `list_head` 是否為空，若為空就回傳 false。接著，為 node 配置`element_t`大小的記憶體空間，並檢查配置是否成功。
同時，我們也要為字串配置記憶體空間，其大小由`str_size`計算而得，再次確認配置是否成功。
在進行記憶體配置後，我們需要從指標 s 的記憶體位置複製到新節點的 value 位置。這裡要使用 memcpy 函數，將 s 中的字串複製到新節點的 value 中。需要注意的是，我們在計算`str_size`時已經包含了結尾的空字串\0，因此在複製字串時，我們只需要複製前面的字元，即 `str_size` - 1。

最後，使用 `list_add` 函數將新的節點插入到head所指向的節點之前。這樣就完成了將新節點加入到鍵結串列中的操作。

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *node = malloc(sizeof(element_t));
    if (!head || !node)
        return false;
    int str_size = (strlen(s) + 1) * sizeof(char);
    node->value = malloc(str_size);
    if (!node->value) {
        free(node);
        return false;
    }
    memcpy(node->value, s, str_size - 1);
    node->value[str_size - 1] = '\0';
    list_add(&node->list, head);
    return true;
}

### q_insert_tail
此題與 `q_insert_head` 做法相似，只是改成在結尾的地方插入新的節點，所以我們只要改成最後面 `list_add_tail` 的地方。

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *node = malloc(sizeof(element_t));
    if (!head || !node)
        return false;
    int str_size = (strlen(s) + 1) * sizeof(char);
    node->value = malloc(str_size);
    if (!node->value) {
        free(node);
        return false;
    }
    memcpy(node->value, s, str_size - 1);
    node->value[str_size - 1] = '\0';
-   list_add(&node->list, head);
+   list_add_tail(&node->list, head);
    return true;
}

### q_remove_head
根據要求，在佇列開頭移去節點。

**刪除與移除的概念**可以參考 [2024 年 Linux 核心設計/實作課程作業 —— lab0 (A)](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a) 提及的內容，了解刪除和移除主要的差異為**目標節點還是否存在於記憶體空間**。

"delete" 和 "remove" 看似都是「刪去某物」，在 Linux 核心的 [include/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中，這二個動作並存，但實際行為卻不同。依據 [Difference between "delete" and "remove"](https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove) 的解釋，可知:

* "remove" 這動作對於 linked list 來說，是斷開節點和節點的關聯，也就是說原本若是 A B C，在 remove(B) 操作完成後，就會變成 A C 的節點關係。特別注意到 B 這個節點其實還存在於記憶體中，只是我們無法從節點間的關係看出來。於是 "remove" 可解讀為 "take away" (將某物帶走)
* "delete" 則有 "erase" 的涵義，若用於 linked list，則指某個節點將被「抹除」，對應的記憶體空間可能會被釋放 (release) 或回收 (reclaim)，並非只是指標的變化

程式步驟：
首先要確保所處理的鏈結串列不是空的。因此，我們會檢查 `head` 指標以及目前的鏈結串列是否為空。如果為空就傳回 `NULL`，表示無有效資料可處理。
接著，在進行字串複製之前，我們需要檢查 `bufsize` 是否存在。若存在才會進行字串的複製操作。在這個過程中，我們必須確保在字串尾端添加 \0，以標示字串的結尾。在計算最大複製字符數時，我們會將所要複製的最大字符數減去結尾字符的佔位。
最後從鏈結串列中刪除移除節點指向的節點時，會回傳指向移除節點的指標。

    if (!head || list_empty(head))
        return NULL;
    element_t *remove_node = list_entry(head->next, element_t, list);
    if (bufsize) {
        strncpy(sp, remove_node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&remove_node->list);
    return remove_node;

### q_remove_tail
此題與 `q_remove_head` 的做法相似，只要更改 `list_entry` 第一個參數 head->next 更改為 head->prev。

    if (!head || list_empty(head))
        return NULL;
-   element_t *remove_node = list_entry(head->next, element_t, list
+   element_t *remove_node = list_entry(head->prev, element_t, list);
    if (bufsize) {
        strncpy(sp, remove_node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&remove_node->list);
    return remove_node;

### q_size
根據要求，計算佇列的節點總量。
首先檢查串列的 `head` 是否為空，如果為空就回傳 `NULL`。接著我們可以使用 `list_for_each` 來走訪整個串列，並在每次走訪過一個節點時將計數器加一。最後，我們回傳計數器的值，這個值即為串列中節點的數量。

    if (!head) {
        return 0;
    }
    int len = 0;
    struct list_head *node;

    list_for_each (node, head)
        len++;
    return len;

### q_delete_mid
根據要求，移除佇列中間的節點。

可以使用兩個指標 `left` & `right` 分別指向鏈結串列的頭尾，各自向反方向走訪節點尋找中間的節點，須考慮兩種情況：
* Case1: 節點數為奇數，兩個指標會相遇，使用 left != right 判斷
* Case2: 節點數為偶數，兩個指標會相鄰，使用 left->next != right 判斷

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

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

在檢查`head`和目前的鏈結串列是否為空的情況下，並利用`list_is_singular`確認是否僅有一個節點存在。接著，使用`list_for_each_entry_safe`來逐一走訪每一個節點。在走訪過程中，需要確認是否存在重複內容的節點，這可以透過以下步驟實現：

首先，利用`flag`這個標誌位來標記重複的情況。同時，利用字串指標儲存下一個節點的內容，並進行比較。若下一個節點不等於`head`且與目前節點的字串內容不同，則繼續迭代。若下一個節點與目前節點的字串內容相同，則將`flag`設置為1。當`flag`等於1時，則刪除該節點並釋放相應的資源。

這樣的流程確保了在鏈結串列中不僅能夠有效地檢查重複內容，並且能夠在需要時適當地刪除重複節點。

    if (!head)
        return false;
    if (list_empty(head) || list_is_singular(head))
        return true;
    element_t *node, *safe;
    bool flag = 0;
    list_for_each_entry_safe (node, safe, head, list) {
        char *str = list_entry(node->list.next, element_t, list)->value;
        if (node->list.next != head && !strcmp(str, node->value)) {
            list_del(&node->list);
            q_release_element(node);
            flag = 1;
        } else if (flag) {
            list_del(&node->list);
            q_release_element(node);
            flag = 0;
        }
    }
    return true;

### q_swap
根據要求，交換佇列中鄰近的節點。
#### swap nodes in pairs
根據提示，先理解 [leetcode - swap nodes in pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)，題目為單向鏈結串列的兩兩交換。
實作流程：建立一個名稱為 dummy 的節點指向第一個節點，用於儲存暫時的結果，`cur` 指標指向用來判別當下節點與該節點的下一個節點是否為 NULL，成立則停止交換。交換則使用 `first` 和 `second` 指標指向目標節點與目標的下一個節點，把兩者交換後把 `cur` 指標往後兩個節點更新。

digraph singly_linked_list {
   rankdir=LR;
    node [shape=record];

    // Define the node structure
    node [label="{<data> data | <next> next}"];

    // Define nodes
    dummy [label="dummy"];
    node0 [label="{<data> 1 | <next> }"];
    node1 [label="{<data> 2 | <next> }"];
    node2 [label="{<data> 3 | <next> }"];
    node3 [label="{<data> 4 | <next> }"];

    // Connect nodes
    dummy:next -> node0:data;
    node0:next -> node1:data;
    node1:next -> node2:data;
    node2:next -> node3:data;


    // Optional: Add a dummy node to represent the end of the list

    null_node [label="NULL",shape=plaintext];

    // Connect the last node to NULL
    node3:next -> null_node;

    // Add a cur pointer to the dummy node
    cur [label="cur",shape=plaintext];
    cur -> dummy;
}

:::spoiler 實作程式碼

struct ListNode* swapPairs(struct ListNode* head) {
    struct ListNode *dummy=(struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *cur = dummy;
    
    while(cur->next!=NULL && cur->next->next!=NULL)
    {
        struct ListNode *first=cur->next;
        struct ListNode *second=cur->next->next;
        first->next = second->next;
        cur->next = second;
        second->next = first;
        cur = cur->next->next;
    }
    return dummy->next;
}  

:::
#### 回到 swap 實作
因為是雙向鏈結串列，所以我不用建立一個新的節點和 `curr` 來判斷是否指向 NULL，並且可以利用 `list.h` 裡的函式 `list_del()` 和 `list_add()` 來刪除與加入節點，之後發現有 `list_move()` 函式可以做到相同的動作，故更改程式。

我使用 `node1`, `node2` 以及 `safe` 指標分別指向頭部的下一個和下下個節點，safe 則指向下一輪交換的首節點。

void q_swap(struct list_head *head)
{
    struct list_head *node1, *node2, *safe;
    for (node1 = head->next, node2 = node1->next, safe = node2->next;
         node1 != head && node2 != head;
         node1 = safe, node2 = node1->next, safe = node2->next) {
-       list_del(node1);
-       list_add(node1,node2);
+       list_move(node1, node2);
    }
}

### q_reverse