# 2023q1 Homework3 (quiz3)
contributed by < [Huaxin](https://github.com/p96114175) >
> [題目](https://hackmd.io/@sysprog/linux2023-quiz3)
:::info
* 測驗一
- [ ] 指出 treesort.c 程式碼的缺失並改進
- [ ] 利用 Linux 核心的 list.h 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 Tree sort 的效率
- [ ] 研讀 Linux 核心的 Red–black tree 程式碼，比較給定的 treesort.c 實作手法，指出後者的改進空間並予以實作
* 測驗二
- [ ] 解釋上述程式碼運作原理，並比較用紅黑樹實作的 priority queue，應提供完整的測試程式和效能分析
- [ ] Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素，並搭配 git log 來解讀
- [ ] 研讀 Linux 核心原始程式碼，指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 rbtree.h，探究是否可用後者替換，從而爭取到貢獻程式碼到 Linux 核心的機會
* 測驗三
- [ ] 解釋 Linear feedback shift register (LFSR) 的運作原理，搭配在 Linux 核心原始程式碼中，用 git log 和 grep 找出 LFSR 的應用案例
- [ ] 解釋上述程式碼運作的原理
- [ ] 在 Linux 核心原始程式碼中找到 log2(x) 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數log2(x) 的應用案例並解說。
- [ ] lab0-c 提供類似的實作 log2_lshift16.h，解釋其原理並嘗試改進其效能
* 測驗四
- [ ] 解釋上述程式碼運作原理
- [ ] 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
- [ ] 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例，例如在 Linux 核心排程器就有
:::

## 測驗一
研究以下文件
[treesort.c](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)
* 定義一個結構體，名為　`node_t`　用於實現紅黑樹。
* `uintptr_t color` 用於儲存節點在紅黑樹的顏色。
* `*left` `*right` 用來指向該節點的兩個左右子節點
* `*next` 用來指向該節點的下一個節點
* 定義一個 `long` 的 `data type` 儲存該節點的值

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

使用結構體 `cmap_internal` 記錄了 `map` 資訊，其中也包含了紅黑樹的根節點 `*head` ， 和比較的涵數指標

struct cmap_internal {
    node_t *head;

    /* Properties */
    size_t key_size, element_size, size;

    cmap_iter_t it_end, it_most, it_least;

    int (*comparator)(void *, void *);
};

定義出顏色中的紅和黑

typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;

使用了 `color` 表示了兩項資訊，分別為節點的顏色、指向父節點的指標 ，這樣可以節省記憶體空間。
透過 `& ~7` ，也就是 `1...11000` 使得 `color` 末 `3` 位元皆為 `0`，便可獲得指向父節點的指標。
若要取得節點的顏色，則使用 `& 1` ，也就是0...00001，取得 LSB 的資訊

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

我們可以從 `rb_set_red` 名稱得知，這是個將節點顏色設定成紅色的功能，其中透過的方法就是 `&= ~1` ，也就是 `color` 對 `1...1110` 做 `&` 操作，使得 LSB 為 `0`。
而 `rb_set_black` 則是將節點設定成黑色，其中會透過 `|= 1` 來達成，也就是將 `color` 對 `0...0001` 做 `|` 操作

#define rb_set_parent(r, p)                         \
    do {                                            \
        (r)->color = rb_color(r) | (uintptr_t) (p); \
    } while (0)
#define rb_set_red(r) \
    do {              \
        (r)->color &= ~1;         \
    } while (0)
#define rb_set_black(r) \
    do {                \
        (r)->color |= 1;          \
    } while (0)

下方函數則用於初始化一個新的紅黑數節點，將左右子節點指標和父節點指標設為 `null`，並將節點顏色初始化設為紅色，但我不明白為何註解上是寫成黑色為 `dedault`，還需要 jserv 老師指教一下

static node_t *cmap_create_node(node_t *node)
{
    /* Setup the pointers */
    node->left = node->right = NULL;
    rb_set_parent(node, NULL);

    /* Set the color to black by default */
    rb_set_red(node);

    return NULL;
}

下方函數則是在對 `node` 進行左旋操作

static node_t *cmap_rotate_left(cmap_t obj, node_t *node)
{
    node_t *r = node->right, *rl = r->left, *up = rb_parent(node);

    /* Adjust */
    rb_set_parent(r, up);
    r->left = node;

    node->right = rl;
    rb_set_parent(node, r);

    if (node->right)
        rb_set_parent(node->right, node);

    if (up) {
        if (up->right == node)
            up->right = r;
        else
            up->left = r;
    }

    if (node == obj->head)
        obj->head = r;

    return r;
}

下方函數則是在對 `node` 進行右旋操作

static node_t *cmap_rotate_right(cmap_t obj, node_t *node)
{
    node_t *l = node->left, *lr = l->right, *up = rb_parent(node);

    rb_set_parent(l, up);
    l->right = node;

    node->left = lr;
    rb_set_parent(node, l);

    if (node->left)
        rb_set_parent(node->left, node);

    if (up) {
        if (up->right == node)
            up->right = l;
        else
            up->left = l;
    }

    if (node == obj->head)
        obj->head = l;

    return l;
}

`cmap_l_l`, `cmap_l_r`, `cmap_r_r`, `cmap_r_l` 則是在平衡我們的紅黑樹時所使用的函數

在 `cmap_insert` 我們可以觀察到如何插入一個 `key/value pair` 到我們的 `cmap`，下方程式則是 `cmap_insert` 中的一部分，主要是在遍尋 `tree` 找尋可以插入的位置，透過比較 `node->value` 和 `cur->value` 得到 `res`，當 `res` 小於零時便會往左子節點走，反之則往右子節點走，若要終止 `for loop` 的條件為 `res` 為 `false` ，也就意味著走訪到的節點為空，便直接做插入的動作並跳出 `loop`。

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;
    }
}

在 `tree_sort` 裡輸入需要排序的 `list`，並用 `record` 指向 `list`，首先透過 `cmap_new` 建立了 `map` 並將 `list` 的節點依序輸入進去 `map` ，然後再用 `cmap_first` 從 `map` 裡找出第一個節點，並用 `first` 指向它，`for (; node; node = cmap_next(node))` 透過迭代 `cmap` 中的每一個節點，儲存到 `list` 中，最後再將 `list` 中最後一個節點的 `next` 指標設定為 `null` ，再把 `record` 指向新的 `list` 的頭節點 `first` ，將使用完的 `map` 釋放掉內存，即可完成排序。

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);
        printf("%ld\n", map->size);
        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);
}

## 測驗二
## 測驗三
## 測驗四