# 2023q1 Homework3 (quiz3)
contributed by <`kart81604`>
## 測驗 `1`
:::success
AAAA = `r->color & ~7`
BBBB = `r->color &= ~1`
CCCC = `r->color |= 1`
DDDD = `cur = cur->left`
EEEE = `cur = cur->right`
FFFF = `&(*list)->next`
GGGG = `&(*list)->next` or `&node->next` 但後者答在老師的 google 表單不算正確
HHHH = `*list = NULL`
:::
### 研讀 [`tree_sort`](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
樹中節點的型態上，要注意的是其中的 `color` ，如果只是代表顏色的話，大可只用 `bool` 來代表，為何還要用 `uintptr` 來儲存呢？
透過 include/linux/rbtree_types.h 中的
```c
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
```
原來這邊指的 `color` 並不是指該節點的顏色，而是它的 parent 的位子跟自身的顏色，一個值之所以可以同時給出兩個資料就是因為其中的 `__attribute__((aligned(sizeof(long))))`
64 位元的環境， `long` 的 size 為 8 bytes 代表每個節點的記憶體位址都會是 8 的倍數，用二位元方式儲存，該位址的後三個 bits 皆為 0 ，既然每個位址後面三個 bits 都為 0 ，那麼不用白不用，就順便拿來儲存顏色的資料，如果最右端的 bit 為 0 ，則代表該點為紅色，反之，則為黑色。
```c
#define rb_set_red(r) \
do { \
(color_t) (r)->color &= 0; \
} while (0)
#define rb_set_black(r) \
do { \
(color_t) (r)->color |= 1; \
} while (0)
```
上面兩個函數皆是對 `r` 的顏色作改變。
了解以上的結構及參數意義後，就可以知道如何取得該 node 的 parent 的記憶體位址，只要把該 node 的 `color` 後面三個 bits 改成 0 ，就可以了。
```c
#define rb_parent(r) ((node_t *) ((r)->color & ~7))
```
以下函式表示對紅黑樹插入新點 `node`。
`obj` 為紀錄整體紅黑樹的資訊，因插入新的點，所以 `obj->size` 要加 1 。
如果這紅黑樹為空，則新插入的點就為這紅黑樹的 root ，則該點改黑，再來對 `obj` 進行調整。
不為空就要找出新插入的點應該要在的位子，找到後插入進去，在對整體紅黑樹進行調整。
```c
static bool cmap_insert(cmap_t obj, node_t *node, void *value)
{
cmap_create_node(node);
obj->size++;
if (!obj->head) {
/* Just insert the node in as the new head. */
obj->head = node;
rb_set_black(obj->head);
/* Calibrate the tree to properly assign pointers. */
cmap_calibrate(obj);
return true;
}
/* 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` ，先把 `list` 中每個點插入到紅黑樹裡，在利用 `camp_first` 找出紅黑樹中最小的點，將該點記在 `first` 中，再利用 `camp_next(node)` 找出整個紅黑樹中，僅大於 node 的點，再放進 `first` 的下一個，重複此作法， `first` 就會是一個排序後的序列了。
```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);
}
```
## 測驗 `2`
:::success
IIII = `node->parent_balance & ~7`
JJJJ = `node->parent_balance & 3`
KKKK = `node->parent_balance & 3`
LLLL = `node->parent_balance & ~7`
MMMM = `avl_rotate_right`
NNNN = `avl_rotate_leftright`
:::
要取得該點的 parent ，方法與第一題的紅黑樹類似，該 node 因為有透過 `__attribute__((aligned(sizeof(unsigned long))))` 來對齊，因此後面三個 bits 都是 0 (這邊指的是 64 位元環境的情況下，如果是 32 位元，則是後面二個 bits 皆為 0 ，以下皆已 64 位元環境下去考慮)，因此拿來儲存 AVL tree 平衡的資訊。
```c
static inline struct avl_node *avl_parent(struct avl_node *node)
{
return (struct avl_node *) (node->parent_balance & ~7);
}
```
要取得該點的 balance 資訊，要拿到該點的 `parent_balance` 的末 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);
}
```
要改變 parent 只要保留原本的 balance 資訊，另外一邊，要改變 balance 資訊，要保留原本的 parent 資訊。
```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;
}
```
插入新點後，要調整樹來使得符合 AVL 的定義，從下例第 7 行開始，如果插入的點為 parent 的右子節點，要判斷 parent 的 balance 狀態，如果 parent 的 balance 為 `AVL_RIGHT` 則勢必要進行 `avl_rotate_left` 或是 `avl_rotate_rightleft` ，那要判斷要用哪個，就要看他右子節點的 balance ，如果為 `AVL_RIGHT` 或是 `AVL_NEUTRAL` 則進行前者，如果為 `AVL_LEFT` 則進行後者，做完之後就調整完畢。如果 parent 的 balance 狀態為 `NETURAL` ，則新加入右子節點會造成右偏重，則將 parent 的 balance 改成 `AVL_RIGHT`，然後進到下一個迴圈。如果 parent 為 `AVL_LEFT` 新加入點後會變成 `AVL_NEUTRAL` ，且整棵樹也調整完畢。
```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);
break;
case AVL_RIGHT:
avl_rotate_leftright(node, parent, root);
break;
}
parent = NULL;
break;
}
}
if (!parent)
break;
node = parent;
}
}
```
## 測驗 `3`
:::success
AAAA = `56`
BBBB = `48`
CCCC = `40`
DDDD = `32`
EEEE = `24`
FFFF = `16`
GGGG = `8`
HHHH = `0`
IIII = `mask111`
JJJJ = `mask011`
:::
以下的定義可以得知 `log_table_256[x]` 的值為 $\left \lfloor{log_2 x}\right \rfloor$ 。
```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 _
};
```
利用上述的陣列來取得 64 位元的 input `v` ，來計算 $\left \lfloor{log_2 v}\right \rfloor$ ，因為 `log_table_256` 只能處理到 8 位元的 input ，因此要透過 bitwise 的操作，將數據縮減到 8 個，運作原理示範於程式碼下。
```c
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;
}
```
```
1234 5678 9012 3456 ...... 1234 <-共 64 bits 表示 position
0110 0110 0011 0101 ...... 0101 <-input v
//右移 32 bits
3456 7890 1234 5678 ...... 1234 <-共32 bits 從第33位元表示，因前32位元皆為0
0110 0110 0011 0101 ...... 0010 <-原本 v 的 32 bits 的 MSB
//再右移 16 bits
9012 3456 7890 1234 ...... 1234 <-共16個bits 從第49位元表示，因前48位元皆為0
0110 0110 0011 0101 ...... 0001 <-原本 v 的 32 bits 的 MSB
//再右移 8 bits
7890 1234 <-共8個 bits 從第57位元表示，因前56位元皆為0
0110 0110 <-原本 v 的 8 bits 的 MSB
//將後面的 8 bits 值透過 log_table_256 去判斷此以二為底的log值再加上56
//得出 6+56 = 62
```
`lsfr` 的運作為判斷 input `*up` ，該值的第 1 個、第 4 個、第 31 個、第 56 個 bit 作 exclusive or ，再將原本的 input 右移一位，再將 MSB 換成 `new_bit` 。
```c
static void lfsr(uint64_t *up)
{
uint64_t new_bit =
((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u;
/* don't have to map '+1' in polynomial */
*up = ((*up) >> 1) | (new_bit << 63);
/* shift *up by 1 to RIGHT and insert new_bit at "empty" position */
}
```
`bucket_number` 是用來計算當前 `x` 中 `N_BITS` bits LSB 是否小於 `N_BUCKET`，小於就回傳，大於的話就將 `x` 右移 `N_BITS + 1` 個 bits，再與 `mask011` 做 `&` ，來確保回傳的數字是小於 `N_BUCKETS` 。
透過這個函式，可以得到總是比 `N_BUCKETS` 的值。
```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 & IIII)) +
((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ));
/* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
* '... & mask011' guarantees that the result is less or equal N_BUCKETS.
*/
}
```
`fill_bucket` 為將現有的 bucket 隨機填入數字，可以觀察到迴圈的次數為 `iterations` ，每一次都會挑一個 bucket 將它裡面的值增加一，在透過 `lfsr` 來更改 x 的數字，盡量讓下一輪挑到的 bucket 會趨近於亂數。
```c
void fill_buckets(unsigned int *buckets, unsigned int iterations)
{
uint64_t x = 0x98765421b16b00b5;
unsigned char lfsr_iter = (N_BITS << 1);
for (uint64_t i = 0; i < iterations; i++) {
unsigned int tmp_bucket = bucket_number(x);
*(buckets + tmp_bucket) = *(buckets + tmp_bucket) + 1;
// 'turn handle' on LFSR lfsr_iteration-times!
unsigned char ell = 0;
while (ell < lfsr_iter) {
lfsr(&x);
ell++;
}
}
}
```
以下為 main function ，buckets 的個數有 20 個， iteraions 的次數為 $2^{20}$ 次， 9 - 15 行為配置記憶體，且也把這些 buckets 中的值歸零， `fill_buckets` 函式就是可以視為將 $2^{20}$ 分配給這 20 buckets 。
`evaluate_buckets` 為將每個 bucket 的值印出來，就不多作介紹。
```c=
int main()
{
int num_of_buckets = 120; /* an example of some non-power of 2 */
int num_of_iterations = (1 << 20); /* roughly 1 million */
set_N_BUCKETS(num_of_buckets);
set_N_BITS();
unsigned int *buckets = malloc(N_BUCKETS * sizeof(unsigned int));
int i = 0;
while (i < N_BUCKETS) {
*(buckets + i) = 0;
i++;
}
fill_buckets(buckets, num_of_iterations);
evaluate_buckets(buckets);
free(buckets);
return 0;
}
```
以下為 ouput 。
```
0:9126 , 1:9309 , 2:9211 , 3:9250 , 4:9225 , 5:9183 , 6:9302 , 7:9228 , 8:9347 , 9:9298 ,
10:9043 , 11:9237 , 12:9173 , 13:9373 , 14:9219 , 15:9136 , 16:9297 , 17:9155 , 18:9272 , 19:9354 ,
20:9271 , 21:9091 , 22:9190 , 23:9265 , 24:9261 , 25:9110 , 26:9288 , 27:9151 , 28:9135 , 29:9337 ,
30:8928 , 31:9077 , 32:9365 , 33:9249 , 34:9116 , 35:9220 , 36:9123 , 37:9400 , 38:9143 , 39:9241 ,
40:9258 , 41:9233 , 42:9258 , 43:9236 , 44:9177 , 45:9181 , 46:9336 , 47:9370 , 48:9157 , 49:9207 ,
50:9127 , 51:9142 , 52:9318 , 53:9200 , 54:9208 , 55:9237 , 56:9293 , 57:9234 , 58:9340 , 59:9250 ,
60:9298 , 61:9246 , 62:9325 , 63:9188 , 64:8276 , 65:7839 , 66:8209 , 67:8089 , 68:8151 , 69:8152 ,
70:8373 , 71:8140 , 72:8106 , 73:8165 , 74:8261 , 75:8121 , 76:8122 , 77:8192 , 78:8141 , 79:8314 ,
80:8030 , 81:8161 , 82:8217 , 83:8326 , 84:8167 , 85:8202 , 86:8047 , 87:8064 , 88:8220 , 89:8301 ,
90:8405 , 91:8140 , 92:8145 , 93:8215 , 94:8231 , 95:8267 , 96:8099 , 97:8160 , 98:8010 , 99:8113 ,
100:8171 , 101:8298 , 102:8169 , 103:8236 , 104:8188 , 105:8162 , 106:8225 , 107:8257 , 108:8239 , 109:8248 ,
110:8264 , 111:8148 , 112:8247 , 113:8062 , 114:8283 , 115:8170 , 116:8221 , 117:8060 , 118:8114 , 119:8125 ,
```
## 測驗 `4`
:::success
KKKK = `r | shift | x >> 1`
:::
```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;
}
```
從第 6 行開始看，如果 `x` 大於 `0xFFFF` ，則 `x` 16 bits 的 MSB 中必有 1 ，因此 $log_2 x$ 必定大於等於 16 ，那接下來要考慮的就是那 16 bits 的 MSB了，因此將 `x` 往右位移 16 個位元，反之，那如果是小於等於 `0xFFFF`，則 `x` 16 bits 的 MSB 全為 0，因此 $log_2 x$ 就必小於 16，那接下來要考慮的為 16 bits 的 LSB(`r` 此時為 0 ，因此不會位移)。`r` 為用來紀錄了共往右位移了多少位元。
在從第 8 行開始，目前要考慮的為 x 當前的 16 bits 的 LSB ，與 `0xFF` 進行比較，如果比較大，則進行位移，反之則不位移，再把位移值給加回 `r` ，重複此步驟與 `0xF` 、 `0x3` 、 `0x1` 比較。
最後就發現，為什麼沒有與 `0x1` 進行比較？
因為 `x >> 1` 這段就代表了與 `0x1` 作比較的行為。
而最後面 return 要加 1 是因為目標要求的是 $log_2 x$ 的上取整函數(ceil)，加 1 這行為就是對 $log_2 x$ 進行無條件進位，但也會發現，如果 $log_2 x$ 原本就為整數，也會被加 1 ，導致輸出不符合預期的結果。因此第 5 行先將 x 減 1 ，來避免這樣的狀況。
Sign in with Wallet
Connect another wallet