---
# System prepended metadata

title: 2022q1 Homework1 (lab0)
tags: [linux2022]

---

---
tags: linux2022
---

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

## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          16
On-line CPU(s) list:             0-15
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           165
Model name:                      Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
Stepping:                        5
CPU MHz:                         2900.000
CPU max MHz:                     4800.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5799.77
Virtualization:                  VT-x
L1d cache:                       256 KiB
L1i cache:                       256 KiB
L2 cache:                        2 MiB
L3 cache:                        16 MiB
NUMA node0 CPU(s):               0-15
```
## 作業要求
> [lab0](https://hackmd.io/@sysprog/2020-lab0)
 
- [x] 開發環境設定
- [x] Fork lab0 on github
- [x] 佇列實作
    - [x] `q_new`: 建立新的「空」佇列
    - [x] `q_free`: 釋放佇列所佔用的記憶體
    - [x] `q_insert_head`: 在 head 插入 (insert) 給定的新節點 (LIFO)
    - [x] `q_insert_tail`: 在 tail 插入 (insert) 給定的新節點 (FIFO)
    - [x] `q_remove_head`: 從 head 移去 (remove) 節點，回傳該節點
    - [x] `q_remove_tail`: 從 tail 移去 (remove) 節點，回傳該節點
    - [x] `q_release_element`: 釋放特定節點的記憶體空間
    - [x] `q_size`: 計算目前佇列的節點總量
    - [x] `q_delete_mid`: 移走佇列中間的節點
    - [x] `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點
    - [x] `q_swap`: 交換佇列中鄰近的節點
    - [x] `q_reverse`: 以反向順序重新排列鏈結串列，不配置或釋放任何節點（重排已經存在的節點）
    - [x] `q_sort`: 以遞增順序來排序鏈結串列的節點
- [ ] 用 Graphviz 在 HackMD 筆記上視覺化展現
- [x] 引入 Git pre-commit hook
    - [x] 透過 clang-format 確保一致的程式風格
        - [x] 詳閱
        - [x] 使用
    - [ ] 透過 GNU Aspell 進行拼字檢查
    - [ ] 開啟 Cppcheck 靜態程式碼檢查功能
- [ ] 以 Valgrind 分析記憶體問題

## 開發過程
### 佇列架構
### lish.h 巨集參考
- `INIT_LIST_HEAD()` - Initialize empty list head
- Add new node
    - `list_add()` - Add a list node to the beginning of the list
    - `list_add_tail()` - Add a list node to the end of the list
    - `list_splice()` - Add list nodes from a list to beginning of another list
    - `list_splice_tail()` - Add list nodes from a list to end of another list
    - `list_splice_init()` - Move list nodes from a list to beginning of another list
    - `list_splice_tail_init()` - Move list nodes from a list to end of another list
- Remove node 
    - `list_del()` - Remove a list node from the list
    - `list_del_init()` - Remove a list node from the list and reinitialize it
- Check
    - `list_empty()` - Check if list head has no nodes attached 
    - `list_is_singular()` - Check if list head has exactly one node attached
- Move
    -  `list_cut_position()` - Move beginning of a list to another list
    -  `list_move()` - Move a list node to the beginning of the list
    -  `list_move_tail()` - Move a list node to the end of the list
- Entry
    - `list_first_entry()` - get first entry of the list 
    - `list_last_entry()` - get last entry of the list
- iteraton
    - `list_for_each` - iterate over list nodes
    - `list_for_each_entry` - iterate over list entries
### 針對佇列的實作
#### `q_new`
用 `malloc` 取得 `struct list_head` 大小的記憶體。
- 如果失敗回傳 `NULL` 。
- 成功則用 `INIT_LIST_HEAD()` 做初始化。 
```c
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}
```

:::danger
注意共筆書寫規範：中英文間用一個半形空白區隔
:notes: jserv
:::
#### `q_free`
此函式須釋放佇列所有空間，所以須釋放 `element` 和 `l` 。

