2025q1 Homework2 (quiz1+2)

contributed by < otischung >

Quiz 1

測驗 1-1

補完之程式碼如下所示

typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

/**
 * Inserts a new item into the list before a specified item.
 * 
 * This function traverses the list to locate the position immediately before the item pointed to by @before and inserts @item in that position.
 * The time complexity is O(n), where n is the number of stepsneeded to reach @before fromthe head of the list.
 * 
 * Parameters:
 * @l       : Pointer to the list.
 * @ before : Pointer to the item before which the new item should be inseted.
 *            - If @before is the head of the list, the new item is inserted at the front.
 *            - If @before is NULL, the new item is appended to the end of the list.
 *            - In all other cases, behavior is undefined if @before does not belong to @l.
 * @item    : The new list item to be inserted.
 */
static inline void list_insert_before(list_t *l,
                                      list_item_t *before,
                                      list_item_t *item)
{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)  // AAAA, BBBB, CCCC
        ;
    *p = item;
    item->next = before;  // DDDD
}

由於 l->head 與 list_item_t *before 都是 struct list_item *，因此我們只需要紀錄這些指標的位址，透過 dereference 即可操作該記憶體內容。

因此，我們的操作步驟如下：

1. 從頭開始，鏈結串列是由 l->head 所紀錄，其型態是 list_item_t *，故其位址為 &l->head，其型態是 list_item_t **。
2. 搜尋 *p 是否等於目標 before，若相同則下一步，若不同則將 *p 的下一個 (*p)->next 的位址紀錄起來 &(*p)->next。
3. 將 *p 所指之處放入 item，並將 item->next 記成 before。

我們分析以下三種情況

1. 插入在鏈結串列之頭
   這種情況的話，p = &l->head，因此，執行插入的時候，*p = l->head = item，再把 item->next 紀錄成 before，也就是之前的頭。
2. 插入在鏈結串列之中間部份
3. 插入在鏈結串列之尾
   這種情況的話，before = NULL，所以最後 *p = NULL，**p 指向最後一個元素的位址，因此將最後一個元素的 next，也就是 *p，指向 item，並將 item 的下一個指向 NULL，而此時 before = NULL，因此不違反原先的設定。

由此證明，以上程式碼具有一般性，不須做其他額外處理。

測驗 1-2

補完之程式碼如下所示

void remove_free_tree(block_t **root, block_t *target)
{
    /* Locate the pointer to the target node in the tree. */
    block_t **node_ptr = find_free_tree(root, target);

    /* If the target node has two children, we need to find a replacement. */
    if ((*node_ptr)->l && (*node_ptr)->r) {
        /* Find the in-order predecessor:
         * This is the rightmost node in the left subtree.
         */
        block_t **pred_ptr = &(*node_ptr)->l;
        while ((*pred_ptr)->r)  // EEEE
            pred_ptr = &(*pred_ptr)->r;  // FFFF
        ...
    }
    ...
}

要找到最右邊的 node，就從左邊一路掃到右邊就可以了。

測驗 1-3

補完之程式碼如下所示

static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    head->prev = prev;  // GGGG
}

void quick_sort(struct list_head *head)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    struct list_head *begin[max_level];
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    begin[0] = list->next;
    list->prev->next = NULL;
    while (i >= 0) {
        struct list_head *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
            struct list_head *pivot = L;
            value = list_entry(pivot, node_t, list)->value  // HHHH
            struct list_head *p = pivot->next;
            pivot->next = NULL; /* break the list */

            while (p) {
                struct list_head *n = p;
                p = p->next;
                int n_value = list_entry(n, node_t, list)->value;  // IIII
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

            begin[i] = left;
            begin[i + 1] = pivot;  // JJJJ
            begin[i + 2] = right;  // KKKK
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }
    }
    list->next = result;
    rebuild_list_link(list);
}

首先，rebuild_list_link() 只在 quick_sort() 最後一行執行，而觀察 quick_sort() 只有處理 next，並未處理 prev，因此判定此 rebuild_list_link() 是為了補上 prev。

因此，我們定義 prev 為第一個元素，node 為第二個元素，透過雙向環狀 linked-list 依序處理，即可推斷 GGGG 為何。

HHHH 與 IIII 皆是利用 container_of macro 取得 node_t 的位址，再取得該 node 的值。

JJJJ 與 KKKK 皆為圖例所示，依序為 left, pivot, 與 right。

Quiz 2

測驗 2-1

補完之程式碼如下所示

static void list_quicksort(struct list_head *head)
{
    struct list_head list_less, list_greater;
    struct listitem *pivot;
    struct listitem *item = NULL, *is = NULL;

    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    pivot = list_first_entry(head, struct listitem, list);   // AAAA
    list_del(&pivot->list);  // BBBB

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            list_move_tail(&item->list, &list_greater);  // CCCC
    }

    list_quicksort(&list_less);
    list_quicksort(&list_greater);

    list_add(&pivot->list, head);  // DDDD
    list_splice(&list_less, head);  // EEEE
    list_splice_tail(&list_greater, head);  // FFFF
}

