2025q1 Homework2 (quiz1+2)

contributed by <JimmyChongz>

第一週課堂測驗

測驗一

解釋 list_insert_before 運作原理

老師說明
宣告一個指標 p，指向 head 指標 _[圖一]，透過 for 迴圈依序指向每一個節點的 next 指標 (也就是指向下一個 node 的指標)，直到 *p (指向下個節點的指標) 為 before 跳出回圈_[圖二]。此時，將 p 指向的指標 Node2->next（即*p ）改指向 item_[圖三]。
圖一：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

list_item_t **p = &l->head;

&l->head 等價 &( l->head ) ，-> 優先權較高。

圖二：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

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

&(*p)->next 等價 &((*p)->next)

圖三：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

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

如此一來，相比於下方版本的 list_insert_before，就可以少使用一個 prev 指標，且也無需判斷當 before == head 的情況，所以只要換個思路，就可以讓程式碼更精簡，這也許就是 Torvalds 口中的「品味」吧！

static inline void list_insert_before(list_t *l,
                                      list_item_t *before,
                                      list_item_t *item)
{
    list_item_t *prev = NULL;
    list_item_t *current;
    
    for (current = l->head; current != before; current = current->next)
        prev = current;
    
    if (!prev) {
        l->head = item;
        item->next = before;
    }
    else {
        prev->next = item;
        item->next = before;
    }
}

延伸問題：在現有的程式碼基礎上，撰寫合併排序操作。

程式碼

#include <stdio.h>

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

typedef struct {
    struct list_item *head;
} list_t;

void print(list_t *l) {
    list_item_t *cur = l->head;
    while (cur) {
        printf("%d->", cur->value);
        cur = cur->next;
    }
    printf("\n");
}

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;
    item->next = before;
}

static inline void merge(list_t *l1, list_t *l2) { // Sort in acsending order
    list_item_t **cur1 = &l1->head;
    list_item_t *cur2 = l2->head;
    while (*cur1 && cur2) {
        if ((*cur1)->value > cur2->value) { // 不用 '='，因為要確保 Stable Sorting
            list_item_t *to_insrt = cur2;
            cur2 = cur2->next;
            list_insert_before(l1, *(cur1), to_insrt);
        }
        else {
            cur1 = &(*cur1)->next;
        }
    }
    
    if (cur2) {
        *cur1 = cur2; // 接起來
    }
}

void mergeSort(list_t *l) { 
    if (!l || !l->head || !l->head->next) {
        return;
    }
    
    list_item_t *fast = l->head;
    list_item_t **slow = &l->head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = &(*slow)->next;
    }
    
    // cut
    list_t l2;
    l2.head = *slow;
    print(&l2);
    *slow = NULL;

    mergeSort(l);
    mergeSort(&l2);
    merge(l, &l2);
}

int main() {
    // 3, 5, 4, 1, 2
    list_t l1;
    list_item_t n1, n2, n3, n4, n5;
    n1.value = 3;
    n2.value = 5;
    n3.value = 4;
    n4.value = 1;
    n5.value = 2;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = NULL;

    l1.head = &n1;
    mergeSort(&l1);
    print(&l1);
}

失誤1：寫太快，在 print function 的迴圈中忘記更新 cur 指標。

失誤2：在 main function 製作鏈結串列時，忘記初始化最後一個節點 n5 的 `next`，導致迴圈無法終止。

失誤3 (mergeSort)：Stack Overflow，mergeSort 的快慢指標沒有切好，導致無限遞迴，如下 [圖四]、[圖五] 所示：

Code

void mergeSort(list_t *l) { 
    if (!l || !l->head || !l->head->next) {
        return;
    }
    
    list_item_t *fast = l->head;
    list_item_t *slow = l->head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    
    // cut
    list_t l2;
    l2.head = slow->next;
    print(&l2);
    slow->next = NULL;

    mergeSort(l);
    mergeSort(&l2);
    merge(l, &l2);
}

圖四：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

圖五：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

由上圖可知，根本沒切到，因此會發生無限遞迴。

將 slow 改用「間接指標」來修正，如下 [圖六]、[圖七]：

Code

