2023q1 Homework1 (lab0)

contributed by < yanjiew1 >

GitHub

開發與實驗環境

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         3400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

進度記錄

以下複製自「作業要求」

改進 `queue.c`

`q_new`

透過 malloc 來配置記憶體，使用 list.h 裡面提供的 INIT_LIST_HEAD 來初始化 struct list_head 。

commit 0f09bf6

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (!new)
        return NULL;

    INIT_LIST_HEAD(new);

    return new;
}

`q_free`

使用 list.h 內提供的 list_for_each_entry_safe 來走訪每一個節點。使用的過程中，safe 會存放下一個節點，而 it 節點可以從 linked list 移除，不影響 list_for_each_entry_safe 運作。故在這裡，可以直接在走訪的過程中釋放每一個節點。最後再呼叫 free 釋放鏈結串列所配置的記憶體空間。。

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *safe, *it;
    list_for_each_entry_safe (it, safe, l, list)
        q_release_element(it);

    free(l);
}

開發過程記錄

一開始程式碼如下：

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    struct list_head *safe;
    struct list_head *it;

    list_for_each_safe (it, safe, l) {
        list_del(it);
        free(it);
    }

    free(l);
}

隨後很快發現，應該要釋放 element_t 才對，因為 struct list_head 是包含在 element_t 裡面的一個成員。於是變更如下：

@@ -5,8 +5,10 @@ void q_free(struct list_head *l)
     struct list_head *it;
 
     list_for_each_safe (it, safe, l) {
+        element_t *elem = list_entry(it, element_t, list);
         list_del(it);
-        free(it);
+        free(elem->value);
+        free(elem);
     }
 
     free(l);

但因為釋放 element_t 很常被用到，所以後來我寫一個獨立函式 q_free_elem 來做。最後又發現 queue.h 有提供 q_release_element ，最後改成用 q_release_element ，修改如下：

@@ -1,14 +1,12 @@
 /* Free all storage used by queue */
 void q_free(struct list_head *l)
 {
-    struct list_head *safe;
-    struct list_head *it;
+    element_t *safe;
+    element_t *it;
 
-    list_for_each_safe (it, safe, l) {
-        element_t *elem = list_entry(it, element_t, list);
-        list_del(it);
-        free(elem->value);
-        free(elem);
+    list_for_each_entry_safe (it, safe, l, list) {
+        list_del(&it->list);
+        q_release_element(it);
     }
 
     free(l);

後來又仔細研究 list_for_each_entry_safe 巨集後，發現 list_del 可以不用做。此巨集的特性是我們可以把 it 直接釋放，只要不要動到 safe ，就可以安全操作。最後變更如下：

@@ -1,13 +1,12 @@
 /* Free all storage used by queue */
 void q_free(struct list_head *l)
 {
-    element_t *safe;
-    element_t *it;
+    if (!l)
+        return;
 
-    list_for_each_entry_safe (it, safe, l, list) {
-        list_del(&it->list);
+    element_t *safe, *it;
+    list_for_each_entry_safe (it, safe, l, list)
         q_release_element(it);
-    }
 
     free(l);
 }

`q_new_elem`

配合 q_insert_head 和 q_insert_tail 要新增元素，新增此函式，用來建立 element_t 。

使用 malloc 來配置記憶體空間。使用 strdup 來配置字串空間並拷貝字串。過程中如果配置失敗，則回傳 NULL 。

commit 1e56bd7

/* Create a new element with the provided string */
static inline element_t *q_new_elem(char *s)
{
    element_t *elem = malloc(sizeof(element_t));
    if (!elem)
        return NULL;

    char *tmp = strdup(s);
    if (!tmp) {
        free(elem);
        return NULL;
    }

    elem->value = tmp;
    return elem;
}

`q_insert_head` 和 `q_insert_tail`

一開始要檢查 head 是否為 NULL ，若為 NULL 則不進行任何操作。

使用前面建立的 q_new_elem 來建立 element_t 。並且透過 list_add 或 list_add_tail 來把節點串上去。若過程中失敗則回傳 false 。

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *elem = q_new_elem(s);
    if (!elem)
        return false;

    list_add(&elem->list, head);

    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *elem = q_new_elem(s);
    if (!elem)
        return false;

    list_add_tail(&elem->list, head);

    return true;
}

`q_copy_string`

在 q_remove_head 和 q_remove_tail 需要複製字串，且 buffer 的大小是有限制的。C 標準函式庫提供的 strcpy 無法滿足此需求，故在此實作另一個函式 q_copy_string 來完成字串拷貝。

static inline void q_copy_string(char *dest, size_t size, const char *src)
{
    size_t i;
    for (i = 0; i < size - 1 && src[i] != '\0'; i++)
        dest[i] = src[i];

    dest[i] = '\0';
}

此函式是否必要？其通用的程度如何？
jserv

謝謝老師，已改用 strncpy 來處理
Commit 5b8c553

`q_remove_head` 和 `q_remove_tail`

這裡實作從佇列中移走開頭或尾端。

利用 list_first_entry 和 list_last_entry 來取得要移除的元素。使用 list_del 來移除元素。題目要求要把移除元素的字串值拷貝到 sp 這個 buffer ，並且 buffer 大小為 bufsize ，就透過前面實作的 q_copy_string 來做。

/* Remove an element from head of queue */
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_first_entry(head, element_t, list);
    list_del(&elem->list);

    if (sp && bufsize)
        q_copy_string(sp, bufsize, elem->value);

    return elem;
}

~~q_remove_tail 程式碼相似，就不佔用版面了。~~

正因程式碼相似度高，你更該思索如何簡化程式碼，從而降低維護的程式碼。
jserv

已讓 q_remove_tail 和 q_insert_tail 重用 q_remove_head 和 q_insert_head 程式碼。謝謝老師
Commit bc97533

`q_size`

實作很簡單：直接使用 list.h 提供的 list_for_each 來走訪每一個節點。每走訪一個節點就遞增 count 變數，最後再回傳 count 變數的值即為所求。

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int count = 0;
    struct list_head *it;

    list_for_each (it, head)
        count++;

    return count;
}

`q_delete_mid`

這裡充份利用雙向鏈結串列的特性，從頭尾開始走訪節點，直到二個指標碰面時，即取得中間的節點。最後再把中間節點所代表的元素刪除。