用 `list_for_each_entry_safe()` 走訪節點。
- entry ，對應 element 物件。
- safe ，允許移除目前節點。

用 `list_del()` 移出佇列， `q_release_element()` 釋放節點空間。
釋放佇列 `l` 。
```c
void q_free(struct list_head *l)
{
    if (!l)
        return; /* queue is NULL */
    element_t *del, *next;
    /* del, the element to be free. next, the next element of del */
    list_for_each_entry_safe (del, next, l, list) {
        list_del(&del->list);
        q_release_element(del);
    }
    free(l);
    return;
}
```
#### `q_insert_head`
若佇列是`NULL` 立刻回傳 false 。
用 `malloc` 取得 `element_t` 大小的記憶體。失敗回傳 false 。
用 `malloc` 取得 s 字串大小的記憶體。失敗釋放 e 的空間並回傳 false 。
用 `memcpy` 複製字串和 `INIT_LIST_HEAD()` 初始化新節點，再用 `list_add` 加入佇列最前端。
```c
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false; /* queue is NULL */
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL; /* could not allocate space */
    int len = strlen(s) + 1;
    e->value = malloc(sizeof(char) * len);
    if (!e->value) {
        free(e);
        return NULL; /* could not allocate space */
    }
    memcpy(e->value, s, len);
    INIT_LIST_HEAD(&e->list);
    list_add(&e->list, head);
    return true;
}
```
##### 更新：
用 `gen_element` 取代與 `q_insert_tail` 相同的程式。
```c
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head || !s)
        return false; /* queue is NULL or s is NULL*/
    element_t *e = gen_element(s);
    if (!e)
        return false;
    list_add(&e->list, head);
    return true;
}
```
#### `q_insert_tail`
大致與 `q_insert_head()` 相同。用 `list_add_tail()` 加入佇列尾端。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false; /* queue is NULL */
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL; /* could not allocate space */
    int len = strlen(s) + 1;
    e->value = malloc(sizeof(char) * len);
    if (!e->value) {
        free(e);
        return NULL; /* could not allocate space */
    }
    memcpy(e->value, s, len);
    INIT_LIST_HEAD(&e->list);
    list_add_tail(&e->list, head);
    return true;
}
```
##### 更新：
```c
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head || !s)
        return false; /* queue is NULL or s is NULL*/
    element_t *e = gen_element(s);
    if (!e)
        return false;
    list_add_tail(&e->list, head);
    return true;
}
```
##### `gen_element`
```c
element_t *gen_element(char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL; /* could not allocate space */
    int len = strlen(s) + 1;
    e->value = malloc(sizeof(char) * len);
    if (!e->value) {
        free(e);
        return NULL; /* could not allocate space */
    }
    memcpy(e->value, s, len);
    INIT_LIST_HEAD(&e->list);
    return e;
}
```
#### `q_remove_head`
若佇列為 `NULL` 或空，回傳 `NULL` 。
`list_first_entry()` 取得第一個節點位置， `list_del_init()` 移除該節點。
若 `sp` 不為 `NULL` ，複製節點的 `value` 到 `sp` 。
回傳該節點。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *e = list_first_entry(head, element_t, list);
    list_del_init(head->next);
    if (sp)
        memcpy(sp, e->value, strlen(e->value) + 1);
    return e;
}

```
#### `q_remove_tail`
用 `q_remove_head()` 實作，傳入 `head->prev->prev` ，其取得的節點便是 `head->prev` 。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return q_remove_head(head->prev->prev, sp, bufsize);
}
```
#### `q_size`
一開始檢查佇列是否為 `NULL` 或空。
使用 `list_for_each()` 走訪佇列，計算節點數量，並回傳。
```c
int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    struct list_head *node;
    int count = 0;
    list_for_each (node, head)
        ++count;
    return count;
}
```
#### `q_delete_mid`
> 根據[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)中的範例實作

一開始檢查佇列是否為 `NULL` 或空。

使用快慢指標找到中間的節點。
- `indir` 指標一個迴圈走到下個節點（一個節點）， `fast` 指標一個迴圈走到下下個節點（兩個節點)。
- 當 `fast = head` (q_size is even) 或 `fast->next = head` (q_size is odd) 時，fast 已走 n 個節點， `*indir` 指向第 $n/2$ 節點，即為中間的節點 (0-based indexing)。
    - 若 q_size = 6, `fast` 停在 5th 節點，`*indir` 指向 3th 節點 。
    - 若 q_size = 5, `fast` 停在 3th 節點，`*indir` 指向 2th 節點 。
- `list_del()` 移除要刪除的節點，用 `list_entry()` 找到節點位置，再釋放空間。
```c
bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head **indir = &head->next, *fast = head->next;
    for (; fast != head && fast->next != head; fast = fast->next->next)
        indir = &(*indir)->next;
    struct list_head *del_node = *indir;
    list_del_init(del_node);
    element_t *del_e = list_entry(del_node, element_t, list);
    q_release_element(del_e);
    return true;
}
```
#### `q_delete_dup`
若佇列為 `NULL` 回傳 `false` 。
用 `list_for_each_entry_safe()` ，因為它允許在走訪佇列時刪除節點。
- 若是 `str` 與 `node->value` 字串相同。移除 `node` 並釋放空間。否則將 `node->vale` 複製給 `str` ，成為下一個要比較的字串。
    - 因為使用此函式的佇列須為已排序好的狀態，有相同字串的節點一定相鄰。一旦發現下個節點字串不同，目前節點的字串便不會再後續出現，不須再比較。
- 經由迴圈，會將 n 個有相同字串的節點的後 n-1 個節點刪除，因為第一次偵測到存在相同字串 `str` 時，同時至少有兩個節點，前一個是更新 `str` 時走訪，目前的節點是發現重複字串且將被刪除的節點，後續重複節點也被走訪後刪除。
為了刪除第一個節點，再刪除目前節點後檢查 `str` 和 `next->value`，若是**不同**，表示重複的 n-1 個節點已被刪除完畢，此時 `next` 的前一個節點就是重複的第一個節點（兩節點之前的其他節點都被移除），用 `list_entry()` 取得該節點 `first_dup` ，移除並釋放空間。
- 變數
    - `str` 存目前比要對的字串。
    - `node` 目前的節點，可被 delete 。
    - `next` , `node` 的下一個節點。
    - `first_dup` ， n 個有相同字串的節點中的第一個節點。
```c
bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *first_dup, *node, *next;
    char *str = malloc(sizeof(char) * 1024);
    list_for_each_entry_safe (node, next, head, list) {
        if (strcmp(str, node->value) == 0) {
            list_del_init(&node->list);
            q_release_element(node);
            if (strcmp(str, next->value) != 0) {
                /* delete the frist node that have duplicate string */
                first_dup = list_entry(next->list.prev, element_t, list);
                list_del_init(&first_dup->list);
                q_release_element(first_dup);
            }
        } else {
            memcpy(str, node->value, strlen(node->value) + 1);
        }
    }
    free(str);
    return true;
}
```
改進：
將 `str` 指標指向目前比對的節點的 `value` ，取代原本的 `malloc` 和 `memcpy` ，減省記憶體空間。初始化則改為指向 `\0` 。
```c
bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *node, *next;
    char *str = "\0";
    list_for_each_entry_safe (node, next, head, list) {
        if (strcmp(str, node->value) == 0) {
            ...
            if (strcmp(str, next->value) != 0) {
                /* delete the frist node that have duplicate string */
                element_t *first_dup = list_entry(next->list.prev, element_t, list);
                list_del_init(&first_dup->list);
                q_release_element(first_dup);
                str = "\0";
            }
        } else {
            str = node->value;
        }
    }
    return true;
}
```
#### `q_swap`
若佇列為 `NULL` 、空，或只有一個節點，則回傳，不須 swap 。
根據 `list_for_each_safe` 迴圈，加上 `safe != head` 的條件，用來在節點為奇數時，剩下最後一個時停止迴圈。
交換節點位置：
- `safe` 後移一個節點，原本 `safe` 的位置為 `node->next` ， 交換 `node` 和 `node->next` 兩節點。
- 更新連接 `node->prev` 和 `node->next` 。
- 更新連接 `node` 和 `node->next` 。
- 更新連接 `node` 和 `safe` 。
```c
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *node, *safe;
    for (node = head->next, safe = node->next; node != head && safe != head;
         node = safe, safe = node->next) {
        safe = safe->next;
        node->prev->next = node->next;
        node->next->prev = node->prev;
        node->prev = node->next;
        node->next->next = node;
        safe->prev = node;
        node->next = safe;
    }
}
```
#### `q_reverse`
確認佇列是否為 `NULL` 或空。
用 `list_for_each_safe` 走訪節點，交換 `node` 的兩個指標 `node->prev` `node-。next` 指向的位址。因為 `list_for_each_safe` 是從第一個節點開始，迴圈結束後交換 `head` 的兩個指標 `prev` `next` 指向的位址（此時 `node == head`）。

```c
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *node, *next;
    list_for_each_safe(node, next, head) {
        node->next = node->prev;
        node->prev = next;
    }
    node->next = node->prev;
    node->prev = next;
    return;
}
```
#### `q_sort`
若佇列為 `NULL` 、空或只有一個節點，則不做排序。
根據 Quick sort 實作排序，將傳入的第一個節點 `head` 當作比較的基準值，數值小的節點移動到 `head` 前，數值相同或大於則維持原位。再用遞迴繼續排序 `head` 的左右子佇列。 
用 `prev` 和 `next` 兩個指標的指標操作。
- 立即回傳，不做迴圈
    - `tail->next == head` 表示上一層遞迴後左子佇列或右佇列為空。
    - `head == tail` 表示上一層遞迴後左子佇列或右佇列只有移的節點。
- 迴圈
    - 初始 `prev` `next` 都指向 `head` 。
    - 若 `*next->next` `value` 小於 `head` `value` ，移到 `*prev` 節點的前面，然後 `prev` 指標指向該節點。
    - 否則（`*next->next` `value` 大於等於 `head` `value`）， `next` 指向下一個節點。
    - 若 `*next == tail` （`*prev == tail`） 表示此子佇列已比較完所有節點且最後一個節點大於等於（小於）`head` 。
- 遞迴呼叫
    - `prev` 和 `next` 再比較後都會指向比較後的節點，因此分別作為左子佇列的 `head` 和右子佇列 `tail` 。
```c
void sort(struct list_head *head, struct list_head *tail)
{
    if (tail->next == head || head == tail)
        return;
    struct list_head **prev = &head, **next = &head;
    char *head_str = list_entry(head, element_t, list)->value;
    for (; (*next) != tail && (*prev) != tail;) {
        char *str = list_entry((*next)->next, element_t, list)->value;
        if (strcmp(str, head_str) < 0) {
            (*prev)->prev->next = (*next)->next;
            (*next)->next->prev = (*prev)->prev;
            (*prev)->prev = (*next)->next;
            (*next)->next = (*next)->next->next;
            (*next)->next->prev = *next;
            (*prev)->prev->next = *prev;
            prev = &(*prev)->prev;
        } else {
            next = &(*next)->next;
        }
    }
    sort(*prev, head->prev);
    sort(head->next, *next);
    return;
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    sort(head->next, head->prev);
}
```

## 參考資訊
- 共筆格式參考：[共筆示範](https://hackmd.io/@cccccs100203/linux2020-lab0)