2025q1 Homework2 (quiz1+2)

contributed by < LambertWSJ >

quiz1 - 指標的指標

按照 list_insert_before 的描述，將 item 插入到串列 l 的 before 前，給定的實做使用指標的指標 p，經過 for 迴圈完後，dereference p 並指派為 item，表示將節點換成 item，item 還需要將下個節點指向 before，因為 item 可能是從別的串列來的，而不是單一節點，因此 item->next 指向的是原串列的節點，而不是串列 l 的 before。

*p = before;
item->next = before;

for 迴圈的目的是要從串列 l 找出 before，因此 p 要指向 l 的開頭，並透過 &(address of) 運算子，依據 C99 6.5.3.1:3

The unary & operator yields the address of its operand. If the operand has type ‘‘type’’,
the result has type ‘‘pointer to type’’

轉換成指標的指標，才會和 p 是同型別，迴圈的終止條件是對 p 做 dereference 取得節點的位址和 before 做比較，不是 before 的話就更新 p 到下個節點。離開迴圈後 p 會指向 before，在由上個段落所描述的操作，就能將 item 插入到 before 之前。

for(p = &l->head; *p != before; p = &(*p)->next)

實做 Merge sort

先實做簡單的遞迴版 Merge sort，函式宣告如下

list_item_t *list_merge_sort(list_item_t *head);

傳入 list 的 head 會較容易撰寫，不用另外處理不同型別的問題，專注在節點上即可。Merge Sort 拆分為分割和合併兩個階段，分割的策略使用快慢指標，遞迴地處理串列的左半邊和右半邊，將左半邊的串列分割為單一節點，單一節點是排序好的，可以和其他排序好的子串列或單一節點合併，當左半邊都集中合併完之後，會將同一處理過程換到右半邊操作，當左右半邊的子串列都排序完後，再合併成排序好的串列。

list_item_t *list_merge_sort(list_item_t *head) {
    if (!head || !head->next)
        return head;

    list_item_t *slow = head, *fast;
    for (fast = head->next; fast && fast->next; fast = fast->next->next)
        slow = slow->next;

    list_item_t *mid = slow->next;
    slow->next = NULL;
    list_item_t *left = list_merge_sort(head);
    list_item_t *right = list_merge_sort(mid);
    return merge_two_lists(left, right);
}

合併函式 merge_two_lists 應用指標的指標，這樣就不需要額外配置記憶體或是 dummy 節點來當 head，只需要指標 list 作為合併完的串列開頭，再用指標的指標 indir 指向 list，當 indir 解參考就能存取到 list，把要合併的節點指派給 list，串列的開頭就有了，要更新下個節點的話只要將 indir 指向到下一個節點即可。

static list_item_t *merge_two_lists(list_item_t *l1, list_item_t *l2) {
    list_item_t *list = NULL, **indir = &list;
    list_item_t **node;
    for (node = NULL; l1 && l2; *node = (*node)->next) {
        node = l1->value < l2->value ? &l1 : &l2;
        *indir = *node;
        indir = &(*indir)->next;
    }
    /* ... */
}

node 的用途是指向下個要合併的節點，比較 l1 和 l2 的值後，紀錄下個要合併的節點，依據 C99 規格書 6.5.15 的註腳

A conditional expression does not yield an lvalue

&(l1->value < l2->value ? l1 : l2) 這樣寫沒辦法讓 address of(&) 取得地址，因為三元表達式回傳的是 value 而非帶有地址的 lvaue，雖然不能夠回傳 lvalue，但可以回傳已經是地址的 value，即 &l1 或 &l2。

有了下個要合併的節點，需要對 node 透過解參考才能存取到它，並指派給 indir 合併，合併完的節點同樣也是透過解參考來達成 *node = (*node)->next，就會將已經合併完的節點更新到下一個。

當迴圈到達終止條件 l1 && l2 離開時，表示其中一個串列還沒合併完，需要將其合併到 indir 上，才算是完成。這裡可以應用一個小技巧。依據 C99 7.18.1.4:1, 使用 uintptr_t 將串列的地址轉為無號整數來操作

The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:
uintptr_t

l1 和 l2 其中一個是合併完的串列，地址就會是 NULL, NULL 的地址是零，零和其他數值做 or 操作，都會是原來的數值，所以將兩個串列的地址做 or 得到的地址就是還沒合併完的串列，再轉形成 list_item_t * 並指派給 *indir 就完成合併了

