2023q1 Homework1 (lab0)

contributed by < Shiritai >

Reviewed by `Urbaner`

考慮重新整理，理出一條主要的開發線，善用開關標籤以免迷失在過長的筆記。

以一個主要個開發線或者主題來敘述開發是很好的想法，未來我將嘗試這樣做。

不過 Hackmd 本身提供快速移動到某標題的功能 (table of content)，以快速閱覽任意長度且設置正常標題的筆記，故似乎沒有必要使用開關標籤。

我認為開關標籤的使用是省略可選的內容，比如本筆記內隱藏針對 VSCode 中使用註解格式的議題，這是因為此部分僅與使用 VSCode 的使用者有關，且並不直接與開發的邏輯有關。

Eroiko
有提到不需貼出整段程式碼，僅需數行即可。考慮精簡頁面，突顯重點。

ok

Eroiko

開發環境

$ 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):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4100.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4399.99

queue 開發過程

q_new

O (1)

建立新鏈結串列節點，僅在成功配置記憶體時初始化回傳值 ret 為首位節點，並回傳。若配置失敗，ret == NULL，正好符合函式要求。







struct list_head *q_new()
{
    struct list_head *ret = malloc(sizeof(struct list_head));
    if (ret)  // if not null
        INIT_LIST_HEAD(ret);
    return ret;
}

q_free

O (n)

留意資訊科技詞彙翻譯，變更下方用語。

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

ok，本以為真的走訪全部可稱遍歷。
今後會多加注意名詞的使用。 Eroiko

透過 list_for_each_entry_safe 巨集走訪所有元素節點，分別先釋放 value 成員再釋放元素節點本身。使用 _safe 版巨集走訪是因為一路上的節點會被釋放。最後不忘要釋放首位元素節點。

















void q_free(struct list_head *l)
{
    if (!l)  // guard invalid condition
        return;

    element_t *cur, *nxt;  // iterators

    // this macro works with DS that contains
    // a member of type "list_head"
    list_for_each_entry_safe (cur, nxt, l, list) {
        // cur->value must have value except queue head
        // which won't be iterated
        q_release_element(cur);
    }

    free(l);  // free head
}

q_element_alloc 輔助函式

O (1 + m e m c p y (s i z e o f (e l e m e n t_t)) + s t r d u p (s))

Allocate 翻為配置。

Eroiko

由於 q_insert_head 和 q_insert_tail 的邏輯相似，皆需「配置新元素節點並複製給定字串值」，故將此邏輯獨立為本函式。我定義回傳值為指標，非 NULL 表成功，否則表 element_t 或 element_t::value 配置失敗。





















/**
 * Allocate and construct a new element
 * @param s value to save as element
 * @return non-null if success, null if any bad thing happens
 */
static element_t *q_element_alloc(const char *s)
{
    // allocate a new element node
    element_t *n_ele = malloc(sizeof(element_t));
    if (!n_ele)  // guard invalid condition
        return NULL;

    // copy value of s to element member
    n_ele->value = strdup(s);
    if (!n_ele->value) {
        // allocation failed
        free(n_ele);
        return NULL;
    }
    return n_ele;
}

注意以下四點：

若 n_ele 配置成功但 n_ele->value 失敗，則回傳 NULL 前不忘歸還 n_ele。
宣告為 static 是為了縮小可見度 (~~封閉性~~ ?)，~~原本名稱前面兩底線更進一步表達此函式的私有性~~。

已修改

Eroiko
要複製的字串參數實際上應該被限縮為常數，因為我們不需要修改之。
使用 doxyden 文本註解格式，這是由於在 VSCode 中比起 Linux Kernel-doc 能辨識並給予清楚的提示。實際上，doxygen 也是當前大多數程式語言都使用的註解格式。
static 是為了 visibility，而非「封閉性」，後者是數學用語。
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

確實… Eroiko
舉例而言…
- 辛辛苦苦使用 Linux Kernel-doc 的註解不能即時得到回饋。
  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 →
  如果讀者您知道哪些 VSCode 擴充套件可以解析 Linux Kernel-doc 的，請務必告訴我。
- 使用 doxygen 可以得到關鍵字的辨識與參數提示。
  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 →

q_insert_head 和 q_insert_tail 的實作與重構

一開始使用最普通的實作。由於都有「配置新元素節點並複製給定字串值」，故將該邏輯獨立為 q_element_alloc。最後使用 list_add_tail 巨集幫助完成 push front/back 的邏輯。













bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)  // NULL queue
        return false;
    // allocate a new element node
    element_t *n_ele = q_element_alloc(s);
    if (!n_ele)
        return false;
    // insert to queue head
    // i.e. head->next become &n_ele->list
    list_add(&n_ele->list, head);
    return true;
}













bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)  // NULL queue
        return false;
    // allocate a new element node
    element_t *n_ele = q_element_alloc(s);
    if (!n_ele)
        return false;
    // insert to queue tail
    // i.e. head->prev become &n_ele->list
    list_add_tail(&n_ele->list, head);
    return true;
}

會發現這倆函式行為極其相似，僅差在函式名稱以及插入位置的不同。不妨使用前處理器的技巧，讓程式更好維護，如下。

注意到前處理的換行不能被 "//" 屏蔽，故使用 C 風格的註解。

Eroiko













#define gen_q_insert(fn_suffix, list_macro)                    \
    bool q_insert_##fn_suffix(struct list_head *head, char *s) \
    {                                                          \
        if (!head) /* NULL queue */                            \
            return false;                                      \
        /* allocate a new element node */                      \
        element_t *n_ele = q_element_alloc(s);                 \
        if (!n_ele)                                            \
            return false;                                      \
        /* insert into queue */                                \
        list_macro(&n_ele->list, head);                        \
        return true;                                           \
    }

如此，兩函式的實作變為簡單兩行。





/* Insert an element at head of queue */
gen_q_insert(head, list_add);

/* Insert an element at tail of queue */
gen_q_insert(tail, list_add_tail);

q_remove_head 和 q_remove_tail 的實作與重構

首先處理邊界情況，接著取得串列的首位準備移除，當 sp 合法時複製欲移除節點之值，最後回傳。














element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))  // guard
        return NULL;
    // fetch last element
    element_t *ret = list_first_entry(head, element_t, list);
    list_del(&ret->list);
    if (sp) {
        // sp is valid
        memcpy(sp, ret->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return ret;
}














element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))  // guard
        return NULL;
    // fetch last element
    element_t *ret = list_last_entry(head, element_t, list);
    list_del(&ret->list);
    if (sp) {
        // sp is valid
        memcpy(sp, ret->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    return ret;
}

與插入的情況相同，可以發現這倆函式行為極其相似，僅差在函式名稱以及插入位置的不同。不仿再次使用前處理器的技巧，讓程式更好維護，如下。
















#define gen_q_remove(fn_suffix, list_macro)                           \
    element_t *q_remove_##fn_suffix(struct list_head *head, char *sp, \
                                    size_t bufsize)                   \
    {                                                                 \
        if (!head || list_empty(head)) /* guard */                    \
            return NULL;                                              \
        /* fetch first element */                                     \
        element_t *ret = list_macro(head, element_t, list);           \
        list_del(&ret->list);                                         \
        if (sp) {                                                     \
            /* sp is valid */                                         \
            memcpy(sp, ret->value, bufsize);                          \
            sp[bufsize - 1] = '\0';                                   \
        }                                                             \
        return ret;                                                   \
    }

注意字串的複製我使用 memcpy 來加快效率，並在最後補上 \0。

於是兩刪除節點函式的實作變成:





/* Remove an element from head of queue */
gen_q_remove(head, list_first_entry);

/* Remove an element from tail of queue */
gen_q_remove(tail, list_last_entry);

減少多餘的程式碼與人工同步的成本。

注意用語！在電腦科學和工程中，冗餘 (英語: redundancy) 是指系統為了提昇其可靠度，刻意組態重複的零件或是機能。顯然這裡不是 redundancy 的寓意，應該避免該詞彙的使用。

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

ok Eroiko

q_size

O (n)

如 Spec 給我們的提示，遍歷整個鏈結串列得所求大小。












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_find_mid 輔助函式

O (n)

有鑒於「尋找中點」需求不僅應用於一處，我將此邏輯獨立為本靜態函式。注意第二個參數 offset 可用來儲存「中點」實際上自 head 往 next 方向之距離，不浪費用來存取非連續記憶體的辛勞；若offset == NULL 則忽視此參數。相似的，文件註解採 doxygen 格式。

算法是利用雙向鏈結串列的特性，以兩個指標分別向 next 和 prev 方向等速移動，透過 front 向 next、back 向 prev 遍歷，目標是讓 front 最終指向目標。由於每次各走一步，總位移量為

2

，故有兩種相遇的可能：

back 和 front 最接近時差一，表有偶數個節點，此情況必有一次迴圈中 back->prev == front。
back 和 front 會相遇，表有奇數個節點。

用以上兩情況決定迴圈的持續條件。


























/**
 * Find the middle point in given list
 *
 * @param offset pointer to obtain position count of mid point.
 * Can pass NULL of you don't need this result.
 */
static struct list_head *q_find_mid(struct list_head *head, int *offset)
{
    if (!head || list_empty(head))
        return NULL;  // nothing to find
    // traverse in different direction
    struct list_head *front = head->next, *back = head;
    int _o = 1;
    // two possible cases for "two step in each loop"
    // in both cases, "front" will be what we want to delete
    // 1. back == front, then there are even nodes
    // 2. back->prev == front, then are odd nodes
    while (back != front && back->prev != front) {
        front = front->next;
        back = back->prev;
        ++_o;
    }
    if (offset)
        *offset = _o;
    return front;
}