其實對於 AAAA 來說，選擇 pivot 可以是任意的，不過在選項中，可以使用 container_of 得出「一個」 node 的 macro，只有 list_first_entry，那麼他就是唯一解。

與測驗 1-3 不同的是，這裡使用遞迴的方式實作，額外準備兩個 list 做遞迴。

取出 pivot 後，將 pivot 移出 list，之後將每個 node 與 pivot 作比較，分別移入兩個 lists。

至此，原本的 head 已經沒有東西了。

遞迴解完之後，先把 pivot 放回 head，再把左邊 list 插入頭段，最後把右側 list 插入尾段。

測驗 2-2

補完之程式碼如下所示

static const int mask[] = {0, 8, 12, 14};  // {0, 8, 12, GGGG}
static const int magic[] = {2, 1, 0, 0};  // {HHHH, 1, 0, IIII}

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == 3)  // JJJJ
        return upper ? magic[upper] : 2 + magic[lower];  // KKKK
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);  // LLLL
}

#define clz32(x) clz2(x, 0)

這個實作是使用遞迴呼叫求解 counting leading zero，直到剩下 2 bits 為止。

每次都將目前的位元平分成 upper 與 lower

c	upper/lower 位元數
0	16
1	8
2	4
3	2

• 當 upper 非 0，則繼續尋找 upper，忽略 lower。
• 當 upper 為 0，則繼續尋找 lower，將目前 upper 的位元數加進來。

當 c == 3 時，則 upper 與 lower 只剩下 0b00, 0b01, 0b10, 0b11 三種可能，而這些數字的開頭分別有 {2, 1, 0, 0} 個 0，因此，當 c == 3 時，

• 當 upper 非 0，則返回 upper 有幾個 0。
• 當 upper 為 0，則返回 lower 有幾個 0，加上 upper 的部分，有 2 個 0。

接下來，我們補完開平方根的程式碼

uint64_t sqrti(uint64_t x)
{
    uint64_t m, y = 0;
    if (x <= 1)
        return x;

    int total_bits = 64;

    /* clz64(x) returns the count of leading zeros in x.
     * (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
     * Rounding that index down to an even number ensures our starting m is a
     * power of 4.
     */
    int shift = (total_bits - 1 - clz64(x)) & ~1;  // MMMM
    m = 1ULL << shift;

    while (m) {
        uint64_t b = y + m;
        y >>= 1;  // NNNN
        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= 2;  // PPPP
    }
    return y;
}

我們的目標是要找到一個最大的數字

$y$ 使得

$y^2\le x$。

我們知道對於所有正整數與 0 可以以二進位表示，即

$$y=a_n{2}^n+a_{n-1}{2}^{n-1}+...+a_1{2}^1+a_0{2}^0$$

對於所有

$n$ 為正整數或 0，

$a_n$ 為 0 或 1。

因此，對於所有

$y$，找到最大的

$n$ 使得

$(2^n{)}^2\le x$，由此開始進行二分搜尋法，繼續尋找

$n-1$,

$n-2$, …,

$1$,

$0$，即可得到

$$y^2=(a_n{2}^n+a_{n-1}{2}^{n-1}+...+a_1{2}^1+a_0{2}^0{)}^2\le x$$

由於我們總是從

$(2^n{)}^2=4^n$ 開始搜尋，因此 shift 必定是偶數，而又因為我們的起始項不超過

$x$，因此我們總是向下取偶數，這等同於將 LSB mask 成 0，即 & ~1。

接下來，我們看一下

$x=170$ 的例子，170 在二進位表示成 0xAA，因此 shift == 6，此時我們有

$m=(2^3{)}^2$,

$y=0$,

$b=y+m=(2^3{)}^2$，

$$64=(2^3{)}^2\le 170$$

由於

$64\le 170$，所以

$y=2^3$。

接下來，我們搜尋

$(2^3+2^2{)}^2\le 170$ 是否正確

$$144=(2^3+2^2{)}^2\le 170$$

$$196=(2^3+2^2+2^1{)}^2>170$$

$$169=(2^3+2^2+2^0{)}^2\le 170$$

我們將等式做展開

$$\begin{array}{rl}144=(2^3+2^2{)}^2& \le 170\\ 144=(2^3{)}^2+(2(2^3)+(2^2))(2^2)& \le 170\\ 144-(2^3{)}^2=2(2^3)(2^2)+(2^2{)}^2& \le 170-(2^3{)}^2\\ 80=2(2^3)(2^2)+(2^2{)}^2& \le 106\\ 196=(2^3+2^2+2^1{)}^2& >170\\ 196=(2^3+2^2{)}^2+2(2^3+2^2)2^1+(2^1{)}^2& >170\\ 169=(2^3+2^2+2^0{)}^2& \le 170\end{array}$$