---
tags: linux
---

# 2023q1 Homework3 (quiz3)
contributed by < `kata1219` >

> [第三週測驗題題目](https://hackmd.io/@sysprog/linux2023-quiz3)
> [實作程式碼(未完成)](https://github.com/kata1219/linux2023_quiz/tree/main/quiz3-c)

### 測驗 `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))));

:::info
補充
ChatGPT: 此段是用來將這個 struct 對齊為 long 的長度，這樣可以確保在結構體中使用的 long 變量的存取速度最快。
> 根據 [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)，如使用 64 位元的電腦在 malloc 時會以 16 bytes 對齊，使用上面方法對齊可從 $16*\lceil40/16\rceil=48$ 減少為 $8*\lceil40/8\rceil=40$。
:::

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

又一個發現一個用法

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

:::info
ChatGPT: 用於創建一個封閉的區塊，從而允許定義區塊中的區域變數。
> 感覺寫起來比下面這個作法更簡潔。

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

:::

`node_t` 結構如下:

digraph G {
    node [shape=record];
    node_struct [label="{<node_port> node_t|{<color> color|{<parent> parent}}}"];
    node_struct:head_port -> node_struct:node_port [style=invis];
    node_struct:size_port -> node_struct:head_port [style=invis];
}

#### 延伸問題
1. 指出 treesort.c 程式碼的缺失並改進

2. 利用 Linux 核心的 list.h 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 Tree sort 的效率
3. 研讀 Linux 核心的 Red–black tree 程式碼，比較給定的 treesort.c 實作手法，指出後者的改進空間並予以實作

---

### 測驗 `2`

#### 延伸問題

---

### 測驗 `3`

#### 延伸問題

---

### 測驗 `4`

#### 延伸問題