q_delete_mid

利用 q_find_mid，根據以上找到欲刪除節點後，便是正常的刪除操作。











bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    struct list_head *mid = q_find_mid(head, NULL);
    if (!mid)
        return false;
    list_del(mid);  // unlink mid node
    element_t *to_del = list_entry(mid, element_t, list);
    q_release_element(to_del);
    return true;
}

q_delete_dup

要刪除重複的節點，首先列表至少要有兩元素，故邊界條件額外考慮僅單節點的情況，可使用 list_is_singlar 巨集來判斷。

接下來的演算法為：透過比較鄰近兩元素 (cur, nxt) 的字串決定行為。

若字串相同，則

刪除 cur
以 mark_del 標記 nxt 為「待刪除元素」

若不同且標記不為空，則

刪除標記下的元素，即上個迴圈的 nxt
重設標記為空，避免重複釋放記憶體

節點的走訪可搭配運用 list_for_each_entry_safe 巨集。

























bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head) || list_is_singular(head))
        return false;  // nothing to be deleted
    // delete cur when cur->value == nxt->value
    element_t *cur, *nxt, *mark_del;
    // if deletion happens, set mark_del as nxt
    // else, delete held node and reset to NULL
    mark_del = NULL;
    list_for_each_entry_safe (cur, nxt, head, list) {
        // notice that nxt == head means the last case,
        // just try to go to "else"
        if (&nxt->list != head && !strcmp(cur->value, nxt->value)) {
            mark_del = nxt;
            list_del(&cur->list);
            q_release_element(cur);
        } else if (mark_del) {
            list_del(&mark_del->list);
            q_release_element(mark_del);
            mark_del = NULL;
        }
    }
    return true;
}

q_swap

O (n)

由於後面會實作 q_reverseK 函式，而 q_swap 實際上就是 q_reverseK 的特例，故直接複用即可，這使程式更加易於維護。






void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    // reuse special case of implemented algorithm
    q_reverseK(head, 2);
}

q_reverse

O (n)

利用巨集，可透過遍歷所有節點，並將節點的 list_head::next 和 list_head::prev 交換，即表示反轉串列，故以下為第一種實作。














void q_reverse(struct list_head *head)
{
    if (!head)
        return;  // nothing to be reversed
    struct list_head *cur, *nxt;
    list_for_each_safe (cur, nxt, head) {
        cur->next = cur->prev;
        cur->prev = nxt;
    }
    // in the end, we should also swap the links of head
    struct list_head *tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

特例是要另外反轉 head 的兩個指標。若要消除此例外，可以使用 do-while 迴圈取代，便是第二種實作如下。














void q_reverse(struct list_head *head)
{
    if (!head)
        return false;  // nothing to be reversed
    struct list_head *cur = head, *nxt = head->next;
    do {
        // swap links
        cur->next = cur->prev;
        cur->prev = nxt;
        // iterate
        cur = nxt;
        nxt = nxt->next;
    } while (cur != head);
}

考慮邊界條件，只要 head 存在，整套算法即可正常運行。

q_reverseK

O (n)

本函式乍一看與 q_reverse 的運作邏輯相似，就是複雜了一點。每 k 個元素一群，要滿 k 個元素才可以進行反轉，故不能邊遍歷邊反轉，得先確認眼下真有 k 個元素。復用 q_reverse 得到的演算法可以是:

以迴圈不斷…
- 走訪
  $k$ 個元素，確認是不是真有
  $k$ 個。
- 將一鏈結串列的一定範圍截斷。
  - 利用巨集 list_cut_position，其根據給定之 head 和右界
  - 為此我們需一指標 lead 向前遍歷 k 位後確認要截斷的位置。
  - 注意 lead 的起點不可為 head，因為 list_cut_position 的截斷是「包含」給定之右界:
    $(h e a d, l e a d]$ ，範圍是左開右閉。
  - 為了不失去領頭做標記的 lead，將其初始化為 head->next，截斷之右界也順應變成 lead->prev。
- 接入暫存串列 rev_head。
- 利用已經實作好的 q_reverse 反轉暫存串列。
- 接入最終串列 new_head。
最後不忘將結果接回 head 串列。






















void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head)
        return;
    struct list_head *lead = head->next;
    LIST_HEAD(new_head);
    do {
        // move k steps
        int i;  // counter
        for (i = 0; i < k && lead != head; ++i)
            lead = lead->next;
        if (i == k) {  // there are k elements: [from, lead)
            // cut k nodes from head, reverse them, and paste to new_head
            LIST_HEAD(rev_head);
            list_cut_position(&rev_head, head, lead->prev);
            q_reverse(&rev_head);
            list_splice_tail_init(&rev_head, &new_head);
        }
    } while (lead != head);
    list_splice_init(&new_head, head);
}

