2023q1 Homework1 (lab0)

contributed by < 25077667 >

開發環境

$ neofetch --stdout
OS: Arch Linux x86_64 
Host: Z370M DS3H 
Kernel: 6.1.11-arch1-1 
Uptime: 10 hours, 56 mins 
Packages: 1343 (pacman) 
Shell: zsh 5.9 
Resolution: 2560x1440 
DE: GNOME 43.2 
WM: Mutter 
WM Theme: Adwaita 
Theme: Adwaita [GTK2/3] 
Icons: Adwaita [GTK2/3] 
Terminal: kgx 
CPU: Intel i5-9400F (6) @ 4.100GHz 
GPU: NVIDIA GeForce GTX 750 Ti 
Memory: 4537MiB / 32030MiB 

$ gcc -v

Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-linux-gnu/12.2.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /build/gcc/src/gcc/configure --enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++,d --enable-bootstrap --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/ --with-build-config=bootstrap-lto --with-linker-hash-style=gnu --with-system-zlib --enable-__cxa_atexit --enable-cet=auto --enable-checking=release --enable-clocale=gnu --enable-default-pie --enable-default-ssp --enable-gnu-indirect-function --enable-gnu-unique-object --enable-libstdcxx-backtrace --enable-link-serialization=1 --enable-linker-build-id --enable-lto --enable-multilib --enable-plugin --enable-shared --enable-threads=posix --disable-libssp --disable-libstdcxx-pch --disable-werror
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.2.1 20230201 (GCC)

改進 lab0-c 程式

In shorts:

• The current score is 100 since fork. (Feb. 28)

比較特別值得紀錄的是，想說先用 Copilot 鬼混一些簡單的問題
但是很不幸的：基礎題沒有一題是答對的

➜  lab0-c git:(master) ✗ make test                 
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-01-ops	0/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-02-ops	0/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-03-ops	0/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-04-ops	0/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-05-ops	0/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
ERROR: Not sorted in ascending order
ERROR: Duplicate strings are in queue or distinct strings are not in queue
ERROR: Freed queue, but 1 blocks are still allocated
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-06-ops	0/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-07-string	0/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-08-robust	0/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---	trace-09-robust	0/6

以 code review 的角度先看 Copilot 寫出看起來正常的程式碼

就是順邏輯而已，沒有仔細琢磨指標的移動情形

所以只能自己寫了，也考慮邏輯：

q_new

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head) {
        free(head);
        return NULL;
    }

    INIT_LIST_HEAD(head);
    return head;
}

因為曾經被 clang-tidy 提醒過
即使 realloc 失敗也是需要 free，因為參考到 7.22.3.1 (std)

The order and contiguity of storage allocated by successive calls to the
aligned_alloc, calloc, malloc, and realloc functions is unspecified. The
pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to
a pointer to any type of object with a fundamental alignment requirement and then used
to access such an object or an array of such objects in the space allocated (until the space
is explicitly deallocated). The lifetime of an allocated object extends from the allocation
until the deallocation. Each such allocation shall yield a pointer to an object disjoint from
any other object. The pointer returned points to the start (lowest byte address) of the
allocated space. If the space cannot be allocated, a null pointer is returned. If the size of
the space requested is zero, the behavior is implementation-defined: either a null pointer
is returned, or the behavior is as if the size were some nonzero value, except that the
returned pointer shall not be used to access an object.

我想在 malloc 也是 free 比較好，同時也因為 7.22.3.3 對 free() 說道：

If ptr is a null pointer, no action occurs.

所以 free 是絕對不會出錯的。

q_free

void q_free(struct list_head *l)
{
    if (__glibc_unlikely(!l))
        return;

    if (__glibc_unlikely(list_empty(l))) {
        free(l);
        return;
    }

    struct list_head *cur = NULL, *safe = NULL;
    list_for_each_safe (cur, safe, l)
        q_release_element(container_of(cur, element_t, list));
    free(l);
}

這邊設計考慮到因為我本身是 C++ major 應該隨時注意到 RAII issue
所以我應該要把 cur 以及 safe 指標做初始化，避免 dangling pointer

即使聽過有人說在 C 語言裡面考慮記憶體安全就是個笑話
The C programming language gives you a knife that could kill you.

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    return q_insert(head, s, list_add);
}

這邊有個較優雅的寫法，源自於去年的練習：

避免贅字，無特別標示的狀況，此處都該是「你的意見」。工程人員說話要精準有效。

jserv
是的，收到。

使用到 function pointer 讓 insert 這個操作具有一定的抽象性

使用更精準的詞彙，並探究其優勢。

jserv

