# 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)

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 中的

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 ，則代表該點為紅色，反之，則為黑色。

#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 ，就可以了。

#define rb_parent(r) ((node_t *) ((r)->color & ~7))

以下函式表示對紅黑樹插入新點 `node`。
`obj` 為紀錄整體紅黑樹的資訊，因插入新的點，所以 `obj->size` 要加 1 。
如果這紅黑樹為空，則新插入的點就為這紅黑樹的 root ，則該點改黑，再來對 `obj` 進行調整。
不為空就要找出新插入的點應該要在的位子，找到後插入進去，在對整體紅黑樹進行調整。

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` 就會是一個排序後的序列了。

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 平衡的資訊。

static inline struct avl_node *avl_parent(struct avl_node *node)
{
    return (struct avl_node *) (node->parent_balance & ~7);
}

要取得該點的 balance 資訊，要拿到該點的 `parent_balance` 的末 2 個 bits ，因此

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 資訊。

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` ，且整棵樹也調整完畢。

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$ 。

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 個，運作原理示範於程式碼下。

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` 。

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` 的值。

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 會趨近於亂數。

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 的值印出來，就不多作介紹。

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`
:::

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 ，來避免這樣的狀況。