## 測驗 α
### important function
#### `st_first`

struct st_node *st_first(struct st_node *n)
{
    if (!st_left(n))
        return n;
    return st_first(st_left(n));
}

左子節點若為空，返回此節點。
佐子節點非為空，使用recursion返回左子節點為空之節點。

#### s`t_last`

struct st_node *st_last(struct st_node *n)
{
    if (!st_right(n))
        return n;
    return st_last(st_right(n));
}

與st_first為相反，不過*st_last相比不同之處為檢查右節點。

#### `st_rotate_left`

static inline void st_rotate_left(struct st_node *n)
{
    struct st_node *l = st_left(n), *p = st_parent(n);    //(1)

    st_parent(l) = st_parent(n);                          //(2)                    
    st_left(n) = st_right(l);                             //(3)
    st_parent(n) = l;                                     //(4)
    st_right(l) = n;

    if (p && st_left(p) == n)
        st_left(p) = l;
    else if (p)
        st_right(p) = l;

    if (st_left(n))
        st_lparent(n) = n;
}

>此Function理解參考下列網址https://josephjsf2.github.io/data/structure/and/algorithm/2019/06/22/avl-tree.html

:::danger
為何不對照你讀過的教科書？儘量研讀權威材料。
:notes: jserv
:::

需要st_rotate_left 場景:

step1 : function中(1)
儲存parent、left node，如下圖中紅色指標所示:

step2 : function中(2)
將l指向parent node :

step3 : function中(3)
將n的左節點指向l的右節點 :

step4 : function中(4)、(5)
分別為建立n指向l、l_right指向n如圖 :

#### st_rotate)right

與st_rotate_left互為相反操作。

#### st_balance

static inline int st_balance(struct st_node *n)
{
    int l = 0, r = 0;

    if (st_left(n))
        l = st_left(n)->hint + 1;

    if (st_right(n))
        r = st_right(n)->hint + 1;

    return l - r;
}

此func為st_update func.中判斷指定node是否平衡的func.
將左右node的hint + 1，代表左右node最大高度，
最後回傳 l - r，因此 > 1 代表向左傾斜、 < -1 代表向右傾斜。

>hint預存該subtree左右子樹最深長度

#### st_update

static inline void st_update(struct st_node **root, struct st_node *n)
{
    if (!n)
        return;

    int b = st_balance(n);
    int prev_hint = n->hint;
    struct st_node *p = st_parent(n);

    if (b < -1) {
        /* leaning to the right */
        if (n == *root)
            *root = st_right(n);
        st_rotate_right(n);
    }

    else if (b > 1) {
        /* leaning to the left */
        if (n == *root)
            *root = st_left(n);
        st_rotate_left(n);
    }

    n->hint = st_max_hint(n);
    if (n->hint == 0 || n->hint != prev_hint)
        st_update(root, p);
}

使用st_balance回傳值判斷n為root的sub tree是否需要平衡。
且中間兩處if 、if else處用於左旋、右旋轉操作。
值得一提的是更新後的高度為左右subtree中hint較大的一方再 + 1。

### AAAA、CCCC

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

        AAAA;
        BBBB;
        return;
    }

此為st_remove中的第一個if判斷式，有了將被刪除的點(del)之後，就是要選出一個node用於在del node被刪除之後替換使用。
所以上述程式碼中的

struct st_node *least = st_first(st_right(del));

是將del right node為subtree root時的最左下的node為整個tree中次大於del node value的node。因此least 用於替換del。

有了least之後，就可以call要用於替換node的function了，那第一個問題就在於:AAAA要使用st_replace_right還是st_replace_left呢?

端倪在於兩個function中替換的部分也就是st_replace_right的197、198行:

    st_parent(r) = p;
    st_left(r) = st_left(n);

st_replace_left的227、228行:

    st_parent(l) = p;
    st_right(l) = st_right(n);

兩者的第一步驟皆為將least指向預先存好欲替換del的母節點p，
然後第二步分兩部分:
1. replace_right : 將least指向n的right。
2. replace_left : 將least指向n的left。