/* Delete the middle node in queue */
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 *left = head->next;
    struct list_head *right = head->prev;

    while (left != right && left->next != right) {
        left = left->next;
        right = right->prev;
    }

    list_del(right);
    element_t *elem = list_entry(right, element_t, list);
    q_release_element(elem);

    return true;
}

`q_delete_dup`

我的作法是先宣告 cut 變數，其內容固定存放「目前走訪元素往前看，第一個其元素值與目前元素不同的元素」。

此外另外宣告一個 ~~trash~~ pending 作為暫時放置待移除元素的地方，要移除的元素都會先放在這裡，最後再一起清掉。

"trash" 命名不精準，可用 pending list 一類的詞彙。
jserv

已修改。 Commit a725fcc

在走訪元素的過程中， ~~&safe->list != head && strcmp(safe->value, it->value) == 0~~ &safe->list != head && !strcmp(safe->value, it->value) 會去判斷下一個元素跟目前元素的值是否相同。若相同時，就繼續走訪，直到遇到下個元素 safe 與目前元素 it 值不同時，再來進行接下來操作，如下：

當下個元素 safe 與目前元素 it 不同時，會先去檢查 cut 變數，是不是指向前一個元素。若是指向前一個元素，代表目前元素跟前一個元素不同，則不用處置，因為目前元素 it 跟前一個元素沒有重複；若 cut 不是指向前一個元素，則代表 cut 指向更之前的元素，且

(c u t, i t]

元素其值均相同，故把

(c u t, i t]

元素全部~~丟到 trash~~ 放到 pending 中。

迴圈最後 cut = safe->list.prev; 這敘述，因為目前元素 it 與下一個元素值 safe 不同 (若相同就不會執行到此，故更新 cut 為目前元素後，再進行下個迴圈。

迴圈結束 q_delete_dup 要返回前。要清除 ~~trash~~ pending 裡的垃圾元素。用 list_for_each_entry_safe 來走訪每一個 ~~trash~~ pending 中的元素，並用 q_release_element 來刪除它。

/* 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)
        return false;

    LIST_HEAD(pending);
    element_t *it, *safe;
    struct list_head *cut = head;

    list_for_each_entry_safe (it, safe, head, list) {
        if (&safe->list != head && !strcmp(safe->value, it->value))
            continue;
        /* Detect duplicated elements */
        if (it->list.prev != cut) {
            LIST_HEAD(tmp);
            list_cut_position(&tmp, cut, &it->list);
            list_splice(&tmp, &pending);
        }
        cut = safe->list.prev;
    }

    /* Process pending list */
    list_for_each_entry_safe (it, safe, &pending, list)
        q_release_element(it);

    return true;
}

將 strcmp(safe->value, it->value) == 0 改為 !strcmp(safe->value, it->value) 可縮減程式碼。
jserv

已修改 Commit bd9253a

`q_reverse`

這裡的實作很簡單，就是用 list_for_each_safe 走訪每一個節點。走訪過程中，用 list_move 把每一個節點移到開頭，這樣子順序就反過來了。 list_for_each_safe 允許對目前走訪的節點移動位置。因為是往前移到開頭，故不會因為節點移動而改變走訪次序或是重複走訪。

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *it, *safe;
    /* Iterate the list and move each item to the head */
    list_for_each_safe (it, safe, head)
        list_move(it, head);
}

變更記錄

把 list_for_each_safe 大括號拿掉，按照 Coding Style ，這裡不用放大括號。

diff --git a/queue.c b/queue.c
diff --git a/queue.c b/queue.c
     struct list_head *it, *safe;
     /* Iterate the list and move each item to the head */
-    list_for_each_safe (it, safe, head) {
+    list_for_each_safe (it, safe, head)
         list_move(it, head);
-    }
 }

`q_reverseK`

使用 count 來記錄已走訪幾個節點，一開始把 count 設為 k ，每走訪一個節點就把 count 減去 1 。當走訪 k 個節點時 (--count 變成 0)，就會把 cut 記錄的切點到目前走訪的節點(不包含 cut 但包含 it，即 (cut, it])切下，放到 tmp 上，再重用前面實作好的 q_reverse ，對 tmp 做反轉，再用 list_splice 把 tmp 接回來。

最後設定 safe->prev 為新的 cut 。這裡不能用 it 是因為 it 已在反轉的過程中移動位置了。

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;
    struct list_head *it, *safe, *cut;
    int count = k;
    cut = head;
    list_for_each_safe (it, safe, head) {
        if (--count)
            continue;
        LIST_HEAD(tmp);
        count = k;
        list_cut_position(&tmp, cut, it);
        q_reverse(&tmp);
        list_splice(&tmp, cut);
        cut = safe->prev;
    }
}

追加 list_empty() 的檢查。
jserv

已修正
Commit b536d66

`q_swap`

swap 就是二個二個一組進行 reverse ，故直接重用 q_reverseK 的程式。

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    q_reverseK(head, 2);
}

`q_merge_two`

因為 q_sort 和 q_merge 都會需要合併二個串列。故新增一個 q_merge_two 用來合併二個串列。參考 alanjian85 同學的實作。合併的方式是每次從輸入的二個串列中，取較小的，放到一個暫存串列中 tmp ，之後再把串列接回 first 。

static int q_merge_two(struct list_head *first, struct list_head *second)
{
    if (!first || !second)
        return 0;

    int count = 0;
    LIST_HEAD(tmp);
    while (!list_empty(first) && !list_empty(second)) {
        element_t *f = list_first_entry(first, element_t, list);
        element_t *s = list_first_entry(second, element_t, list);
        if (strcmp(f->value, s->value) <= 0)
            list_move_tail(&f->list, &tmp);
        else
            list_move_tail(&s->list, &tmp);
        count++;
    }
    count += q_size(first) + q_size(second);
    list_splice(&tmp, first);
    list_splice_tail_init(second, first);

    return count;
}

`q_sort`

採用 merge sort 遞迴演算法。一開始運用雙向鏈結串列的特性，從頭尾開始往中間找到中間節點，找到後，把 (head, mid] 留在 head 並把 (mid, head) 切下來加到 second 中。再針對 head 、 second 分別遞迴呼叫 q_sort ，對子串列進行排序。最後再把排序好的 head 和 second 透過 q_merge_two 合併。

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    /* Try to use merge sort*/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    /* Find middle point */
    struct list_head *mid, *left, *right;
    left = right = head;
    do {
        left = left->next;
        right = right->prev;
    } while (left != right && left->next != right);
    mid = left;

    /* Divide into two part */
    LIST_HEAD(second);
    list_cut_position(&second, mid, head->prev);

    /* Conquer */
    q_sort(head);
    q_sort(&second);

    /* Merge */
    q_merge_two(head, &second);
}

