2023q1 Homework4 (quiz4)

tags: linux2023

contributed by < Paintako >

測驗 1

typedef struct {                                          \
        x_type *node;                                     \
        int cmp;                                          \
    } x_prefix##path_entry_t;  

閱讀前置處理器篇, 得知 x_prefix## 是透過 cpp 來展開產生程式碼的, 註釋也有提示 :

*   x_prefix:
*     Prefix for generated functions (e.g., ex_).

故產生出來的程式碼會像是 x_prefix##path_entry_t -> ex_path_entry_t

rb_gen macro

insert

這段程式是 left-leaning 2-3 red-black trees 的實作
參考 LLRB

插入時, 先找到插入位置, 再從從樹葉一路往上到 root 調整

因為是左傾樹, 所以如果遇到插入時, 所以插入時遇到只有右子時需要往左調整

如果遇到連續兩個紅點 (or link), 則需要做 balance

而遇到 4 樹的情況, 需要做分裂

4 樹: node with 3 keys and 4 children
3、4 樹 in RB trees:

• 用 紅邊 表示 3、4 樹的邊
• 3樹:
• 4樹:

 x_prefix##path_entry_t path[RB_MAX_DEPTH];                             \
        x_prefix##path_entry_t *pathp;                                         \
        rbt_node_new(x_type, x_field, rbtree, node);                           \
        /* Wind. */                                                            \
        path->node = rbtree->root;  

一開始不曉得為何 path 明明就是宣告成 array 的形式, 但卻可以直接賦值, 但後來想到, path 雖然是一個 array, 但 array 等同於指向 array[0] 的指針, 所以當我們使用 path->node 時, 相當於 path[0].node, 這樣的寫法可以省去紀錄 i, 並且只通過操作指標的方式取得 array 中的成員.

 pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);

而這裡為何是 pathp[1]? 因為我們只是操作 pointer, 而 pointer 的下一個成員即是樹中的下一個節點.

這邊插入一個新節點時, 從 root 開始比較, 並且把比較的結果 ( cmp ) 以及比較的節點紀錄在 path 中

找到要插入的位置後, 看 path 中前一個點 (父點) 的資訊, 前一個點中有 cmp , 可以得知插入點是屬於左子 ( cmp < 0 ), 或者右子 (cmp > 0)

給定一節點 x, 考慮以下情形:

1. rbtn_rotate_left
2. rbtn_rotate_right

第一種 rotate_left

• 旋轉前:

• 旋轉後:
  

第二種 rotate_right

• 旋轉前:

• 旋轉後:
  

 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); // AAAA         \
                    rbtn_rotate_right(x_type, x_field, cnode, tnode);          \
                    cnode = tnode;                                             \
                }                 

此段程式碼是檢查出現連續兩紅點的情形, 如果連續出現兩個紅點, 則旋轉調整, 而調整完後是 4 樹, 所以這邊先對 leftleft 調整成黑點, 則在調整完後, 就已經是 4 樹分裂的情形.

 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);  // BBBB     \
                    rbtn_red_set(x_type, x_field, cnode);  // CCCC             \
                    cnode = tnode;                                             \
                }                                                              \
            }                                                                  \
            pathp->node = cnode;                                               \
        }                                    

上面的是考慮 插入的點 > 比較節點 的情形, 如圖示

這種情況下, 比較節點有兩種情形:

1. 沒有左子, 或者左子不是紅的 :
   這種情況, 會先紀錄 cnode 的顏色, 並且左旋轉, 旋轉上來的 tnode 設為 cnode 的顏色, 並且因為旋轉後的 cnode 改成紅色, 並且往上繼續檢查

2. 有左子, 並且左子是紅的, 也就是 4 樹, 如下圖:
   

   
   這種情形只需調整顏色即可

Todo:
圖表改成 Graphviz & TreeComparison

remove

else {                                                             \
    pathp[1].node = rbtn_right_get(x_type, x_field, pathp->node);  \
    if (cmp == 0) {                                                \
    /* Find node's successor, in preparation for swap. */          \
    pathp->cmp = 1; // DDDD                                        \
    nodep = pathp;                                                 \
    for (pathp++; pathp->node; pathp++) {                          \
        pathp->cmp = -1;                                           \
        pathp[1].node =                                            \
            rbtn_left_get(x_type, x_field, pathp->node);           \
        }                                                          \
        break;                                                     \
    }                                                              \
}                                                        

要刪除某個節點時, 一樣先從 root 一路往下尋找要刪除的點, 這邊我們假設已經找到要刪除的點, 用一個指針 nodep 記錄刪除地址, 再來往右子樹開始找, 找到 右子樹中最小的點, 作為替代點, 這也就是為何 pathp->cmp (第5行) 要設為 1 的原因.

接著, 判斷刪除點是否有 successor, 有的話把此點拉上來替代

這個點有三種情況:

• case1: 是 right-least (右子樹中最小的)
• case2: 沒有右子但有左子
• case3: 這個樹只有刪除點一點

首先是第一種情況: 後繼者在右子樹當中

if (pathp->node != node) {                                             \
            /* Swap node with its successor. */                                \
            bool tred = rbtn_red_get(x_type, x_field, pathp->node);            \
            rbtn_color_set(x_type, x_field, pathp->node,                       \
                           rbtn_red_get(x_type, x_field, node));               \
            rbtn_left_set(x_type, x_field, pathp->node,                        \
                          rbtn_left_get(x_type, x_field, node));               \
            /* If node's successor is its right child, the following code */   \
            /* will do the wrong thing for the right child pointer.       */   \
            /* However, it doesn't matter, because the pointer will be    */   \
            /* properly set when the successor is pruned.                 */   \
            rbtn_right_set(x_type, x_field, pathp->node,                       \
                           rbtn_right_get(x_type, x_field, node));             \
            rbtn_color_set(x_type, x_field, node, tred);                       \
            /* The pruned leaf node's child pointers are never accessed   */   \
            /* again, so don't bother setting them to nil.                */   \
            nodep->node = pathp->node;                                         \
            pathp->node = node;                                                \
            if (nodep == path) {                                               \
                rbtree->root = nodep->node;                                    \
            } else {                                                           \
                if (nodep[-1].cmp < 0) {                                       \
                    rbtn_left_set(x_type, x_field, nodep[-1].node,             \
                                  nodep->node);                                \
                } else {                                                       \
                    rbtn_right_set(x_type, x_field, nodep[-1].node,            \
                                   nodep->node);                               \
                }                                                              \
            }                         

1. 先找到後繼者的位置 pathp, 並把連結顏色 assign 給後繼者
2. 再來把要刪除節點 node 的左右子點 assign 給後繼者, 就可以把 node 給移除了
3. 移除後, 判斷後繼者的位置, 如果他是 root, 代表此點沒有雙親, 反之, 找出他的父母並 assign 給此點

再來考慮第二種情況, 也就是沒有右子, 但是有左子的情況, 有左子同樣判斷以下條件:

1. 如果找到後繼者的位址 == pathp, 也就是找到的位置位於樹根, 那麼將 root 的位址改成刪除點的左子
2. 不是以上情況, 只要把左子拉到刪除的位置並且 assign 他的左右父點即可

最後是第三種情況, 刪除點的位置位於 root, 這時只需要判斷 nodep == path 即可確定是不是刪除點 = root