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

### Review by `164253`
`q_remove_head` 和 `q_remove_tail` 有許多重複部分
`q_delete_mid` 中的快慢指針可以改為兩個指針從頭尾向中間靠近
`q_ascend` 和 `q_descend` 中也有許多重複

## 開發與實驗環境

$ 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:            12th Gen Intel(R) Core(TM) i5-12400
    CPU family:          6
    Model:               151
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         4400.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4992.00

## 使用的結構體

### 雙向鏈節串列實作

:::warning
是「雙向鏈結串列」。
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
:::

使用 `list_head` 以及 `element_t` 這兩種結構體來實作雙向鏈節

#### `list_head`

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

digraph list_head {
    rankdir=LR;
    node[shape=record, style=bold];
    
    subgraph cluster_list_head {
        label="list_head";
        style=bold;
        head [label="{<prev>prev|<next>next}"];
    }
}

#### `element_t`

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

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    
    subgraph cluster_0 {
        node [shape=record];
        value [label="value", width=1.35];
        subgraph cluster_00 {
            label="list_head";
            style=bold;
            head [label="{<prev>prev|<next>next}"];
        }
        style=bold;
        label=element_t;
    }
}

從這兩種結構體的定義中，我們可以了解到本次作業中佇列的實作方式是將結構體 `list_head` 嵌入到新的結構體 `element_t` 中。這種方法類似於 Linux 核心的 Linked list 實作方式。
這樣設計的好處是只要將 `list_head` 納入到新的結構體的一個成員中，就可以操作這個佇列，而不需要自行維護一套雙向鏈結串列。

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    
    subgraph cluster_0 {
        label="list_head";
        style=bold;
        head0 [label="{<prev>prev|<next>next}"];
    }
    
    subgraph cluster_1 {
        node [shape=record];
        value1 [label="value", width=1.35];
        subgraph cluster_10 {
            label="list_head";
            style=bold;
            head1 [label="{<prev>prev|<next>next}"];
        }
        style=bold;
        label=element_t;
    }
    
    subgraph cluster_2 {
        node [shape=record];
        value2 [label="value", width=1.35];
        subgraph cluster_20 {
            label="list_head";
            style=bold;
            head2 [label="{<prev>prev|<next>next}"];
        }
        style=bold;
        label=element_t;
    }
    
    subgraph cluster_3 {
        node [shape=record];
        value3 [label="value", width=1.35];
        subgraph cluster_30 {
            label="list_head";
            style=bold;
            head3 [label="{<prev>prev|<next>next}"];
        }
        style=bold;
        label=element_t;
    }
    
    head0:next -> head1:prev;
    head1:next -> head2:prev;
    head2:next -> head3:prev;
    head3:next -> head0:prev;
}

### 佇列管理

使用結構體 `queue_contex_t` 及 `queue_chain_t` 管理多個佇列

#### `queue_contex_t`

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

:::danger
避免非必要的項目縮排 (即 `* `)，以清晰、明確，且通順的漢語書寫。
> 已修正
:::

`q`：指向佇列 `head` 節點的指標

`chain`：用於將不同佇列的頭節點連接在一起

`size`：表示這個佇列的長度

`id`：唯一的識別號，用於區分不同的佇列

graph {
    rankdir=RL;
    node[shape=record, style=bold];
    
    subgraph cluster_0 {   
        label=queue_contex_t;
        style=bold;
        node [shape=record];

        q [label="q", width=1.35];
        subgraph cluster_00 {
            label="chain";
            style=bold;
            h [label="{<prev>prev|<next>next}"];
        }
        s [label="size", width=1.35];
        id [label="id", width=1.35];
    }
}

#### `queue_chain_t`

typedef struct {
    struct list_head head;
    int size;
} queue_chain_t;

static queue_chain_t chain = {.size = 0};

graph list {
    rankdir=LR;
    style=bold;
    node[shape=record, style=bold];
    // queue_chain_t
    subgraph cluster_1 {
        style=bold;
        label="queue_chain_t";
        node [shape=record];
        s1 [label="size", width=1.35];
        subgraph cluster_10 {
            label="chain";
            style=bold;
            h1 [label="{<prev>prev|<next>next}"];
        }
    }
}

`queue_chain_t` 利用 `chain` 將各個 `queue_contex_t` 串連成一個雙向鍊結串列，如此一來便能管理多個佇列，示意圖如下：

