# [2022q1](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 18 週測驗題
###### tags: `linux2022`

:::info
目的: 檢驗學員對 Linux 核心資料結構和 **[bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)** 的認知
:::

作答表單:
* ==[測驗 `1`](https://docs.google.com/forms/d/e/1FAIpQLScaCSiaHMOcUuLWgzIilP8yR6h5DX-NCatoQ5VggcpXvHMgvA/viewform)== (Linux 核心設計)

### 測驗 `1`

[rbtree-minimal](https://gist.github.com/jserv/3e87c957b577dc46c91d51f94159666c) 是改寫自 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 程式書寫，注意排版風格