2025q1 Homework2 (quiz1+2)

contributed by < Denny0097 >

2025q1 第 1 週測驗題

Q1

{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

根據 function name，應要做到從 head 開始往下(&p->next)，直到 insert position 的迴圈，

又根據 function args , insert position 理應就是 before。
而為了完成走訪，使 AFTERTHOUGHT 為下一個 list_item_t 的 position，也就是 p 所指向的 l 值 (data type: list_item_t pointer) 所指向的 next 的 position ：&(*p)->next :

​​​​AAAA = &l->head
​​​​BBBB = before
​​​​CCCC = &(*p)->next

當找到 insert position 時，插入 item 並接上後續 list :

​​​​DDDD = (*p)->next

延伸問題:

解釋上方程式碼運作原理
在現有的程式碼基礎上，撰寫合併排序操作

Q2

Goal : remove_free_tree compeleted

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 (EEEE)
            pred_ptr = FFFF;
    //...

觀察前面宣告了 node_ptr 用來尋找需要被移除的 tree，宣告 pred_ptr 來指向該 tree - l's postion，
/* Find the in-order predecessor:
in-order : left -> parent -> right
build order 會如下：

因此當有兩子點時，會尋找左子點的右子點來作為 replacement：

​​​​EEEE : (*pred_ptr)->r
​​​​FFFF : &(*pred_ptr)->r

Q3

goal : rebuild_list_link

    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    /* GGGG */;

觀察 code 在做走訪每一個 node 並建立 prev, next 跟前後 node 的 link，走到最後應該要讓 head 跟 tail of list 相連：

​​​​GGGG : head->prev=prev

接著是 quick_sort 主體:

{
    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 = /* 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 = /* IIII */;
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

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

quick sort 會先選出一個 pivot，而該 quick sort 選 leftest node，也代表 int value 應該要存入該點的 value 讓後續走訪 node 去比較，而根據 data struct

#include "list.h"

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

要用到 list_entry 去讀取 contain 該 list 的 node_t 所儲存的 value：

​​​​HHHH : list_entry(pivot,node_t,list)->value

在開始走訪後，每次都要比較該點跟 pivot 的 value 來做 classify：

​​​​IIII : list_entry(n,node_t,list)->value

走訪完成，讓分類好的 pivot, left, right 的三個 list_head 依大小排入 begin[] :

​​​​JJJJ : pivot
​​​​KKKK : right

2025q1 第 2 週測驗題

Q1

goal : compelete stable list_quicksort function

{

    // ...
    
    pivot = AAAA(head, struct listitem, list);
    BBBB(&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
            CCCC(&item->list, &list_greater);
    }

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

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

依先前的先前的 quick sort 設計，令 pivot 為 head 指向的 leftest node：

​​​​AAAA : list_first_entry

並先將其分割出 list：

​​​​BBBB : list_del

走訪並 compare all list，分別放到 list_greater 跟 list_less 的 tail：

​​​​CCCC : list_move_tail

最後要先將 pivot 放回 head list 中， list_less(less than pivot) insert to front of pivot, list_greater(greater than pivot) inser to tail of pivot：

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

Q2

​​​​GGGG : 
​​​​HHHH : 
​​​​IIII : 
​​​​JJJJ : 
​​​​KKKK :
​​​​LLLL : 

Q3

Reference

• 2025q1 第 1 週測驗題
• 2025q1 第 2 週測驗題