# 2024 Homework4 (quiz3+4)
## 第三周測驗
[2024q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗 `1` : Using bitwise operations to compute square root
先看原程式碼
```c
#include <math.h>
int i_sqrt(int N)
{
int msb = (int) log2(N);
int a = 1 << msb;
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
編譯方式
```
$ gcc -o i_sqrt i_sqrt.c -lm
```
> 因為呼叫 log2，所以需要連結 libm (math library)，即 -lm 選項
假設 N = $36_{10}$ =$100100_2$，`msb = 5` => a = $100000_2$
接著進入迴圈中
| 迴圈次數 | a | result |是否進入迴圈|
| -------- | -------- | -------- |- |
| 1 | $100000_2$ | 0 |y |
| 2 | $10000_2$ | 0 |y |
| 3 | $1000_2$ | 0 |y |
| 4 | $100_2$ | $100_2$ |y |
| 5 | $10_2$ | $110_2$ |y |
| 6 | $1_2$ | 0 |n |
在此 `bitwise` 操作中， `(result + a)` 的平方逐一比較 `N` 值，當值較小時就疊加當前的值，即 `result += a` ，直到為 N 的開方根值。
> 此題一開始用十進位去看比較容易明白， `a >>= 1` 看作 `a / 2`。
編譯方式：`$ gcc -o i_sqrt i_sqrt.c -lm`
版本二使用右移操作直到 n 值為 0 ，藉此計算 `msb`
```clike
int msb = 0;
int n = N;
while (n > 1) {
n >>= 1;
msb++;
}
```
版本三使用 [Digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 方法進行開方根。將平方數拆成 2 的冪相加
令 $x=N^2=(a_n+a_{n-1}+...+a_0)^2$ ，其中 N 即為所求的開方根
$P_m=a_n+a_{n-1}+...+a_m$
$P_0=a_n+a_{n-1}+...+a_0=N$ 即為所求
推論出:
$P_m=P_{m+1}+a_m$
後續將求出所有 $a_m=2^m$ or $0$，從 $m = n$ 一直到 $m = 0$，而求得 $a_m$ 只須比較$P_m^2 \le N^2$，有兩種情況：
\begin{cases}
P_m=P_{m+1}+2^m \ \ ;\ P_m^2 \le N^2\\
P_m=P_{m+1}\ \ \ \ \ \ \ \ \ \ \ \ ;\ otherwise
\end{cases}
由於每輪逐一比較的運算成本過高，提出了另個想法
將$N^2-P_m^2$ 的值表示位$X_m$
\begin{cases}
X_m=N^2-P_m^2--(1) \\
X_{m+1}=N^2-P_{m+1}^2--(2)
\end{cases}
將(1)式減(2)式可得 $X_m-X_{m+1}=-P_m^2+P_{m+1}^2--(3)$
其中 $P_m$ 平方為
$P_m^2=P_{m+1}^2+2a_mP_{m+1}+a_m^2=P_{m+1}^2+(2P_{m+1}+a_m)a_m$
令 $Y_m= P_m^2-P_{m+1}^2=(2P_{m+1}+a_m)a_m$
最後將 $Y_m$ 代回到(3)式可得：
$X_m=X_{m+1}-Y_m$
將 $Y_m$ 拆解 $c_m,d_m$
$c_m=P_{m+1}2^{m+1}$
$d_m=(2^m)^2$
得：
\begin{cases}
Y_m=c_m+d_m\ ;if\ a_m=2^m\\
Y_m=0\ \ \ \ \ \ \ \ \ \ \ \ \ \ ;if\ a_m=0
\end{cases}
藉由位元運算從$c_m,d_m$推出下一輪
$c_{m-1}=P_m2^m=(P_{m+1}+a_m)2^m=P_{m+1}2^m+a_m2^m$
\begin{cases}
c_m/2+d_m\ \ if\ a_m=2^m\\
c_m/2\ \ \ \ \ \ \ \ \ \ \ \ if\ a_m=0\\
\end{cases}
$d_{m-1}=d_m/4$
**Linux 核心原始程式碼** [linux/block/blk-wbt.c](https://github.com/torvalds/linux/blob/39cd87c4eb2b893354f3b850f916353f2658ae6f/block/blk-wbt.c#L9)
```c
static void rwb_arm_timer(struct rq_wb *rwb)
{
struct rq_depth *rqd = &rwb->rq_depth;
if (rqd->scale_step > 0) {
/*
* We should speed this up, using some variant of a fast
* integer inverse square root calculation. Since we only do
* this for every window expiration, it's not a huge deal,
* though.
*/
rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
int_sqrt((rqd->scale_step + 1) << 8));
} else {
/*
* For step < 0, we don't want to increase/decrease the
* window size.
*/
rwb->cur_win_nsec = rwb->win_nsec;
}
blk_stat_activate_nsecs(rwb->cb, rwb->cur_win_nsec);
}
```
尚未完成
### 測驗 `2` : Using bitwise operations to perform mod 10 and div 10
參考《[Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf)》，採用 bitwise operation 來實作除法
$n\ \dfrac{a}{2^N}$ 此題選用 a=13 N=7 => $n\ \dfrac{13}{2^7}$ ，其中 $\dfrac{13}{2^7}$ 為 $0.10156$ 。
完整程式碼
```c
unsigned d2, d1, d0, q, r;
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) >> 7;
r = tmp - (((q << 2) + q) << 1);
```
將 $tmp\times \dfrac{13}{2^7}$ 改寫成 $tmp\times 13 \div 16 \div 8$，其中 $tmp\times \dfrac{13}{8}\times 8=13tmp$ 可從下方程式碼得到
```c
(((tmp >> 3) + (tmp >> 1) + tmp) << 3)
```
由於 `tmp` 右移三位會遺失原本最低三位的 bit ，因此將分別用 `d0` 、 `d1` 、 `d2` 來儲存原先的 bit ，再將遺失的 bit 補回來，最後在除以128，即為 $\dfrac{13}{128} tmp$，得到一個近似 $tmp\div 10$ 的結果 ( `q` )。
```c
q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) >> 7;
```
:::info
上述程式碼中不太理解為何補足遺失的最低三位 bit 是加上 `+ d0 + d1 + d2` ，在我實作中發現就算缺少這段程式碼也不會影響其結果，其大致的觀念我能理解是為了增加其精度，但又為何不直接加上 `+ d2` 就好。
:::
下方程式碼根據餘數定理：$f-g\times Q=r$，可以得到 $r$ (餘數)
- $f$ : 被除式
- $g$ : 除式
- $Q$ : 商
- $r$ : 餘數
```c
r = tmp - (((q << 2) + q) << 1);
```
其中`(((q << 2) + q) << 1)` 等於 $(q\times 4+q)\times2=q\times 10$
將程式碼包裝成
```c
#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
uint32_t q = (x >> 4) + x;
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
*div = (q >> 3);
*mod = in - ((q & ~0x7) + (*div << 1));
}
```
`uint32_t x = (in | 1) - (in >> 2)` 得到 $\dfrac{3}{4}in$
`uint32_t q = (x >> 4) + x;` 得到 $q=\dfrac{3}{4}in\div 16+\dfrac{3}{4}in=\dfrac{51}{64}in$ ，其中 $\dfrac{51}{64}in$約為 $0.796875in$ 近似 $\dfrac{8}{10}$
再經由 bitwise 操作使 0.796875 更接近 0.8
```c
q = (q >> 8) + x; // q = 0.799987793
q = (q >> 8) + x; // q = 0.799999952
q = (q >> 8) + x; // q = 0.799999998
q = (q >> 8) + x; // q = 0.8
```
最後 `*div = (q >> 3);` 即為 $*div=\dfrac{8}{10}in\div 8=\dfrac{1}{10}in$
`((q & ~0x7) + (*div << 1));` 為 $\dfrac{8}{10}in+\dfrac{1}{10}in\times 2=\dfrac{in}{10}\times10$，其中 $\dfrac{in}{10}$ 為商。
在由餘式定理：$f-g\times Q=r$ 求得 `*mod` 值為何
**練習撰寫不依賴任何除法指令的 % 9 (modulo 9) 和 % 5 (modulo 5) 程式碼**
尚未進行
### 測驗 `3` : Using bitwise operations to calculate the logarithm base 2
用 `ilog2` 計算以 2 為底的對數，且其輸入和輸出皆為整數。
稍微改寫一下原程式碼方便識讀，舉例 $i = 4_{10} = 100_2$
| while ( i >= 2 ) | 原 i | 後 i | log |
| -------- | -------- | -------- | - |
| 第 1 次迴圈 | 100 | 10 | 1 |
| 第 2 次迴圈 | 10 | 1 | 2 |
輸出 `log = 2`
```diff
int ilog2(int i)
{
- int log = -1;
+ int log = 0;
- while (i){
+ while (i >= 2) {
i >>= 1;
log++;
}
return log;
}
```
改寫後的程式碼，將 `i` 用一定數量的位元去進行判斷，有效提升數字較大時的計算速度，其原因為原程式碼每個位元逐一去判斷，反覆進行多次的迴圈，改後後判斷分成 4 個階段，若 `i` 大於 $2^{16}、2^8、2^4、2^1$則直接進行位元操作。
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= 65536) {
result += 16;
i >>= 16;
}
while (i >= 256) {
result += 8;
i >>= 8;
}
while (i >= 16) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
**在 Linux 核心原始程式碼找出 log2 的相關程式碼 (或類似的形式)，並解說應用案例**
看到 log2 為底的形式就想到 `clz` 、 `ffs` 、 `fls` 等相關的操作都有類似的手法。
在 [linux/arch/arc/include/asm/bitops.h](https://github.com/torvalds/linux/blob/026e680b0a08a62b1d948e5a8ca78700bfac0e6e/arch/arc/include/asm/bitops.h#L28) 中找到 fls 的實作，其作用為返回最高有效 bit 位(由最低位往左數)，當判斷式為 0 進行位移操作，其手法相似 log2 ，不同於位元操作向左進行。
該順序不同於 `log2` ， `constant_fls` 從 1 起始，當沒有有效位返回 0 。
```c
static inline int constant_fls(unsigned int x)
{
int r = 32;
if (!x)
return 0;
if (!(x & 0xffff0000u)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xff000000u)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xf0000000u)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xc0000000u)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x80000000u))
r -= 1;
return r;
}
```
### 測驗 `4` : Using bitwise to calculate EWMA
> 參考 [stevendd543](https://hackmd.io/@stevennnnnn/linux2024-homework4#%E7%AC%AC%E5%9B%9B%E9%A1%8C)、[2024q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-4)
**Exponentially Weighted Moving Average**
賦予資料指數衰減的權重，主要目的使越舊的資料權重越低，反之越新的資料對整體平均值的影響越大，以下為此統計手法的公式：
$$
S_t =
\begin{cases}
Y_0 \quad\quad &t=0
\\
\alpha Y_t + (1-\alpha) \cdot S_{t-1} \quad\quad &t>0
\end{cases}
$$
- $\alpha$ 表示歷史資料加權降低的程度，介在 0 ～ 1 之間，越高的 $\alpha$ 會使歷史資料減少的越快
- $Y_t$表示時間 t 時的資料點
- $S_{t}$ 表示時間 t 時的 EWMA
```c
void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
if (!is_power_of_2(weight) || !is_power_of_2(factor))
assert(0 && "weight and factor have to be a power of two!");
avg->weight = ilog2(weight);
avg->factor = ilog2(factor);
avg->internal = 0;
}
```
`@internal` : 看作 $t$ 當前的位置
`@factor` : 縮放因子，必須是 2 的冪次
`@weight` : 資料的權重，在這 $\alpha=2^{avg->weight}$ 透過右移來達到$\alpha=2^{-(avg->weight)}=\dfrac{1}{2^{avg->weight}}$，必須是 2 的冪次
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << weight) - avg->internal) +
(val << avg->factor)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
一開始 $t=0$ ，因此 $S_t=Y_0$ 對應到 `avg->internal = (val << avg->factor);`
，接著 `avg->internal = (((avg->internal << avg->weight) - avg->internal) + (val << avg->factor)) >> avg->weight` 的理解較為困難，看起來與題意的公式不同，在 [stevendd543](https://hackmd.io/@stevennnnnn/linux2024-homework4#%E7%AC%AC%E5%9B%9B%E9%A1%8C) 筆記中的舉例有非常清楚解釋：
令 $\alpha\alpha^{-1}=1$，將公式改寫成
$\alpha^{-1}S_t=\alpha^{-1}(\alpha Y_t+(1-\alpha)S_{t-1})$
$\ \ \ \ \ \ \ \ \ \ =Y_t+(\alpha^{-1}-1)S_{t-1}$
其中 $(\alpha^{-1}-1)S_{t-1}$ 等效於 `((avg->internal << avg->weight) - avg->internal)`，$Y_t$ 等效於 `(val << avg->factor)` ，最後將整個公式 `>> avg->weight` 即為 $\alpha^{-1}S_t\times \alpha=S_t$ (當時 $t$ 的EWMA)。
```c
unsigned long ewma_read(const struct ewma *avg)
{
return avg->internal >> avg->factor;
}
```
將計算的平均值除以縮放因子而得到真正的平均值。
**在 Linux 核心原始程式碼找出 EWMA 的相關程式碼 (或類似的形式)，至少該涵蓋無線網路裝置驅動程式**
### 測驗 `5` : Test 3 Extension
延伸測驗 3，已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算 [log2] ，也就是 [ceil](https://man7.org/linux/man-pages/man3/ceil.3.html) 和 log2 的組合並轉型為整數。
`x--` 目的為避免 `x` 為 2 的冪，接著使用類似測驗 `3` 的作法，在指定的位元寬度中比較，若條件成立就會進行位元操作，下方程式碼寫的更加複雜因此實際帶入數值去進一步解釋。
```c
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;
}
```
case `1`
x = 0000 0000 0000 0000 0000 1000 0000 0000
```
x-- = 0000 0000 0000 0000 0000 0111 1111 1111
r = (x > 0xFFFF) << 4 = 0 << 4 = 0
x = x >> r = 0000 0000 0000 0000 0000 0111 1111 1111
shift = (x > 0xFF) << 3 = 1 << 3 = 8
x >>= shift = 0000 0000 0000 0000 0000 0000 0000 0111
r |= shift = 8
shift = (x > 0xF) << 2 = 0 << 2 = 0
x >>= shift = 0000 0000 0000 0000 0000 0000 0000 0111
r |= shift = 8
shift = (x > 0x3) << 1 = 1 << 1 = 2
x >>= shift = 0000 0000 0000 0000 0000 0000 0000 0001
return (r | shift | x > 1) + 1 = return (11)
```
- 透過 `shift = (x > 0xFF) << 3` 決定 `x` 要右移的大小
- `r |= shift` 等效 `r += shift` ，用來記錄由第 0 bit 往左數到 msb 的有效位
- 最後結果把先前 `x--` 的值加回來
**改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless**
```diff
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
+ bool mark = x;
+ x -= !!x
- x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
- return (r | shift | x > 1) + 1;
+ return (r | shift | x > 1) + mark;
}
```
當 `x = 0` 時 `ceil_ilog2` 應要回傳 0 ，因此設立一個 `mark` 來紀錄最後是否 +1 。
**Linux 核心原始程式碼**
尚未完成
## 第四周測驗
[2024q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-1)
### 測驗 `1` : Total Hamming Distance
閱讀 [population count](https://en.wikichip.org/wiki/population_count#google_vignette) 了解計算二進位表示式中有多少個位元為 `1` 、 了解 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_weight) 所代表的意思。
更進階的操作參照[測驗1](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-1)，大致內容為每4個位元為一個單位，求出其中的 set bits 個數，32位元中總共有 8 組，將每組算得的 set bits 個數加總在一起，裡面的推導過程需詳讀就能得知最後為何 `v >> 24` 即為 popcount 。
考題針對 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/description/)
```c
int totalHammingDistance(int* nums, int numsSize)
{
int total = 0;;
for (int i = 0;i < numsSize;i++)
for (int j = 0; j < numsSize;j++)
total += __builtin_popcount(nums[i] ^ nums[j]);
return total >> 1;
}
```
Leetcode 範例描述到
```
Input: nums = [4,14,2]
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
```
在考題程式碼中為兩兩成對的去計算 popcount ，因此會出現HammingDistance(4, 14)與HammingDistance(14, 4)這種情況，因此最後回傳要除以 2 (即 `return total >> 1`)。
**不依賴 popcount，嘗試以上述歸納的規則，針對 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/description/) 撰寫出更高效的程式碼**
參考 solution 中的解答
```c
int totalHammingDistance(int* nums, int numsSize){
int ans = 0;
for (int i = 0; i < 32; ++i) {
int c = 0;
for (int j = 0; j < numsSize; ++j) {
c += (nums[j] >> i) & 1;
}
ans += c * (numsSize - c);
}
return ans;
}
```
使用 bitwise 逐一比較二進制中每個位元是否為 1 ，其判斷式 `(nums[j] >> i) & 1`
每當比較完一位元，便計算其 HammingDistance 的值 ( `ans += c * (numsSize - c)` )
| n 'th bit | 3 | 2 | 1 | 0 |
| -------- | -------- | -------- | - | - |
| input 4 | 0 | 1 | 0 | 0 |
| input 14 |1 | 1 | 1 | 0 |
| input 2 | 0 | 0 | 1 | 0 |
1. 第 0 個 bit 觀察:
全部都是 0 => Hamming Distance = 0
2. 第 1 個 bit 觀察:
1 有兩個 => Hamming Distance = (2)* (numsSize - 2)
3. 第 3 個 bit 觀察:
1 有一個 => Hamming Distance = (1)* (numsSize - 1)
### 測驗`2` : Remainder by Summing digits
了解[ [ 離散數學 ] 同餘（Mod）](https://ithelp.ithome.com.tw/articles/10205727)的性質及定義
詳讀 [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 中提及 Remainder by Summing digits
以除 3 為例， $1\equiv 1\pmod 3$ , $2\equiv -1\pmod 3$
$2^k\equiv$
\begin{cases}
1\equiv 1\pmod 3, & \text{if $k$ is even} \\
2\equiv -1\pmod 3, & \text{if $k$ is odd}
\end{cases}
n 以二進制表示成 $n=b_{n-1}b_{n-2}...b_1b_0$
\begin{aligned}
n &= {\sum\limits_{i=0}^{n-1}} b_i2^{i} 由以上推論出\ n \equiv {\sum\limits_{i=0}^{n-1}} b_i(-1)^i\pmod 3
\end{aligned}
將上式結合 popcount 寫成程式
```c
n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)
```
> 0x55 = 0b01010101
> 0xAA = 0b10101010
再由定理
$popcount(x \And \overline{m}) - popcount(x \And m) = popcount(x \bigoplus m) - popcount(m)$
> 定理證明在 [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 裡有提到，頁碼：P13
化簡成
```c
n = popcount(n ^ 0xAAAAAAAA) - 16
```
```c
int mod3(unsigned n)
{
n = popcount(n ^ 0xAAAAAAAA) + 23; //n = popcount(n ^ 0xAAAAAAAA) - 16 + 39;
n = popcount(n ^ 0x2A) - 3;
return n + ((n >> 31) & 3); //避免 n 為負數值
}
```
為了避免 `n` 變成負數，因此加上一個足夠大的 3 的倍數，範例中為加 39 ，在第二輪應用使 `n` 介於 -3~2 之間而非 -3~3 之間。
`return n + ((n >> 31) & 3)`主要用作避免 n 為負數值，若為 n 為正則不受影響。
```
舉例 若 n = -1
-1 -> 0b1111 1111 1111 1111 1111 1111 1111 1111 # n
0b11 # (n >> 31) & 3
0b10 # n + ((n >> 31) & 3)
```
lookup table
```c
int mod3(unsigned n)
{
static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 };
n = popcount(n ^ 0xAAAAAAAA);
return table[n];
}
```
使用查表的方式去尋找對應的餘數。
**tictactoe.c**
**將上述手法應用於第三次作業中，追求更有效的賽局判定機制。**
### 測驗 `3` : XTree
[AVL Tree](https://josephjsf2.github.io/data/structure/and/algorithm/2019/06/22/avl-tree.html) 是一種Binary Search Tree (BST) 實作方法，透過高度計算及 balance factor 判斷是否需要旋轉來平衡。
[red-black tree](https://clu.gitbook.io/data-structure-note/1.4.3-red-black-tree) 遵循以下規則來達成平衡：
1. 節點只有黑或紅
2. 根節點必為黑
3. 若節點是紅色的，則其子節點必為黑色，反之不必為真(黑色節點的下個節點可為黑或紅)
4. 所有從該節點走到其子樹下的末端節點 (leaf) 的上之黑色節點數量必定
此題 XTree 的平衡機制與 AVL tree 相似，利用 hint 來評估是否需要做 rotate，然而 xt_node 的 hint 的計算方式是，其左右節點 hint 最大值 +1 並且只有在被呼叫到 xt_update 時才會被更新。
```c
#define xt_root(r) (r->root)
#define xt_left(n) (n->left)
#define xt_right(n) (n->right)
#define xt_rparent(n) (xt_right(n)->parent)
#define xt_lparent(n) (xt_left(n)->parent)
#define xt_parent(n) (n->parent)
```
**`xt_create`** : 初始化 `XTree`
**`xt_destroy`**
利用遞迴
```c
if (xt_root(tree))
__xt_destroy(tree, xt_root(tree));
```
將樹裡的每個節點釋放，在 `__xt_destroy()` 中
```c
if (xt_left(n))
__xt_destroy(tree, xt_left(n));
if (xt_right(n))
__xt_destroy(tree, xt_right(n));
```
若 `xt_left` (左子樹)或 `xt_right` (右子樹)存在則繼續往下走直到盡頭 `tree->destroy_node(n)` 來釋放。
**`xt_first`**
用遞迴的方式尋找最左邊的節點
```c
if (!xt_left(n))
return n;
return xt_first(xt_left(n));
```
**`xt_last`**
與 `xt_first` 一樣，但變成尋找最右變的節點
**`xt_rotate_left`**
```c
struct xt_node *l = xt_left(n), *p = xt_parent(n);
xt_parent(l) = xt_parent(n);
xt_left(n) = xt_right(l);
xt_parent(n) = l;
xt_right(l) = n;
```
這段程式碼為下圖操作
```graphviz
digraph Tree {
graph[ordering=out]
p -> n
n -> l
n -> r
l -> A
l -> B
label=before
}
```
```graphviz
digraph Tree {
graph[ordering=out]
p -> l
l -> A
l -> n
n -> B
n -> r
label=after
}
```
```c
if (p && xt_left(p) == n)
xt_left(p) = l;
else if (p)
xt_right(p) = l;
```
假設 p 的右子樹不存在
```graphviz
digraph Tree {
graph[ordering=out]
null [label="" shape=plaintext]
null1 [label="" shape=plaintext]
p -> l
p -> null
l -> null1
l -> n
label=before
}
```
```graphviz
digraph Tree {
graph[ordering=out]
null [label="" shape=plaintext]
null1 [label="" shape=plaintext]
p -> null
p -> l
l -> null1
l -> n
label=after
}
```
```c
if (xt_left(n))
xt_lparent(n) = n;
```
重新定義 n 節點的 parent
**`xt_rotate_right`**
操作手法與 `xt_rotate_left` 相似，因此僅用圖示
```graphviz
digraph Tree {
graph[ordering=out]
p -> n
n -> l
n -> r
r -> A
r -> B
label=before
}
```
```graphviz
digraph Tree {
graph[ordering=out]
p -> r
r -> n
n -> l
n -> A
r -> B
label=after
}
```
**`xt_balance`**
與 AVL Tree 中 Balance Factor of T, BF(T) 的平衡判斷相似，這裡的 hint 為左子樹高 - 右子樹高
**`xt_max_hint`**
選擇左子樹與右子樹的 hint 的最大值 `+1` 即為節點 n 的 hint 值(更新 hint)
**`xt_update`**
若樹不平衡 `xt_balance < -1` 進行 `xt_rotate_right` , `xt_balance > 1` 進行 `xt_rotate_left`
**`xt_insert`**
插入新節點在樹中
**`xt_remove`**
當移除一節點 `del` 時，將該右子樹的最左來填補，即 `least` 來替換掉原本的 `del` ，並檢查是否平衡 `xt_update`，反之則用左子樹的最右節點來點補，若被刪除的節點為 `leaf` 將不用進行交換。
```c
static void __xt_remove(struct xt_node **root, struct xt_node *del)
{
if (xt_right(del)) {
struct xt_node *least = xt_first(xt_right(del));
if (del == *root)
*root = least;
xt_replace_right(del, least);
xt_update(root, xt_right(least));
return;
}
if (xt_left(del)) {
struct xt_node *most = xt_last(xt_left(del));
if (del == *root)
*root = most;
xt_replace_left(del, most);
xt_update(root, xt_left(most));
return;
}
if (del == *root) {
*root = 0;
return;
}
/* empty node */
struct xt_node *parent = xt_parent(del);
if (xt_left(parent) == del)
xt_left(parent) = 0;
else
xt_right(parent) = 0;
xt_update(root, parent);
}
```
Sign in with Wallet
Connect another wallet