---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `PinLin` >
## 實作佇列各項操作（`queue.c`）
### `q_new`
```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;
}
```
在作業的要求中，我們需要區分佇列不存在（`l = NULL`）與空佇列（`l = []`）的情況，因此在執行 `q_new` 之後，我建立了一個 `list_head` 物件作為佇列的開頭（head），宣示這是一個沒有資料但是仍然存在的空佇列。
:::info
這裡建立的不是 `element_t` 物件，是因為其作為佇列的開頭是用來表達佇列存在，若有值（value）在此也沒有意義。
:::
### `q_free`
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *curr, *next;
list_for_each_entry_safe (curr, next, l, list)
q_release_element(curr);
free(l);
}
```
這邊使用 `list_for_each_entry_safe` 走訪佇列中的每一個元素，並呼叫 `q_release_element` 將其佔用的記憶體空間釋放，最後再把用以表達佇列開頭（head）的 `list_head` 物件釋放。
:::info
根據 Linux 原始碼中對 `list_for_each_entry_safe` 的[定義](https://github.com/torvalds/linux/blob/4f12b742eb2b3a850ac8be7dc4ed52976fc6cb0b/include/linux/list.h#L724)，迴圈始於 head 的後一個元素，在走訪所有元素回到 head 時結束。
:::
### `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;
}
```
在題目的要求中，我們需要將傳入的字串 `s` 自己再複製一份。我先使用了 `malloc` 函式配置一段大小為 `strlen(s) + 1` 的空間，再用 `strcpy` 函式把字串 `s` 的內容複製過去。但是後來在 commit 時，我得到了 `Dangerous function detected` 的錯誤提示，參考了 [eric88525](https://hackmd.io/@eric88525/linux2022-lab0#q_insert_head) 後，改用 `strdup` 函式來替代原先的做法。
:::warning
你要說明為何如此。
:notes: jserv
:::
> 我認為使用 `strdup` 函式比較安全，是因為函式會自行根據來源字串的長度配置了大小相符的空間，再將來源字串的內容複製過去，從而避免了使用 `strcpy` 函式時的以下風險：
> 1. 預先配置的空間過小造成複製時溢位
> 2. 複製的長度沒有計算到最後用以標示字串結尾的 NULL 字元
### `q_insert_tail`
與 `q_insert_head` 基本上相同，只差在最後呼叫改為 `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 *e = list_entry(head->next, element_t, list);
list_del(head->next);
if (sp) {
// If sp is non-NULL, copy the value of removed element to *sp.
strncpy(sp, e->value, bufsize);
sp[bufsize - 1] = '\0';
}
return e;
}
```
首先透過 `list_entry` 取得 head 的後一個元素，接著呼叫 `list_del` 將其從鏈結串列「remove」，如果指標 `sp` 有值則將該元素的值使用 `strncpy` 複製至指標 `sp` 指向的空間，最後將 `sp[bufsize - 1]` 直接設為 `\0` 以確保複製過去的內容是 null-terminated。
:::info
strncpy(3p) — Linux manual page 中的 [APPLICATION USAGE ](https://man7.org/linux/man-pages/man3/strncpy.3p.html#APPLICATION%20USAGE) 段落提及：
> If there is no NUL character byte in the first n bytes of the array pointed to by s2, the result is not null-terminated.
:::
> 後來發現有 `list_empty` 這個巨集，可以更好的替代原先 `q_size(head) == 0` 的作法，因為呼叫 `q_size` 時需要走訪整個鏈結串列。
### `q_remove_tail`
與 `q_remove_head` 基本上相同，只差在作用的節點改為 `head->prev`。
### `q_delete_mid`
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *fast = head->next, *slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
這裡我透過快慢指標的技巧來找出中間的節點。
> 後來發現有 `list_empty` 這個巨集，可以更好的替代原先 `q_size(head) == 0` 的作法，因為呼叫 `q_size` 時需要走訪整個鏈結串列。
### `q_delete_dup`
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
bool is_dup = false;
element_t *curr, *next;
list_for_each_entry_safe (curr, next, head, list) {
if (curr->list.next != head && strcmp(curr->value, next->value) == 0) {
list_del(&curr->list);
q_release_element(curr);
is_dup = true;
} else if (is_dup) {
list_del(&curr->list);
q_release_element(curr);
is_dup = false;
}
}
return true;
}
```
要確認有哪些值重複出現過，就必須完整走訪一遍。我透過 `list_for_each_entry_safe` 來走訪每一個元素，首先透過 `curr->list.next != head` 確認下一個節點不是 head，便利用 `list_for_each_entry_safe` 暫存的下一個元素與當前的元素分別取值做比較。在刪除重複值的部分在實作時遇到一些障礙，所以參考了 [laneser](https://hackmd.io/@laneser/linux2022_lab0#q_delete_dup)。
:::info
必須先透過 `curr->list.next != head` 確認下一個節點，因為 head 並沒有被嵌入到 `element_t` 當中，讀取其透過 `list_entry` 取得的記憶體位址將會是非法存取！
:::
### `q_swap`
```c
void q_swap(struct list_head *head)
{
if (!head)
return;
struct list_head *curr, *next, *temp = NULL;
list_for_each_safe (curr, next, head) {
if (!temp) {
list_del(curr);
temp = curr;
} else {
list_add(temp, curr);
temp = NULL;
}
}
if (temp)
list_add_tail(temp, head);
}
```
首先我宣告一個指標 `temp`，透過 `list_for_each_safe` 來走訪每個元素，在 `temp` 沒有值時將 `curr` 指向的節點從鏈結串列移除，然後以 `temp` 暫存其位址，在 `temp` 有值時將其指向的節點加到 `curr` 指向的節點後方，迴圈結束後如果 `temp` 仍有值，就直接加到鏈結串列的尾巴。
:::info
在將 `curr` 指向的節點移除或把 `temp` 指向的節點加到 `curr` 指向的節點後面之前，我們已經把下一個節點的位址存在 `next` 了，所以不會影嚮到走訪的順序。
:::
### `q_reverse`
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *curr, *next;
list_for_each_safe (curr, next, head) {
list_move(curr, head);
}
}
```
原本在實作這個函式的時候，我額外宣吿一個起始值與 `head` 相同的 `tail` 變數，嘗試用動態改變鏈結串列尾部位置的方式來控制迴圈結束，但是後來發現我會在理論上最後一次判斷是否為 `tail` 前便將 `tail` 重新賦值，所以這個方法不可行。後來參考其他同學的作法，發現 [kdnvt](https://hackmd.io/@5ux520T8Sd-OoYfdxZR55Q/SyzDKJ9y9#q_reverse) 的作法簡潔易懂，太神了。
### `q_sort`
```c
void merge_sort(struct list_head *head);
struct list_head *divide_and_conquer(struct list_head *head);
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
merge_sort(head);
}
void merge_sort(struct list_head *head)
{
// Unlink list head and list tail
head->prev->next = NULL;
head->next = divide_and_conquer(head->next);
// Recover circular doubly linked list
struct list_head *curr = head;
while (curr->next) {
curr->next->prev = curr;
curr = curr->next;
}
head->prev = curr;
curr->next = head;
}
struct list_head *divide_and_conquer(struct list_head *head)
{
if (!head || !head->next)
return head;
// Divide
struct list_head *fast = head, *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
slow->prev->next = NULL;
struct list_head *left = divide_and_conquer(head);
struct list_head *right = divide_and_conquer(slow);
// Conquer
struct list_head *merged = NULL, **next_ptr = &merged;
while (left && right) {
if (strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) < 0) {
*next_ptr = left;
left = left->next;
} else {
*next_ptr = right;
right = right->next;
}
next_ptr = &(*next_ptr)->next;
}
*next_ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);
return merged;
}
```
原本在實作過程中希望能讓鏈結串列保持環狀以及雙向，但是發現這樣很難寫出可以複用的程式碼，在參考了 [jj97181818](https://hackmd.io/@jj97181818/linux2022-lab0#q_sort) 的寫法之後，我在一開始便先透過 `head->prev->next = NULL;` 將 head 和 tail 的連結中斷，直到最後排序完再把環狀和雙向的特性修補回來。
## 新增命令 `shuffle`
```c
void q_shuffle(struct list_head *head)
{
if (!head)
return;
srand(time(NULL));
struct list_head *node1 = head->prev;
int len = q_size(head);
while (len > 1) {
struct list_head *node2 = head->next;
for (int i = rand() % len; i > 0; i--) {
node2 = node2->next;
}
char *temp = list_entry(node1, element_t, list)->value;
list_entry(node1, element_t, list)->value =
list_entry(node2, element_t, list)->value;
list_entry(node2, element_t, list)->value = temp;
node1 = node1->prev;
len--;
}
}
```
首先我在 `queue.c` 中實作了 Fisher–Yates shuffle 的函式 `q_shuffle`，原本預期要修改 `queue.h` 以加入這個函式的定義，但是後來我發現題目有限制不得修改 `queue.h`，所以我選擇額外新增一個 `queue_shuffle.h` 的檔案，並在 `qtest.c` 中引入它。
## 新增命令 `web`
首先我將 tiny-web-server 的原始程式碼檔案 `tiny.c` 放入專案當中，接著編輯 `Makefile` 將其納入建置過程。
```diff
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
- linenoise.o
+ linenoise.o tinyweb.o
```
參考老師在作業說明中給的程式碼，將 tiny-web-server 中的函式 `process` 修改以滿足作業的要求。接著自行編寫標頭檔供其它檔案引入。
```c
#ifndef LAB0_TINYWEB_H
#define LAB0_TINYWEB_H
#include <netinet/in.h>
#include <stdbool.h>
extern int webfd;
extern bool noise;
/* Simplifies calls to bind(), connect(), and accept() */
typedef struct sockaddr SA;
int open_listenfd(int port);
char *process(int fd, struct sockaddr_in *clientaddr);
#endif /* LAB0_TINYWEB_H */
```
老師在作業中有提出一個可行的方向，是讓我們在執行 `web` 命令後不再使用 linenoise 來處理輸入，而是改用函式 `cmd_select`，首先將全域變數 `noise` 值設為 `false`。
```c
static bool do_web(int argc, char *argv[])
{
...
webfd = open_listenfd(port);
if (webfd > 0) {
report(3, "Listen on port %d, fd is %d", port, webfd);
noise = false;
return true;
}
report(1, "Could not launch the tiny-web-server");
return false;
}
```
接著修改函式 `run_console`（使用老師提供的程式碼），根據變數 `noise` 來判斷是否使用 linenoise 處理輸入。
```c
if (!has_infile) {
char *cmdline;
while (noise && (cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
while (buf_stack && buf_stack->fd != STDIN_FILENO)
cmd_select(0, NULL, NULL, NULL, NULL);
has_infile = false;
}
if (!noise) {
while (!cmd_done()) {
cmd_select(0, NULL, NULL, NULL, NULL);
}
}
...
```
接著修改函式 `cmd_select`（使用老師提供的程式碼），嘗試同時接收來自 tiny-web-server pipe 和 stdin 的輸入。
```c
...
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
char *cmdline;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
} else if (readfds && FD_ISSET(webfd, readfds)) {
FD_CLR(webfd, readfds);
result--;
int connfd;
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
connfd = accept(webfd, (SA *) &clientaddr, &clientlen);
char *p = process(connfd, &clientaddr);
if (p)
interpret_cmd(p);
free(p);
close(connfd);
}
```
接著便可以透過命令列工具 `curl` 或是瀏覽器對我們的程式發送命令了。
Sign in with Wallet
Connect another wallet