# linux2023: yeeecheng

## 測驗α-1
## 測驗α-2

由於```BBBB```小題答錯，因此重新思考這個部分。

1. 欲刪除 val=4 的節點，須從其右子樹找到最小值節點 val=5，刪除前的高度如圖所示。 

struct st_node *least = st_first(st_right(del));

![](https://hackmd.io/_uploads/B16nCGqnh.jpg)

2. val=5 的節點會取代 val=4 的節點，並將 val=5 的右節點 val=7 遞補上來。

/* 對應的程式碼 */
st_replace_right(del, least);

![](https://hackmd.io/_uploads/ByFNSzj22.jpg)

3. 最後，需要將右子樹的高度更新，更新位置從 val = 7 的節點開始，但程式碼提供的變數無法找到最下面的節點，因為 ``` st_replace_right(del, least)```已經將least的右節點改為 val = 10 的節點，因此若使用```st_update(root, st_right(least))```找到會是 val=10 的節點，並非 val=7 的節點。因此應該將程式碼變更為以下：

oid st_remove(struct st_node **root, struct st_node *del)
{
if (st_right(del)) {
struct st_node *least = st_first(st_right(del)), *least_parent = st_parent(least);
if (del == *root)
*root = least;

st_replace_right(del,least); //AAAA

/* BBBB */
if (st_left(least_parent)) && least_parent != del)
st_update(root, st_left(least_parent));
else
st_update(root, least_parent);
return;
}

if (st_left(del)) {
struct st_node *most = st_last(st_left(del)), *least_parent = st_parent(least);;
if (del == *root)
*root = most;

st_replace_left(del, most);//CCCC
/* DDDD */
if (st_right(least_parent)) && least_parent != del)
st_update(root, st_right(least_parent));
else
st_update(root, least_parent);
return;
}
// ...
}

如此以來才能夠實現從更新高度的功能。




## 測驗α-3

## 測驗β-1

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) { /* power of two? */
return (sz + mask << 1) & ~mask;
}
return (((sz + mask) / alignment) * alignment);
}

根據記憶體對齊的規則，sz 需為 aligment 的倍數。因此，若 sz 不能被 aligment 整除的話，則需要將 sz padding 至下一個能被 aligment 整除的數。而此 padding 值的範圍是 ```1 ~ aligment-1```，因此在函式 align_up 中，定義mask(即 aligment-1) 作為 padding 的值，並得到```((((sz + mask) / alignment) * alignment)```，照理來說，使用此式子可以處理任意的 sz  與 aligment，但函式中多判斷了```(alignment & mask) == 0```，用意是想利用 power of 2 在bitwise 的特性，即 aligment 為2的指數時， ```aligment-1``` 的二進位會是0111...的形式，則```& ~mask```便能夠實現如同先除 aligment 再乘 aligment 的運算，兩者的差異在於運算的執行效率，因為使用```*```,``` / ```編譯成組合語言所需的行數比使用```&```,```|```多，因此在計算完```sz+mask```後，使用```& ~mask```能夠更快得到結果。

## 測驗β-2
在``` linux/include/linux/kernel.h ```找到以下 macro

/* @a is a power of 2 value */
#define ALIGN(x, a) __ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a) __ALIGN_KERNEL((x) - ((a) - 1), (a))
#define __ALIGN_MASK(x, mask) __ALIGN_KERNEL_MASK((x), (mask))
#define PTR_ALIGN(p, a) ((typeof(p))ALIGN((unsigned long)(p), (a)))
#define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0)

其中的 ```__ALGIN_KERNEL```與```__ALGIN_KERNEL_MASK```在``` linux/include/uapi/linux/kernel.h```中

#define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))

macro ```__ALIGN_KERNEL_MASK(x, mask)```的定義與題目中 ```MMMM```的方法相同，而```__ALIGN_KERNEL(x, a)```則對應到 ```mask = aligement -1```

## 測驗γ-1

## 測驗γ-2

## 測驗γ-3