# 2023q1 Homework3 (quiz3)
contributed by < `koty6069` >

[2023q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)
## 測驗 `1`
### 程式碼解析 [(incomplete treesort.c)](https://gist.github.com/jserv/920766d1fd893d0efd66ac7fdaf23401)
此程式主要是使用 C 實作紅黑樹來實現 C++ 中的 `std::map`。

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

定義紅黑樹節點時使用與 [linux 核心](https://github.com/torvalds/linux/blob/master/include/linux/rbtree_types.h) 相同的技巧，宣告 `unsigned long` 儲存親代節點，並透過 `__attribute__((aligned(sizeof(long))))` 將此結構對齊 `sizeof(long)` ，使得最低 2 個位元空出，就可以將顏色儲存在最低位元中。

與 linux 核心的宣告不同處在於，因為要直接使用來進行排序，因此將 `value` 放在結構體內用來存放數值，並且新增 `next` 指向原本 `list` 中的下一個節點。
> 在 `/usr/include/stdint.h` 可以得知 `uintptr_t` 為 `unsigned long` 型態。

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

根據名字可以看出 `rb_parent` 用來取得親代節點，`rb_color` 用來取得當前節點的顏色，因為親代節點和顏色同時存放在 `uintptr_t color` 中，要取得顏色就是將最低位元取出，要取得親代節點則是要去除掉最低位元，因此 `AAAA` 為 `(r)->color & ~1`。

typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;

在此實作中將紅色設定為 0、黑色為 1，所以設定顏色時就是將最低位元設定為 0 或 1。

#define rb_set_red(r) \
    do {              \
        BBBB;         \
    } while (0)
#define rb_set_black(r) \
    do {                \
        CCCC;           \
    } while (0)

要設成紅色就是與 `1111...1110` 做 `and`，`BBBB` 為 `(r)->color &= ~1`，要設成黑色就是與 `0000...0001` 做 `or`， `CCCC` 為 `(r)->color |= 1`。
<!--

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

新加入的節點應該為紅色，對照 119 行也是如此，所以 118 行應該為 red 而非 black。
-->

static node_t *cmap_rotate_left(cmap_t obj, node_t *node)
static node_t *cmap_rotate_right(cmap_t obj, node_t *node)

`cmap_rotate_left` 和 `cmap_rotate_right` 為單一次的左旋轉和右旋轉，可參考 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree#%E7%B0%A1%E8%BF%B0%E7%B4%85%E9%BB%91%E6%A8%B9)。`cmap_l_l`、`cmap_l_r`、`cmap_r_r` 和 `cmap_r_l` 則是插入或刪除紅黑樹節點時遇到不同情況進行的調整，會透過 `cmap_fix_colors` 在調整顏色時呼叫這些函式進行使用。

static bool cmap_insert(cmap_t obj, node_t *node, void *value)

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

`cmap_insert` 為插入新節點，因此會透過 `for` 迴圈找到應該對應的位置，與一般的二元搜尋樹相同，若要插入的值較小就往左走，反之往右走，若當前節點的左或右子樹為 `NULL`，就代表找到插入的位置，也就是會進入 `if (!cur->left)` 和 `if (!cur->right)` 條件式中，將節點放入該位置並檢查插入節點後的紅黑樹是否符合規則，若不為 `NULL` 代表需要繼續向左或右走，因此 `DDDD` 為 `cur = cur->left`，`EEEE` 為 `cur = cur->right`。

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

`tree_sort` 則是使用 `map` 來進行排序，會傳入一個要被排序的 `list`，在 `while` 迴圈中一個一個將值插入 `map`，因此 `FFFF` 為 `&(*list)->next`，接著在 `for` 迴圈中使用 `cmap_next` 照順序取出並放回 `list` 即完成排序，`GGGG` 同樣為 `&(*list)->next`，當兩個迴圈都執行完時，`*list` 會落在 `list` 的最尾端，需要將其指向 `NULL` 表示結束，所以 `HHHH` 為 `*list = NULL`。