2024q1 Homework1 (lab0)

contributed by < ranvd >

Reviewed by Shawn531

開發紀錄中可以加入 commit 連結以便追蹤。
善用 diff

Reviewed by `ShawnXuanc`

可以減少完整程式碼的張貼

程式碼有善用 list 巨集以及將重複的程式碼再利用

Reviewed by `Shiang1212`

有幾份 commit 沒有撰寫 commit message。即便該 commit 只有簡單的程式更動，仍應該在 commit message 中描述程式碼更動的重點，加速其他開發人員理解這份程式更動的脈絡，進而提高專案的可維護性。

開發環境

$ uname -r
5.15.133.1-microsoft-standard-WSL2

$ 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):                  20
  On-line CPU(s) list:   0-19
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i7-12700H
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  10
    Socket(s):           1
    Stepping:            3
    BogoMIPS:            5376.00

針對指定佇列操作的實作

`q_new`

改進你的漢語表達。

一開始我沒有檢查 malloc 的回傳結果，因此當 malloc 失敗時回傳的 NULL 會導致在執行 INIT_LIST_HEAD 巨集內的程式碼時對 null pointer 取值，進而引發 segmentation fault。因此增加了以下程式碼檢查 malloc 是否成功。

INIT_LIST_HEAD 不是巨集。

struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(new);
+    if (!new)
+        return NULL;

    return new;
}

`q_free`

因為 head 有可能是 null pointer，因此在執行 q_free 動作前應該先檢查 head 是否為 NULL，否則會觸發 segmentation fault。

void q_free(struct list_head *head)
{
    element_t *e, *s;
    
+    if (!head)
+        return;
    list_for_each_entry_safe (e, s, head, list) {
        q_release_element(e);
    }

    free(head);
}

`q_insert_head` 與 `q_insert_tail`

由於一開始沒注意到 strdup 也透過巨集的方式替換成專案內的實作，在 make test 時一直想不透為什麼檢查了 malloc 的回傳值後 q_insert_head 還會觸發 segmentation fault。在發現 test_strdup 內也使用到 test_malloc 後就增加下列程式碼，透過檢查 new->value 是否為 null pointer 來判斷 strdup 是否有執行成功。(q_insert_tail 也有相同的更動)

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    new->value = strdup(s);
+    if (!new->value) {
+        free(new);
+        return false;
+    }
    list_add(&new->list, head);
    return true;
}

閱讀 alanjian85 時，看到老師在多處提醒應該盡量重複使用程式碼，因此以下將 q_insert_tail 改寫，重複使用 q_insert_head 中的程式碼。

bool q_insert_tail(struct list_head *head, char *s)
{
    return q_insert_head(head->prev, s);
}

`q_remove_head` 與 `q_remove_tail`

因為 strncpy 會將字串中的前 n 個字元複製到指定的空間，因此當要複製的字串超過 bufsize 時，會使得指定指定的空間中的字串沒有 '\0'，因此後續如果在執行 printf, strcpy 等函式的時候會出現錯誤。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    struct list_head *rm = head->next;
    list_del(rm);

    if (sp){
        strncpy(sp, list_entry(rm, element_t, list)->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return list_entry(rm, element_t, list);
}

也在閱讀 alanjian85 時，看到老師在多處提醒應該盡量重複使用程式碼，因此以下將 q_remove_tail 改寫，重複使用 q_remove_head 中的程式碼。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return q_remove_head(head->prev->prev, sp, bufsize);
}

`q_delete_mid`

使用快慢指標來找出佇列中的中間點。在重新閱讀自己的實作後，發現 head == head->next 應該使用 list.h 內的 list_empty 替代，以提高程式碼的可讀性。

bool q_delete_mid(struct list_head *head)
{
-    if (!head || head == head->next)
+    if (!head || list_empty(head))
        return false;

    struct list_head *slow, *fast;

    fast = head;
    list_for_each (slow, head) {
        if (fast->next == head || fast->next->next == head)
            break;
        fast = fast->next->next;
    }

    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}