總之，就是比較有彈性，把實際操作的 head tail 當作 callback。

static inline bool q_insert(struct list_head *head,
                            char *s,
                            void (*op)(struct list_head *, struct list_head *))
{
    if (__glibc_unlikely(!head || !s))
        return false;

    element_t *me = new_node(s);
    if (__glibc_unlikely(!me))
        return false;

    op(&me->list, head);
    return true;
}

q_insert_tail

所以 q_insert_tail 就可以這樣寫了：

bool q_insert_tail(struct list_head *head, char *s)
{
    return q_insert(head, s, list_add_tail);
}

q_remove_head

這邊跟上面稍微不一樣的方式，上面都有可以呼叫的 function pointer 當作 callback function
但是 remove 目前 sysprog21/lab0-c 專案沒有，所以寫這樣的形式

當然如果想要自己放 renmove head/tail function 也是可以剌

static inline element_t *q_remove(struct list_head *head,
                                  char *sp,
                                  size_t bufsize,
                                  struct list_head *rm_node)
{
    element_t *ele = list_entry(rm_node, element_t, list);
    if (sp && ele->value) {
        strncpy(sp, ele->value, bufsize);
        sp[bufsize - 1] = 0;
    }
    list_del(rm_node);
    return ele;
}

所以 remove_head：

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

    return q_remove(head, sp, bufsize, head->next);
}

q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (__glibc_unlikely(!head || list_empty(head)))
        return NULL;
    return q_remove(head, sp, bufsize, head->prev);
}

q_size

這邊沒有保證須要

$O(1)$ 時間完成，於是採用

$O(N)$ 方式實作：

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    size_t size = 0;
    struct list_head *p = NULL;
    list_for_each (p, head)
        ++size;
    return size;
}

q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/

    if (__glibc_unlikely(!head || list_empty(head)))
        return false;

    struct list_head *fast = head->next, *slow = head->next;
    while (fast != head && fast->next != head)
        slow = slow->next, fast = fast->next->next;
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));

    return true;
}

這邊採用一個比較經典的演算法是快慢指標 (Floyd's Algorithm (Tortoise and Hare Algorithm))
基本上就是：

• 快指標每次移動二步，慢指標移動一步

這樣快指標到結尾的時候，慢指標就是在一半的位置。

q_delete_dup

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

    if (__glibc_unlikely(!head || list_empty(head)))
        return false;

    struct list_head *node = NULL, *safe = NULL;
    bool last_dup = false;
    list_for_each_safe (node, safe, head) {
        element_t *cur = list_entry(node, element_t, list);
        const bool match =
            node->next != head &&
            !strcmp(cur->value, list_entry(node->next, element_t, list)->value);
        if (match || last_dup) {
            list_del(node);
            q_release_element(cur);
        }
        last_dup = match;
    }

    return true;
}

作法 naive ，沒有好解釋的。

凡事都有優缺點，去探討。

jserv

要探討的話，有個議題是 cache locality 因為這樣每走兩步就交換，這樣會有 linked-list 容易 major page fault (這需要實驗做討論)。

不過如果可以假設有很低成本的 perfect-hash function

$f()$ 那我可以把 strcmp() 換成

$f()$
這樣有機會減少比較次數。

q_swap

每次移動兩步

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (__glibc_unlikely(!head))
        return;
    for (struct list_head **it = &head->next;
         *it != head && (*it)->next != head; it = &(*it)->next->next)
        swap_pair(it);
}

交換相鄰兩節點，運用到指標的指標技巧

static inline void swap_pair(struct list_head **head)
{
    struct list_head *first = *head, *second = first->next;
    first->next = second->next;
    second->next = first;
    second->prev = first->prev;
    first->prev = second;
    *head = second;
}

q_reverse

void q_reverse(struct list_head *head)
{
    // https://leetcode.com/problems/reverse-linked-list/
    if (__glibc_unlikely(!head || list_empty(head)))
        return;
    struct list_head *cur = NULL, *safe = NULL;
    list_for_each_safe (cur, safe, head)
        list_move(cur, head);  // Move to the beginning
}

把每個節點搬到「頭」，就是把整個 list 反轉

q_reverseK

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (__glibc_unlikely(!head || list_empty(head) || k <= 1))
        return;
    
    struct list_head *cur = NULL, *safe = NULL;
    list_for_each_safe (cur, safe, head) {
        struct list_head *tail = cur;
        for (int i = 1; i < k && tail->next != head; ++i)
            tail = tail->next;
        if (tail->next == head)
            break;
        list_cut_position(head, head, tail->next);
        list_splice(head, cur);
    }
}

