執行人: EdwardCKC
專題解說錄影
重做第 4 週測驗題的測驗三,包含延伸問題,以掌握紅黑樹實作議題。
重做第 4 週測驗題的測驗三,包含延伸問題,彙整其他學員的成果。至少要包含:
rb_node
只包含 left
, right
這二個指標,parent
指標被調整到哪?為何這樣的紅黑樹依舊可運作?RB_LOG2_MAX_NODES
用於計算紅黑樹中節點的最大數量的對數值,也用作控制樹的最大深度。
參考並整理 Korin777 同學的 quiz 4 測驗三 以及 Toneary 同學的 quiz 4 測驗三:
因為 node_t
的大小為 sizeof(void *) * 4
所以 node 最多有
取 可以得到:
在 加入 32 bit 或 64 bit 架構判定後就會是:
若 sizeof(void*) == 8
就會是
問題: 為什麼在 32-bit 或以下的系統是 -3(8) 和 -2(4)?
因為不太能理解RB_LOG2_MAX_NODES
的程式碼,所以使用 gcc -E
去顯示 printf(RB_LOG2_MAX_NODES)
在 preprocessor 階段的結果,再配合 gcc -O3 -S
去輸出組合語言的結果:
發現 RB_LOG2_MAX_NODES
是 59
直接在 compile-time 轉成一個常數,同時在《Demystifying the Linux CPU Scheduler》紅黑樹的部分提到,在32 bit 和 64 bit 架構會因為 alignment,使最後的2 和 3 significant bits 沒有被使用。
最後,經過老師的解釋才明白 RB_LOG2_MAX_NODES
也是用作分配紅黑樹的最少記憶體空間
Kernel developers combined the parent node with the color by alignment. __attribute__((aligned(sizeof(long)))) would make rb_node structure aligned to the size of long, and with respect to 32-bit and 64-bit architectures, the alignment would be 4 bytes and 8 bytes. Resulting in the least 2 (for 32-bit) or 3 (for 64-bit) significant bits unused. Storing the 1-bit color information (0 for red and 1 for black) in the LSB would not cause any problem andleads to saving an additional bit.
sum_subtree
利用 rbtn_left_get
和 rbtn_right_get
以迭代方式走訪整個紅黑樹,並計算所有節點的值的總和
這是左傾紅黑樹 (LLRBT),所以第 260 行會先檢查左子節點是否為 NULL
在for loop (263-264 行)除了檢查 pre
的右子節點非空,還檢查不是目前節點,是為了確保在走訪節點時,不會進入無限循環的情況。
同時在 267-271 行,檢查如果右子節點是空的,就先把 node
插入為 pre
節點的右子節點,再更新 node
為左子節點,使下一次循環迭代時,會繼續走訪目前節點的左子樹。
如果右子節點非空,等於目前節點的右子樹已經被走訪過。在這種情況下,將 pre
節點的右子節點設為 NULL;這樣做的目的是防止重複存取目前節點。
親代節點紀錄在 re_tree
的 root
指標是因為在走訪或改變樹的結構 (旋轉) 才需要用到,把親代節點 獨立出來可以節省記憶體和簡化紅黑樹的實作。需要時可以通過走訪樹獲取親代節點。
以 rb_gen_insert
來說 path[RB_MAX_DEPTH]
會紀錄走訪時的路徑(包括親代節點),當目前節點在 rotate 時要改變親代節點,會把 path->node
更新到 rbtree->root
再把親代節點設定為黑色。
##
是 concatenation 的意思,以 rb_gen
部分片段為例:
rb_gen_insert
如何新增節點完整巨集 rb_gen_insert 程式碼
gcc -E -P
展開 rb_gen_insert
的函式path
array,用於存儲搜尋路徑。路徑中的每個節點都包含一個子節點的指標以及一個布爾值 less,表示節點應該插入到左子樹或右子樹。path
資料結構為什麼要再宣告 pathp
的指標是因為搜尋路徑的長度是動態的。使用 pathp
的好處是可以在走訪過程中修改 path
,並且可以方便地在走訪完畢後獲取最終的路徑結果。
root
node 開始,根據新節點的值與每個節點的值進行比較,向下走訪樹並更新路徑。(less
function)link
結構的特性)pathp
為將被加入的新節點link
資料結構struct {
node_t *left, *right;
_Bool red;
} link;
while (pathp-- != path)
loop 會在 if (pathp->less)
比較最後一個節點與新節點的值去判定要插入左/右子節點(左為少)root
node 設置為路徑中的第一個節點,並將根節點標記為黑色,完成新增節點的操作。參考並整理 wanghanchi 同學的 quiz 4 測驗三 以及 Hongweii 同學的 quiz 4 測驗三:
因為 4 byte alignment 關係,所以最後兩個 bits 用不到可以用來紀錄 node 的顏色。將節點結構顏色標注嵌入到右邊節點的指標變數當中
改寫其他巨集
Linux 核心的 rbtree 具備 cache 機制 (參見 Red-black Trees (rbtree) in Linux),探討其原理,並嘗試在上述程式碼的基礎之上實作。
對照《Demystifying the Linux CPU Scheduler》第 3.1 節 "Red-black tree" 相關描述
在 Linux 核心的 rbtree.h
就已經有定義 RB_ROOT_CACHED
,它的這個 cache 機制是加入到 root node 裡面, 然後 cache 的是整個紅黑樹的最左邊的 node, 而最左邊的 node 的值也是最小的。 為什麼要 cache 整個樹最小的值,可以用 cpu scheduler 為例子作說明:
在《Demystifying the Linux CPU Scheduler》提到紅黑樹是用來記錄那些將被執行的 runnable tasks 的 vruntime
Red-black tree The runnable tasks are stored inside a red-black tree (RB- tree), where processes are inserted based on a linear ordering of execution time.
…
the task to run next is the one with the smallest vruntime.
而最小的 vruntime
task 會最先被執行,那在有 cache 最左邊的 node (最小 vruntime
) 情況下會是 O(1) 的存取時間,而非是 O(log n)。
在 linux 核心的紅黑樹的 node 結構如下:
加入 cache 機制的 root node 結構:
它多了一個 rb_leftmost
的指標直接記錄最左邊的 node 的位置,使一開始在訪問時 root node 就可以直接跳過走訪的過程,減少了走訪的時間。