2025q1 Homework2 (quiz1+2)

contributed by <Nsly0204>

第一周測驗題

測驗 1

解釋程式碼運作原理

先分析以下程式碼，可以發現 list_item 是一個類似 linux 核心風格的鍊結串列實作，list_item 類似於 list_head ，而list_t 類似於 *head。

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

typedef struct {
    struct list_item *head;
} list_t;

有了以上分析再結合指標的指標的概念，將 p 作為指向 (*node)->next 的指標，而 (*p) 指向 node ，由此可知當*p != before 時持續往下走訪，直到停止條件 (*p)->next == before 時，把 node 替換成 item 即為所求。

// 在指定節點之前插入新節點
static void list_insert_before(list_t *list, list_item_t *before, list_item_t *item)
{
    list_item_t **p;
    for (p = &list->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    (*p)->next = before;
}

在執行以下程式時出現 segmentation fault:














    int main() {
    list_t l;
    list_item_t *it1, *it2;
    list_item_t it3;

    list_item_t *ptr1;
    it1->value = 1;
    it2->value = 2;
    it1->next = it2;
    it2->next = NULL; 
    l.head = it1;
    ptr1 = it2;
    printf("l.head->value = %d \n", l.head->value);
}

利用 gdb 偵錯之後發現在第7行時發現錯誤

Program received signal SIGSEGV, Segmentation fault.
0x0000555555555159 in main () at dbl_ptr_test.c:21
21 it1->value = 1;

查閱 c11 規格書

§ 6.2.4 Storage durations of objects
A non-lvalue expression with structure or union type, where the structure or union
contains a member with array type (including, recursively, members of all contained
structures and unions) refers to an object with automatic storage duration and temporary
lifetime.36) Its lifetime begins when the expression is evaluated and its initial value is the
value of the expression. Its lifetime ends when the evaluation of the containing full
expression or full declarator ends. Any attempt to modify an object with temporary
lifetime results in undefined behavior.

思考後發現來目前所有指標變數 it1，it2 等都是只有 temporary lifetime 的指標，尚未被配置記憶體位置，觸發上述規格書末段的 undefined behavior ，須補上顯示記憶體配置即可正常執行。

it1 = (list_item_t *)malloc(sizeof(list_item_t));
it2 = (list_item_t *)malloc(sizeof(list_item_t));

在原本的quiz1中不用這樣寫的原因是 static list_t l; 為 file scope variable ，代表在編譯時在 .data 的部份就有靜態配置記憶體，故沒有發生 undefined behavier。

在現有的程式碼基礎上，撰寫合併排序操作

測驗 2

快速複習BST(Binary Search Tree)

解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

本次測驗嘗試用樹狀結構模擬記憶體管理，二元搜索樹(以下簡稱BST)的節點代表可用空間，函式 remove_free_tree 代表目前需要一個 target->size 大小的記憶體區塊，對應操作從 BST 中找到一個大於等於要求 (target) 的記憶體空間進行分配，被分配的空間會從管理閒置空間的 BST 中被刪除。

BST 的刪除通常會被分成三種情況：

刪除的節點是 leaf (沒有child)
- 直接刪除節點即可
刪除的節點只有一個 child
- 用唯一的子節點代替被刪除的節點
刪除的節點有兩個 child
- 繼承者為待刪除的節點的左子節點，直接取代。
- 繼承者在左子樹更深曾的地方，遞迴呼叫函式把繼任者從子樹刪除，直到

3 的情況因為需要把左右子數接回，我們需要找到 inorder predecessor 也就是左子樹中最右邊的點(小於root中最大的節點)取代被移除的節點所以我們進一步討論子節點取代被刪除節點的可能。

find_free_tree
考慮到如果目的是管理樹狀結構的記憶體區塊，樹狀結構本身會很深，外加 void remove_free_tree(block_t **root, block_t *target) 在每次遞迴都會呼叫此函式，若使用常規的遞迴寫法可能會有 stack overflow 發生，故這裡使用迭代實現。

