2023q1 Homework3 (quiz3)

contributed by <Shiritai>

測驗一

完成紅黑樹 parent 指標之指標、對齊、顏色等相關操作。

AAAA 考慮對齊，取得親代指標
指標以 long (64 bits) 對齊，由於每個地址指向一 byte (8 bits)，故真正對齊的地址需為
$\frac{64}{8} = 8$ 的倍數，也就是最低
$3$ 位元應為零。
不過考慮 long 在不同 ABI 下長度不一，此時可以利用 sizeof 處理跨平台的情況。
```
#define rb_parent(r) ((node_t *) ((r)->color & ~(sizeof(long) - 1)))
```
BBBB 設定顏色為紅色
單純對最低位進行標記。
```
(r)->color &= CMAP_RED; // CMAP_RED = 0
```

CCCC 設定顏色為黑色
單純對最低位進行標記。

(r)->color |= CMAP_BLACK; // CMAP_BLACK = 1

完成走訪邏輯

DDDD、EEEE 走訪左右子樹，當非走訪至葉節點且與當前節點相比較小／大時，往左／右子節點走訪。

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

完成 treesort 邏輯

保存間接指標以利收尾
```
node_t **record = list;
```

將欲排序資料放入 cmap

cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
while (*list) {
    cmap_insert(map, *list, NULL);
    list = &(*list)->next; // TODO: FFFF
}

中序遍歷整顆紅黑樹，重建 list

node_t *node = cmap_first(map), *first = node;
for (; node; node = cmap_next(node)) {
    *list = node;
    list = &(*list)->next; // TODO: GGGG
}

收尾
將 list 末個 next 設為 NULL 後，重設間接指標的起點。

*list = NULL; // TODO: HHHH
*record = first;
free(map);

圖示化分析以間接指標遍歷的邏輯

以中序遍歷重建 list，為例，其使用間接指標的技巧，避免邊界條件判斷的必要。假設從 a 走訪到 c，行為如下圖所示：

*list = node (1), list = &(*list)->next

*list = node (2), list = &(*list)->next

*list = node (3), list = &(*list)->next

假設遍歷完樹，收尾時將最後一個 next 設為 NULL ~~是業界常態~~

測驗二

節點與平衡標記相關

取親代指標的邏輯與測驗一同理，利用 sizeof 完成跨平台的指標對齊。

static inline struct avl_node *avl_parent(struct avl_node *node)
{
    // TODO: IIII
    return (struct avl_node *) (node->parent_balance & ~(sizeof(unsigned long) - 1));
}

取顏色直接取最低兩位元即可，之所以是兩位元是因為平衡因子有 0, 1, 2 三種可能，佔

2

bits。

static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
    // TODO: JJJJ
    return (enum avl_node_balance)(node->parent_balance & 3);
}

指派 `parent_balance` 成員

為其指派親代節點指標可利用之前實作的 avl_balance 函式保留平衡因子的部分：

static void avl_set_parent(struct avl_node *node, struct avl_node *parent)
{
    // TODO: KKKK
    node->parent_balance =
        (unsigned long) parent | (avl_balance(node));
}

指派平衡因子時同理可複用之前實作過的 avl_parent 函式來保留親代指標的部分：

static void avl_set_balance(struct avl_node *node,
                            enum avl_node_balance balance)
{
    // TODO: LLLL
    node->parent_balance =
        ((enum avl_node_balance) avl_parent(node)) | balance;
}

AVL 樹插入節點的平衡操作

旋轉比較難畫，就直接引用維基百科的圖了。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

觀察 MMMM, NNNN 所在之迴圈中較前面，針對 RR／RL 所執行的左旋轉／右旋後左旋，推斷 MMMM 和 NNNN 為處理 LL／LR 的情況，故為對應的右旋轉／左旋後右旋，實作如下：

// inside while loop
if (avl_is_right_child(node)) { ... } else {
    switch (avl_balance(parent)) {
        ...
    case AVL_LEFT:
        /* compensate double left balance by rotation
         * and stop afterwards
         */
        switch (avl_balance(node)) {
        default:
        case AVL_LEFT:
        case AVL_NEUTRAL:
            // TODO: MMMM
            avl_rotate_right(node, parent, root);
            break;
        case AVL_RIGHT:
            // TODO: NNNN
            avl_rotate_leftright(node, parent, root);
            break;
        }
        ...
    }
}

測驗三

TODO

測驗四

測驗四題目

以下程式碼應實現

⌈ \log_{2} (x) ⌉

。

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

測驗四分析

觀察程式碼，由其行為可見當 x 大於某二的冪長度之全一時，便以 shift 蒐集某長度之全一的長度，記錄 shift 於 r 後將 x 位移 shift。從

16

個

1

開始，推測最後會處理一個 1 的情況，故我們應該看到：

// collect result of 0x3 part
// ...
r |= shift;
// collect result of 0x1 part
shift = (x > 0x1) << 0;
x >>= shift;
r |= shift;

上述程式碼對 x 的操作沒有必要，因為後續不再使用，故 (不考慮註解的) 第 3 行可去除，並可將 1, 2, 3 行簡化為：

r |= shift | x > 0x1;

至於 r 紀錄了什麼？當 x 為無號最大值

x_{m a x}

(全一) 時，shift 一路下來捕獲了

16, 8, 4, 2, 1

，並將其以 or 運算紀錄於 r，結果為

31

，與

⌈ \log_{2} (x_{m a x}) ⌉ = 32

差一，由此認為 return (KKKK) + 1; 的 + 1 因此出現。

這樣一來 KKKK 為何就比較明朗了。考慮前方簡化版邏輯，由於直接回傳，不需要將結果存入 r，故改為 expression 版如下：

return (r | shift | (x > 0x1)) + 1;

再來我們簡化 x > 0x1 的部分。由於我們已經使用

2^{1}, 2^{1}, 2^{3}, 2^{4}

這幾把拿來左移的尺，對於

32

位元的數字而言只可能還沒碰到原本最高的兩位，此時 x 只剩

0 \sim 3

這四種可能，故可替換其邏輯為 x >> 1，捕獲未觸碰的原最高位。

所以答案為

KKKK = r | shift | x >> 1