`q_reverse`

透過 list.h 提供的介面 list_move 與 list_for_each_safe 可以很方便的實作 q_reverse 的功能。

void q_reverse(struct list_head *head)
{
    struct list_head *li, *sa;
    list_for_each_safe (li, sa, head)
        list_move(li, head);
}

`q_reverseK`

由於 q_reverseK 函式要求在佇列中每 K 個節點要進行反轉，因此我將每 k 佇列中的節點放到暫時的佇列 tmp 中，並透過上面提到的 q_reverse 函式將佇列反轉。反轉過後的佇列可以使用 list.h 中提供的介面 list_splice_tail 放到新的佇列 result 中，這樣可以避免一個一個加入節點。

void q_reverseK(struct list_head *head, int k)
{
    if (k <= 0)
        return;

    struct list_head result, tmp;
    INIT_LIST_HEAD(&result);
    INIT_LIST_HEAD(&tmp);

    while (!list_empty(head)) {
        struct list_head *p = head->next;
        for (int i = 1; i < k && p != head; i++) {
            p = p->next;
        }

        list_cut_position(&tmp, head, (p == head) ? p->prev : p);
        if (p != head)
            q_reverse(&tmp);

        list_splice_tail(&tmp, &result);
    }

    list_splice(&result, head);
}

`q_swap`

在閱讀 yanjiew 時，看到 yanjiew 的 q_swap 的實作後，發現 q_swap 要求每兩個節點相互交換位置，因此可以視為 q_reverseK(head, 2)，因此將實作改成以下方式。

void q_swap(struct list_head *head)
{
    q_reverseK(head, 2);
}

`q_descend` 與 `q_ascend`

q_descend 與 q_ascend 要求剩下在佇列中的節點要符合嚴格的遞減/遞增序列，以下以 q_descend 作範例。由於 q_descend 要求佇列符合嚴格的遞減序列，因此可以得知，對於任意一個在佇列中的節點，其前面的節點必定要大於自己，且其後面的節點必定小於自己。因此可以從佇列的後面開始遍歷整個佇列，在過程中用指標 max 紀錄目前遇到的最大值的位置。如果在遍歷的過程中 max 有被更動即代表上個 max 與現在 max 的節點符合嚴格遞減序列的要求；反之，如果再遍歷的過程中 max 沒有被更動即代表 max 與現在走訪到的節點不符合嚴格遞減序列，因此要將目前走訪到的節點從佇列中移除。

int q_descend(struct list_head *head)
{
    struct list_head *n, *safe, *max = head->prev;
    int size = 1;
    for (n = max->prev, safe = n->prev; n != head;
         n = safe, safe = safe->prev) {
        if (strcmp(list_entry(n, element_t, list)->value,
                   list_entry(max, element_t, list)->value) > 0) {
            size++;
            max = n;
        } else {
            list_del(n);
            q_release_element(list_entry(n, element_t, list));
        }
    }
    return size;
}

q_ascend 與 q_descend 很像，只需將判斷式從 > 0 改成 < 0 即可，目前想到的重複利用程式碼的方式為使用巨集來做代換。不過這樣只有看起來程式碼比較少，實際上在巨集展開後是一樣的，因此目前沒有實作。

`element_t_cmp`

因為後續 q_sort 與 q_merge 需要考慮到不同的排序方式(由 descned 變數控制)，因此實作一個比較函式來統一回傳的介面對後續的實作比較方便，程式也可以保持較高的可讀性。

根據 man 3 strcmp

The strcmp() and strncmp() functions return an integer less than, equal to, or greater than zero if s1 (or the first n bytes thereof) is found, respectively, to be less than, to match, or be greater than s2.

由敘述只能得知當兩個不同的字串 s1 與 s2 放到 strcmp 的結果可能是大於 0 或小於 0，並不能確定是否為 1 或 -1，因此此函式也會遵循這個規定。

首先分析可能發生的情況