block_t **find_free_tree(block_t **root, block_t *target)
{
    // find the minimum node >= target
    if (!(*root) || !root)
        return NULL;
    
    block_t **curr = root;
    while ((*curr))
    {
        if ((*curr)->size == target->size)
            break;
        if ((*curr)->l && (*curr)->l->size >= target->size)
            curr = &(*curr)->l;
        else 
            break;
    }
    return curr;
}

測試
這裡參考 rota1001 補上 insert_tree 和主函式，以亂序插入10個節點測試程式運作。

void insert_tree(block_t **root, size_t size)

void insert_tree(block_t **root, size_t size)
{
    if (!(*root)) {
        *root = malloc(sizeof(block_t));
        if(!(*root))
            return;
        (*root)->size = size;
        (*root)->l = (*root)->r = NULL;
        return;
    }
    if ((*root)->size < size)
        insert_tree(&(*root)->r, size);
    else if ((*root)->size > size)
        insert_tree(&(*root)->l, size);
    else {
        printf("Invalid input size");
        free(*root);
    }
}

int main ()

int main ()
{
    block_t *root = NULL;
    for (int i = 0; i < 10; i++) {
        insert_tree(&root, (i * 3) % 10);
    }
    print_tree(root);
    puts("");

    block_t temp;
    for (int i = 0; i < 10; i++)
    {
        temp.size = i;
        remove_free_tree(&root,&temp);
        print_tree(root);
        puts("");
    }
}

範例輸出(依序刪除0~9的節點)：

0 1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 
2 3 4 5 6 7 8 9 
3 4 5 6 7 8 9 
4 5 6 7 8 9 
5 6 7 8 9 
6 7 8 9 
7 8 9 
8 9 
9

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

測驗 3

解釋上述程式碼運作原理

研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

第二周測驗題

測驗 1

寫過 lab0 之後本次小考相對輕鬆，程式碼如下，引入 lab0 中的 list.h 即可編譯執行。

static void list_quicksort(struct list_head *head)

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);
    list_del(&pivot->list);

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

    // recursive solution
    list_quicksort(&list_less);
    list_quicksort(&list_greater);

    // combine the lists
    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}

解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting

Lehmer Random Number Generator(Lehmer RNG)
本次小考呼叫兩次 8 bits Lehmer RNG 合併實作出一個 16 bits 亂數，參考維基百科，其基本思想為：

X_{k + 1} = a \cdot X_{k} mod m

可以發現一個 Lehmer RNG 需要一個起始值

X_{0}

，倍數

a

，和同餘數

m

，其中

(a, m)

互質顯然為好的選擇，但因為用 mod 實作，我們可以預期此亂數產生器有以下缺陷：

關乎循環週期的
$m$ 不能太小，首先
$m$ 最好的選擇是質數，若為了運算方便設定成 2 的冪，參照費馬小定理
$a^{p} - a | p$ ，若 m 有 2 的因數循環週期至少為 m/4。
$m$ 應的
$a$ 也不能太小，舉例來說
$a = 2_{10} = 10_{2}$ ，不難發現
$a^{2} X_{0}, a^{3} X_{0}, a^{4} X_{0}$ 會有尾數不變情況。
無論
$a$ 如何選擇， bit 0 也就是奇偶性不會改變。

結論來說，

(a, m)

的選擇在 Lehmer RNG 中尤其重要，通常會強制選擇一個很大的質數，如

(7^{5}, 2^{3} 1 - 1)

或是

(2^{48}, 44485709377909)

，而本次小考利用三個 Lehmer RNG 互相做位元運算即是減少尾數循環週期短的的經典手段，而把高低 8 bits 分開產生進一步延長總體的循環週期，更多的數學分析考以參考 linear congruential generator。

若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
答案很簡單，在我們 top-down 遞迴拆分鏈結串列時默認元素排序是由左而右，其中 list_move 是從 head 插入，排序因此變成由右往左，無法滿足 stable sorting。

改進 random_shuffle_array

參考 lab0 參考使用 Fisher-Yates shuffle algorithm 實作達成：

覆蓋所有可能情況
各情況機率相等