list_item_t *merge_two_lists(list_item_t *l1, list_item_t *l2) {
    /* ... */
    *indir = (list_item_t *) ((uintptr_t) l1 | (uintptr_t) l2);
    return list;
}

quiz1 - 基於樹的記憶體配置器

程式碼解說

使用間接指標改寫

Free Tree 提供的函式介面都使用指標的指標作為root 的型態，實做完一般的版本後，開始思考如何用間接指標改寫，讓程式碼更精簡又有品味。

block_insert_free_tree

插入節點到二元樹可依據左小又大的規則在樹上找空位來插入節點，若不使用間接指標，按造參考書上通常會完成下面的實做。

需要較多程式碼完成，而且還要檢查邊界條件。

void block_insert_free_tree(block_t **root, block_t *node) {
    if(!node) return;
    if(!*root && node) {
        *root = node;
        return;
    }
    block_t *proot = *root;
    while (proot) {
        if (proot->size < node->size) {
            if(!proot->r) {
                proot->r = node;
                break;
            }
            proot = proot->r;
        } else {
            if(!proot->l) {
                proot->l = node;
                break;
            }
            proot = proot->l;
        }
    }
}

如果用上了間接指標的話，可以省略邊界條件的檢查還能大幅簡化程式碼。

使用 indir 指向 root，進到 for 迴圈的判斷條件就可以檢查傳進來的 root 是不是一棵空的二元樹，itr 是輔助用的指標，避免每次從 root 上的節點取值都要先將 indir 解參考，和 node 比較後，依據左小右大的規則決定下個要走訪的節點。依據你所不知道的 C 語言: linked list 和非連續記憶體的說明，三元表達式不會回傳 lvalue，所以只能分別回傳 &itr->l 和 &itr->r 給 indir。

改寫後的實做，看起來像是用間接指標實做鍊結串列的插入。

void block_insert_free_tree(block_t **root, block_t *node)
{
    block_t **indir = root;
    for(block_t *itr; *indir;) {
        itr = *indir;
        indir = itr->size > node->size? &itr->l: &itr->r;
    }
    *indir = node;
}

find_predecessor_free_tree

BST 的 predecessor 是走訪順序中的前一個節點，也就是比 node 還小的最大節點，如果 node 有左子樹，那就是找左子樹的最大值，如果 node 沒有左子樹，則需要找它的前一個。

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    block_t *pred = NULL;
    for(block_t **indir = root, *itr; *indir;) {
        itr = *indir;
        if(itr->size < node->size) {
            pred = itr;
            indir = &itr->r;
        } else
            indir = &itr->l;
    }
    return pred;
}

上面的實做可利用 , comma operator 再進一步精簡，但看起來就像是為簡化而簡化。

依據 C99 6.5.17 - Comma operator

The left operand of a comma operator is evaluated as a void expression; there is a
sequence point after its evaluation. Then the right operand is evaluated; the result has its type and value.94)

， 的左邊會是 expression，右邊才會求值(evaluated)並返回數值和型態，和三元表達式一樣，不會返回 lvalue。

94. A comma operator does not yield an lvalue.

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    block_t *pred = NULL;

    for (block_t **indir = root, *itr; *indir;) {
        itr = *indir;
        indir = itr->size < node->size? (pred = itr, &itr->r): &itr->l;
    }
    return pred;
}

不正確的實做方式

有些範例會提供下面的程式碼，告訴你不需要 root 就可以求出 node 的 predecessor，但這個實做如果傳入的 node 是葉子或是葉子的前一個節點就會是錯誤的結果。

block_t *find_predecessor_free_tree_v2(block_t **root, block_t *node)
{
    if(!node) return node;

    block_t *pred = node->l? node->l: node;
    while (pred->r)
        pred = pred->r;

    return pred;
}

find_free_tree

依據 BST 左小右大的規則，還有其自我相似性，可以用遞迴寫出很直覺的搜尋演算法，但是遞迴需要較大的空間儲存每次呼叫自己的 stack frame，還有終止條件要判斷，如果利用指標的指標實做迭代版 BST 搜尋，就沒有這兩項劣勢了

block_t **find_free_tree_recur(block_t **root, block_t *target) {
    block_t *node = *root;
    if(!node)
        return root;
    if (node == target)
        return root;
    else
        return node->size < target->size?
            find_free_tree_recur(&node->r, target):
            find_free_tree_recur(&node->l, target);
    return NULL;
}

