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

### Reviewed by `weihsinyeh`
1. [commit 8477620](https://github.com/w96086123/lab0-c/commit/8477620260a622c8d637d2f955e979c6104a07f8) 說list_for_each_entry_safe 可以解決 older solution don't free element. 的原因會讓讀者更清楚修改的用意。
2. [commit 77f096a](https://github.com/w96086123/lab0-c/commit/77f096ae8cc7568d82ee75d2fe8e9e39779ddddb) 看merge的程式碼讓我發現原來可以這樣使用 LIST API ，而不用寫得很冗長。可以將想法寫到 commit 裡面。
3. 除了在 commit 裡面紀錄修改，也可以把每次 modify 的原因寫在開發紀錄裡面。好處就是自己有哪些問題可以順便紀錄，而不用在 commit 的前要先把自己有疑慮的程式註解掉，節省麻煩。

## 開發環境
$ gcc --version
(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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99

## 指定的佇列操作

### `q_new`

:::danger
使用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範
:::

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

利用 malloc 進行記憶體配置，並利用 list.h 中的 INIT_LIST_HEAD 讓 head 自己指向自己，達成空佇列的表示。

:::danger
改進你的漢語表達。
:::

### q_free

:::danger
使用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範
:::

>先理解 list_for_each_entry_safe 這個巨集

:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

此巨集代表的是將 List 更迭，過程中會將 next 讀入並且存起來，此作法稱為 safe ，因此適合用於刪除 List 的時使用。
並且需要搭配我希望可以搭配 `q_release_element` ，因此我選擇使用 `list_for_each_entry_safe` 。

將 List 更迭一次。在的過程中，將當前的 node 進行刪除，並將該空間釋放出來，達到釋放佇列的空間。

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

### q_insert_head
>先理解 element_t 這個型態裡包含什麼

typedef struct {
    char *value;
    struct list_head list;
} element_t;

可知 `element_t` 中會儲存值與前後節點的指向

先建立一個 `element_t` 的型態並命名為 new_element ,後將 s 複製給 new_element 的 value ，並且利用 list_add_head 這個巨集進行在 head 的地方插入，若以上動作都可完成，傳回 ture ，否則回傳 false

### q_insert_tail

:::danger
使用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範
:::

與 q_insert_head 作法相似。不同之處為利用的巨集不同，此功能需要用到的巨集為 list_add_tail 。

### q_remove_head

:::danger
使用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範
:::

>由於註解上只有寫 Remove an element from head of queue ，但回傳的型態是 element_t，因此要先了解回傳的內容是什麼

由於回傳的型態為 element_t ，因此可以猜測實作的方式為將 head 由佇列中刪除，且不用釋放原有的空間，並返回 head 即可。

### q_remove_tail

:::danger
使用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範
:::

與 q_remove_head 相似，只需要將提取的地方由 first 改成 last 即可。

### q_delete_mid

:::danger
使用 `git rebase -i` 重新撰寫 git commit message，務必詳閱作業說明提及的規範
:::

> 直觀作法為先取得 queue 的大小，並且除以2取得中間的索引值，後將中間節點移除並且釋放空間。

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

由於上課有提到[快慢指標](https://hackmd.io/@sysprog/ry8NwAMvT)的方式，嘗試使用此作法。

:::danger
為何要捨近求遠？教材已針對上述議題討論，你該在此展現自己的洞見。
:::

### q_delete_dup

建立兩個指標 prev and current ，藉由比較指標的內容來判斷是否有重複，若有重複則將 current 所指向的內容刪除，並且將 current 指向下一個點，若沒有相同，則將 prev and current 指向各至的下一個節點。

:::danger
改進你的漢語表達。
:::
原有的刪除方式會遺留一個重複的節點，因此結果出錯。
所以加入一個 `bool` 變數判斷目前節點是否曾為重複的。若目前節點與下個節點數值不一樣且 `bool` 為真時，則刪除目前節點，已解決原有的問題。
### q_swap
參考 [Han1018](https://github.com/Han1018/lab0-c/blob/master/queue.c)，他利用了迴圈的處理方式，先分成初始化、條件式和計算方式三個部份，初始化的部份，會先建立兩個指標，個別指向 head->next 和 head->next->next，條件式的條件為只有其中一個指標為 head 時則跳出迴圈，計算方式的部份則是個別指標往後跳兩格，達到處理一對的效果。

:::danger
不要說「似乎」「有點」這種不清晰的話語，工程人員說話要精準。學員投入時間到這門課程，就是希望自己的專業素養能提升，你既然發現他人的不足，就該清楚陳述你認為更好的方案，並予以討論。

假裝有禮貌，無助於討論。
:::

但是這位同學的指標名稱不好，分別為 li 和 tmp ，這樣的寫法無法很容易判斷相互關係，因此我將指標名稱改成 pre 和 current ，提昇可讀性。

:::warning
你的開發紀錄當然反映出「你的觀點」，因此不用說「個人認為」，清楚闡述考量即可。在[第 3 次作業](https://hackmd.io/@sysprog/linux2024-review)中，你可充分發揮。
:::

### q_reverse
利用 `list_for_each_safe` 的操作，可以一次取得目前與下一個節點。在遍歷的過程中，進行以下操作，將目前節點的 `next` 與 `prev` 進行交換，直到結束。

### q_reverseK
原本想要利用 `q_reverse` 進行修改，但發現如果用此方式需要進行切割，所以會產生多於步驟，譬如：切割。因此改成移動 head 與將目前的 node 移動至當前 head 的方法，進行處理。
另外每組需要交換的數量要設定為輸入值減一，理由為，因為使用的方法為將 node 移動至當前的 head 並且初始開始移動的 node 為 `head->next` ，因此每組實際移動的量只有輸入值減一。
### q_sort
Sort 有許多種方法，譬如： quick sort ， merge sort 等等。
因為原本需要提供 merge 方法，因此我實作 merge sort ，實作方法如下。
1. 使用快慢指針尋找中間節點。
2. 利用 `list_cut_position` 和 `list_splice` 進行切割。
3. 利用遞迴的方式對切割後的兩個 `list` 再次進行切割。
4. 進行 merge

### q_merge
一開始看到 `head` 為 list_head 時，感到疑問，因為要進行合併應該要為多的鏈結的 head ，因此觀看同學們的程式碼與 `qtest` 發現格式一開始要先轉換為 `queue_contex_t` 。

#### queue_context_t

digraph {
    rankdir = LR;
    node [shape="box"];
    // splines=false;
    // overlap = scale;
    struct1 [label= 
    <
        <table>
            <tr>
                <td port="q">q</td>
            </tr>
            <tr>
                <td port="chain">chain</td>
            </tr>
            <tr>
                <td port="size">size</td>
            </tr>
            <tr>
                <td port="id">id</td>
            </tr>
        </table>
    >,
    ];
    struct2 [label= 
    <
        <table>
            <tr >
                <td port="q">q</td>
            </tr>
            <tr >
                <td port="chain">chain</td>
            </tr>
            <tr >
                <td port="size">size</td>
            </tr>
            <tr>
                <td port="id">id</td>
            </tr>
        </table>
    >
    ];
    struct3 [label=
    <
        <table>
            <tr>
                <td port="value">value</td>
            </tr>
            <tr>                
                <td port="list">list</td>
            </tr>
        </table>
    >
    ];
    struct4 [label=
    <
        <table>
            <tr>
                <td port="value">value</td>
            </tr>
            <tr>                
                <td port="list">list</td>
            </tr>
        </table>
    >
    ];
    struct5 [label=
    <
        <table>
            <tr>
                <td port="value">value</td>
            </tr>
            <tr>                
                <td port="list">list</td>
            </tr>
        </table>
    >
    ];
struct6 [label=
    <
        <table>
            <tr>
                <td port="value">value</td>
            </tr>
            <tr>                
                <td port="list">list</td>
            </tr>
        </table>
    >
    ];
    {rank=same; struct1; struct2;}
    {rank=same; struct3; struct4;}

    struct1:chain -> struct2;
    struct2:chain -> struct1;

    struct1:q -> struct3;
    struct2:q -> struct4;

    struct3:list -> struct5;
    struct4:list -> struct6;
    struct5:list -> struct3;
    struct6:list -> struct4;


}

> [name=趙韋霖] 需要尋找如何讓線不要與節點重疊。

依照上面的 `queue_context_t` 的架構內容，知道使用合併前需要先使用 `contain_of` 進入各 `q` 取得每個 link list 的 head ，後續就使用常用 merge 方法。

### q_ascend 和 q_descend
兩組方法相似，差異只為遞增或遞減，因此可以寫為同一個函式。
根據 Leetcode 給予的兩個 Hit ，知道在原有的題目上需要 Reverse 與儲存目前的最大值。
由於 Leetcode 給予的資料結構為單向鍊結，但在使環境下使用的是雙向環狀鍊結，因此可以直接使用 prev ，不需要進行反轉。