Try   HackMD

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







graphname



n01

A



n02

B



n01--n02




n03

C



n01--n03




n05

E



n03--n05




n04

D



n03--n04




n06

new node



n05--n06




n07

NULL



n05--n07










graphname

path[]


list_1

(A,1)

(C,-1)

(E,-1)

(NULL)

 

 

 

 



ptr
pathp



ptr->list_1:f3





ptr2
pathp--



ptr2->list_1:f2





抵達 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 進行處理,以保持路徑的正確

改善此程式碼

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

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

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

  1. 256 行後的程式碼,有大量程式碼 畫蛇添足,其實可以簡化至,其實可以簡化至和 246 行後相同架構
  2. 利用 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

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


![](https://i.imgur.com/phNEaO1.png)

文字訊息不要用螢幕截圖展現,尊重視覺障礙者的閱讀權益。另外,你該在 GNU/Linux 環境中實驗,避免用 WSL。
:notes: 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