digraph list {
    rankdir=LR;
    style=bold;
    node[shape=record, style=bold];
    
    // queue_chain_t
    subgraph cluster_1 {
        style=bold;
        label="queue_chain_t";
        node [shape=record];
        s1 [label="size", width=1.35];
        subgraph cluster_10 {
            label="chain";
            style=bold;
            h1 [label="{<prev>prev|<next>next}"];
        }
    }
    
    // queue_contex_t
    subgraph cluster_2 {
        style=bold;
        label=queue_contex_t;
        node [shape=record];
        
        q2 [label="q", width=1.35];
        subgraph cluster_20 {
            label="chain";
            style=bold;
            h2 [label="{<prev>prev|<next>next}"];
        }
        s2 [label="size", width=1.35];
        id2 [label="id", width=1.35];
    }
    
    // queue_contex_t
    subgraph cluster_3 {
        style=bold;
        label=queue_contex_t;
        node [shape=record];
        
        q3 [label="q", width=1.35];
        subgraph cluster_30 {
            label="chain";
            style=bold;
            h3[label="{<prev>prev|<next>next}"];
        }
        s3 [label="size", width=1.35];
        id3 [label="id", width=1.35];
    }
    
    a [label="......", color=transparent]
    
    a       -> h1:prev
    h1:next -> h2:prev;
    h2:next -> h3:prev;
    h3:next -> a
    //{rank=same; s1; s2; s3}
    
    
}

## 指定的佇列操作

