linux2025-homework2

contributed by <Ian-Yen>

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

2025q1 第 1 週測驗題

測驗一

這邊先把答案填上：
AAAA : &l->head
BBBB : before
CCCC : &(*p)->next
DDDD : (*p)->next

解釋上方程式碼運作原理

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)
        ;
    *p = item;
    (*p)->next = before;
}

根據題目敘述，這個函式希望能夠把 item 放在 l 這個 list 的 before 之前。
而這個list最前面的節點就是 head 。

先把 p 指向 head

往後面一個一個找

找到 before 這時跳出迴圈。

把 item 塞進去。

把 before 接回去。
下面是如果 before 是 head 。

p 指向 head 然後跳出去。

item 變到前面了。
下面是如果 before 是 NULL。

p 找到最後一個的 next 也就是 NULL。

item 跑到最後一個了。

其他行為都是為定義的行為。

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

static int list_size(list_t *l)
{
    if(!l || !l->head)
        return 0;
    int ret = 1;
    for(struct list_item *h = l->head;h->next;h = h->next, ret++)
        ;
    return ret;
}

先補上裡面沒有的 list_size。

merge。

static inline list_item_t *merge(list_item_t *l, list_item_t *r)
{
    list_item_t *h = NULL;
    list_item_t **node = &h;
    for(;l && r;){
        if(l->value <= r->value) {
            *node = l;
            node = &l->next;
            l = l->next;
        } else {
            *node = r;
            node = &r->next;
            r = r->next;
        }
    }

    *node = l ? l : r;

    return h;
}

先判斷要先放 l 或是 r 的下一個值，然後使用到指標的指標來把他放進去，並先找到下一個值應該要被放在哪裡，一直循環直到某一邊空了，就直接把另一邊放進去然後回傳。

例外處理

如果 l 與 r 只有一個不是 NULL 或是兩個都是 NULL ，就會直接跳過迴圈，然後先找有沒有不是 NULL 的那個回傳，都是的話就隨便傳一個，我這邊用 l 判斷所以都是 NULL 就會回傳 r 。

sort

這邊原本要用 linux 核心風格的 list_sort ，但是單向鍊結串列沒有雙向鍊結串列的優點，少一邊不能串在一起，所以在這邊使用陣列來做，擷取他的想法，用 count 來判斷要合併幾個，雖然少了保證合併時大小的比值至多為 2 的優勢 ，但這樣可以不用在合併的時候多耗費

$O(lo{g}_{2}n)$ 的時間來把所有的東西往前移一格，且也能盡量作到合併時大小為 1:1 的優勢。

static inline void sort(list_t *l)
{
    if(!l || !l->head)
        return;

    list_item_t *stack[12] = {NULL};
    int count = 0, pos = 0;

    for (list_item_t *p = l->head, *safe;p; p = safe) {
        safe = p-> next;
        p->next = NULL;
        stack[pos++] = p;
        for (int tmp = count; tmp & 1; tmp >>= 1, pos--)
            stack[pos - 2] = merge(stack[pos - 1], stack[pos - 2]);
        count++;
    }

    for (;pos > 1 ;pos--)
        stack[pos - 2] = merge(stack[pos - 1], stack[pos - 2]);

    l->head = stack[0];
}

測驗二

這邊先把答案填上
EEEE : (*pred_ptr)->r
FFFF : &(*pred_ptr)->r

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

這邊的 remove_free_tree 是希望找到一個擁有大於等於 target 的 size 的所有位置裡面的最小值，然後把它從樹裡面移除，如果這棵數裡面所有的節點都比 target 的 size 小，就回傳NULL。

而因為這棵數是一棵 binary search tree 所以要找到目標位置，可以先看這個節點的 size 有沒有大於 target ，如果沒有的話，就往右邊的子節點去找，如果有的話，就先看看往左邊的子節點的 size 有沒有大於等於 target 要的 size ，有救往左邊的子節點找，沒有的話就回傳現在的節點。

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

要讓這邊的程式碼能動，只要補足 find_free_tree 即可。

block_t **find_free_tree(block_t **root, block_t *target)
{
    if(!(*root))
        return root;
    if((*root)->l && (*root)->l->size >= target->size)
        return find_free_tree(&(*root)->l, target);
    else if((*root)->size >= target->size)
        return root;
    else
        return find_free_tree(&(*root)->r, target);
}

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

待辦

測驗三

這邊先把答案填上：
GGGG : head->prev = prev
HHHH : list_entry(pivot, node_t, list)->value
IIII : list_entry(n, node_t, list)->value
JJJJ : pivot
KKKK : right

解釋上述程式碼運作原理

分析quick_sort實做細節

首先把第一個節點當作 pivot ，並用他的值來當作 value 從左邊往右邊找，當一個節點的值小於等於 value 就把它丟進 left 其他丟進 right。
然後把 left , pivot , right 分別照順序丟進 begin ， begin 裡面紀錄的值的值域可以很明顯的發現是排序後的 (begin[i]的最大值 < begin[i + 1]的最小值) 然後往右找，先把右邊的做好了，再做左邊。

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

從這篇裡面可以看到，他利用雙向 link_list 做了一個 tree_sort 作法是將 prev 與 next 拿去當成 l 與 r 然後用遞迴的方式再把它變回一個雙向 link_list 的形式。

static struct void traverse(struct list_head *root,
                            struct list_head *head)
{       
    struct list_head *work;

    if(!root){
        traverse(root->prev);
        work = root->next;
        list_add(root, head);
        traverse(work);
    }
}

static void tree_sort(struct list_head *head)
{       
    if(!head)
        return;
    struct list_head *result = NULL, **p = &result, *h = NULL, *t = NULL;
    element_t *pos, *safe;
    list_for_each_entry_safe (pos, safe, head, list) {
        p = &result;
        while(*p) {
            if(strcmp(pos->value, list_entry(*p, element_t, list)->value) >= 0)
                p = &(*p)->next;
            else
                p = &(*p)->prev;
        }
        
        *p = &pos->list;
        (*p)->next = NULL;
        (*p)->prev = NULL;
    }
    head->next = head;
    head->prev = head;
    traverse(result, head);
}

2025q1 第 2 週測驗題

測驗一

這邊先把答案填上：
AAAA : list_first_entry
BBBB : list_del
CCCC : list_move_tail
DDDD : list_add
EEEE : list_splice
FFFF : list_splice_tail

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

他的運作原理跟上面的測驗3很像，只是把迴圈的部份改成遞迴，這邊就不多贅述了。

把 list_move_tail 改成 list_move 不能滿足 stable sorting 的原因是因為這樣順序會顛倒，如果有兩個相同的 value 他們的順序會跟初始的不一樣。

改進 random_shuffle_array

用 hw1 提到過的 Fisher-Yates Shuffle 改進 random_shuffle_array

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        uint16_t j = i + get_unsigned16() % (len - i);
        uint16_t temp = operations[i];
        operations[i] = operations[j];
        operations[j] = temp;
    }
}

將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋

測驗二