# 2023q1 Homework3 (quiz3)
contributed by <terry23304>
## 測驗 1
```c
typedef struct __node {
uintptr_t color;
struct __node *left, *right;
struct __node *next;
long value;
} node_t __attribute__((aligned(sizeof(long))));
```
透過 ` __attribute__((aligned(sizeof(long))))` 把 `struct __node` 對齊 `sizeof(long)`
```c
typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;
#define rb_parent(r) ((node_t *) ((r)->__rb_parent_color & ~(sizeof(long)-1)))
#define rb_color(r) ((color_t) (r)->color & 1)
```
捨棄最低位的 $log(sizeof(long))$ 個位元，將結果轉為 pointer to node_t 就可以得到 parent 的位址
```c
#define rb_set_red(r) \
do { \
r->color &= 0; \
} while (0)
#define rb_set_black(r) \
do { \
r->color |= 1; \
} while (0)
```
最低位元儲存顏色，若為 0 是紅色， 1 則是黑色
`cmap_insert`
比較要插入的節點與目前節點的大小，較小往左走，反之往右。
```c
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) { // 往左 traverse
if (!cur->left) { // 無左子則插入
cur->left = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
cur = cur->left;
} else { // 往右 traverse
if (!cur->right) { // 無右子則插入
cur->right = node;
rb_set_parent(node, cur);
cmap_fix_colors(obj, node);
break;
}
cur = cur->right;
}
}
```
插入節點，並將節點依照順序串起來，最後把末端的 `next` 指向 `NULL`
```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
parent_balance: combination of @parent and @balance (lowest two bits)
```c
struct avl_node {
unsigned long parent_balance;
struct avl_node *left, *right;
} AVL_NODE_ALIGNED;
```
parent_balance 最後兩 bit 儲存 balance 資訊，去除最後 3 bit 即可得到 parent address
```c
static inline struct avl_node *avl_parent(struct avl_node *node)
{
return (struct avl_node *) (node->parent_balance & ~3);
}
```
要取得 balance 狀態則取得 `node->parent_balance` 最後兩 bit 即可
```c
static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
return (enum avl_node_balance)(node->parent_balance & 3);
}
```
設定 node 只需把 address 與 balance 狀態結合
```c
static void avl_set_parent(struct avl_node *node, struct avl_node *parent)
{
node->parent_balance =
(unsigned long) parent | parent->parent_balance & 3;
}
static void avl_set_balance(struct avl_node *node,
enum avl_node_balance balance)
{
node->parent_balance = (unsigned long) node | balance;
}
```
插入新節點後確認是否還平衡，先檢查插入節點是左子還是右子，再檢查 parent 的 balance 狀態在插入新節點後是否平衡，若新結點為右子，且 parent 平衡狀態為 `AVL_RIGHT` 則需要旋轉來調整平衡，若為 `AVL_NEUTRAL` 則把 parent balance 狀態改為 `AVL_RIGHT` 即可，而若是 `AVL_LEFT` 在右子插入一節點後 parent 左右子樹高度會相等，把平衡狀態改為 `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
`log_table_256[x]` 值為 $\left \lfloor{log_2 x}\right \rfloor$， `_(n)` 展開後會是 16 個 n
```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 位元，而查表只能查到 256 個 log 值，將 64 位元切成八個區塊與測驗四一樣使用 binary search 來找到 v 的大小並補上 log 值
```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) {
// 32 + 16 + 8 = 56
r = 56 + log_table_256[t];
} else {
// 32 + 16 = 48
r = 48 + log_table_256[tt];
}
} else {
t = ttt >> 8;
if (t) {
// 32 + 8 = 40
r = 40 + log_table_256[t];
} else {
r = 32 + log_table_256[ttt];
}
}
} else {
tt = v >> 16;
if (tt) {
t = tt >> 8;
if (t) {
// 16 + 8 = 24
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;
}
```
```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));
/* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
* '... & mask011' guarantees that the result is less or equal N_BUCKETS.
*/
}
```
## 測驗 4
輸入為 32 位元的 unsigned int
利用 binary search 概念找出 leading 1 在哪一區塊
若 `x > 0xFFFF` 則 `x` 右移 16 bit 留下 x 左半部分的位元
```c
r = (x > 0xFFFF) << 4;
x >>= r;
```
若剩下的 16 bit 左邊 8 bit 不為零則再捨棄 x 右半邊，留下左半部分的位元
```c
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
```
剩下 8 bit 左邊 4 bit 不為零則捨棄 x 右 4 bit 的位元
```c
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
```
檢查最後 4 bit leading 1 在前兩 bit 還是後兩 bit
```C
shift = (x > 0x3) << 1;
x >>= shift;
```
總共 32 bit，取 log 後可用 5 bit 表示，左 3 bit 由 `r` 紀錄，第二位元由 `shift` 決定， 因最後的 `x` 只會剩下兩 bit ， lsb 由 `x>>1`來得知剩下兩 bit leading 1 位置。
`r | shift | x >> 1) + 1`
+1 為補上一開始的 -1 來達到上高斯的效果
Sign in with Wallet
Connect another wallet