---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `Chao-Shun-Cheng` >
## 實驗環境
```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): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
Stepping: 10
CPU MHz: 3700.000
CPU max MHz: 4700.0000
CPU min MHz: 800.0000
BogoMIPS: 7399.70
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
## 作業要求
* `q_new` : 建立新的「空」佇列
* `q_free` : 釋放佇列所佔用的記憶體
* `q_insert_head` : 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
* `q_insert_tail` : 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
* `q_remove_head` : 在佇列開頭 (head) 移去 (remove) 給定的節點
* `q_release_element` : 釋放特定節點的記憶體空間
* `q_size` : 計算目前佇列的節點總量
* `q_delete_mid` : 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
* `q_delete_dup` : 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* `q_swap` : 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
* `q_reverse` : 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
* `q_sort` : 以遞增順序來排序鏈結串列的節點
## 開發過程
### `queue.c` 實作
#### `queue` 資料結構
從 `queue.h` 當中的 `element_t` 可以知道 Node 的資料結構包含一個 `value` 與 `list` 。其中 `value` 會指向一個字串，另外 `list` 則是會定義在 `list.h` 裡的一種資料結構。可以看到 `list` 有兩個指標分別指向下一個與上一個 Node 的 `list`。
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
完整的 `queue` 資料結構如下圖所示。
#### `q_new`
`new` 需要先透過 `malloc` 進行記憶體配置，再透過 `list.h` 所提供的 `INIT_LIST_HEAD` 去進行初始化。
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head) {
INIT_LIST_HEAD(head);
return head;
} else {
return NULL;
}
}
```
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
#### `q_free`
首先要判斷 `queue` 裡面是否存在節點，可以利用 `list.h` 提供的 `list_empty` 去判斷。如果有 Node 再利用 `list_first_entry` 去得到指向包含這個 `list` 的 `element`。最後再利用 `q_release_element` 去釋放 Node 的記憶體。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
while (!list_empty(l)) {
element_t *target = list_first_entry(l, element_t, list);
list_del(l->next);
q_release_element(target);
}
free(l);
}
```
其中 `list_first_entry` 是利用 `container_of` 去獲得 Node 的記憶體位置，詳細使用方法與原理可以參考 [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)。
#### `q_insert_head`
首先要先利用 `malloc` 去分配 Node 所需要的記憶體空間，再去分配 `value ` 所需要的空間，最後再利用 `list.h` 所提供的 `list_add` 將 Node 插入 `queue` 當中。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *newh = malloc(sizeof(element_t));
if (!newh)
return false;
int len = strlen(s);
newh->value = malloc(sizeof(char) * (len + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len + 1);
list_add(&newh->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;
element_t *newh = malloc(sizeof(element_t));
if (!newh)
return false;
int len = strlen(s);
newh->value = malloc(sizeof(char) * (len + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len + 1);
list_add_tail(&newh->list, head);
return true;
}
```
#### `q_remove_head`
首先透過 `list_first_entry` 去獲得指向第一個 Node 的指標，再透過 `list_del` 去將 Node 移出 `queue`。需要特別注意的是 `value` 與 `bufsize` 的大小，以及結尾字元 `\0`。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head) || !sp)
return NULL;
element_t *target = list_first_entry(head, element_t, list);
list_del(head->next);
int len = strlen(target->value);
if (len > (bufsize - 1)) {
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strncpy(sp, target->value, len);
sp[len] = '\0';
}
return target;
}
```
#### `q_remove_tail`
與 `q_remove_head` 雷同，不過是透過 `list_last_entry` 去獲得指向最後一個 Node 的指標。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head) || !sp)
return NULL;
element_t *target = list_last_entry(head, element_t, list);
list_del(head->prev);
int len = strlen(target->value);
if (len > (bufsize - 1)) {
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strncpy(sp, target->value, len);
sp[len] = '\0';
}
return target;
}
```
#### `q_size`
這邊是直接用 `list_for_each` 走訪全部節點以計算數量。還在思考如何降低計算時間。
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
struct list_head *node = NULL;
int size = 0;
list_for_each (node, head) {
size++;
}
return size;
}
```
#### `q_delete_mid`
宣告兩個指標 `next_node` 與 `prev_node` 用 `while` 分別從 `queue` 的前與後去走，當 `prev_node == next_node` 或 `next_node->next == prev_node` 就代表找到中間的 Node 了。
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *next_node = head->next, *prev_node = head->prev;
while (next_node != prev_node && next_node->next != prev_node) {
next_node = next_node->next;
prev_node = prev_node->prev;
}
element_t *target = list_entry(prev_node, element_t, list);
list_del(prev_node);
q_release_element(target);
return true;
}
```
#### `q_delete_dup`
這題主要是參考 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 這題的內容來實作，不過在原題目中是有重複的要<font color=red>***全部 delete***</font> ，因此我透過 `list_for_each_safe` 去看每個 Node 的值，並將值用 `value` 指標指著，再透過`strcmp(value, target->value) == 0` 來去判斷鄰近的 `Value` 是不是一樣，是的話就 `delete` ，直到遇到不一樣為止。
##### ***Case one : 沒有遇到相同***
`value` 直接可以指到下一個值
##### ***Case two : 有遇到相同***
`delete` 後面重複出現的之後，還要再<font color=red>***刪掉自己本身***</font>
`Version one`
考慮刪掉自己本身的 Node ，但發現 `trace-06` 一直過不了。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
struct list_head *node = NULL, *safe = NULL;
bool dup = false;
char *value = NULL;
element_t *target = NULL;
list_for_each_safe (node, safe, head) {
target = list_entry(node, element_t, list);
if (strcmp(value, target->value) == 0) { // duplicates
list_del(node);
q_release_element(target);
dup = true;
} else {
value = target->value;
if (dup) {
target = list_entry(node->prev, element_t, list);
list_del(node->prev);
q_release_element(target);
dup = false;
}
}
}
return true;
}
```
`Version two`
於是嘗試不刪掉自己本身，指刪掉後面一樣的 Node ，竟然神奇的過了。不確定是不是我對題目有誤解還是有甚麼 Bug 。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return false;
bool dup = false;
char *value = NULL;
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
if (value && strcmp(value, entry->value) == 0) {
list_del(&entry->list);
q_release_element(entry);
dup = true;
} else {
value = entry->value;
if (dup) {
// target = list_entry(entry->list.prev, element_t, list);
// list_del(&target->list);
// q_release_element(target);
dup = false;
}
}
}
return true;
}
```
#### `q_swap`
`swap` 這邊是利用 `from` 與 `to` 兩個指標分別去紀錄要 `swap` 兩個 Node 的前後關係，再透過 `while` 去把所有需要 `swap` 的 Node 進行相關的指標替換即可。
```c
void q_swap(struct list_head *head)
{
if (!head || list_is_singular(head))
return;
struct list_head *node = head->next, *from = NULL, *to = NULL, *next = NULL;
while ((node != head) && (node->next != head)) {
next = node->next;
from = node->prev;
to = node->next->next;
from->next = next;
next->prev = from;
next->next = node;
node->prev = next;
node->next = to;
to->prev = node;
node = to;
}
}
```
#### `q_reverse`
這邊的想法是直接將 `prev` 與 `next` 兩個指標的內容交換即可。因此直接透過 `list_for_each_safe` 去把每個 Node 裡的 `prev` 與 `next` 內容交換。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node = NULL, *safe = NULL, *temp = NULL;
list_for_each_safe (node, safe, head) {
temp = node->next;
node->next = node->prev;
node->prev = temp;
}
temp = head->next;
head->next = head->prev;
head->prev = temp;
}
```
#### `q_sort`
這邊是利用 mergesort 下去進行排序，並透過 `LIST_HEAD` 將變數放在 `stack` 裡，就不用特別去思考如何釋放記憶體的議題。雖然測資可以通過，但當我要 `git commit` 時發現，`queue.h` 不能修改。會去研讀 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並進一步思考如何修改。
:::info
後來發現將 `Function` 放在 `q_sort` 上面就可以直接使用，不用特別在宣告在 `queue.h` 裡面，總算可以順利 git commit 了。
:::
mergesort 主要有兩個重點，分別是將 `list` 切開以及合併，合併這邊參考 [LeetCode 21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/) 的思考下去實作。
```c
void mergetwolist(struct list_head *head1,
struct list_head *head2,
struct list_head *head)
{
if (!head || !head1 || !head2 || (list_empty(head1) && list_empty(head2)))
return;
if (list_empty(head1)) {
list_splice_tail_init(head2, head);
return;
}
if (list_empty(head2)) {
list_splice_tail_init(head1, head);
return;
}
struct list_head *temp = NULL, *l1 = head1->next, *l2 = head2->next;
while (l1 != head1 && l2 != head2) {
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) > 0) {
temp = l2;
l2 = l2->next;
list_move_tail(temp, head);
} else {
temp = l1;
l1 = l1->next;
list_move_tail(temp, head);
}
}
list_splice_tail_init(head1, head);
list_splice_tail_init(head2, head);
}
```
切分的部分則是利用區域變數的特性，離開函式會自動釋放記憶體的優勢，來去進行實作。
```c
void mergesort(struct list_head *head, int size)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
LIST_HEAD(head1);
LIST_HEAD(head2);
int mid = size >> 1, count = 0;
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head) {
count++;
if (count == mid) {
list_cut_position(&head1, head, node);
list_splice_tail_init(head, &head2);
break;
}
}
mergesort(&head1, mid);
mergesort(&head2, size - mid);
mergetwolist(&head1, &head2, head);
}
```
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
mergesort(head, q_size(head));
}
```
#### `make test` 自動評分
```c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, and sort
--- trace-06-ops 6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
--- trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
花了一些時間與參考許多同學的實作方式，總算是看到皮卡丘了 QAQ
:::danger
文字訊息不要用螢幕截圖展現，你的讀者可能是視障朋友，而且圖片無助於資料檢索。
:notes: jserv
:::
:::info
已經修正，感謝老師提醒
:::
Sign in with Wallet
Connect another wallet