由此可以得知用於替換的least(次大於n的node)應用於replace right替換、
most(次小於n的node)應用於replace left替換。

最後AAAA、CCCC相互相反、對應，前者使用replace_right、後者使用replace_left。

### BBBB、DDDD、EEEE
在跟替換完node後，避免Tree不平衡的問題就需要來平衡樹了。
在上面important function中有講到的st_update function，分別傳入root、當前刪除節點即可使用st_update平衡。

### FFFF、GGGG
FFFF、GGGG為treeint_dump中的程式碼，所以要先了解treeint_dump是用在做甚麼的function。

看到main.c中的433、434行:

    printf("[ After insertions ]\n");
    treeint_dump();

在看到老師給的範例說明可以得知treeint_dump()是在insert完node之後print出值的函式。

回到treeint_dump本身，以及老師給的範例之中發現到所有被print出來的值為由小至大，而BST中若使用inorder的順序print出node的話就會是依序由小至大排序的結果。
因此FFFF、GGGG會分別為inorder順序，也就是分別為:

n->left
n->right

達到inorder的順序。

## 測驗 β
此題為給定的 alignment 數值，輸出大於等於 alignment 的記憶體對齊地址。
思路:先從MMMM以外的部分開始著手解讀
以下code:

return (((sz + mask) / alignment) * alignment);

可以發現透過直接利用C語言整數的特性將小於alignment的部分清除，以去對其記憶體地址。

同時在MMMM前的if判斷式為:

if ((alignment & mask) == 0) {  /* power of two? */

線索在於註解內的 "power of two"?
二的冪有何特性?
例如8二進制為1000、這樣它的mask就會是0111；
或是16的二進制為10000、其mask就會是01111。
可以發現特性是除了最高位元其他都會是1，可以利用這一點來操作mask以讓小於alignment部分清除。

由上可以得知需要被保留的部分是大於alignment的部分，這點可以透過與mask取補數達到目的。
答案為 : (sz + mask) & ~mask;

## 測驗 γ
需要填入HHHH、JJJJ的兩個部分分別是HHHH:

    verify(pthread_mutex_lock(&qs->mtx_st));
    while (qs->st == ts_idle)
        verify(HHHH);
    verify(pthread_mutex_unlock(&qs->mtx_st));
    if (qs->st == ts_term) {
        return NULL;
    }
    assert(qs->st == ts_work);

    qsort_algo(qs);

JJJJ:

    verify(pthread_mutex_lock(&c->mtx_al));
    qs->st = ts_idle;
    c->idlethreads++;
    if (c->idlethreads == c->nthreads) {
        for (i = 0; i < c->nthreads; i++) {
            qs2 = &c->pool[i];
            if (qs2 == qs)
                continue;
            verify(pthread_mutex_lock(&qs2->mtx_st));
            qs2->st = ts_term;
            verify(JJJJ);
            verify(pthread_mutex_unlock(&qs2->mtx_st));
        }
        verify(pthread_mutex_unlock(&c->mtx_al));
        return NULL;
    }
    verify(pthread_mutex_unlock(&c->mtx_al));
    goto again;

### HHHH
從上述程式碼中可以看出一些端倪，在於while (qs->st == ts_idle) 這一loop。
HHHH所要填入的東西可以讓qs->ts == ts_idle一直為true，才會在此停留，同時有涉及verify function的都是與pthread相關操作的function才會需要驗證是否操作成功。
考量以上兩點答案應該是pthread_cond_wait，此function功能為用於堵塞當前thread，透過此方法才可以讓qs->st的值在被指定作業之前為ts_idle。

### JJJJ
JJJJ的線索在於JJJJ的上一行code:

qs2->st = ts_term;

也就是在做完之後會將qs2->st改為term。
在enum thread_state中有記述term為代表asked to terminate，要求改變qs2->st狀態。
所以做完工作之後最直接的想法就是釋放當前mutex lock已讓其他的thread才可以持有mutex，然而這部分已經有被寫下。
因此答案只剩下跟HHHH相互對應的，一為卡住thread、一為釋放thread，所以JJJJ應填入pthread_cond_signal以喚醒其他正在pthread_cond_wait上的執行緒。