覺得被坑，一開始 code review 這覺得沒什麼問題，想說 Copilot 可以把 leetcode 寫的很好。
但是很不幸的， Copilot 是錯的。需要重新想一次。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (__glibc_unlikely(!head || list_empty(head) || k <= 1))
        return;

    size_t count = 0;
    struct list_head *cur = NULL, *safe = NULL, *me = head;
    list_for_each_safe (cur, safe, head) {
        count++;
        if (__glibc_unlikely(count == k)) {
            LIST_HEAD(tmp);
            count = 0;

            list_cut_position(&tmp, me, cur);
            q_reverse(&tmp);  // Reuse q_reverse
            list_splice_init(&tmp, me);

            me = safe->prev;
        }
    }
}

想說時間不多，先參考同學的 komark06 並且改寫成自己的版本。

好處我交給 chatGPT 說：

第一個程式碼相對於第二個程式碼更佳優秀。原因在於第一個程式碼檢查了一個非常特殊的邊界條件：當傳入的串列 head 是空的、沒有節點或者 k 小於等於 1 時，直接返回，這有助於確保在進行操作之前，傳入的參數符合要求，從而保證程式碼的正確性和穩定性。
此外，第一個程式碼使用了 __glibc_unlikely 巨集來提示編譯器機率很低，這有助於改善程式碼的效能。同時，程式碼還使用了一個計數器 count 變量，以計算從遍歷過的節點數量。當計數器達到 k 時，程式碼創建了一個臨時串列 tmp，然後通過 list_cut_position 函數從原始串列中切下一部分節點，然後反轉這部分節點，最後使用 list_splice_init 函數將它們重新連接到原始串列中。
這種程式碼結構清晰，可讀性強，更容易理解和維護。從軟體工程的角度來看，良好的程式碼風格可以減少代碼維護成本、提高代碼的可讀性和可維護性，從而使軟體系統更穩定、更可靠。

Q: 請說明上述上述程式 對變數「限制作用域」的好處
A: 將變數限制在其實際需要使用的作用域內，可以增加代碼的可讀性和可維護性，有助於減少代碼中的錯誤和問題。這是因為限制變數作用域可以：

1. 避免變數在代碼中被意外使用或修改，尤其是當變數名稱容易混淆時，可以避免代碼出現錯誤。
2. 減少變數的生命週期，即變數只在需要使用的區塊中存在，避免了不必要的內存佔用，並減少了可能的內存泄漏。
3. 提高代碼的可讀性和可維護性，因為在較小的作用域中，變數的使用目的更清晰，代碼的結構更易於理解。
   在軟體工程中，變數的限制作用域是一個良好的編碼實踐，可以幫助開發人員開發出更可靠、可維護和易於理解的代碼。此外，這種實踐也有助於減少代碼中的問題，提高代碼品質和穩定性。
   
   

Q: 請說明這兩份程式碼的共同優點
A: 這兩份程式碼的共同優點是它們都對原始串列進行了反轉並且在一定的 k 範圍內將它分成了多個小塊進行處理，這樣可以減少整個串列反轉的時間和空間複雜度，並且更方便進行代碼的維護和擴展。此外，這兩份程式碼都使用了 Linux 內核中常見的「鏈結串列」數據結構，這是一種高效、可靠的數據結構，因此在處理類似問題時可以考慮使用這種數據結構。

這回答不是我要的答案，所以我再進行提示。

Q: 你應該針對重用 q_reverse 函式進行論述
A: 這兩份程式碼的共同優點是在 q_reverse 函式上的重用。在第一份程式碼中，當找到一組大小為 k 的節點時，它會切割出這些節點形成一個新的串列，然後調用 q_reverse 函式來反轉它們的順序。在第二份程式碼中，同樣地，當找到一組大小為 k 的節點時，它也會切割出這些節點形成一個新的串列，然後調用 q_reverse 函式來反轉它們的順序。
這樣做的好處是可以減少代碼的重複，使代碼更容易維護和修改。如果將 q_reverse 函式中的邏輯更改或修復錯誤，這將反映在這兩個函式中，從而避免了修改多處代碼的風險。這種重複使用代碼的方法也符合軟體工程中「避免代碼重複」的最佳實踐，有助於提高代碼的可重用性和可維護性。

