# 2024q1 Homework1 (lab0)
contributed by < [`wilson20010327`](https://github.com/wilson20010327) >

## 實驗環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0

$ lscpu
Architecture:                       x86_64
CPU op-mode(s):                     32-bit, 64-bit
Byte Order:                         Little Endian
Address sizes:                      39 bits physical, 48 bits virtual
CPU(s):                             6
On-line CPU(s) list:                0-5
Thread(s) per core:                 1
Core(s) per socket:                 6
Socket(s):                          1
Vendor ID:                          GenuineIntel
CPU family:                         6
Model:                              158
Model name:                         Intel(R) Core(TM) i5-9400F CPU @ 2.90GHz
Stepping:                           10
CPU MHz:                            2903.998
BogoMIPS:                           5807.99

## 指定的佇列操作
### `q_reverse`
> commit [31e3fd3](https://github.com/wilson20010327/lab0-c/commit/31e3fd3c75430c67aec3d99bb54c231bf339d9e5)

將佇列中的所有節點以原先的順序走訪，並將所經歷的每個節點移至佇列的頭部，此就可以形成一個與原先佇列反轉的新佇列。

:::warning
改進你的漢語表達，用精準的詞彙。
:::

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *pos, *safe;
    list_for_each_safe (pos, safe, head) {
        list_move(pos, head);
    }
    return;
}

### `q_delete_dup`
> commit [96337bf](https://github.com/wilson20010327/lab0-c/commit/96337bf25330560d4d9c88d5736c95de371099fa)

:::danger
注意用語。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

<s>函數</s> 函式會先將一個指標 `new_head` 指向佇列最初的節點，然後開始走訪整個佇列。`pos` 作為現在所抵達的節點，`safe` 為下一個節點。

:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::

若 `pos` 以及 `safe` 的資料相同以及 `pos` 不是佇列最後一個節點，則 `new_head` 不做更新。反之當 `pos` 以及 `safe` 的資料不相相同或 `pos` 是佇列最後一個節點，檢查 `new_head` 是否為 `pos` 的 `list`：若為是，表示前面沒有擁有重複的資料，將 `new_head` 賦予 `safe->list` 的位置。若為否，表示前面節點有重複的資料，將從 `new_head` 至 `pos` 所有節點剪下併接至新指派的佇列 `pending_head` 並將 `new_head` 賦予 `safe->list` 的位置。

:::danger
「走訪」和「整個」具備相同的語境，避免贅詞。可改說「逐一走訪」
:::

<s>走訪整個</s> 逐一走訪佇列後，再將 `pending_head` 指向的佇列清除。

/* 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)
        return 0;
    LIST_HEAD(pending_head);
    element_t *pos, *safe;
    struct list_head *new_head = head->next;
    list_for_each_entry_safe (pos, safe, head, list) {
        if ((&safe->list != head) && !strcmp(pos->value, safe->value))
            /* if match*/
            continue;
        else {
            /* if no match or the end */
            if (&pos->list != new_head) {
                LIST_HEAD(temp_head);
                list_cut_position(&temp_head, new_head->prev, &pos->list);
                list_splice(&temp_head, &pending_head);
            }
            new_head = &safe->list;
        }
    }
    list_for_each_entry_safe (pos, safe, &pending_head, list)
        q_release_element(pos);

    return true;
}

### `q_merge2`
在實作中，需要執行將兩佇列結合，因此將此部分實作成一個函式。

:::danger
`q_merge2` 存在的考量是什麼？
:::

