Try   HackMD

2023q1 Homework4 (quiz4)

contributed by < terry23304 >

測驗 1

把顏色資訊儲存在右子的最低位元中，最低位元為 1 則為紅， 0 為黑

#define rb_node(x_type)           \
    struct {                      \
        x_type *left, *right_red; \
    }

insert

從 root 開始走訪，直到插入點並記錄走訪過的節點

path->node = rbtree->root;                                             \
for (pathp = path; pathp->node; pathp++) {                             \
    int cmp = pathp->cmp = x_cmp(node, pathp->node);                   \
    assert(cmp != 0);                                                  \
    if (cmp < 0) {                                                     \
        pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);   \
    } else {                                                           \
        pathp[1].node = rbtn_right_get(x_type, x_field, pathp->node);  \
    }                                                                  \
}

對樹自底向上進行調整

若 pathp->node 為左子，因為左傾樹，點為左子時不會有平輩節點，不須考慮自己與平輩節點皆為紅的狀況

if (pathp->cmp < 0) {                                              \
    x_type *left = pathp[1].node;                                  \
    rbtn_left_set(x_type, x_field, cnode, left);                   \
    // 若不是紅則符合規則
    if (!rbtn_red_get(x_type, x_field, left))                      \
        return;                                                    \
    x_type *leftleft = rbtn_left_get(x_type, x_field, left);       \
    // 紅紅相連->要往右轉
    if (leftleft && rbtn_red_get(x_type, x_field, leftleft)) {     \
        /* Fix up 4-node. */                                       \
        x_type *tnode;                                             \
        rbtn_black_set(x_type, x_field, leftleft);                           \
        rbtn_rotate_right(x_type, x_field, cnode, tnode);          \
        cnode = tnode;                                             \
    }                                                              \
}

若 pathp->node 為右子，要檢查平輩節點是否皆為紅點與有沒有符合左傾樹與有沒有相鄰的紅點

else {                                                             \
    x_type *right = pathp[1].node;                                 \
    rbtn_right_set(x_type, x_field, cnode, right);                 \
    if (!rbtn_red_get(x_type, x_field, right))                     \
        return;                                                    \
    x_type *left = rbtn_left_get(x_type, x_field, cnode);          \
    if (left && rbtn_red_get(x_type, x_field, left)) {             \
        /* Split 4-node. */                                        \
        rbtn_black_set(x_type, x_field, left);                     \
        rbtn_black_set(x_type, x_field, right);                    \
        rbtn_red_set(x_type, x_field, cnode);                      \
    } else {                                                       \
        /* Lean left. */                                           \
        x_type *tnode;                                             \
        bool tred = rbtn_red_get(x_type, x_field, cnode);          \
        rbtn_rotate_left(x_type, x_field, cnode, tnode);           \
        rbtn_color_set(x_type, x_field, tnode, tred);              \
        rbtn_red_set(x_type, x_field, cnode);                      \
        cnode = tnode;                                             \
    }                                                              \
}

remove

從樹根開始找到要刪除的節點，並往左尋訪找到 successor 並用 pathp 紀錄

path->node = rbtree->root;                                             \
for (pathp = path; pathp->node; pathp++) {                             \
    int cmp = pathp->cmp = x_cmp(node, pathp->node);                   \
    if (cmp < 0) {                                                     \
        pathp[1].node = rbtn_left_get(x_type, x_field, pathp->node);   \
    } else {                                                           \
        pathp[1].node = rbtn_right_get(x_type, x_field, pathp->node);  \
        if (cmp == 0) {                                                \
            /* Find node's successor, in preparation for swap. */      \
            pathp->cmp = 1;                                            \
            nodep = pathp;                                             \
            for (pathp++; pathp->node; pathp++) {                      \
                pathp->cmp = -1;                                       \
                pathp[1].node =                                        \
                    rbtn_left_get(x_type, x_field, pathp->node);       \
            }                                                          \
            break;                                                     \
        }                                                              \
    }                                                                  \
}

若 successor 不等於 node 則代表 successor 在 node 的子樹中

