or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
2023q1 Homework3 (quiz3)
tags:
linux2023
contributed by <Paintako>
測驗 1
考慮以下結構體, "利用 ABI 特性來「標示不用的節點」手段"
首先看到
__attribute__((aligned(sizeof(long))))
, 透過__attribute__((aligned(sizeof(long))))
讓編譯器知道 struct rb_node 會對齊 sizeof(long)指的是,
struct __node
的起始位址會是 8 Byte 倍數的位置反過來說, 如果某個位址對齊了 8 byte (1000), 會有3個 bit 是永遠用不到的.
以下實驗證明了使用
__attribute__((aligned(sizeof(long))))
的結構體的地址永遠對齊 8 Bytes:那
uintptr_t color
這段 color 到底代表的是?只知道是一個指標,具體這個指標指的東西是指?
看到後續程式碼:
可得知, 父點和顏色都存儲在
node_t
中,猜測父點和顏色都存在color
中結合前面已知條件,
node_t
的記憶體位址皆對齊於8, 所以不論 color 指向的記憶體位址為何, 把後 3 bit 給清除掉, 那此地址就符合node_t
的規範.再結合記憶體對齊的規範, 如果此記憶體對齊 8 Byte, 那後 3 bit 皆不用不到, 那此 3 bit 可以用來表示此點是黑還是紅
結合以上兩者操作, 基本可以判定 color 指的就是:
故程式碼如下:
要設定一個
node_t
的顏色為黑色的話, 根據typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;
得知, 黑色=1, 紅色=0ABI:
while(0):
Ref: ChatGpt
關於插入紅黑樹, 非常直覺的, 比現在這個節點的值小就往左子樹找, 反之往右子樹找
如果往下走的過程中當前節點是 NULL, 等於找到要插入的位置
所以以下程式碼:
以下程式碼, 會把一個 list 的 node_t 給傳入, 然後建立一個新的 map 給這個 list, 一個個的插入 node_t
插入後相當於建好一棵紅黑樹, 再從這棵樹中依照
cmap_next
中取得下一個點, 放入 list 中, 這樣子把整個 cmap iterate 完後, 等同於排序好整個 list.測驗 2
考慮以下程式碼:
可得知, 這裡的對齊手法跟紅黑樹的對齊手法一致, 讓地址皆對齊於 8 byte
AVL tree 對於樹高有嚴格要求, 這裡使用一個 enum 來紀錄左右子樹高度差
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
當:
可用 2 個 bit 表示這棵樹的平衡狀態
故當要讀取此樹的高度差時, 只需要讀取最後兩個 bit 就可以了
static void avl_set_parent
:此函式的用意在於給定父點的指標, 並且設定 current node 的
parent_balance
, 已知parent_balance
含:參考以下兩位同學的作法
看到原本程式碼中的註解:
一開始有點疑惑, 但後來才想到這個函式的用意是設定新的父點, 那原本 node 內的後 3 bit 代表的是原本的平衡狀態, 故結合新的 parent pointer 以及原本的平衡狀態就可以更新
parent_balance
了前面的問題釐清後, 要解答
static void avl_set_balance
就簡單很多, 只要把parent_balance
後 3 bit 設定成0 剩餘的就是地址了, 再結合 balance 就可以把parent_balance
給設定好.接著, 看到
void avl_insert_balance(struct avl_node *node, struct avl_root *root)
他的描述是: 沿著樹往"上"走, 然後沿路 rebalance, 如果路上會遇到:
RL/RR/LR/LL 這四種情況就會進行調整.
在
static inline void avl_insert
中會呼叫到此函式插入前, 先呼叫
avl_link_node
函式, 作用是將給定的 parent 連結到此點上面, 連結後相當於這棵樹多了一個 leaf, 再從這個葉子往上走到 root為止, 期間如果有遇到不平衡狀態就調整.當插入後, 先判斷插入的點是左是右(因為要區分父點平衡狀態), 然後檢查父點的平衡狀態
avl_rotate_rightleft(node, parent, root)
釐清了以上觀念, 考慮插入節點是左子的情況:
平衡
左子樹比右子樹還高
右子樹比左子樹還高
程式碼: