2023q1 Homework4 (quiz4)

contributed by< WeiHongWi >

測驗一

Insert

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);  \
    }                       
}
pathp->node = node;
...

path->node 指向 rbtree->root，利用指標 pathp 走訪紅黑樹，比較要插入的新節點內含和紅黑樹已有節點的內含值，則 new node 為當下 pathp 所指的 node 的左子樹 , 若新節點的內含值大於 node ,則 new node 為當下 pathp 所指的節點的右子樹. 而迴圈的終結條件為 pathp->node 為空, 所以此時 node 就放入 pathp->node

1. 改進標示，避免濫用 **，標點符號採全形。
2. 避免非必要的中英夾雜
3. 善用 ChatGPT 改寫，漢語書寫不該比 OpenAI 差
4. 探討程式碼之前，應簡述個別操作的特性和要點

jserv

for (pathp--; (uintptr_t) pathp >= (uintptr_t) path; pathp--){
...
    if (pathp->cmp < 0){
        x_type *leftleft = rbtn_left_get(x_type, x_field, left);
        if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) {     \                       
            x_type *tnode;
            rbtn_black_set(x_type, x_field, leftleft);
            rbtn_rotate_right(x_type, x_field, cnode, tnode);
            cnode = tnode;
        }
    }
...
}
...

首先要注意到 for loop 的 initial condition 是 pathp - - 也就是 pathp 改為指向 new node 的 parent.

if (pathp->cmp < 0)

利用結構體 x_prefix##path_entry_t 中的成員 cmp 來做為判斷 pathp 所指向的 node 的 children 在插入 new node 所經過的 path 中為 left child 還是 right child, 接下來從經過的 path 回推到 root ,此時的 for loop 要做的事情確認插入的 node 是否違反 red black tree 的定義.

if (leftleft && rbtn_red_get(x_type, x_field, leftleft))

若 path 中有連續兩個 node 為 red 則需要 right rotate 而判斷的條件為上述的 code.

...
else {
    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_red_set(x_type, x_field, cnode);
    cnode = tnode;
}
...

而這段為對 left leaning 的情況,其中 left leaning 為　left child 為黑 ,right child 為 red 此時需要 left rotate. 這邊值得注意的是 , rbtn_color_set(xtype,x_field, tnode, tred)的使用, 先利用 bool tred 判斷 cnode 的顏色 , 其中判斷式為以下:

((bool) (((uintptr_t) (x_node)->x_field.right_red) & 1))

而 bool tred 用在 rbtn_color_set() 使得 tnode 得到 cnode 的 color.

Remove

一開始和 insert() 一樣,先 search ,這裡我只列出不同的地方,當找到要 remove 的 node 時,也要尋找它的右子樹中最小的值,也就是 leftmost 的 node. 利用 nodep = pathp 紀錄要 remove 的 node , 並利用 for loop 找到最靠左的 node,當　for loop 結束時 pathp 指向 leftmost node的 left child 且此 child 為 NULL.之後也利用 pathp - - 回到 leftmost node.而此 leftmost node 也是用來取代預刪除 node 的位置.

for (pathp = path; pathp->node; pathp++) {
    ...
    if (cmp == 0) {
        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;
    }
    ...
}

再來的 if-else statement 用來判斷預要刪除的 node 是否為 leaf node.

下列的 code 為 remove node 非 leaf , 所以將 remove node 的左子樹和右子樹和 leftmost node 連接在一起,而其中 if(nodep == path) 用來判斷 nodep 是否為 rb tree 的 root ,因為刪除的 node 有可能在原先的 rb tree 為 root.

if (pathp->node != node)
{
    ...
    rbtn_left_set(x_type, x_field, pathp->node,rbtn_left_get(x_type, x_field, node)); 
    rbtn_right_set(x_type, x_field, pathp->node,rbtn_right_get(x_type, x_field, node));
    ...
    nodep->node = pathp->node;
    pathp->node = node;
    if (nodep == path){
        ...
    }else{
        ...
    }
}