即 unbiased shuffle。

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (; len > 1; len--) {
        uint16_t idx = get_unsigned16() % (len);
        if (idx == len-1)
            continue;
        uint16_t temp = operations[idx];
        operations[len-1] = operations[idx];
        operations[idx] = operations[temp];
    }
}

可以進一步學習 rota1001 使用 bit operator 的精簡 swap。

測驗 2

可以先參考從 √2 的存在談開平方根的快速運算和檢討第二週測驗題，了解 Digit-by-digit 方法如何只使用加減與位移運算來開平方根。
以下將用兩部分說明實作:

Digit-by-digit 的實作。
如何善用前一次迭代結果減少下一次迭代的計算量。

Digit-by-digit

⌊ \sqrt{N} ⌋

的實作可進一步分成以下步驟:

Count leading zeros: 因為是無號整數
$N$ 開平方根，利用
$\sqrt{N} \leq N$ 的特性，演算法可以直接從 MSB 的 1 開始往 LSB 迭代。
每次迭代判斷如果增加一個 bit 則那個 bit 應該是 1 or 0。
終止迭代的條件為做到最後的 LSB。

Count leading zeros 實作: clz2()

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

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)
        return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

根據題目敘述，在不斷把 x 拆分上下半部到每個半部只剩下兩位時，我們會直接用 magic[] 進行查表。

需要輸入迭代次數 c 的原因為，總共輸入有 32 bits ，在第三次遞迴呼叫，也就是第四次執行時， x 有 32/8 = 4 bits ，也就是 upper 和 lower 個剩下 2bits 時進行查表操作 return upper ? magic[upper] : 2 + magic[lower];，由此我們也知道 magic[index] 對應的值就是在最後 2 bits (index)下，對應的 0 個數。

至此我們清楚知道 uint32_t upper = (x >> (16 >> c)); 是藉由 16 除以

2^{c}

調整位移次數，但至於低位部分需要的 mask 需要不一樣的位移次數，參考下表可以簡單知道在不同迭代次數為了達成所需要 1 的個數，我們如何設計 mask[]。

c	x bits	mask
0	32	0b 1111 1111 1111 1111
1	16	0b 0000 0000 1111 1111
2	8	0b 0000 0000 0000 1111
3	4	0b 0000 0000 0000 0011

Digit-by-digit 實作: sqrti()

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;
    m = 1ULL << shift;

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

為什麼需要 int shift = (total_bits - 1 - clz64(x)) & ~1;

uint64_t sqrti_simple(uint64_t x) // contributed by [rota1001]
{
    uint64_t m;
    if (x <= 1)
        return x;
    
    int total_bits = 64;
    int shift = (total_bits - 1 - clz64(x)) & ~1;
    
    uint64_t p = 0;
    for(int i = (shift / 2); i >= 0; i--) {
        uint64_t b = (p << (i + 1)) + (1 << (2 * i));
        if (x >= b) {        // if X_m > Y_m
            x -= b;          // X_m -= Y_m
            p += (1 << i);   // P_m + one bit 1
        } 
    }
    return p;
}

一開始看這個程式碼的時候我不太理解為什麼 m 一定要位移偶數次，直到我參考 rota1001 的說明我才恍然大悟，原來真正的原因是我們發現

⌊ \sqrt{N} ⌋

的 first set one 一定出現在 N 的 first set one 一半的地方，如果

⌊ \sqrt{N} ⌋

的 first set one 不能被 2 整除，則無條件進位，等效於 shift 無條件捨去，可以參考 rota1001 大大所寫的 for(int i = (shift / 2); i >= 0; i--) ，覺得不直觀的也可以直接進行二進位乘法進行驗證。

接下來的部分相對直觀，我們首先定義:

\begin{aligned} N^{2} & \approx ( & b_{n} \times 2^{n} & + & b_{n - 1} \times 2^{n - 1} & + \dots & + & b_{i} \times 2^{i} & + \dots & + & b_{1} \times 2^{1} & + & b_{0} \times 2^{0})^{2} \\ = ( & a_{n} & + & a_{n - 1} & + \dots & + & a_{i} & + \dots & + & a_{1} & + & a_{0})^{2} \end{aligned}