> commit [cfd28e8](https://github.com/wilson20010327/lab0-c/commit/cfd28e8c68c7835a6556570bca30c67d189998ff)

將兩個依照 `descend` 方向排列的佇列合成一個 `descend` 方向排列的佇列

void q_merge2(struct list_head *head,struct list_head *second_head,bool descend)
{
    /* merge two list and head will point to the new list */
    if (!head || !second_head)
        return;
    LIST_HEAD(temp);
    while (!list_empty(head) && !list_empty(second_head)) {
        element_t *node1 = list_first_entry(head, element_t, list);
        element_t *node2 = list_first_entry(second_head, element_t, list);
        bool cmp = (strcmp(node1->value, node2->value) <= 0);
        cmp = descend ? !cmp : cmp;
        if (cmp) {
            list_move_tail(&node1->list, &temp);
        } else {
            list_move_tail(&node2->list, &temp);
        }
    }
    /* splice the list in front of the list pointed by head and head point to
     * the new list */
    list_splice(&temp, head);
    if (!list_empty(second_head)) {
        list_splice_tail(second_head, head);
    }
}

### q_merge
> commit [c9bef2e](https://github.com/wilson20010327/lab0-c/commit/c9bef2ef57ba680f5abcf148dea006a3bb8fe8cb)

int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return list_first_entry(head, queue_contex_t, chain)->size;
    LIST_HEAD(stack);
    queue_contex_t *cur, *safe;
    int count = 0;
    list_for_each_entry_safe (cur, safe, head, chain) {
        count += cur->size;
        q_merge2(cur->q, &stack, descend);
    }
    list_splice(&stack, list_first_entry(head, queue_contex_t, chain)->q);
    return count;
}

在持續開發後發現在 Linux 核心風格的 List API 中，在串接鏈結串列時，通常以第一個參數接至第二個參數中 ( e.g., `list_splice`, `list_move_tail`)，因此我將自己撰寫的 `q_merge2` 的參數順序做變更滿足此要求。除此之外，在使用時使用者或許會在兩個佇列合併之後繼續使用 `second_head` , 若未在合併之後重新初始化 `second_head` 會造成程式錯誤，程式持續執行但是已無法對其正常操作，以下為執行的執行過程以及結果。

cmd> new
l = []
cmd> it aaa
l = [aaa]
cmd> it bbb
l = [aaa bbb]
cmd> it ccc
l = [aaa bbb ccc]
cmd> it ddd
l = [aaa bbb ccc ddd]
cmd> it eee
l = [aaa bbb ccc ddd eee]
cmd> new
l = []
cmd> it aaa
l = [aaa]
cmd> it bbb
l = [aaa bbb]
cmd> merge

當執行後整個程式仍然在執行，輸入也會正常顯示，但已經跟無法跟正常時一樣做相關的操作，我認為是因為並未初始化 `head` 使的 console 沒辦法取的正常的數值，而其就卡在要列印出現在 `head` 指向的佇列，我無法驗證我的猜想，我目前認為是因為在 console 呈現佇列數值的程式不在測時的範圍，而此就會造成這個問題，會進一步研究。

- void q_merge2(struct list_head *head,struct list_head *second_head,bool descend)
+ void q_merge2(struct list_head *second_head,struct list_head *head,bool descend)
{
    /* merge two list and head will point to the new list */
@@ -224,7 +224,7 @@ void q_merge2(struct list_head *head,
     * the new list */
    list_splice(&temp, head);
    if (!list_empty(second_head)) {
-       list_splice_tail(second_head, head);
+       list_splice_tail_init(second_head, head);
    }
}

### 尋找上述問題以及試著解決
> commit [4fe0c35](https://github.com/wilson20010327/lab0-c/commit/4fe0c350ed2a9dee604271c5ad6263ac7a706132)
>
使用 gdb 進行除錯結果為下，在 qtest.c 中的 q_show 函式會在印出之佇列之前檢測佇列是否為雙向循環佇列，問題點出在檢測的函式。

is_circular () at qtest.c:883
883         while (cur != current->q) {
(gdb) print cur
$1 = (struct list_head *) 0x55555556a408
(gdb) step
884             if (!cur)
(gdb) step
886             cur = cur->next;
(gdb) step
883         while (cur != current->q) {
(gdb) print cur
$2 = (struct list_head *) 0x55555556a118
(gdb) step 3
883         while (cur != current->q) {
(gdb) print cur
$3 = (struct list_head *) 0x55555556a498
(gdb) step 3
883         while (cur != current->q) {
(gdb) print cur
$4 = (struct list_head *) 0x55555556a1c8
(gdb) step 3
883         while (cur != current->q) {
(gdb) print cur
$5 = (struct list_head *) 0x55555556a278
(gdb) step 3
883         while (cur != current->q) {
(gdb) print cur
$6 = (struct list_head *) 0x55555556a308
(gdb) step 3
883         while (cur != current->q) {
(gdb) print cur
$7 = (struct list_head *) 0x55555556a068
(gdb) step 3
883         while (cur != current->q) {
(gdb) print cur
$8 = (struct list_head *) 0x55555556a408

在 is_circular 函式中檢測方式是以 while 迴圈做檢測，其中止條件為節點為佇列的頭或是節點為 NULL ，若此佇列為中的一部分為 loop 會造成無窮迴圈。將 is_circular 函式從單指針方法改為使用慢指針和快指針。單指針方法無法在不使用額外儲存的情況下檢測到發生在佇列中的 loop 。利用慢指針和快指針可以有效地檢測到佇列中的 loop 。但這種方法稍微增加的條件檢查。

static bool is_circular()
{
    struct list_head *cur = current->q->next;
+   struct list_head *fast = (cur) ? cur->next : NULL;
    while (cur != current->q) {
-        if (!cur)
+        if (!cur || !fast || !(fast->next))
            return false;
+        if (cur == fast)
+            return false;
        cur = cur->next;
+        fast = fast->next->next;
    }
    ...
}

---
before rebase
## 整合網頁伺服器
note : 作業描述的 `linenoiseEdit` 位於 `linenoise.c/line_edit`

在作業介紹以及測試時，都可以看到若透過瀏覽器發送 http request 可以順利的產生對應指令，但會多出 `cmd> Unknown command 'favicon.ico'` 根據了作業說明做了更改。

@@ -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);

        if (p)

### 後續發現與探討
經過改正後，以瀏覽器測試確實不會再有 `cmd> Unknown command 'favicon.ico'` 提示了，但也生成了其他問題。首先，以瀏覽器所送出的指令會被執行兩次，且若以 `curl http://localhost:9999/new` 進行測試則會出現我們在 `buffer` 補上後續的額外資料，如下圖
<s>
</s>

:::danger
文字訊息避免用圖片來表示，否則不好搜尋和分類。
:::

#### 驗證問題點
* 以 `wireshark` 檢測封包狀況，如下圖。以下情況為以瀏覽器下達一次 `new` <s>指令</s> 命令後下達 `quit` <s>指令</s> 命令一次，可以看到瀏覽器竟然會傳送兩次相同的請求

:::danger
command 是「命令」，而非「指令」(instruction)
:::

### 額外發現
在此次測試中，使用兩個不同的瀏覽器 (Brave, Microsoft Edge) 做為測試媒介分別稱之為 A、B。首先執行程式並且執行 `web` 模式，以 A 先下達指令一系列<s>指令</s> 命令，再開啟 B 下達<s>指令</s> 命令，這時 B 所下達的命令部會被執行直到再以 A 執行一次命令， B 所下達的指令才會被執行，相同的狀況也發生在兩個不同的執行輸入(command line、瀏覽器)此情況下前者為 B ，後者為 A。
## Rebase from remote

git remote add upstream https://github.com/sysprog21/lab0-c.git

git fetch upstream

git rebase upstream/master

git push origin master --force