linux2023:ab749

測驗 α

移除節點的程式碼：

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; //st_replace_right(del, least)
        BBBB; //st_update(root, least)
        return;
    }

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

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

由小到大印出的程式碼：

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

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

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

    __treeint_dump(GGGG, depth + 1); //st_right(n)
}

1.解釋
2.特別跟 AVL tree 和 red-black tree 相比
3.設計效能評比程式，探討上述程式碼和 red-black tree 效能落差

測驗 β

#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; //sz&(~mask)     
    }
    return (((sz + mask) / alignment) * alignment);
}

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

測驗 γ

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

回饋表單 https://docs.google.com/forms/d/e/1FAIpQLSchjBeTO5la96o1rMkUsYcTqPAAWdNqr1oHraqHkUiCHtraVw/viewform
題目 https://hackmd.io/@sysprog/linux2023-summer-quiz0