Q: 雖然 C 語言標準中沒有對 RAII 進行保證，但是請說明 RAII 在此處運用的優勢。
A: RAII（Resource Acquisition Is Initialization）是一種資源管理方式，透過在物件建立時取得資源，並在物件生命週期結束時自動釋放資源，可以避免資源洩漏和重複釋放等問題。
在這段程式碼中，第一份程式碼使用了 RAII 的概念，當需要反轉的節點形成一個臨時的串列時，使用了 LIST_HEAD 宏定義了一個 struct list_head 結構的空頭節點。因為它是在自動變數中聲明的，所以在該變數的生命週期結束時，它的資源也會被釋放。這可以避免在出錯的情況下忘記釋放該節點的資源，從而造成資源洩漏的問題。
相較之下，第二份程式碼沒有使用 RAII 機制，而是在函數中聲明一個 dummy 節點，並在函數結束時手動釋放它的資源。這樣容易忘記釋放資源，並且也不如 RAII 一樣優雅、安全和方便。因此，使用 RAII 可以使程式碼更加健壯、可靠和易於維護。

q_sort

覺得說沒有必要自己重新想一次，我只需要先去吸收前人的查克拉，參考別人的實驗結果再繼續向前改進。
於是，花了一天時間琢磨 Merge Sort 與它的變化
決定修改過來用。

但是目前遇到一個很嚴重的問題是，C 語言沒有 type decuction
所以在使用 linux 核心風格的 API 時，常常混淆到底現在的資料型態是什麼？而後就要重新推導一次。
如此反覆覺得自己記憶力不好，又容易出錯。

因為根據以前經驗，Jserv 會測驗 sort 的非遞迴時作版本（而故意使我們遞迴實作的 sort stack overflow）
所以在這邊就直接參考非遞迴的 merge sort，而原本該文章的實作是只有 singly-linked list，並且最後的 next 是 NULL

在我們本次作業的實踐中，是 doubly-linked list 並且是 circuler-linked list 首尾相接。

曾經有看過有人的做法是把 doubly-linked list 當作 singly-linked list 來存取。
寫起來應該沒有比較簡單？

對於這點我不確定，要再仔細思考

mergeTwoLists version 1

總之，修改原作的思考如下：
首先是 merge two list

// Merge two sorted lists
static inline element_t *mergeTwoLists(element_t *L1, element_t *L2)
{
    element_t head;
    INIT_LIST_HEAD(&head.list);

    element_t *ptr = &head;
    while (L1 && L2) {
        if (strcmp(L1->value, L2->value) <= 0) {
            ptr->list.next = &L1->list;
            L1->list.prev = &ptr->list;

            L1 = list_entry(L1->list.next, element_t, list);
        } else {
            ptr->list.next = &L2->list;
            L2->list.prev = &ptr->list;

            L2 = list_entry(L2->list.next, element_t, list);
        }
        ptr = list_entry(ptr->list.next, element_t, list);
    }
    // Concatenate the rest of L1 or L2 to the tail of ptr
    ptr->list.next = list_empty(L1) ? L2 : L1;
    return list_entry(head.list.next, element_t, list);
}

修改過程中有看到 indirect pointer 的做法，但是這邊過於抽象。
我想把改成 indirect pointer 的實作放到未來再改進。

而且用 indirect pointer 的時候會有一個問題需要考慮：
這邊傳進來的是 element_t * ，如果使用 indirect poiner 表示: element_t ** 會發現
list_entry(L1->list.next, element_t, list) -> 這是一個 element_t * 而已
這時候再對他取 reference ???
associate 到的位址會在 stack 上，而不是在 heap 上。
這就不是我們要的那個物件。
所以我認為在這實作 indirect pointer 有困難

這邊同時未來可以把 strcmp 改成 callback 如上面的標示，就可以變成 descending 或 ascending

寫道這邊 code review 又發現問題：
上面這段程式碼的最後兩行：

// Concatenate the rest of L1 or L2 to the tail of ptr
    ptr->list.next = list_empty(L1) ? L2 : L1;
    return list_entry(head.list.next, element_t, list);

請問這時候 ptr->list.next 是什麼資料型態？

struct list_head *

那右邊 L1, L2 是什麼資料型態？

element_t *

喔不， C 語言沒有 strong-type 這樣在沒有 compile 的情況，要發現這邊 type incompatible 不容易

所以應該修正如下：

element_t *rest_list = list_empty(L1) ? L2 : L1;
ptr->list.next = &rest_list->list;

return list_entry(head.list.next, element_t, list);

寫到這邊再 review 一次上面的程式碼，又發現尚有一個缺失：
這會造成無窮迴圈

看到這，對，你發現了。

while (L1 && L2)

這麼顯而易見的語意，在這是不行的，因為這是 circuler linked-list …
永遠不會碰到 NULL pointer 的情況，使得這迴圈停止。

這樣的問題，修改如下：

struct list_head *L1_head = &L1->list;
struct list_head *L2_head = &L2->list;

