---
tags: linux kernel
---
# 2023q1 Homework4 (quiz4)
contributed by < `hankTaro` >
## 測驗 `1`
### 說明與改寫
此程式碼運用了大量巨集，因此在對巨集不夠熟悉的其況下會有判讀困難，所以這裡先對於巨集內的程式碼說明，至於將 color 利用對齊在 [quiz 3](https://hackmd.io/@hankTaro/linux2023-quiz3) 已有解釋，這邊便不多做解釋
```c=1
#define rb_gen(x_attr, x_prefix, x_rbt_type, x_type, x_field, x_cmp) \
typedef struct { \
x_type *node; \
int cmp; \
} x_prefix##path_entry_t; \
x_attr void x_prefix##new (x_rbt_type * rbtree) \
{ \
rb_new(x_type, x_field, rbtree); \
} \
```
在第一次縮排內的程式碼為有大量的 concatenation，用於用 `rb_gen` 傳入的參數取代巨集中的 `x_attr` `x_prefix` 等等
假如 `rb_gen(static, tree_, tree_t, node_t, link, node_cmp);` ，第 6 行會變成 `static void tree_new (tree_t* rbtree)`
故在這個巨集中，宣告了好幾組函式，而這接函數的名稱與參數等等，將由此呼叫此巨集傳入的參數決定
```c
x_attr void x_prefix##new (x_rbt_type * rbtree) {...}
x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node) {...}
x_attr void x_prefix##remove(x_rbt_type *rbtree, x_type *node) {...}
x_attr void x_prefix##destroy_recurse(x_rbt_type *rbtree, x_type *node,
void (*cb)(x_type *, void *),
void *arg) {...}
x_attr void x_prefix##destroy(x_rbt_type *rbtree,
void (*cb)(x_type *, void *),
void *arg) {...}
```
在這個巨集中分別宣告了以上 5 種函式
接下來便開始說明此程式碼是如何省略掉結構中的 parent 位置的
<!--
```c
/* Node structure */
#define rb_node(x_type) \
struct { \
x_type *left, *right_red; \
}
struct node_ {
rb_node(node_t) link;
int key;
};
```
等同
```c
struct node_ {
struct link{
node_t *left, *right_red;
} ;
int key;
};
``` -->
```c
typedef struct { \
x_type *node; \
int cmp; \
} x_prefix##path_entry_t;
...
x_prefix##path_entry_t path[RB_MAX_DEPTH]; \
x_prefix##path_entry_t *pathp;
```
此省略 parent 的方法，其概念是利用上方 `pathp` 紀錄尋訪路徑，並記錄尋訪各點與插入點的大小關係
```c
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);
}
}
```
以上程式碼為，從 root 一路利用比較 `node` 與當前尋訪的節點，來決定下一個尋訪的節點，並記錄各節點與 `node` 的大小關係，由於從上而下尋訪並未記錄各 `*pathp` 的連接關係(`right` or `left`)，所以需要在從下而上尋訪時，利用 `pathp->cmp` 推敲其關係
```graphviz
graph graphname {
label=""
n01 [label="A",color="b"] ;
n01 -- n02 ;
n01 -- n03 ;
n02 [label="B",color="b"] ;
n03 -- n05 ;
n03 -- n04 ;
n03 [label="C",color="red"] ;
n04 [label="D",color="b"] ;
n05 [label="E",color="b"] ;
n06 [label="new node",color="red"] ;
n07 [label="NULL",color="b"] ;
n05 -- n06 ;
n05 -- n07 ;
}
```
``` graphviz
digraph graphname {
label="path[]"
list_1[label="<f0>(A,1)|<f1>(C,-1)|<f2>(E,-1)|<f3>(NULL)|<f4>|<f5>|<f6>|<f7>",shape=record, fixedsize=false,width=6]
ptr [label=pathp ,shape=plaintext]
ptr->list_1:f3
ptr2 [label="pathp--" ,shape=plaintext]
ptr2->list_1:f2
}
```
> 抵達 leaf 時的狀況
當抵達 leaf 後，便開始利用迴圈反向尋訪，用 `pathp--` 找出當前位置的親代節點，將新節點依照存於 `pathp` 中的大小關係，插入親帶節點的 right 或是 left ，隨後檢查 RBT 是否符合規則，若符合規則便 `return` ，若未符合，必須向上重複調整，直到符合規則或是抵達 `root` ，當抵達 `root` 便是迴圈結束的時候，依據 RBT 規則， `root` 必須為黑，所以在迴圈結束後將 `root` 設為黑
```c=241
for (pathp--; (uintptr_t) pathp >= (uintptr_t) path; pathp--) { \
x_type *cnode = pathp->node; \
if (pathp->cmp < 0) { \
x_type *left = pathp[1].node; \
rbtn_left_set(x_type, x_field, cnode, left); \
if (!rbtn_red_get(x_type, x_field, left)) \
return; \
x_type *leftleft = rbtn_left_get(x_type, x_field, left); \
if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) { \
/* Fix up 4-node. */ \
x_type *tnode; \
rbtn_black_set(x_type, x_field, leftleft); \
rbtn_rotate_right(x_type, x_field, cnode, tnode); \
cnode = tnode; \
} \
} else { \
x_type *right = pathp[1].node; \
rbtn_right_set(x_type, x_field, cnode, right); \
if (!rbtn_red_get(x_type, x_field, right)) \
return; \
x_type *left = rbtn_left_get(x_type, x_field, cnode); \
if (left && rbtn_red_get(x_type, x_field, left)) { \
/* Split 4-node. */ \
rbtn_black_set(x_type, x_field, left); \
rbtn_black_set(x_type, x_field, right); \
rbtn_red_set(x_type, x_field, cnode); \
} else { \
/* Lean left. */ \
x_type *tnode; \
bool tred = rbtn_red_get(x_type, x_field, cnode); \
rbtn_rotate_left(x_type, x_field, cnode, tnode); \
rbtn_color_set(x_type, x_field, tnode, tred); \
rbtn_rotate_left(x_type, x_field, cnode); \
cnode = tnode; \
} \
} \
pathp->node = cnode; \
} \
/* Set root, and make it black. */ \
rbtree->root = path->node; \
rbtn_black_set(x_type, x_field, rbtree->root); \
```
值得注意的是，此程式碼使用的調整規則與[一般常見的方法](http://alrightchiu.github.io/SecondRound/red-black-tree-insertxin-zeng-zi-liao-yu-fixupxiu-zheng.html)不同，因為在 `pathp` 的資料結構中，需要確保路徑在被尋訪前不被更改，所以若使用一般的方法處理，有可能會更改到當前節點的親代節點與祖備節點，會導致向上尋訪的路徑出現錯誤，所以要確保平衡的正確，必須不去更動到當前尋訪節點的上方，或是改寫一般方法，在對應的 case 中對 pathp 進行處理，以保持路徑的正確
### 改善此程式碼
:::warning
不要濫用成語，依據[國語辭典](https://dict.revised.moe.edu.tw/dictView.jsp?ID=83966)，「畫蛇添足」指多此一舉而於事無補，但你在沒有具體證據並有改進方案之前，只能推論程式碼有改進的機會。
:notes: jserv
:::
<s>1. `245` 與 `258` 行中的 `rbtn_right_set` 和 `rbtn_left_set`，在 tree 大到一定程度時，其有效功能只會有一次，也就是插入新節點的那一次，在對 RBT 向上尋訪做調整時，這行程式碼會是完全沒用的，故可考慮將其移出迴圈，將新節點的連接作為進入迴圈前置處理的部分，迴圈內則只處理平衡規則的部分
> 更正: 此行程式碼還有其他作用，因為旋轉後需要將 `pathp->node` 設為其頂端結點`cnode = tnode;` `pathp->node = cnode;` ，所以有其用處
2. `256` 行後的程式碼，有大量程式碼 <s>畫蛇添足</s>，其實可以簡化至，其實可以簡化至和 `246` 行後相同架構
3. 利用 `switch` 減少迴圈次數以及分支數量(需要先實施第一點)
> 當前程式碼與一般程式碼的差別在於，一般方法是從子節點向上觀察其親代節點與親代節點的平輩節點，而此程式碼的方法是從當前節點向下觀察其路徑上的節點，由於一般方法處理完一次平衡問題，便會將當前節點移動到區域頂端節點再次做判斷(case 1 的話)，也就是說此程式碼只需要將初始節點設在插入節點的祖輩節點，在第一次進入迴圈後，除了遇到 case 1 ，都無須再做平衡，而 case 1 做完後只需要將 `pathp -= 2` 就可以進行下一次的判斷
* 因為 RBT 只有在 case 1 調整後的頂端節點，或是插入新節點以上兩者的親代節點為紅色時，才需要再次調整，所以只要判斷 pathp 下兩次路徑的顏色是否都為紅，若沒有則可 return (因為第一次插入前 RBT 必定合法，所以無須考慮當前節點與插入節點的親代節點都為紅的狀況)
* 可利用 switch 寫出四種 case ，分別是 case 0 直接 return, case 1 調整完後要向上調整 , case 2~3 調整完後直接 return</s>
:::danger
想法上有疏漏，在程式碼撰寫階段遇到了問題，需要重新思考改進的方式
:::
```c
```
<!-- 
-->
<s>
</s>
:::danger
文字訊息不要用螢幕截圖展現，尊重視覺障礙者的閱讀權益。另外，你該在 GNU/Linux 環境中實驗，避免用 WSL。
:notes: jserv
:::
TODO
### 能否用其方法改良當前 Linux 核心的 RBT
欲考慮面向
* 效能方面的成本
* 在支援多執行續上是否會受到影響
* 考慮 right_color 的呼叫頻率是否會影響效能(因為每次取得 right 或是 color 都要額外執行一次 bitmask)
---
## 測驗 `2`
---
## 測驗 `3`
<!-- 
 -->
```c
if (cmp(cur, next)) {
while (next < last && cmp(cur, next)) {
++run_len;
cur += size;
next += size;
}
} else {
while (next < last && cmp(cur, next)) {
++run_len;
cur += size;
next += size;
}
__reverse(first, next, size);
}
```
else 中的 `while (next < last && cmp(cur, next))` 永不成立，因為若成立，就會不進 else
Sign in with Wallet
Connect another wallet