2021q1 Homework1 (quiz1)

contributed by < akamayu-ouo >

第一周測驗題

#define LLL left = &((*left)->next)
#define AAA &right
#define BBB &left
#define CCC                      \
    list_concat(&result, pivot); \
    list_concat(&result, right)

list_concat

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next);
    *left = right;
}

假設這個函式被用以下方式呼叫

list_concat(&X, Y);

因此 left 的初始值為 &X，right 則為 Y 。

X 為 NULL

此時的關係

跳過迴圈後執行 *left = right; ，將 *left（X）設成 right （A 的記憶體位置）。

回傳後的結果即為

X 不為 NULL

進入函式時變數的關係如下：

因為對指標 A->B 等價於 (*A).B ，第 3 行可以改寫成

left = &((**left).next);

將 *left 、**left 以及 (**left).next 分別標注在圖上就是

更新 left 後它會指向 A.next，此時 **left 即為 A 的下一個元素 B 。值得注意的是 X 的值維持不變，呼叫者仍有辦法以此找到 linked list 的起始點 A（然而在函數中已無法得知 X 的值了）。

重複 left = &((**left).next); ，直到 *left 的值是 NULL 。此時 left 指向以 X 為首的 linked list 中最後一個元素的 next 變數。

跳出迴圈後執行 *left = right; ，將 B.next 設成 right 。

回傳後呼叫者看到的結果如下

Quick Sort

void quicksort(node_t **list)
{
    if (!*list)
        return;

    /* 選擇 pivot：從要排序的數字中選擇一個數字，此處直接使用第一個數字 */
    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    /* 分割：將要排序的數字依照跟 pivot 的大小關係分為兩組（ pivot 不參與分組 ）*/
    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? &right : &left, n);
    }

    /* 遞迴：用 quick sort 排好那兩組數字 */
    quicksort(&left);
    quicksort(&right);

    /* 組合：以「不大於 — pivot — 大於」的順序組合在一起，得到排好的序列 */
    node_t *result = NULL;
    list_concat(&result, left);
    list_concat(&result, pivot);
    list_concat(&result, right);
    *list = result;
}

用圖來解釋

• 選擇 pivot

• 分割成兩條 lists

• 將其分別排序

• 重新接合

Memory Leak

範例測試程式中，若檢查發現 linked list 沒有正確排序，程式會馬上結束，但沒有釋放記憶體，造成 memory leak。

if (!list_is_ordered(list))
    return EXIT_FAILURE;

list_free(&list);
return EXIT_SUCCESS;

將範例程式中的 quicksort(&list) 那行註解掉後使用 valgrind --leak-check=full 測試的結果如下：

==3686237== HEAP SUMMARY:
==3686237==     in use at exit: 320 bytes in 20 blocks
==3686237==   total heap usage: 21 allocs, 1 frees, 1,344 bytes allocated
==3686237==
==3686237== 320 (16 direct, 304 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==3686237==    at 0x483E77F: malloc (vg_replace_malloc.c:307)
==3686237==    by 0x1091A1: list_make_node_t (in /.../sysprog21/Week1/quiz1/main)
==3686237==    by 0x1094BD: main (in /.../sysprog21/Week1/quiz1/main)
==3686237==
==3686237== LEAK SUMMARY:
==3686237==    definitely lost: 16 bytes in 1 blocks
==3686237==    indirectly lost: 304 bytes in 19 blocks
==3686237==      possibly lost: 0 bytes in 0 blocks
==3686237==    still reachable: 0 bytes in 0 blocks
==3686237==         suppressed: 0 bytes in 0 blocks
==3686237==
==3686237== For lists of detected and suppressed errors, rerun with: -s
==3686237== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

從輸出資訊（第 8 與 9 行）可以看出沒有被收回的記憶體是由函式 list_make_node_t 透過 malloc 配置。

我將測試程式修改如下以避免 memory leak。

-    if (!list_is_ordered(list))
-        return EXIT_FAILURE;
+    const bool ordered = list_is_ordered(list);

     list_free(&list);
-    return EXIT_SUCCESS;
+
+    return ordered ? EXIT_SUCCESS : EXIT_FAILURE;

Random

根據 rand(3)：

If no seed value is provided, the rand() function is automatically seeded with a value of 1.

也就是說，若在呼叫 rand() 之前沒有用 srand() 設定過種子， rand() 的行為會跟使用 1 作為種子一樣。因此範例程式才會總是產生出一樣的測試資料。

我改用 lrand48 來產生亂數。

All the functions work by generating a sequence of 48-bit integers, Xi, according to the linear congruential formula:
Xn+1 = (aXn + c) mod m, where n >= 0
The parameter m = 2^48, hence 48-bit integer arithmetic is performed. Unless lcong48() is called, a and c are given by:
a = 0x5DEECE66D
c = 0xB

To Be Continued …