改用間接指標後，程式碼大幅的簡化了，也不需要一進函式就判斷 root 是否存在。

block_t **find_free_tree(block_t **root, block_t *target) {
    for(block_t **indir = root, *itr; *indir; ) {
        itr = *indir;
        if (itr->size == target->size)
            return indir;
        indir = itr->size > target->size? &itr->l: &itr->r;
    }
    return NULL;
}

比較 memory allocator

實做中，會比較 freelist 和 freetree

quiz1 - Optimized QuickSor

quiz2 - List QuickSort

穩定和不穩定排序 - 節點插入位置改變排序性質

Note

觀念釐清：不穩定排序不是指排序演算法在不同測試案例會有不同的時間複雜度，而是原始資料中，已排序好的資料順序被改變。

使用 kernel list API 版本實做的 quicksort，只要修改下方分配節點到 list_less 和 list_greater 的程式片段，就會造成不穩定排序的結果。

static void list_quicksort(struct list_head *head) {
    /* ... */
    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 */
    }
    /* ... */
}

若 CCCC 是 list_move 的話，節點會插入到 head 的下一個節點，相當於 insert head 的操作，會破壞原始資料的順序，造成不穩定排序。

舉例來說，串列有 3 個節點的值都是 0xac 的話，只有地址不一樣，如果是穩定排序的話，就應該維持串列原本位置的順序。

如果按造

$nod{e}_{addr1}$ ~

$nod{e}_{addr3}$ 的順序，呼叫 list_move 將上述節點存入到 list_greater，結果會像下圖一樣，即便內含值一樣，但是順序卻不一樣，所以會導致不穩定排序

上述操作若改成 list_move_tail 的話，則相當於將節點做 insert tail，不會改變原本的順序，所以是穩定排序

這是不容易注意到的細節，就算測試通過，也沒發現這個問題，僅僅只是換個 API 就會造成不穩定排序，日後實做相關串列排序的演算法應考慮到插入位置是否會造成不穩定排序。

quiz2 - sqrti

clz2

題目給定分治法的 clz，參數 x 和 c 分別為 32 位元無號輸入數值和 leading zero 的位置，為方便說明，leading zero 簡寫為 LZ。

因為是拆成 upper 和 lower 各 16 bit 來做，等最後 2 bit 再來判斷位置，而 LZ 只會在其中一個，依據最後 2 bit 作為判斷條件，16 向右位移 3 就會剩下 2 bit。

c 和判斷 upper/lower 的長度，如下表，acc 表示從 c 等於 0 累加 16 >> c

c	upper/lower	acc(16 >> c)
0	16	16
1	8	24
2	4	28
3	2	30

