HackMD
2023q1 Homework3 (quiz3)
tags: linux2023
contributed by <Paintako>
測驗 1
考慮以下結構體, "利用 ABI 特性來「標示不用的節點」手段"
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
首先看到 __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:
#include <stdio.h>
typedef struct __node1{
int value;
char c;
} node1_t __attribute__((aligned(sizeof(long))));
int main() {
node1_t *ptr = malloc(sizeof(node1_t));
printf("%p\n",ptr);
node1_t *ptr1 = malloc(sizeof(node1_t));
printf("%p\n",ptr1);
node1_t *ptr2 = malloc(sizeof(node1_t));
printf("%p\n",ptr2);
return 0;
}
Node1 address: 0x7ffcbb1b7040
Node2 address: 0x7ffcbb1b7018
Node3 address: 0x7ffcbb1b7020
那 uintptr_t color 這段 color 到底代表的是？
只知道是一個指標，具體這個指標指的東西是指？
看到後續程式碼：
#define rb_parent(r) ((node_t *) (AAAA))
#define rb_color(r) ((color_t) (r)->color & 1)
可得知, 父點和顏色都存儲在 node_t 中，猜測父點和顏色都存在 color中
結合前面已知條件, node_t的記憶體位址皆對齊於8, 所以不論 color 指向的記憶體位址為何, 把後 3 bit 給清除掉, 那此地址就符合 node_t 的規範.
再結合記憶體對齊的規範, 如果此記憶體對齊 8 Byte, 那後 3 bit 皆不用不到, 那此 3 bit 可以用來表示此點是黑還是紅
結合以上兩者操作, 基本可以判定 color 指的就是：
- 父點指標
- 自己的顏色
故程式碼如下：
#define rb_parent(r) ((node_t *) (r)->color & ~7) // AAAA
#define rb_color(r) ((color_t) (r)->color & 1)
要設定一個 node_t 的顏色為黑色的話, 根據 typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t; 得知, 黑色＝1, 紅色=0
#define rb_set_red(r)
do {
r->color &= 0; // BBBB
} while (0)
#define rb_set_black(r)
do {
r->color ｜= 1; // CCCC
} while (0)
ABI:
- 二進制介面（Application Binary Interface），也就是程序二進制接口或應用程式介面。ABI 定義了在這個架構下不同程式和函數之間的二進制接口規範，例如函數的呼叫約定、參數傳遞方式、資料對齊方式等等。
while(0):
- while (0) 是一個空循環，其主要作用是在 Marco 定義中使用，以便在調用 Marco 時可以避免出現語法錯誤。
Ref: ChatGpt
關於插入紅黑樹, 非常直覺的, 比現在這個節點的值小就往左子樹找, 反之往右子樹找
如果往下走的過程中當前節點是 NULL, 等於找到要插入的位置
所以以下程式碼：
if (res < 0) {
if (!cur->left) {
cur->left = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
cur = curr->left; // DDDD
} else {
if (!cur->right) {
cur->right = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
cur = curr->right; // EEEE
}
以下程式碼, 會把一個 list 的 node_t 給傳入, 然後建立一個新的 map 給這個 list, 一個個的插入 node_t
插入後相當於建好一棵紅黑樹, 再從這棵樹中依照 cmap_next 中取得下一個點, 放入 list 中, 這樣子把整個 cmap iterate 完後, 等同於排序好整個 list.
void tree_sort(node_t **list)
{
node_t **record = list;
cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
while (*list) {
cmap_insert(map, *list, NULL);
list = &(*list)->next; // FFFF
}
node_t *node = cmap_first(map), *first = node;
for (; node; node = cmap_next(node)) {
*list = node;
list = &(*list)->next // GGGG
}
*list = NULL; // HHHH
*record = first;
free(map);
}
測驗 2
考慮以下程式碼：
#define AVL_NODE_ALIGNED __attribute__((aligned(sizeof(unsigned long))))
struct avl_node {
unsigned long parent_balance;
struct avl_node *left, *right;
} AVL_NODE_ALIGNED;
可得知, 這裡的對齊手法跟紅黑樹的對齊手法一致, 讓地址皆對齊於 8 byte
static inline struct avl_node *avl_parent(struct avl_node *node)
{
return (struct avl_node *) ((node->parent_balance)& ~7); // IIII
}
AVL tree 對於樹高有嚴格要求, 這裡使用一個 enum 來紀錄左右子樹高度差
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
當：
- 左右子樹一樣高： node_balance = 0
- 左樹比又右樹高： node_balance = 1
- 左樹比又右樹高： node_balance = 2
可用 2 個 bit 表示這棵樹的平衡狀態
故當要讀取此樹的高度差時, 只需要讀取最後兩個 bit 就可以了
static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
return (enum avl_node_balance)((node->parent_balance) & 3); // JJJJ
}
static void avl_set_parent:
此函式的用意在於給定父點的指標, 並且設定 current node 的 parent_balance, 已知 parent_balance 含：
- 父點指標
- 自身平衡狀態 （0,1,2)
參考以下兩位同學的作法
看到原本程式碼中的註解：
* struct avl_node - node of an avl tree
* @parent: pointer to the parent node in the tree
* @balance: balance of the node
* @parent_balance: combination of @parent and @balance (lowest two bits)
* @left: pointer to the left child in the tree
* @right: pointer to the right child in the tree
一開始有點疑惑, 但後來才想到這個函式的用意是設定新的父點, 那原本 node 內的後 3 bit 代表的是原本的平衡狀態, 故結合新的 parent pointer 以及原本的平衡狀態就可以更新 parent_balance 了
前面的問題釐清後, 要解答 static void avl_set_balance 就簡單很多, 只要把 parent_balance 後 3 bit 設定成0 剩餘的就是地址了, 再結合 balance 就可以把 parent_balance 給設定好.
static void avl_set_balance(struct avl_node *node,
enum avl_node_balance balance)
{
node->parent_balance = (node->parent_balance) & ~7 | 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為止, 期間如果有遇到不平衡狀態就調整.
當插入後, 先判斷插入的點是左是右（因為要區分父點平衡狀態）, 然後檢查父點的平衡狀態
- 當前節點是右邊的話, 則父點有三種情況
- 平衡
- 這樣就無須調整, 只須把父點的平衡設成右子樹比較高, 繼續往上檢查
- 左子樹比右子樹還高
- 原本父點是左子樹比較高, 但是右邊插入一個點後, 父點變平衡
- 右子樹比左子樹還高
- 這種情況下, 是不可能發生在 leaf 的, 考慮已經往上爬了一點距離的情況
- 如果 node 平衡狀況是：
- 平衡
- 右子樹比較高
- 程式碼中並未定義這種情形, 原因是因為上面平衡的情況下就會先進行旋轉, 來避免LL/RR 的情況
- 左子樹比較高
- 進行 RL 調整
avl_rotate_rightleft(node, parent, root)
- 平衡
- 平衡
釐清了以上觀念, 考慮插入節點是左子的情況：
- 當前節點是左邊的話, 則父點有三種情況
-
平衡
- 原本父點平衡, 插入左子後, 父點平衡變左子比右子高
-
左子樹比右子樹還高
- 同上面的結論, 這種情況不可能發生在 leaf 的, 考慮已經往上爬了一點距離的情況
- 如果 node 平衡狀況是：
- 平衡
- 為了避免出現 RR 的情況, 會提前進行旋轉
- 左子樹比較高
- 程式碼中並未定義這種情形, 原因是因為上面平衡的情況下就會先進行旋轉, 來避免LL/RR 的情況
- 右子樹比較高
- LR 調整
- 平衡
-
右子樹比左子樹還高
- 這種情況下, 因為原本右子比左子還高, 插入左子後, 讓父點剛好變平衡
-
程式碼：
void avl_insert_balance(struct avl_node *node, struct avl_root *root)
{
struct avl_node *parent;
/* go tree upwards and fix the nodes on the way */
while ((parent = avl_parent(node))) {
if (avl_is_right_child(node)) {
switch (avl_balance(parent)) {
default:
case AVL_RIGHT:
/* compensate double right balance by rotation
* and stop afterwards
*/
switch (avl_balance(node)) {
default:
case AVL_RIGHT:
case AVL_NEUTRAL:
avl_rotate_left(node, parent, root);
break;
case AVL_LEFT:
avl_rotate_rightleft(node, parent, root);
break;
}
parent = NULL;
break;
case AVL_NEUTRAL:
/* mark balance as right and continue upwards */
avl_set_balance(parent, AVL_RIGHT);
break;
case AVL_LEFT:
/* new right child + left leaning == balanced
* nothing to propagate upwards after that
*/
avl_set_balance(parent, AVL_NEUTRAL);
parent = NULL;
break;
}
} else {
switch (avl_balance(parent)) {
default:
case AVL_RIGHT:
/* new left child + right leaning == balanced
* nothing to propagate upwards after that
*/
avl_set_balance(parent, AVL_NEUTRAL);
parent = NULL;
break;
case AVL_NEUTRAL:
/* mark balance as left and continue upwards */
avl_set_balance(parent, AVL_LEFT);
break;
case AVL_LEFT:
/* compensate double left balance by rotation
* and stop afterwards
*/
switch (avl_balance(node)) {
default:
case AVL_LEFT:
case AVL_NEUTRAL:
avl_rotate_right(node, parent, root); // MMMM
break;
case AVL_RIGHT:
avl_rotate_leftright(node, parent, root); // NNNN
break;
}
parent = NULL;
break;
}
}
if (!parent)
break;
node = parent;
}
}