### `q_new`
> commit [2201f29](https://github.com/sysprog21/lab0-c/commit/2201f294a4eeda28eb3eda7587da4e57b6712a04)

:::danger
使用你 fork 後得到的 GitHub repository 的 commit 超連結
:::

建立新的「空」佇列

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

1. 使用 `malloc` 配置 `list_head` 大小的記憶體空間，並由指標 `head` 指向
2. 若空間分配失敗(`malloc` 回傳 NULL)，則回傳 `NULL`
3. 使用 `INIT_LIST_HEAD` 初始化 `head`

### `q_free`
> commit [0fa78c5](https://github.com/sysprog21/lab0-c/commit/0fa78c540de3c65ebc0e02733dc4b599be47da5a)

釋放佇列所佔用的記憶體

使用 `list_for_each_entry_safe` 走訪每個節點，再利用 `q_release_element` 釋放節點所佔用的記憶體

### `q_insert_head`

> commit [b4290b3](https://github.com/sysprog21/lab0-c/commit/b4290b3e0e1dd54a8f3413fc597549a3039529fa)
在佇列前端插入值為 `s` 的新節點

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

使用 `melloc` 配置 `element_t` 大小的記憶體空間，若配置失敗則回傳 `false`
使用函式 `strdup` 複製字串資料，若複製失敗則回傳 `false`
使用 `list_add` 將節點加入佇列的前端

### `q_insert_tail`

> commit [b4290b3](https://github.com/sysprog21/lab0-c/commit/b4290b3e0e1dd54a8f3413fc597549a3039529fa)

在佇列尾端插入值為 `s` 的新節點

我發現 `q_insert_tail` 實際上與 `q_insert_head` 幾乎相同，唯一的區別在於新元素應該從佇列的哪個位置添加。因此，可以重用 `q_insert_head` 的程式碼。

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }

    q_insert_head(&head->prev, s);
}

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

### `q_remove_head`

> commit [b4290b3](https://github.com/sysprog21/lab0-c/commit/b4290b3e0e1dd54a8f3413fc597549a3039529fa)

將佇列的第一個 `entry` 移除，並將 `entry` 的 `value` 複製到 `buffer` 中

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

使用 `list_first_entry` 取得佇列的第一個 `entry`
使用 `list_del` 將該 `entry` 由佇列中刪除
使用 `strncpy` 複製該 `entry` 的 `value` 至 `buffer`中

:::danger
注意行文的空白字元！
:::

發現原本的方法在buffer大小不夠時會產生字串結尾無'\0'的狀況，修改方式如下:
[7ceb10a](https://github.com/sysprog21/lab0-c/commit/7ceb10a547274ece326883340e493983230be0ac)

@@ -79,7 +79,8 @@ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
     list_del(&element->list);
 
     if (sp && bufsize) {
-        strncpy(sp, element->value, bufsize);
+        strncpy(sp, element->value, bufsize - 1);
+        sp[bufsize - 1] = '\0';
     }
 
     return element;

### `q_remove_tail`

> commit [b4290b3](https://github.com/sysprog21/lab0-c/commit/b4290b3e0e1dd54a8f3413fc597549a3039529fa)

將佇列的最後一個 `entry` 移除，並將 `entry` 的 `value` 複製到 `buffer` 中

與 `q_remove_head`類似，差別為將 `list_first_entry` 改為 `list_last_entry`

### `q_size`

> commit [fc78b84](https://github.com/sysprog21/lab0-c/commit/fc78b84f89a17393f12c0bc20da2af408850b278)

取得佇列的長度

使用 `list_for_each` 走訪佇列的每個節點，並利用變數 `len` 紀錄節點數量

### `q_delete_mid`

> commit [8dc1568](https://github.com/sysprog21/lab0-c/commit/8dc1568dfd782deb7cadb1c69ac6cf7460352e32)

刪除佇列中間的節點

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

參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List) 所提到的**快慢指標**技巧找出佇列中間的節點
使用 `list_del` 將該節點由佇列刪除
使用 `q_release_element` 釋放該節點所佔用的記憶體

### `q_delete_dup`

> commit [b5f0c26](https://github.com/sysprog21/lab0-c/commit/b5f0c26a074c7e32f16ff40f701721e406d2c9ac)

刪除佇列中具有重複值的節點

實作方式：
1. 使用 `list_for_each_entry_safe` 走訪佇列中的每個節點
2. 使用 `strcmp` 比較該節點與右側節點是否有相同的值
3. 若兩節點有相同的值，則將 `equal` 設為 `true`，並將該節點刪除
4. 若兩節點沒有相同的值，則判斷 `equal` 是否為 `true`，

### `q_reverse`

> commit [dd6f602](https://github.com/sysprog21/lab0-c/commit/dd6f602c5b63ce408dc2fbf9a564df3c9a2d6924)

反轉佇列中的元素

逐一將每個節點移動至佇列的最前方，等同於將佇列反轉

使用 `list_for_each_entry_safe` 走訪每個佇列的節點，並利用 `list_move` 將節點移動至佇列的最前方

### `q_reverseK`
> commit [ab10d48](https://github.com/sysprog21/lab0-c/commit/ab10d48aabd127750a631c0df98d5788aa5266f0)

將佇列每 `k` 個節點反轉一次

將佇列以 `k` 為單位，切割成數個子佇列，再將每個子佇列反轉，即可獲得 `reverseK` 的效果

1. 走訪佇列的每個節點，並以指標 `cut` 紀錄子佇列的開頭處
2. 若經過 `k` 個點，則利用 `list_cut_position` 將子佇列切出，並複製至新的佇列 `tmp`
3. 使用 `q_reverse` 將 `tmp` 佇列反轉
4. 使用 `list_splice` 將 `tmp` 佇列插入回原本的佇列

### `q_swap`
> commit [c9e9b0b](https://github.com/sysprog21/lab0-c/commit/c9e9b0b29dc4586e9c1459f85a75118b02be3808)

將佇列每2個節點反轉一次

`q_swap` 為 `q_reverseK` k=2 時的特例

### `q_ascend`
> commit [6a45a0c](https://github.com/sysprog21/lab0-c/commit/6a45a0c395bbc54ec44fd86d4ef0b7997a6ab594)

移除每個節點，只要該節點右側的任何地方存在一個嚴格小於它的節點。

題目要求「若某節點的右側存在值小於該節點的其他節點，則必須移除該節點」。
如果按照原始規則，需要使用兩層迴圈來實作。然而，我們可以將這個條件簡化為「由右至左檢查每個節點，若該節點的左側節點**大於**該節點，則將左側節點移除」。這樣的話，只需要一層迴圈即可實作。

### `q_descend`
> commit [6a45a0c](https://github.com/sysprog21/lab0-c/commit/6a45a0c395bbc54ec44fd86d4ef0b7997a6ab594)

移除每個節點，只要該節點右側的任何地方存在一個嚴格大於它的節點。

與 `q_ascend` 實作方式類似，差別為將條件改為「由右至左檢查每個節點，若該節點的左側節點**小於**該節點，則將左側節點移除」。

### `q_sort`
> commit [601f6b5](https://github.com/sysprog21/lab0-c/commit/601f6b5b5e82e54e98ab315a874e77c9ab41b430)

將佇列中的元素按照升序/降序排序

採用 merge sort 遞迴演算法來實作。

:::danger
如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::

### `q_merge`
> commit [2552906](https://github.com/sysprog21/lab0-c/commit/2552906dc138bd97c594ca95c44424e4da773048)

將所有的佇列合併成一個排序的佇列

將所有的佇列合併為一個佇列，再將該佇列用 `q_sort` 進行排序

## 以 [Valgrind](https://valgrind.org/) 分析記憶體問題

執行 `make valgrind`

執行 massif: 分析
- Heap blocks
- Heap administration blocks
- Stack sizes

valgrind --tool=massif ./qtest -f <trace file>

使用 Valgrind 驗證程式後，沒有出現記憶體錯誤的狀況，但仍然會有錯誤訊息 `ERROR: Probably not constant time or wrong implementation`

使用 massif-visualizer 將數據圖形化

$ massif-visualizer massif.out.<pid>

分析 trace-17-complexity.cmd

## 使用 address sanitizer

make clean
make SANITIZER=1

之後執行 `make test` ，沒有出現任何記憶體相關錯誤訊息，檢查通過。

:::danger
尚未依據作業三指示，進行對應的 git rebase 操作！
:::