# 2023q1 Homework1 (lab0)
contributed by < `daven3302` >
## 開發環境

$ neofetch --stdout
OS: Arch Linux on Windows 10 x86_64
Kernel: 5.15.79.1-microsoft-standard-WSL2
Uptime: 4 hours, 10 mins
Packages: 423 (pacman)
Shell: zsh 5.9
Terminal: Windows Terminal
CPU: 11th Gen Intel i5-1135G7 (8) @ 2.419GHz
GPU: 7926:00:00.0 Microsoft Corporation Basic Render Driver
Memory: 1308MiB / 7835MiB

$ gcc -v
gcc version 12.2.1 20230201 (GCC)

$ cppcheck --version
Cppcheck 2.10

## 佇列程式碼
### q_new()

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

:::warning
`malloc` 不需要轉型，亦即使用 `head = malloc(...);` 這樣的敘述。
:notes: jserv
- 讓 left value 與 right value 的資料型態相等，是否能讓程式碼的可讀性增加？
:question: daven3302
:::

因為要產生一個空佇列，所以令 head 節點的 prev 和 next 皆指向 head
如果 malloc 回傳 NULL，直接讓函式回傳 NULL

:::info
:joy_cat: 可以使用 `INIT_LIST_HEAD` 使程式碼變得更加易讀
:::

### q_free()
- 程式碼

void q_free(struct list_head *l)
{
    struct list_head *now, *safe;
    list_for_each_safe (now, safe, l)
        q_release_element(list_entry(now, element_t, list));
    free(l);
}

讓指標在佇列做迭代,並且釋放此指標指向的節點，直到佇列為空佇列，再釋放佇列的最開頭的記憶體
為了維持程式碼風格的一致性，將 container_of 替換為 list_entry

### q_insert_head()

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

> how about this

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *insert;
    insert = malloc(sizeof(element_t));
    insert->value = malloc(sizeof(char) * (strlen(s) + 1));
    if(!insert || !(insert->value)){
        free(insert);
        return NULL;
    }
    INIT_LIST_HEAD(&insert->list);
    strncpy(insert->value, s, strlen(s) + 1);
    list_add(&(insert->list), head);
    return true;
}

先配置一塊新的記憶體，然後複製由參數傳進來的字串，將新的記憶體插入佇列
我一開始的時候沒有配置 `element_t` 的成員 value 的記憶體位置，且沒有初始化 element_t 的成員 list，所以導致記憶體錯誤
如果 malloc 回傳 NULL，直接讓函式回傳 NULL，並釋放之前配置的記憶體

新增 '\0' 在字串 `insert->value` 後面，避免字串未終結

### q_insert_tail()

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!s || !head)
        return false;
    element_t *insert;
    insert = (element_t *) malloc(sizeof(element_t));
    if (!insert)
        return false;
    INIT_LIST_HEAD(&insert->list);
    int len = (strlen(s) + 1);
    insert->value = (char *) malloc(sizeof(char) * len + 1);
    if (!(insert->value)) {
        free(insert);
        return false;
    }
    strncpy(insert->value, s, len);
    insert->value[len] = '\0';
    list_add_tail(&(insert->list), head);
    return true;
}

跟 q_insert_head() 一樣的原理,只是插入點由開頭變成結尾
如果 malloc 回傳 NULL，直接讓函式回傳 NULL，並釋放之前要求配置的記憶體

新增 '\0' 在字串 `insert->value` 後面，避免字串未終結

### q_remove_head()

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    struct list_head *node;
    element_t *removed;
    if (!head)
        return NULL;
    if (list_empty(head))
        return NULL;
    node = head->next;
    removed = list_entry(node, element_t, list);
    list_del_init(node);
    if (sp)  // fixed bug when sp is NULL
    {
        strncpy(sp, removed->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return removed;
}

先判定佇列是否為 NULL 或是空佇列，若不是，則將佇列裡第一個元素移除，並將此元素的成員 value，複製到 sp
原本沒有想到當 sp 為 NULL 的情況，所以加了一個判斷式判斷
在提交 git commit 時，pre-commit hook 觸發以下錯誤訊息

Following files need to be cleaned up:
queue.c
list.h:169:13: warning: Either the condition 'head==NULL' is redundant or there is possible null pointer dereference: head. [nullPointerRedundantCheck]
    return (head->next == head);
            ^
queue.c:136:34: note: Assuming that condition 'head==NULL' is not redundant
    if (list_empty(head) || head == NULL)
                                 ^
queue.c:136:20: note: Calling function 'list_empty', 1st argument 'head' value is 0
    if (list_empty(head) || head == NULL)
                   ^
list.h:169:13: note: Null pointer dereference
    return (head->next == head);
            ^
list.h:169:13: warning: Null pointer dereference: head [ctunullpointer]
    return (head->next == head);
            ^
queue.c:69:34: note: Assuming that condition 'head==NULL' is not redundant

                                 ^
queue.c:69:19: note: Calling function list_empty, 1st argument is null
    if (list_empty(head) || head == NULL)
                  ^
list.h:169:13: note: Dereferencing argument head that is null
    return (head->next == head);
            ^

Fail to pass static analysis

所以我將程式碼修正如下:

-if (list_empty(head) || head == NULL)
+if (!head)
+    return;
+if (list_empty(head))   
     return;

### q_remove_tail()

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    struct list_head *node;
    element_t *removed;
    if (!head)
        return NULL;
    if (list_empty(head))
        return NULL;
    node = head->prev;
    removed = list_entry(node, element_t, list);
    list_del_init(node);
    if (sp)  // fixed bug when sp is NULL
    {
        strncpy(sp, removed->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return removed;
}

跟 q_remove_tail 一樣的原理，只是刪除節點由開頭的節點變成結尾的節點

### q_delete_mid()

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head)
        return false;
    if (list_empty(head))
        return false;
    if (list_is_singular(head)) {
        q_remove_head(head, NULL, 0);
        return true;
    }

    int n = q_size(head) % 2
                ? q_size(head) / 2 + 1
                : q_size(head) / 2;  // if the size of the list is odd , you
                                     // need to add 1 to fix
    struct list_head *node;
    node = head;
    for (int i = 0; i < n; i++)
        node = node->next;
    list_del_init(node);
    return true;
}