void mergeSort(list_t *l) {
    if (!l || !l->head || !l->head->next) {
        return;
    }
    
    list_item_t *fast = l->head;
    list_item_t **slow = &l->head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = &(*slow)->next;
    }
    
    // cut
    list_t l2;
    l2.head = *slow;
    print(&l2);
    *slow = NULL;

    mergeSort(l);
    mergeSort(&l2);
    merge(l, &l2);
}

圖六：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

圖七：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

失誤4 (merge)：maintain prev 指標，導致最無法後將 l2 與 l1 連接。

Code

static inline void merge(list_t *l1, list_t *l2) {
    list_item_t *cur1 = l1->head;
    list_item_t *cur2 = l2->head;
    while (cur1 && cur2) {
        if (cur1->value > cur2->value) { // 不用 =，因為要確保 Stable Sorting
            list_item_t *to_insrt = cur2;
            cur2 = cur2->next;
            list_insert_before(l1, cur1, to_insrt);
        }
        else {
            cur1 = cur1->next;
        }
    }
    
    if (cur2) {
        // cur1 為 NULL，接不起來！！！
    }
}

將 cur1 改用「間接指標」修正：

Code

static inline void merge(list_t *l1, list_t *l2) {
    list_item_t **cur1 = &l1->head;
    list_item_t *cur2 = l2->head;
    while (*cur1 && cur2) {
        if ((*cur1)->value > cur2->value) { // 不用 =，因為要確保 Stable Sorting
            list_item_t *to_insrt = cur2;
            cur2 = cur2->next;
            list_insert_before(l1, *(cur1), to_insrt);
        }
        else {
            cur1 = &(*cur1)->next;
        }
    }
    
    if (cur2) {
        *cur1 = cur2; // 接起來
    }
}

測驗二：Find the in-order predecessor

老師說明
思路：就是用 while 迴圈找到 target 的 predecessor。其中 target 的 predecessor 即 target 在中序前一個節點，而 target 的 predecessor 其實就是 target 的左子樹之最大值，如下圖所示：(A ~ L 表示中序的追蹤順序，eg. E 的 predecessor 即為 D)

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r) {
    pred_ptr = &(*pred_ptr)->r;
}

延伸問題

完成 find_free_tree

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

完成 find_predecessor_free_tree

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    if (!node->l && !node->r)
    {
        return node;
    }
    else if (!node->l)
    {
        return node->r;
    }
    else
    {
        block_t *pred_ptr = node->l;
        while (pred_ptr->r)
            pred_ptr = pred_ptr->r;
        return pred_ptr;
    }
}

測試

完整程式碼

#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct block
{
    size_t size;
    struct block *l, *r;
} block_t;

block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);

/*
 * Structure representing a free memory block in the memory allocator.
 * The free tree is a binary search tree that organizes free blocks (of type block_t)
 * to efficiently locate a block of appropriate size during memory allocation.
 */
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)
            pred_ptr = &(*pred_ptr)->r;

        /* Verify the found predecessor using a helper function (for debugging).
         */
        block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
        assert(expected_pred == *pred_ptr);

        /* If the predecessor is the immediate left child. */
        if (*pred_ptr == (*node_ptr)->l)
        {
            block_t *old_right = (*node_ptr)->r;
            *node_ptr = *pred_ptr;      /* Replace target with its left child. */
            (*node_ptr)->r = old_right; /* Attach the original right subtree. */
            assert(*node_ptr != (*node_ptr)->l);
            assert(*node_ptr != (*node_ptr)->r);
        }
        else
        {
            /* The predecessor is deeper in the left subtree. */
            block_t *old_left = (*node_ptr)->l;
            block_t *old_right = (*node_ptr)->r;
            block_t *pred_node = *pred_ptr;
            /* Remove the predecessor from its original location. */
            remove_free_tree(&old_left, *pred_ptr);
            /* Replace the target node with the predecessor. */
            *node_ptr = pred_node;
            (*node_ptr)->l = old_left;
            (*node_ptr)->r = old_right;
            assert(*node_ptr != (*node_ptr)->l);
            assert(*node_ptr != (*node_ptr)->r);
        }
    }
    /* If the target node has one child (or none), simply splice it out. */
    else if ((*node_ptr)->l || (*node_ptr)->r)
    {
        block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;
    }
    else
    {
        /* No children: remove the node. */
        *node_ptr = NULL;
    }

    /* Clear the removed node's child pointers to avoid dangling references. */
    target->l = NULL;
    target->r = NULL;
}

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

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    if (!node->l && !node->r)
    {
        return node;
    }
    else if (!node->l)
    {
        return node->r;
    }
    else
    {
        block_t *pred_ptr = node->l;
        while (pred_ptr->r)
            pred_ptr = pred_ptr->r;
        return pred_ptr;
    }
}