若要改為迭代的實作，你預計怎麼做？
jserv

在還沒看到 Linux kernel 排序演算法前，我會傳統資料結構教科書內 bottom-up 方式實作。看到 Linux 排序演算法後，很明顯發現它比傳統教科書方式聰明。之後我會研究 Python 內的 Timsort 來實作。把 Timsort 實作出來後，新增一個 sort option ，來切換排序演算法。

更新記錄

原本串列合併的程式直接寫在 q_sort 裡，後來把它移到獨立的函式中。

Commit 09de13c

`q_descend`

我的想法就是從尾到頭掃過一次。在掃的過程中，會判斷下一個節點(prev)是否小於等於目前節點(cur)，若是就把下一個節點(prev)刪除再重複迴圈，直到下一個節點是大於目前節點時，才會把 cur 移動到下一個節點，並且 cnt (計數器) 加 1 。

目前 lab0-c 內建的 list.h 標頭檔和 Linux 核心原始程式碼 include/linux/list.h 存在一些差距，後者的 list_for_each_prev 巨集不在前者出現。若有它則可以用它來實作。

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    /**
     * Traverse from the last entry and remove the element that is
     * smaller or equal to its right. Also count the number of elements.
     */
    int cnt = 1;
    element_t *cur = list_last_entry(head, element_t, list);
    while (cur->list.prev != head) {
        element_t *prev = list_last_entry(&cur->list, element_t, list);
        if (strcmp(prev->value, cur->value) < 0) {
            list_del(&prev->list);
            q_release_element(prev);
        } else {
            cnt++;
            cur = prev;
        }
    }

    return cnt;
}

針對呼叫 strcmp 的那行敘述，若搭配使用 break 或 continue 關鍵字，可進一步縮減程式碼。
jserv

`q_merge`

採用 Strategies for Stable Merge Sorting 這篇論文中的 2-merge 演算法來實作。用此演算法，使合併二個 queue 時，其二個 queue 元素數量差距不要太大。

其運作原理是這樣：

pending list 為一類似 stack 的結構，意即先加入它的 queue 會在後面才取出來。
每次迴圈加入 1 個 queue 進入 pending list ，直到沒有未加入 pending list 的 queue。
若 pending list 個數大於 3 個時，判斷是否合併：

從 pending list 依序取出 x, y, z 。若 |y| < 2|x| 則按下步驟進行合併，若否，則繼續進行 2. 迴圈
- 若 |x| < |z| 則將 x 和 y 合併，否則 y 和 z 合併
- 合併後需要再重新取出 x 、 y 、 z ，判斷是否符合需要合併的條件

把 pending list 中未合併的 queue 進行合併。

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;

    if (list_is_singular(head))
        return list_first_entry(head, queue_contex_t, chain)->size;

    /* Use 2-merge algorithm in https://arxiv.org/pdf/1801.04641.pdf */
    LIST_HEAD(pending);
    LIST_HEAD(empty);
    int n = 0;
    while (!list_empty(head)) {
        list_move(head->next, &pending);
        n++;

        while (n > 3) {
            queue_contex_t *x, *y, *z;
            x = list_first_entry(&pending, queue_contex_t, chain);
            y = list_first_entry(&x->chain, queue_contex_t, chain);
            z = list_first_entry(&x->chain, queue_contex_t, chain);

            if (y->size >= z->size << 1)
                break;

            if (x->size < z->size) {
                y->size = q_merge_two(y->q, x->q);
                list_move(&x->chain, &empty);
                n--;
            } else {
                z->size = q_merge_two(z->q, y->q);
                list_move(&y->chain, &empty);
                n--;
            }
        }
    }

    /* Merge remaining list */
    while (n > 1) {
        queue_contex_t *x, *y;
        x = list_first_entry(&pending, queue_contex_t, chain);
        y = list_first_entry(&x->chain, queue_contex_t, chain);
        y->size = q_merge_two(y->q, x->q);
        list_move(&x->chain, &empty);
        n--;
    }

    /* Move the last queue and empty queue to head */
    list_splice(&empty, head);
    list_splice(&pending, head);

    return list_first_entry(head, queue_contex_t, chain)->size;
}

更新記錄

原本是這重用前面實作的 q_sort 。我把所有鏈結串列接在一起，然後呼叫 q_sort 排序好，放回第一個串列。後來變更實作，改成直接進行合併，並且合併時，透過一些策略降低二個 queue 要合併時的長度差異。

Commit f6568be

`q_ascend`

這是後來 lab-0 加上的函式，跟 q_descend 很像。故把 q_descend 的程式複製一份來用，把中間的 < 改為 > 即可。

int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    /**
     * Traverse from the last entry and remove the element that is
     * smaller or equal to its right. Also count the number of elements.
     */
    int cnt = 1;
    element_t *cur = list_last_entry(head, element_t, list);
    while (cur->list.prev != head) {
        element_t *prev = list_last_entry(&cur->list, element_t, list);
        if (strcmp(prev->value, cur->value) > 0) {
            list_del(&prev->list);
            q_release_element(prev);
        } else {
            cnt++;
            cur = prev;
        }
    }

    return cnt;
}

Valgrind 與 Address Sanitizer 記憶體檢查

Makefile 中關於 `make valgrind` 的內容分析

valgrind: valgrind_existence
	# Explicitly disable sanitizer(s)
	$(MAKE) clean SANITIZER=0 qtest
	$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
	cp qtest $(patched_file)
	chmod u+x $(patched_file)
	sed -i "s/alarm/isnan/g" $(patched_file)
	scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
	@echo
	@echo "Test with specific case by running command:" 
	@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"

裡面看到很神奇的部份，就是在用 Valgrind 執行時，會把 qtest 執行檔中，所有 alarm 改為 isnan 。我的猜測是因為 Valgrind 會使程式執行速度變慢，導致一些操作會超過時間限制。我把這行拿掉 sed -i "s/alarm/isnan/g" $(patched_file) ，執行 make valgrind ，果然就出現超時訊息。查詢 C 標準函式庫可知，isnan(3p) 是用來檢查傳入的浮點數是否為 NaN ，會選用這個函數來取代 alarm ，估計是因為它跟 alarm 一樣函式名稱都是 5 個字元，此外 isnan 沒有任何 side effects ，故剛好可以拿來用。為了測試，我嘗試把 isnan 替換成 asinf 看看能不能運作。實測的結果如預期，可以正常運作。

