2022q1 第 18 週測驗題

tags: linux2022

目的: 檢驗學員對 Linux 核心資料結構和 bitwise 操作 的認知

作答表單:

• 測驗 1 (Linux 核心設計)

測驗 1

rbtree-minimal 是改寫自 Linux 核心紅黑樹的實作，參考的測試程式執行輸出如下:

rbtree testing -> test 1 (latency of nnodes insert+delete): 11820 cycles
 -> test 2 (latency of nnodes cached insert+delete): 13024 cycles
 -> test 3 (latency of inorder traversal): 2269 cycles
 -> test 4 (latency to fetch first node)
        non-cached: 18 cycles
rbtree_cached testing        cached: 2 cycles

請補完原始程式碼，使其運作符合預期。作答規範:

• XXXX, YYYY, ZZZZ 是包含 , (逗號) 的參數列表，不包含小括號 (即 ( 和 ))，且都該要有 RB_RED 或 RB_BLACK 巨集
• 以合法 C 程式書寫，注意排版風格