while(L1->list.next != L1_head && L2->list.next != L2_head) {
    // ...
}

你答對了，重新再看一次又發現問題：
最後一行這有什麼問題呢？

return list_entry(head.list.next, element_t, list);

這個 list 還沒有連結反向的 prev 啊！！！
所以要在 if {} else {} 裏面連結好，再把最後一個連回到： ptr->list.next
對，因為 ptr->list 是區域變數，他的 next 才是我們真正合併的頭。

改了幾下，又看到，後面這邊的 list_empty(L1) 似乎有些問題
因為 list_empty 定義如下：

static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

在上面搬動 L1 與 L2 的過程中，會不會影響 head->next 其實永遠不會 == head 的情況？
這件事情一再告訴我們物件導向、模組化的重要性。
寫到這邊還要往前去檢查 list_empty 這判斷的檢查是不是合乎在這樣條件下邏輯。

mergeTwoLists version 2

總之，最後參考了 @alanjian85 改成自己的風格後加上適當註解

struct list_head *q_merge_two(struct list_head *first, struct list_head *second)
{
    if (__glibc_unlikely(!first || !second))
        return 0;
    struct list_head temp_head;
    INIT_LIST_HEAD(&temp_head);

    while (!list_empty(first) && !list_empty(second)) {
        // Aliasing to get the first element of each list
        const element_t *first_front = list_first_entry(first, element_t, list);
        const element_t *second_front =
            list_first_entry(second, element_t, list);

        const char *first_str = first_front->value,
                   *second_str = second_front->value;
        element_t *minimum =
            strcmp(first_str, second_str) < 0 ? first_front : second_front;

        // Move the node to the newer list
        list_move_tail(&minimum->list, &temp_head);
    }
    // Concatenate the rest of the list
    list_splice_tail_init(first, &temp_head);
    list_splice_tail_init(second, &temp_head);

    // Make it still circular
    list_splice(&temp_head, first);
    return first;
}

Copilot's divide_to_sorted

接下來，看到 divide_to_sorted 因為觀察到，在 Merge Sort 與他的變化報告中，
這個的效能顯著比其他兩者的好。比快慢指標大約快 4 倍，並且

$\delta$ 小很多，不會有巨幅震盪的情況。

static void divide_to_sorted(element_t **list,
                             element_t *lists[],
                             size_t *listsSize)
{
    size_t i = 0;
    element_t *sorted = *list;
    while (!list_empty(&sorted->list)) {
        element_t *iter = NULL;

        // Loop until the end of the list or the next element is larger than the
        // previous one
        list_for_each_entry (iter, &sorted->list, list) {
            element_t *next_node = list_entry(iter->list.next, element_t, list);
            // if it is not the head of list(end of list), because the list is
            // circular
            if (next_node != sorted &&
                strcmp(iter->value, next_node->value) > 0)
                break;
        }

        lists[i++] = sorted;

        // Concatenate last element to the head of sorted list
        iter->list.next = &sorted->list;
        sorted->list.prev = &iter->list;

        sorted = next_ele(iter);
    }
    *listsSize = i;
}

目前初次 code review 改寫之後的程式，覺得沒有問題。

Copilot's interval_merge

然後寫了：

static element_t *interval_merge(element_t *lists[], size_t listsSize)
{
    if (listsSize == 0)
        return lists[0];

    for (size_t interval = 1; interval < listsSize; interval *= 2)
        for (int i = 0; i + interval < listsSize; i += interval * 2) {
            struct list_head *cur =
                q_merge_two(&(lists[i]->list), &(lists[i + interval]->list));
            lists[i] = list_entry(cur, element_t, list);
        }

    return lists[0];
}

並且寫這些 helper 的總和，回到 q_sort

void q_sort(struct list_head *head)
{
    if (__glibc_unlikely(!head || list_empty(head)))
        return;

    size_t len = q_size(head);
    if (len == 1)
        return;

    element_t **arr = malloc(len * sizeof(element_t *));
    element_t *cur = list_entry(head, element_t, list);

    // Reference:
    // https://hackmd.io/@lambert-wu/list-merge-sort#%E5%88%86%E5%89%B2%E6%88%90%E6%8E%92%E5%BA%8F%E5%A5%BD%E7%9A%84%E4%B8%B2%E5%88%97
    divide_to_sorted(&cur, arr, &len);
    element_t *sorted = interval_merge(arr, len);
    head = &sorted->list;
    free(arr);
}

進行測試：

