2022q1 Homework1 (lab0)

contributed by < PinLin >

實作佇列各項操作（queue.c）

q_new

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），宣示這是一個沒有資料但是仍然存在的空佇列。

這裡建立的不是 element_t 物件，是因為其作為佇列的開頭是用來表達佇列存在，若有值（value）在此也沒有意義。

q_free

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 物件釋放。

根據 Linux 原始碼中對 list_for_each_entry_safe 的定義，迴圈始於 head 的後一個元素，在走訪所有元素回到 head 時結束。

q_insert_head

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 後，改用 strdup 函式來替代原先的做法。

你要說明為何如此。

jserv

我認為使用 strdup 函式比較安全，是因為函式會自行根據來源字串的長度配置了大小相符的空間，再將來源字串的內容複製過去，從而避免了使用 strcpy 函式時的以下風險：

1. 預先配置的空間過小造成複製時溢位
2. 複製的長度沒有計算到最後用以標示字串結尾的 NULL 字元

q_insert_tail

與 q_insert_head 基本上相同，只差在最後呼叫改為 list_add_tail，將新節點插入至佇列的結尾。

q_remove_head

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。

strncpy(3p) — Linux manual page 中的 APPLICATION USAGE 段落提及：

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

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

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。

必須先透過 curr->list.next != head 確認下一個節點，因為 head 並沒有被嵌入到 element_t 當中，讀取其透過 list_entry 取得的記憶體位址將會是非法存取！

q_swap

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 仍有值，就直接加到鏈結串列的尾巴。

在將 curr 指向的節點移除或把 temp 指向的節點加到 curr 指向的節點後面之前，我們已經把下一個節點的位址存在 next 了，所以不會影嚮到走訪的順序。

q_reverse

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 的作法簡潔易懂，太神了。

q_sort

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 的寫法之後，我在一開始便先透過 head->prev->next = NULL; 將 head 和 tail 的連結中斷，直到最後排序完再把環狀和雙向的特性修補回來。

新增命令 shuffle

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 將其納入建置過程。

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 修改以滿足作業的要求。接著自行編寫標頭檔供其它檔案引入。

#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。

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 處理輸入。

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 的輸入。

...
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 或是瀏覽器對我們的程式發送命令了。