HackMD
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
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
2025q1 第 2 週測驗題
EEEE: list_splice()
FFFF: list_splice_tail()
MMMM: ~1ULL
1
2