與 q_reverse 相似，考慮邊界條件，只要 head 存在，整套算法即可正常運行。

in_order 輔助函式

由於 Merge request #133 加入對升序、降序的支援，我決定將「是否正確的排序」的邏輯從原本呼叫 strcmp 後比對回傳值的操作獨立成 in_order 函式，以便多處重複利用。

實作的部分即儲存 strcmp 的結果，對三種可能進行確認，詳見函式內註解。

另由於本函式小巧玲瓏，故加入 inline 修飾，期待編譯器將呼叫處改為程式碼展開。















/**
 * Return whether a and b with order: [... , a, b, ...] is in correct ordering,
 * where a and b are strings for comparison.
 * @param descend whether we're using descending order
 */
static inline bool in_order(const char *a, const char *b, bool descend)
{
    int _cmp = strcmp(a, b);
    /**
     * strcmp(a, b) == 0: always in order
     * strcmp(a, b) < 0: inorder if using ascending order
     * strcmp(a, b) > 0: inorder if using descending order
     */
    return !_cmp || (_cmp < 0 && !descend) || (_cmp > 0 && descend);
}

merge_two_lists 輔助函式

本輔助函式的意義在將 sub 串列併入 major 串列中，假設兩者都排完序。不同於上課介紹過的「先找一暫存串列，將兩目標串列的節點併入暫存串列後轉移回原串列」的做法，本函式假設一定併入 major，故可以省略與 major 長度相等之「併入」操作，降低執行時的負擔。

原本的實作為以下:






























/**
 * Helper function to merge two sorted lists.
 * @param major major list of merging, all nodes will
 * move to this linked list, must not be empty!
 * @param sub list to be merged.
 */
static void merge_two_lists(struct list_head *major, struct list_head *sub)
{
    if (list_empty(major)) {
        list_splice_init(sub, major);
        return;
    } else if (!sub || list_empty(sub)) {
        return;
    }
    struct list_head *m = major->next;
    element_t *m_ele = list_entry(m, element_t, list);
    element_t *s_ele = list_first_entry(sub, element_t, list);
    do {
        if (strcmp(m_ele->value, s_ele->value) > 0) {
            list_move_tail(sub->next, m);
            s_ele = list_first_entry(sub, element_t, list);
        } else if (m->next != major) {
            m = m->next;
            m_ele = list_entry(m, element_t, list);
        } else {
            list_splice_tail_init(sub, major);
            return;
        }
    } while (!list_empty(sub));
}

除了 edge case 有點雜亂外， do-while 迴圈內也不怎麼「美觀」，函式的其中一個返回的可能甚至在 else 條件下，實在說不上有品味…

經重構後為以下，邏輯相等不過好看多了。
























/**
 * Helper function to merge two sorted lists.
 * @param major major list of merging, all nodes will
 * move to this linked list
 * @param sub list to be merged.
 */
static void merge_two_lists(struct list_head *major, struct list_head *sub)
{
    if (!sub)
        return;
    struct list_head *m = major->next;
    element_t *m_ele = list_entry(m, element_t, list);
    element_t *s_ele = list_first_entry(sub, element_t, list);
    while (!list_empty(sub) && m != major) {
        if (strcmp(m_ele->value, s_ele->value) > 0) {
            list_move_tail(sub->next, m);
            s_ele = list_first_entry(sub, element_t, list);
        } else {
            m = m->next;
            m_ele = list_entry(m, element_t, list);
        }
    }
    list_splice_tail_init(sub, major);
}

新的 merge_two_lists 應該提供升/降序的合併，故將比較部分從


strcmp(m_ele->value, s_ele->value) > 0

改為


!in_order(m_ele->value, s_ele->value, descend)

注意新的函式簽名額外加入 descend 參數。

q_i_sort (insertion sort) 輔助函式

考慮到後面我們要實作穩定的排序，不一定要使用 merge sort，insertion sort 也是某些情境下的好選擇。

在資料結構中我們學到，在欲排序元素較少的情況下，尤其趨近排序完成的情況下，insertion sort 擁有優異的效能表現，無論是時間抑或空間複雜度上。

時間上可使用迴圈完成，無需 function call 的額外負擔。具體而言可能有參數的預備、calling stack 的操作 push/pop，code memory 中的跳導致的 cache miss 等。

空間上 insertion sort 可以就地排序，且僅需

O (1)

的額外空間，比起 merge sort 使用 calling stack、quick sort 使用 calling stack 或普通 stack 還好。

注意到我的演算法參數有二，標示著欲排序的範圍。不直接如 q_sort 傳入 head 是為了擴展性，是為了讓本函式可以進行局部排序。
























