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

:::danger
注意空白！
唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
:::

## 開發環境

$ 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):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
    CPU family:          6
    Model:               166
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            0
    CPU max MHz:         4700.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3199.92

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

在一週的時間發現自己不足，不補三週的內容，也把以前的 fundamental of data structure in c 與 C++ How to Program : Late Objects Version ，才找回對鏈結串列<s>連結串列</s> 鏈結串列與其他演算法的概念<s>感覺</s>

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

你所不知道的 C 語言: linked list 和非連續記憶體中提及，指標的指標應用與如何寫出優雅的程式
首先是結構定義:

typedef struct list_entry {
    int value;//the value stored in noide
    struct list_entry *next;
} list_entry_t;

要從給定的鏈結串列中，移走 (remove) 符合特定數值的節點時，可撰寫以下程式碼:

list_entry_t *remove(list_entry_t *head, int value)
{
    if (!head)//linked list without head
        return NULL;
    if (head->value == value)//the node with that value is pointed by head
        return head->next;

    list_entry_t *prev = head;
    list_entry_t *cur = head->next;
    while (cur) {//loop through the list to find the node with the value
        if (cur->value == value) {
            prev->next = cur->next;
            return head;
        }
        prev = cur;
        cur = cur->next;
    }
    return head;               
}

這段程式碼考慮到開頭的節點是否被移走，於是要有對應的程式碼來處理特例，最終回傳新的開頭節點。改進方式為，引入一個暫時節點，使其在給定的開頭節點之前，這樣就不用特別撰寫程式碼來處理特例：

list_entry_t *remove(list_entry_t *head, int value)
{
    list_entry_t dummy = {.next = head};
    for (list_entry_t *prev = &dummy; prev->next; prev = prev->next) {
        if (prev->next->value == value) {
            prev->next = prev->next->next;
            break;
        }
    }
    return dummy.next;
}

> The first operand of the . operator shall have a qualified or unqualified structure or union
type, and the second operand shall name a member of that type.

參考規格書中針對 `.` 的敘述，此函式將 dummy 視為 list 的一員

不過這段程式碼依舊可改進，因為我們根本不用回傳新的開頭節點，相反的，可將函式原型改為 `void remove(list_entry_t **head, int value)`，藉由間接指標來更動傳入的鏈結串列開頭節點。

void *remove(list_entry_t **head, int value)//**head is the pointer to the head
{
    for (list_entry_t *prev = &(**head); prev->next; prev = prev->next) {
        if (prev->next->value == value) {
            prev->next = prev->next->next;
            break;
        }
    }
}

在閱讀作業時了解到 `e.g.` 是範例與舉例的簡寫

## 指定的佇列操作
參考 <pao0626> 、<ShallowFeather>、<vax-r>

### `q_new`
>建立新的「空」佇列
* 問題：如何建立佇列、何謂空
* 方法：利用The Linux Kernel API中的void INIT_LIST_HEAD(struct list_head *list)建立新的list head
* 實作：建立空序列時先用malloc配置list_head大小的記憶體，INIT_LIST_HEAD來初始化

### `q_free`
>釋放佇列所佔用的記憶體;

* 問題：鏈結串列佔用哪些記憶體、如何釋放
* 方法：釋放指向頭節點的指標和走訪並釋放各個節點的指標與內容
* 實作：利用list_for_each_entry_safe( The Linux Kernel API - List Management Functions)、q_release_element(queue.h)

