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 進行處理,以保持路徑的正確
不要濫用成語,依據國語辭典,「畫蛇添足」指多此一舉而於事無補,但你在沒有具體證據並有改進方案之前,只能推論程式碼有改進的機會。
:notes: jserv
1. 245
與 258
行中的 rbtn_right_set
和 rbtn_left_set
,在 tree 大到一定程度時,其有效功能只會有一次,也就是插入新節點的那一次,在對 RBT 向上尋訪做調整時,這行程式碼會是完全沒用的,故可考慮將其移出迴圈,將新節點的連接作為進入迴圈前置處理的部分,迴圈內則只處理平衡規則的部分
更正: 此行程式碼還有其他作用,因為旋轉後需要將
pathp->node
設為其頂端結點cnode = tnode;
pathp->node = cnode;
,所以有其用處
256
行後的程式碼,有大量程式碼 246
行後相同架構switch
減少迴圈次數以及分支數量(需要先實施第一點)
當前程式碼與一般程式碼的差別在於,一般方法是從子節點向上觀察其親代節點與親代節點的平輩節點,而此程式碼的方法是從當前節點向下觀察其路徑上的節點,由於一般方法處理完一次平衡問題,便會將當前節點移動到區域頂端節點再次做判斷(case 1 的話),也就是說此程式碼只需要將初始節點設在插入節點的祖輩節點,在第一次進入迴圈後,除了遇到 case 1 ,都無須再做平衡,而 case 1 做完後只需要將
pathp -= 2
就可以進行下一次的判斷
想法上有疏漏,在程式碼撰寫階段遇到了問題,需要重新思考改進的方式
文字訊息不要用螢幕截圖展現,尊重視覺障礙者的閱讀權益。另外,你該在 GNU/Linux 環境中實驗,避免用 WSL。
:notes: jserv
TODO
欲考慮面向
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