---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `zxcj04` >
> [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
## 實驗環境
```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: 43 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: AuthenticAMD
CPU family: 23
Model: 1
Model name: AMD Ryzen 5 1600 Six-Core Processor
Stepping: 1
Frequency boost: enabled
CPU MHz: 1377.939
CPU max MHz: 3200.0000
CPU min MHz: 1550.0000
BogoMIPS: 6387.35
Virtualization: AMD-V
L1d cache: 192 KiB
L1i cache: 384 KiB
L2 cache: 3 MiB
L3 cache: 16 MiB
NUMA node0 CPU(s): 0-11
```
## 開發紀錄
### q_new
```c
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
逐一走訪鏈結串列的節點前，先檢查輸入的指標是否有效。
由於涉及到 list entry 的 delete 以及 node 的 remove 因此使用`list_for_each_entry_safe`
一開始忽略了 entry 中的 value 也需要 free 所以卡了一陣子。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
free(entry->value);
free(entry);
}
free(l);
}
```
### q_insert_head
對 Linux 核心風格的 circular doubly-linked list 不夠熟悉。看了〈[你所不知道的 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 核心風格 API 的程式碼是在參考了 [@jasperlin1996-q_insert_head](https://hackmd.io/@jasperlin1996/linux2022-lab0#q_insert_head) 的方法後寫出來。
```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;
size_t len = strlen(s) + 1;
node->value = (char *) malloc(sizeof(char) * len);
if (!node->value) {
free(node);
return false;
}
strncpy(node->value, s, len);
LIST_HEAD(list);
node->list = list;
list_add(&node->list, head);
return true;
}
```
### q_remove_head
逐一走訪鏈結串列的節點前，先檢查輸入的指標是否有效以及串列中是否存在節點。
使用 `strnlen` 以確保即將被複製的字串長度為 bufsize
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *del_entry = list_first_entry(head, element_t, list);
size_t len = strnlen(del_entry->value, bufsize - 1) + 1;
strncpy(sp, del_entry->value, len);
list_del(&del_entry->list);
return del_entry;
}
```
後來發現不需要使用 `strnlen` 來檢查長度
只要用 `strncpy` 並在字串結尾補上 `\0` 即可
(參考 @laneser 及 @japerlin1996 的筆記)
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *del_entry = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, del_entry->value, bufsize);
sp[bufsize - 1] = '\0';
}
list_del(&del_entry->list);
return del_entry;
}
```
### q_remove_tail
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *del_entry = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, del_entry->value, bufsize);
sp[bufsize - 1] = '\0';
}
list_del(&del_entry->list);
return del_entry;
}
```
### q_delete_mid
使用了 〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉中的快慢指標技巧找到中間的節點，並從串列中刪除後釋放記憶體。
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *slow = head->next, *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
### q_swap
這邊我原本是先取的要交換的兩個節點，並且去調整前後節點的 next 以及 prev 來完成交換。
但覺得不太優雅，因此在參考了 @laneser 的作法後發現實際上是作一樣的動作，但可以利用 Linux 核心風格 API 來簡化程式碼。
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *now;
for (now = head->next; now != head && now->next != head; now = now->next) {
struct list_head *next = now->next;
list_del(now);
list_add(now, next);
}
}
```
### q_delete_dup
一開始誤會題意，以為是要把重複的留下一個，仔細看過後發現要把所有重複的節點都刪掉會有點麻煩，嘗試過用一個 flag 來辨別，也試過用另一個字串來紀錄重複的字串，最後還是選擇使用 flag 的方式，會繼續思考有沒有辦法簡化現在的程式碼。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
if (list_empty(head) || list_is_singular(head))
return true;
element_t *now, *next;
bool is_dup = false;
list_for_each_entry_safe (now, next, head, list) {
if (now->list.next != head && strcmp(now->value, next->value) == 0) {
list_del(&now->list);
q_release_element(now);
is_dup = true;
} else if (is_dup) {
list_del(&now->list);
q_release_element(now);
is_dup = false;
}
}
return true;
}
```
### q_reverse
逐一走訪鏈結串列的節點，將所有節點的 next 及 prev 交換。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *now = head;
do {
struct list_head *tmp = now->next;
now->next = now->prev;
now->prev = tmp;
now = now->next;
} while (now != head);
}
```
### q_sort
使用了我比較熟悉的 merge sort 來實作，但其中要去確保節點的 next 及 prev 都是正確的讓程式碼多了很多不優雅的部份。
參考了 @laneser 的方法之後豁然開朗，原來可以在一開始斷開 head 的 prev ，然後直接當成 singly-linked list 來做，最後再重建 prev。
目前這個版本在 make test 的 trace-14-perf 會不通過。
```c
struct list_head *merge_sorted(struct list_head *list1, struct list_head *list2)
{
if (!list1)
return list2;
if (!list2)
return list1;
element_t *cmp1 = list_entry(list1, element_t, list);
element_t *cmp2 = list_entry(list2, element_t, list);
if (strcmp(cmp1->value, cmp2->value) <= 0) {
list1->next = merge_sorted(list1->next, list2);
return list1;
} else {
list2->next = merge_sorted(list1, list2->next);
return list2;
}
}
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
return merge_sorted(merge_sort(head), merge_sort(fast));
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *list = head->next;
head->prev->next = NULL;
list = merge_sort(list);
head->next = list;
// rebuild prev link
struct list_head *i = head;
while (i->next != NULL) {
i->next->prev = i;
i = i->next;
}
head->prev = i;
i->next = head;
}
```
將 merge_sorted 中的遞迴改成疊代後終於通過測試了。
```c
struct list_head *merge_sorted(struct list_head *list1, struct list_head *list2)
{
struct list_head *result = NULL, *now = result;
while (true) {
element_t *cmp1 = list_entry(list1, element_t, list);
element_t *cmp2 = list_entry(list2, element_t, list);
if (strcmp(cmp1->value, cmp2->value) <= 0) {
if (result == NULL) {
result = list1;
now = result;
} else {
now->next = list1;
now = now->next;
}
list1 = list1->next;
if (!list1) {
now->next = list2;
break;
}
} else {
if (result == NULL) {
result = list2;
now = result;
} else {
now->next = list2;
now = now->next;
}
list2 = list2->next;
if (!list2) {
now->next = list1;
break;
}
}
}
return result;
}
```
## 在 qtest 提供新的命令 shuffle
在 qtest.c 的 `console_init` 中加入
```c
ADD_COMMAND(shuffle, " | Shuffle queue");
```
並實作 `do_shuffle` 函式
```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();
srand((unsigned int) (time(NULL)));
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
在 queue.h 及 queue.c 中加入 `q_shuffle` 的定義並實作
```c
void swap_node(struct list_head *node1, struct list_head *node2)
{
struct list_head *tmp = node1->prev;
list_move(node1, node2);
list_move(node2, tmp);
}
struct list_head *list_idx(struct list_head *head, int idx)
{
do {
head = head->next;
} while (idx--);
return head;
}
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int len = q_size(head);
for (int i = len - 1; i > 0; i--) {
int idx = rand() % (i + 1);
swap_node(list_idx(head, idx), list_idx(head, i));
}
}
```
結果發現因為修改到了 queue.h ，所以在 git commit 的時候會被擋下來，因此放棄在 queue.c 中實作，改為直接將 `q_shuffle` 放在 qtest.c 中。
Sign in with Wallet
Connect another wallet