# 2022q1 Homework1 (lab0)
contributed by < `ibat10clw` >
> [lab0-c](https://github.com/ibat10clw/lab0-c)
###### tags: `linux2022`
## 實驗環境
```shell
$ gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 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
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
Stepping: 3
CPU MHz: 1200.000
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 7183.16
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
Vulnerability Itlb multihit: KVM: Mitigation: VMX disabled
Vulnerability L1tf: Mitigation; PTE Inversion; VMX conditional cach
e flushes, SMT vulnerable
Vulnerability Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Vulnerability Meltdown: Mitigation; PTI
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled v
ia prctl and seccomp
Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user
pointer sanitization
Vulnerability Spectre v2: Mitigation; Full generic retpoline, IBPB condit
ional, IBRS_FW, STIBP conditional, RSB filling
Vulnerability Srbds: Mitigation; Microcode
Vulnerability Tsx async abort: Not affected
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtr
r pge mca cmov pat pse36 clflush dts acpi mmx f
xsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rd
tscp lm constant_tsc arch_perfmon pebs bts rep_
good nopl xtopology nonstop_tsc cpuid aperfmper
f pni pclmulqdq dtes64 monitor ds_cpl vmx smx e
st tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_
1 sse4_2 x2apic movbe popcnt tsc_deadline_timer
aes xsave avx f16c rdrand lahf_lm abm cpuid_fa
ult epb invpcid_single pti ssbd ibrs ibpb stibp
tpr_shadow vnmi flexpriority ept vpid ept_ad f
sgsbase tsc_adjust bmi1 avx2 smep bmi2 erms inv
pcid xsaveopt dtherm ida arat pln pts md_clear
flush_l1d
```
## 作業要求
> [lab0](https://hackmd.io/@sysprog/linux2022-lab0)
* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
* q_new: 建立一個新的 queue 並將 head 的指標初始化
* q_free: 釋放目前 queue 中的所有元素
* q_insert_head: 在 head 插入一個新元素
* q_insert_tail: 在 tail 插入一個新元素
* q_remove_head: 移除 head 端的元素
* q_remove_tail: 移除 tail 端的元素
* q_size: 計算 queue 的長度
* q_delete_mid: 刪除 queue 中間的元素(⌊q_size / 2⌋)
* q_delete_dup: 刪除 queue 所有重複的元素
* q_swap: 將 queue 中相鄰的元素交換位置
* q_reverse: 將 queue 的順序反轉
* q_sort: 將 queue 中的元素以字典序做排序
## 開發紀錄
### q_new
最一開始沒有去判斷當 malloc 失敗的時候要有例外處理, 到了執行評分程式時才注意到, 後面如果有需要做 malloc 的部份也都需要檢查回傳的結果是否成功
INIT_LIST_HEAD 的作用是將 head->prev 和 head->next 指向自己
```c=
struct list_head *q_new()
{
// allocate a space of list_head
struct list_head *q = (struct list_head *) malloc(sizeof(struct list_head));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
### q_free
根據[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)中提到在 linux 中的 list 會把 list_head 嵌入到所需的結構體中, 但傳入的參數是 list_head, 因此需要透過 list_head 去找到 element_t 才能夠真正的去釋放記憶體
此外 element_t 中的 value 是一個指標, 也需要將其指向的記憶體空間收回
```c
void q_free(struct list_head *l) {
if (!l)
return;
element_t *previous, *current;
list_for_each_entry_safe (current, previous, l, list) {
free(current->value);
free(current);
}
free(l);
}
```
### q_insert_head
在插入的部份有兩個地方需要用到 malloc, 分別是 node 本身和 node 要存的value
由於 value 的部份是字串, 需要計算它的長度後再進行分配, 要是失敗的話則要先把前面 malloc 的node 釋放掉才能 return, 當 data 都準備好後只要將其接在 head 的next就好
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = (element_t *) malloc(sizeof(element_t));
if (!node)
return false;
unsigned int len = strlen(s) + 1;
node->value = malloc(sizeof(char) * len);
if (!node->value) {
free(node);
return false;
}
memcpy(node->value, s, len);
list_add(&node->list, head);
return true;
}
```
### q_insert_tail
由於是 circular doubly linked list, 因此能夠參考 insert head 的部份, 只有最後要改為將 data 接在 head 的 prev 就可以了
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = (element_t *) malloc(sizeof(element_t));
if (!node)
return false;
unsigned int len = strlen(s) + 1;
node->value = malloc(sizeof(char) * len);
if (!node->value) {
free(node);
return false;
}
memcpy(node->value, s, len);
list_add_tail(&node->list, head);
return true;
}
```
### q_remove_head
根據作業要求除了要將 node 移出 list 以外, 當傳入的 sp 不是空指標時要將 data 複製進去
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
element_t *node = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(head->next);
return node;
}
```
### q_remove_tail
跟 remove_head 做比較, 差別只有移除的 node 從 head->next 改為 head->prev
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
element_t *node = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(head->prev);
return node;
}
```
### q_size
透過走訪整個 list 後來計算 list 的長度
```c
int q_size(struct list_head *head)
{
if (!head || head == head->next)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_delete_mid
這邊的關鍵在於如何找出位於中間的 node
我使用了 slow 和 fast 的指標來走訪 list, 兩個指標的移動速度剛好差一倍, 所以當 fast 繞了一圈後 slow恰好會在 list 中間, 找到之後將其刪除(除了移出 list 外, 記憶體也要收回)
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || head->next == head)
return false;
struct list_head *fast = head;
struct list_head *slow = head;
do {
fast = fast->next->next;
slow = slow->next;
} while (fast->next != head && fast != head);
element_t *target = list_entry(slow, element_t, list);
list_del(slow);
free(target->value);
free(target);
return true;
}
```
### q_delete_dup
由於只會作用在 sorted list , 我用了一個 current 的指標, 並且會在每個 node 都向後看, 只要發現重複就將開始刪除, 直到 current->next 和 current 不相等後再把 current 刪除, 並且往更新過後的 list 的下一個 node 前進
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || head->next == head)
return false;
struct list_head *current = head->next;
char tag;
while (current != head) {
element_t *node = list_entry(current, element_t, list);
while (current->next != head &&
!strcmp(node->value,
list_entry(current->next, element_t, list)->value)) {
tag = 1;
element_t *del_node = list_entry(current->next, element_t, list);
list_del(current->next);
free(del_node->value);
free(del_node);
}
if (tag) {
tag = 0;
element_t *del_node = list_entry(current, element_t, list);
struct list_head *tmp = current->next;
list_del(current);
free(del_node->value);
free(del_node);
current = tmp;
} else
current = current->next;
}
return true;
}
```
### q_swap
這裡採用比較直覺的作法, 交換兩個 node 共會影響 6 個 link 把他們全部轉向即可
由於 while 的判斷, 當 current 走回 head 的時候就會停止, 不過若 q_size 為偶數, 則最後一個 node 也會被調整, 最後的 if 是為了在此情形中調整 head 的 link
```c
void q_swap(struct list_head *head)
{
struct list_head *current = head->next, *previous = head, *tmp = NULL;
while (current != head && current->next != head) {
tmp = previous;
previous = current;
current = current->next;
previous->next = current->next;
current->next = previous;
current->prev = previous->prev;
previous->prev = current;
tmp->next = current;
previous->next->prev = previous;
current = previous->next;
}
if (current->next != head) {
previous->next = head;
head->prev = previous;
}
}
```
### q_reverse
由於 head 是不帶 data 的, 因此要反轉 list 只需要將 所有 node 的 next 和 prev 做交換即可
指標 tmp 用於輔助交換, 當交換完成後原先的 next 的方向會變成存在 prev 內, 因此透過 prev 來移動 current
```c
void q_reverse(struct list_head *head)
{
if (!head || head == head->next || list_is_singular(head))
return;
struct list_head *tmp;
struct list_head *current = head->next;
while (current != head) {
tmp = current->prev;
current->prev = current->next;
current->next = tmp;
current = current->prev;
}
tmp = head->prev;
head->prev = head->next;
head->next = tmp;
}
```
### q_sort
這邊採用了遞迴的 merge sort來實作, 並且在排序的過程中先忽視 prev 的存在, 同時將 circular 的結構破壞, 等待排序完畢後再透過 next 的順序去恢復成 doubly circular linked list
merge sort 共有兩大重點, 分別是:
1. 分割
在分割的部份我採用了 slow 和 fast 的指標來找尋 list 的中間節點, 找到後將中間節點的 next 指向 NULL, 直到所有 sub list 的 size 都小於等於 1 為止
1. 合併
合併的部份採用的方式是老師[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)中介紹的 merge two sorted list 的方法
當 sorting 完成後, 把 prev 的 link 連回去, 然後把 last node 與 head 的連結也恢復後就完成了
```c
struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; l1 && l2; *node = (*node)->next) {
node = strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) < 0
? &l1
: &l2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = l1 ? l1 : l2;
return head;
}
struct list_head *mergesort(struct list_head *head)
{
if (!head->next) {
return head;
}
struct list_head *fast = head;
struct list_head *slow = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *left = mergesort(head);
struct list_head *right = mergesort(mid);
return merge(left, right);
}
void q_sort(struct list_head *head)
{
if (!head || head->next == head || list_is_singular(head))
return;
struct list_head *tmp = head->next;
head->prev->next = NULL;
head->next = NULL;
struct list_head *sorted = mergesort(tmp);
struct list_head *current = sorted;
struct list_head *previous = 0;
while (current) {
previous = current;
current = current->next;
if (current)
current->prev = previous;
}
sorted->prev = head;
head->next = sorted;
head->prev = previous;
previous->next = head;
}
```
### 在 qtest 提供新的命令 shuffle
目前已經在 queue.c 中完成了 shuffle 的程式碼
先建立一個 newh 來輔助洗牌
每個回合會從原 list 中隨機選一個 node 移除, 並且 insert 在 newh 的 head
當所有元素都以新的順序被串在 newh 後, 之後再將 newh, first node, last node 的 link 串回原先的 head
便完成了洗牌的操作
```c
static bool q_shuffle(struct list_head *head)
{
if(!head || list_empty(head))
return false;
else if(list_is_singular(head))
return true;
int len = 0;
struct list_head *li;
struct list_head newh;
newh.next = &newh;
newh.prev = &newh;
list_for_each (li, head)
len++;
srand(time(NULL));
while (len) {
int node_num = (rand() % len) + 1;
li = head;
do {
li = li->next;
} while (--node_num);
struct list_head *tmp = li;
list_del(li);
list_add(tmp, &newh);
len--;
}
newh.next->prev = head;
newh.prev->next = head;
head->next = newh.next;
head->prev = newh.prev;
return true;
}
```
接下來要將功能與 qtest 做結合
在閱讀了作業要求中, 如何新增 do_hello 的方法後, 已經有成功新增 hello 命令
同時在 qtest.c 中找到了 do_show 的實作, 打算模仿此方法將 shuffle 的命令加入 qtest 中
最後我仿照了 do_dm 將 shuffle 的功能加入了 qtest
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Try to access null queue");
error_check();
bool ok = true;
if (exception_setup(true))
ok = q_shuffle(l_meta.l);
exception_cancel();
show_queue(3);
return ok && !error_check();
}
```
## TODO
### trace-17-complexity
我的程式碼在 github 的 CI 有時後會失敗, 但在自己的電腦上測試從 insert, remove, free 這三個部份做完後就一直是通過的狀態, 需要進一步釐清原因
### 部份程式碼改進
與觀摩區的作業比較後認為我的程式碼應該需要多使用 list.h 提供的 API 去改寫, 但有些 macro 還不是很理解, 等待理解後在將他們改進
## 參考資料
* [Reverse a doubly circular linked list](https://www.geeksforgeeks.org/reverse-a-doubly-circular-linked-list/)
*
Sign in with Wallet
Connect another wallet