a > b 且 descend = 1：回傳一個大於 0 的數值
a > b 且 descend = 0：回傳一個小於 0 的數值
a == b：回傳 0
a < b 且 descend = 1：回傳一個小於 0 的數值
a < b 且 descend = 0：回傳一個大於 0 的數值

因此可以透過將 descend << 31 與 strcmp 的結果做 XOR 運算後做 - 運算來取得正確的會傳結果。例如 a < b 且 descned=1 時，回傳結果應該要小於 0，透過 strcmp(a, b) ^ descend << 31，使得最高位元因為 XOR 運算被設為 0，此時結果大於 0，最後加上 - 運算就可使結果小於 0。

static int element_t_cmp(struct list_head *a, struct list_head *b, bool descend)
{
    char *a_value = list_entry(a, element_t, list)->value;
    char *b_value = list_entry(b, element_t, list)->value;

    return -(strcmp(a_value, b_value) ^ (descend << 31));
}

`q_sort`

在 q_sort 實作中採用部分 timsort 的想法與 buttom-up 的 merge sort 的合併方式，一開始會將佇列分成多個 run，每個 run 之間使用 prev 指標來連接，形成堆疊的結構，如下圖。每個 run 皆會符合 descend 變數中的要求，如果 descend==1 則 run 以遞減方式排列；反之，以遞增方式排列。當將所有佇列的節點分成不同的 run 後就會進行 run 之間的合併，合併的方式為每兩個連續的 run 一組，並以組為單位合併，以此方式不斷迭代直到堆疊中只剩下一個 run。

假設有 n 個 run，則在第一次迭代後會剩下
$⌈ \frac{n}{2} ⌉$ 個 run，第二次迭代剩下
$⌈ \frac{n}{4} ⌉$ ，以此類推直到剩下一個 run 在堆疊中。

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return;

    /* convert circular-linked list into linear-linked list */
    struct list_head *list = head->next, *stk_ptr = NULL, *tmp;
    list_del_init(head);
    list->prev = list->prev->next = NULL;

    int stk_size = 0;
    while (list) {
        tmp = find_run(&list, descend);
        stk_size++;
        tmp->prev = stk_ptr;
        stk_ptr = tmp;
    }

    list = merge_force_collapse(stk_ptr, descend);

    for (struct list_head *safe = list->next;;) {
        list_add_tail(list, head);
        list = safe;
        if (!list)
            break;
        safe = safe->next;
    }
}

在合併堆疊中的 run 的過程中，除了需要紀錄堆疊的開頭外，也需要將合併後的 run 放回堆疊中的正確位置，為了省去特殊情況的判斷，在連接 run 與紀錄堆疊的開頭時可以使用指標的指標來實作。

static struct list_head *merge_force_collapse(struct list_head *stk,
                                              bool descend)
{
    while (stk && stk->prev) {
        struct list_head **iptr = &stk;
        while ((*iptr) && (*iptr)->prev) {
            (*iptr) = merge_at(*iptr, descend);
            iptr = &(*iptr)->prev;
        }
    }
    return stk;
}

由於在開發 q_sort 過程中一直觸發 segmentation fault，因此使用 GDB 進行除錯。在過程中一直遇到 ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient 的問題。透過 GDB 的 bt、up、down 追蹤程式碼後發現是因為執行時間過長，導致系統發出 SIGALRM 的訊號。從 GDB 5.4 Signals 的手冊可以看到，GDB 可以針對不同的 Signal 做出不同的應對方式，在將 GDB 對 SIGALRM 的行為設定為 ignore 後就可以正常除錯。

不過在後續閱讀 README.md 的時候發現，文件已經告知使用 ./script/debug -d 就可以直接正常的除錯。

merge_list