### `q_insert_head`
>在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)、`q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* 問題：如何確保可以插入並插入新節點
* 方法：確保head指標非空、確保節點本身與value記憶體成功分配，插入節點方法
* 實作：利用malloc分配記憶體給節點本身、strdup分配記憶體給value、並使用list_add、list_add_tail插入新節點
strdup：

### `q_remove_head`在佇列開頭 (head) 移去 (remove) 給定的節點、`q_remove_tail`: 在佇列尾端 (tail) 移去 (remove) 給定的節點;
* 問題：如何確保有節點與內容可以移除並將其移除，如何找到佇列開頭與結尾
* 方法：判段head指標與佇列本身是否為空、找到佇列頭的或尾端、將節點移除佇列、回傳被移除的佇列的值
* 實作：可以呼叫head指向的值或是用list_first_entry，尾端則可以透過list_last_entry、list_del可以移除佇列的節點
bufsize：

### `q_size`
>計算目前佇列的節點總量;
* 問題：如何計算節點數量
* 方法：確保佇列不為空且有函數走訪佇列的每個值
* 實作：判斷head是否為空指標並利用list_for_each走訪每個節點
list_for_each：

### `q_delete_mid`
>移走佇列中間的節點
* 問題：何謂中間?如何找到、是否有東西可以刪
* 方法：因為 queue 是用 circuler linked list 實作，因此可以藉由分別往兩個方向訪問，直到碰頭代表已找到中間點
* 實作：從head開始一邊向first:head->next一邊向second:head->pre開始訪問，直到first==second or first->next == second停止，再將該first 點刪除

### `q_delete_dup`
>在已經排序的狀況，移走佇列中具備重複內容的節點
* 問題：如何找到重複的節點、是否有東西可以刪、是否會重複訪問要定義何時停止
* 方法：用兩個指針訪問每個節點，其中一個放入當前的值，下一個用要被檢查的值，若檢查到一樣的則將其刪除
* 實作：list_for_each_entry_safe(cur, tmp, head, list) ，cur 表示正在訪問的節點，tmp表示下一個要訪問的節點，用list_for_each_entry_safe的好處是當cur被刪除時還是可以，安全的從tmp接續訪問

### `q_swap`
>交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
* 問題：以兩個節點為一組，兩兩交換，在訪問每一組時將他們交換
Input: head = [1,2,3,4]->Output: [2,1,4,3]
要如何在走訪節點時可以兩兩一組？要如何讓節點位置交換
* 方法：void list_move(struct list_head *list, struct list_head *head)可以讓list節點接續head節點
* 實作：用list_for_each走訪節點，並用list_move將當前接續下一個節點，接著第二次遞迴時，他會從根據順序走訪第一個節點的下一個節點，也就是第三個節點，以此接續直到到，下一個節點為head時結束
list_move後為何用list_for_each還能走訪到被移動節點的下一個節點

### `q_reverse`
>以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
* 問題：將鏈結串列重新反方向排序
* 方法：從head->pre開始反向走訪節點直到head停止
* 實作：用list_for_each_reverse反向走訪與list_move調整節點位置

### `q_reverseK`
* 問題：如何將鏈結串列以每 k 個節點為一組進行反轉？
* 方法：預先配置一個新的鏈結串列，用於存儲反轉後的結果。每次從原始鏈結串列中取出 k 個節點，並進行反轉，然後將反轉後的結果添加到新鏈結串列的末尾。最後將新鏈結串列中的結果複製回原始鏈結串列。
* 實作：藉由list_cut_position

### `q_sort`
>以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法

* 方法：利用 mergesort 演算法進行排序，將鍵結串列切割為較小的子串列，然後逐步合併這些子串列。
透過遞迴實現 mergesort 演算法，每次將鍵結串列切割成兩半，然後分別對兩半進行排序和合併。
* 實作：首先判斷鍵結串列是否為空或只有一個節點，若是則直接返回，使用快慢指針找到鍵結串列的中間節點，將其分為兩個子串列，遞迴調用 mergesort 函式對這兩個子串列進行排序，最後，將排好序的兩個子串列進行合併，得到最終的排序結果。

### `q_descend`
>參閱 LeetCode 2487. Remove Nodes From Linked List

- 問題：如何在給定的鏈結串列中移除具有比其後面節點值更小的節點？

- 方法：反向遍歷鏈結串列，比較當前節點和其後面節點的值，如果當前節點的值比後面節點的值小，則刪除後面節點。

- 實作：

    int q_descend(struct list_head *head)
    {
        // 確保 head 不為空
        if (!head)
            return 0;

        // 初始化節點計數
        int len = 0;

        // 從最後一個節點開始向前遍歷
        struct list_head *cur = head->prev;

        // 遍歷整個鏈結串列
        while (cur != head) {
            // 增加節點計數
            len++;

            // 如果下一個節點是 head，則跳出循環
            if (cur->prev == head)
                break;

            // 將節點轉換為元素結構
            element_t *c = container_of(cur, element_t, list),
                      *p = container_of(cur->prev, element_t, list);

            // 如果下一個節點的值大於當前節點的值，則刪除下一個節點
            if (strcmp(c->value, p->value) > 0) {
                list_del(&p->list);
                q_release_element(p);
                len--;
            } else {
                // 否則，繼續向前走訪
                cur = cur->prev;
            }
        }

        // 返回節點計數
        return len;
    }

### `q_merge`
>合併所有已排序的佇列，並合而為一個新的已排序佇列

* 問題：如何將所有已排序的佇列合併成一個新的已排序佇列？

* 方法：
1. 檢查佇列是否為空，如果是，則返回。
2. 取得第一個佇列。
3. 如果只有一個佇列，則直接返回該佇列的大小。
4. 從第二個佇列開始，將每個佇列的節點合併到第一個佇列中。
5. 將合併後的佇列進行排序。
6. 返回合併後的第一個佇列的大小。

* 實作：

    int q_merge(struct list_head *head)
    {
        if (!head || list_empty(head))
            return 0;

        // 取得第一個佇列
        queue_contex_t *fir = container_of(head->next, queue_contex_t, chain);

        // 如果只有一個佇列，直接返回大小
        if (head->next == head->prev)
            return fir->size;

        // 從第二個佇列開始合併
        for (struct list_head *cur = head->next->next; cur != head; cur = cur->next) {
            // 取得當前佇列
            queue_contex_t *que = container_of(cur, queue_contex_t, chain);

            // 將當前佇列合併到第一個佇列中
            list_splice_init(que->q, fir->q);

            // 將當前佇列大小歸零
            que->size = 0;
        }

        // 對第一個佇列進行排序
        q_sort(fir->q);

        // 更新第一個佇列的大小
        fir->size = q_size(fir->q);

        // 返回第一個佇列的大小
        return fir->size;
    }