block_t *insert_free_tree(block_t **root, size_t size)
{
    block_t *newNode = malloc(sizeof(block_t));
    newNode->l = NULL;
    newNode->r = NULL;
    newNode->size = size;
    if (!*root)
    {
        *root = newNode;
        return NULL;
    }
    block_t **cur = root;
    while (*cur)
    {
        if (newNode->size > (*cur)->size)
        {
            cur = &(*cur)->r;
        }
        else
        {
            cur = &(*cur)->l;
        }
    }
    *cur = newNode;
    return newNode;
}

block_t *new_free_tree(size_t size)
{
    block_t *root = malloc(sizeof(block_t));
    root->size = size;
    root->l = NULL;
    root->r = NULL;
    return root;
}

void free_free_tree(block_t *root)
{
    if (root == NULL) return;

    free_free_tree(root->l);
    free_free_tree(root->r);
    free(root);
}

void print_free_tree(block_t *root)
{
    if (root)
    {
        print_free_tree(root->l);
        printf("%ld->", root->size);
        print_free_tree(root->r);
    }
}

int main()
{
    block_t *root = new_free_tree('I');
    insert_free_tree(&root, 'G');
    insert_free_tree(&root, 'J');
    block_t *target = insert_free_tree(&root, 'E');
    insert_free_tree(&root, 'H');
    insert_free_tree(&root, 'L');
    insert_free_tree(&root, 'A');
    insert_free_tree(&root, 'F');
    insert_free_tree(&root, 'K');
    insert_free_tree(&root, 'C');
    insert_free_tree(&root, 'B');
    insert_free_tree(&root, 'D');
    print_free_tree(root);
    printf("\npredecessor: %ld\n", find_predecessor_free_tree(&root, target)->size);
    remove_free_tree(&root, target);
    print_free_tree(root);
    free_free_tree(root);
    return 0;
}

// output
65->66->67->68->69->70->71->72->73->74->75->76->
predecessor: 68
65->66->67->68->70->71->72->73->74->75->76->

測驗三

老師介紹 container_of
將程式拆解成四個部分：

Initialize

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level]; // 宣告兩個指標陣列 begin, end
    node_t *result = NULL, *left = NULL, *right = NULL;

    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) { // L, R 尚未交會
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

3.

        while (p) { // 用指標 p 遍歷 pivot 後的所有節點，若小於 pivot 則將該點置入 left，反之置入 right
            node_t *n = p;
            p = p->next; // CCCC
            list_add(n->value > value ? &right : &left, n);
        }

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

4.

            begin[i] = left; // i = 0
            end[i] = list_tail(&left); // DDDD
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = list_tail(&right); // EEEE

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

截圖 2025-02-21 上午11.02.36

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
}

截圖 2025-02-21 中午12.05.54

第二週課堂測驗

測驗一：實作 Quick Sort

作法：將傳入串列的第一個節點設為 pivot，再遍歷整條鏈結串列，將比 pivot 大的節點移動至 list_greater 中；比 pivot 小的節點移至 list_less 中，且要保持順序，遍歷完成後，再將 list_greater 和 list_less 做遞迴呼叫做排序，依此類推。最後，會得到兩條已排序好的鏈結串列以及一個 pivot 節點 (即傳入串列的第一個節點)，再將其合併成一條排序好的鏈結串列。

延伸問題：

探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting ?
- 因為使用 list_move 會改變原串列的排列順序。
  e.g. Input list: 3, 1, 4, 4*, 2, 5
  可以發現在 Round 3 時，4* 被移到 4 的前面，已經改變原串列的順序了，故 Unstable。
將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋
- TODO