# Linux 核心專題: 紅黑樹實作改進
> 執行人: koty6069
> [專題解說錄影](https://youtu.be/1vFhn9fedkU)
:::success
:question: 提問清單
* ?
:::
## 任務描述
重做[第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3) 的測驗一及[第 4 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz4)的測驗一，彙整其他學員的成果，連同延伸問題。
### 第 3 週程式碼解析 [(incomplete treesort.c)](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)
> [2023q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)
此程式主要是使用 C 實作紅黑樹來實作 C++ 中的 [std::map](https://en.cppreference.com/w/cpp/container/map)。
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
定義結構 `node_t` 作為紅黑樹節點，包含 `left` 和 `right` 指向左右子節點，`value` 用來存放數值，`next` 指向原本陣列中的下一個節點。其中 `color` 使用與 [linux 核心](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_types.h) 相同的技巧，宣告 `unsigned long` 儲存親代節點，並透過 `__attribute__((aligned(sizeof(long))))` 將此結構對齊 `sizeof(long)`，因為 `sizeof(long)` 是 8 個 bytes，因此指標的地址會是 8 的倍數，使得最低 3 個位元不會使用到，所以可以將顏色儲存在最低位元中。
> 在 `/usr/include/stdint.h` 可以得知 `uintptr_t` 為 `unsigned long` 型態。
```c
#define rb_parent(r) ((node_t *) (AAAA))
#define rb_color(r) ((color_t) (r)->color & 1)
```
根據名字可以看出 `rb_parent` 用來取得親代節點，`rb_color` 用來取得當前節點的顏色，因為親代節點和顏色同時存放在 `uintptr_t color` 中，要取得顏色就是將最低位元取出，要取得親代節點則是要將最低三個位元設成 0，因此 `AAAA` 為 `(r)->color & ~7`。
```c
typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;
```
在此實作中將紅色設定為 0、黑色為 1，所以設定顏色時就是將最低位元設定為 0 或 1。
```c
#define rb_set_parent(r, p) \
do { \
(r)->color = rb_color(r) | (uintptr_t) (p); \
} while (0)
```
設定親代節點時要注意將此節點的顏色保留下來並透過 `or` 放回 `color` 的最低位元。
```c
#define rb_set_red(r) \
do { \
BBBB; \
} while (0)
#define rb_set_black(r) \
do { \
CCCC; \
} while (0)
```
將節點設成紅色就是將最低位元設成 0，也就是與 `1111...1110` 做 `and`，所以 `BBBB` 為 `(r)->color &= ~1`，將節點設成黑色就是將最低位元設成 0，也就是與 `0000...0001` 做 `or`，因此 `CCCC` 為 `(r)->color |= 1`。
:::danger
在 112 行的 `cmap_create_node` 中發現註解有小錯誤。
```c=118
/* Set the color to black by default */
rb_set_red(node);
```
新加入的節點應該為紅色，對照 119 行也是如此，所以 118 行應該為 red 而非 black。
:::
```c
static node_t *cmap_rotate_left(cmap_t obj, node_t *node)
static node_t *cmap_rotate_right(cmap_t obj, node_t *node)
```
`cmap_rotate_left` 和 `cmap_rotate_right` 為單一次的左旋轉和右旋轉，可參考 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree#%E7%B0%A1%E8%BF%B0%E7%B4%85%E9%BB%91%E6%A8%B9)。`cmap_l_l`、`cmap_l_r`、`cmap_r_r` 和 `cmap_r_l` 則是插入或刪除紅黑樹節點時遇到不同情況進行的調整，會透過 `cmap_fix_colors` 在調整顏色時呼叫這些函式進行使用。
```c
static bool cmap_insert(cmap_t obj, node_t *node, void *value)
```
```c
/* Traverse the tree until we hit the end or find a side that is NULL */
for (node_t *cur = obj->head;;) {
int res = obj->comparator(&node->value, &cur->value);
if (!res) /* If the key matches something else, don't insert */
assert(0 && "not support repetitive value");
if (res < 0) {
if (!cur->left) {
cur->left = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
DDDD;
} else {
if (!cur->right) {
cur->right = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
EEEE;
}
}
```
`cmap_insert` 作用為插入新節點，會透過 `for` 迴圈找到適當的插入位置，與一般的二元搜尋樹相同，透過 `obj->comparator` 取得與當前節點的比較值 `res`，`res` 為 -1 代表要插入的值較小所以往左走，`res` 為 1 代表要插入的值較大因此往右走，若當前節點的左或右子樹為 `NULL`，意味著可以將節點插入在該位置，也就是會進入 `if (!cur->left)` 和 `if (!cur->right)` 條件式中，將節點放入該位置並檢查新增節點後的紅黑樹是否符合規則，若左右子樹不為 `NULL` 就不會進入這兩個 `if` 條件式，代表需要繼續向左或右走，因此 `DDDD` 為 `cur = cur->left`，`EEEE` 為 `cur = cur->right`。
```c
void tree_sort(node_t **list)
{
node_t **record = list;
cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
while (*list) {
cmap_insert(map, *list, NULL);
list = FFFF;
}
node_t *node = cmap_first(map), *first = node;
for (; node; node = cmap_next(node)) {
*list = node;
list = GGGG;
}
HHHH;
*record = first;
free(map);
}
```
`tree_sort` 就是使用 `map` 來進行排序，會傳入一個要被排序的 `list`，在 `while` 迴圈中一個一個將值插入 `map`，可以得知 `FFFF` 是在走訪整個 `list`，也就是要前進到 `list` 中的下個位置，因此 `FFFF` 為 `&(*list)->next`，接著在 `for` 迴圈中使用 `cmap_next` 照順序取出並放回 `list` 即完成排序，`GGGG` 同樣為 `&(*list)->next`，當兩個迴圈都執行完時，`*list` 會落在 `list` 的最尾端，需要將其指向 `NULL` 表示結束，所以 `HHHH` 為 `*list = NULL`。
### 第 4 週程式碼解析
> [2023q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz4)
#### 理解 [Left-leaning Red-Black Trees](https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf)
原先將 2-3-4 樹轉為紅黑樹時，會將 3-node 轉為一紅邊一黑邊的左右子樹，因為紅邊可以在左或右，會導致轉換後的紅黑樹有多種情況，使得實作時程式碼會變得非常複雜，因此提出左傾紅黑樹，將 3-node 固定轉換成左子樹為紅邊的情況，這樣可以把轉換後的紅黑樹限制為一種，2-3-4 樹和紅黑樹之間的關係變為 1-1 對應。
在插入新節點的部分可明顯看出左傾紅黑樹的優勢，只要在搜尋要插入的位置時檢查路徑上遇到的情況並進行以下幾種操作，即可確保整棵樹仍會遵守紅黑樹的規則：
1. 若遇到 4-node （也就是左右子樹皆為紅色），就將顏色翻轉。
2. 遇到右子樹為紅就將其旋轉為左傾。
3. 遇到連續兩個紅邊，執行右旋轉，將其平衡為 4-node。
只要在原始二元搜尋樹的插入操作加入以上幾項檢查即可完成紅黑樹的插入操作，相較於一般的紅黑樹需考慮更多種情況，程式碼顯得更加簡潔。
#### 解析程式碼 [(Incomplete rb.h)](https://gist.github.com/jserv/6610eb56bf2486979c8bf6ee8061f71c)
```c
/* Node structure */
#define rb_node(x_type) \
struct { \
x_type *left, *right_red; \
}
```
使用巨集定義紅黑樹的節點，與第三次作業不同處在於只紀錄左右子節點，並無紀錄親代節點的位址，也因此利用[對齊](https://hackmd.io/@sysprog/linux-rbtree#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E7%B4%85%E9%BB%91%E6%A8%B9%E5%AF%A6%E4%BD%9C)的技巧將顏色儲存在右子樹 （`right_red`） 的最低位元。
```c
/* Right accessors */
#define rbtn_right_get(x_type, x_field, x_node) \
((x_type *) (((intptr_t) (x_node)->x_field.right_red) & ~3))
#define rbtn_right_set(x_type, x_field, x_node, x_right) \
do { \
(x_node)->x_field.right_red = \
(x_type *) (((uintptr_t) x_right) | \
(((uintptr_t) (x_node)->x_field.right_red) & 1)); \
} while (0)
```
取得右節點時要將用不到的最低三位元清空，設定時將傳入的 `x_right` 與存有原本顏色的最低位元做 `or`，用以將原本節點的顏色保留下來。
```c
/* Node initializer */
#define rbt_node_new(x_type, x_field, x_rbt, x_node) \
do { \
/* Bookkeeping bit cannot be used by node pointer. */ \
assert(((uintptr_t) (x_node) & (0x1)) == 0); \
rbtn_left_set(x_type, x_field, (x_node), NULL); \
rbtn_right_set(x_type, x_field, (x_node), NULL); \
rbtn_red_set(x_type, x_field, (x_node)); \
} while (0)
```
初始化一個新的紅黑樹節點，先將左右子節點設為 `NULL`，按照規則會將此節點設為紅色。
```c
/* Internal utility macros */
#define rbtn_rotate_left(x_type, x_field, x_node, r_node) \
do { \
(r_node) = rbtn_right_get(x_type, x_field, (x_node)); \
rbtn_right_set(x_type, x_field, (x_node), \
rbtn_left_get(x_type, x_field, (r_node))); \
rbtn_left_set(x_type, x_field, (r_node), (x_node)); \
} while (0)
#define rbtn_rotate_right(x_type, x_field, x_node, r_node) \
do { \
(r_node) = rbtn_left_get(x_type, x_field, (x_node)); \
rbtn_left_set(x_type, x_field, (x_node), \
rbtn_right_get(x_type, x_field, (r_node))); \
rbtn_right_set(x_type, x_field, (r_node), (x_node)); \
} while (0)
```
執行一次左旋轉或右旋轉的巨集，以左旋為例，會進行三個步驟：
1. 取得原先節點 `x_node` 的左子樹 `r_node`。
2. 將 `r_node` 的左子樹接到 `x_node` 的右子樹。
3. 將 `x_node` 接到 `r_node` 的左子樹。
##### rb_gen
```c
#define rb_gen(x_attr, x_prefix, x_rbt_type, x_type, x_field, x_cmp)
```
`rb_gen` 使用[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)提到的連結技巧，會根據傳入的參數去展開巨集，產生一系列對應的程式碼。
```c
rb_gen(static, tree_, tree_t, node_t, link, node_cmp);
```
在測驗題中將以上參數傳入 `rb_gen`，根據 `rb_proto` 會產生包含 `tree_new`、`tree_insert` 等在內的函式，`tree_t` 為記錄紅黑樹的結構，`node_t` 則為紅黑樹節點， `link` 為節點之間的連結， `node_cmp` 為比較節點大小值的函式，根據註解要求，若值較小需傳回 `-1`，相等傳回 `0`，較大傳回 `1`。
```c
typedef struct { \
x_type *node; \
int cmp; \
} x_prefix##path_entry_t;
```
因為本實作中每個節點只有記錄自己的左右子樹，並沒有記錄親代節點，因此另外定義一個 `tree_path_entry_t` 的結構體，用來在走訪紅黑樹時存放走過的路徑，`node` 就是存放走過的節點內容， `cmp` 則用來記錄比較的結果（也就是上方的 `-1`、`0`、`1`），可以得知要往右或往左走訪。
##### tree_search
作用為在紅黑樹中找到 `key` 值的位置。
```c
int cmp; \
x_type *ret = rbtree->root; \
while (ret && (cmp = (x_cmp) (key, ret)) != 0) { \
if (cmp < 0) { \
ret = rbtn_left_get(x_type, x_field, ret); \
} else { \
ret = rbtn_right_get(x_type, x_field, ret); \
} \
} \
return ret;
```
使用到比較函式 `node_cmp` ，若比較結果 `cmp` 為 `-1` 就往左走，`cmp` 為 `1` 就向右走，`cmp` 為 `0` 代表找到該值，因此就脫離迴圈並回傳。
##### tree_insert
```c
x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node)
```
作用為將節點插入紅黑樹中適當的位置。
```c=1
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;
```
首先建立一個長度為 `RB_MAX_DEPTH` 的 `tree_path_entry_t` 陣列，用來記錄過的路徑，其中`RB_MAX_DEPTH` 就是給予紅黑樹的高度限制，在走訪時可以確定不會超過紅黑樹的高度，`*pathp` 則是在 `for` 迴圈時迭代整個陣列所使用。
在進入迴圈前會將 `root` 放入 `path` 的第一個位置，進入迴圈後，第 7 行會在每次迭代時將比較的結果存進當前陣列位置的 `cmp`，在 9~13 行會依據比較的結果，將左或右子節點放入陣列的下一個位置 `pathp[1]` 接著 `pathp` 會指向下一個位置，當目前的指到的陣列位置 `pathp->node` 為空時，就會離開迴圈，此時指到的陣列位置就是此次路徑的最後一個節點，因此 15 行將預備要插入的節點 `node` 放入。
以下面這顆紅黑樹舉例，假設要插入的節點為 `41`，首先需要找到 `41` 的位置並記錄路徑。
```graphviz
digraph RBT {
graph[ordering="out"]
node [shape=circle, fixedsize=true, style=filled,width=.5]
35, 66[fillcolor=red]
50 -> {35 80}
35 -> {33 48}
80 -> {66}
}
```
1. 41 < 50 ， cmp = -1 ， 往左子樹進行下一次比較。
2. 41 > 35 ， cmp = 1 ， 往右子樹進行下一次比較。
3. 41 < 48 ， cmp = -1 ， 往左子樹進行下一次比較。
4. 遇到 NULL，結束迴圈，將 41 放入 pathp 目前指到的位置。。
找到 `48` 的左子節點為要插入的位置，同時會得到每一輪的 `path` 陣列如下。
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"Round 0" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=7, fixedsize=true];
pointers [label="<f0> pathp | <f1> | <f2> | <f3> ", color=white];
values [label="<f0> node: 50, cmp = | <f1> node: , cmp = | <f2> node: , cmp = | <f3> node: , cmp = ", color=black, fillcolor=lightgray, style=filled];
edge [color=black];
pointers:f0 -> values:f0;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"Round 1" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=7, fixedsize=true];
pointers [label="<f0> pathp | <f1> pathp[1]| <f2> | <f3>", color=white];
values [label="<f0> node: 50, cmp = -1 | <f1> node: 35, cmp = | <f2> node: , cmp = | <f3> node: 35, cmp = ", color=black, fillcolor=lightgray, style=filled];
edge [color=black];
pointers:f0 -> values:f0;
pointers:f1 -> values:f1;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"Round 2" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=7, fixedsize=true];
pointers [label="<f0> | <f1> pathp | <f2> pathp[1]| <f3>", color=white];
values [label="<f0> node: 50, cmp = -1 | <f1> node: 35, cmp = 1 | <f2> node: 48, cmp = | <f3> node: , cmp = ", color=black, fillcolor=lightgray, style=filled];
edge [color=black];
pointers:f1 -> values:f1;
pointers:f2 -> values:f2;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"Round 3" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=7, fixedsize=true];
pointers [label="<f0> | <f1> | <f2> pathp | <f3> pathp[1]", color=white];
values [label="<f0> node: 50, cmp = -1 | <f1> node: 35, cmp = 1 | <f2> node: 48, cmp = -1| <f3> node: NULL, cmp = ", color=black, fillcolor=lightgray, style=filled];
edge [color=black];
pointers:f2 -> values:f2;
pointers:f3 -> values:f3;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=18];
"Round 4" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=7, fixedsize=true];
pointers [label="<f0> | <f1> | <f2> | <f3> pathp", color=white];
values [label="<f0> node: 50, cmp = -1 | <f1> node: 35, cmp = 1 | <f2> node: 48, cmp = -1| <f3> node: 41, cmp = ", color=black, fillcolor=lightgray, style=filled];
edge [color=black];
pointers:f3 -> values:f3;
}
```
```c
for (pathp--; (uintptr_t) pathp >= (uintptr_t) path; pathp--) { \
x_type *cnode = pathp->node;
```
正式進行插入的動作，會從前述路徑 `path` 的倒數第二的節點開始，不斷沿著記錄的路徑向前，在此過程中依序檢查各節點間的關係是否符合紅黑樹的規則，若違反就進行調整，直到達到路徑的起始點 `(uintptr_t) pathp >= (uintptr_t) path`，這樣就能確保整個紅黑樹都符合規則，`cnode` 為當前位置的節點。
```graphviz
digraph {
node [shape=record, fontcolor=black, fontsize=14, width=8, fixedsize=true];
pointers [label="<f0> | <f1> pathp | <f2> cnode", color=white];
values [label="<f0> node: 50, cmp = -1 | <f1> node: 35, cmp = 1 | <f2> node: 48, cmp = -1| <f3> node: 41, cmp = ", color=black, fillcolor=lightgray, style=filled];
edge [color=black];
pointers:f1 -> values:f2;
pointers:f2 -> values:f2;
}
```
```c=
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; \
AAAA(x_type, x_field, leftleft); \
rbtn_rotate_right(x_type, x_field, cnode, tnode); \
cnode = tnode; \
}
```
每次迴圈會以當前指到的節點為主，去檢查 `cmp` 是 `1` 或 `-1`，假如 `cmp < 0` 代表需要將陣列中下一個節點放入左子樹中，因為在紅黑樹中只需要旋轉紅邊，因此當第 4 行發現到下個節點並非紅色時，就不需再繼續檢查，直接 `return`，結束插入的程序。
第 7 行的 `if` 條件式在檢測連續兩個紅邊的情形，也就是最前述提到的第 3 種情況，這時要將其修正為 4-node，於是直行右旋轉將 `left` 調整至目前節點的位置，`AAAA` 為 `rbtn_black_set`。
> 3. 遇到連續兩個紅邊，執行右旋轉，將其平衡為 4-node。
```c=
} 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, BBBB); \
CCCC(x_type, x_field, cnode); \
cnode = tnode; \
} \
} \
pathp->node = cnode;
```
進入 `else` 則是下一節點為右子樹的情形，第 7 行為最前述的第 1 種情形，要將 4-node 分割，因此進行顏色翻轉，將左右子節點設為黑色，當前節點設為紅色。
> 1. 若遇到 4-node （也就是左右子樹皆為紅色），就將顏色翻轉。
第 12 行的 `else` 代表只有右節點為紅色，就是第 2 種情形，要將右子樹的紅邊旋轉去左邊，執行左旋轉後將原本的右節點 `tnode` 轉至 `cnode` 的位置，再將其設為原本 `cnode` 的顏色， `BBBB` 為 `tred`，此時 `cnode` 在原本 `left` 的位置，我們的目的是將紅邊調整至左邊，因此最後要將 `cnode` 設為紅色，`CCCC` 為 `rbtn_red_set`。
> 2. 遇到右子樹為紅就將其旋轉為左傾。
```c
/* Set root, and make it black. */ \
rbtree->root = path->node; \
rbtn_black_set(x_type, x_field, rbtree->root);
```
最後重新記錄 `root` 的位置，並將其設為黑色以保持規則的正確性。
##### tree_remove
用來將節點刪除並對紅黑樹做對應的調整。
```c
x_prefix##path_entry_t path[RB_MAX_DEPTH]; \
x_prefix##path_entry_t *pathp; \
x_prefix##path_entry_t *nodep; \
/* This is just to silence a compiler warning. */ \
nodep = NULL;
```
刪除時一樣使用紀錄路徑的技巧。
```c
if (cmp == 0) { \
/* Find node's successor, in preparation for swap. */ \
pathp->cmp = DDDD; \
nodep = pathp; \
for (pathp++; pathp->node; pathp++) { \
pathp->cmp = -1; \
pathp[1].node = \
rbtn_left_get(x_type, x_field, pathp->node); \
} \
break; \
}
```
當 `cmp == 0` 代表找到要刪除的節點，這邊會把該節點的後續左子節點都記錄進 `path`，直到遇到 `NULL` 才停止，也就是說 `path` 會持續存到左子樹中最小的節點，第 3 行會將 `path` 中原本 `cmp` 為 0 的值改為 1 以確保後面透過 `path` 反向走訪紅黑樹時方向不會錯誤，因此 `DDDD` 為 1。
```c
pathp--;
if (pathp->node != node)
```
這邊會檢查要拿來替代的節點 `pathp->node` 不是目標要刪除的節點 `node`，接著會將兩者交換，也就是將 `node` 的顏色和左右子樹都設定給 `pathp->node`，同時也會將 `path` 中兩者的位置交換。
```c
if (rbtn_red_get(x_type, x_field, pathp->node)) { \
/* Prune red node, which requires no fixup. */ \
assert(pathp[-1].cmp < 0); \
rbtn_left_set(x_type, x_field, pathp[-1].node, NULL); \
return; \
}
```
如果要刪除的節點是紅色，因為不會影響到樹的平衡能夠直接刪除。
```c
pathp->node = NULL; \
for (pathp--; (uintptr_t) pathp >= (uintptr_t) path; pathp--) { \
```
若為黑色，則需要循著 `path` 反向走訪經過的節點並根據不同情況作出平衡。
### 兩種紅黑樹實作方式比較
比較上述兩種紅黑樹的實作方式，最主要的差異在於紅黑樹節點的結構上，quiz3 (Linux 核心風格) 的結構中有左右子節點和親代節點，quiz4 (jemalloc 風格) 同樣有左右子節點，不同之處在於結構體內並無直接紀錄親代節點，取而代之的是在操作紅黑樹時額外利用一個陣列 `path` 記錄走過的紅黑樹路徑，並透過這個路徑對紅黑樹進行平衡。
<!-- 不將親代節點記錄在結構體中帶來的好處是能夠減少每個節點所需的空間，每次透過 cache 交換資料的大小是固定的，如果減少每個節點所需的空間就可以在一次的交換中放入更多節點，除此之外，為了達成此目的所使用的 `path` 是陣列，陣列是連續記憶體，在記憶體操作上比起 quiz3 接近於鏈結串列的存取方式要更加友善，並且在執行操作前就會直接根據紅黑樹的最大高度去配置陣列大小，在執行過程中不會遇到有關記憶體空間不足等配置記憶體的錯誤。-->
## TODO: 紅黑樹實作的效能評比
利用 [rb-bench](https://github.com/jserv/rb-bench)，分析不同紅黑樹實作手法的差異，應當考慮更大的資料範圍
> 對照 [rbtree_bench](https://github.com/ypaskell/rbtree_bench)
### 執行 rb-bench 及結果分析
參考 [Chiwawachiwawa](https://hackmd.io/@CWWPPB/H1IyltGW2#%E5%A6%82%E4%BD%95%E4%BD%BF%E7%94%A8-rb_bench) 同學的執行步驟使用 rb-bench。
1. 執行 `make all`
2. 執行 `./rb-bench > reports/test-linux-emag.xml`
3. 執行 `make images`
得到以下這張圖，在線性時的效能排序和原本的範例圖片有所不同，以下就這張圖進行討論。
> Linear: 插入的節點為遞增的數值。
> RandomOps: 若要插入的隨機數已在樹中就將其移除，反之進行插入。
* Linear: EC > LLRB > bheap > jemalloc > Linux > FreeBSD
* RandomOps: LLRB > EC > jemalloc > FreeBSD > Linux > bheap
可以看出在線性時表現最好的是 FreeBSD，在隨機時表現最好者為 bheap，而 Linux 在兩種情境下都處於第二好的位置，jemalloc 在線性時輸於 Linux 排第三，到隨機時則排到第四名。
接著調整 `test.h` 中的 `small_set_size` （預設是 128）觀察不同方法間的變化。
* `small_set_size = 256`
Linear: EC > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > EC > jemalloc > FreeBSD > Linux > bheap
* `small_set_size = 512`
Linear: EC > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > EC > jemalloc > FreeBSD > Linux > bheap
* `small_set_size = 1024`
Linear: EC > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > EC > jemalloc > FreeBSD > Linux > bheap
* `small_set_size = 2048`
Linear: EC > LLRB > bheap > jemalloc > Linux > FreeBSD
RandomOps: LLRB > EC > jemalloc > FreeBSD > Linux > bheap
### rbtree-linux
```c
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */
```
與 quiz3 中看到的節點結構相同，記錄親代節點，並利用對齊將顏色與親代節點存放在一起。
#### 插入
```c
static void test_rb_linux_insert(void *tree, void *node)
```
```c
rb_link_node(&n->node, parent, next);
rb_linux_insert_color(&n->node, root);
```
在 `test-rbtree-linux.c` 中的 `test_rb-linux-insert` 函式會找到新節點應該插入的位置，接著呼叫 `rb_link_node` 將此節點加入到樹中，再透過 `rb_linux_insert_color` 進行平衡調整。
```c
static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
```
```c
if (!parent) {
rb_set_parent_color(node, NULL, RB_BLACK);
break;
} else if (rb_is_black(parent))
break;
```
在 `rbtree-linux.c` 中會呼叫 `__rb_insert` 進行插入的動作，函式內透過一個無限 `while` 迴圈執行紅黑樹的平衡調整，當親代節點為黑色時，就代表紅黑樹的性質已滿足，不需再做調整，只要親代節點仍是紅的就要持續迴圈進行調整。接著迴圈內主要分成兩種情況，`parent` 是 `gparent` 的左子樹或右子樹，以下討論左子樹的情況。
:::info
下方示意圖中，英文字母小寫為紅色節點，大寫為黑色節點。
:::
```c
Case 1 - color flips
G g
/ \ / \
p u --> P U
/ /
n n
```
若 `uncle node` 為紅色就進行一次顏色翻轉，後將要調整的節點轉移到 `gparent` 上直接進行下一次迴圈。
```c
Case 2 - left rotate at parent
G G
/ \ / \
p U --> n U
\ /
n p
```
若 `uncle node` 為黑且新加入的節點為親代節點的右節點，會以 `parent` 為中心進行一次左旋轉，但這樣會導致連續兩個紅色節點，所以會順勢進入 case 3。
```c
Case 3 - right rotate at gparent
G P
/ \ / \
p U --> n g
/ \
n U
```
遇到連續兩個紅節點時，會以 `gparent` 為中心進行一次右旋轉，調整完後結束迴圈。
在右子樹的情況也是要處理以上三種情況，只是調整的方向不同，總共有六種可能的情況。
#### 刪除
```c
void rb_linux_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *rebalance;
rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
if (rebalance)
____rb_erase_color(rebalance, root, dummy_rotate);
}
```
`rbtree-linux.c` 中的 `rb_linux_erase` 會先呼叫 `rbtree-linux-augmented.h` 中的 `__rb_erase_augmented` 函式將目標節點 `node` 刪除，再根據回傳的 `rebalance` 決定是否要呼叫 `____rb_erase_color` 對紅黑樹做平衡調整。
```c
static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
const struct rb_augment_callbacks *augment)
```
解析刪除的函式 `__rb_erase_augmented`，在刪除 `node` 時大致上會遇到三種情況。
```c
struct rb_node *child = node->rb_right, *tmp = node->rb_left;
...
if (!tmp)
...
/*
* Case 1: node to erase has no more than 1 child (easy!)
*
* Note that if there is one child it must be red due to 5)
* and node must be black due to 4). We adjust colors locally
* so as to bypass __rb_erase_color() later on.
*/
...
__rb_change_child(node, child, parent, root);
...
else if (!child)
...
/* Still case 1, but this time the child is node->rb_left */
...
__rb_change_child(node, child, parent, root);
```
```c
static inline void
__rb_change_child(struct rb_node *old, struct rb_node *new,
struct rb_node *parent, struct rb_root *root)
{
if (parent) {
if (parent->rb_left == old)
parent->rb_left = new;
else
parent->rb_right = new;
} else
root->rb_node = new;
}
```
第一種是 `node` 只有一個子節點或沒有子節點的情況，如果只有左或右子節點，只要將該子節點取代原本 `node` 的位置即可，後續也不用再做調整（`rebalance = NULL`）；若 `node` 沒有子節點，就會根據 `node` 的顏色決定要不要做平衡調整（`rebalance = __rb_is_black(pc) ? parent : NULL`）。
```c
struct rb_node *successor = child, *child2;
tmp = child->rb_left;
```
```c
/*
* Case 2: node's successor is its right child
*
* (n) (s)
* / \ / \
* (x) (s) -> (x) (c)
* \
* (c)
*/
```
第二種情況，當右子節點 `child` 沒有左子樹時，就將其當作 `successor` 用來取代 `node` 的位置。
```c
/*
* Case 3: node's successor is leftmost under
* node's right child subtree
*
* (n) (s)
* / \ / \
* (x) (y) -> (x) (y)
* / /
* (p) (p)
* / /
* (s) (c)
* \
* (c)
*/
```
```c
do {
parent = successor;
successor = tmp;
tmp = tmp->rb_left;
} while (tmp);
/*使用迴圈找到 leftmost 節點*/
```
第三種情況，當右子節點 `child` 有左子樹時，需要找到其左子樹中 leftmost 的節點當作 `successor` 來取代 `node` 的位置，並將 `successor` 的右子節點放到 `successor` 原本的位置。
```c
if (child2) {
successor->__rb_parent_color = pc;
rb_set_parent_color(child2, parent, RB_BLACK);
rebalance = NULL;
} else {
unsigned long pc2 = successor->__rb_parent_color;
successor->__rb_parent_color = pc;
rebalance = __rb_is_black(pc2) ? parent : NULL;
}
```
若 `successor` 有右子節點的情況就不需再作調整，反之則要視 `parent` 是否為黑色決定是否要做後續的平衡調整。
```c
static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
```
平衡時一樣透過無限 `while` 迴圈執行，迴圈內首先會以 `node` 是 `parent` 的左子樹或右子樹做區分，以下討論 `node` 為左子樹的情形。
```c
/*
* Case 1 - left rotate at parent
*
* P S
* / \ / \
* N s --> p Sr
* / \ / \
* Sl Sr N Sl
*/
```
當 `sibling` 為紅色時，會將 `parent` 做一次左旋轉。
```c
/*
* Case 4 - left rotate at parent + color flips
* (p and sl could be either color here.
* After rotation, p becomes black, s acquires
* p's color, and sl keeps its color)
*
* (p) (s)
* / \ / \
* N S --> P Sr
* / \ / \
* (sl) sr N (sl)
*/
```
如果 `sibling` 有右子節點且該節點為黑色，直接跳到 case 4 對 `parent` 做左旋轉以及將顏色翻轉，接著就結束迴圈。
```c
/*
* Case 2 - sibling color flip
* (p could be either color here)
*
* (p) (p)
* / \ / \
* N S --> N s
* / \ / \
* Sl Sr Sl Sr
*
* This leaves us violating 5) which
* can be fixed by flipping p to black
* if it was red, or by recursing at p.
* p is red when coming from Case 1.
*/
```
```c
if (!tmp1 || rb_is_black(tmp1))
...
if (!tmp2 || rb_is_black(tmp2))
```
`sibling` 沒有任何子節點或左右子節點皆為黑色，就要將 `sibling` 和 `parent` 的顏色翻轉，若 `parent` 原本為黑色就要以 `parent` 為主重新進行一次迴圈，若為紅色則可以直接結束迴圈。
```c
/*
* Case 3 - right rotate at sibling
* (p could be either color here)
*
* (p) (p)
* / \ / \
* N S --> N Sl
* / \ \
* sl Sr s
* \
* Sr
*/
```
不符合 case 2 的條件時（左節點為紅色），就對 `sibling` 做右旋轉，接著進入 case 4。
與插入時相同，當 `node` 為右子樹時也是要檢查以上四種情形，只是發生的情況會是對稱的。
### rbtree-jemalloc
```c
#define rb_node(a_type) \
struct { \
a_type *rbn_left; \
a_type *rbn_right_red; \
}
```
節點結構與 quiz4 相同，不記錄親代節點，將顏色與右節點存放一起，這邊同樣是實作左傾紅黑樹。
#### 插入
```c
a_prefix##insert(a_rbt_type *rbtree, a_type *node)
```
```c
a_prefix##path_entry_t path[RB_MAX_DEPTH]; \
a_prefix##path_entry_t *pathp;
```
與前面看過的程式碼相同，插入時會先找到對應的位置，將走訪過的節點使用 `path` 陣列儲存，再反向迭代陣列，除了將節點接上紅黑樹，也要循著走訪路徑將紅黑樹做平衡調整。
```c
for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--)
...
if (rbtn_red_get(a_type, a_field, left))
...
if (rbtn_red_get(a_type, a_field, right))
```
迭代的過程利用 `for` 迴圈往前一一檢查走過的節點，只要當前節點在 `path` 中的下一個節點是紅色，就需要進一步檢查做出對應的調整，若為黑色則代表性質已滿足，會直接結束插入的動作。
```c
/* Fix up 4-node. */
...
/* Split 4-node. */
...
/* Lean left. */
```
在調整時，因為 jemalloc 實作的是左傾紅黑樹，因此需要作出調整的只有以上三種情況，在節點為左子樹時要檢查 `Fix up 4-node.` 情況，在節點為右子樹時要檢查剩下兩種情況，Linux 核心在左右子樹時都要檢查三種狀況，jemalloc 要做的處理相對較少，每個節點檢查過一次並作出調整即可確保符合性質。
#### 刪除
刪除時要先找到 `node` 的位置，在搜尋過程中會將路徑記錄在 `path` 陣列，找到 `node` 後，會持續向左子樹前進，直到找到 leftmost 的節點作為 successor，接著會將 `node` 與 successor 做交換，若 `node` 只有一個左子節點，就直接將該節點接到原本 `node` 的位置。
```c
/* The node to be pruned is black, so unwind until balance is */\
/* restored. */\
...
for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--)
...
if (pathp->cmp < 0)
...
else
```
如果刪除掉的節點是紅色就不需要進行調整，若是黑色就需反向走訪 `path` 陣列，檢查每個節點是否需要平衡調整，檢查時主要分成兩種狀況， `cmp < 0` 或 `cmp > 0` ，也就是 `pathp[1].node` 是在左子樹或在右子樹的情況。
```c
/* || */\
/* pathp(r) */\
/* // \ */\
/* (b) (b) */\
/* / */\
/* (r) */\
```
當 `cmp < 0` 以及 `pathp->node` 為紅色的情況下，若有 `right-left` 且為紅色，會透過兩次旋轉將其轉移到目前 `pathp` 到的節點位置。
```c
/* || */\
/* pathp(r) */\
/* // \ */\
/* (b) (b) */\
/* / */\
/* (b) */\
```
若 `right-left` 為黑色，會使用一次旋轉將 `right` 轉到 `pathp` 的位置。
```c
if (pathp[-1].cmp < 0) { \
rbtn_left_set(a_type, a_field, pathp[-1].node, \
tnode); \
} else { \
rbtn_right_set(a_type, a_field, pathp[-1].node, \
tnode); \
} \
```
因為不記錄親代節點，在上述的旋轉後要透過 `rbtn_left_set` 或 `rbtn_right_set` 將旋轉後的節點接到原本 `pathp->node` 的位置。
當 `pathp->node` 為黑色時一樣要檢查上述兩種情況並進行調整，差異在於節點顏色設置的不同。
```c
/* || */\
/* pathp(b) */\
/* / \\ */\
/* (r) (b) */\
/* \ */\
/* (b) */\
/* / */\
/* (r) */\
```
當 `cmp > 0` 以及 `pathp->node` 為黑色、 `left` 為紅色時，若有 `left-right-left` 且為紅色，就會執行三次旋轉，將 `left-right` 轉至 `pathp->node` 的位置。若 `left-right-left` 為黑色，則只要一次旋轉，將 `left` 轉上來。
```c
/* || */\
/* pathp(r) */\
/* / \\ */\
/* (b) (b) */\
/* / */\
/* (r) */\
```
若 `pathp->node` 為紅色、 `left` 為黑色以及 `left-left` 為紅色，會執行一次旋轉將 `left` 移至 `pathp->node` 的位置，`left-left` 為黑色時，則不須旋轉，僅調整顏色即可。
```c
/* || */\
/* pathp(b) */\
/* / \\ */\
/* (b) (b) */\
/* / */\
/* (r) */\
```
若 `pathp->node` 為黑色、 `left` 為黑色以及 `left-left` 為紅色，會執行一次旋轉將 `left` 移至 `pathp->node` 的位置。若 `left-left` 為黑色，則直接將 `left` 設為紅色。
光從程式碼的行數可以看出，jemalloc 在刪除後要做平衡調整時可能會遇到的情況比 Linux 核心更多，加上 jemalloc 會透過紀錄的路徑一個節點一個節點去做檢查，因此在刪除時帶來的效能提升就不像插入時那麼多。
:::warning
研讀〈[Left-Leaning Red-Black Trees Considered Harmful](https://read.seas.harvard.edu/~kohler/notes/llrb.html)，理解經典的紅黑樹和調整過的 LLRB 實作之間的效能落差。
:notes: jserv
:::
### 研讀〈[Left-Leaning Red-Black Trees Considered Harmful](https://read.seas.harvard.edu/~kohler/notes/llrb.html)〉
#### Parent Pointers
LLRB 的提出者 Robert Sedgewick 在實作左傾紅黑樹時並沒有使用到 parent pointers，因為他認為這樣會增加大量的 overhead，並且無法減少要處理的情況數量；但本文作者覺得 parent pointers 所帶來的 overhead 沒有那麼嚴重。
透過 parent pointers 能夠輕易地走訪整個紅黑樹，可以很快速地找到任何節點的 successor 或 predecessor，在 amortized time 測量下可以達到 O(1) 的時間複雜度，如果不使用 parent pointers 也可以達到類似的成效，但會需要有一個儲存從當前節點到根節點所有節點的路徑（例如 jemalloc 中的 `path` 陣列），這樣就需要花費額外的空間去儲存，而且有可能比存在節點結構中的指標需要更多的空間。
本文作者也透過實驗去比較 parent pointers 的有無對紅黑樹不同操作的效能影響，結果發現有 parent pointers 的情況下插入、搜尋和刪除所花費的時間的確較長，但差距非常的小。
> Insert phase: 0.556s without parents, 0.576s with parents (1.03x)
> Find phase: 1.656s without parents, 1.672s with parents (1.01x)
> Delete phase: 1.024s without parents, 1.108s with parents (1.08x)
此外，文中有提到 jemalloc 在移除 parent pointers 後減少了 0.4% 的記憶體開銷。
#### Additional rotations
原本的紅黑樹有限制操作時進行旋轉的次數，插入時最多兩次旋轉，刪除時不能超過三次旋轉，但 Sedgewick 提出的左傾紅黑樹實作中，3-nodes 必須是向左生長的，透過這個限制將最終產生的紅黑樹情形減少，也因為此限制，很明顯的可以看出有效的左傾紅黑樹數量會小於有效的傳統紅黑樹數量，為了使左傾紅黑樹符合限制，勢必得使用更多次的旋轉進行調整，也因此會產生更多的記憶體存取。
尤其在刪除的過程中，左傾紅黑樹會在由上而下搜尋要刪除節點的過程中就針對節點的情況進行旋轉，在刪除掉目標節點後，又會循著先前走訪的路徑由下而上的去對樹進行修正，本文作者認為這些過程中許多的旋轉可能是不必要的，再加上左傾紅黑樹不使用 parent pointers，在向下搜尋的過程中會需要進行比較並將結果記錄下來，這也會導致額外的時間或記憶體花費（作者有提到通常進行比較的成本是非常大的）。
本文作者透過實驗發現左傾紅黑樹的插入和刪除時所需的旋轉次數都明顯大於傳統紅黑樹，尤其在刪除時左傾紅黑樹所需的旋轉次數平均會是傳統紅黑樹的 51 倍，這是非常誇張的效能落差。
> Insert phase: Normal RB 0.582 rotations/insert, LLRB 1.725 rotations/insert (2.96x—probably a constant factor)
> Delete phase: Normal RB 0.380 rotations/delete, LLRB 19.757 rotations/delete (51.99x!!—both a constant factor and a log-N factor)
#### Perfomance
作者最終實驗得到的結論是傳統紅黑樹的效能都勝過 Robert Sedgewick 實作的左傾紅黑樹，很明顯就是因為額外的旋轉步驟降低了左傾紅黑樹的效能，尤其是在刪除時會有大量的旋轉操作，導致效能差距更大。
> Insert phase: conventional RB 0.476s, LLRB 0.560s (1.18x)
> Find phase: conventional RB 1.648s, LLRB 1.680s (1.02x)
> Delete phase: conventional RB 0.612s, LLRB 1.032s (1.69x)
### Linux 核心紅黑樹與 jemalloc 比較
Linux 核心在實作上因為節點結構中有紀錄親代節點，因此在插入、刪除或平衡調整時，除了改變親代節點的子節點外，還要另外去設定該節點的親代節點（`rb_set_parent`、`rb_set_parent_color`）。在 jemalloc 中，不使用 parent pointers，而是在進行插入或刪除時才會用 `path` 陣列去記錄走過的路徑，直接減少了每個節點結構體的大小，在 cacheline 固定為 64 bytes 的情況下，可以使一次能放入 cache 的節點數量增加，提升整體系統的使用效率；透過記錄 cmp 的技巧， `path` 陣列在存取前一個（`pathp[-1].node`）或後一個節點（`pathp[1].node`）時，也受益於陣列連續記憶體的特性，比起直接透過 parent pointers 存取節點的 Linux 核心對 cache 更不容易發生 cache miss 的情況，在進行平衡調整後，也只要透過 `rbtn_left_set` 或 `rbtn_right_set` 將調整後的節點接到原本節點的位置即可。
對照下方 rbtree_bench 提供的測試數據，可以看到在插入和搜尋時都有顯著的效能提升，推測就是因為 jemalloc 較不容易發生 cache miss 的狀況，減少浪費掉的時間，在插入時因為要處理的調整狀況較少，也能夠提升一定的效能，而刪除的部分因為要調整的情況反而較為繁複，使得刪除時的效能提升較少。
:::warning
[rbtree_bench](https://github.com/ypaskell/rbtree_bench) 提供測試數據:
> The following data represents the average time of 20 experiments, each involving the insertion, finding, and deletion of 1 million randomly generated nodes in a random order tested on Apple M1 Pro (10 core)
>
> | Type | Insert (ns) | Find (ns) | Remove (ns) |
> | ----------- | ----------: | --------: | ----------: |
> | linux-flavor | 746263750 | 62612250 | 804232500 |
> | jemalloc-flavor | 613500500 | 34647200 | 760888100 |
> | improvement | 17 % | 44 % | 5.5 % |
:::
## TODO: 研讀 jemalloc 的紅黑樹實作
以 jemalloc 內建的測試程式來探討 [rb.h](https://github.com/jemalloc/jemalloc/blob/dev/include/jemalloc/internal/rb.h) 行為，解讀其效能表現
按照 `INSTALL.md` 的指示安裝後執行 `run_tests.sh`。
## TODO: 研究 Linux 核心紅黑樹效能改進方案
Sign in with Wallet
Connect another wallet