2023q1 Homework4 (quiz4)

contributed by < hankTaro >

測驗 1

說明與改寫

此程式碼運用了大量巨集，因此在對巨集不夠熟悉的其況下會有判讀困難，所以這裡先對於巨集內的程式碼說明，至於將 color 利用對齊在 quiz 3 已有解釋，這邊便不多做解釋

#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)

故在這個巨集中，宣告了好幾組函式，而這接函數的名稱與參數等等，將由此呼叫此巨集傳入的參數決定

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 位置的

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 紀錄尋訪路徑，並記錄尋訪各點與插入點的大小關係

        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 推敲其關係

抵達 leaf 時的狀況

當抵達 leaf 後，便開始利用迴圈反向尋訪，用 pathp-- 找出當前位置的親代節點，將新節點依照存於 pathp 中的大小關係，插入親帶節點的 right 或是 left ，隨後檢查 RBT 是否符合規則，若符合規則便 return ，若未符合，必須向上重複調整，直到符合規則或是抵達 root ，當抵達 root 便是迴圈結束的時候，依據 RBT 規則， root 必須為黑，所以在迴圈結束後將 root 設為黑

        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);                         \

值得注意的是，此程式碼使用的調整規則與一般常見的方法不同，因為在 pathp 的資料結構中，需要確保路徑在被尋訪前不被更改，所以若使用一般的方法處理，有可能會更改到當前節點的親代節點與祖備節點，會導致向上尋訪的路徑出現錯誤，所以要確保平衡的正確，必須不去更動到當前尋訪節點的上方，或是改寫一般方法，在對應的 case 中對 pathp 進行處理，以保持路徑的正確

改善此程式碼

不要濫用成語，依據國語辭典，「畫蛇添足」指多此一舉而於事無補，但你在沒有具體證據並有改進方案之前，只能推論程式碼有改進的機會。

jserv

1. 245 與 258 行中的 rbtn_right_set 和 rbtn_left_set，在 tree 大到一定程度時，其有效功能只會有一次，也就是插入新節點的那一次，在對 RBT 向上尋訪做調整時，這行程式碼會是完全沒用的，故可考慮將其移出迴圈，將新節點的連接作為進入迴圈前置處理的部分，迴圈內則只處理平衡規則的部分

更正: 此行程式碼還有其他作用，因為旋轉後需要將 pathp->node 設為其頂端結點cnode = tnode; pathp->node = cnode; ，所以有其用處

2. 256 行後的程式碼，有大量程式碼 畫蛇添足，其實可以簡化至，其實可以簡化至和 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

想法上有疏漏，在程式碼撰寫階段遇到了問題，需要重新思考改進的方式


文字訊息不要用螢幕截圖展現，尊重視覺障礙者的閱讀權益。另外，你該在 GNU/Linux 環境中實驗，避免用 WSL。

jserv

TODO

能否用其方法改良當前 Linux 核心的 RBT

欲考慮面向

• 效能方面的成本
• 在支援多執行續上是否會受到影響
• 考慮 right_color 的呼叫頻率是否會影響效能(因為每次取得 right 或是 color 都要額外執行一次 bitmask)

---

測驗 2

---

測驗 3

    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