---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < [ganoliz](https://github.com/ganoliz) >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
架構： x86_64
CPU 作業模式： 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
每核心執行緒數： 2
每通訊端核心數： 4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
製程： 9
CPU MHz： 2436.942
CPU max MHz: 4200.0000
CPU min MHz: 800.0000
BogoMIPS: 7200.00
虛擬： VT-x
L1d 快取： 128 KiB
L1i 快取： 128 KiB
L2 快取： 1 MiB
L3 快取： 8 MiB
NUMA node0 CPU(s)： 0-7
```
## 作業要求
* **實做 queue.c 的相關程式碼**：
* q_new: 建立新的「空」佇列;
* q_free: 釋放佇列所佔用的記憶體;
* q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點;
* q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點;
* q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* q_release_element: 釋放特定節點的記憶體空間;
* q_size: 計算目前佇列的節點總量;
* q_delete_mid: 移走佇列中間的節點;
* q_swap: 交換佇列中鄰近的節點;
* q_reverse: 以反向順序重新排列鏈結串列;
* q_sort: 以遞增順序來排序鏈結串列的節點;
* **在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作**
* **在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令**
* **指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request**
## 開發過程
### q_new:
```c
struct list_head *q_new()
{
struct list_head *Queue = malloc(sizeof(struct list_head));
if (Queue == NULL)
return NULL;
INIT_LIST_HEAD(Queue);
return Queue;
}
```
**新增一個Queue**:初期寫法是使用queue指標指向自身，後來詳讀[你所不知道的 C 語言: linked list 和非連續記憶體](/YA7RMqd6RE2UL8OmmjU9PQ)與 list.h 的 The Linux Kernel API ，將寫法改為 macro 。
### q_free:
```c
void q_free(struct list_head *l)
{
struct list_head *temp;
if (l == NULL) {
return;
}
if (list_empty(l)) {
// printf("l is already release");
free(l);
return;
}
if (list_is_singular(l)) {
element_t *node = container_of(l->next, typeof(element_t), list);
q_release_element(node);
free(l);
return;
}
for (temp = l->next; temp != l;) {
element_t *node = container_of(temp, typeof(element_t), list);
temp = temp->next;
q_release_element(node);
}
free(l);
return;
}
```
**釋放Queue**:可以看到 q_free() 針對不同的節點數做了很多if判斷。
假如head沒有 element_t 節點，就將本身 new 出來的 list_head 釋放就可以了。若是有節點則使用 container_of(list_entry) 找出 element_t 的位置再將其 element_t 釋放，最後再將 head 釋放。
顯然程式碼是有改進空間的，針對不同節點的共同特性找出來，就可以精簡程式碼不用那麼多 if 判斷。
### q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *Node = malloc(sizeof(element_t));
char *c = malloc(strlen(s) + 1);
if (Node == NULL || c == NULL) {
if (Node != NULL) {
free(Node);
}
if (c != NULL) {
free(c);
}
return false;
}
memcpy(c, s, strlen(s) + 1);
Node->value = c;
INIT_LIST_HEAD(&Node->list);
list_add(&Node->list, head);
return true;
}
```
**新增節點**:若是 malloc 不成功，要找出是 element_t 不成功還是 char 不成功，然後釋放掉另一個後回傳 false 。這是一個我很後面才改的小 Bug ，也讓我知道系統程式要考慮得很嚴謹，不能讓記憶體洩漏。
節點新增成功之後，將字串用 memcpy 複製到 element_t 的 value 成員。接著使用 API 初始化 element_t 的成員 list ，並將它的 list 新增到 head 的後面。
### q_insert_tail
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *Node = malloc(sizeof(element_t));
char *c = malloc(strlen(s) + 1);
// struct list_head *temp;
if (Node == NULL || c == NULL) {
if (Node != NULL) {
free(Node);
}
if (c != NULL) {
free(c);
}
return false;
}
memcpy(c, s, strlen(s) + 1);
Node->value = c;
INIT_LIST_HEAD(&Node->list);
list_add_tail(&Node->list, head);
return true;
}
```
**新增節點至尾端**:基本上跟 q_inset_head 相同，只是使用 list.h 的 API 不一樣，改使用 list_add_tail 。
### q_remove_head
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head)) {
return NULL;
}
struct list_head *node = head->next;
element_t *element;
element = list_entry(node, typeof(element_t), list);
if (sp) {
memcpy(sp, element->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del(node);
return element;
}
```
**移除從頭開始的第一個節點**: 將節點移除，若Queue不存在或是為空則回傳NULL。一開始搞不太清楚 char * sp 的用途還寫了很多 if-else 判斷式。稍微觀摩一下同學的程式碼就理解到 sp 。若有提供 sp ，就將 element_t 的 value 複製過去，複製直到 bufsize-1 的大小(遇到'\0'會自動停止)。值得注意的是若 element_t 的 value 大小超過 bufsize-1 其餘就會被砍掉，然後 * (sp+bufsize-1) 的位置一定要放'\0'，否則系統不會知道結束位置在哪裡。
### q_remove_tail
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head)) {
return NULL;
}
struct list_head *node = head->prev;
element_t *element;
element = list_entry(node, typeof(element_t), list);
if (sp) {
memcpy(sp, element->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del(node);
return element;
}
```
**從尾端移除節點**:基本上和從頭移除節點相同，只是存取的 node 點變成 head->prev，當然也可以使用 list_last_entry 來取得最後一個節點的位置。
### q_release_element
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
**釋放節點**:毫無疑問!就是個釋放節點。
### q_size:
```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;
}
```
**Queue的大小**:透過 list_for_eac 走訪每個 node，並每次對 len+1，最後返回 len 的長度。
### q_delete_middle
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (head == NULL || list_empty(head))
return false;
else if (list_is_singular(head)) {
// q_remove_head(head, NULL, 100);
element_t *temp = list_entry(head->next, element_t, list);
list_del(&temp->list);
q_release_element(temp);
return true;
}
struct list_head **indir = &head->next, *prev = NULL;
for (struct list_head *fast = head->next;
fast != head && fast->next != head; fast = fast->next->next) {
prev = *indir;
indir = &(*indir)->next;
}
struct list_head *next = (*indir)->next;
element_t *temp = list_entry(*indir, element_t, list);
list_del(*indir);
q_release_element(temp);
prev->next = next;
return true;
}
```
**移除中心點**: 參考[你所不知道的 C 語言: linked list 和非連續記憶體](/YA7RMqd6RE2UL8OmmjU9PQ)中所述之移除中心點方法，以快慢指標來實作( slow 走一格時 fast 走兩格)，找到中心點後將中心點使用 list_del 刪除(其實這樣就能將其前面的節點指向後面)。
```graphviz
digraph test {
node[shape=record];
rankdir=LR;
head [label="{<left>prev|<right>next}", style=bold];
node1 [label="value|{<left>prev|<right>next}", style=bold];
node2 [label="value|{<left>prev|<right>next}", style=bold];
head->node1[label="prev"]
node1->node2[label="fast"]
}
```
### q_delete_dup
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
if (list_is_singular(head)) {
return true;
}
bool duplicate = false;
struct list_head *current, *next;
list_for_each_safe (current, next, head) {
element_t *node = list_entry(current, element_t, list);
element_t *safe = list_entry(next, element_t, list);
if (next == head) {
if (duplicate) {
element_t *temp = node;
// node=list_entry(node->list.prev,element_t,list);
printf("remove node last:%c \n", *(temp->value));
list_del(&temp->list);
q_release_element(temp);
}
break;
}
if (strcmp(node->value, safe->value) == 0) {
element_t *temp = node;
// node=list_entry(node->list.prev,element_t,list);
duplicate = true;
// printf("remove node:%c \n",*(temp->value));
list_del(&temp->list);
q_release_element(temp);
}
else if (duplicate) {
element_t *temp = node;
// node=list_entry(node->list.prev,element_t,list);
printf("remove node last:%c \n", *(temp->value));
list_del(&temp->list);
q_release_element(temp);
duplicate = false;
}
}
return true;
}
```
**刪除重複的所有Node**:參考同學設置一個 bool duplicate 的想法，假如有重複就設 duplicate 為 true並刪除，若是 strcmp 之後未重複，則是判斷前面是否為 duplicate，若是則代表前面有出現過並把該node刪除。這部分程式碼還是有保留一些冗餘的部分，比如當 current == tail 且 next == head的情況下，需要用這段程式碼第一個if述句來特別開一個條件給它，寫起來不夠 general。
### q_swap
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
struct list_head *odd, *even, *temp;
odd = head->next, even = head->next->next;
while (odd != head && even != head) {
odd->next = even->next;
odd->prev->next = even;
temp = odd->prev;
odd->prev = even;
even->next->prev = odd;
even->next = odd;
even->prev = temp;
odd = odd->next;
even = odd->next;
}
```
**節點倆倆交換位置**:透過 odd 為奇數節點， even 為偶數節點走訪整個 Queue ，並兩兩指標交換。
```graphviz
digraph swap{
node[shape=record];
rankdir=LR;
head [label="{<left>prev|<right>next}", style=bold];
node1 [label="1|{<left>prev|<right>next}", style=bold];
node2 [label="2|{<left>prev|<right>next}", style=bold];
node3 [label="3 |{<left>prev|<right>next}", style=bold];
node4 [label="4|{<left>prev|<right>next}", style=bold];
node5 [label="5|{<left>prev|<right>next}", style=bold];
node6 [label="6|{<left>prev|<right>next}", style=bold];
head:right->node1
node1:right->node2
node2:right->node3[label="Step2"]
node3:right->node4 [label="Step1"]
node4:right->node5[label="Step5"]
node5:right->node6
node6:right->head
odd->node3
even->node4
head:left->node6
node6:left->node5
node5:left->node4[label="Step4"]
node4:left->node3[label="Step6"]
node3:left->node2[label="Step3"]
node2:left->node1
node1:left->head
}
```
根據圖，我們總共需要移動六個指標，首先移動
* 1. odd->next
* 2. odd->prev->next
* 3. odd->prev
* 4. even->next->prev
* 5. even->next
* 6. even->prev
然後因為現在 odd 實質上等於 even 的位置了，所以 odd 往 next 移動一次就等於新的要調整的 odd 了，然後 even 再順勢往 odd 的 next 再移動一次，就是新的要調整的 even 了(整體可讀性低了一些些)。
### q_reverse
```c
void q_reverse(struct list_head *head)
{
if (head == NULL || list_is_singular(head) || list_empty(head))
return;
struct list_head *li;
struct list_head *temp;
temp = head->prev;
head->prev = head->next;
head->next = temp;
list_for_each (li, head) {
temp = li->prev;
li->prev = li->next;
li->next = temp;
}
}
```
**Queue 翻轉**: 使用 list_for_each 走訪節點，然後將節點的 prev 與 next 對調(應該使用 list_for_each_safe 比較保險，因為有動到 Node 裡的東西)，走完每個節點對調完即完成。
### q_sort
```c
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *temp = head->next;
head->prev->next = NULL;
head->prev = NULL;
head->next->prev = NULL;
head->next = NULL;
struct list_head *sortlist = mergesort_list(temp);
```
**MergeSort**: 參考 [你所不知道的 C 語言: linked list 和非連續記憶體](/YA7RMqd6RE2UL8OmmjU9PQ) 中的 merge sort 範例 ，在這個函式裡，我們先把 head 丟棄，避免它在我們後續使用 list_entrt 找 element_t 位置的時候指涉到 head 導致錯誤。接著我們把第一個元素 temp 丟進 mergesort_list() 裡:
```c
static struct list_head *mergesort_list(struct list_head *head)
{
if (!head)
return NULL;
if (head->next == NULL)
return head;
struct list_head *slow = head;
for (struct list_head *fast = head->next;
fast != NULL && fast->next != NULL; fast = fast->next->next) {
slow = slow->next;
}
struct list_head *mid = slow->next;
// element_t *t=list_entry(mid,element_t,list);
// printf("mid= %c \n",*(t->value));
mid->prev = NULL;
slow->next = NULL;
// element_t *temp_sl=list_entry(slow,element_t,list);
// printf("slow= %c \t",*(temp_sl->value));
struct list_head *left = mergesort_list(head), *right = mergesort_list(mid);
return mergeTwoLists(left, right);
```
在這個函式裡我們會使用遞迴把所有 element_t 變為一個個互不相聯的元素使用 delete_mid的方法。所以說我們斷開了所有 prev 跟 next 。接著遞迴呼叫 mergeTwoLists 來兩兩合併 List :
```c
static struct list_head *mergeTwoLists(struct list_head *L1,
struct list_head *L2)
{
struct list_head *head = NULL;
struct list_head **ptr = &head;
for (; L1 && L2; ptr = &(*ptr)->next) {
element_t *l1 = list_entry(L1, element_t, list);
element_t *l2 = list_entry(L2, element_t, list);
if (strcmp(l1->value, l2->value) < 0) {
*ptr = L1;
L1 = L1->next;
} else {
*ptr = L2;
L2 = L2->next;
}
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
這裡就是參考老師的 merge two sorted lists ，非常漂亮。由於最後形成的是一個 Single-Linked-lists ，於是當我們最後回到 q_sort 裡時，需要將 prev 依序補上形成 Double-Linked-lists ，再把 head 接回來，大功告成。
```c
//struct list_head *sortlist = mergesort_list(temp);
// above ============================================================
struct list_head *prev = sortlist;
struct list_head *current = sortlist->next;
for (; current != NULL; current = current->next, prev = prev->next) {
current->prev = prev;
}
head->next = sortlist; // let head connect to value
sortlist->prev = head;
head->prev = prev; // finally prev will reach tail
prev->next = head;
```
Sign in with Wallet
Connect another wallet