使用 Valgrind

執行 make valgrind ，產生了很多 Memory leak 的訊息。以下為節錄的訊息：

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==30743== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==30743==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==30743==    by 0x10CBE6: do_new (qtest.c:146)
==30743==    by 0x10DE12: interpret_cmda (console.c:181)
==30743==    by 0x10E3C7: interpret_cmd (console.c:201)
==30743==    by 0x10E7C8: cmd_select (console.c:610)
==30743==    by 0x10F0B4: run_console (console.c:705)
==30743==    by 0x10D204: main (qtest.c:1228)
==30743==

我先用 valgrind ./qtest 的方式測試，發現只要在結束前沒有把所有的 queue 釋放，就會產生上述訊息。後來發現在 q_quit 裡面，在第一行是 return true; 使下面釋放記憶體的程式沒辦法執行。把這行拿掉後就正常了。

--- a/qtest.c
+++ b/qtest.c
@@ -1059,7 +1059,6 @@ static void q_init()
 
 static bool q_quit(int argc, char *argv[])
 {
-    return true;
     report(3, "Freeing queue");
     if (current && current->size > BIG_LIST_SIZE)
         set_cautious_mode(false);

但若是使用 valgrind ./qtest < traces/trace-01-ops.cmd 的方式來執行，仍然會出現下面訊息：

==33817== 130 bytes in 10 blocks are still reachable in loss record 1 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x49FE60E: strdup (strdup.c:42)
==33817==    by 0x1121B9: line_history_add (linenoise.c:1275)
==33817==    by 0x113014: line_hostory_load (linenoise.c:1360)
==33817==    by 0x10D332: main (qtest.c:1215)
==33817== 
==33817== 130 bytes in 10 blocks are still reachable in loss record 2 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x49FE60E: strdup (strdup.c:42)
==33817==    by 0x1121B9: line_history_add (linenoise.c:1275)
==33817==    by 0x10F10C: run_console (console.c:692)
==33817==    by 0x10D2D7: main (qtest.c:1227)
==33817== 
==33817== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x112205: line_history_add (linenoise.c:1263)
==33817==    by 0x113014: line_hostory_load (linenoise.c:1360)
==33817==    by 0x10D332: main (qtest.c:1215)
==33817==

從上述訊息可以看出是 linenoise 中處理 history 的部份出錯。分析了一下 linenoise.c 的程式碼，發現 line_atexit 只會在 enable_raw_mode 函式裡被註冊為 atexit function ，但是在 stdin 不為 tty 的情況下 enable_raw_mode 不會被呼叫到。故把註冊 line_atexit 的程式移到 linenoise function 就解決了。

--- a/linenoise.c
+++ b/linenoise.c
@@ -243,10 +243,6 @@ static int enable_raw_mode(int fd)
 {
     if (!isatty(STDIN_FILENO))
         goto fatal;
-    if (!atexit_registered) {
-        atexit(line_atexit);
-        atexit_registered = true;
-    }
     if (tcgetattr(fd, &orig_termios) == -1)
         goto fatal;
 
@@ -1189,6 +1185,11 @@ char *linenoise(const char *prompt)
 {
     char buf[LINENOISE_MAX_LINE];
 
+    if (!atexit_registered) {
+        atexit(line_atexit);
+        atexit_registered = true;
+    }
+
     if (!isatty(STDIN_FILENO)) {
         /* Not a tty: read from file / pipe. In this mode we don't want any
          * limit to the line size, so we call a function to handle that. */

至此，所有 make valgrind 會產生的記憶體問題都解決了。

使用 address sanitizer

重新編譯有開啟 address sanitizer 的版本。

make clean
make SANITIZER=1

之後執行 make test ，沒有出現任何記憶體相關錯誤訊息。至此檢查通過。

加入 option `descend`

lab-0 在 Commit 0fcefb0 加入了 descend option ，故把上游版本 sysprog21/lab0-c 合併進來時，也需要一併實作 option descend 。

修改 `q_merge_two`

因為 q_sort 和 q_merge 都會用到 q_merge_two 來合併二個串列。故在 q_merge_two 實作合併時，由大到小排序。其中迴圈內在選擇要哪一個元素放到合併後的串列時，做了些更動，如下：

         element_t *f = list_first_entry(first, element_t, list);
         element_t *s = list_first_entry(second, element_t, list);
-        if (strcmp(f->value, s->value) <= 0)
+        int cmp = strcmp(f->value, s->value);
+        if (descend)
+            cmp = -cmp;
+        if (cmp <= 0)
             list_move_tail(&f->list, &tmp);
         else
             list_move_tail(&s->list, &tmp);

而 q_merge_two 函式宣告改為：

static int q_merge_two(struct list_head *first,
                       struct list_head *second,
                       bool descend)

針對 descend 為 true 的清況，正負號反轉，即可實現大到小排序，且也維持 q_sort 和 q_merge 的穩定排序特性。

修改 `q_sort` 和 `q_merge`

而 q_sort 和 q_merge 則是修改成：呼叫 q_merge_two 時會多傳入 descend 參數，來決定是否要由大到小排序。

修改 `q_ksort`

q_ksort 是使用 Linux 核心的 list_sort 排序演算法。list_sort 會傳入比較函式 cmp 作為參數。故我實作一個比較函式 q_cmp_descend ，它會呼叫原本的比較函式 q_cmp ，但正負號相反，如下：

static int q_cmp_descend(void *priv,
                         const struct list_head *a,
                         const struct list_head *b)
{
    return -q_cmp(priv, a, b);
}

再把 q_ksort 改成判斷 descend 是否為 true ，再選擇適當的比較函式。

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

    list_cmp_func_t cmp = descend ? q_cmp_descend : q_cmp;

    list_sort(NULL, head, cmp);
}

Linux 核心 Linked List 排序研究

整合 Linux 核心的 `list_sort`

將 Linux 核心原始程式碼的 list_sort.c 和 list_sort.h 複製到 lab0-c 專案中，進行些許修改讓它可以成功在這個專案中編譯。主要是把 u8 改為 uint8_t (並加入 stdint.h) 、移除不必要的 #include 。之後修改 Makefile 加入 list_sort.o 後，確認用 make 命令可以正常編譯。

接下來是額外撰寫一份用 Linux kernel 排序的程式。因為 queue.h 不能更動，我決定把這個程式放在另一個檔案 ksort.c 並且有對應的標頭檔 ksort.h 。此也在 Makefile 內加入 ksort.o 。

因為 Linux kernel 實作需傳入 cmp 比較函式作為比較大小用。我的實作如下：

static int q_cmp(void *priv,
                 const struct list_head *a,
                 const struct list_head *b)
{
    // cppcheck-suppress nullPointer
    element_t *elem_a = list_entry(a, element_t, list);
    // cppcheck-suppress nullPointer
    element_t *elem_b = list_entry(b, element_t, list);

    return strcmp(elem_a->value, elem_b->value);
}

我新增了一個 option ksort ，可以用來切換排序實作。在 qtest.c 按照原本定義 option 的格式新增下方程式在 console_init 中。此外也加入一個全域變數來記錄目前要使用的排序實作。

未來或許會有多款排序的實作，設計選項時，應予以考慮，亦即你可用 option sort 0 (預設), option sort 1 (上述來自 Linux 核心原始程式碼的 list_sort), option sort 2 (未來實作的排序程式碼) 來切換。
jserv

static int use_ksort = 0;

add_param("ksort", &use_ksort,
          "Whether to use Linux kernel sorting algorithm", NULL);

效能分析

在開始分析效能前。看到 Linux 核心的 list_sort 是以 bottom-up 方式實作 merge sort 並且合併方式是用對 cache 較友善的方式。即

3 \times 2^{k}

就合併，大概可以猜測 Linux 的排序實作效能會比較好。我用以下的命令序列來分析排序效能:

new
option ksort 1/0 <= 跟據要測試的排序實作進行切換
ih RAND 2000000
shuffle
time sort        <= 執行 10 次取平均， 中間以 shuffle 間隔

為了避免出現 Time out 的問題。開始測試前會先 patch ./qtest，即 sed -i "s/alarm/isnan/g"。

測試的結果如下表：

我的排序	Linux Kernel 排序
2.8899	2.1537

可以看到我的 top-down 排序演算法花的時間是 Linux 核心 list_sort 實作的 1.341 倍。即比 Linux 排序演算法慢 34% 左右。

Linux Kernel Linked List 排序演算法探索

Linux 核心是使用 bottom-up 的 merge sort ，但是它合併的方式跟傳統教科書不一樣。

TODO 補完此節

`web` 命令/網頁伺服器改善

TODO

亂數研究及 shuffle 實作

程式實作

在作業說明裡面，每次抽到的數字後，都要從最前面開始往後數，這樣子會讓時間複雜度最壞情況至

O (n^{2})

，故我採取不同的策略。

我先建立一個存放所有節點的指標陣列，如下所示：

struct list_head **entries = malloc(sizeof(struct list_head *) * size);

可變更為 malloc(sizeof(*entries) * size) 以縮減程式碼。
jserv

已修改。 Commit 92d98c6

把所有節點的位址放入陣列中：

int i = 0;
list_for_each (node, head)
    entries[i++] = node;

取得隨機數先直接使用 C 語言標準函式庫提供的 rand 函數取得隨機數。因為 rand 的範圍是 [0, RAND_MAX] ， RAND_MAX 不一定可以被候選數個數整除。故使用一個迴圈，丟棄任何會大於 RAND_MAX - (RAND_MAX % k) 的數值，使得取得的隨機數最大值可被候選數個數整除。讓每一個候選數被選中的機率是一樣的。以下是相關程式碼片段。這裡要取得

[0, i]

之間的數。

int n;
do {
    n = rand();
} while (n >= RAND_MAX - (RAND_MAX % (i + 1)));
n %= i + 1;

對照看 random.[ch] 程式碼。
jserv

這樣的實作缺點是需要使用 malloc 來配置額外空間。無法做到空間複雜度

O (1)

。目前還沒想到能在時間複雜度為

O (n)

情況下，空間複雜度為

O (1)

的方式。

Fisher–Yates shuffle 亂度分析

分析方式為建立一個 queue ，並分別新增 a, b, c, d 至 queue 中。執行 shuffle 1000000 次，並統計每種排列方式出現的次數。

直接使用作業說明提供的程式來分析。把作業說明的 Python 程式複製到 script/shuffle.py ，並修改改用 a, b, c, d 來進行 shuffle 測試。

排列	出現次數	期待次數	$\frac{(O_{i} - E_{i})^{2}}{E_{i}}$
abcd	41451	41666.67	1.1162907
abdc	41827	41666.67	0.6169627
acbd	41722	41666.67	0.0734827
acdb	41524	41666.67	0.4884907
adbc	41707	41666.67	0.0390427
adcb	41439	41666.67	1.2439707
bacd	41937	41666.67	1.7539227
badc	41628	41666.67	0.0358827
bcad	42129	41666.67	5.1300507
bcda	41591	41666.67	0.1374107
bdac	41626	41666.67	0.0396907
bdca	41709	41666.67	0.0430107
cabd	41418	41666.67	1.4840427
cadb	41500	41666.67	0.6666667
cbad	41712	41666.67	0.0493227
cbda	41794	41666.67	0.3891307
cdab	41439	41666.67	1.2439707
cdba	42090	41666.67	4.3010667
dabc	41767	41666.67	0.2416027
dacb	41190	41666.67	5.4530667
dbac	41823	41666.67	0.5865627
dbca	41679	41666.67	0.0036507
dcab	41625	41666.67	0.0416667
dcba	41673	41666.67	0.0009627
Total			25.17992

使用此線上工具計算 P 值，計算出來為 0.34 左右，故無法拒絕 Fisher–Yates shuffle 不是 Uniform Distribution。

Entropy 觀察

跟據作業要求，執行以下命令來觀察 entropy。

option entropy 1
new
it RAND 10

l = [haiowq(29.69%) wncthutns(32.81%) yhzrx(26.56%) dfjqntag(35.94%) whgushb(29.69%) ciahh(21.88%) oidgffg(26.56%) pmeqkxou(35.94%) xffww(17.19%) nrgavix(32.81%)]

大致上可以發現，在相同字串長度下，不重複的字母數愈多，其 entropy 愈高。例如： ciahh(21.88%), xffww(17.19%) ，也就是代表其亂度愈高。

從 entropy 公式可以發現，若字串中每一個字母其出現機率愈一致（即字串愈亂)，且一字串所包含的不同字母數愈多 (即每個字母出現的機率一致)，其 entropy 愈高，符合作業說明所說的。

不過到這裡，我還是沒有完全理解 entropy 的意義，目前的理解是：它用來表達一個訊息內容有多亂。之後還要再研讀。

加入 Xoshiro256++ 亂數產生器並比較系統提供之亂數產生器

qtest 亂數產生器存放在 random.c ，可以看到此亂數產生器是直接使用 Linux 核心提供的亂數產生器。

我跟據作業提供的 Wikipedia Xorshift 參考連結，並參考了相關的變形實作。我決定引進 Xoshiro256++ 來作為另一套亂數產生器。因為原本的 Xorshift 跟據維基百科說明，在統計上可能有些瑕疵。而其變種 Xoshiro256++ 在作者官網介紹中感覺看不出有瑕疵。

Xorshift 是 Linear-feedback shift register (LFSR) 的子集合

作者在他的網站上提供了 Xoshiro256++ 的程式碼，故我就直接使用作者網站提供的程式碼，再做點修改。此外作者建議使用 SplitMix64 作為初始化 Xoshiro256++ 的內部狀態，同樣也在他的網站上提供程式碼，我也直接把它拿來用。

把上述程式結合，再做點修改後，Xoshiro256++ 亂數產生器程式放在 xoshiro.c 檔案內。

另外再建立一個 qrandom.c 檔案，這裡是亂數產生器的單一入口，會再透過全域變數 qrandom_impl 來決定要使用的亂數產生器。而 qrandom_impl 可用 option random 來控制。目前設定是 qrandom_impl == 0 時使用系統提供的亂數產生器， qrandom_impl != 1 時就用 Xoshiro256++。

此外，我在 qtest.c 內實作 -r　選項，可讓 qtest 直接使用內部的亂數產生器，產生隨機 raw bytes 並輸出到 stdout 。-r 0 為使用內建的亂數產生器，-r 1 為使用 xoshiro256++ ，搭配作業說明 ent 工具來評估亂數產生器的品質。

在 main 函式處理命令列選項的 switch-case 地方加入：

case 'r':
    char *endptr;
    errno = 0;
    qrandom_impl = strtol(optarg, &endptr, 10);
    if (errno != 0 || endptr == optarg) {
        fprintf(stderr, "Invalid random number generator\n");
        exit(EXIT_FAILURE);
    }
    generate_randombytes();
    break;

另外也新增一個函式 generate_randombytes ，來把亂數輸出到 stdout 。

#define RANDOM_BYTES 1048576
static void generate_randombytes(void)
{
    uint8_t *buf = malloc(RANDOM_BYTES);
    if (!buf)
        exit(1);

    do {
        qrandombytes(buf, RANDOM_BYTES);
    } while (fwrite(buf, RANDOM_BYTES, 1, stdout));

    exit(0);
}

`Xoshiro256++` 亂數品質測試

執行下面命令來測試亂數品質，可得到這個報告

./qtest -r 1 | head -c 10M | ent
Entropy = 7.999998 bits per byte

Optimum compression would reduce the size
of this 104857600 byte file by 0 percent.

Chi square distribution for 104857600 samples is 264.69, and randomly
would exceed this value 32.52 percent of the times.

Arithmetic mean value of data bytes is 127.4997 (127.5 = random).
Monte Carlo value for Pi is 3.142157713 (error 0.02 percent).
Serial correlation coefficient is 0.000097 (totally uncorrelated = 0.0).

卡方檢定的結果 p 值為 32.52% ，離 5% 遙遠，故此亂數產生器產生的亂數可能是 Uniform Distribution 的。

此外 entropy 值為 7.99998 bits per byte, 可說是相當高。

系統內建亂數測試

$ ./qtest -r 0 | head -c 10M | ent
Entropy = 7.999983 bits per byte.

Optimum compression would reduce the size
of this 10485760 byte file by 0 percent.

Chi square distribution for 10485760 samples is 248.23, and randomly
would exceed this value 60.75 percent of the times.

Arithmetic mean value of data bytes is 127.4847 (127.5 = random).
Monte Carlo value for Pi is 3.141642434 (error 0.00 percent).
Serial correlation coefficient is -0.000522 (totally uncorrelated = 0.0).

卡方檢定的結果 p 值為 60.75% ，離 5% 遙遠，故此亂數產生器產生的亂數可能是 Uniform Distribution 的。

此外 entropy 值為 7.999983 bits per byte, 也是相當高。

故二種亂數產生器均能產生品質不錯的亂數。

原本想要用 dieharder 測試，但跑了很久都沒有結束，所以後來就先提供 ent 報告結果。

你若對這主題感興趣，可對照閱讀 Uniting the Linux random-number devices，亂數產生器的品質，是近期 Linux 核心的重要開發方針之一。
jserv

研讀論文〈Dude, is my code constant time?〉

論文

`dudect` 統計原理

dudect 會以二種不同類型的資料作為輸入，對待測的程式進行多次時間量測，並分別觀察二種資料作為輸入時其執行時間的分布，進行比較。這二種不同類型的資料分別是：

固定資料
隨機資料

若固定輸入資料與隨機輸入資料的時間分布有顯著差異，則可以證明待測的程式其執行時間不是常數時間。反之則其執行時間可能是常數時間（即無法拒絕其為常數時間）

執行 dudect 分為三步驟：

量測執行時間：對二種不同類型的資料進行多次量測。論文建議不要進行一類量測再進行另外一類，避免數值受環境干擾。建議的方式是：每次隨機任一類資料，進行執行時間量測。
量測後的資料處理：
- Cropping 因為執行時，作業系統或硬體中斷都可能打斷正在執行中的程式，這會讓量測不準確。此外資料會偏向較長執行時間一方。故可以透過 Cropping 手法來裁剪執行時間較長的部份。
- Higher-order preprocessing ：尚未理解這部份
進行統計分析：透過統計方法拒絕虛無假說「二種輸入類型執行時間分佈一致」。若成功拒絕此虛無假說，則可說明程式執行不是常數時間。論文中提到二種檢測方式，其中 dudect 是用 Welch’s t-test
- Welch’s t-test
- Non-parametric tests

這份文件有其他人寫的論文說明也可供參考

需要再研讀 目前還是不懂 Welch’s t-test 和 Student's t-test 的原理，還需要再研究。

目前 `lab0-c` 內 `dudect` 缺陷

我發現 lab0-c 裡 dudect 有許多嚴重錯誤會導致偏差

跟據作業說明：「在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。」經過檢查 lab0-c 的程式碼，發現的確沒有 percentile 相關程式。在原始的 oreparaz/dudect 會先計算 percentile 並把極端值除去。故在 lab-0 裡沒有正確實作這部份。
constants.c 裡的 prepare_inputs 和 measure 設計錯誤。 prepare_inputs 裡的字串產生程式沒有辦法產生長度一致的字串，因為 randombytes 可能會讓字串中間有 '\0' ，此外 prepare_inputs 沒有跟據「固定資料」產生固定字串。
prepare_inputs　雖然一開始產生隨機資料放在 input_data 中，但這份資料沒有在 measure 使用

dudect 是直接用 rdtsc 指令來計算花費週期數，但計算的結果會包含程式執行到一半可能會被中斷去執行，因為系統上不是只有待測程式在執行。

對 `lab-0` 中 `dudect` 的改進

改進方法如下：

嘗試直接把 oreparaz/dudect 引入 lab0-c 中，解決沒有 percentile 相關程式的問題。且 oreparaz/dudect 內的統計相關程式比較完整。
重寫準備輸入資料和待測程式碼（也就是 dudect 會呼叫量測時間的程式），改善上節提到的缺陷。

我直接把 dudect.h 引入我的程式，但把它拆成 dudect.c 和 dudect.h 。
把 dudect.c 內的 randombytes 和 randombit 的函式移除，因此在 random.c 就有提供相同的函式了。
dudect 原本是設計一個 binary 只能有一種測試，因為它會直接呼叫 prepare_inputs 和 do_one_computation 這二個由使用者實作的函式，但因為 lab0-c 有四個待測物，故我把 dudect_config_t 內加入 prepare 和 compute 二個存放 function pointer 欄位，然後把原本呼叫 prepare_inputs 和 do_one_computation 改成呼叫 dudect_config_t 內的 function pointer 。

typedef struct __dudect_config dudect_config_t;

typedef void (*dudect_prepare_func_t)(void *priv,
                                      dudect_config_t *conf,
                                      uint8_t *input_data,
                                      uint8_t *classes);

typedef uint8_t (*dudect_compute_func_t)(void *priv,
                                         size_t size,
                                         uint8_t *data);

struct __dudect_config {
    size_t chunk_size;
    size_t number_measurements;
    void *priv;
    dudect_prepare_func_t prepare;
    dudect_compute_func_t compute;
};

增加 DUDECT_NOT_ENOUGHT_MEASUREMENTS 這個狀態。並修改 report 在還沒收集足夠資料時，回傳 DUDECT_NOT_ENOUGHT_MEASUREMENTS 。而 dudect_main 函式中，預設也是在還沒測試時回 DUDECT_NOT_ENOUGHT_MEASUREMENTS

typedef enum {
    DUDECT_LEAKAGE_FOUND = 0,
    DUDECT_NO_LEAKAGE_EVIDENCE_YET,
    DUDECT_NOT_ENOUGHT_MEASUREMENTS,
} dudect_state_t;

實作 measure.c 和 measure.h ，放置待測程式及 dudect_config_t 的相關設定。並且也實作 is_##op_const 巨集用來產生 is_xxx_const 函數供 qtest.c 內的程式呼叫。此外把 CHUNK_SIZE 提升到 640 使測試更準確。因為版面有限，就不把程式碼貼出來，可點連結觀看。
為了測試看看 dudect 是不是能正常偵測時間差異，我故意把固定資料那組測資的字串長度改成 0，確實 dudect 就能發現非常數時間。確認功能正常後就回復原本設定。

完成以上步驟後，make test 的結果正確回報為執行時間為常數時間。

請提交 pull request。
jserv

可再進一步實驗

嘗試用 perf_event_open 搭配 config = PERF_COUNT_HW_CPU_CYCLES 量測時間。看看能不能更能排除待測程式執行時被中斷的執行時間。
嘗試對原本的 labc-0 中的 dudect 程式做修正，而不是直接引入上游最新版和重寫測試程式。

貢獻與程式改進記錄

修正 GitHub Action 問題

我檢視我的 repository 的 GitHub Action 有無正常運作時，發現 GitHub Action 在 Run webfactory/ssh-agent@v0.7.0 這個步驟時就失敗了。

於是我就看了一下原始的 sysprog21/lab0-c repository 。裡面的 GitHub Action 可以運作成功。發現原來 Run webfactory/ssh-agent@v0.7.0 是用來載入 ssh private key 讓原始 sysprog21/lab0-c repository 在沒有 queue.c 的解答情況下，能從另一個 private repository 拷貝 queue.c 來使用，使原始的 sysprog21/lab0-c repository 的 GitHub 在沒解答情況下也可以測試。

但是在 fork 之後的 repository ，不會有 ssh private key 。導致在 Run webfactory/ssh-agent@v0.7.0 步驟就失敗，以致後面的 make check 、 make test 等步驟都不會執行。

我看了 GitHub 的文件後，發現可以把 GitHub Action 某個步驟標示為即使失敗仍然能繼續執行。故我在 .github/workflows/main.yml 裡進行小修正，針對 webfactory/ssh-agent@v0.7.0 這個步驟加入 continue-on-error: true 來讓它失敗時，也可以往下執行其他 GitHub Action ，使得即便沒有 ssh private key ， GitHub Action 也能有作用。

我為此建了一個 pull request 來提交我的改動，目前已經被 merge 了。

diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
index 56c7d9e..6ed0b93 100644
--- a/.github/workflows/main.yml
+++ b/.github/workflows/main.yml
@@ -8,6 +8,7 @@ jobs:
     steps:
     - uses: actions/checkout@v3.3.0
     - uses: webfactory/ssh-agent@v0.7.0
+      continue-on-error: true
       with:
           ssh-private-key: ${{ secrets.SSH_PRIVATE_KEY }}
     - name: install-dependencies

其他貢獻

#121 Remove return true; in q_quit function
原本的程式 q_quit 一開始就 return true; 導致後面記憶體釋放的程式沒有執行，以致於觸發 valgrind memory leak。此 pull request 改善此問題
#122 Register line_atexit in linenoise function
line_atexit 內會呼叫 free_history 釋放記憶體。但在 stdin 非 tty 時， line_atexit 不會被註冊，以致於使用檔案輸入指令時，沒辦法釋放 linenoise 記憶體，導致 linenoise 出現 memory leak 。此 pull request 修正此問題。
#127 Merge do_i(h|t) into a single function
#130 Fix warning message in do_descend

TODO 放 GitHub Pull requests

其他記錄

cppcheck 問題

要 commit 時發現在 report.c 中的 static char *msg_name_text[N_MSG] 變數宣告會觸發 cppcheck 錯誤。原本打算把此行改為 static char * const msg_name_text[N_MSG] ，但後來發現 GitHub 有更新新的程式碼加入 // cppcheck-suppress constVariable 修正此問題，因此我直接在 GitHub 網頁介面上操作 sync fork 取得更新的程式至自己 fork 出來的 repository 。

因為自己只寫了一點點程式，故直接捨棄本地端的 commit，用 GitHub 上新的程式覆寫本地的 repository 。

可善用 git rebase
jserv

謝謝老師，我會嘗試練習 git rebase

D4nnyLee

2023/02/22 06:49:39

小於~~等於~~

這裡應該是只有小於。在原題的第二個範例中，[1, 1, 1, 1] 做完之後應該要得到 [1, 1, 1, 1]，但如果是小於等於時就刪除的話，最後會得到 [1]。 (Edited)

王彥傑

2023/02/23 22:51:11

謝謝你，你說得沒錯

Jim Huang

2023/03/01 12:34:25

```c /* Swap every two adjacent nodes */ void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ q_reverseK(head, 2); } ```

特例！ (Edited)

Peter Chen; Kohan Chen

2023/03/25 03:42:45

```c static int q_merge_two(struct list_head *first, struct list_head *second) { if (!first || !second) return 0; int count = 0; LIST_HEAD(tmp); while (!list_empty(first) && !list_empty(second)) { element_t *f = list_first_entry(first, element_t, list); element_t *s = list_first_entry(second, element_t, list); if (strcmp(f->value, s->value) <= 0) list_move_tail(&f->list, &tmp); else list_move_tail(&s->list, &tmp); count++; } count += q_size(first) + q_size(second); list_splice(&tmp, first); list_splice_tail_init(second, first); return count; } ```

這一行是否因為 second 可能有剩下的節點沒能比較。 (Edited)

2023/03/25 05:47:54

沒事，迴圈經過 empty ，剩下節點，後面做 splice 接合到 tmp 和 first。只是接在 first 的兩邊。 (Edited)

2023/03/26 10:30:50

cut

很爛的點，cnt 和 cut 長得很像，可能看錯。只是個建議。 (Edited)

2023/03/30 03:21:43

我把 cnt 改為 count 了

2023/03/30 03:22:26

感謝您的提醒。希望能讓程式碼更容易閱讀

2023/03/28 04:02:11

```c /* Remove every node which has a node with a strictly greater value anywhere to * the right side of it */ int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; /** * Traverse from the last entry and remove the element that is * smaller or equal to its right. Also count the number of elements. */ int cnt = 1; element_t *cur = list_last_entry(head, element_t, list); while (cur->list.prev != head) { element_t *prev = list_last_entry(&cur->list, element_t, list); if (strcmp(prev->value, cur->value) < 0) { list_del(&prev->list); q_release_element(prev); } else { cnt++; cur = prev; } } return cnt; } ```

這樣做有機會刪掉局部最大值，當尾部有更大值會全刪掉。 (Edited)

2023/03/28 06:34:43

我似乎想錯了，你的作法才正確。

2023/03/28 06:30:20

如果看 LeetCode 原始題目，它就是要刪除任何元素其右邊有比它大的元素。故若尾部最大值，且沒有元素跟它一樣大，則其左邊元素要全刪是對的 (Edited)

2023/03/31 02:25:36

測

typo: 偵測 (Edited)

2023/03/31 06:44:05

已修正 (Edited)

2023q1 Homework1 (lab0)

開發與實驗環境

進度記錄

改進 queue.c

q_new

q_free

開發過程記錄

q_new_elem

q_insert_head 和 q_insert_tail

q_copy_string

q_remove_head 和 q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_reverse

變更記錄

q_reverseK

q_swap

q_merge_two

q_sort

更新記錄

q_descend

q_merge

更新記錄

q_ascend

Valgrind 與 Address Sanitizer 記憶體檢查

Makefile 中關於 make valgrind 的內容分析

使用 Valgrind

使用 address sanitizer

加入 option descend

修改 q_merge_two

修改 q_sort 和 q_merge

修改 q_ksort

Linux 核心 Linked List 排序研究

整合 Linux 核心的 list_sort

效能分析

Linux Kernel Linked List 排序演算法探索

web 命令/網頁伺服器改善

亂數研究及 shuffle 實作

程式實作

Fisher–Yates shuffle 亂度分析

Entropy 觀察

加入 Xoshiro256++ 亂數產生器並比較系統提供之亂數產生器

Xoshiro256++ 亂數品質測試

系統內建亂數測試

研讀論文〈Dude, is my code constant time?〉

dudect 統計原理

目前 lab0-c 內 dudect 缺陷

對 lab-0 中 dudect 的改進

貢獻與程式改進記錄

修正 GitHub Action 問題

其他貢獻

其他記錄

cppcheck 問題

Read more

2023q1 Homework7 (ktcp)

2023q1 Homework6 (quiz5)

2023q1 Homework5 (assessment)

2023q1 Homework6 (quiz6)

改進 `queue.c`

`q_new`

`q_free`

`q_new_elem`

`q_insert_head` 和 `q_insert_tail`

`q_copy_string`

`q_remove_head` 和 `q_remove_tail`

`q_size`

`q_delete_mid`

`q_delete_dup`

`q_reverse`

`q_reverseK`

`q_swap`

`q_merge_two`

`q_sort`

`q_descend`

`q_merge`

`q_ascend`

Makefile 中關於 `make valgrind` 的內容分析

加入 option `descend`

修改 `q_merge_two`

修改 `q_sort` 和 `q_merge`

修改 `q_ksort`

整合 Linux 核心的 `list_sort`

`web` 命令/網頁伺服器改善

`Xoshiro256++` 亂數品質測試

`dudect` 統計原理

目前 `lab0-c` 內 `dudect` 缺陷

對 `lab-0` 中 `dudect` 的改進