+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
FATAL ERROR: Calls to malloc disallowed
FATAL Error.  Exiting
---     trace-03-ops    0/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
FATAL ERROR: Calls to malloc disallowed
FATAL Error.  Exiting
---     trace-04-ops    0/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
FATAL ERROR: Calls to malloc disallowed
FATAL Error.  Exiting
---     trace-05-ops    0/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
FATAL ERROR: Calls to malloc disallowed
FATAL Error.  Exiting
---     trace-06-ops    0/6

FATAL ERROR: Calls to malloc disallowed

但是我不想處理不能用 malloc 的問題，想先暫時用 mmap 繞過它。
然後在這目前拿到 65 分

改成 mmap ，然後稍微做以下更動就跑到 71 分。

但是目前有一個問題是 sort 進行第一次執行是正確的，但是當我做第二次 sort 的時候
在 qtest.c 的 do_sort ：

    bool ok = true;
    if (current && current->size) {
        for (struct list_head *cur_l = current->q->next;
             cur_l != current->q && --cnt; cur_l = cur_l->next) {
            /* Ensure each element in ascending order */
            /* FIXME: add an option to specify sorting order */
            element_t *item, *next_item;
            item = list_entry(cur_l, element_t, list);
            next_item = list_entry(cur_l->next, element_t, list);
            if (strcmp(item->value, next_item->value) > 0) {
                report(1, "ERROR: Not sorted in ascending order");
                ok = false;
                break;
            }
        }
    }

這段第 10 行

這邊想問一個問題，我們在稱程式碼 line 的時候都稱「行」
但是根據繁體中文，橫的應該稱作「列」

比如說 command line 應該稱作「命令列」
並且根據 線代啟示錄 ：「在台灣，橫向稱為列，縱向稱為行。」
所以這邊是大陸用語的誤用嗎？

這背後是段歷史故事，下次課堂再澄清。英語詞彙的翻譯不該是總是一對一，否則就陷入簡體中文「魯棒性」一類的謬誤。

jserv

好，回到 line 10,
會顯示 segmentation fault 在我的 mmap 版本 sort 當中
解釋一下改成 mmap 的邏輯：

