# 2023q1 Homework3 (quiz3)
contributed by < `LiChiiiii`>
>測驗題目：[quiz3](https://hackmd.io/@sysprog/linux2023-quiz3)
## 測驗一
#### 紅黑樹
研讀 [treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401) ，考慮一個 Tree sort 的實作，搭配 Red–black tree 作為排序所需的自我平衡樹。
定義一個列舉型別 `color_t` ，包含兩個值，分別為 `CMAP_RED` 與 `CMAP_BLACK`，代表紅色節點和黑色節點。
```c
typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;
```
定義一個結構 `node_t` ，其中 `color` 代表節點顏色， `left` 和 `right` 分別代表紅黑樹的左節點和右節點，`next` 代表在原始陣列中下一個節點， `value` 代表節點的值。
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
為了節省記憶體空間，這裡把父節點的位址存在 `uintptr_t color` 的最高位中。在 64 位元的系統中，考慮到 alignment，記憶體以 8 bytes 為一個單位進行管理，也就是說 `node_t` 的位址的最後 3 個 bits 一定為 0 ，因此只要對給定的引數 `(r)` 清除後面 3 個 bits 就可以得到父節點的位址，並且在引數 `(r)` 最後一個 bit 存放顏色信息， `(r)->color & 1` 取出最後一個 bit 。
```c
#define rb_parent(r) ((node_t *) ((r)->color & ~7))
#define rb_color(r) ((color_t) (r)->color & 1)
```
在設定顏色時，以 bitwise 操作，若節點是紅色則設定最後一個bit 為 0 ，反之。
```c
#define rb_set_red(r) do { (r)->color &= ~1; } while (0)
#define rb_set_black(r) do { (r)->color |= 1; } while (0)
```
`cmap_insert()` 是在紅黑樹中插入節點的功能，若比較結果 `res` 小於零代表往左邊走，否則往右邊走，直到走訪到的節點為 NULL，或迴圈結束，即插入節點。
```c
static bool cmap_insert(cmap_t obj, node_t *node, void *value)
{
/* Just insert the node in as the new head. */
/* Calibrate the tree to properly assign pointers.*/
...
/* Traverse the tree until we hit the end or find a side that is NULL */
for (node_t *cur = obj->head;;) {
int res = obj->comparator(&node->value, &cur->value);
if (!res) /* If the key matches something else, don't insert */
assert(0 && "not support repetitive value");
if (res < 0) {
if (!cur->left) {
cur->left = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
cur = cur->left;
}
else {
if (!cur->right) {
cur->right = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
cur = cur->right;
}
}
cmap_calibrate(obj);
return true;
}
```
`tree_sort()` 會建立一個 map 配置 key 和 element 足夠的空間，接著在 while 迴圈將 list 中的每個節點一個一個插入 map 中。定義 `*node` 為 map 中擁有最小值的節點，透過 for 迴圈，從最左子開始在紅黑樹找到下一個節點（`cmap_next(node)` ），由小到大放入 list 中，完成 sort 功能。
```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 ;
}
node_t *node = cmap_first(map), *first = node;
for (; node; node = cmap_next(node)) {
*list = node;
list = &(*list) -> next ;
}
*list = NULL;
*record = first;
free(map);
}
```
## 測驗二
#### AVL 樹
定義一個結構 `avl_node` ，其中 `parent_balance` 最低位 2 bits 紀錄 node 的平衡狀態，高位紀錄父節點的位址，`left` 和 `right` 分別代表 AVL 樹的左節點和右節點。
```c
struct avl_node {
unsigned long parent_balance;
struct avl_node *left, *right;
} AVL_NODE_ALIGNED;
```
因此想取出得到父節點就將 `parent_balance` 的高位取出，因為是 64 位元的系統，所以 `avl_node` 的位址的最後 3 個 bits 一定為 0，因此只要把最後 3 bits 設為 0 ，即可得到父節點的位址。
```c
static inline struct avl_node *avl_parent(struct avl_node *node)
{
return (struct avl_node *) ((node)->parent_balance & ~7);
}
```
定義一個列舉型別 `avl_node_balance` ，包含三個值，分別為 `AVL_NEUTRAL` 、 `AVL_LEFT` 和 `AVL_RIGHT` 。
- `AVL_NEUTRAL` : 左子樹和右子樹的深度一樣
- `AVL_LEFT` ： 左子樹的深度 - 右子樹的深度 = 1
- `AVL_RIGHT` ： 右子樹的深度 - 左子樹的深度 = 1
```c
enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };
```
因為 `parent_balance` 最低位 2 bits 存放節點的平衡狀態，利用 `& 3` 將最低位 2 bits 取出。
```c
static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
return (enum avl_node_balance)((node)->parent_balance & 3);
}
```
透過 `node->parent_balance & 3` 保留原本的 balance 資訊，利用 or 設定 parent。
透過 `node->parent_balance & ~7` 保留原本的 parent 資訊，利用 or 設定 balance。
```c
static void avl_set_parent(struct avl_node *node, struct avl_node *parent)
{
node->parent_balance = (unsigned long) parent | (node->parent_balance & 3);
}
static void avl_set_balance(struct avl_node *node,
enum avl_node_balance balance)
{
node->parent_balance = (node->parent_balance & ~7) | balance;
}
```
插入新節點後需要確認 tree 是否平衡。換句話說，會先檢查插入節點是左子還是右子，再檢查 parent 的 balance 狀態在插入新節點後是否平衡。
如果插入的新節點是左子，就去檢查 parent 的 balancd 狀態，會出現三種可能的狀態：`AVL_RIGHT` 、 `AVL_NEUTRAL` 、 `AVL_LEFT`，當parent 是 `AVL_LEFT` 的狀態時表示左子樹高度比右子樹高 1 ，接著檢查插入節點的 balance ，如果是 `AVL_LEFT` 或 `AVL_NEUTRAL`，那麼就進行右旋操作（第42行），如果是 `AVL_RIGHT` ，那麼就進行左右旋操作，先將右子樹向左旋轉，再將原節點向右旋轉（第45行）。
```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
*/
...
case AVL_NEUTRAL:
/* mark balance as right and continue upwards */
...
case AVL_LEFT:
/* new right child + left leaning == balanced
* nothing to propagate upwards after that
*/
...
} else {
switch (avl_balance(parent)) {
default:
case AVL_RIGHT:
/* new left child + right leaning == balanced
* nothing to propagate upwards after that
*/
...
case AVL_NEUTRAL:
/* mark balance as left and continue upwards */
...
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);
break;
case AVL_RIGHT:
avl_rotate_leftright(node, parent, root);
break;
}
parent = NULL;
break;
}
}
if (!parent)
break;
node = parent;
}
}
```
## 測驗三
這段程式碼是一個長度為 256 的表格，被稱為「對數表」（log table），用於計算二進制數字的位數（也就是 `log_table_256[x]` = $log_{2}x$ ）。例如， log_table_256[6] 的值為 2 ，代表著二進位表示法中的 `00000110` ，第一個 1 位元出現在位置 2 。
```c
static const char log_table_256[256] = {
#define _(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3,
3, 3, 3, 3, 3, _(4), _(5), _(5), _(6), _(6), _(6),
_(6), _(7), _(7), _(7), _(7), _(7), _(7), _(7), _(7),
#undef _
};
```
在程式碼中，它首先檢查最高的 32 位元，如果它們不是 0 ，則將它們向右移動 32 位元，並繼續檢查下一個 16 位元和 8 位元。找到的最高位元的對數與某些固定的值相加，以計算整個 64 位元的對數。因為表格中的值是以 2 為底的對數，所以它們的值域在 0 到 7 之間，可以直接用來計算每個 8 位元組的對數，而不需要進行實際的對數運算。
```c
/* ASSUME x >= 1
* returns smallest integer b such that 2^b = 1 << b is >= x
*/
uint64_t log2_64(uint64_t v)
{
unsigned r;
uint64_t t, tt, ttt;
ttt = v >> 32;
if (ttt) {
tt = ttt >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = 56 + log_table_256[t];
} else {
r = 48 + log_table_256[tt];
}
} else {
t = ttt >> 8;
if (t) {
r = 40 + log_table_256[t];
} else {
r = 32 + log_table_256[ttt];
}
}
} else {
tt = v >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = 24 + log_table_256[t];
} else {
r = 16 + log_table_256[tt];
}
} else {
t = v >> 8;
if (t) {
r = 8 + log_table_256[t];
} else {
r = 0 + log_table_256[v];
}
}
}
return r;
}
```
這段程式碼是用來將一個 64 位元整數 x 根據 N_BITS 和 N_BUCKETS 的設定，將其分配到對應的桶(bucket)中。其中，mask111 和 mask011 分別是用來產生全為 1 的二進位數字，mask111的長度為 N_BITS + 1， mask011 的長度為 N_BITS 。
```c
unsigned int bucket_number(uint64_t x)
{
uint64_t mask111 = (1 << (N_BITS + 1)) - 1;
uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */
unsigned char leq = ((x & mask111) < N_BUCKETS);
/* leq (less or equal) is 0 or 1. */
return (leq * (x & mask111)) +
((1 - leq) * ((x >> (N_BITS + 1)) & mask011));
}
```
## 測驗四
### 運作原理
考慮 `ceil_log2` 可針對給定無號 32 位元數值 x，找出 $⌈log2(x)⌉$，舉例來說：
* `ceil_log2(7)` = 3
* `ceil_log2(8)` = 3
* `ceil_log2(9)` = 4
主要概念是找到最高位元的 `1` 是在 32 bits 中的哪一個 bit，因為可以根據最高位元的 `1` 來觀察這個數值是介於哪兩個 2 的次方數之間。
程式碼運作方式如下：
1. 變數 `r` 初始值為 0 ，目的是儲存計算後的對數結果。變數 `shift` 初始值為 0 ，目的是用來儲存計算每次 `x` 的偏移量。
2. 將 `x` 先減 1 ，確保四捨五入可以到最近的 2 的次方數
3. 檢查 `x` 是否大於 `0xFFFF` ，若是的話， `r` 會被設為 `16` ，否和 `r` = 0 ，並將 `x` 右移 `16` bits；
檢查 `x` 是否大於 `0xFFF` ，若是的話， `shift` 會被設為 `8`，否則 `shift` = 0 ，並將 `x` 右移 `8` bits，接著 `r` 和 `shift` 做結合，以此類推檢查 `0xF` 和 `0x3`。
4. 最後 `r` 會和最後剩下的偏移量 `shift`（可能是 0、1 或 2 個位元）及其移位後的結果結合，得出最終的對數結果。該結果最後會加 `1`，以取得向上取整後的對數值。
從 `0xFFFF` 開始檢查，是因為當輸入值大於 `0xFFFF` 時，右移 16 位元可以將輸入值的高 16 位元右移到低 16 位元，這樣可以把輸入值的位數減少一半，從而加快計算速度。接著，再根據輸入值的大小，從 `0xFF`、`0xF`、`0x3` 分別開始檢查，進行對應的右移操作，最後計算出以 2 為底數的對數的位數。
```c
int ceil_log2(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;
}
```
Trace `ceil_log2(0x0FFFFFFF)` 的執行過程。
```c
shift = 0
r = 0
x = 0x0FFFFFFF
x = 0x0FFFFFFE
x > 0xFFFF
r = 0x10
x = 0x00000FFF
x > 0xFF
shift = 0x08
x = 0x0000000F
r = 0x18
x > 0xF
shift = 0x04
x = 0
r = 0x1C
x < 0x3
shift = 0
return (0x1C | 0 | 0 ) + 1 = 0x1D //以 2 為底數的對數的位數
```
Sign in with Wallet
Connect another wallet