p 代表
$P_{i} = b_{n} 2^{n} + . . . (共 i 位) = \sum_{k = i}^{n} a_{k}, n = shift / 2$ ，等價直到現在迭代次數 i 為止的
$⌊ \sqrt{N} ⌋$ ，注意到
$i$ 從 n 遞減，
$P_{i} = P_{i + 1} + a_{i}$ 。
b 代表
$Y_{i} = (P_{i})^{2} - P_{i + 1}^{2} = (P_{i + 1} + a_{i})^{2} - P_{i + 1}^{2} = (2 a_{i} P_{i + 1} + a_{i}^{2})$ ，代表下一次迭代若增加一 bit 1 會讓
$P_{i}^{2}$ 增加多少。
x 代表
$X_{i}$ ，代表計算道第 i 位的誤差， i 並非是迭代次數。

總結來說我們需要藉由比較計算誤差

X_{i} = N - P_{i}^{2}

和

Y_{i} = (2 a_{i} P_{i + 1} + a_{i}^{2})

的大小去決定我們的答案

P_{i} = P_{i} + a_{i}

的下一位

a_{i}

該是 0 或是

2^{i}

，若下一位是 0， remain error

X_{m}

不變，下一位是 1 ，則其計算方法如下:

X_{i} = N - P_{i}^{2} = N - (P_{i + 1}^{2} + 2 a_{i} P_{i + 1} + a_{i}^{2}) = X_{i + 1} - (2 a_{i} P_{i + 1} + a_{i}^{2}) = X_{i + 1} - Y_{i}

第二部分




















uint64_t sqrti_simple(uint64_t x)
{
    uint64_t m, y = 0;
    if (x <= 1)
        return x;
    
    int total_bits = 64;
    int shift = (total_bits - 1 - clz64(x)) & ~1;
    
    for(int i = (shift / 2); i >= 0; i--) {
        uint64_t b = y + (1 << (2 * i));
        y >>= 1;
        if (x >= b) {
            x -= b;
            y += (1 << (2 * i));
        } 
    }
    return y;
}

這裡已經透過去比較

X_{i}

Y_{i}

，巧妙的避開

P_{i}

平方的問題了，但為了近一步減少位移運算，我們發現 p 重複出現，透過代數代換，y = (p << (i + 1)) 得到:

在迴圈外 b = (p << (i + 1)) + (1 << (2 * i)); 替換成 b = y + (1 << (2 * i)); 默認
$b_{i} = 1$ 。
迴圈內 p += (1 << i) 替換 y += (y >> 1) + (1 << (2 * i))。

第二步的替換比較不直觀，本來以為需要複雜的數學推導，實際做過之後發現只是單純的把代數代換展開:

$y_{i} = P_{i} \times 2^{i}$ ，
$y_{i + 1} = P_{i + 1} \times 2^{i + 1}$ ， y = (p << (i + 1))，這邊讓容易搞混的地方是
$P_{i + 1}$ 是上一次迭代的值，這邊的
$y_{i}$ 指的是做完本次迭代的
$y$ 值，故在執行到 15 行之前都只有
$y_{i + 1}$ 。
$P_{i} = P_{i + 1} + 2^{i}$ ，
$2^{i} P_{i} = 2^{i} P_{i + 1} + 2^{2 i}$ ，
$y_{i} = y_{i + 1} 2^{- 1} + 2^{2 i}$ ，y += (y >> 1) + (1 << (2 * i))，至此完成計算到第
$i$ 位的整數該根號運算，答案為
$y_{i}$ 。
檢查起始條件
$y_{0} = p_{0} \times 2^{0}$ ，剛剛好不需要修正。

int main(){
    for (uint64_t i = 1; i < 100000000; i++)
    {
        double real = sqrt((double)i);
        assert(sqrti(i) == sqrti_simple(i) && (uint64_t)real == sqrti(i));
    }
    return 0;
}

實作小數開根號

從整數平方根到浮點數開平方根:導讀 Python's Square Root Algorithm。

測驗 3

