2023q1 Homework3 (quiz3)

contributed by < koty6069 >

2023q1 第 3 週測驗題

測驗 1

程式碼解析 (incomplete treesort.c)

此程式主要是使用 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 核心 相同的技巧，宣告 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。

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 核心的紅黑樹。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。