---
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)
Sign in with Wallet
Connect another wallet