---
tags: Linux Kernel
---

# 2023q1 Homework4 (quiz4)
contributed by < [`chun61205`](https://github.com/chun61205) >

> [2023q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz4)

## 測驗一
### 解釋程式碼原理

:::warning
列出程式碼之前，應提及程式碼的設計考量、列出你的觀察和推測，稍後再來驗證，而非對著程式碼「舉燭」。
:notes: jserv
:::
#### `RB_MAX_DEPTH`

#define RB_MAX_DEPTH (sizeof(void *) << 4)

這段程式碼在定義紅黑樹的最大高度。猜測是因為紅黑樹的高度增長較慢，且這裡的紅黑樹實作並沒有使用到親節點，而是採用「走訪路徑」的方式實作插入等巨集，因此如果樹高太高會造成效率大大降低。並且，限制最大高度還能確保樹不會占用太大空間。
#### 資料結構

/* Node structure */
#define rb_node(x_type)           \
    struct {                      \
        x_type *left, *right_red; \
    }

/* Root structure */
#define rb_tree(x_type) \
    struct {            \
        x_type *root;   \
    }

此段程式碼實作 Left-Leaning 2-3 Red-Black Trees ，可以看的出來顏色被儲存在 `right_red` 。而為什麼親節點不會被使用則需要再觀察。
#### `insert`
先解釋 `insert` 的第一部分。

x_prefix##path_entry_t path[RB_MAX_DEPTH];                             \
x_prefix##path_entry_t *pathp;                                         \
rbt_node_new(x_type, x_field, rbtree, node);                           \
/* Wind. */                                                            \
path->node = rbtree->root;                                             \
for (pathp = path; pathp->node; pathp++) {                             \
    int cmp = pathp->cmp = x_cmp(node, pathp->node);                   \
    assert(cmp != 0);                                                  \
    if (cmp < 0) {                                                     \
        pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);   \
    } else {                                                           \
        pathp[1].node = rbtn_right_get(x_type, x_field, pathp->node);  \
    }                                                                  \
}                                                                      \
pathp->node = node;                                                    \

觀察這段程式碼後可以發現，之所以這個紅黑樹實作沒有使用到親節點，是因為這裡使用 `pathp` 走訪整個樹，將走訪的路徑記錄下來後，再把目標節點插入到尾端。
實際的運作流程可以參考 [WangHanChi](https://hackmd.io/@wanghanchi/linux2023-quiz4#tree_insert) 的說明。

---

## 測驗二
## 測驗三