void q_sort(struct list_head *head)
{
    if (__glibc_unlikely(!head || list_empty(head)))
        return;

    size_t len = q_size(head);
    if (len == 1)
        return;

    size_t expected_size = ALIGN(len * sizeof(struct list_head), 4096);

    struct list_head *arr = mmap(NULL, expected_size, PROT_READ | PROT_WRITE,
                                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

    // Reference:
    // https://hackmd.io/@lambert-wu/list-merge-sort#%E5%88%86%E5%89%B2%E6%88%90%E6%8E%92%E5%BA%8F%E5%A5%BD%E7%9A%84%E4%B8%B2%E5%88%97
    divide_to_sorted(head, arr, &len);
    interval_merge(arr, len);

    /**It will look like:
     * 0x55555556c008 a
     * prev: 0x7ffff7fc3000(mmap), next: 0x55555556ccc8

     * 0x55555556ccc8 b
     * prev: 0x55555556c008,       next: 0x55555556c0d8

     * 0x55555556c0d8 r
     * prev: 0x55555556ccc8,       next: 0x7ffff7fc3000(mmap)
     *
     */
    arr->next->prev = head;
    arr->prev->next = head;

    munmap(arr, expected_size);
}

這邊想要做到的根據 Merge Sort 與它的變化 的實驗指出：
divide to sorted 的效能可以是快慢指標的

$[1.5,8]$ 倍之多

我改寫的 divide_to_sorted

於是採納這樣的實作邏輯：

// divide @list to lists of sorted elements
// And the size of the lists is stored in @listsSize
static void divide_to_sorted(struct list_head *head,
                             struct list_head arr[],
                             size_t *len)
{
    struct list_head *sorted = head;
    size_t i = 0;
    do {
        struct list_head *iter = NULL;

        // Loop until the end of the list or the next element is larger than the
        // previous one
        list_for_each (iter, sorted) {
            struct list_head *next_node = iter->next;
            // if it is not the head of list(end of list), because the list is
            // circular
            if (iter == head || next_node == head)
                break;

            element_t *cur = list_entry(iter, element_t, list);
            element_t *next = list_entry(next_node, element_t, list);
            if (strcmp(cur->value, next->value) > 0)
                break;
        }

        INIT_LIST_HEAD(&arr[i]);
        struct list_head *next = iter->next;
        list_cut_position(&arr[i], sorted, iter);
        i++;
        sorted = next->prev;  // Recover the pointer to the last element of the
                              // list
    } while (sorted != head);
    // Concatenate the rest of the list to the array
    INIT_LIST_HEAD(&arr[i]);
    list_splice_tail(sorted, &arr[i++]);
    *len = i;
}

這段程式碼將一個循環雙向鏈結串列 (head) 分割成多個已排序元素的小鏈結串列。
這些小鏈結串列的大小儲存在 listsSize 中，它是 struct list_head 的陣列。函數 divide_to_sorted 接受三個參數：head 是要被分割的原 list，arr 是用於存儲分割後的小鏈結串列的 struct list_head 陣列，而 len 是一個指向 size_t 變量的指標，將更新為 arr 陣列的大小。

該函數開始時將 sorted 初始化為 head。然後進入一個 do-while 循環，直到 sorted 等於 head 為止（即，我們已經遍歷了整個循環鏈結串列）。

在循環內部，該函數使用 list_for_each 走訪當前子鏈結串列中的元素，從 sorted 元素開始。循環會繼續直到達到子鏈結串列的末尾（所以也就會是遍歷），或者直到遇到一個元素的值小於前一個元素（這意味著子鏈結串列不再是升序的）為止。

一旦已排序的子鏈結串列被識別出來，該函數就在 arr 中創建一個新鏈結串列，並將已排序的子鏈結串列存儲其中。這是通過使用 INIT_LIST_HEAD 初始化新鏈結串列並使用 list_cut_position 從原始循環鏈結串列中刪除已排序的子鏈結串列並將其添加到 arr 中的新鏈結串列中來完成的。

在從原始鏈結串列中刪除已排序的子鏈結串列之後，該函數會更新 sorted，使其指向剛剛刪除的子鏈結串列的最後一個元素。這是因為我們希望從下一個已排序的子鏈結串列的第一個元素開始下一次循環的迭代。

一旦循環結束，該函數就會將原始循環鏈結串列中的任何剩餘元素（不屬於任何已排序子鏈結串列的元素）連接到一個新的鏈結串列中，並將其存儲在 arr 中。 arr 陣列的大小然後存儲在 len。

總體而言，該函數實現了將一個循環鏈雙向鏈結串列分割成多個已排序子鏈表的算法。這可以用於排序或分區數據，或者在其他情況下需要分割和處理列表的情況下使用。

linked list 翻譯為「鏈結串列」，不要說「鏈表」，後者實際不是「表」

jserv

上面這段我只是請 chatGPT 幫我寫 ><

邏輯如下圖
假如原本的 linked-list 如下：

而經過 divide_to_sorted 會變成

這邊有一個比較特別的實作問題：
原先上面的做法是傳入 element_t *lists[], 相當物件導向的寫法
但是會遇到一個問題是對 stack 取 container_of 是 non-sense 的操作；因為物件在 heap 上，但是傳入 the value of the poiner 再取用 address of 會拿到的地址是在 stack 進而推算出毫無意義的記憶體位址，而又型態正常。
所以斟酌後改用 linux kernel 風格，傳入 struct list_head arr[] 作為實體儲存空間。

另外還有一個問題在於，原先我們的 queue

最前頭，要有一個 list_head 作為標示才對

併入 sorted list 之後，我們就可以將 arr[0] … 的記憶體空間，放置「最前頭」的 prev, next 指標。

我改寫的 interval_merge

而後再看到 interval_merge

static struct list_head *interval_merge(struct list_head lists[],
                                        size_t listsSize)
{
    if (listsSize == 1)
        return lists;

    for (size_t interval = 1; interval < listsSize; interval *= 2)
        for (size_t i = 0; i + interval < listsSize; i += interval * 2)
            q_merge_two(&lists[i], &lists[i + interval]);

    return lists;
}

這個步驟的核心是一個迴圈，迴圈的運行次數是一個指數數列（1, 2, 4, 8, 16, …），並對應到要合併的子串的大小。每次迴圈處理的是相鄰的兩個子串，先將這兩個子串進行合併，再將合併後的子串放入到輸入的 lists 陣列中的左邊子串的位置（即 lists[i]）。這個操作實際上是在不斷地將輸入的子串進行合併，直到得到一個包含所有元素的已排序的 linked-list 為止。

這個步驟的輸入是一個包含多個已排序的 linked-list 的 lists 陣列，listsSize 變數表示 lists 陣列的大小。如果 listsSize 為 1，則直接返回 lists 陣列。否則，執行合併算法，最終返回 lists 陣列。

(src: Merge Sort 與它的變化 )

但是請注意到這邊回傳的 linked list 「頭」會被記錄在 mmap 分配到的空間上，
我們在使用完這份 page 之後，應該要注意歸還記憶體，即便 jserv 提供 hooked-malloc 沒做這檢查，使得我們可以 bypass

     /**It will look like:
     * 0x55555556c008 a
     * prev: 0x7ffff7fc3000(mmap), next: 0x55555556ccc8

     * 0x55555556ccc8 b
     * prev: 0x55555556c008,       next: 0x55555556c0d8

     * 0x55555556c0d8 r
     * prev: 0x55555556ccc8,       next: 0x7ffff7fc3000(mmap)
     *
     */

所以我們回到 q_sort:

    struct list_head *arr = mmap(NULL, expected_size, PROT_READ | PROT_WRITE,
                                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

    divide_to_sorted(head, arr, &len);
    interval_merge(arr, len);

    /**It will look like:
     * ...
     */
    arr->next->prev = head;
    arr->prev->next = head;

    munmap(arr, expected_size);

sort 第二次會爛掉的 bug

觀察 trace-03 確實是第二次會爛掉，但是仔細深入發現其實這是一個 general case
當輸入

ih m
ih n
ih a
sort

的時候會壞掉，因為反轉後的串列的頭節點是反轉前的尾節點，反轉後的尾節點是反轉前的頭節點，這樣可能會導致問題。為了避免這些問題，我們需要修復原始串列的頭節點和尾節點。

我們需要調整 head 的 prev 指向 arr->prev 的地址，以及 head 的 next 指向 arr->next 的地址，但不能直接使用 arr 的地址因為它會被 munmap 釋放。

因此，修正如下：

    /**
     * And the head will look like:
     * prev: the last node, next: the first node of the original list.
     *
     * So we need to fix the head's prev to the address of arr->prev.
     * And the head's next to the address of arr->next.
     * We cannot use the address of arr directly because it will be freed.
     */
    head->prev = arr->prev;
    head->next = arr->next;

什麼？！到測資第 15 個測試案例才發現自己是假解？

測試案例 (test case) 和測試資料不同，這裡是指前者。

jserv

回顧到 list_cut_position 的實際行為會發現：

TO BE EDITED!!!

q_descend

leetcode 原題目要求：

刪除每個節點，如果其右側的任何位置都存在一個值嚴格大於該節點的節點。

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    element_t *entry = NULL;
    list_for_each_entry (entry, head, list) {
        struct list_head *prev = entry->list.prev, *safe = prev->prev;
        for (; prev != head; prev = safe, safe = safe->prev) {
            element_t *prev_entry = list_entry(prev, element_t, list);
            if (strcmp(prev_entry->value, entry->value) >= 0)
                break;
            list_del(prev);
            q_release_element(prev_entry);
        }
    }
    return q_size(head);
}

在這裡我們採用 naive 的方式，如果遇到 prev 的字串小於自己，就把 prev 清除。

然後我們看一下 chatGPT 幫我寫的解釋：

這段程式碼是用來對雙向鏈表中的元素進行降序排序的函數。它使用了冒泡排序的思想，從鏈表頭開始遍歷，對於每個元素，它再次從頭開始遍歷，尋找比當前元素值更小的元素並交換位置。具體來說，它遍歷鏈表中每個元素，然後從它前面的元素開始，對比其值，如果前一個元素的值比當前元素的值更大或相等，則停止遍歷，否則就交換這兩個元素的位置，並繼續向前遍歷。這樣，當遍歷完成時，鏈表中的元素就會按照降序排列。該函數返回排序後鏈表的元素個數。

資源截圖：

請注意到語言模型相當有可能在鬼扯，他們只是中文房間(Chinese room)

修正 simulation 驗證時間複雜度之致命錯誤

提交之 commit

T 檢定是檢定兩分配的差距，判斷是否獨立同分配（理論上面對相同測資，同一顆 cpu 執行同一段程式碼，執行時間應該要獨立同分配）

但是 Jserv 在這做一個很不合理的操作，他讓兩筆測資不同
class 0 跟 class 1

我們可以看到這段：

    for (size_t i = 0; i < N_MEASURES; i++) {
        classes[i] = randombit();
        if (classes[i] == 0)
            memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
    }

設定 input_data 作為使用者的測資，但是在這被 memset 成 NULL
所以這裡永遠會拿到空字串，但是反觀 classes[i] 如果是 1 也就是另外一組被 T 檢定的目標卻是完整的 7-bytes 內容

注意到可能還是會有空字元在內容之中，所以我們不能在這邊說字串長度是 7

所以根據 insert head 需要根據字串大小分配空間，這樣在計算 strlen() 就會是另外一個的約 7 倍時間
嚴格計算的話要算期望值，就 1/256 … 去窮舉累加

所以這樣會讓測試的分配相當容易落入拒絕區。

比較 sort 效能與實驗

因為內容預期會有點多，所以開新的紀錄：

link