2022q1 Homework1 (lab0)

contributed by < steven1lung >

開發環境

$ uname -a
Linux steven--laptop 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
$ gcc -v
gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

作業要求

K01: lab0、2022q1 Homework1 (作業區)

在 GitHub 上 fork lab0-c
- 參閱 Git 教學和 GitHub 設定指引 ^{附教學影片}
依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
- 在提交程式變更前，務必詳閱如何寫好 Git Commit Message
- 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- 可依據前述說明，嘗試整合 tiny-web-server
除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
  - 先執行 qtest 再於命令提示列輸入 help 命令，會使開啟 Address Sanitizer 觸發錯誤，應予以排除
- 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
- 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
指出現有程式的缺陷 (提示: 和 RIO 套件有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request

改進下方內容的漢語書寫，力求通順和達意，並適度加上標點符號。請設想日後你在面試場合中，會如何跟公司主管介紹自己所作所為呢？很多人宣稱自己因為「口才不好」，於是在面試場合失利，但我發現，其實其中多數是平常沒做好溝通的準備。我要求學員撰寫開發紀錄，有個考量是，引導學員練習展現自己的想法。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

Queue Implementation

`q_new`

一開始先用 malloc() 要一個 list_head 大小的空間，如果 malloc() 失敗就回傳 NULL。再用 INIT_LIST_HEAD() 這個 macro 來初始化我們的 list_head ，最後把 list_head 回傳。

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

可以在 list.h 找到 INIT_LIST_HEAD 的定義，是將傳進來的 head 的 next 跟 prev 都指向自己。

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`

q_free 這個 function 會將傳進來的整條 queue 的空間釋放掉，我這邊使用到 list_for_each_entry_safe() 這個 macro 來實做，所以先介紹一下這個 macro。

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

這個巨集會迭代存取每一個 list 裡面的 entries ，多用一個 safe 的指標來存 entry 的下一個位址，可以在刪除 entries 時不影響到後面的走訪操作。

巨集裡使用到的 list_entry 跟 container_of 是一樣的，不知為什麼要再定義一樣的一個巨集？

container_of 在 Linux 核心其他地方可用，這裡配合 List API 命名風格，保持 list_ 開頭

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

Macro 裡面使用到的 list_entry 可以從結構體裡面的 list 位址來得知整個結構體的位址，這樣就可以從 list_head 迭代過程中對結構體進行操作。

在剛進這個函式時，先判斷要刪除的佇列是否為 NULL，是的話舊部需要做接下來的動作。這邊使用了 list_for_each_entry_safe 對每個 element_t 直接做存取，先將 element_t 裡面的 list_head 指標從 list 之中移除，再把 element_t 佔用的空間釋放。

使用 list_del_init 可以在 remove 後，把 next 跟 prev 都指向自己，不像 list_del 會是指向原本的下一個。可以從已經 remove 的 list_head 指標去存取下一個或前一個節點是不安全的行為。

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *li, *tmp;
    list_for_each_entry_safe (li, tmp, l, list) {
        list_del_init(&li->list);
        free(li->value);
        free(li);
    }
    free(l);
}

`q_insert_head` & `q_insert_tail`

這個函式會在佇列的頭端或是尾端插入一個新的元素，並且也會把指定的 value 值也一併傳進來。

一開始我先呼叫 malloc() 建立一個新的 element_t，如果 malloc() 失敗就回傳 false 中斷此次的操作。因為 element_t 裡的 value 也是指標，所以也要為 value 要一段空間來存字串，故我使用了 strlen() 來計算我需要多少 byte 來存這次的 value。但是因 strlen() 並不會將 '\0' 也算進去，所以最後要求的空間需要再 +1。

The strlen() function calculates the length of the string pointed to by *s, excluding the terminating null byte ('\0'). It returns the number of bytes in the string pointed to by *s.

改進引言的完整度。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

配置完 value 需要的空間後就是要將字串複製過去，我使用了 strncpy() 來從原本的指標 s 複製到新的指標 value 。

The strcpy() function copies the string pointed to by src, including
the terminating null byte ('\0'), to the buffer pointed to by dest.
The strncpy() function is similar, except that at most n bytes of src
are copied.

strncpy 會複製最多 n 個位元組到 destination ，如果要複製的字串長度超過 n bytes，而其中沒有 '\0'，那 destination 的複製結果也不會是 null-terminated。
這邊因為 strncpy 的 n 是 strlen(s)+1 ，所以會大於要複製字串s 的長度，故不用考慮複製的結果不會沒有'\0'。最後再將這次運算的結果 true 回傳就完成。

bool q_insert_head(struct list_head *head, char *s)
{
    // construct new element
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    new->value = malloc(strlen(s) + 1);
    if (!new->value) {
        free(new);
        return false;
    }
    INIT_LIST_HEAD(&new->list);
    strncpy(new->value, s, strlen(s) + 1);

    // add element to queue head
    list_add(&new->list, head);
    return true;
}

`q_reverse`

這個函式會將傳進來的佇列反轉，回傳頭變尾、尾變頭的結果。

一開始先檢查佇列是不是 null、 empty 或是只有一個節點，是的話就不需要再反轉，畢竟就一個點或是空的。在每個迴圈中，先將原本的 next 存起來safe=li->next，再將 next 跟 prev 做互換，之後把剛剛存的 safe 設定成下一個 node 就可以對每個 node 做 reverse。

在 list_for_each 巨集結束後要對 head 也做反轉，因為在巨集裡可以看到 for loop initital 直接設定 li = head->next，所以最後也要把 head 反轉。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *li, *safe;
    list_for_each_safe (li, safe, head) {
        li->next = li->prev;
        li->prev = safe;
    }
    safe = head->next;
    head->next = li->prev;
    head->prev = safe;
}

`q_remove_head` & `q_remove_tail`

開頭先檢查佇列是否為 NULL 或是空，是的話就回傳 NULL。接著用 list_first_entry() 或 list_last_entry() 來取得頭或尾的元素 target。使用 list_del_init() 安全地將這個節點 remove，再使用 strncpy 複製最多 bufsize - 1 個字元至 *sp，最後將 remove 的節點回傳。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target = list_first_entry(head, element_t, list);
    list_del_init(&target->list);
    if (sp) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return target;
}

`q_delete_mid`

這個函式會將中間的節點刪除，如果是偶數個節點會挑第

⌊ \frac{x}{2} ⌋

項元素進行刪除。

一開始先判斷這個佇列是否為 NULL 或是否為空，是的話就回傳 false。

接下來就是挑選中間的元素，我的方法是使用兩個指標 left、right 從佇列的頭跟尾往中間移動，因為我移動的順序是先移動 right 再移動 left，所以兩指標互相碰面的情況只有兩種，雙方各移動一格碰面或是 left 移動一格後跟 right 碰面，故這樣的結果就會是挑第

⌊ \frac{x}{2} ⌋

項元素。最後再將選到的節點刪除，並回傳 true。

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 = list_get_mid(head);
    element_t *tmp = list_entry(mid, element_t, list);
    list_del_init(&tmp->list);
    free(tmp->value);
    free(tmp);
    return true;
}

struct list_head *list_get_mid(struct list_head *head)
{
    struct list_head *left = head, *right = head;
    while (!(right->prev == left || right->prev == left->next)) {
        left = left->next;
        right = right->prev;
    }
    return right->prev;
}

`q_sort`

這個函式是我花比較長時間的地方，因為我對雙向鏈結串列的運用還不是很熟悉，所以在對每個節點進行處理都要思考一下，把圖畫出來後才比較放心自己的程式沒有寫錯。

我使用的演算法是 merge sort，會選擇 merge sort 的原因是因為 merge sort 對非連續的記憶體的操作比起其他演算法更友善，比較不需要 random memory access。

Merge sort 分為兩大部份: divide 跟 conquer，我將這兩個步驟各寫成一個函式，讓我比較好了解我需要完成的功能。

在 Divide 的部份我使用了內建的函式 list_cut_position() 將一個佇列分成兩個小的佇列 head 跟 head2。Conquer 的部份我從 head 的角度去思考，每次的迴圈我都會找到 head 現在要插入 head2 元素的位置，找到 head2 比 head 小的元素後，使用 list_del_init() 與 list_add_tail() 將要插入 head 的元素從 head2 佇列移除，再將他插入至 head 佇列的尾端。

額外新增

在 google 搜尋了一下 How to improve my merge sort，看到可以在排序前先檢查看看佇列是否已經排序完成，所以我在 q_sort() 開頭增加了一個判斷式 list_check_sorted()。這個判斷式會檢查佇列是否已經排序好，並回傳 1 已經排列好跟 0 未排列。如果已經排列好，那後續的操作就不需要了。

int list_check_sorted(struct list_head *head)
{
    element_t *el;
    char *prev_val = list_first_entry(head, element_t, list)->value;
    list_for_each_entry (el, head, list) {
        if (strcmp(el->value, prev_val) < 0)
            return 0;
        prev_val = el->value;
    }
    return 1;
}

void q_sort(struct list_head *head)
{
    if (!head || q_size(head) <= 1)
        return;
    if (list_check_sorted(head) == 1)
        return;
    LIST_HEAD(head2);
    list_cut_position(&head2, head, list_get_mid(head));
    q_sort(head);
    q_sort(&head2);
    merge(head, &head2);
}


void merge(struct list_head *head, struct list_head *head2)
{
    struct list_head *i_head = head->next, *i_head2, *next;
    for (i_head2 = head2->next; !list_empty(head2); i_head2 = next) {
        while (i_head != head &&
               strcmp(list_entry(i_head, element_t, list)->value,
                      list_entry(i_head2, element_t, list)->value) < 0) {
            i_head = i_head->next;
        }
        if (i_head == head)
            list_splice_tail_init(head2, i_head);
        else {
            next = i_head2->next;
            list_del_init(i_head2);
            list_add_tail(i_head2, i_head);
        }
    }
}

`q_swap`

一開始先判斷這個佇列是否為 NULL 或數量是否少於1，是的話就結束並不做任何運算。因為這個函式式要將每兩對進行交換，所以我使用 q_size()/2 來算出我需要交換多少對，再透過 for 迴圈對每組進行交換。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || q_size(head) <= 1)
        return;
    struct list_head *li = head->next;
    int pairs = q_size(head) / 2;
    for (int i = 0; i < pairs; ++i) {
        element_t *cur = list_entry(li, element_t, list);
        element_t *next = list_entry(li->next, element_t, list);
        char *tmp = cur->value;
        cur->value = next->value;
        next->value = tmp;
        li = li->next->next;
    }
}

`q_delete_dup`

這個函式會將相同的元素全部刪除，佇列剩下的元素都會是不同的。

先從頭開始檢查現在的節點跟下一個節點是不是相同，如果相同的話就刪除此節點，再往下一個節點檢查是否又相同。

因為一直使用到 strcmp() 兩個節點的字串，所以將此函式用巨集的方式定義在外面，使用的時候再呼叫就好，可以讓 while 裡的判斷較易讀。

#define list_value_cmp(li1, li2)                    \
    strcmp(list_entry(li1, element_t, list)->value, \
           list_entry(li2, element_t, list)->value)

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;

    struct list_head *li = head->next, *safe;
    while (li != head) {
        struct list_head *cur = li;
        if (cur->next != head && !list_value_cmp(cur, cur->next)) {
            while (cur->next != head && !list_value_cmp(cur, cur->next)) {
                safe = cur->next;
                list_free_node(cur);
                cur = safe;
            }
            safe = cur->next;
            list_free_node(cur);
            cur = safe;
        }
        li = cur->next;
    }
    return true;
}

`q_shuffle`

洗牌參考了 Fisher-Yates Algorithm，演算法的虛擬碼如下:

for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

大致上可以想成將陣列分成未洗牌的陣列跟完成洗牌的陣列，一開始完成洗牌的陣列是空的，全部的元素都在未洗牌的陣列裡。在未洗牌的陣列中隨機挑選一個元素跟最後一個元素互換，這樣就完成一個元素的洗牌了。
現在未完成洗牌的元素有 n-1 個，而完成洗牌的元素有 1 個。一直做下去將所有未完成洗牌陣列裡的元素都換到完成洗牌陣列裡去就大功告成了。

void list_value_swap(struct list_head *li1, struct list_head *li2)
{
    element_t *tmp1 = list_entry(li1, element_t, list);
    element_t *tmp2 = list_entry(li2, element_t, list);
    char *tmp = tmp1->value;
    tmp1->value = tmp2->value;
    tmp2->value = tmp;
}

void q_shuffle(struct list_head *head)
{
    int size = q_size(head);
    if (!head || size <= 1)
        return;
    for (int i = size - 1; i > 0; --i) {
        int j = rand() % i;
        struct list_head *li = head->next, *tail = head;
        for (int tmp = j; tmp > 0; --tmp)
            li = li->next;
        for (int tmp = size - i; tmp > 0; --tmp)
            tail = tail->prev;
        list_value_swap(li, tail);
    }
}

2022q1 Homework1 (lab0)

開發環境

作業要求

Queue Implementation

q_new

q_free

q_insert_head & q_insert_tail

q_reverse

q_remove_head & q_remove_tail

q_delete_mid

q_sort

額外新增

q_swap

q_delete_dup

q_shuffle

Read more

Linux 紅黑樹探討

Git 基礎教學

提交第一份 Patch 到 Linux Kernel

2022q1 Homework6 (ktcp)