而接著為 remove node 為 leaf.而在之前找尋 leftmost node 是屬於 remove node 的右子樹,所以也要額外確認 remove node 的左子樹,若存在,則和 parent node 做連接 , 其中 pathp[-1] 即是 parent node 的表示.再者刪除的 node 為 leaf 所以必為紅色，做完後就能夠直接 return.

else{
    x_type *left = rbtn_left_get(x_type, x_field, node);
    if (left) {
        if(pathp==path){
        ...
        }
        else{
            if (pathp[-1].cmp < 0) {
                rbtn_left_set(x_type, x_field, pathp[-1].node, left);
            } else {
                btn_right_set(x_type, x_field, pathp[-1].node, left);
            }
        }     
    }
    else{
        ...
    }
}

所以接下來要探討的是,刪除的為黑色的 node 時 , path[0],path[1],…,path[-1] 要怎麼更新才能符合 left leaning red black tree 的規範.

目前 pathp 指向用來替代的 node , 若此替代的 node 為黑色,則需要重新 balance leaning left red black tree.這裡的 balance 為每段 在 llrb tree 的 path 上的黑色 node 數目相同.

在此之前,已經完成兩種情況的 remove
(1)刪除的 node 為leaf
(2)替代的 node 為 red , 不影響 balance

這裡說明只有替代的 node 為其 parent 的 right child 的情況,舉例來說以左下為範例, 7 為替代的 node , 5 為 pathp 所指向的 node

替代的 node 為右子樹要探討的情況更多,因為 left leaning 的設定所以不用去探討右上圖的情況,因此簡單了 red black tree 的實作

因為要 balance , 所以目標是要讓所有 path 都有相同數目的黑色 node.

第 1 種 : pathp 為 red , pathp 的左子點,利用 rbtn_left_get()得到並命名為 left 且為黑色, leftleft 為 left 的左子點且為紅色.

    
    /*           ||
              pathp(r)
              /     \
             b       b   ==> 
            /
           r 
    */
...
rbtn_black_set(x_type, x_field, pathp->node);
rbtn_red_set(x_type, x_field, left);
rbtn_black_set(x_type, x_field, leftleft);
rbtn_rotate_right(x_type, x_field, pathp->node,tnode);
...

第 2 種

第 3 種

ToDo: 比較不同寫法的紅黑樹的效能

研究 jemalloc/rb.c

---

測驗三

將測驗 1 對節點的紅色和黑色標注的技巧嵌入到指標變數中

在 rbi.h 中,關於 color 的存放使用 type bool 的 object red 來紀錄 node 的顏色,程式如下

struct rb_node{
    struct rb_node *left, *right;
    bool red;
}

而測驗 1 中的 rb.h 利用記憶體對齊的特性,舉例來說，__attribute**(aligned(sizeof(long))) 讓記憶體地址以 4 為倍數成長,則後兩個 bits 用不到可以用來紀錄 node 的 color.

struct rb_node {
    struct rb_node *left,*right_red;
}

參照 rb.h , 將 rbi.c 的 function 改寫 , 舉例來說 : rbtn_right_get() , 因為前面的 62 個 bits 為真正的 pointer , 所以變為

((x_type*)(((intptr_t)((x_node)->x_field.right)) & ~3))

再者 , rbtn_black_set() 和 rbtn_red_set() 改寫成

#define rbtn_red_set(x_type, x_field, x_node) \
    do {                                      \
        (x_node)->x_field.right = (x_type*)((uintptr_t)((x_node)->x_field.right) | 1); \
    } while (0)
#define rbtn_black_set(x_type, x_field, x_node) \
    do {                                        \
        (x_node)->x_field.right =          \
            (x_type*)((intptr_t)((x_node)->x_field.right) & ~3); \
    } while (0)

比對 linux/rbtree.h

根據上述的例子，Linux 處理親代節點指標的方式是，將原本只用 1 個 bits 來紀錄 node 的 color 變成用 2 個 bits 來紀錄 node 的 color 和 parent 的 color

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

rb_tree_cached 的機制