2025q1 Homework2 (quiz1+2)

contributed by < chensheep >

2025q1 第 1 週測驗題

測驗 1

參考 list_insert_before 說明如上圖，是要在給定的 before 前加入新的 item。

考慮以下情形，目前 list 中有三個 items。

假設目標是在 1 之前加入一個新的 item 4 ，可以觀察到需要修改部份標注成紅色。

因此這邊拿一個指針 p 指到要修改的記憶體位置，如下圖，這樣可以同時擁有要修改的位置 p 與指到當前需被比較的 *p。

觀察 list_insert_before 函式

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

第 5 行對應流程如下

第 6 行對應流程如下，所以 DDDD 為 item->next

回到 list_insert_before 函式第 3 行， p 一開始指到 list 存放指到第一個 item 指標的位置，因此為 AAAA &l->head。
*p 表示當前的 item 當當前的 item 為目標 before 則離開迴圈，因此 BBBB 為 before。
最後要更新 p 為當前 item 存放指向下一個節點指標的位址，所以 CCCC 為 &(*p)->next。

延伸問題

解釋上方程式碼運作原理

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

測驗 2

針對本段程式碼

/* 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;

閱讀註解可知目標是找到左子樹中最右邊的節點。
所以當此節點沒有右邊的節點即為目標，因此 EEEE 為 (*pred_ptr)->r。
當此節點有右節點時，更新 pred_ptr 為當前節點指向右邊節點的位址，因此 FFFF 為 &(*pred_ptr)->r。

嘗試編譯 memory-allocators

sudo apt  install cmake
cmake -S memory-allocators -B build
cmake --build build 

測驗 3

題目中 rebuild_list_link 的目的為給定一個 list 重新將這個 list 中每個節點的 prev 指針重建指向正確的節點。
因為在進行 quick_sort 排序時，我們忽略維護每個節點的 prev 指針，所以排序完成後需對此函式 list 重建 prev 指針。
rebuild_list_link 函式中使用 node 與 prev 去紀錄當前的節點與其前一個節點，以此每次將 node 的 prev 更新，並移動到下一個節點。
最後 node 為 NULL 時離開迴圈，此時 prev 紀錄最後一個節點，因此將其 next 指向 head，並將 head 的 prev 指向其。
即 GGGG 為 head->prev=prev。

接著分析 quick_sort 函式，begin[i] 為目前要排序的 list。
假如 L 等於 R 表示 0 個或 1 個節點，代表排序完成，將這個成果放到 result list 中。
反之代表這個 list 未完成排列，取出其第一個節點作為 pivot，
在透過 list_entry 取出值，因此 HHHH 為 list_entry(pivot,node_t,list)->value。
接著將剩餘的節點依序跟 pivot 的值相比，小於的放到 left 大於的放到 right 相反的放到 left。
分別紀錄這三個 list 到 begin[i]，begin[i+1]，begin[i+2]，因此 JJJJ 與 KKKK 分別為 pivot 與 right。
將 i + 2 表示我們先選擇 begin[i+2] 為下輪要排序的 list。

以下進行簡單的演示

9 5 8 6 1 10

0 1 6 8 5
1 9
2 10

result 9 10

0
1 1
2 5 8 6

0
1 1
2
3 5
4 6 8

0
1 1
2
3 5
4
5 6
6 8

1 5 6 8 9 10

GGGG 為有效 C 語言表示式，不含 ; 或 , 字元
HHHH 和 IIII 包含 list_entry 巨集，不含 ; 字元
JJJJ 和 KKKK 為有效 C 語言表示式，不含 ; 或 , 字元
以最精簡的方式撰寫，不包含空白

list_entry(head->next, node_t, list)->value;

GGGG: head->prev=prev
HHHH: list_entry(pivot,node_t,list)->value
IIII: list_entry(n,node_t,list)->value
JJJJ: pivot
KKKK: right

延伸問題:

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

針對 rebuild_list_link

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

2025q1 第 2 週測驗題

測驗 1

快速排序函式的原型宣告如下

static void list_quicksort(struct list_head *head);

在 list_quicksort 中本次透過 recursive 方式實現。
在函式 list_quicksort 我們宣告 list_less 與 list_greater 分別用來放置比 pivot 小與大的節點。
如果傳入的 list 為空的或是只有一個節點表示排序完畢。
反之進行排序，這邊取出第一個節點，可以透過 list_first_entry ，因此 AAAA 為 list_first_entry。
取出第一個節點後將其從 list 移除，因此 BBBB 為 list_del。
接著針對剩餘的節點與 pivo 的值進行比較，較小者加入到 list_less 中，反之加入到 list_greater 中。
這邊 CCCC 為 list_move_tail 主要是考量到為符合 stable sorting ，所以先被比較到的節點，其應該放置在 list_greater 前面，所以後來被比較到的節點 list_move_tail 放置到 list_greater 的尾端，可以維持其原本的相對位置。
最後將排序完成的 pivot->list，list_less 與 list_greater 重新放回 head 中。
因為 pivot 為單一節點，所以使用 list_add 即可，因此 DDDD 為 list_add。
list_less 與 list_greater 中有可能有多個節點，因此要透過其他方式。
list_less list 需要放置到 head 的前端，因此透過 list_splice 可以將一個 list 的所有節點放到另一個 list 的前端，EEEE 為 list_splice。
list_less list 需要放置到 head 的後端，因此透過 list_splice_tail 可以將一個 list 的所有節點放到另一個 list 的後端，FFFF 為 list_splice_tail。
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 在內排序實作的效能表現並充分解釋

MMMM: ~1ULL
1
2

測驗 2

測驗 3

對應到

find_key 函式實做如下

static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *head = &(map->ht)[hash(key, AAAA)];
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

hash 的 bit 大小在初始化 map_t 結構時即已經帶入，因此從 map_t 結構中可以取出 AAAA 為 map->bits。
相對應的 BBBB 同樣為 map->bits。
新增操作： (部分遮蔽)

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, BBBB)];
    struct hlist_node *n = &kn->node, *first = h->first;

    n->next = first;
    if (first)
        CCCC = &n->next;
    h->first = n;
    DDDD = &h->first;
}

這邊的目標是將新增的 hlist_node 放置到這個 list 的最前方。
因此首先將新增的 node 其 next 指向目前的 first，進一步判斷 first 存在的話，需將期 pprev 修改為新增的 node 的 next 位址。
因此 CCCC 為 first->pprev。
另外需將新增的 node 其 pprev 指到 hlist_head.first 因此 DDDD 為 n->pprev。
接著觀察釋放記憶體的操作:

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 = EEEE;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

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

Reference