/**
 * Sort list of closed range [from, to] using insertion sort.
 * Assume from != NULL and to != NULL !!!
 * @param from starting node of sorting (include), must NOT be NULL
 * @param to ending node of sorting (include), must NOT be NULL
 */
static void q_i_sort(struct list_head *from, const struct list_head *to)
{
    const struct list_head *l_bd = from->prev,
                           *r_bd = to->next;  // boundary never change!
    struct list_head *cur = from->next;
    while (cur != r_bd) {  // loop if haven't reach end of sorting range
        struct list_head *nxt = cur->next, *prv = cur;
        element_t *c_ele = list_entry(cur, element_t, list), *p_ele;
        // traverse (back) to correct position
        // cur should finally be placed at prv->next;
        do {
            prv = prv->prev;
            p_ele = list_entry(prv, element_t, list);
        } while (prv != l_bd && strcmp(p_ele->value, c_ele->value) > 0);
        list_move(cur, prv);
        cur = nxt;  // iterator increment
    };
}

順帶一提，一開始實作時由於不是先以 l_bd (left bound) 和 r_bd (right bound) 兩恆定指標將我們感興趣的邊界記下，而是動態去與 from、to 的鄰居比較，未考量 from、to 本身也是會被移動的對象，所以除錯搞了很久…

重構時為邊界加上 const 修飾。

新的 q_i_sort 應該提供升/降序的合併，故將比較部分從


strcmp(m_ele->value, s_ele->value) > 0

改為


!in_order(m_ele->value, s_ele->value, descend)

注意新的函式簽名額外加入 descend 參數。

q_sort

本函式為 merge sort + insertion sort 的混合穩定排序。當欲排序數量大於 THRESHOLD 時使用 merge sort 的 partition，反之使用前面實作好的 insertion sort q_i_sort 直接排序。最後透過同樣實作好的 merge_two_lists 完成合併。

程式碼可分為三塊解釋。

邊界條件與變數初始化

THRESHOLD 的大小我認為與 insertion sort 的甜蜜點和 cache 的大小有關。
另外注意到之所以我不將單節點串列納入邊界情況，是因為我的實作確保以下兩點：
1. 每次必定切成近乎等長的兩串列呼叫遞迴
2. 使用 insertion sort 針對長度較小的情況排序
如此，遇到長度很低的串列自然會使用 insertion sort 排序完成，省略了大量函式呼叫。
```
if (!head)
    return;
// Use merge sort + insertion sort
// threshold to use insertion sort optimization
static const int THRESHOLD = 32;

// for merge sort, we first divide then conquer
// initialize stack two heads
LIST_HEAD(other);
```

切分與遞迴

中點的尋找我採用前面實作過的 q_find_mid 來同時取得分割點與此點兩邊串列大致的長度，後續將以此決定切分後的邏輯。


















// find pivot
/**
 * Offset of left side (mid point), which is
 * approximately the same as right side
 */
int offset;
struct list_head *pivot = q_find_mid(head, &offset);

// divide into two lists: head and other
list_cut_position(&other, head, pivot);

if (offset > THRESHOLD) {
    q_sort(head);
    q_sort(&other);
} else {
    q_i_sort(head->next, head->prev);
    q_i_sort(other.next, other.prev);
}

合併

以 head 為標的合併。


// merge then complete
merge_two_lists(head, &other);

新的 q_sort 函式簽名加入 descend 參數，連帶調整呼叫 q_sort, q_i_sort 和 merge_two_lists。

q_descend 和 q_ascend 的實作與重構

O (n)

解決 q_descend 的演算法為將題意換句話說，就是維護從右往左看的單調上升序列。




























int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head) || list_is_singular(head))
        return 0;
    int cnt = 0;
    struct list_head *lead = head->prev, *test = lead->prev;

    // not necessarily change in each loop, declare outside
    element_t *l_ele = list_entry(lead, element_t, list);

    do {
        // must change in each loop
        element_t *t_ele = list_entry(test, element_t, list);
        struct list_head *tmp = test->prev;

        if (strcmp(t_ele->value, l_ele->value) > 0)
            l_ele = t_ele;  // save in new list
        else {
            list_del(test);            // remove from doubly linked list
            q_release_element(t_ele);  // delete element node
            ++cnt;
        }

        test = tmp;  // move test
    } while (test != head);
    return cnt;
}

由於新版 lab0-c 改成要實作 q_ascend 和 q_descend 兩個維護單調序列的函式，此兩函式實際上唯一的區別在輔助函式 in_order 的回傳值。如同 q_insert_head 和 q_insert_tail 的實作與重構，我以 gen_q_monotonic 巨集實現兩函式，透過巨集參數決定演算法維護的是單調升序抑或降序的序列。

