---
# System prepended metadata

title: 2023q1 Homework4 (quiz4)
tags: [linux]

---

# 2023q1 Homework4 (quiz4)
contributed by < `LiChiiiii` >

>測驗題目：[quiz4](https://hackmd.io/@sysprog/linux2023-quiz4)

## 測驗一
在測驗一提供的程式碼中定義
```c
typedef rb_tree(node_t) tree_t;
rb_gen(static, tree_, tree_t, node_t, link, node_cmp);
```
對照 [rb.h](https://gist.github.com/jserv/6610eb56bf2486979c8bf6ee8061f71c) 之巨集的使用，展開 `rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp)` 巨集可以得到插入、刪除等功能之函式。

#### 推敲其設計思維
##### `tree_insert()`
將巨集 `x_attr void x_prefix##insert(x_rbt_type *rbtree, x_type *node)` 展開為 `static void tree_insert (tree_t *rbtree, node_t *node)` ，此函式將新節點插入紅黑樹中，主要有三個步驟：
1. 根據節點的比較結果遞迴查找插入位置
2. 依次從下往上檢查是否需要旋轉
3. 將根節點設為黑色。

舉個例子來說，現在有一個紅黑樹。
```graphviz
digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.5]
    
    2[fillcolor=red]
    
    A,B,C,D,E,F[fontsize=0,color=transparent] 
    7 -> {2 11}
    2 -> {1 5}
    1 -> {A B} 
    5 -> {C D}
    11 -> {E F}
    
}
```
我們想插入新的節點 `3`，會先用 BST 的概念尋找插入的位置。 
1.  `3` 與 `7` 比較，紀錄 cmp = -1 ，並往左進行下一層尋找。
2.  `3` 與 `2` 比較，紀錄 cmp = 1 ，並往右進行下一層尋找。
3.  `3` 與 `5` 比較，紀錄 cmp = -1 ，並往左進行下一層尋找，得到 NULL 跳出迴圈，把插入位置指向此節點，也就是 `pathp->node = node` 。
```graphviz
digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.5]
    
    2,3[fillcolor=red]
    
    A,B,C,D,E,F[fontsize=0,color=transparent] 
    7 -> {2 11}
    2 -> {1 5}
    1 -> {A B} 
    5 -> {3 D}
    11 -> {E F} 
}
```
由於在尋找插入的位置的過程中，有依序紀錄經過每個節點及其 cmp 至名為 path 的陣列，因此當找到插入位置的同時，也得到了以下陣列 path 。
```graphviz
digraph path{
    // node [shape=plaintext, fontcolor=black, fontsize=18];
    // "Pointers:" -> "Values:" [color=white];

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    pointers [label="<f0> | <f1> | <f2>pathp |<f3> pathp[1]", color=white];
    values [label="<f0> 7, -1 | <f1> 2, 1 | <f2> 5, -1 | <f3> 3", fillcolor=pink, style=filled];

    // { rank=same; "Pointers:"; pointers }
    // { rank=same; "Values:"; values }

    edge [color=black];
    pointers:f2 -> values:f2;
    pointers:f3 -> values:f3;
}
```
接下來將 pathp 反向回去，判斷每個 pathp 的 cmp 值來檢查是否需要旋轉。
如果 cmp < 0 ，且出現左邊狀況則進行旋轉成右邊的樣子。
```graphviz
digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.7]
    
    left, leftleft [fillcolor=red]
    A,B[fontsize=0,color=transparent] 

    cnode -> left
    cnode -> A [color=transparent]
    left -> leftleft
    // left -> B [color=transparent]
    

    
    left_[fillcolor=red]
    A,B[fontsize=0,color=transparent] 
    left_ -> leftleft_
    left_ -> cnode_
}
```
```c
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;                                      
}                   
```
如果 cmp >= 0 ，
1. 出現左邊狀況則進行顏色轉換設定成右邊的樣子。
```graphviz
digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.7]
    
    left, right [fillcolor=red]

    cnode -> left
    cnode -> right
    
    cnode_[fillcolor=red]
    cnode_ -> left_
    cnode_ -> right_
}
```
2. 出現左邊狀況則進行旋轉成右邊的樣子。這邊是為了滿足 LLRBT 的左傾條件。
```graphviz
digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.7]
    
    tnode [fillcolor=red]
    null, null1[fontsize=0,color=transparent] 

    cnode -> null[color=transparent]
    cnode -> tnode
    
    cnode_[fillcolor=red]
    tnode_ -> cnode_
    tnode_ -> null1[color=transparent]
}
```
```c
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);  
    rbtn_red_set(x_type, x_field, cnode);    
    cnode = tnode;        
}                   
```
最後將根節點設為黑色。

##### `tree_remove()`
將巨集 `x_attr void x_prefix##remove(x_rbt_type *rbtree, x_type *node)` 展開為 `static void tree_remove(tree_t *rbtree, node_t *node)` ，此函式用於刪除紅黑樹中的節點，跟 `tree_insert()` 一樣的方式去尋找要刪除的節點，只是額外加上 `if(cmp==0)` ，若條件式成立，則表示找到要刪除的節點，接著就是找出節點的 successor ，來為交換做準備。
舉個例子來說，現在有一個紅黑樹，我想刪除節點 `2`。
```graphviz
digraph BST {
    graph[ordering="out"]
    node [shape=circle, fixedsize=true, style=filled,width=.5]
    
    2[fillcolor=red]
    
    A,B,C,D,E,F[fontsize=0,color=transparent] 
    7 -> {2 11}
    2 -> {1 5}
    1 -> {A B} 
    5 -> {C D}
    11 -> {E F}
    
}
```
可以得到這個 path 陣列。
```graphviz
digraph path{
    // node [shape=plaintext, fontcolor=black, fontsize=18];
    // "Pointers:" -> "Values:" [color=white];

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    pointers [label="<f0> | <f1>pathp ", color=white];
    values [label="<f0> 7, -1 | <f1> 2, -1 ", fillcolor=pink, style=filled];

    // { rank=same; "Pointers:"; pointers }
    // { rank=same; "Values:"; values }

    edge [color=black];
    pointers:f1 -> values:f1;
}
```
在 `cmp == 0` 時，代表找到想刪除的節點，也就是找到節點 `2`，會設定 pathp->cmp = 1 ，並尋找此節點的 successor 。
```c
if (cmp == 0) {
/* Find node's successor, in preparation for swap. */    
    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;                                                    
} 
```
因此 path 陣列會變成
```graphviz
digraph path{
    // node [shape=plaintext, fontcolor=black, fontsize=18];
    // "Pointers:" -> "Values:" [color=white];

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    pointers [label="<f0>pathp[-1] | <f1>pathp | <f2>pathp[1] ", color=white];
    values [label="<f0> 7, -1 | <f1> 2, 1 | <f2> 1, -1", fillcolor=pink, style=filled];

    // { rank=same; "Pointers:"; pointers }
    // { rank=same; "Values:"; values }

    edge [color=black];
    pointers:f0 -> values:f0;
    pointers:f1 -> values:f1;
    pointers:f2 -> values:f2;
}
```


## 測驗二
## 測驗三