# 2023q1 Homework3 (quiz3)
###### tags: `linux2023`
contributed by <Paintako>
## 測驗 1
考慮以下結構體, "利用 ABI 特性來「標示不用的節點」手段"
```c
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:
```c
#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;
}
```
```shell
Node1 address: 0x7ffcbb1b7040
Node2 address: 0x7ffcbb1b7018
Node3 address: 0x7ffcbb1b7020
```
那 `uintptr_t color` 這段 color 到底代表的是？
只知道是一個指標，具體這個指標指的東西是指？
看到後續程式碼：
```c
#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 指的就是：
1. 父點指標
2. 自己的顏色
故程式碼如下：
```c
#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
```c
#define rb_set_red(r)
do {
r->color &= 0; // BBBB
} while (0)
#define rb_set_black(r)
do {
r->color ｜= 1; // CCCC
} while (0)
```
:::warning
ABI:
* 二進制介面（Application Binary Interface），也就是程序二進制接口或應用程式介面。ABI 定義了在這個架構下不同程式和函數之間的二進制接口規範，例如函數的呼叫約定、參數傳遞方式、資料對齊方式等等。
while(0):
* while (0) 是一個空循環，其主要作用是在 Marco 定義中使用，以便在調用 Marco 時可以避免出現語法錯誤。
Ref: ChatGpt
:::
關於插入紅黑樹, 非常直覺的, 比現在這個節點的值小就往左子樹找, 反之往右子樹找
如果往下走的過程中當前節點是 NULL, 等於找到要插入的位置
所以以下程式碼：
```c
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.
```c
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
考慮以下程式碼：
```c
#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
```c
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, };`
當：
1. 左右子樹一樣高： node_balance = 0
2. 左樹比又右樹高： node_balance = 1
3. 左樹比又右樹高： node_balance = 2
可用 2 個 bit 表示這棵樹的平衡狀態
故當要讀取此樹的高度差時, 只需要讀取最後兩個 bit 就可以了
```c
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` 含：
1. 父點指標
2. 自身平衡狀態 （0,1,2)
參考以下兩位同學的作法
* avl_balance(node) [Ref](https://hackmd.io/@paul90317/linux2023q1-quiz3#%E6%B8%AC%E9%A9%97-2)
* node->parent_balance & 3 [Ref](https://hackmd.io/@Toneary/2023q1-Homework3-quiz3)
看到原本程式碼中的註解：
```c
* 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` 給設定好.
```c
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 調整
* 右子樹比左子樹還高
* 
* 這種情況下, 因為原本右子比左子還高, 插入左子後, 讓父點剛好變平衡
程式碼：
```c
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;
}
}
```
Sign in with Wallet
Connect another wallet