> [github](https://github.com/backink/Linux2023_summer/tree/main/hw1)

## 測驗 α

目標：完成 Incomplete search tree 當中未完成的部份程式碼

原始程式碼見 [main.c](https://gist.github.com/jserv/4dfaf78cf516cc20f4bc55ce388c195d)

### α - 1

以下節錄部份程式碼

void st_remove(struct st_node **root, struct st_node *del)
{
    if (st_right(del)) {
        struct st_node *least = st_first(st_right(del));
        if (del == *root)
            *root = least;

        AAAA;
        BBBB;
        return;
    }

    if (st_left(del)) {
        struct st_node *most = st_last(st_left(del));
        if (del == *root)
            *root = most;

        CCCC;
        DDDD;
        return;
    }

    if (del == *root) {
        *root = 0;
        return;
    }

    /* empty node */
    struct st_node *parent = st_parent(del);
    if (st_left(parent) == del)
        st_left(parent) = 0;
    else
        st_right(parent) = 0;

    EEEE;
}

AAAA 為 ```st_replace_right(del, least);```
若 del 有 right child 則找右子樹最小值作為刪除後的替換值

BBBB 為 ```st_update(root, st_right(least))```
替換後 update 右子樹

CCCC 為 ```st_replace_left(del, most);```
若 del 有 left child 則找左子樹最大值作為刪除後的替換值

DDDD 為 ```st_update(root, st_left(most))```
替換後 update 左子樹

EEEE 為 ```st_update(root, parent);```
若刪除節點左右 child 都為 NULL，刪除完後從parent node 開始update

:::warning
因為 update 是從 bottom up 往上平衡，我認為應該要從替換節點（least 和 most）的 parent 開始向上 update，因為 least 和 most 從原本位置移掉之後，hint 值可能受到影響的節點應該會從他們的 parent 開始，但是目前的程式碼似乎沒有記錄這個節點
:::

static void __treeint_dump(struct st_node *n, int depth)
{
    if (!n)
        return;

    __treeint_dump(FFFF, depth + 1);

    struct treeint *v = treeint_entry(n);
    printf("%d\n", v->value);

    __treeint_dump(GGGG, depth + 1);
}

依據 inorder traversal 的原則
FFFF 為 ```st_left(n)```
GGGG 為 ```st_right(n)```

:::success
延伸問題

2. 指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作
3. 設計效能評比程式，探討上述程式碼和 red-black tree 效能落差
:::

### α - 2

在理解S-tree程式碼的過程中，發現在特定insert sequence 會造成搜尋特定節點會需要 O(n)時間
如圖顯示在插入new node之後，左方的樹會旋轉成右邊的形狀，且update函數在遞迴後不會update到parent節點
利用這樣的特性繼續插入節點，會發現形成一個左傾且接近線性的樹形（相對rotate left可以刻意製造右傾的樹），導致後續搜尋節點時會需要O(n)的時間複雜度

### α - 3
測試效能

## 測驗 β

以下程式碼可針對給定的 alignment 數值，輸出大於等於 alignment 的記憶體對齊地址

目標：已知 alignment 不為 0，填補 MMMM 使程式碼輸出符合預期結果

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {  /* power of two? */
        return MMMM;       
    }
    return (((sz + mask) / alignment) * alignment);
}

### β - 1

update：答案中不能出現 alignment，修改答案在下面，最初答案仍保留方便檢視思考過程

MMMM 為 ```sz + ((alignment - (sz & mask)) & (~alignment))```
當 alignment 本身是 2 的冪，例如 alignment = b000...1000， mask 會是 b000...0111
以下分成兩種情況討論
1. 若 sz 在 alignment 以下位元有值需要向上對齊，以 sz = b011...0010 為例， ```alignment - (size & mask)``` b000...1000 - b000...0010 會等於 b000...0110（在此情況中，```& (~alignment)``` 等於 & b111...0111 不影響計算結果）
而 sz 加上此數值 b011...0010 + b000...0110 會等於將不及 alignment 長度的尾數向上補齊至一個 alignment 的位置 b011...1000
2. 若 sz 在 alignment 以下位元沒有值，是已經對齊好的狀態，例如 sz = b011...1000，```alignment - (size & mask)``` 會是 b000...1000，在 ```& (~alignment)```後會得到 0，sz 加上 0 則保持原本數值，符合已經對齊好不改變的預期結果

Update：
MMMM 為 ```(sz + mask) & (~mask)```

:::success
延伸問題

2. 在 Linux 核心原始程式碼找出類似 align_up 的程式碼，並舉例說明其用法
:::

## 測驗 γ

HHHH 為 ```pthread_cond_wait(&qs->cond_st, &qs->mtx_st)```
根據上下文程式碼邏輯

verify(pthread_mutex_lock(&qs->mtx_st));
while (qs->st == ts_idle)
    verify(HHHH);
verify(pthread_mutex_unlock(&qs->mtx_st));

在獲得mutex之後，若滿足while條件（idle）則需要放棄mutex且在condition variable 基礎上等待其他thread對此condition variable發出signal，喚起等待中的thread重新獲得mutex並檢查是否可以跳出while迴圈往下執行

JJJJ 為 ```pthread_cond_signal(&qs2->cond_st)```
根據上下文程式碼邏輯

verify(pthread_mutex_lock(&qs2->mtx_st));
qs2->st = ts_term;
verify(JJJJ);
verify(pthread_mutex_unlock(&qs2->mtx_st));

將qs2的狀態改變（termination）之後，發出signal喚醒等待此condition variable的thread，使其跳脫等待迴圈往下執行

:::success
延伸問題
2. 以 Thread Sanitizer 找出上述程式碼的 data race 並著手修正
3. 研讀 專題: lib/sort.c，提出上述程式碼效能改進之規劃並予以實作
:::

### γ - 2
### γ - 3