用來合併兩個環狀鏈結串列，使用兩層迴圈，外層走訪鏈結串列 from，內層走訪鏈結串列 to，因為呼叫 merge_list 的前提是兩個鏈結串列是已經排序好的，因此內層的迴圈會透過先前提到的 element_t_cmp 函式來判斷 cmp_ptr 是否指向第一個 list 可以插入的位置，等到找到位置後將 list 從 from 中移出並加入插入至 cmp_ptr 前。當兩個迴圈都走訪完後，如果 from 還有節點沒有被放入 to，則將剩下的節點全部放入 to 的尾端。

static void merge_list(struct list_head *to,
                       struct list_head *from,
                       bool descend)
{
    struct list_head *list, *safe, *cmp_ptr = to->next;
    if (list_empty(from))
        return;

    list_for_each_safe (list, safe, from) {
        while (cmp_ptr != to && element_t_cmp(cmp_ptr, list, descend) > 0) {
            cmp_ptr = cmp_ptr->next;
        }

        if (cmp_ptr == to)
            break;

        list_del(list);
        list_add_tail(list, cmp_ptr);
    }

    list_splice_tail_init(from, to);
}

q_merge

這裡的 merge 因為要求需要將所有的鏈結串列合併至第一個，因此這個實作並沒有太多的考量，而是以實作上方便做優先，直接將除了第一個以外的鏈結串列合併至第一個鏈結串列。

int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    struct list_head *f = head->next, *m = f->next;

    for (; f != head && m != head; m = m->next) {
        queue_contex_t *to = list_entry(f, queue_contex_t, chain);
        queue_contex_t *from = list_entry(m, queue_contex_t, chain);
        merge_list(to->q, from->q, descend);
    }

    return q_size(list_entry(f, queue_contex_t, chain)->q);
}

既然你選擇合併排序演算法，你要如何確保輸入的資料涵蓋合併排序演算法的最差狀況呢？

確保 linenoise 套件在 web 啟動時正常執行

目前只有使用 firefox 瀏覽器測試成功，使用 Chrome 會出現非預期錯誤，整個程式會卡在 web_recv，變成只剩下 web 功能，目前沒辦法解決。

原本在啟動 web 功能後 linenoise 的功能會因為 use_linenoise 被設定為 false 而關閉，因此我的想法是直接忽略這項變數，在 linenoise 內使用 select 系統呼叫同時監控 socket file descriptor 與 stdin file descriptor，就如同作業中的提示。

為了能夠在不同的檔案中存取到 socket file descriptor，應將 web_fd 以一般變數的方式宣告。並且在執行 interpret_cmd 後應將建立的連線 (web_connfd) 關閉，防止 client 端無盡的等待。

-static int web_fd;
+int web_fd = -1;