本次測驗一樣填完答案後引入 lab0 的 list.h 即可編譯執行。

void map_deinit(map_t *map)
{
    if (!map)
        return;

    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
        struct hlist_head *head = &map->ht[i];
        for (struct hlist_node *p = head->first; p;) {
            struct hash_key *kn = container_of(p, struct hash_key, node);
            struct hlist_node *n = p;
            p = p->next;

            if (!n->pprev) /* unhashed */
                goto bail;

            struct hlist_node *next = n->next, **pprev = n->pprev;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

參考以上實作， linux 核心風格的實作特色在於善用其獨特的 container_of 函式之外，就是善用 pointer 和 indirect pointer。因此以下會著重對這兩部份進行討論。

由於 hash table 的實作只需要單向鏈結串列，因此反向的 prev 指標可以被我們善加利用。考慮我們在刪除單向鏈結串列節點時，一般的實作方法會需要一個額外的 pointer 去指向被刪除的節點或是被刪除的下一個節點

先思考一般的單向鏈結串列刪除特定節點會遇到的例外問題：

如果只有 list_head 則不刪除。
如果走訪的指標指向 NULL ，須當成例外狀況處理。

因此，我們把閒置的 *prev 指標改成間接指標 **pprev 直接存取上一個 node 所在的位址(實際上為上一個節點指向下一個節點的指標next）。

p 為走訪指標，n 指向 *p 的上一個節點，程式會逐步從頭走訪單向鏈結串列，走訪中止條件為 p=NULL ，刪除時我們全程只需要對 n 進行操作，先用變數紀錄兩個指標 n->next 和 n->pprev ，因為 pprev 指標存在的關係，我們只須判斷是否存在下一個需要接上的指標後即可 free 掉節點 n，如此我們發現：無論 n 是否是指向 NULL ，因為我們不需要對節點 n 本身進行操作 (只需要存下 *pprev 的指標，不需要依賴 n->next)，故可以直接對節點 n 進行刪除，達成程式碼的簡潔。

筆記

你所不知道的C語言：指標篇

// Answer
struct tag (*var[])()

cdecl> declare array of pointer to function returning struct tag

我們必須先了解以下兩者的差別：

// an array of pointer: *var[]
pointer_type *array_name [array_size];
pointer_type* array_name[array_size];

// a pointer to array
pointer_type (*array_name)[array_size];

an array of pointer：從宣告的形式 pointer_type * 就能看出是指標，而後面的 [array_size] 則代表有 array_size 這麼多個指標。
a pointer to array：先考慮 pointer_type array_name[array_size] 的基本陣列宣告後比較可以知道。這裡將 array_name 轉型成為指標，意思是說 array_name 從原本的陣列變成一個指向陣列的指標。
在了解 array of pointer 之後，參考 Function pointers in C ，我們可以發現這其實是與 pointer to array 一樣的轉型方式，將 functionPtr 轉形成指標的形式。

// a int type pointer to the function
int sum = (*functionPtr)(2, 3); // sum == 5

接下來參考論壇討論 Declare a C/C++ function returning pointer to array of integer pointers 根據裡面提供的程式並在 godbolt 驗證。

// argument int *
function(int *)
// a function with argument int *, returning pointer to   (*function(int *)) 
// a function with argument int *, returning pointer to array of 4
(*function(int *))[4]
// a function with argument int *, returning pointer to array of 4 integer pointers
int *(*function(int *))[4];

有了以上的知識我們觀察解答然後逐一拆解

*var[] // "var" is an array of pointer
(*var[])() // "var" is an array of pointer to function w/o parameter
struct tag (*var[])() // array of pointer to function returning struct tag

2025q1 Homework2 (quiz1+2)

第一周測驗題

測驗 1

測驗 2

測驗 3

第二周測驗題

測驗 1

改進 random_shuffle_array

測驗 2

實作小數開根號

測驗 3

筆記

你所不知道的C語言：指標篇

Read more

2025q1 Homework3 (kxo)

2025q1 Homework5 (assessment)

2025q1 Homework1 (lab0)

2025q1 Homework3 (kxo)