2023q1 Homework1 (lab0)

contributed by < Ahsen-lab >

實驗環境

$ 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

作業要求

作業要求

queue.c 僅提供介面 (interface) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:

• 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
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
• q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
• q_reverseK: 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group
• q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;
• q_descend: 參閱 LeetCode 2487. Remove Nodes From Linked List
• q_merge: 合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 LeetCode 23. Merge k Sorted Lists

開發過程

注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！

jserv

q_new

建立新的「空」佇列，使用 malloc 配置記憶體空間給 head ，再用 INIT_LIST_HEAD 巨集來初始化 head ，需要注意 malloc 有可能會 fail，若配置記憶體空間失敗，則回傳 NULL 。

/*
 * 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

釋放佇列所佔用的記憶體

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

在佇列開頭新增一個新節點

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 和 harness.c 檔案中，可見到對記憶體管理所進行的實作，會追蹤記憶體配置和釋放的狀態，將原先的 malloc 與 free 使用 test_malloc 與 test_free 取代，因此在配置記憶體空間時，只可用 malloc 來配置空間。

選擇使用 strdup 來配置記憶體空間給字串是因為根據 strdup(3)，strdup 會使用 malloc 來配置記憶體給新的字串。

 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

在佇列尾端新增一個新節點

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

移除佇列開頭的節點

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

移除佇列尾端的節點

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，

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 和非連續記憶體 案例探討 : Leetcode 2095. 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 。

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 同學的作法。

使用 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 無須刪除。

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;
}

詳閱 CONTRIBUTING.md，避免 needDel 這樣違反一致程式碼風格的用法。

jserv

根據 CONTRIBUTING.md，使用 snakecase 風格來命名變數，變更如下:

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

善用 q_release_element 以縮減程式碼。need_del 可換為其他更符合題意的詞彙。

jserv

參考老師的建議

• 以 q_release_element 縮減程式碼
• 將變數 need_del 改名為 fund_dup 以符合題意
• 將指標 entry 和 safe 改名為 cur 和 tmp 等更易懂的名稱

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

最後放上修改後的程式碼

完整程式碼

/* 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 巨集來完成實作：

/* 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 中，就可達到交換佇列中鄰近的節點的目的。

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 巨集來將當前的節點移動到佇列的開頭，以此達到反向排列佇列的效果。

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 個節點為一組進行反向排列的目的。

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 。

/**
 * 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

保持一致的命名風格。

jserv

參考 案例探討: LeetCode 21. Merge Two Sorted Lists 中指標的指標的方式來實作此函式，用來合併兩個已排序的佇列。

指標用途：

• e1 、 e2 : 分別指向 l1 和 l2 當前所指向的節點所連接的 element
• merged_head : 這個指標用來指向合併後的新佇列。
• cur : 比較 l1 和 l2 兩個節點中的字串， cur 會指向字典序 ( lexicographically ) 較小的節點。
• merged_tail : 指向合併後的佇列的尾端。

完整程式碼

/* 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 會指向本身的下一個節點。

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 的步驟。

list_del_init(*merged_tail);
list_add_tail(*merged_tail, merged_head);
merged_tail = &(*merged_tail)->next;

4. 最後當迴圈結束時，將剩餘的節點全部串到新佇列的尾端，並回傳 merged_head 。

merged_head == l1->next ? list_append(l2, merged_head)
                    : list_append(l1, merged_head);
return merged_head;

merge_k_lists

參考 你所不知道的 C 語言: linked list 和非連續記憶體 中的 Merge Sort 的實作，以 Merge Sort 的方式來合併多個已排序的佇列。

首先，檢查 h 是否為空佇列，如果是則直接回傳 h，表示無需合併，這同時也是遞迴函式的截止條件。

if (list_empty(h))
    return h;

接著， Merge Sort 主要分為兩大步驟，分割和合併：

分割

使用前面提到的快慢指標的技巧來找出中間的節點，以便從中將佇列分割為兩個佇列，接著用遞迴的方式重複呼叫 merge_k_lists 函式，將佇列不斷分割為二，最後佇列將被分割為一個個單獨的節點。

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 函式來兩兩合併佇列，如此便可得到排序後的完整佇列。

return merge_two_lists(slow, fast);

以下為 merge_k_lists 函式的完整程式碼

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 併回到佇列的頭部，如此即可完成佇列的排序。

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。

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 會指向當前佇列的頭部。

/**
 * 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。

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;
}

注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！

jserv

整合網頁伺服器

修復 favicon.ico 的問題

因為部分瀏覽器會要求 request 中要提供網頁圖案的對應資訊，而原始程式中的 response 為：

char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";

其中並沒有包含關於 icon 的資訊。要修改這個問題，參考 解決 favicon.ico 的問題 ，在 cmd_select 函式中，將 http response 的內容改為

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

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 套件。

@@ -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 處理命令列輸入。

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

首先判斷是否有啟用 web 命令，若 web_fd > 0 ，表示網頁伺服器已啟用。

• 先將 socket 改為 non-blocking，防止程式停止接收使用者輸入：

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 可以同時處理來自使用者與網頁伺服器的命令。

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. 最後回傳接收到的命令的長度。

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 有事件發生，則代表來自命令列的命令，此時程式會讀取使用者輸入的命令，最後會回傳讀取的命令的長度。

else if (FD_ISSET(stdin_fd, &set)) {
    nread = read(l.ifd, &c, 1);
    if (nread <= 0)
        return l.len;
}

而若是 web 命令未啟動，即 web_fd <= 0 ，表示網頁伺服器未啟用，只需處理來自命令列的命令

else {
    nread = read(l.ifd, &c, 1);
    if (nread <= 0)
        return l.len;
}

完整的實作

@@ -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 和非連續記憶體 中對於 Fisher–Yates shuffle 演算法的 實作

• 首先在 console_init 函式中新增一個 shuffle 命令即描述

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. 顯示洗牌後的結果並回傳成功與否

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. 當所有輪的交換操作完成後，佇列中的元素順序被打亂，保存在原佇列中。

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?〉

Simulation 程式實作驗證流程

在 qtest 中執行 option simulation 1 可開啟 “simulation” 模式，測試時間複雜度。

首先觀察 do_option 函式中的程式碼

/* 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;
}