bool run_console(char *infile_name)
{
    ... 略
    if (!has_infile) {
        char *cmdline;
-        while (use_linenoise && (cmdline = linenoise(prompt))) {
+        while (cmdline = linenoise(prompt)) {
            interpret_cmd(cmdline);
            line_history_add(cmdline);       /* Add to the history. */
            line_history_save(HISTORY_FILE); /* Save the history on disk. */
            line_free(cmdline);
            while (buf_stack && buf_stack->fd != STDIN_FILENO)
                cmd_select(0, NULL, NULL, NULL, NULL);
            has_infile = false;
+            if (web_connfd){
+                close(web_connfd);
+                web_connfd = 0;
+            }
        }
-        if (!use_linenoise) {
-            while (!cmd_done())
-                cmd_select(0, NULL, NULL, NULL, NULL);
-        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }
}

接著是修改 linenoise 套件的內容，因為 stdin 與 socket 這兩邊的 file descriptor 隨時有可能有輸入，因此選擇使用 select 來等待可執行相應動作的 file descriptor。不過這兩個 file descriptor 的輸入行為有很大的區別，socket 這邊的輸入會是完整的指令請求，不存在指令命令只打到一半情況，例如使用 web 的方式執行 new，傳送過去的指令命令就只能是 new，如果只傳了 ne 則會因為沒有辦再修改而直接跳出錯誤；反之，stdin 這邊的輸入可以在任何情況下針對目前還沒傳送出去的指令命令做修改，且由於需要支援自動補齊，所以每當 stdin 有任何輸入時程式都應該做出相對應的反應。

「指令」？

更正：command 的中文翻譯是命令

因此我在 linenoise 中宣告了兩個新變數，第一個是 struct line_state 靜態全域結構 g，用來備份 stdin 輸入時的狀態；第二個是靜態 bool 變數 need_swap 用來紀錄上一次處理的資料是否是來自 socket 端，如果是的話 need_swap = 1。

static struct line_state g;
static bool need_swap = 0;

如果當 stdin 輸入到一半時 socket 要求建立連線，就可以先將目前的狀態存至 g 中，並處理 socket 的請求。如果目前處理的是 socket 連線，則 need_swap = 1，這代表下一次在做 select 之前需要先將在 g 的資料寫回 l 作為目前的狀況。

        } else if (FD_ISSET(web_fd, &read_fds)) {
            /* Copy l into g which is used for store current state*/
            line_state_write(&g, &l);
            need_swap = 1;

            FD_CLR(web_fd, &read_fds);
            struct sockaddr_in clientaddr;
            socklen_t clientlen = sizeof(clientaddr);
            ...建立連線

在處理完 socket 的請求後，依據 need_swap 內的數值選擇是否要將 g 的資料寫回 l，即恢復被中斷前的狀態，且應該要將 l.buf 內的資料輸出至畫面中，讓使用者知道自己剛才打的指令內容，這樣即使輸入到一半被中斷，stdin 端的功能不會受影響。

        if (need_swap) {
            need_swap = 0;
            line_state_write(&l, &g);
            if (write(l.ofd, l.buf, l.len) == -1)
                ;
        }

        ...略
        int result = select(nfds, &read_fds, NULL, NULL, NULL);

執行結果會如下面所展示。當使用者輸入 my input buffer 時，有一個 socket 端的請求，會先保存目前的狀態，並處理 socket 的執行內容。接著，恢復剛才 socket 進入前的狀態，並將 l.buf 的內容輸出至介面 (即 my input buffer)。

cmd> web
listen on port 9999, fd is 3
cmd> my input buffer
Warning: Calling insert head on null queue
l = NULL
cmd> my input buffer

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

收到

~~![image](https://hackmd.io/_uploads/S1ZHTUS0T.png)~~

重新張貼「關鍵」程式碼。

目前已知此實作的缺陷

除了在一開始提到程式無法在 chrome 瀏覽器上正常的執行外，當按下 tab 鍵使用自動補齊功能時，為了維持功能的正常運作，在 complete_line 函式中會再次讀取一個字元，作為後續動作的執行依據。因此當按下 tab 鍵時，網頁端的請求會被 block 住，要等到 stdin 再次按下除了 tab 以外的鍵才可以。

static int complete_line(struct line_state *ls)
{
    line_completions_t lc = {0, NULL};
    char c = 0;

    ... 略

            int nread = read(ls->ifd, &c, 1);
            if (nread <= 0) {
                free_completions(&lc);
                return -1;
            }

            switch (c) {
            case 9: /* tab */
                i = (i + 1) % (lc.len + 1);
                if (i == lc.len)
                    line_beep();
                break;
            case 27: /* escape */
                /* Re-show original buffer */
                if (i < lc.len)
                    refresh_line(ls);
                stop = true;
                break;
            default:
                /* Update buffer and return */
                if (i < lc.len) {
                    int nwritten =
                        snprintf(ls->buf, ls->buflen, "%s", lc.cvec[i]);
                    ls->len = ls->pos = nwritten;
                }
                stop = true;
                break;
    ... 略
}

研讀 lib/list_sort.c

以下當變數不為陣列時，使用 count[k] 表示第 k 個 bit；count[k-1:0] 表示第 k-1 到第 0 個 bits。

從以下註解可以得知 list_sort 為 2:1 balance merge sort。即意，在等待合併的鏈結串列中，有兩個長度為

2^{k}

的鏈結串列時，且在這鏈結串列之後的資料個數總和如果等於

2^{k}

時就將這兩個鏈結串列進行合併成長度為

2^{k + 1}

的鏈結串列。

 * This mergesort is as eager as possible while always performing at least
 * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
 * merged to a size-2^(k+1) list as soon as we have 2^k following elements.

count 為 list_sort 中用來記錄目前已經放入等待合併的資料個數。根據以下註解可以得知，當 count 數量增加，導致 count[k]==1 且 count[k-1:0]==0 時，代表有兩個長度為

2^{k}

的鏈結串列可以被合併成

2^{k + 1}

。除了 count[k] 第一次等於 1 時例外 (即 count 為 2 的冪時)。

 * Each time we increment "count", we set one bit (bit k) and clear
 * bits k-1 .. 0.  Each time this happens (except the very first time
 * for each bit, when count increments to 2^k), we merge two lists of
 * size 2^k into one list of size 2^(k+1).

註解中提到，需要透過 count[k-1] 與 count[n:k+1] 的資訊得知目前有幾個長度為

2^{k}

的鏈結串列在等待合併。因此可以分為六種不同的情況，以下 x 代表任意的數值；y 代表不為 0 的數值，且如果 k==0 時 -1 bit 當作是 1。其中第五種情況 (y01x) 最為重要，因為代表有兩個長度為

2^{k}

的鏈結串列在等待合併，當發生上面提到的 count[k]==1 且 count[k-1:0]==0 時就將兩個

2^{k}

鏈結串列合併。考慮 count 為 (10101)₂ 時，等待合併的鏈結串列為 8+8+2+2+1，此時同時在 k=3 與 k=1 的位置皆出現第五種 y01x 的情況，但再將 count+1 後 count 為 (10110)₂ 這時只有 k=1 的位置發生了 count[1]==1 且 count[0:0]==0 的情況，因此將

2^{1}

合併，等待合併的鏈結串列變成 8+8+(4)+1+1。

 * The number of pending lists of size 2^k is determined by the
 * state of bit k of "count" plus two extra pieces of information:
 *
 * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
 * - Whether the higher-order bits are zero or non-zero (i.e.
 *   is count >= 2^(k+1)).
 *
 * There are six states we distinguish.  "x" represents some arbitrary
 * bits, and "y" represents some arbitrary non-zero bits:
 * 0:  00x: 0 pending of size 2^k;           x pending of sizes < 2^k
 * 1:  01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
 * 2: x10x: 0 pending of size 2^k; 2^k     + x pending of sizes < 2^k
 * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
 * 4: y00x: 1 pending of size 2^k; 2^k     + x pending of sizes < 2^k
 * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k

由上面的例子中可以知道，當有同時有兩個不同的數字

k

與

k^{'}

使得正在等待合併的鏈結串列中分別有兩個

2^{k}

與

2^{k^{'}}

時，會從小的數字開始合併。可以看到，list_sort 中透過 for 迴圈將最低位的 0 找出來後，就去判斷 bits 是否為 0，如果不為 0 就代表符合 y01x 的情況，因為 count 會在 while 迴圈最後時加一，使得 count[k]==1 且 count[k-1:0]==0，因此這邊可以先進行合併。

	do {
		size_t bits;
		struct list_head **tail = &pending;

		/* Find the least-significant clear bit in count */
		for (bits = count; bits & 1; bits >>= 1)
			tail = &(*tail)->prev;
		/* Do the indicated merge */
		if (likely(bits)) {
			struct list_head *a = *tail, *b = a->prev;

			a = merge(priv, cmp, b, a);
			/* Install the merged result in place of the inputs */
			a->prev = b->prev;
			*tail = a;
		}

		/* Move one element from input list to pending */
		list->prev = pending;
		pending = list;
		list = list->next;
		pending->next = NULL;
		count++;
	} while (list);

當所有的節點都已經從 list 中拿出，代表所有的節點都已經在 pending 中等待合併。因此這時候需要將在 pending 上的多個鏈結串列合併成一個鏈結串列。這時會從長度最小的開始合併，同時因為一開始的限制 (當

2^{k}

合併成

2^{k + 1}

時，合併與未合併的鏈結串列長度總和必須要有

3 \times 2^{k}

)，使得在最差的情況下只會是兩個長度為 2:1 的鏈結串列做合併。

	/* End of input; merge together all the pending lists. */
	list = pending;
	pending = pending->prev;
	for (;;) {
		struct list_head *next = pending->prev;

		if (!next)
			break;
		list = merge(priv, cmp, pending, list);
		pending = next;
	}

論文閱讀

在 Queue-Mergesort 中利用 Huffman encoding 的方式證明了在最差的情況下，Queue-Mergesort 是 Optimal 的，且 Top-down mergesort 也是。接著在 The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules 中提到不同的 mergesort 的比較次數可以寫成

f_{n} = f_{τ (n)} + f_{n - τ (n)} + g_{n}

的遞迴關係式，其中

g_{n}

代表合併時所需的比較次數。根據不同的實作可以將

τ (n)

分成三種

$τ (x) = ⌊ \frac{n}{2} ⌋$ ：Top-down mergesort
$τ (x) = 2^{⌈ l o g_{2} \frac{n}{2} ⌉}$ ：Buttom-up mergesort
$τ (x) = 2^{⌊ l o g_{2} \frac{2 n}{3} ⌋}$ ：Queue-mergesort

在論文中提到這個

2^{⌊ l o g_{2} 2 n / 3 ⌋}

是一個特別的數字，可以使最差的情況下要合併的兩邊資料長度為 2:1，如果使用其他的數字就可能導致

f_{n}

在分割時兩邊的差距過大。

Note that
$2^{⌊ l o g_{2} 2 n / 3 ⌋}$ is the unique power of two lying between
$n / 3$ and
$2 n / 3$ and that the choice of rationals other than
$2 / 3$ will not be more balanced. For example, if
$2^{⌊ l o g_{2} n / 2 ⌋}$ or
$2^{⌊ l o g_{2} 5 n / 9 ⌋}$ then the sizes of two subproblems are
$(2, 5)$ for
$n = 7$ while the balanced power-of-two gives
$(3, 4)$

因為 Queue-mergesort 可以表示成 Huffman Tree，因此在 On the Optimality of Huffman Trees 的內容可以套用至 Queue-mergesort，論文中說明 Huffman Tree 的遞迴關係中的 k 是

2^{⌊ l o g_{2} \frac{2 n}{3} ⌋}

而不是其他數字或

⌊ 2 n / 3 ⌋

。

$F (n) = 1 - q^{n} + min_{1 \leq k \leq n - 1} F (k) + F (n - k)$ Since the function
$f (n) = 1 - q^{n}$ is concave nondecreasing, the "power of 2" rule applies, and the optimal
$k$ is the power of 2 satisfying
$n / 3 \leq k < 2 n / 3$

最後透過 Geogebra 觀察函式在不同 n 時的數值，下圖中

f

代表

2^{⌊ l o g_{2} 2 n / 3 ⌋}

，

h

與

g

分別代表

2 n / 3

與

n / 3

。可以看到確實

f

會在

h

與

g

之間。這讓 mergesort 在合併兩個鏈結串列時可以維持在最差長度為 2:1 的情況。

不過論文中很多部分還不能理解，例如為什麼 Buttom-up mergesort 的數值是

2^{⌈ l o g_{2} \frac{n}{2} ⌉}

。還有許多推倒的過程不太能理解，只能記住結論而已。

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

2024q1 Homework1 (lab0)

Reviewed by Shawn531

Reviewed by ShawnXuanc

Reviewed by Shiang1212

開發環境

針對指定佇列操作的實作

q_new

q_free

q_insert_head 與 q_insert_tail

q_remove_head 與 q_remove_tail

q_delete_mid

q_reverse

q_reverseK

q_swap

q_descend 與 q_ascend

element_t_cmp

q_sort