與舊版的 q_descend 相比，調換 if-else 的內容，使「升序」(descend 替換為 false) 為預設的序列，這符合程式的直觀行為。





























#define gen_q_monotonic(fn_suffix, descend)                                \
    int q_##fn_suffix(struct list_head *head)                              \
    {                                                                      \
        /* https://leetcode.com/problems/remove-nodes-from-linked-list/ */ \
        if (!head || list_empty(head) || list_is_singular(head))           \
            return 0;                                                      \
        int cnt = 0;                                                       \
        struct list_head *lead = head->prev, *test = lead->prev;           \
                                                                           \
        /* not necessarily change in each loop, declare outside */         \
        element_t *l_ele = list_entry(lead, element_t, list);              \
                                                                           \
        do {                                                               \
            /* t_ele must change in each loop */                           \
            element_t *t_ele = list_entry(test, element_t, list);          \
            struct list_head *tmp = test->prev;                            \
                                                                           \
            if (!in_order(t_ele->value, l_ele->value, descend)) {          \
                list_del(test);           /* remove from linked list */    \
                q_release_element(t_ele); /* delete element node */        \
                ++cnt;                                                     \
            } else {                                                       \
                l_ele = t_ele; /* save in new list */                      \
            }                                                              \
                                                                           \
            test = tmp; /* move test */                                    \
        } while (test != head);                                            \
        return cnt;                                                        \
    }

如此一來，q_ascend 和 q_descend 的實作變成簡單兩行。







/* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
gen_q_monotonic(ascend, false);

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
gen_q_monotonic(descend, true);

q_merge

O (n)

當中

n

為總元素數。
要將所有 queue 的內容併為一個，相當於不斷套用前面實作好的「將一串列併入某串列」的邏輯。要使 merge_two_lists 正常運作的條件為 major 參數需非 NULL，故將等價意義的 !head || list_empty(head) 設為邊界條件。

過程為先將首個 queue 元素 first 自原串列分離，遍歷所有剩下的串列並將當中的 queue 一個個併入 first->q，最後把 first 接回元素串列。



















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 *first = list_first_entry(head, queue_contex_t, chain);
    // unlink first queue
    list_del(&first->chain);
    // iterate through remaining queues and merge into "first->q"
    queue_contex_t *cur = NULL;
    list_for_each_entry (cur, head, chain) {
        merge_two_lists(first->q, cur->q);
        first->size += cur->size;
    }
    // relink first queue
    list_add(&first->chain, head);  // restore the first queue
    return first->size;
}

新的 q_merge 應該提供升/降序的合併，故將比較部分從


strcmp(m_ele->value, s_ele->value) > 0

改為


!in_order(m_ele->value, s_ele->value, descend)

注意新的函式簽名額外加入 descend 參數。

Valgrind 的使用與記憶體分析

為了更好的閱讀 Valgrind 的輸出報告，可以使用命令列的重新導向功能，比如

(make valgrind) > make_valgrind_output.log 2 > make_valgrind_err.log

若要將 stdout 和 stderr 重新導向至同一檔案，可改成以下

(make valgrind) > make_valgrind.log 2>&1

如此一來我們便能仔細端詳 stdout 和 stderr。

memcpy 記憶體讀取問題

在 q_remove_head 和 q_remove_tail 中，我原本認為使用 memcpy 理當較 strncpy 高效，故使用前者。不過開啟 Valgrind 後發現 memcpy 會讀取到非法位置。

scripts/driver.py -p /tmp/qtest.YkLqZX --valgrind 
# Test of insert_head and remove_head
==320616== Invalid read of size 8
==320616==    at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==320616==    by 0x10FD60: memcpy (string_fortified.h:29)
==320616==    by 0x10FD60: q_remove_head (queue.c:102)
==320616==    by 0x10CA60: queue_remove (qtest.c:354)
==320616==    by 0x10CC08: do_rh (qtest.c:411)
==320616==    by 0x10E356: interpret_cmda (console.c:181)
==320616==    by 0x10E90B: interpret_cmd (console.c:201)
==320616==    by 0x10ED0C: cmd_select (console.c:610)
==320616==    by 0x10F5F8: run_console (console.c:729)
==320616==    by 0x10D748: main (qtest.c:1338)
==320616==  Address 0x4b80128 is 8 bytes before a block of size 2,049 alloc'd
==320616==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==320616==    by 0x10C7FF: queue_remove (qtest.c:319)
==320616==    by 0x10CC08: do_rh (qtest.c:411)
==320616==    by 0x10E356: interpret_cmda (console.c:181)
==320616==    by 0x10E90B: interpret_cmd (console.c:201)
==320616==    by 0x10ED0C: cmd_select (console.c:610)
==320616==    by 0x10F5F8: run_console (console.c:729)
==320616==    by 0x10D748: main (qtest.c:1338)
==320616== 
==320616== Invalid read of size 8

list_sort.c 排序比較

TODO

以下為小筆記

Linux 核心 list_sort.c 引用關係表，省略所有名為 linux 的路徑。

Web server 調整

TODO

以下為小筆記

select 資訊

以下資訊來自 Linux Manual Page。

select 函式功能

select() allows a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2), or a sufficiently small write(2)) without blocking.

關於 File descriptor sets

The principal arguments of select() are three "sets" of file descriptors (declared with the type fd_set), which allow the caller to wait for three classes of events on the specified set of file descriptors. Each of the fd_set arguments may be specified as NULL if no file descriptors are to be watched for the corresponding class of events.

注意官方提到若使用於迴圈內，也就是 fd_set 可能在迴圈內被修改，則我們應該 (用 FD_ZERO) 重新初始化 fd_set。

以下四個巨集協助修改 file descriptor set。
- FD_ZERO: 初始化 fd_set。
- FD_SET: 加入某 fd 至 fd_set。
- FD_CLR: 將某 fd 自 fd_set 移除。
- FD_ISSET: 確認某 fd 是否在 fd_set 中，存在則非零，不存在則為零。
另一函式 pselect 與 select 有些許不同。
加入 select

於 linenoice:line_edit 中加入 Spec 建議的程式碼後，須引入以下標頭檔。
```
#include <netinet/in.h> /* sockaddr_in */
#include <sys/select.h> /* fd_set */
```
並修改 listenfd 為 web 輸入的檔案描述子 l.ifd、將 SA 縮寫改為 struct sockaddr_in。

其他紀錄

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 →

作業完成度

Quick Note

以規定之標準格式化程式碼檔案

clang-format -i *.[ch]

if-else 採 K&R 風格







if (condition1) {
    
} else if (condition2) {
    
} else {
    
}

GDB 重要命令與用法紀錄

帶參數除錯

gdb --args EXECUTABLE ARG1 ARG2 ...

使用重新導向除錯

gdb EXECUTABLE
...
(gdb) run < FILE_TO_REDIRECT_AS_INPUT

常用命令

Command	Alias	Argument	Usage
`help`	`h`	`ALL_GDB_COMMAND`	啥都不知道時先 `help` 一下就對了
`print`	`p`	`SOMETHING`	印出 `SOMETHING`，可以是參數、指標，甚至呼叫函式的節果
`break`	`b`	`FILE:LINE_NUMBER`	在 `FILE` 的第 `LINE_NUMBER` 設定中斷點，比如 `b queue.c:123`
`step`	-	-	單步執行
`continue`	`c`	-	從當前中斷點繼續執行 (至下個中斷點或執行結束 or 報錯)
`info`	`i`	`SOME_GDB_COMMAND`	印出 `SOME_GDB_COMMAND` 的相關訊息，可使用 `help info` 查看哪些命令可供查看
`backtrace`	`bt`	-	印出 function stack
`frame`	`f`	`FRAME_NUMBER`	移動至 function stack 中編號 `FRAME_NUMBER` 的 frame，目前有哪些 frame 可用 `bt` 查詢
`up`	-	-	切換到上層 frame
`down`	-	-	切換到下層 frame

查閱教育部辭典「幀」的釋義: 量詞。計算照片、字畫等的單位。但這樣的量詞跟 GDB 原本的 stack frame 不相符，後者更在意可切換 stack context 的範疇。因應漢語的侷限，這裡不該翻譯。

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

ok

Valgrind
- 透過維護一組暫存器和主記憶體的副本，安全監視程式的運行。寫好的 Machine Code 先被轉譯為虛擬指令集 VEX (中間表示法 IR)，再以 JIT 的方式重新翻譯為目標架構的 Machine Code。
自動測試程式
- 透過 function hooking 搭配雙向鏈結串列，儲存記憶體使用的
  - 測試時將 malloc, calloc 透過巨集與 test_malloc, test_calloc 掛鉤。

Sync fork 紀錄

由於我 fork 的 repository 與源 repository 有不少落差，今希望將源 repository (i.e. upstream) 的修改也加入我 fork 的 repository。

Git 為遠端加入 upstream

查看當前遠端 repository

> git remote -v
origin  https://github.com/Shiritai/lab0-c.git (fetch)
origin  https://github.com/Shiritai/lab0-c.git (push)

新增 upstream

> git remote add upstream https://github.com/sysprog21/lab0-c.git

確認

> git remote -v
origin  https://github.com/Shiritai/lab0-c.git (fetch)
origin  https://github.com/Shiritai/lab0-c.git (push)
upstream        https://github.com/sysprog21/lab0-c.git (fetch)
upstream        https://github.com/sysprog21/lab0-c.git (push)

Sync fork

載入 upstream

> git fetch upstream
remote: Enumerating objects: 94, done.
remote: Counting objects: 100% (58/58), done.
remote: Compressing objects: 100% (10/10), done.
remote: Total 94 (delta 48), reused 54 (delta 48), pack-reused 36
Unpacking objects: 100% (94/94), 32.80 KiB | 645.00 KiB/s, done.
From https://github.com/sysprog21/lab0-c
 * [new branch]      master     -> upstream/master

保險起見將本地主分支備份為 backup

> git checkout -b backup
Switched to a new branch 'backup'
> git checkout master
Switched to branch 'master'
> git branch
  backup
* master
(END)

嘗試與 upstream 合併

> git merge upstream/master
Auto-merging .github/workflows/main.yml
CONFLICT (content): Merge conflict in .github/workflows/main.yml
Auto-merging linenoise.c
Auto-merging qtest.c
Auto-merging queue.c
CONFLICT (content): Merge conflict in queue.c
Auto-merging report.c
CONFLICT (content): Merge conflict in report.c
Automatic merge failed; fix conflicts and then commit the result.

使用 git 自動合併的話，可以看到數個檔案出現衝突，這符合預期，接下來便是針對衝突逐一解決。

merge 紀錄
- 使用 VSCode 內 Merge editer 的 accept combination 會自動嘗試合併兩方的修改。
- q_sort 的部分，由於改成支援升序與降序兩種方式，q_sort 的簽名進行了調整，需合併衝突：採用新簽名。
- 新增 q_ascend 函式，直接併入即可。

遇到問題

SSH 設定與 ssh-private-key 問題
- 這可能是由於自己已經有一 ssh key，卻又不小心生成另一個，因為自以為舊的可能不會派上用場。
- 目前透過修改 main.yml 使 github action 可運行測試。
  - 當然這顯然不是個好方法，僅權宜
```
# TODO uncomment this
# - uses: webfactory/ssh-agent@v0.7.0
#   with:
#       ssh-private-key: ${{ secrets.SSH_PRIVATE_KEY }}
```
- ~~具體等完成 lab 的其他部分後再來研究…~~
- 透過 sync fork，將 upstream 上同學的 merge request 併入後得到解決。
目前實作之分數為
$100 / 100$ ，不知為何突然最後一項常數時間的測試場景通過了…

Cppcheck 警告

警告位置: repost.c:report_event

static char *msg_name_text[N_MSG] = {
    "WARNING",
    "ERROR",
    "FATAL ERROR",
};

原本透過加上 const 解決。
upstream 的 commit 0180045 將 pre-commit.hook 修改，我將其 sync 回我 fork 的 repository 而解決。

Typos or patch?!

要先 fork + 打開 Github Action 後，照 Spec 的「小試身手」操作才會正確運行
- git commit 後會自動進行測試、報告結果，並寄送至郵件
Valgrind + 自動測試程式
- Signal 處理與應用
  - queue_init 不存在，應為 q_init
  - sigsegvhandler 不存在，應為 sigsegv_handler
  - sigalrmhandler 不存在，應為 sigalrm_handler

請修改 HackMD 頁面。

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

好的，修改完畢。

web
- linenoiseEdit 可改為 linenoice.c:line_edit 方能立刻找到
- 程式碼的諸多函式名稱有誤，需舉燭
- 部分操作難以理解，似乎因為是針對以前的程式碼說明？！
Linux 核心排序實作的演進
- 數學推導過程沒採用 LaTeX 風格於 Markdown 的置中語法，有點不習慣。即:
```
$$
\rm{example statement}
$$
```
整個 Hackmd 都有的排版建議
- 程式碼區於列表下 (i.e. * 無序列表或 1. 有序列表) 幾乎都沒有縮排，也許是為了控制單行字數能保持一致，不過有點違和。

2023q1 Homework1 (lab0)

Reviewed by Urbaner

開發環境

queue 開發過程

q_new

q_free

q_element_alloc 輔助函式

q_insert_head 和 q_insert_tail 的實作與重構

q_remove_head 和 q_remove_tail 的實作與重構

q_size

q_find_mid 輔助函式

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

in_order 輔助函式

merge_two_lists 輔助函式

q_i_sort (insertion sort) 輔助函式

q_sort

q_descend 和 q_ascend 的實作與重構

q_merge

Valgrind 的使用與記憶體分析

memcpy 記憶體讀取問題

list_sort.c 排序比較

Web server 調整

其他紀錄

Image Not Showing Possible Reasons The image file may be corruptedThe server hosting the image is unavailableThe image path is incorrectThe image format is not supported Learn More → 作業完成度

Quick Note

Sync fork 紀錄

遇到問題

Typos or patch?!

Read more

Arch Linux 伺服器建置

Rust X OS 筆記

Ubuntu (desktop) 實驗平台搭建紀錄

Introduction to Database Systems

Reviewed by `Urbaner`

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 →

作業完成度