# 2023q1 Homework4 (quiz4)
contributed by< `WeiHongWi` >
## 測驗一
### Insert
```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); \
}
}
pathp->node = node;
...
```
`path->node` 指向 `rbtree->root`，利用指標 pathp 走訪紅黑樹，比較要插入的新節點內含和紅黑樹已有節點的內含值，則 new node 為當下 pathp 所指的 node 的左子樹 , 若新節點的內含值大於 node ,則 new node 為當下 `pathp` 所指的節點的右子樹. 而迴圈的終結條件為 `pathp->node` 為空, 所以此時 node 就放入 `pathp->node`
:::warning
:warning:
1. 改進標示，避免濫用 `**`，標點符號採全形。
2. 避免非必要的中英夾雜
3. 善用 ChatGPT 改寫，漢語書寫不該比 OpenAI 差
4. 探討程式碼之前，應簡述個別操作的特性和要點
:notes: jserv
:::
```c
for (pathp--; (uintptr_t) pathp >= (uintptr_t) path; pathp--){
...
if (pathp->cmp < 0){
x_type *leftleft = rbtn_left_get(x_type, x_field, left);
if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) { \
x_type *tnode;
rbtn_black_set(x_type, x_field, leftleft);
rbtn_rotate_right(x_type, x_field, cnode, tnode);
cnode = tnode;
}
}
...
}
...
```
首先要注意到 for loop 的 initial condition 是 **pathp - -** 也就是 pathp 改為**指向 new node 的 parent**.
```c
if (pathp->cmp < 0)
```
利用結構體 `x_prefix##path_entry_t` 中的成員 `cmp` 來做為判斷 **pathp 所指向的 node 的 children** 在插入 new node 所經過的 path 中為 left child 還是 right child, 接下來從經過的 path 回推到 root ,此時的 for loop 要做的事情確認插入的 node 是否違反 red black tree 的定義.
```c
if (leftleft && rbtn_red_get(x_type, x_field, leftleft))
```
若 path 中有連續兩個 node 為 red 則需要 right rotate 而判斷的條件為上述的 code.
```c
...
else {
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_red_set(x_type, x_field, cnode);
cnode = tnode;
}
...
```
而這段為對 **left leaning** 的情況,其中 left leaning 為 left child 為黑 ,right child 為 red 此時需要 left rotate. 這邊值得注意的是 , **rbtn_color_set**(xtype,x_field, tnode, tred)的使用, 先利用 bool tred 判斷 cnode 的顏色 , 其中判斷式為以下:
```c
((bool) (((uintptr_t) (x_node)->x_field.right_red) & 1))
```
而 bool tred 用在 rbtn_color_set() 使得 tnode 得到 cnode 的 color.
### Remove
一開始和 insert() 一樣,先 search ,這裡我只列出不同的地方,當找到要 remove 的 node 時,也要尋找它的**右子樹中最小的值**,也就是 **leftmost 的 node.** 利用 nodep = pathp 紀錄要 remove 的 node , 並利用 for loop 找到最靠左的 node,當 for loop 結束時 **pathp 指向 leftmost node的 left child** 且此 child 為 NULL.之後也利用 **pathp - -** 回到 leftmost node.而此 leftmost node 也是用來取代預刪除 node 的位置.
```c
for (pathp = path; pathp->node; pathp++) {
...
if (cmp == 0) {
pathp->cmp = 1;
nodep = pathp;
for (pathp++; pathp->node; pathp++) {
pathp->cmp = -1;
pathp[1].node =rbtn_left_get(x_type, x_field, pathp->node);
}
break;
}
...
}
```
再來的 if-else statement 用來判斷預要刪除的 node 是否為 leaf node.
下列的 code 為 ***remove node 非 leaf*** , 所以將 remove node 的左子樹和右子樹和 leftmost node 連接在一起,而其中 if(nodep == path) 用來判斷 nodep 是否為 rb tree 的 root ,因為刪除的 node 有可能在原先的 rb tree 為 root.
```c
if (pathp->node != node)
{
...
rbtn_left_set(x_type, x_field, pathp->node,rbtn_left_get(x_type, x_field, node));
rbtn_right_set(x_type, x_field, pathp->node,rbtn_right_get(x_type, x_field, node));
...
nodep->node = pathp->node;
pathp->node = node;
if (nodep == path){
...
}else{
...
}
}
```
而接著為 ***remove node 為 leaf***.而在之前找尋 leftmost node 是屬於 remove node 的右子樹,所以也要額外確認 remove node 的左子樹,若存在,則和 parent node 做連接 , 其中 **pathp[-1]** 即是 parent node 的表示.再者刪除的 node 為 leaf 所以必為紅色，**做完後就能夠直接 return**.
```c
else{
x_type *left = rbtn_left_get(x_type, x_field, node);
if (left) {
if(pathp==path){
...
}
else{
if (pathp[-1].cmp < 0) {
rbtn_left_set(x_type, x_field, pathp[-1].node, left);
} else {
btn_right_set(x_type, x_field, pathp[-1].node, left);
}
}
}
else{
...
}
}
```
所以接下來要探討的是,刪除的為黑色的 node 時 , path[0],path[1],...,path[-1] 要怎麼更新才能符合 left leaning red black tree 的規範.
目前 pathp 指向用來替代的 node , 若**此替代的 node 為黑色,則需要重新 balance** leaning left red black tree.這裡的 balance 為每段 在 llrb tree 的 path 上的黑色 node 數目相同.
在此之前,已經完成兩種情況的 remove
(1)刪除的 node 為leaf
(2)替代的 node 為 red , 不影響 balance
這裡說明只有替代的 node 為其 parent 的 right child 的情況,舉例來說以**左下**為範例, **7 為替代的 node** , 5 為 pathp 所指向的 node
替代的 node 為右子樹要探討的情況更多,**因為 left leaning 的設定所以不用去探討右上圖的情況**,因此簡單了 red black tree 的實作
:::success
因為要 balance , 所以目標是要讓所有 path 都有相同數目的黑色 node.
:::
第 1 種 : pathp 為 red , pathp 的左子點,利用 rbtn_left_get()得到並命名為 **left** 且**為黑色**, **leftleft** 為 left 的左子點且**為紅色**.
```c
/* ||
pathp(r)
/ \
b b ==>
/
r
*/
...
rbtn_black_set(x_type, x_field, pathp->node);
rbtn_red_set(x_type, x_field, left);
rbtn_black_set(x_type, x_field, leftleft);
rbtn_rotate_right(x_type, x_field, pathp->node,tnode);
...
```
第 2 種
第 3 種
:::info
ToDo: 比較不同寫法的紅黑樹的效能
:::
### 研究 [jemalloc/rb.c](https://github.com/jemalloc/jemalloc/blob/dev/test/unit/rb.c)
---
## 測驗三
### 將測驗 1 對節點的紅色和黑色標注的技巧嵌入到指標變數中
在 rbi.h 中,關於 color 的存放使用 type bool 的 object red 來紀錄 node 的顏色,程式如下
```c
struct rb_node{
struct rb_node *left, *right;
bool red;
}
```
而測驗 1 中的 rb.h 利用記憶體對齊的特性,舉例來說，`__attribute**(aligned(sizeof(long)))` 讓記憶體地址以 4 為倍數成長,則後兩個 bits 用不到可以用來紀錄 node 的 color.
```c
struct rb_node {
struct rb_node *left,*right_red;
}
```
參照 rb.h , 將 rbi.c 的 function 改寫 , 舉例來說 : rbtn_right_get() , 因為前面的 62 個 bits 為真正的 pointer , 所以變為
```c
((x_type*)(((intptr_t)((x_node)->x_field.right)) & ~3))
```
再者 , rbtn_black_set() 和 rbtn_red_set() 改寫成
```c
#define rbtn_red_set(x_type, x_field, x_node) \
do { \
(x_node)->x_field.right = (x_type*)((uintptr_t)((x_node)->x_field.right) | 1); \
} while (0)
#define rbtn_black_set(x_type, x_field, x_node) \
do { \
(x_node)->x_field.right = \
(x_type*)((intptr_t)((x_node)->x_field.right) & ~3); \
} while (0)
```
### 比對 [linux/rbtree.h](https://github.com/torvalds/linux/blob/master/include/linux/rbtree.h)
根據上述的例子，Linux 處理親代節點指標的方式是，將原本只用 1 個 bits 來紀錄 node 的 color 變成用 2 個 bits 來紀錄 node 的 color 和 parent 的 color
```c
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
```
### rb_tree_cached 的機制
Sign in with Wallet
Connect another wallet