# 2024q1 Homework4 (quiz3+4)
contributed by <[marvin0102](https://github.com/marvin0102/lab0-c)>
# 第一周測驗
## 測驗 1: 計算開平方根
假設我們要求 $x$ 的平方根，將 $x$ 轉為二進位後，可以將 $x$ 拆成 2 的冪相加:
$x = (000b_0b_1b_2...b_{n-1}b_n)^2$
其中 $000b_0b_1b_2...b_{n-1}b_n$ 為 bits pattern，而 $b_0$ 為最高位的 1 。
設 $a_0 = 000...b_n$ 、 $a_1 = 000...b_{n-1}0$ ... $a_1 = 000...b_{n-2}00$ ，因此可以將 $x$ 拆成：
$x = N^2 = (a_n + a_{n-1} + a_{n-2} + ... + a_0)^2$ , $a_m=2^m$ or $a_m=0$
使用矩陣乘法可得
\begin{bmatrix}
a_0a_0&a_1a_0&a_2a_0&...&a_na_0\\
a_0a_1&a_1a_1&a_2a_1&...&a_na_1\\
a_0a_2&a_1a_2&a_2a_2&...&a_na_2\\
... \\
a_0a_n&a_1a_n&a_2a_n&...&a_na_n
\end{bmatrix}
可以將這個矩陣拆為：
\begin{bmatrix}
a_0a_0&a_1a_0&a_2a_0&...&a_na_0\\
a_0a_1&&&&\\
a_0a_2&&&&\\
... \\
a_0a_n&&&&
\end{bmatrix}
\begin{bmatrix}
a_1a_1&a_1a_2&...&a_na_0\\
a_1a_1&&&\\
a_1a_2&&&\\
... \\
a_1a_n&&&
\end{bmatrix}
至最後一向
\begin{bmatrix}
a_na_n
\end{bmatrix}
將這些矩陣結合可以整理成以下公式
\begin{align}
N^2 &= a_n^2 + [2a_n+a{n-1}]a_{n-1} + [2(a_n+a_{n-1}) + a_{n-2}]a_{n-2} + ...+[2(\sum_{i=1}^na_i)+a_0]a_0\\
&= a_n^2 + [2P_n+a{n-1}]a_{n-1} + [2P_{n-1} + a_{n-2}]a_{n-2} + ...+[2P_{0}+a_0]a_0
\end{align}
其中 $P_m = a_n + a_{n-1} + ... + a_m$
而所求 $N = P_0$ 即為所求。
可以知道
$P_m= a_n + a_{n-1} + ... + a_m = (a_n + a_{n-1} + ... +a_{m+1})+ a_m = P_{m+1} + a_m$
經由測試 $P_m^2 \le N^2$ 判斷 $a_m=2^m$ or $a_m=0$
\begin{cases}
P_m = P_{m+1}+2^m, &\text{if $P_m^2 \le N^2$}\\
P_m = P_{m+1}, &\text{otherwise}
\end{cases}
$m = 0$ 時，$P_m$ 即為所求
可以透過上一輪的差值計算比較 $P_m^2 \le N^2$ ，設 $X_m = N^2-P_m^2$ 為 $P_m^2$ 、$N^2$ 的差值，可以由上一輪的差值 $X_{m+1}$ 減去 $Y_m$ 而得， $Y_m$ 的計算如下：
- $X_m = N^2-P_m^2 = X_{m+1}-Y_m$
- $Y_m = N^2-P_{m+1}^2 - (N^2-P_{m}^2) = P_{m}^2 - P_{m+1}^2 = 2P_{m+1}a_m + a_m^2$
因此，可以由上一輪的 $P_{m+1}$ 計算 $Y_m$
將 $Y_m$ 拆成 $c_m, d_m$，可得
$$Y_m =
\begin{cases}
c_m+d_m, &\text{if $a_m = 2^m$}\\
0, &\text{if $a_m = 0$}
\end{cases}
$$
其中 $c_m = P_{m+1}2^{m+1}$ 、 $d_m = (2^m)^2$
接著嘗試通過 $c_m$ 、 $d_m$ 推論下一輪的 $c_{m-1}$ 、 $d_{m-1}$:
- $$c_{m-1} = P_{m}2^{m} = (P_{m+1}+a_m)2^{m} = P_{m+1}2^{m} + a_m2^{m} =
\begin{cases}
c_m/2+d_m, &\text{if $a_m = 2^m$}\\
c_m/2, &\text{if $a_m = 0$}
\end{cases}
$$
- $d_{m-1} = (2^{m-1})^2 = \frac{d_{m}}{4}$
接下來就可以游上往下尋找 $a_n+a_{n-1}+...+a_0$，設從 $a_n$ 開始往下尋找：
- 因為 $n$ 為最大位數，因此 $P_{n+1} = 0$ ， $c_n = P_{n+1}2^{n+1} = 0$
- $d_n = (2^n)^2 = 4^n$
因為 $d_m$ 最小為 1 ，但是座位移操作最後必為 0 ，因此我們可以將 $d!=0$ 作為搜尋的判斷式。
從原始碼來解析：
```c
int i_sqrt(int x)
{
if (x <= 1) /* Assume x is always positive */
return x;
int z = 0;
for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= AAAA) {
int b = z + m;
z >>= BBBB;
if (x >= b)
x -= b, z += m;
}
return z;
}
```
因為無法計算虛數，因此須先將 $x$ 為負數的情況排除。
從 `1UL << ((31 - __builtin_clz(x)) & ~1UL)` 的作用為計算 $x$ 中最大 2 的冪為多少，也就是 $x = N^2 = (2^n+2^{n-1}+...+1)^2$ 中 $(2^n)^2$ ，因此我們可以知道 `m` 為 $b_n = 4^n$。
又由上面的公式，$d_{m-1} = (2^{m-1})^2 = \frac{d_{m}}{4}$ 可知，每一輪迴圈 `m` 須除 4 ，也就是右移 2 bits ，因此 `AAAA` 為 `2` 。
從 `return z;` 及 `z` 的起始值為 0 可推得， `z` 即為 $c_n$，且 `b` 為 $Y_n$，又因為 `z` 每次累加 $(2^n)^2$，因此需要每次迴圈除 2 ，使 `z` 變為 $P_n$，因此 `BBBB` 為 1。
### Linux 平方根運算應用案例：
在 [block/blk-wbt.c](https://elixir.bootlin.com/linux/v6.8/source/block/blk-wbt.c#L92) 中尋找到函式 `rwb_arm_timer` 使用 `int_sqrt` 的應用案例。
`int_sqrt` 被定義於 `lib/math/int_sqrt.c` 中，用於計算整數的平方根。
從註解可以了解
```c
* buffered writeback throttling. loosely based on CoDel. We can't drop
* packets for IO scheduling, so the logic is something like this:
* - Monitor latencies in a defined window of time.
* - If the minimum latency in the above window exceeds some target, increment
* scaling step and scale down queue depth by a factor of 2x. The monitoring
* window is then shrunk to 100 / sqrt(scaling step + 1).
```
如果上述 `window` 中的最小延遲超過某個目標值，則增加 `scaling step` ，並將佇列深度縮小 factor 的 2 倍。然後，`monitoring window` 縮小為 100 / sqrt(縮放步驟 + 1)。
具體程式碼：
```c
rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
int_sqrt((rqd->scale_step + 1) << 8));
```
### 實作更快的程式碼：
TODO
## 測驗 2: 計算除法
不使用 `/` 與 `%` 求一數字除以 10 的商跟餘數，相當於乘 $\frac{1}{10}$，但因為 10 不能以 2 的冪表示，因此需要找近似值 $\frac{a}{2^N}$ 使近似於 $\frac{1}{10}$ ，當 $2^N = 128$ 、 $a=13$ 時， $\frac{128}{13} \approx 9.84$ 與 10 很接近
```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);
```
因為 $13 = 8+4+1$ 因此我們可以透過 `(((tmp >> 3) + (tmp >> 1) + tmp) << 3)` 計算 $x*13$ ，因為右移時，會遺失最低位的 3 個位元，因此須利用 `+ d0 + d1 + d2`，紀錄並將其加回。
在我們得到 $x*13$ 後，在除以 128 即為我們所求的商，也就是 `>> 7`。
而餘數可以利用公式， $f - g \times Q= r$ 得到，`r = tmp - (((q << 2) + q) << 1);`。
完整程式碼為：
```c
#include <stdint.h>
#include <stdio.h>
int main()
{
for (int n = 0; n <= 19; n++) {
unsigned d2, d1, d0, q, r;
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
r = n - (((q << 2) + q) << 1);
printf("q: %d r: %d\n", q, r);
}
return 0;
}
```
可包裝為以下函式:
```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 >> CCCC);
*mod = in - ((q & ~0x7) + (*div << DDDD));
}
```
起初在觀察程式時，並沒有理解到兩程式之間的關聯性，在閱讀 [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 時，發現兩程式都是用近似值計算除以 10 的結果。
`x = (in | 1) - (in >> 2)` 計算 $x = in - \frac{1}{4}in = \frac{3}{4}in$ ，`q = (x >> 4) + x` 可以得 $q = \frac{x}{16} + x = \frac{3}{64}in + \frac{3}{4}in = \frac{51}{64}in \approx 0.79in$ 近似 0.8，有此可知 `*div = (q >> CCCC)` 須將 `q` 除以 8 才可得 `in/10` ，因此 `CCCC` 為 `3`。
```c
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
```
而四次位移是為了縮小誤差。
而餘數的計算同樣是將 `in - div*10` 而得，`(q & ~0x7)`保留除了最後三位元以外的其他位元，能等同於 `div<<3`，因為 `10 = 0b1010`，我們已經取得了`div<<3`，引此 `(*div << DDDD)` 為 `(*div << 1)`。
## 測驗 3:
當我們計算以 2 為第底數的對數時，我們可以計算一數的 leading set bit (從 most significant bit 開始計算）得到對數的近似值，例如：
```c
log(128) = log(0b1000 0000) = 7 // first set bit of 128 is 8
log(160) = log(0b1010 0000) = 7.321 // first set bit of 160 is 8
```
我們可以使用類似二元搜尋樹的方式加快 leading set bit 的搜索，方法如下：
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= AAAA) {
result += 16;
i >>= 16;
}
while (i >= BBBB) {
result += 8;
i >>= 8;
}
while (i >= CCCC) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
從第一個迴圈中`i >>= 16` 可知，此迴圈一次檢查 16 位元，如果 `i` 的 leading set bit 大於 16 位時，可以直接將 i 右移 16 位元，因此 `AAAA` 為 `0xffff`。
後面的迴圈同樣分別檢查 8 、 4 、 1 位元，因此 `BBBB` 、 `CCCC` 分別為 `0xff` 與 `0xf`。
可以利用 GNU extension `__builtin_clz` 來改寫使得程式更精簡：
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(DDDD));
}
```
:::info
從 [GCC online documentation](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的敘述：
Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined
可以知道 `__builtin_clz` 返回從 most significant bit （32 or 64) 開始計算，到碰的第一個 set bit 為止， 0 的數量。
其中，前綴的 `__builtin_` 代表此函式為 GCC 的 built-in 函式，
:::
因此，`ilog32(n)` 就是先使用 `__builtin_clz(n)` 計算 leading bits 的數量，再用 31 減掉，就可以得到從 most significant bit 數來第一個 set bit 的位置。
### Linux log2 的應用案例:
在 [include/linux/log2.h](https://elixir.bootlin.com/linux/v6.8/source/include/linux/log2.h#L156) 中定義了 log2 相關的聚集 `ilog`，其中包含了函式 `__ilog2_u64` 及 `__ilog2_u32` ，使`ilog2` 可以計算變數大小為 64 或 32 位元的對數值。
Linux/block 負責磁碟管理，其中[block/blk-zoned.c]([block/blk-zoned.c](https://elixir.bootlin.com/linux/v6.8/source/block/blk-zoned.c)) 使用 `ilog2` 計算 zone 的個數。
```c
unsigned int bdev_nr_zones(struct block_device *bdev)
{
sector_t zone_sectors = bdev_zone_sectors(bdev);
if (!bdev_is_zoned(bdev))
return 0;
return (bdev_nr_sectors(bdev) + zone_sectors - 1) >>
ilog2(zone_sectors);
}
```
## 測驗 ４:
從函式 `ewma_init` 中， `avg->factor` 為 `factor` 的對數，且函式 `ewma_read` 中，返回值為 `avg->internal >> avg->factor` 可以知道，再做 ewma 計算時，會以 $internal = factor*avg$ 做計算，當讀取數值時，須先將 $internal \div faxtor$ 才會得到正確的值。
在此前提下，分析函式 `ewma_add` ：
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << EEEE) - avg->internal) +
(val << FFFF)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
對照 EWMA 的數學定義：
$$
S_t=
\begin{cases}
Y_0 &t=0\\
\alpha Y_t+(1-\alpha) S_{t-1} &t>0
\end{cases}
$$
當加入第一筆資料時 $S_0 = Y_0$ 對應到 `avg->internal = (val << avg->factor)` 符合觀察。因此， $S_t = \alpha Y_t+(1-\alpha) S_{t-1}$ 在程式內乘上 $factor$ 後，
變為 $internal = weight*(factor*val) + (1 - weight)*internal$，但在函式中卻用了
`>> avg->weight` ，在觀察程式後發現，將 $\alpha = \frac{1}{2^{avg->weight}}$ 帶入公式計算可以發現，原本的公式變為 $S_t = \frac{1}{2^{avg->weight}} Y_t+(1-\frac{1}{2^{avg->weight}}) S_{t-1}$ ，
同乘 $2^{avg->weight}$ 後 $2^{avg->weight}S_t = Y_t+(2^{avg->weight}-1) S_{t-1}$ 與 `((avg->internal << avg->weight) - avg->internal) + (val << avg->factor)` 相符，因此最後計算的結果須除 $2^{avg->weight}$ 才會得到正確的結果。
### Linux EWMA 的相關程式碼與應用案例：
[include/linux/average.h](https://elixir.bootlin.com/linux/v6.8/source/include/linux/average.h#L28) 定義了 EWMA 的巨集 `DECLARE_EWMA` ，其中可以使用巨集引數 `name` 自行定義 EWMA 相關函式名稱，分別有 `ewma_##name##_init` 、 `ewma_##name##_read` 、 `ewma_##name##_add` 三個函式與結構體 `ewma_##name`。
`DECLARE_EWMA` 引數中 `_precision` 為定點數得 fraction bit 個數，而 EWMA 數學定義中的 $\alpha$ 則是以 `1/_weight_rcp` 的形式定義。
在 [drivers/net/wireless/ath/ath11k/core.h](https://elixir.bootlin.com/linux/v6.8/source/drivers/net/wireless/ath/ath11k/core.h#L478) 中，使用了 `DECLARE_EWMA(avg_rssi, 10, 8)` 定義了結構體 `ewma_avg_rssi` ，並且用 `ath11k_sta` 包裝。
在 [drivers/net/wireless/ath/ath11k/mac.c](https://elixir.bootlin.com/linux/v6.8/source/drivers/net/wireless/ath/ath11k/mac.c#L4986) 中函式 `ath11k_mac_station_add` 初始化，確切的作用仍在理解中。
## 測驗 5：
函式 `ceil_ilog2` 的作用為計算以2為底數的對數並且向上取整，實作方法與測驗 3 類似，通過二元搜尋的方式找出從 msb開始計算的 leading set bit 的位置。
```c
r = (x > 0xFFFF) << 4;
x >>= r;
```
`r` 為記錄leading set bit 的位置，當 `x > 0xFFFF` 成立時， `r` 為 $2^4$ ，代表 leading set bit 大於 16 位元，而 `x >>= r` 則是將 `x` 右移 16 位元再做後續的比較，若 `x > 0xFFFF` 不成立時，則 `r = 0` 且 `x` 無位移。
```c
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
```
在檢驗完 16 位元後，接續檢驗 8 位元，而 `r |= shift` 則是將兩次檢驗的位元結果相加。
再分別檢驗完 16 、 8 、 4 、 2 位元後，接著將這些檢驗結果與 `(x>1)` 相加即為從 msb開始計算的 leading set bit 的位置。
而因為結果需要向上取整，因此最後的結果需要加 1 ，如果 `x` 為 $2^n$ 則結果就會錯誤，因此在函示一開始需加上 `x--` 以避免此情況。
### 改進程式碼
在原本的函示中，因為 `x--` 在 `x` 為 0 時，會將 `x` 變為負數進而無法計算，因此只要將程式碼改為：
```diff
- x--;
+ x -= !(!x);
```
# 第二周測驗
## 測驗 1:
因為需要計算陣列 nums 中任兩個元素的 Hamming distance ，因此需要兩個迴圈將陣列 nums 中的元素相互比對並且透過 `__builtin_popcount(nums[i] ^ nums[j]` 計算 Hamming distance ，但因為兩層迴圈都是從頭開始走訪陣列 nums 因此會有重複計算的問題，例如：當 i=0 時， `nums[i] ^ nums[j]` 會計算 j=1,2,...,n， 而 `i=1` 時，會計算 j=0,2,...,n ， 其中 `nums[0] ^ nums[1]` `nums[1] ^ nums[0]`重複計算了，因此當計算完成時， `total` 為兩倍的 Hamming distance ，在最後還須除 2 ，也就是 `total>>1`。
觀察每個 bit 的 Hamming distance ：
| n'th bit | 4 | 3 | 2 | 1 | 0 |
| ---- | ---- | ---- | ---- | ---- | ---- |
| input 7 | 0 | 0 | 1 | 1 | 1 |
| input 5 | 0 | 0 | 1 | 0 | 1 |
| input 10 | 0 | 1 | 0 | 1 | 0 |
| input 17 | 1 | 0 | 0 | 0 | 1 |
每個 bit 的 Hamming distance 為陣列中取兩個元素，滿足兩元素中該 bit 為 [0,1] 或 [1,0] 的組合數量。例如：
1. 第 0 個 bit 觀察 :
只有 10 的第 0 個 bit 為 `0` -> Hamming Distance = (1)*(numsize - 1)
2. 第 1 個 bit 觀察 :
有兩個 bit 為 `0` -> Hamming Distance = (2)*(numsize - 2)
因此，我們可以統整所有元素中每個 bit 為 1 的數量，並計算每個 bit 的 Hamming distance ，最後再加總起來就是 total Hamming distance。
程式碼如下：
```c
int totalHammingDistance(int* nums, int numsSize)
{
int total = 0;
for (int i = 0;i < 32;i++)
int count = 0;
for (int j = 0; j < numsSize;j++)
if(nums[j] & (1<<i)){
count++;
}
total += count*(numsSize-count);
return total;
}
```
## 測驗 2:
觀察陣列 `move_masks` ，因為井字遊戲最多只有 9 個可能的選擇，因此可以知道 `move_masks` 中每一個元素代表井字遊戲的其中一個位置。將九宮格內的直線、橫線與斜線個數相加剛好為 8 條連線，又每條連線為九宮格中的三格連線所形成。
觀察元素內的數值可以發現，相比於直接將座標進行編號， `move_masks` 的做法是將九宮格中的連線做編號，每 4 個 bits 紀錄一條連線，則 `uint32_t` 恰好可以記錄 8 條連線。
在紀錄著一條連線的 4 bits 中，每位元代表連線中的其中一個格子，當遊戲的其中一方勝利時，代表 8 條連線中，有至少一條連線的三個格子被遊戲中的一方填滿，此時紀錄著這條連線的 4 bits 為 `0111` 即 `0x7`。
```c
static inline uint32_t is_win(uint32_t player_board)
{
return (player_board + 0x11111111) & 0x88888888;
}
```
這時只要將記錄著遊戲狀態的變數 `player_board` 加 `0x11111111` 即每 4 bits 加 1 ，並觀察是否有其中 4 bits 進位為 `1000` 即 `0x8` 就可知道是否達成勝利條件。
井字遊戲中，每一個格在都會影響到不只一條連線，因此 `move_masks` 的每個元素 set bit 個數至少為三以上，且每 4 bits 只會有一個 set bit。
觀察遊戲的整體流程， `boards` 負責記錄玩家的遊戲狀態，`available_moves` 代表目前可以下棋的位置，一開始皆為 9 個，而決定下棋位置方式為，透過 `xorshift32()` 隨機生成一數字，除 `n_moves` 並使用函式 `fastmod` 取餘數，最後取得的數值 `i` ， `available_moves[i]` 即為下棋的位置。
因此我們知道函式 `fastmod` 中的 `mod7` 為取 7 的餘數， [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 中，函式 `rems7` 透過 $8^k \equiv 1 (mod 7)$ 快速計算 $mod 7$ 具體程式如下：
```c
int remu7(int n) {
int r;
static char table[75] = {5,6, 0,1,2,3,4,5,6,
0,1,2,3,4,5,6, 0,1,2,3,4,5,6, 0,1,2,3,4,5,6,
0,1,2,3,4,5,6, 0,1,2,3,4,5,6, 0,1,2,3,4,5,6,
0,1,2,3,4,5,6, 0,1,2,3,4,5,6, 0,1,2,3,4,5,6, 0,1,2};
r = (n >> 15) + (n & 0x7FFF); // FFFF0000 to 17FFE.
r = (r >> 9) + (r & 0x001FF); // FFFFFF80 to 2BD.
r = (r>> 6)+(r&0x0003F); //-2to72(decimal).
return table[r];
}
```
因為 $2^{15} \equiv 1 (mod 7)$ ，所以我們可以將 n 右移 15 位元並且跟 n 從 lsb 開始計算 15 位元相加，其值取餘數後，與 n 取餘數的值相同。後面的 `(r >> 9)` 、 `(r>> 6)` 也是相同的原理。
[Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf) 中提另一種取餘數的方法，利用 $n \mod 7 = \lfloor\frac{8}{7}n\rfloor \mod 8$ 的方法取餘數：
```c
int remu7(unsigned n) {
n = (0x24924924*n + (n >> 1) + (n >> 4)) >> 29;
return n & ((int)(n - 7) >> 31);
}
```
透過將 $n*\lfloor\frac{2^{32}}{7}\rfloor$ 之後再往右移 29 位元，即可在省去高為元的同時，取得我們想要的答案。
而井字遊戲中的函式 `mod7` 則是結合兩者：
1. 使用 `x = (x >> 15) + (x & UINT32_C(0x7FFF));`縮小為數的計算。
2. 因為誤差的關係，採用 $n*\lceil\frac{2^{32}}{7}\rceil$ 也就是 `((x * UINT32_C(0x24924925)) >> 29)` 取得餘數。
## 測驗 3:
`treeint.c` 為一個測試程式，分別測試 BST 的插入、搜尋與刪除所花的時間，實作方法為使用結構體 `treeint_ops` 以函式指標的方式將 `treeint_xt.[ch]` 所提供的函式製作程 function hook ，並透過 `ops` 進行函式呼叫。其中，`xtree.[ch]` 負責處理 xtree 的平衡、新增與刪除，由資料型別 `xt_node` 作為樹的節點相連接。而 `treeint_xt.[ch]` 將 `xtree.c` 中的函式包裝成符合程式所需的資料型別 ，也就是定義了 entry 的資料型別 `treeint_st` 與比較函式 `treeint_xt_cmp` 。
`treeint_xt.[ch]` 提供的 5 個函式，分別透過呼叫 `xtree.[ch]` 中對應的函式完成對 BST 的操作。而 `xtree.[ch]` 提供了以下函式：
- `struct xt_tree *xt_create(cmp_t *cmp,
struct xt_node *(*create_node)(void *key),
void (*destroy_node)(struct xt_node *n))`:
作用為初始化 xtree ，並且定義了搜尋、建構或移除節點時所需的函式。
- `void xt_destroy(struct xt_tree *tree)`:
呼叫函式 `__xt_destroy` 使用遞迴得方式移除整棵樹。
- `int xt_insert(struct xt_tree *tree, void *key)`:
透過函式 `__xt_find` 尋找 `key` 在 xtree 中插入的位置，並呼叫 `__xt_insert` 將新節點插入 xtree 中。
- `int xt_remove(struct xt_tree *tree, void *key)`:
與 `xt_insert` 相似，透過函式 `__xt_find` 尋找 `key` 在 xtree 中的位置，呼叫 `__xt_remove` 將節點從 xtree 中移除。
- `struct xt_node *xt_find(struct xt_tree *tree, void *key)`:
透過呼叫 `__xt_find2` 以遞迴的方式尋找 `key` 在 xtree 中的位置並回傳節點指標。
xtree 與 AVL tree 、 Red Black tree 相似，三者皆為[自平衡樹](https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)， xtree 的平衡機制是利用 `hint` 來評估是否需要做 rotate， `xt_node` 的 `hint` 的計算方式是，其左右節點 `hint` 最大值 +1 並且只有在被呼叫到 `xt_update` 時才會被更新。
其中：
- `xt_update`:
透過呼叫 `xt_balance` 判斷左右子節點 `hint` 的差值是否超過 1 ，如果是則 rotate 進行平衡，接著檢查 `hint` 在平衡後是否改變，如果是則往上對親節點進行平衡。
- `xt_rotate_right`:
將節點向右旋轉以平衡 xtree
```graphviz
digraph structs {
node[shape=circle];
node0 [label= "p"];
node1 [label= "n", color = red];
node2 [label= "l"];
node3 [label= "r"];
node4 [label= "ll"];
node5 [label= "lr"];
node0 -> node1;
node1 -> node2;
node1 -> node3;
node2 -> node4;
node2 -> node5;
node[shape=circle];
node7 [label= "p"];
node11 [label= "ll"];
node8 [label= "n", color = red];
node9 [label= "l"];
node12 [label= "lr"];
node10 [label= "r"];
node7 -> node9;
node8 -> node12;
node9 -> node8;
node9 -> node11;
node8 -> node10;
}
```
- `xt_rotate_left`:
將節點向左旋轉以平衡 xtree
```graphviz
digraph structs {
node[shape=circle];
node0 [label= "p"];
node1 [label= "n", color = red];
node2 [label= "l"];
node3 [label= "r"];
node4 [label= "rl"];
node5 [label= "rr"];
node0 -> node1;
node1 -> node2;
node1 -> node3;
node3 -> node4;
node3 -> node5;
node[shape=circle];
node7 [label= "p"];
node9 [label= "l"];
node8 [label= "n", color = red];
node11 [label= "rl"];
node12 [label= "rr"];
node10 [label= "r"];
node7 -> node10;
node10 -> node12;
node8 -> node11;
node8 -> node9;
node10 -> node8;
}
```
### 改進程式：
TODO
Sign in with Wallet
Connect another wallet