###### tags: `Linux`
# 2023q1 Homework3 (quiz3)
contributed by < [`shhung`](https://github.com/shhung) >
[quiz3](https://hackmd.io/@sysprog/linux2023-quiz3)

## 測驗`1`

觀察結構的宣告

typedef struct __node {
    uintptr_t color;
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t __attribute__((aligned(sizeof(long))));

aligned 8 個 byte，代表定址都會是 8 的倍數，也就是最低位的 3 個位元不會被用到，可以利用這三個位元來做顏色的設定。

#define rb_parent(r) ((node_t *) (((r)->color & ~7))) // AAAA
#define rb_color(r) ((color_t) (r)->color & 1)

可以看到 `rb_color` 是取最後一個位元當作顏色，所以我們要將顏色設定在最後一個位元

// BBBB
#define rb_set_red(r)               \
    do {                            \
        (r)->color &= ~1;     \
    } while (0)
// CCCC
#define rb_set_black(r)             \
    do {                            \
        (r)->color |= 1;   \
    } while (0)

`DDDD` 和 `EEEE` 所在的部份是在做 tree 的尋訪，根據程式碼邏輯分別為向左和向右

    /* 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; // DDDD
        } else {
            if (!cur->right) {
                cur->right = node;
                rb_set_parent(node, cur);
                cmap_fix_colors(obj, node);
                break;
            }
            cur = cur->right; // EEEE
        }
    }

`FFFF` ,`GGGG`, `HHHH` 位於 `tree_sort` 之中，程式邏輯是將數列依序存如由紅黑樹實做的 `cmap` 結構中，而在插入的過程中依照大小存放，因此當資料都放進去後，循序走訪將資料都取出後即可獲得排序完的數列。

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 = FFFF;
        list = &(*list)->next;
    }
    node_t *node = cmap_first(map), *first = node;
    for (; node; node = cmap_next(node)) {
        *list = node;
        // list = GGGG;
        list = &(*list)->next;
    }
    // HHHH;
    *list = NULL;
    *record = first;
    free(map);
}

## 測驗 `4`

先思考 `log` 用 bitwise 來看的話要怎麼找， `8` 的二進位是 `b'00001000`，取 `log` 就是 `3`，再觀察其他數值發現最高位往後看第一個 `1` 出現的位置就是 `log` 的答案，類似 `quiz2` 用到的 `__builtin_ffs`，而資料型態為 `32` 位元，所以每次會比較一半的位元， $2^{n-1}, ..., 2^1$ ， `r` 用來累加比較的結果， `shift` 則用來暫存每一次比較的結果，因此在 `return` 的地方也必須再做一次 `r | shift` 將 `(x > 0x3) << 1` 的結果加起來，而最後 `x` 還有 `2` 個位元沒有比到， `x` 可能是 `b'11` `b'10` `b'01` `b'00`，這邊只要將 `x` 右移 `1` 位就能得到結果不需要比較，因此 `return` 要再加上 `x >> 1`，而 `()`外的 `+1` 是因為一開始的 `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 (KKKK) + 1;       
    return (r | shift | x >> 1) + 1;       
}