if (pathp->node != node) {                                             \
    /* Swap node with its successor. */                                \
    bool tred = rbtn_red_get(x_type, x_field, pathp->node);            \
    rbtn_color_set(x_type, x_field, pathp->node,                       \
                   rbtn_red_get(x_type, x_field, node));               \
    // 交換 node 與 successor
    rbtn_left_set(x_type, x_field, pathp->node,                        \
                  rbtn_left_get(x_type, x_field, node));               \
    rbtn_right_set(x_type, x_field, pathp->node,                       \
                   rbtn_right_get(x_type, x_field, node));             \
    rbtn_color_set(x_type, x_field, node, tred);                       \

    nodep->node = pathp->node;                                         \
    pathp->node = node;                                                \
    // 若已是 root 則設成　root
    if (nodep == path) {                                               \
        rbtree->root = nodep->node;                                    \
    } else {                                                           \
        // 看目前在 parent node 的左子還是右子樹，並把 Link 接上
        if (nodep[-1].cmp < 0) {                                       \
            rbtn_left_set(x_type, x_field, nodep[-1].node,             \
                          nodep->node);                                \
        } else {                                                       \
            rbtn_right_set(x_type, x_field, nodep[-1].node,            \
                           nodep->node);                               \
        }                                                              \
    }                                                                  \
}

若要刪除的節點 successor 不在 node 的右子樹中

else {                                                                 \
    x_type *left = rbtn_left_get(x_type, x_field, node);               \
    if (left) {                                                        \
        /* node has no successor, but it has a left child.        */   \
        /* Splice node out, without losing the left child.        */   \
        assert(!rbtn_red_get(x_type, x_field, node));                  \
        assert(rbtn_red_get(x_type, x_field, left));                   \
        rbtn_black_set(x_type, x_field, left);                         \
        if (pathp == path) {                                           \
            rbtree->root = left;                                       \
            /* Nothing to summarize -- the subtree rooted at the  */   \
            /* node's left child hasn't changed, and it's now the */   \
            /* root.                                              */   \
        } else {                                                       \
            if (pathp[-1].cmp < 0) {                                   \
                rbtn_left_set(x_type, x_field, pathp[-1].node, left);  \
            } else {                                                   \
                rbtn_right_set(x_type, x_field, pathp[-1].node, left); \
            }                                                          \
        }                                                              \
        return;                                                        \
    } else if (path == pathp) {                                        \
        /* The tree only contained one node. */                        \
        rbtree->root = NULL;                                           \
        return;                                                        \
    }                                                                  \
}

測驗 2

Timsort: 採用了 insersion sort 與 merge sort
先分成小區塊，再用 Insertion Sort 對每個區塊做排序，再把這些區塊合併起來

inplace merge

合併兩個 run [1, 2, 5, 7] 、 [3, 4, 6, 8]

找到 run 1 中小於 cur_2 的區域 (1, 2)，用 cur_1 紀錄

while (cur_1 < last_2 && !cmp(cur_2, cur_1))
    cur_1 += size;

找到 run 2 中小於 cur_1 的區域 (3, 4)，用 cur_2 紀錄

while (cur_2 < last_2 && cmp(cur_2, cur_1))
    cur_2 += size;







%0



Pointers:
Pointers:



Values:
Values:



Pointers:->Values:





pointers

first_1

cur_1

last_1

first_2

cur_2

last_2



values

1

2

5

7

3

4

6

8



pointers:f0->values:f0





pointers:f1->values:f4





pointers:f2->values:f3





pointers:f3->values:f7





pointers:f7->values:f2





pointers:f10->values:f6

先反轉 cur_1 到 first_2 -= size

__reverse(cur_1, first_2, size);







%0



Pointers:
Pointers:



Values:
Values:



Pointers:->Values:





pointers

first_1

cur_1

last_1

first_2

cur_2

last_2



values

1

2

7

5

3

4

6

8



pointers:f0->values:f0





pointers:f1->values:f4





pointers:f2->values:f3





pointers:f3->values:f7





pointers:f7->values:f2





pointers:f10->values:f6

再翻轉 first_2 到 cur_2 -= size

__reverse(first_2, cur_2, size);







%0



Pointers:
Pointers:



Values:
Values:



Pointers:->Values:





pointers

first_1

cur_1

last_1

first_2

cur_2

last_2



values

1

2

7

5

4

3

6

8



pointers:f0->values:f0





pointers:f1->values:f4





pointers:f2->values:f3





pointers:f3->values:f7





pointers:f7->values:f2





pointers:f10->values:f6

最後翻轉 cur_1 到 cur_2 ，完成 first_1 到 cur_2

__reverse(cur_1, cur_2, size);







%0



Pointers:
Pointers:



Values:
Values:



Pointers:->Values:





pointers

first_1

cur_1

last_1

first_2

cur_2

last_2



values

1

2

3

4

5

7

6

8



pointers:f0->values:f0





pointers:f1->values:f4





pointers:f2->values:f3





pointers:f3->values:f7





pointers:f7->values:f2





pointers:f10->values:f6

更新 first_1 、 first_2 指到尚未排序的區域

first_1 = cur_1 + (cur_2 - first_2);
first_2 = cur_2;







%0



Pointers:
Pointers:



Values:
Values:



Pointers:->Values:





pointers

first_1

first_2



values

1

2

3

4

5

7

6

8



pointers:f0->values:f4





pointers:f1->values:f7

再用同樣的方式繼續合併直到完成

merge rule

若 run 的大小差不多合併的效率更好，所以在下層長度比上層大時才合併

return run_length(stack[top]) > run_length(stack[top - 1]) ||
       run_length(stack[top]) + run_length(stack[top - 1]) >
           run_length(stack[top - 2]);

next partition

切出各個 run 並用 insertion sort 排序
計算有多少數已是升冪或降冪排序好的，若為降冪則做反轉，並計算該 run 的長度

if (cmp(cur, next)) {
    while (next < last && cmp(cur, next)) {
        ++run_len;
        cur += size;
        next += size;
    }
} else {
    while (next < last && !cmp(cur, next)) {
        ++run_len;
        cur += size;
        next += size;
    }
    __reverse(first, next, size);
}

若長度還小於 MIN_RUN 且總長比 MIN_RUN 大則加大該 run 的長度，並用 insertion sort 排序。

    if (next < last && run_len < MIN_RUN) {
        last = first + MIN_RUN * size < last ? first + MIN_RUN * size : last;
        __insertion_sort(first, last, size, cmp);
        return (last - first) / size;
    }
    return run_len;
}

timsort

把數列切成好幾個 run 放進 stack 中，若符合規則每次取兩個合併

while (cur < last) {
    size_t len = next_partition(cur, last, size, cmp);
    stack[top].first = cur;
    stack[top].last = stack[top].first + len * size;
    cur = stack[top].last;

    while (merge_rule(stack, top)) {
        if (buf)
            __merge(stack[top - 1].first, stack[top - 1].last,
                    stack[top].first, stack[top].last, buf, size, cmp);
        else
            __inplace_merge(stack[top - 1].first, stack[top - 1].last,
                            stack[top].first, stack[top].last, size, cmp);

        stack[top - 1].last = stack[top].last;
        top --;
    }
    top++;
}

最後把剩餘的 run 合併起來

while (top > 1) {
    --top;
    if (buf)
        __merge(stack[top - 1].first, stack[top - 1].last, stack[top].first,
                stack[top].last, buf, size, cmp);
    else
        __inplace_merge(stack[top - 1].first, stack[top - 1].last,
                        stack[top].first, stack[top].last, size, cmp);
    // 合併 top 跟 top - 1 所以要更新 top - 1 的 last
    stack[top - 1].last = stack[top].last;
}

測驗 3

#define RB_LOG2_MAX_NODES            \
    (RB_LOG2_MAX_MEM_BYTES -         \
     (sizeof(void *) >= 8   ? 4      \
      : sizeof(void *) >= 4 ? 3   \
                            : 2) - 1)

sum subtree

int result = 0;
while (node) {
    node_t *pre;
    if (!rbtn_left_get(node_t, link, node))
        goto do_print;
    for (pre = rbtn_left_get(node_t, link, node);
         rbtn_right_get(node_t, link, pre) &&
         rbtn_right_get(node_t, link, pre) != node;
         pre = rbtn_right_get(node_t, link, pre)) {
    }
    if (!rbtn_right_get(node_t, link, pre)) {
        // 把右子設成 Node
        rbtn_right_get(node_t, link, pre) = node;
        node = rbtn_left_get(node_t, link, node);
    } else {
        rbtn_right_get(node_t, link, pre) = NULL;

    do_print:
        result += node->value;
        printf("value: %d\n", node->value);
        node = rbtn_right_get(node_t, link, node);
    }
}
Last changed by 
 
李晨瑞
0
280

Read more

Linux Kernel Development

A process is a program in the midst of execution. To Linux thread is just a process which share resources with other process (e.g. )

Jan 20, 2025
RV32 port for MIT xv6 operating system (and contribute!)

2.1 下載原始碼注意取得原始碼時採用git clone 的方式會非常慢，所以我們推薦根據你需要的版本號直接下載對應的源碼壓縮包的方式，本次實驗採用的是目前最新的v5.1.0。

Jan 21, 2024
Assignment 3: single-cycle RISC-V CPU

when ===

Dec 1, 2023
Computer Architecture HW2

riscv64-unknown-elf-gcc -march=rv32i -mabi=ilp32 pi.c -o pi

Nov 30, 2023
Read more from 李晨瑞
Published on HackMD