linux2023: Eddie-064 - HW1

quiz0
linux2023-summer

測驗 α - 1 : 解釋程式碼運作原理

S-tree 相關函式

• st_first : 以遞迴的方式找到 S-tree 最左邊的節點，而因 S-tree 為一種 BST，因此最左邊的節點也是整個 S-tree 的最小值。

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

    return st_first(st_left(n));
}

• st_last : 以遞迴的方式找到 S-tree 最右邊的節點，也是整個 S-tree 的最大值。

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

    return st_last(st_right(n));
}

• st_rotate_left : 當 AVL tree 左半邊不平衡時，需要做的 rotate 操作。

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_balance : 計算 AVL tree 是否平衡，正常值為 -1, 0, 1。

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

• st_max_hint : 計算 n 節點的最大高度。

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

• st_update : 判斷以 n 節點為首的子樹是否平衡，如不平衡則做 rotate。最後判斷子樹高度是否有改變，如果改變則執行 st_update(root, p) 判斷與 Sibling 是否平衡。

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_insert : 插入 n 節點至指定的 d 位置，確認 s-tree 是否平衡。

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_replace_right : 在二元搜尋樹中刪除節點時需要選取子樹的一個節點做替換，這個函式是在替換節點為右子樹的情境下，實作以 r 節點替換 n 節點。

static inline void st_replace_right(struct st_node *n, struct st_node *r)
{
    struct st_node *p = st_parent(n), *rp = st_parent(r);

    if (st_left(rp) == r) {
        st_left(rp) = st_right(r);
        if (st_right(r))
            st_rparent(r) = rp;
    }

    if (st_parent(rp) == n)
        st_parent(rp) = r;

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

    if (st_right(n) != r) {
        st_right(r) = st_right(n);
        st_rparent(n) = r;
    }

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

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

• st_remove : 實作 s-tree 移除的函式。
  • AAAA : 當被移除節點 del 存在右節點，尋找右子樹最小值替換以符合 BST 特性，而找到替換節點後還需要處理 node link 細節，因此填空答案應為 st_replace_right(del, least)。
  • BBBB : 因為移除的節點是 least，所以應該更新原先 least 的 parent 才是最小的 cost，但因為 link 已經被刪去，所以次處應填 st_update(root, st_right(least)) 或 st_update(root, st_first(least))。
  • CCCC : 找到替換節點後還需要處理 node link 細節，因此填空答案應為 st_replace_left(del, most)。
  • DDDD : 因為移除的節點是 most，所以應該更新原先 most 的 parent 才是最小的 cost，但因為 link 已經被刪去，所以次處應填 st_update(root, st_left(most)) 或 st_update(root, st_last(most))。
  • EEEE : n 節點為 leaf node 移除自己後，需要確保 s-tree 為平衡，因此要執行 st_update(root, parent)。

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

Test program

• __treeint_dump : 這裡要將 s-tree 中所有節點的大小依升序排列輸出至終端機，而二元樹的 in-order Traversal 正好能夠實現這個功能。因此 FFFF 為應先尋訪的 st_left(n)，而 GGGG 為最後尋訪的 st_right(n)。

/* 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
}

測驗 α - 2

測驗 β - 1 : 說明程式碼原理

• 這個函式計算記憶體對齊後應該分配的空間，將對齊大小分為 2 的冪和非 2 的冪，2 的冪可以透過位元運算降低計算的 cost。
  • (alignment & mask) == 0 判斷當對齊大小為 2 的冪時計算，可以透過 & 將餘數清空，但因為計算後不能小於原本使用的 sz 大小，所以要先加上 alignment - 1，因此 MMMM 應該填 (sz + mask)&(~mask)。

#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 : 說明程式碼原理

下方包含 qsort_mt 和 qsort_thread 函式。

• 下方程式碼的 18 至 32 行為初始化 mutex 及創建 threads，並設置 qs 的 status 為 idle。
• HHHH : 建立多個 qsort_thread 的執行緒後，一開始會在狀態 idle 等待被觸發，因為 qs->stat 為多個執行緒共用的資料，因此更動時需要 mutex 機制保護。而如果要控制執行順序則需要透過 condvar 的機制，所以 HHHH 應為 pthread_cond_wait(&qs->cond_st, &qs->mtx_st) 等待 idle 狀態被修改後觸發 condvar。
• JJJJ : 下方程式碼的 116 至 119 行，因為修改了 qs2 的狀態因此需要透過 pthread_cond_signal(&qs2->cond_st) 通知。

/* The multithreaded qsort public interface */
void qsort_mt(void *a,
              size_t n,
              size_t es,
              cmp_t *cmp,
              int maxthreads,
              int forkelem)
{
    struct qsort *qs;
    struct common c;
    int i, islot;
    bool bailout = true;

    if (n < forkelem)
        goto f1;
    errno = 0;
    /* Try to initialize the resources we need. */
    if (pthread_mutex_init(&c.mtx_al, NULL) != 0)
        goto f1;
    if ((c.pool = calloc(maxthreads, sizeof(struct qsort))) == NULL)
        goto f2;
    for (islot = 0; islot < maxthreads; islot++) {
        qs = &c.pool[islot];
        if (pthread_mutex_init(&qs->mtx_st, NULL) != 0)
            goto f3;
        if (pthread_cond_init(&qs->cond_st, NULL) != 0) {
            verify(pthread_mutex_destroy(&qs->mtx_st));
            goto f3;
        }
        qs->st = ts_idle;
        qs->common = &c;
        if (pthread_create(&qs->id, NULL, qsort_thread, qs) != 0) {
            verify(pthread_mutex_destroy(&qs->mtx_st));
            verify(pthread_cond_destroy(&qs->cond_st));
            goto f3;
        }
    }

    /* All systems go. */
    bailout = false;

    /* Initialize common elements. */
    c.swaptype = ((char *) a - (char *) 0) % sizeof(long) || es % sizeof(long)
                     ? 2
                 : es == sizeof(long) ? 0
                                      : 1;
    c.es = es;
    c.cmp = cmp;
    c.forkelem = forkelem;
    c.idlethreads = c.nthreads = maxthreads;

    /* Hand out the first work batch. */
    qs = &c.pool[0];
    verify(pthread_mutex_lock(&qs->mtx_st));
    qs->a = a;
    qs->n = n;
    qs->st = ts_work;
    c.idlethreads--;
    verify(pthread_cond_signal(&qs->cond_st));
    verify(pthread_mutex_unlock(&qs->mtx_st));

    /* Wait for all threads to finish, and free acquired resources. */
f3:
    for (i = 0; i < islot; i++) {
        qs = &c.pool[i];
        if (bailout) {
            verify(pthread_mutex_lock(&qs->mtx_st));
            qs->st = ts_term;
            verify(pthread_cond_signal(&qs->cond_st));
            verify(pthread_mutex_unlock(&qs->mtx_st));
        }
        verify(pthread_join(qs->id, NULL));
        verify(pthread_mutex_destroy(&qs->mtx_st));
        verify(pthread_cond_destroy(&qs->cond_st));
    }
    free(c.pool);
f2:
    verify(pthread_mutex_destroy(&c.mtx_al));
    if (bailout) {
        fprintf(stderr, "Resource initialization failed; bailing out.\n");
    f1:
        qsort(a, n, es, cmp);
    }
}

/* Thread-callable quicksort. */
static void *qsort_thread(void *p)
{
    struct qsort *qs, *qs2;
    int i;
    struct common *c;

    qs = p;
    c = qs->common;
again:
    /* Wait for work to be allocated. */
    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);

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