---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < [`Ahsen-lab`](https://github.com/Ahsen-lab) >
## 實驗環境
```shell
$ 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): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 6799.81
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
```
## 作業要求
> [作業要求](https://hackmd.io/@sysprog/linux2023-lab0)
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* `q_remove_tail`: 在佇列尾端 (tail) 移去 (remove) 給定的節點;
* `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_reverseK`: 類似 `q_reverse`，但指定每 k 個節點為一組，進行反向順序排列，詳見 [LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/)
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
* `q_descend`: 參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)
* `q_merge`: 合併所有==已排序==的佇列，並合而為一個新的已排序佇列，詳見 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
## 開發過程
:::danger
注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！
:notes: jserv
:::
### q_new
建立新的「空」佇列，使用 `malloc` 配置記憶體空間給 `head` ，再用 `INIT_LIST_HEAD` 巨集來初始化 `head` ，需要注意 `malloc` 有可能會 fail，若配置記憶體空間失敗，則回傳 `NULL` 。
```c
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
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
釋放佇列所佔用的記憶體
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *cur, *tmp;
element_t *elem = NULL;
list_for_each_safe (cur, tmp, l) {
elem = list_entry(cur, element_t, list);
q_release_element(elem);
}
free(l);
}
```
用 `list_for_each_safe` 巨集走訪每個節點並用 `list_entry` 巨集取出對應的 `element` ，然後釋放 `element` 所佔的記憶體空間。
### q_insert_head
在佇列開頭新增一個新節點
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
node->value = strdup(s);
if (!node->value) {
free(node);
return false;
}
list_add(&node->list, head);
return true;
}
```
我的作法是配置一段記憶體空間給一個新的 `element` ，再配置一段空間給 `element` 的成員變數 `char *value` 用來儲存字串。而因為在 [harness.h](https://github.com/sysprog21/lab0-c/blob/master/harness.h) 和 [harness.c](https://github.com/sysprog21/lab0-c/blob/master/harness.c) 檔案中，可見到對記憶體管理所進行的實作，會追蹤記憶體配置和釋放的狀態，將原先的 `malloc` 與 `free` 使用 `test_malloc` 與 `test_free` 取代，因此在配置記憶體空間時，只可用 `malloc` 來配置空間。
選擇使用 `strdup` 來配置記憶體空間給字串是因為根據 [strdup(3)](https://man7.org/linux/man-pages/man3/strdup.3.html)，`strdup` 會使用 `malloc` 來配置記憶體給新的字串。
```c
char *strdup(const char *s);
```
>The `strdup()` function returns a pointer to a new string which is a duplicate of the string `s`. Memory for the new string is obtained with `malloc()`, and can be freed with `free()`.
### q_insert_tail
在佇列尾端新增一個新節點
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
node->value = strdup(s);
if (!node->value) {
free(node);
return false;
}
list_add_tail(&node->list, head);
return true;
}
```
實作概念與 `q_insert_head` 相同，只是將 `list_add` 換成 `list_add_tail`。
### q_remove_head
移除佇列開頭的節點
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *elem = list_entry(head->next, element_t, list);
list_del_init(head->next);
if (sp) {
strncpy(sp, elem->value, bufsize);
sp[bufsize - 1] = '\0';
}
return elem;
}
```
首先檢查佇列是否存在以及是否為空佇列，若是的話則不做任何事，返回 `NULL` ，若不是的話則使用 `list_entry` 巨集取出開頭第一個 `element` ，再將該節點從佇列中移除，如果 `sp` 不為 `NULL` ，將第一個 `element` 中所存的字串複製給 `sp` 。
### 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 *elem = list_entry(head->prev, element_t, list);
list_del_init(head->prev);
if (sp) {
strncpy(sp, elem->value, bufsize);
sp[bufsize - 1] = '\0';
}
return elem;
}
```
實作概念與 `q_remove_tail` 相同，只是所移除的節點為 `head->prev` ，也就是倒數第一個節點。
### q_size
計算目前佇列的節點總量，設定一個變數 `len` ，初始值為 `0` ，再使用 `list_for_each` 巨集來遍歷佇列中的所有節點，每經過一個節點 `len` 就加一，最後回傳 `len` 的值，若佇列為 `NULL` 或 `empty` 則返回 `0`，
```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
移走佇列中間的節點，作法參考
>[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List) 案例探討 : [Leetcode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
原本的案例探討是針對單向的 linked list，但為適用於雙向環狀 linked list ，若傳入的佇列為 `NULL` 或是空佇列，則回傳 `false`。
使用快慢指標的技巧來找出中間的節點，首先設定一個指標 `mid` ，以及一個指標 `fast` ，兩個指標都會指向 `head->next` ，然後使用迴圈走訪節點， `fast` 每次會前進兩個節點，而 `mid` 每次前進一個，當 `fast` 本身等於 `head` 或是 `fast->next` 等於 `head` 時，代表已走訪完佇列，這時 `mid` 會指向佇列中間的節點。
找到中間節點後，使用 `list_entry` 巨集來取得相對應的 `element`，然後用 `list_del_init` 巨集來移除節點並用 `free` 釋放記憶體空間，最後回傳 `true` 。
```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 *mid = head->next, *fast = head->next;
while (fast != head && fast->next != head) {
mid = mid->next;
fast = fast->next->next;
}
element_t *elem = list_entry(mid, element_t, list);
list_del_init(mid);
q_release_element(elem);
return true;
}
```
### q_delete_dup
在已經排序的狀況，移走佇列中具備重複內容的節點，若傳入的佇列為 `NULL` 或空佇列，回傳 `false`。
>以下實作有參考 [laneser](https://hackmd.io/@laneser/linux2022_lab0#q_delete_mid) 同學的作法。
使用 `list_for_each_entry_safe` 巨集來走訪佇列中的所有 `element` ， `entry` 代表當前所指向的 `element` ，`safe` 則指向 `entry` 的下一個 `element`。
另外，在走訪節點的過程中需要考慮兩個情況：
1. `entry->value == safe->value`：
* 刪除 `entry`，並將 `needDel` 設成 `true`，表示所有與 `entry` 有相同字串的節點都是需要刪除的節點。
2. `entry->value != safe->value`：
* 若 `needDel == true` 表示 `entry` 也是需要刪除的節點。
* 若 `needDel == false` 表示 `entry` 無須刪除。
```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;
element_t *entry, *safe;
bool needDel = false;
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list != head && strcmp(entry->value, safe->value) == 0) {
list_del_init(&entry->list);
free(entry->value);
free(entry);
needDel = true;
} else if (needDel) {
list_del_init(&entry->list);
free(entry->value);
free(entry);
needDel = false;
}
}
return true;
}
```
:::warning
詳閱 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md)，避免 `needDel` 這樣違反一致程式碼風格的用法。
:notes: jserv
:::
根據 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md)，使用 [snakecase](https://en.wikipedia.org/wiki/Snake_case) 風格來命名變數，變更如下:
```diff
@@ -5,18 +5,18 @@ bool q_delete_dup(struct list_head *head
return false;
element_t *entry, *safe;
- bool needDel = false;
+ bool need_del = false;
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list != head && strcmp(entry->value, safe->value) == 0) {
list_del_init(&entry->list);
free(entry->value);
free(entry);
- needDel = true;
- } else if (needDel) {
+ need_del = true;
+ } else if (need_del) {
list_del_init(&entry->list);
free(entry->value);
free(entry);
- needDel = false;
+ need_del = false;
}
}
return true;
```
:::warning
善用 `q_release_element` 以縮減程式碼。`need_del` 可換為其他更符合題意的詞彙。
:notes: jserv
:::
參考老師的建議
- 以 `q_release_element` 縮減程式碼
- 將變數 `need_del` 改名為 `fund_dup` 以符合題意
- 將指標 `entry` 和 `safe` 改名為 `cur` 和 `tmp` 等更易懂的名稱
```diff
@@ -153,17 +153,17 @@ bool q_delete_dup(struct list_head *head)
if (!head || list_empty(head))
return false;
- element_t *entry, *safe;
- bool need_del = false;
- list_for_each_entry_safe (entry, safe, head, list) {
- if (&safe->list != head && strcmp(entry->value, safe->value) == 0) {
- list_del_init(&entry->list);
- q_release_element(entry);
- need_del = true;
- } else if (need_del) {
- list_del_init(&entry->list);
- q_release_element(entry);
- need_del = false;
+ element_t *cur, *tmp;
+ bool found_dup = false;
+ list_for_each_entry_safe (cur, tmp, head, list) {
+ if (&tmp->list != head && strcmp(cur->value, tmp->value) == 0) {
+ list_del_init(&cur->list);
+ q_release_element(cur);
+ found_dup = true;
+ } else if (found_dup) {
+ list_del_init(&cur->list);
+ q_release_element(cur);
+ found_dup = false;
}
}
return true;
```
最後放上修改後的程式碼
:::spoiler 完整程式碼
```c
/* Delete all nodes that have duplicate string */
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;
element_t *cur, *tmp;
bool found_dup = false;
list_for_each_entry_safe (cur, tmp, head, list) {
if (&tmp->list != head && strcmp(cur->value, tmp->value) == 0) {
list_del_init(&cur->list);
q_release_element(cur);
found_dup = true;
} else if (found_dup) {
list_del_init(&cur->list);
q_release_element(cur);
found_dup = false;
}
}
return true;
}
```
:::
### q_swap
交換佇列中鄰近的節點，若傳入的佇列為 `NULL` ，則不做任何動作。
這個函式中我主要是用 `list_move` 巨集來完成實作：
```c
/* list_move API */
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
```
`list_move` 巨集會將 `node` 移到佇列的開頭，也就是會讓 `head->next` 指向 `node` ，利用這個功能，搭配迴圈走訪節點，一開始設定一個指標 `h` 指向 `head` 。
每次迴圈 `h` 會前進兩個節點 `h = h->next->next` ，將 `h->next->next` 當作新的 `head` 代入 `list_move` 中，就可達到交換佇列中鄰近的節點的目的。
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *h;
for (h = head; (h->next != head) && (h->next->next != head);
h = h->next->next)
list_move(h->next->next, h);
}
```
### q_reverse
以反向順序重新排列佇列
首先判斷傳入的佇列是否為 `NULL` 或空佇列或是僅有單一節點的佇列，若是的話則不做任何動作。
使用 `list_for_each_safe` 巨集來走訪佇列中的節點，並使用 `list_move` 巨集來將當前的節點移動到佇列的開頭，以此達到反向排列佇列的效果。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *cur, *tmp;
list_for_each_safe (cur, tmp, head) {
list_move(cur, head);
}
}
```
### q_reverseK
以每 `K` 個節點為一組進行反向排列該佇列
首先判斷傳入的佇列是否為 `NULL` 或空佇列或是僅有單一節點的佇列，以及 `K` 是否小於 `2` 或大於佇列的總長度，若是的話則不做任何動作。
與 `q_reverse` 的實作概念相同，但新增一個 `count` 變數來計算是否已走訪到第 `K` 個節點，若是的話將該節點設為 `tmp_head` ，也就是當作一個暫定的新的 `head` ，然後重置 `count` 為 `0`，如此一來 `list_move` 巨集會將 `tmp_head` 之後的節點一一移動到 `tmp_head` 的後面，也就是會重新開始反向排列 `tmp_head` 後的節點。
重複上述步驟便可達到以每 `K` 個節點為一組進行反向排列的目的。
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head) || list_is_singular(head) || k < 2 ||
k > q_size(head))
return;
struct list_head *cur, *tmp, *tmp_head = head;
int count = 0;
list_for_each_safe (cur, tmp, head) {
list_move(cur, tmp_head);
count++;
if (count == k) {
tmp_head = tmp->prev;
count = 0;
}
}
}
```
### list_append
這個函式被用在 `merge_two_lists` 函式中，目的是將兩個佇列串接在一起。
- `list` : 指向要被串接到後面的那個佇列
- `head` : 指向前面的那個佇列
與 `list_splice_tail` 函式不同的是， `list_append` 會將 `list` 所指的整個佇列，包含第一個節點，都接到 `head` 的後面，而 `list_splice_tail` 只會將 `list` 的下一個節點之後的節點合併到 `head` 。
```c
/**
* list_append() - Add all nodes from a list to the end of another list
* @list: pointer to the head of the list with the node entries to add
* @head: pointer to the head of the list to add the nodes to
*
* All nodes from @list, including the @list head, are added to the end of the
* list of @head.
*/
void list_append(struct list_head *list, struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_last = list->prev;
head_last->next = list;
list_last->next = head;
list->prev = head_last;
head->prev = list_last;
}
```
### merge_two_lists
:::warning
保持一致的命名風格。
:notes: jserv
:::
參考 [案例探討: 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) 中指標的指標的方式來實作此函式，用來合併兩個已排序的佇列。
指標用途：
- `e1` 、 `e2` : 分別指向 `l1` 和 `l2` 當前所指向的節點所連接的 element
- `merged_head` : 這個指標用來指向合併後的新佇列。
- `cur` : 比較 `l1` 和 `l2` 兩個節點中的字串， `cur` 會指向字典序 ( lexicographically ) 較小的節點。
- `merged_tail` : 指向合併後的佇列的尾端。
:::spoiler 完整程式碼
```c
/* Merge Two Sorted Lists */
struct list_head *mergeTwoLists(struct list_head *l1, struct list_head *l2)
{
struct list_head *merged_head = NULL, **merged_tail = &merged_head,
**cur = NULL;
element_t *e1 = NULL, *e2 = NULL;
while (l1->next != merged_head && l2->next != merged_head) {
e1 = list_entry(l1, element_t, list);
e2 = list_entry(l2, element_t, list);
cur = ((strcmp(e1->value, e2->value) <= 0) ? &l1 : &l2);
*merged_tail = *cur;
*cur = (*cur)->next;
list_del_init(*merged_tail);
list_add_tail(*merged_tail, merged_head);
merged_tail = &(*merged_tail)->next;
}
merged_head == l1->next ? list_append(l2, merged_head)
: list_append(l1, merged_head);
return merged_head;
}
```
:::
1. 使用一個迴圈來遍歷佇列 `l1` 和 `l2` ，比較 `l1` 和 `l2` 當前所指向的節點中的字串，選出字典序 ( lexicographically ) 較小的節點。
2. 接著用指標的指標 `cur` 指向選中的節點 ( 假設是 `l1` ) 的位址，而 `*merged_tail` 也會指向該節點，然後 `*cur` 會移向 `l1` 的下一個節點，因為 `cur` 中存放的是 `&l1` ，因此 `*cur = (*cur)->next` 就相當於 `l1 = l1->next` ，即 `l1` 會指向本身的下一個節點。
```c
e1 = list_entry(l1, element_t, list);
e2 = list_entry(l2, element_t, list);
cur = ((strcmp(e1->value, e2->value) <= 0) ? &l1 : &l2);
*merged_tail = *cur;
*cur = (*cur)->next;
```
3. 選中的節點 `*merged_tail` ， 用 `list_del_init` 函式將其從原本的佇列移除，然後 `list_add_tail` 函式將其添加到新佇列的尾端，接著 `merged_tail` 會指向要存放下一個節點的空間，當下一個節點被選中後，會重複 1 ~ 3 的步驟。
```c
list_del_init(*merged_tail);
list_add_tail(*merged_tail, merged_head);
merged_tail = &(*merged_tail)->next;
```
4. 最後當迴圈結束時，將剩餘的節點全部串到新佇列的尾端，並回傳 `merged_head` 。
```c
merged_head == l1->next ? list_append(l2, merged_head)
: list_append(l1, merged_head);
return merged_head;
```
### merge_k_lists
參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 中的 [Merge Sort 的實作](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)，以 Merge Sort 的方式來合併多個已排序的佇列。
首先，檢查 `h` 是否為空佇列，如果是則直接回傳 `h`，表示無需合併，這同時也是遞迴函式的截止條件。
```c
if (list_empty(h))
return h;
```
接著， Merge Sort 主要分為兩大步驟，分割和合併：
#### 分割
使用前面提到的快慢指標的技巧來找出中間的節點，以便從中將佇列分割為兩個佇列，接著用遞迴的方式重複呼叫 `merge_k_lists` 函式，將佇列不斷分割為二，最後佇列將被分割為一個個單獨的節點。
```c
struct list_head *slow = h, *fast = h->next, *mid;
while (fast != h && fast->next != h) {
slow = slow->next;
fast = fast->next->next;
}
mid = slow->next;
mid->prev = h->prev;
h->prev->next = mid;
slow->next = h;
h->prev = slow;
slow = merge_k_lists(h);
fast = merge_k_lists(mid);
```
#### 合併
每個單獨的節點都可視為已排序的佇列，透過遞迴調用 `merge_two_lists` 函式來兩兩合併佇列，如此便可得到排序後的完整佇列。
```c
return merge_two_lists(slow, fast);
```
以下為 `merge_k_lists` 函式的完整程式碼
```c
struct list_head *merge_k_lists(struct list_head *h)
{
if (list_empty(h))
return h;
struct list_head *slow = h, *fast = h->next, *mid;
while (fast != h && fast->next != h) {
slow = slow->next;
fast = fast->next->next;
}
mid = slow->next;
mid->prev = h->prev;
h->prev->next = mid;
slow->next = h;
h->prev = slow;
slow = merge_k_lists(h);
fast = merge_k_lists(mid);
return merge_two_lists(slow, fast);
}
```
### q_sort
以==遞增順序==來排序佇列中的節點，首先判斷傳入的佇列是否為 `NULL` 或空佇列或是僅有單一節點的佇列，若是的話則不做任何動作。
接著給定一個指標 `new_queue` 指向 `head` 的下一個節點，並將 `head` 暫時移出佇列，因為 `head` 本身並沒有連接到 element，不包含任何字串因此不參與排序。
然後調用 `merge_k_lists` 函式 來排序 `new_queue` ，完成後用 `list_add` 巨集將 `head` 併回到佇列的頭部，如此即可完成佇列的排序。
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *new_queue = head->next;
list_del_init(head);
new_queue = merge_k_lists(new_queue);
list_add(head, new_queue->prev);
}
```
### q_descend
`q_descend` 函式的主要功能為，對於佇列中的任何節點，如果其右側還有節點的值比它大，則將其從佇列中移除。
實做的概念為，通過將佇列反轉，以相反的順序遍歷佇列，從佇列的尾端開始遍歷，一旦找到一個節點比開頭節點（`first`）的值小，就從鏈表中刪除該節點 (`cur`) 。反之，如果找到一個節點比開頭節點的值大或相等，則將該節點設置為新的開頭節點。
最後，將佇列再次反轉以返回原始順序，並回傳佇列中剩餘節點的數量。
函式的流程如下：
1. 檢查佇列是否為 `NULL` 或是空佇列，若是則直接回傳 0。
2. 檢查佇列中是否只有一個節點，若是則直接返回 1。
3. 將佇列反轉，使其最右側的節點變成最左側的節點，方便從尾端開始遍歷佇列。
4. 將 `first` 指向佇列中第一個節點，初始時 `size` 設為 0，`deleted_nodes` 設為 0。
5. 使用 `list_for_each_entry_safe` 巨集從左到右遍歷佇列，對於每個節點執行以下操作：
- 將 `size` 加 1，代表經過了一個節點。
- 如果 `first` 指向的節點的值比當前節點的值大，代表存在某個右側節點的值比當前節點大，因此需要將當前節點從佇列中移除。
- 移除當前節點後，將 `deleted_nodes` 加 1，代表已經刪除了一個節點。
- 如果 `first` 指向的節點的值不比當前節點的值大，代表右側沒有比當前節點大的節點，因此將 `first` 指向當前節點。
6. 將佇列反轉回原本的順序。
7. 返回未被刪除節點的數量，即 `size` 減去 `deleted_nodes`。
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return 1;
q_reverse(head);
element_t *cur, *tmp;
element_t *first = list_entry(head->next, element_t, list);
int size = 0, deleted_nodes = 0;
list_for_each_entry_safe (cur, tmp, head, list) {
size++;
if (strcmp(first->value, cur->value) > 0) {
list_del_init(&cur->list);
q_release_element(cur);
deleted_nodes++;
} else {
first = cur;
}
}
q_reverse(head);
return size - deleted_nodes;
}
```
### q_merge
觀察 `queue_contex_t` 結構，`chain` 會將所有佇列的頭部都串連在一起，`q` 會指向當前佇列的頭部。
```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_merge` 會將 `chain` 中所有的佇列合併為一個新的已排序佇列。
函式的流程如下：
1. 檢查 chain 是否為 `NULL` 或是空的 chain，若是則直接回傳 0。
2. 如果 chain 只有一個佇列，則直接返回這個已排序佇列的節點數量。
3. 如果 chain 有多個佇列，則取出第一個佇列（即 `queue_contex_t` 結構體），將其保存到 `head_chain` 指標中。
4. 然後從 head_chain 指針中的鏈表中取出第一個已排序鏈表，並將其從鏈表中刪除，將其指針保存在 queue 指針中。
5. 使用 `list_for_each_entry_safe` 遍歷 chain 中的所有佇列，每次取出一個已排序鏈表，然後將其從鏈表中刪除，將其指針保存在 entry 指針中。
6. 然後使用 merge_two_lists 函數將 queue 和 entry 這兩個已排序鏈表合併成一個新的已排序鏈表，並將其指針保存在 queue 指針中。
7. 將 entry 的節點數量添加到 total 變量中，然後重複執行步驟 5 和步驟 6，直到 head 鏈表中的所有節點都被遍歷完畢為止。
8. 最後，將 queue 指針指向的已排序鏈表添加到 head_chain 指針所指向的鏈表中，然後返回已排序鏈表的節點數量 total。
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
queue_contex_t *head_chain = list_entry(head->next, queue_contex_t, chain);
if (list_is_singular(head))
return head_chain->size;
struct list_head *queue = head_chain->q->next, *chain = NULL;
list_del_init(head_chain->q);
queue_contex_t *cur, *tmp;
int total = head_chain->size;
list_for_each_entry_safe (cur, tmp, head, chain) {
if (cur == head_chain)
continue;
chain = cur->q->next;
list_del_init(cur->q);
queue = merge_two_lists(queue, chain);
total += cur->size;
}
list_add(head_chain->q, queue->prev);
return total;
}
```
:::danger
注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！
:notes: jserv
:::
## 整合網頁伺服器
### 修復 `favicon.ico` 的問題
因為部分瀏覽器會要求 request 中要提供網頁圖案的對應資訊，而原始程式中的 response 為：
```c
char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
```
其中並沒有包含關於 icon 的資訊。要修改這個問題，參考 [解決 `favicon.ico` 的問題](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-c#%E8%A7%A3%E6%B1%BA-faviconico-%E7%9A%84%E5%95%8F%E9%A1%8C) ，在 `cmd_select` 函式中，將 http response 的內容改為
```diff
@@ -617,7 +617,14 @@ static int cmd_select(int nfds,
accept(web_fd, (struct sockaddr *) &clientaddr, &clientlen);
char *p = web_recv(web_connfd, &clientaddr);
- char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
+ char *buffer =
+ "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
+ "Content-Type: text/html\r\n\r\n"
+ "<html><head><style>"
+ "body{font-family: monospace; font-size: 13px;}"
+ "td {padding: 1.5px 6px;}"
+ "</style><link rel=\"shortcut icon\" href=\"#\">"
+ "</head><body><table>\n";
web_send(web_connfd, buffer);
```
即可修復此問題。
### 確保 `web` 命令與 `linenoise` 套件可一起使用
目前一旦網頁伺服器啟動後，原本處理命令列操作的 `linenoise` 套件就無法使用。
觀察 `console.c` 中的程式碼，在 `do_web` 函式中，當網頁伺服器啟動時，會將 `use_linenoise` 設為 `false`
```c
web_fd = web_open(port);
if (web_fd > 0) {
printf("listen on port %d, fd is %d\n", port, web_fd);
use_linenoise = false;
} else {
perror("ERROR");
exit(web_fd);
}
```
而在 `run_console` 函式中，若 `use_linenoise = false` ，則不會啟用 `linenoise` 套件，會調用 `cmd_select` 函式來處理使用者輸入的命令，因此無法讓網頁伺服器與 `linenoise` 套件同時使用。
為了讓解決這個問題，首先我刪除了 `use_linenoise` 變數，也就是說不論是否有啟動網頁伺服器，都會使用 `linenoise` 套件。
```diff
@@ -404,7 +403,6 @@ static bool do_web(int argc, char *argv[])
web_fd = web_open(port);
if (web_fd > 0) {
printf("listen on port %d, fd is %d\n", port, web_fd);
- use_linenoise = false;
} else {
perror("ERROR");
exit(web_fd);
}
return true;
}
```
同樣的，也要修改 `run_console` 函式，移除關於 `use_linenoise` 的判斷，統一使用 `linenoise` 處理命令列輸入。
```diff
@@ -694,7 +691,7 @@ bool run_console(char *infile_name)
if (!has_infile) {
char *cmdline;
- while (use_linenoise && (cmdline = linenoise(prompt))) {
+ while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
line_history_add(cmdline); /* Add to the history. */
line_history_save(HISTORY_FILE); /* Save the history on disk. */
@@ -702,10 +699,9 @@ bool run_console(char *infile_name)
while (buf_stack && buf_stack->fd != STDIN_FILENO)
cmd_select(0, NULL, NULL, NULL, NULL);
has_infile = false;
- }
- if (!use_linenoise) {
- while (!cmd_done())
- cmd_select(0, NULL, NULL, NULL, NULL);
+
+ if (web_connfd > 0)
+ close(web_connfd);
}
} else {
while (!cmd_done())
```
但這樣又會有另一個問題，觀察程式等待輸入時的主要迴圈，位於 `linenoise()->line_raw()->line_edit()` 內的 `while(1)` 迴圈。
但 `linenoise` 是用 `read` 等待使用者輸入，無法接收 web 傳來的資訊。
因此要在 `line_edit()` 內的 `while(1)` 迴圈中嘗試用 `select()` 同時處理來自 `stdin` 及 `socket`的資訊。
> 參考 [整合 tiny-web-server](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-c#%E6%95%B4%E5%90%88-tiny-web-server)
首先判斷是否有啟用 `web` 命令，若 `web_fd > 0` ，表示網頁伺服器已啟用。
- 先將 socket 改為 non-blocking，防止程式停止接收使用者輸入：
```c
int flags = fcntl(web_fd, F_GETFL);
if (flags != (flags | O_NONBLOCK))
fcntl(web_fd, F_SETFL, flags | O_NONBLOCK);
```
- 接著，將 `web_fd` 和 `stdin_fd` 加入 `fd_set` 中，讓 `select` 可以同時處理來自使用者與網頁伺服器的命令。
```c
fd_set set;
FD_ZERO(&set);
FD_SET(web_fd, &set);
FD_SET(stdin_fd, &set);
int rv = select(web_fd + 1, &set, NULL, NULL, NULL);
```
- `select` 會監聽兩個 file descriptors（`web_fd` 和 `stdin_fd`）是否有 connect 或request 等事件發生。
- 如果是 `web_fd` 有事件發生，則代表有來自 web 的命令，並回傳一個 HTTP 200 OK 的回應。參考 `cmd_select` 中針對 web 命令的處理：
1. 使用 `accept` 函式等待客戶端的連接請求到達。
2. `web_recv` 函式會接收 HTTP 請求並回傳命令的字串。
3. 將命令字串複製到 `buf` 中。
4. 使用 `web_send` 將 response 回傳給客戶端 ( 記得修復 `favicon.ico` 的問題 )。
5. 最後回傳接收到的命令的長度。
```c
if (FD_ISSET(web_fd, &set)) {
web_connfd = accept(web_fd, (SA *) &clientaddr, &clientlen);
char *p = web_recv(web_connfd, &clientaddr);
strncpy(buf, p, strlen(p) + 1);
int len = strlen(p);
char *buffer =
"HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
"Content-Type: text/html\r\n\r\n"
"<html><head><style>"
"body{font-family: monospace; font-size: 13px;}"
"td {padding: 1.5px 6px;}"
"</style><link rel=\"shortcut icon\" href=\"#\">"
"</head><body><table>\n";
web_send(web_connfd, buffer);
free(p);
return len;
}
```
- 如果是 `stdin_fd` 有事件發生，則代表來自命令列的命令，此時程式會讀取使用者輸入的命令，最後會回傳讀取的命令的長度。
```c
else if (FD_ISSET(stdin_fd, &set)) {
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
}
```
而若是 `web` 命令未啟動，即 `web_fd <= 0` ，表示網頁伺服器未啟用，只需處理來自命令列的命令
```c
else {
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
}
```
:::spoiler 完整的實作
```diff
@@ -932,9 +935,56 @@ static int line_edit(int stdin_fd,
int nread;
char seq[5];
- nread = read(l.ifd, &c, 1);
- if (nread <= 0)
- return l.len;
+ if (web_fd > 0) {
+ int flags = fcntl(web_fd, F_GETFL);
+ if (flags != (flags | O_NONBLOCK))
+ fcntl(web_fd, F_SETFL, flags | O_NONBLOCK);
+
+ fd_set set;
+ FD_ZERO(&set);
+ FD_SET(web_fd, &set);
+ FD_SET(stdin_fd, &set);
+
+ int rv = select(web_fd + 1, &set, NULL, NULL, NULL);
+ struct sockaddr_in clientaddr;
+ socklen_t clientlen = sizeof(clientaddr);
+
+ switch (rv) {
+ case -1:
+ perror("select"); /* an error occurred */
+ continue;
+ case 0:
+ printf("timeout occurred\n"); /* a timeout occurred */
+ continue;
+ default:
+ if (FD_ISSET(web_fd, &set)) {
+ web_connfd = accept(web_fd, (SA *) &clientaddr, &clientlen);
+ char *p = web_recv(web_connfd, &clientaddr);
+ strncpy(buf, p, strlen(p) + 1);
+ int len = strlen(p);
+ char *buffer =
+ "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
+ "Content-Type: text/html\r\n\r\n"
+ "<html><head><style>"
+ "body{font-family: monospace; font-size: 13px;}"
+ "td {padding: 1.5px 6px;}"
+ "</style><link rel=\"shortcut icon\" href=\"#\">"
+ "</head><body><table>\n";
+ web_send(web_connfd, buffer);
+ free(p);
+ return len;
+ } else if (FD_ISSET(stdin_fd, &set)) {
+ nread = read(l.ifd, &c, 1);
+ if (nread <= 0)
+ return l.len;
+ }
+ break;
+ }
+ } else {
+ nread = read(l.ifd, &c, 1);
+ if (nread <= 0)
+ return l.len;
+ }
```
:::
## 在 `qtest` 提供新的命令 `shuffle`
藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作。
我參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 中對於 [Fisher–Yates shuffle](https://hackmd.io/@sysprog/c-linked-list#Fisher%E2%80%93Yates-shuffle) 演算法的 [實作](https://hackmd.io/@sysprog/c-linked-list#%E5%AF%A6%E4%BD%9C)
- 首先在 `console_init` 函式中新增一個 `shuffle` 命令即描述
```c
ADD_COMMAND(shuffle,
"Shuffle all nodes in queue using the Fisher-Yates "
"shuffle algorithm",
"");
```
- 接著實作 `do_shuffle` 函式，定義 `shuffle` 命令的行為
1. `shuffle` 命令不接受參數，若有輸入參數會回傳 `false`
2. 若佇列為 `NULL` 則跳出警告並結束
3. `shuffle` 的實作中不允許配置新的記憶體，因此開啟 `set_noallocate_mode(true);`
4. 呼叫 `q_shuffle(current->q);` 來進行洗牌操作
5. 顯示洗牌後的結果並回傳成功與否
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q)
report(3, "Warning: Calling shuffle on null queue");
error_check();
set_noallocate_mode(true);
if (current && exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
q_show(3);
return !error_check();
}
```
- `q_shuffle` 中定義了洗牌演算法的實作
1. 首先判斷傳入的佇列是否為 `NULL` 或空佇列或是僅有單一節點的佇列，若是的話則不做任何動作。
2. 使用時間戳作為亂數種子，初始化亂數產生器。
3. 獲取佇列的長度。
4. 初始化一個指標 `new` ，指向佇列的最後一個元素。
5. 進行 `len - 1` 輪的隨機交換操作，每一輪從原佇列中隨機選擇一個位置 `random`，從頭部開始遍歷鏈表，找到第 `ramdom` 個元素 `old`，然後交換 `old` 和 `new` 所對應的值。
6. 隨著每一輪的結束，`new` 遞減，指向原佇列中靠前的元素。
7. 當所有輪的交換操作完成後，佇列中的元素順序被打亂，保存在原佇列中。
```c
static void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
srand(time(NULL));
int len = q_size(head);
int random;
char *tmp;
struct list_head *old, *new = head->prev;
element_t *entry_old, *entry_new;
while (len-- > 1) {
random = rand() % len;
old = head->next;
while (random--)
old = old->next;
entry_old = list_entry(old, element_t, list);
entry_new = list_entry(new, element_t, list);
tmp = entry_old->value;
entry_old->value = entry_new->value;
entry_new->value = tmp;
new = new->prev;
}
}
```
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
### Simulation 程式實作驗證流程
在 `qtest` 中執行 `option simulation 1` 可開啟 “simulation” 模式，測試時間複雜度。
首先觀察 `do_option` 函式中的程式碼
```c
/* Find parameter in list */
param_element_t *plist = param_list;
while (!found && plist) {
if (strcmp(plist->name, name) == 0) {
int oldval = *plist->valp;
*plist->valp = value;
if (plist->setter)
plist->setter(oldval);
found = true;
} else
plist = plist->next;
}
```
Sign in with Wallet
Connect another wallet