我選擇用 `q_size()` 回傳佇列的元素數量，來計算從佇列的起始點到中間點的步數，再用迴圈迭代到我要的位置並移除此節點

### q_delete_dup()

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    struct list_head *now, *safe;
    if (!head)
        return false;
    if (list_empty(head))
        return false;
    list_for_each_safe (now, safe, head) {
        if (list_entry(now, element_t, list)->value ==
            list_entry(safe, element_t, list)->value)
            list_del(safe->prev);
    }
    return true;
}

由指標 now 和 safe 所指向的元素去判斷相鄰兩點是否為重複元素，若為重複元素，刪除 now 所指向的節點

### q_swap()

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    struct list_head *n1, *n2,
        *ns;          // n1,n2 are node to swap , ns is start point
    ns = head->next;  // the first start point
    for (int i = 0; i < q_size(head) / 2; i++) {
        n1 = ns;
        n2 = ns->next;
        ns = ns->next->next;  // start point next time
        // swap
        n1->next = n2->next;
        n2->next = n1;
        n2->prev = n1->prev;
        n1->prev = n2;
        n2->prev->next = n2;
        n1->next->prev = n1;
    }
}

若是佇列中的節點數為奇數時,忽略最後一個節點，指標 ns 為每次交換前的起始目標點，所以當每一次交換完成之後，指標 ns 會指向現在節點的後兩個節點

### q_reverse

void q_reverse(struct list_head *head)
{
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        node->next = node->prev;
        node->prev = safe;
    }
    safe = head->next;
    head->next = head->prev;
    head->prev = safe;
}

將 `node->next` 和 `node->prev` 互相交換，只要<s>遍尋</s>(逐一走訪) --- 整個佇列就可達到反轉佇列的目標

:::danger
注意 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) 並正確使用標點符號，區分全形逗點和 comma (`,`)，後者用於分隔英語詞彙或程式碼的 identifier。
:notes: jserv
:::

### q_reverseK

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    struct list_head *node_start, *node_k, *node_next, *tmp;
    node_start = head->next;
    for (int i = 0; i < q_size(head) / k; i++) {
        node_k = node_start;
        for (int j = 0; j < k - 1; j++)
            node_k = node_k->next;
        node_next = node_k->next;
        for (int j = 0; j < k / 2; j++) {
            q_swap_node(node_start, node_k);
            tmp = node_start;
            node_start = node_k->next;
            node_k = tmp->prev;
        }
        node_start = node_next;
    }
}

node_start 為指向

### q_sort

void q_sort(struct list_head *head)
{
    struct list_head *n1, *n2, *tmp;
    list_for_each (n1, head) {
        for (n2 = n1->next; n2 != (head); n2 = n2->next) {
            if (n1 == n2)
                continue;
            if (q_compare(n1, n2) > 0) {
                q_swap_node(n1, n2);
                tmp = n1;
                n1 = n2;
                n2 = tmp;
            }
        }
    }
}

以 bubble sort 來做排序， `n1`,`n2` 所指向的節點交換之後，需要將 `n1`,`n2` 指向正確的位置，所以將 `n1`,`n2` 交換

### q_swap_node

void q_swap_node(struct list_head *node1, struct list_head *node2)
{
    struct list_head *safe1, *safe2;
    if (!node1 || !node2)
        return;
    safe1 = node1->next;
    safe2 = node2->prev;
    if (!safe1 || !safe2 || !(node1->prev) || !(node2->next))
        return;
    bool flag = (node1->next == node2);
    // swap
    node1->next = node2->next;
    node1->next->prev = node1;
    node2->prev = node1->prev;
    node2->prev->next = node2;
    if (flag) {
        node1->prev = node2;
        node2->next = node1;
    } else {
        node1->prev = safe2;
        safe2->next = node1;
        node2->next = safe1;
        safe1->prev = node2;
    }
}

將兩個在佇列上的節點做交換
### q_compare

int q_compare(struct list_head *node1, struct list_head *node2)
{
    return strcmp(list_entry(node1, element_t, list)->value,
                  list_entry(node2, element_t, list)->value);
}

對兩個節點做大小的比較