unsigned clz2(uint32_t x, int c) {
    /* ... */
    if (c == 3)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

雖然看到 mask 和 magic 已經知道 c 很可能是 3，但是這樣子判斷欠缺合理性，mask 和 magic 再多塞幾個數值在陣列裡面的話，就被騙到了。

因為每次都要少一半長度的判斷，下次 lower 的遞迴則是 (16 >> (c)) + clz2(lower, c + 1)，遞迴函式執行到終止條件時會逐步返回，過程中累加 16 >> c 到 30。

若 LZ 在 upper，則當 c == 3 會剩下兩個 bit，可以用來推測 magic，此時的 upper 是 x 的第 30 和 31 個 bit，

$x_{[31:30]}$ 表示 x 的第 30 到 31 個 bit，用 2 進位表示數值，由小到大整理成下表，LZ 也代表 magic 的數值

$x_{[31:30]}$ or $x_{[1:0]}$	LZ
${00}_2$	2
${01}_2$	1
${10}_2$	0
${11}_2$	0

有了 magic 可以判斷 KKKK 應為 2。

從每次要從 upper 或 lower 判斷 LZ 位置來看，mask 的 GGGG 應為 14，這樣在 c 為 3 時，判斷的長度才會是 2

static const int mask[] = {0, 8, 12, GGGG};
unsigned clz2(uint32_t x, int c) {
    /* ... */
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    /* ... */
}

sqrti

ToDo：本文說明可能有誤，釐清詞彙中
帶入和代入
除和除以

實做完 clz 後，嘗試實做基於 2 進位的 digit-by-digit method 的整數平方根，研讀講義和 Wiki 後，可能是篇幅問題所以部份公式沒有推導，直接給出來，藉此機會來練習推導看看。

假設

$N^2$ 可以用二進位系統取得逼近解

$$N^2=(a_n+a_{n-1}+\cdots +a_1+a_0{)}^2$$

其中

$a_m$ 可能是

$2^m$ 或是

$0$，計算

$2^n$ 到

$2^0$ 並累加起來，會得到平方根

$P_m$

$$P_m=a_n+a_{n-1}+\cdots +a_m$$

要找出

$a_m$ 是

$2^m$ 或

$0$，先將

$P_m$ 改寫成另一種等價的形式

$$P_m=P_{m+1}+a_m$$

過去看到數學公式通常都是下一項等於前一項做運算得出來，這裡的

$P_m$ 則是相反，用下一項

$P_{m+1}$ 運算得出來，把

$P_m$ 帶數字展開來就知道為什麼了，令

$m=4,n=7$

$$\begin{array}{rl}& P_4=a7+a6+a5+a4\\ & P_5=a7+a6+a5\end{array}$$

可以看出

$P_m$ 和

$P_{m+1}$ 少了一個

$a_m$。

如果

$P_m^2$ 沒有超過

$N^2$，則

$a_m=2^m$，表示

$a_m$ 是包含在平方和

$P_m$ 裡面的係數，不會因為加上

$a_m$ 就超過

$N^2$，反之如果超過的話，就不屬於

$P_m$，

$a_m=0$

$$a_m=\{\begin{array}{ll}{2}^m,& \text{if }{P}_m^2\le N^2\\ 0,& otherwise\end{array}$$

找出每一項

$a_m$ 並累加，就可以得到整數平方根

$P_m$。

為避免每一次計算

$a_m$ 都要對

$P_m$ 做平方，可以儲存兩數之差

$X_m=N^2-P_m^2$，並逐步更新

$X_m$，為此要推導下一項

$X_{m+1}$

$$X_{m+1}=N^2-P_{m+1}^2$$

$P_{m+1}^2$ 可以展開成

$(P_m-a_m{)}^2$ 並帶入差平方的公式

$$\begin{array}{rl}{X}_{m+1}& =N^2-(P_m-a_m{)}^2\\ & =N^2-(P_m^2-2P_m{a}_m+a_m^2)\\ & =N^2-P_m^2+2P_m{a}_m-a_m^2\end{array}$$

其中

$X_m=N^2-P_m^2$ 以及

$P_m=P_{m+1}+a_m$，代入展開後的式子

$$\begin{array}{rl}{X}_{m+1}& =N^2-P_m^2+2P_m{a}_m-a_m^2\\ & =X_m+2(P_{m+1}+a_m)a_m-a_m^2\\ & =X_m+2P_{m+1}{a}_m+2a_m^2-a_m^2\\ & =X_m+2P_{m+1}{a}_m+a_m^2\end{array}$$

得出

$X_{m+1}=X_m+2P_{m+1}{a}_m+a_m^2$。

令

$Y_m=2P_{m+1}{a}_m+a_m^2$ 得

$X_m=X_{m+1}-Y_m$，探討

$a_m$ 不為零時的情況，並將

$Y_m$ 拆成

$c_m$ 和

$d_m$

$$\begin{array}{rl}{c}_m& =2P_{m+1}{a}_m=P_{m+1}{2}^{m+1}\\ d_m& =(2^m{)}^2\end{array}$$

$$Y_m=\{\begin{array}{ll}{c}_m+d_m& \text{if }{a}_m=2^m\\ 0& \text{if }{a}_m=0\end{array}$$

$c_m$ 和

$d_m$ 的更新如下

$$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=P_{m+1}{2}^m+a_m{2}^m$$

其中

$a_m$ 可能是

$0$ 或是

$2^m$，如果

$a_m=2^m$，帶入

$c_{m-1}$

$$c_{m-1}=P_{m+1}{a}^m+a_m^2=\frac{c_m}{2}+d_m$$
若

$a_m=0$ 代入

$c_{m-1}$

$$\begin{array}{rl}{c}_{m-1}& =(P_{m+1}+a_m)2^m\\ & =P_{m+1}{2}^m\\ & =\frac{c_m}{2}\end{array}$$

故得知更新

$c_m$ 和

$d_m$ 的公式如下

$$\begin{array}{rl}{c}_{m-1}& =\{\begin{array}{ll}\frac{c_m}{2}+d_m& \text{if }{a}_m=2^m\\ \frac{c_m}{2}& \text{if }{a}_m=0\end{array}\\ d_{m-1}& =(2^{m-1}{)}^2=\frac{d_m}{4}\end{array}$$

公式都推導出來後，回頭看程式碼，先回答為什麼要取出 msb 而且還要是 4 的冪?

$P_m$ 是

$a_n$ 累加到

$a_m$，

$a_m$ 不確定是多少，有幾個，但至少會有一個，那就是最高項

$a_n$，這也是為什麼

$P_m$ 要從

$a_n$ 開始累加到

$a_m$。

初始值

$P_n=a_n=2^n$,

$P_n$ 要滿足

$P_n^2\le N^2$, 則

$P_n^2=(2^n{)}^2=4^n$，因此初始值必須是最接近

$N$ 的 4 的冪。

uint64_t sqrti(uint64_t x) {
    /* ... */
    int shift = (total_bits - 1 - clz64(x)) & -2;
    m = 1ULL << shift;
    /* ... */
}

有了

$a_n$ 就能按照更新公式來迭代求得逼近解

$P_m$ 剩下的

$a_m$。將

$a_n$ 代入並計算初始

$Y_m=c_m+d_m$

$$\begin{array}{rl}{Y}_m& =c_m+d_m\\ & =P_{m+1}{2}^{m+1}+(2^m{)}^2\\ & =(P_m-2^n)2^{n+1}+(2^n{)}^2\end{array}$$
初始值

$P_m=P_n=a_n$ 代回上式

$$\begin{array}{rl}{Y}_m& =(P_m-2^n)2^{n+1}+(2^n{)}^2\\ & =(2^n-2^n)2^{n+1}+(2^n{)}^2\\ c_m& =0,d_m=a_n^2\end{array}$$
因為

$c_m=0$，

$d_m$ 可在迴圈中算出來，所以一開始 y 才設為 0，y 也可以一開始就設為 m 但是迴圈要另外處理。

uint64_t sqrti(uint64_t x) {
    uint64_t m, y = 0; /* y = c_m */
    int shift = (total_bits - 1 - clz64(x)) & -2;
    m = 1ULL << shift; /* m = d_m = a_n^2 */
    /* ... */
}

初始的

$Y_m$ 算好之後，就可以準備更新

$c_m$ 和

$d_m$ 了，更新公式如下

$$\begin{array}{rl}{c}_{m-1}& =\{\begin{array}{ll}\frac{c_m}{2}+d_m& \text{if }{a}_m=2^m\\ \frac{c_m}{2}& \text{if }{a}_m=0\end{array}\\ d_{m-1}& =(2^{m-1}{)}^2=\frac{d_m}{4}\end{array}$$
無論

$a_m$ 是否為零，

$c_m$ 都要除 2，

$d_m$ 每次都要除 4，若

$a_m$ 存在，則

$c_{m-1}$ 要再加上

$d_m$，而

$d_m$ 每一輪都要除 4

$a_m$ 是否存在，要藉由

$X_{m+1}\ge Y_m$ 判斷，如果存在的話，

$X_m$ 也要更新，公式如下

$$X_m=X_{m+1}-Y_m$$

這裡看上去不直覺，為什麼又是用下一項 (

$X_{m+1}$) 來更新？

嘗試推導

$X_{m+1}$ 來解釋

$$X_{m+1}=N^2-P_{m+1}^2=N^2-(P_m-a_m{)}^2$$
因為是從最高位來計算，令

$m=n$，會得出

$X_{m+1}=N^2$

$$X_{m+1}=N^2-(a_n-a_n{)}^2=N^2$$

當

$m=n$ 時，

$X_{m+1}$ 剛剛好是

$N^2$，此外

$m$ 所代表的意義是位數，因此當

$X_{m+1}\ge Y_m$ 時，更新

$X_m$ 的時候是用前一次高位的

$X_{m+1}$ 減去

$Y_m$。

uint64_t sqrti(uint64_t x) {
    /* ... */
    while (m) {
        uint64_t b = y + m; /* Y_m = c_m + d_m */
        y >>= 1;
        if (x >= b) { /* check a_m exist     */
            x -= b;   /* X_m = X_{m-1} - Y_m */
            y += m;   /* c_{m-1} += d_m      */
        }
        m >>= 2;
    }
    return y;
}

quiz2 - Kernel Hash Table