2023q1 Homework3 (quiz3)

contributed by < kata1219 >

第三週測驗題題目
實作程式碼(未完成)

測驗 1

發現了一個我還沒看過的用法 __attribute__((aligned(sizeof(long))))。由於題目中需要計算記憶體地址，訂定明確的 struct 大小。

typedef struct __node
{
    uintptr_t color;
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t __attribute__((aligned(sizeof(long))));

補充
ChatGPT: 此段是用來將這個 struct 對齊為 long 的長度，這樣可以確保在結構體中使用的 long 變量的存取速度最快。

根據 你所不知道的 C 語言：記憶體管理、對齊及硬體特性，如使用 64 位元的電腦在 malloc 時會以 16 bytes 對齊，使用上面方法對齊可從

$16\ast \lceil 40/16\rceil =48$ 減少為

$8\ast \lceil 40/8\rceil =40$。

cmap_new() 使用到了函式指標，在 q_sort() 中也有類似的用法，用來決定排序的順序。

又一個發現一個用法

#define rb_set_red(r) \
    do                \
    {                 \
        BBBB;         \
    } while (0)

ChatGPT: 用於創建一個封閉的區塊，從而允許定義區塊中的區域變數。

感覺寫起來比下面這個作法更簡潔。

#define MAX(a, b)          \
    ({                     \
        typeof(a) _a = a;  \
        typeof(b) _b = b;  \
        _a > _b ? _a : _b; \
    })

node_t 結構如下:

延伸問題

1. 指出 treesort.c 程式碼的缺失並改進

2. 利用 Linux 核心的 list.h 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 Tree sort 的效率

3. 研讀 Linux 核心的 Red–black tree 程式碼，比較給定的 treesort.c 實作手法，指出後者的改進空間並予以實作

---

測驗 2

延伸問題

---

測驗 3

延伸問題

---

測驗 4

延伸問題