---
title: 2023q1 Homework1 (lab0)
tags: Linux核心實作
---
# 2023q1 Homework1 (lab0)
contributed by < [`lorian0738`](https://github.com/lorian0738) >
### Reviewed by `zeddyuu`
* 開發過程中的編譯器不應該是 Visual Studio Code，應該是整合開發環境
* 有些函式只有部份程式碼，建議可以貼上整段的程式碼再開始說明會比較完整且可讀
* 快慢指標用圖片說明很好，但建議可以用 Graphviz
* 完整說明改善程式碼前後的想法差異，很棒
* 一些部份尚未完成，像洗牌操作以及論文閱讀等等
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 4200.0000
CPU min MHz: 800.0000
BogoMIPS: 7200.00
```
## 開發過程
### 前置作業
#### 檢查 Linux 版本
原本想用 `lsb_release` 檢查，但是我裝的版本沒有這個指令
因此改用 `cat /etc/*-release`
得 `VERSION_ID="22.04"` 確認符合作業需求
#### github 設定
參照 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fgit-with-github#Git-%E6%95%99%E5%AD%B8%E5%92%8C-GitHub-%E8%A8%AD%E5%AE%9A%E6%8C%87%E5%BC%95) 建立 GitHub 帳號與產生 SSH key
建立完公鑰下指令 `clip < ~/.ssh/id_rsa.pub` 時沒有這個指令
於是用 `sudo apt install geomview` 下載
然而還是無法取得公鑰
最後輸入 `cat ~/.ssh/id_rsa.pub` 再複製
(註：
`git commit -a` 將所有改過的 ~~push 到 GitHub 上~~ commit 出去建立一個新的 git 版本
`git log` 看曾經 ~~push~~ commit 過的情況
也可以用 `tig` 看更詳細的
最後用 `git push -u origin master` push 到 Github 上）
#### 檢查 cppcheck 版本
指令：`cppcheck --version`
確認 Cppcheck 2.7 符合規定
#### 取得程式碼
至 [lab0-c](https://github.com/sysprog21/lab0-c) fork 到自己的GitHub
再照要求 clone 下來 `git clone git@github.com:lorian0738/lab0-c`
#### 編譯器
使用 Visual studio Code
### q_new
> 建立新的「空」佇列
先要 list_head 的空間，如果沒有要到就 return 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;
}
```
### q_free
> 釋放佇列所佔用的記憶體
判斷若為 NULL 則直接 return，若為 empty則釋放 list_head 佔用的空間
否則利用 `list_for_each_entry_safe` 和 `q_release_element` 逐一釋放每個 node 佔用的空間
最後要記得把 head 的空間也釋放掉
```c
void q_free(struct list_head *l)
{
if (!l)
return;
if (list_empty(l)) {
free(l);
return;
}
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
}
```
### q_insert_head
> 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
原本的寫法：
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *entry = (element_t *) malloc(sizeof(element_t));
if (!entry)
return false;
entry->value = s;
list_add(&entry->list, head);
return true;
}
```
但發現忘記應該要先複製要加入的字串，否則原本的資料更動的時候會動到entry中儲存的資料，改寫成：
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *element = (element_t *) malloc(sizeof(element_t));
char *tmp = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (!element || !tmp)
return false;
strncpy(tmp, s, strlen(s) + 1);
element->value = tmp;
list_add(&element->list, head);
return true;
}
```
其中直接用 `strncpy` 複製可確保複製到 buffer 可容納大小且自動在結尾補上 '\0'
後來發現應該要在一開始檢查 queue 是否為 NULL ，因此在最前面補上
```c
if (head == NULL)
return false;
```
且在 make test 時發現有 malloc 的錯誤，檢查後發現目前的程式有可能在要 element_t 的空間時有要到，但是在要字串的空間時失敗回傳false，前面要的空間應該要被釋放掉，應分開判斷是否有要到空間改為如下：
```c
if (!element)
return false;
if (!tmp) {
free(element);
return false;
}
```
此步將原本 `7 blocks are still allocated` 降為 4 ( insert_tail 的部份從 9 降到 4 )，但還是有空間沒有釋放，才想到也有可能是前面 element_t 就沒有要到空間了，但繼續做下去才檢查的話有可能後面的字串有要到空間，這時候就會沒有釋放到字串的空間，因此應該換個順序：
```c
element_t *element = (element_t *) malloc(sizeof(element_t));
if (!element)
return false;
char *tmp = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (!tmp) {
free(element);
return false;
}
```
才解決這個問題
:::info
在 commit 的時候原本想寫 Fix malloc failure on insert_head and insert_tail
但 malloc 不合法，必須寫完整的 memory allocation 才可以
改完後超過上限 50 個 characters
因此最後提交 Fix memory allocation failure on insert
:::
### q_insert_tail
> 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
和 q_insert_head 差不多，差別在於最後以 `list_add_tail` 加到最後
```c
list_add_tail(&element->list, head);
```
### q_remove_head
> 在佇列開頭 (head) 移去 (remove) 給定的節點
在 queue.h 的檔案中：
```
* @head: header of queue
* @sp: string would be inserted
* @bufsize: size of the string
*
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
```
第二行有點看不懂 sp 是什麼，註解和前面做 insert 時的 s 一樣，但這裡應該沒有要將字串插入，所以有點困惑
但第五行的意思推測是要將移除的字串複製過去
```
Return: the pointer to element, %NULL if queue is NULL or empty
```
首先判斷 queue 是否為 NULL 或空
```c
if (!head || list_empty(head))
return NULL;
```
接著用 `list_first_entry` 取出開頭的 entry，
並用 `list_del` 移走該點
```c
element_t *element = (element_t *) malloc(sizeof(element_t));
element = list_first_entry(head, element_t, list);
list_del(head->next);
```
最後判斷 sp 是否不是 NULL 以做複製，再回傳 element
```c
if (sp != NULL) {
strncpy(sp, element->value, bufsize -1);
sp[bufsize - 1] = '\0';
}
return element;
```
但後來發現其實 `list_del` 不會釋放空間，取出開頭時不需要要一個新的空間，應該直接寫成以下就好
```c
element_t *element = list_first_entry(head, element_t, list);
```
### q_remove_tail
> 在佇列尾端 (tail) 移去 (remove) 給定的節點
作法和 `remove_head` 差不多，僅改用 `list_last_entry` 取出最後一個entry，且刪除節點時刪的是 head->prev 也就是最後一點
### q_size
> 計算目前佇列的節點總量
利用 `list_for_each` 跑過 list 且每跑一個 node 長度就加一
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### 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/)
確定 list 不是 NULL 或 empty 後，用前面寫過的 q_size 取得 list 的長度
```c
int mid = q_size(head) / 2;
```
接著以 list_for_each_entry_safe 跑 entry 到中間的時候做 delete 和 release
```c
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
if (mid == 0) {
list_del(&entry->list);
q_release_element(entry);
return true;
}
mid = mid - 1;
}
return false;
```
### q_delete_dup
> 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
首先判斷 list 若為 NULL 則回傳 false
而若 list 為 empty 或只有一點，就直接回傳true
```c
if (!head)
return false;
if (list_empty(head) || list_is_singular(head))
return true;
```
接著利用 `list_for_each_entry_safe` 走訪 list，將下一個 entry 的 value 位址紀錄在 tmp，若現在的值和下一個一樣表示需要 release，且紀錄 delete 為 1，這樣走到有重複的最後一個 entry 時才會記得需要 release
而寫到這裡的時候有點混亂，有許多語法上的錯誤，以下紀錄。
原本的寫法 part 1：
```
element_t *entry = NULL, *safe = NULL;
char *tmp = NULL;
bool delete = 0;
list_for_each_entry_safe (entry, safe, head, list) {
if (&entry->list.next == head)
return true;
```
當下一個為 head 就直接 return 了，忽略了最後一個 entry 可能跟前面重疊到所以也需要刪除，應該確認 delete 是否為 0 再 return
修正：
```c
if (entry->list.next == head) {
if (delete) {
list_del(&entry->list);
q_release_element(entry);
return true;
} else {
return true;
}
}
```
原本的寫法 part 2：
```
*tmp = container_of(&entry->list.next, element_t, list)->value;
if (strcmp(&entry->value, tmp) == 0) {
delete = 1;
list_del(&entry->list);
q_release_element(entry);
} else if (delete) {
delete = 0;
list_del(&entry->list);
q_release_element(entry);
}
}
return true;
```
value 本身就是一個指向字串的指標了
tmp 也是指標，直接用 = 就好
在做字串比較的時候也不需要再取址
修正：
```c
tmp = container_of(entry->list.next, element_t, list)->value;
```
```c
if (strcmp(entry->value, tmp) == 0) {
```
### q_swap
> 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
利用 list_for_each_entry_safe 每跑兩個 node 就將該 node 移到前一個的前面
```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;
element_t *entry = NULL, *safe = NULL;
bool even = 0;
list_for_each_entry_safe (entry, safe, head, list) {
if (even) {
list_move(&entry->list, entry->list.prev);
}
even = !even;
}
return;
}
```
修正：`list_move` 是把 node 移到指向 node 的後面，所以這樣什麼都不會改動，應該要用 `list_move_tail`
### q_reverse
> 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
在 queue.h 中：
```
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
```
但 q_remove_head 也沒有 allocate 或 free 所以覺得有點困惑
但總之是要將 list 整個顛倒過來
因此需要將第一個和最後一個對調、第二個和倒數第二個對調......以此類推。
首先判斷 list 若為 NULL 或 empty 或只有一個節點就直接 return
接著用 left 和 right 的指標分別指向第一點、最後一點，並往右、左跑 list
以while迴圈持續交換 left 和 right 指到的點，直到指到同一個點或是相鄰的點
```c
while (left != right) {
if (left->next == right) {
list_move(left,right);
break;
}
tmp = left->prev;
list_move(left,right);
list_move(right,tmp);
tmp = left->prev;
left = right->next;
right = tmp;
}
```
### q_reverseK
> 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 [LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/)
若 head 為 NULL 或 empty 或只有一個節點或 k 為一就直接 return
接著跑迴圈並紀錄當跑了 k 個節點就需要做 reverse
```c
struct list_head *node = NULL, *safe = NULL;
struct list_head *left = head->next;
struct list_head *right;
struct list_head *tmp;
int count = 0;
list_for_each_safe (node, safe, head) {
count = count + 1;
if (count == k) {
count = 0;
right = node;
while (left != right) {
if (left->next == right) {
list_move(left, right);
break;
}
tmp = left->prev;
list_move(left, right);
list_move(right, tmp);
tmp = left->prev;
left = right->next;
right = tmp;
}
left = safe;
}
}
```
~~跑完後有可能最後幾個加起來不到 k 個節點的沒有做 reverse 要再把它做完~~
**更新：重看一次題目發現剩餘的不用做，也就是以下不需要**
```c
if (left != head) {
right = head->prev;
while (left != right) {
if (left->next == right) {
list_move(left, right);
break;
}
tmp = left->prev;
list_move(left, right);
list_move(right, tmp);
tmp = left->prev;
left = right->next;
right = tmp;
}
}
```
目前的寫法過於冗長，需要再想想更精簡的作法
### q_sort
> 以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法
看過文章後選擇用複雜度為 O(nlogn) 的 merge sort 方法實作
#### 原先的想法（有許多錯誤）：
一樣判斷可以直接 return 的狀況，並呼叫 mergesort_list 做 divide and conquer 中 divide 的部份 `mergesort_list`
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
head = mergesort_list(head);
}
```
找出中間點並拆成兩個 list，遞迴下去直到拆不了，再呼叫 `mergeTwoLists` 將兩兩合併
```c
struct list_head *mergesort_list(struct list_head *head)
{
if (!head || !head->next)
return head;
// let right points to midle
struct list_head *left = head->next;
struct list_head *right = head->prev;
while (left != right) {
if (left->next == right) {
break;
}
left = left->next;
right = right->prev;
}
// cut the link of list
left->next = NULL;
head->prev->next = NULL;
left = mergesort_list(head), right = mergesort_list(right);
return mergeTwoLists(left, right);
}
```
參考 [案例探討: LeetCode 21. Merge Two Sorted Lists](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) 使用指標的指標的方法
覺得這樣的寫法很不可思議，需要仔細思考並不搞混每個指標指在哪裡
而其中指標類型 uintptr_t 定義在 stdint.h 之中，因此加了標頭檔 `#include <stdint.h>`
```c
struct list_head *mergeTwoLists(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 = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
#### 修正：
> 觀摩[同學的做法](https://hackmd.io/@wanghanchi/linux2023-lab0#q_sort)後發現想法錯誤的地方
1. 找中間點的方法錯誤：原本想和前面的做法一樣從尾端和開頭開始往中間找中間點，但是在 merge 的過程中只會將next指向正確的下一個節點，而下一個節點的 prev 不會更新到正確的上一個 node，所以不能用這種方法找中間節點，應該要用快慢指標找
快慢指標（極度陽春版，若有學會如何製作更精美的版本再更新）：
```c
struct list_head *slow = head;
for (struct list_head *fast = head; fast && fast->next; fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow;
```
2. 沒有串好 circular linked-list：一樣因為過程的 prev 指標都是錯誤的，所以需要在 q_sort 做完 mergesort_list 後更新正確的 prev 指標
```c
struct list_head *p = head, *n = head->next;
for(; n != NULL; n = n->next) {
n -> prev = p;
p = n;
}
p->next = head;
head->prev = p;
```
3. 為遞迴方便，mergesort_list 傳入的 head 應直接指向第一個 node
```c
head->next = mergesort_list(head->next);
```
### q_descend
> 參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)
首先判斷 NULL 或 empty 直接回傳長度為 0
而若只有一個 node 則直接回傳 1
```c
if (!head || list_empty(head)) {
return 0;
} else if (list_is_singular(head)) {
return 1;
}
```
因為直接做不好做，可以將 list 做 reverse，接著紀錄沿途遇到的最大值，若在其後有較小的值則刪除，最後再做一次 reverse 即可
```c
q_reverse(head);
char *max = list_first_entry(head, element_t, list)->value;
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
if (strcmp(entry->value, max) < 0) {
list_del(&entry->list);
} else {
max = entry->value;
}
}
q_reverse(head);
return q_size(head);
```
但 make test 可以發現有錯，訊息：
```
ERROR: There is no queue, but 4 blocks are still allocated
ERROR: Freed queue, but 4 blocks are still allocated
```
看起來是需要釋放空間，雖然題目寫的是 remove，於是做完 list_del 之後加了：
```c
free(entry);
```
但這樣還是有沒釋放到的空間，發現 entry->value 沒有釋放到，改成以下：
```c
q_release_element(entry);
```
### q_merge
> 合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
在 queue.h 中可見關於 q_merge：
```
* @head: header of chain
```
而 chain 被用在 queue_contex_t 中，被用來將許多 queue 的 head 串在一起
```c
/**
* queue_contex_t - The context managing a chain of queues
* @q: pointer to the head of the queue
* @chain: used by chaining the heads of queues
* @size: the length of this queue
* @id: the unique identification number
*/
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
而先前有做過 q_sort，因此先將每個 queue 合在一起，再做 sort 即可
首先若 chain 為 NULL 或 empty 回傳 0
接著原本和上面一樣想著若為 singular 回傳 1，但這裡的 head 指的是 chain 的 head，就算是 singular 也有可能有一串 queue 所以不能這樣寫
```c
if (!head || list_empty(head)) {
return 0;
}
```
接著以 list_for_each_entry 走訪 chain，將每個 queue 接上第一個 queue
for 迴圈中也是從第一個 entry 開始走，一開始沒有注意到直接做 `list_splice_init` ，導致重複接了第一個 queue，應該要避免
```c
queue_contex_t *new_head = list_first_entry(head, queue_contex_t, chain);
queue_contex_t *entry = NULL;
list_for_each_entry (entry, head, chain) {
if (entry == new_head)
continue;
list_splice_init(entry->q, new_head->q);
}
```
再進行 sort 並回傳大小
```c
q_sort(new_head->q);
return q_size(new_head->q);
```
### make test 沒有皮卡丘
目前分數：95/100
constant time 沒有過
## 以 [Valgrind](https://valgrind.org/) 分析記憶體問題
```
$ make valgrind
```
這邊測出
`--- TOTAL 100/100`
最後兩行：
```
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.6Sd6EX --valgrind -t <tid>
```
Sign in with Wallet
Connect another wallet