---
# System prepended metadata

title: 'linux2023:tintinjian12999'

---

# linux2023:tintinjian12999
contributed by < [tintinjian12999](https://github.com/tintinjian12999) >

## 測驗 𝛼 - 1 
### 結構體
#### st_node
``` c
struct st_node {
    short hint;
    struct st_node *parent;
    struct st_node *left, *right;
};
```
parent 為指向親代節點的指標，left, right 分別為指向左子樹與右子樹的指標，hint 為用來決定是否需要平衡的參數。
![](https://hackmd.io/_uploads/BJ_ITQ-hh.png)
#### st_root
```c
struct st_root {
    struct st_node *root;
};
```
root 為指向整棵樹的根節點的指標。
![](https://hackmd.io/_uploads/Byr9AmWh3.png)
### 型別
```c
enum st_dir { LEFT, RIGHT };
```
用來讓程式變得更有可讀性，而非用布林或數字決定是左或右。
### 巨集
```c
#define st_root(r) (r->root)
#define st_left(n) (n->left)
#define st_right(n) (n->right)
#define st_rparent(n) (st_right(n)->parent)
#define st_lparent(n) (st_left(n)->parent)
#define st_parent(n) (n->parent)
```
st_root : 取出根節點的指標
st_left : 取出左子節點的指標
st_right : 取出右子節點的指標
st_rparent : 取出右子節點之親代節點的指標
st_lparent : 取出左子節點之親代節點的指標
st_parent : 取出當前節點之親代節點的指標
### 函式
#### st_first
```c
struct st_node *st_first(struct st_node *n)
{
    if (!st_left(n))
        return n;

    return st_first(st_left(n));
}
```
找出整棵樹的最小節點
![](https://hackmd.io/_uploads/BJKSBBb22.png)

#### st_last
```c
struct st_node *st_last(struct st_node *n)
{
    if (!st_right(n))
        return n;

    return st_last(st_right(n));
}
```
找出整棵樹最大的節點 (這裡節點 14 的右子樹為 NULL)
![](https://hackmd.io/_uploads/SkdV6D7n3.png)
#### st_rotate_left
```c
static inline void st_rotate_left(struct st_node *n)
{
    struct st_node *l = st_left(n), *p = st_parent(n);

    st_parent(l) = st_parent(n);
    st_left(n) = st_right(l);
    st_parent(n) = l;
    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;
}
```
對當前節點作左旋
#### st_rotate_right
```c
static inline void st_rotate_right(struct st_node *n)
{
    struct st_node *r = st_right(n), *p = st_parent(n);

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

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

    if (st_right(n))
        st_rparent(n) = n;
}
```
對當前節點做右旋
#### st_balance
```c
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;
}
```
計算當前節點的 balance factor
#### st_max_hint
```c
static inline int st_max_hint(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 ? l : r;
}
```
回傳左節點與右節點中 hint 較高的一方(相當於 AVL tree 中的樹高)
### st_update
```c
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);
}
```
對當前節點做 balancing
#### st_insert
```c
void st_insert(struct st_node **root,
               struct st_node *p,
               struct st_node *n,
               enum st_dir d)
{
    if (d == LEFT)
        st_left(p) = n;
    else
        st_right(p) = n;

    st_parent(n) = p;
    st_update(root, n);
}
```
根據 st_dir 的值將新的節點插入當前節點的左節點或右節點並做 balancing
#### st_replace_right
#### st_replace_left
#### st_remove
```c 
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;

        st_replace_right(del, least); //AAAA
        st_update(root, st_right(least)); //BBBB
        return;
    }

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

        st_replace_left(del, most); //CCCC
        st_update(root, st_left(most)); //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;

    st_update(root, parent); //EEEE
}
```
當要移除的節點有右子樹時，要將該節點替換為右子樹的最小節點 (為確保替換後該節點右子樹裡的值都比該節點大)，且因為已經更動過右子樹內的節點，因此需要對其作 update ，如果沒有右子樹的話則替換為左子樹裡的最大節點，並對左子樹做 update ，如果要被移除的節點沒有任何的子節點的話， 則可以將其直接移除並對該節點的親代節點做 update。

#### __treeint_dump
```c
/* ascending order */
static void __treeint_dump(struct st_node *n, int depth)
{
    if (!n)
        return;

    __treeint_dump(st_left(n), depth + 1); //FFFF

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

    __treeint_dump(st_right(n), depth + 1); //GGGG
}
```
走訪並印出左子樹與右子樹的值
## 測驗 𝛽 - 1
考慮給定的範例
```
align_up(120, 4) = 120
align_up(121, 4) = 124
align_up(122, 4) = 124
align_up(123, 4) = 124
```
從以上不難觀察到其實 align_up 所做的是將 sz 除以 alignment 的商取上高斯並再乘以 alignment，也就是 $$ \lceil\frac{sz}{alignment}\rceil * alignment $$
上高斯的部分可以透過 $$ceilVal = (a + b - 1) / b$$獲得，因此整個式子可以寫成 $$ (\frac{sz + (alignment - 1)}{alignment}) * alignment$$
因為這裡的 alignment 為 2 的冪且 mask = alignment - 1，我們可以進一步改寫為
$$(sz + mask) >> \log2(alignment)) << \log2(alignment)$$ 透過觀察$$>> \log2(alignment)) << \log2(alignment)$$ 的操作 (以 123, alignment = 4 為例)
$$ (123 + 3) = 1111110_2 \\
1111110 >> 2 = 11111\\
11111 << 2 = 1111100
$$
可以看到作用為消除最後的 ```log2(alignment)``` 個 bit ，而此操作可以改寫為  
```(sz + mask) & alignment -> (sz + mask) & ~mask```
```c
#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 (sz + mask) & ~mask; //MMMM
    }
    return (((sz + mask) / alignment) * alignment); //如果 alignment 不是 2 的冪則不能化簡
}
```

## 測驗 𝛾 - 1
參考 [並行程式設計: POSIX Thread](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fposix-threads) 裡有關 condition variables 的用法，此處的 HHHH 應為 
```c
pthread_cond_wait(&qs->cond_st)
```
JJJJ 為
```c
pthread_cond_signal(&qs->cond_st, &qs->mtx_st)
```

:::warning
為何？
:notes: jserv
:::