HackMD
2025q1 Homework2(quiz1+2)
contributed by <leonnig>
Quiz 1
測驗1
static inline void list_insert_before(list_t *l, list__item_t *before, list_item_t *item)
{
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
;
*p = item;
DDDD = before;
}
此 function 的功能是將item插入到 list 中 before指向的節點的位置。
如果要達成這個功能，勢必要從頭 traverse 過 list 以找到該插入的位置，可以從程式碼中發現，宣告了一個p pointer to pointer 去做 traverse，p一開始要指向的要是一個指標，並且是從開頭的位置，所以AAAA要是整個串列的起點，也就是 &l->head。
而中止條件*p != BBBB，可以看出對p做 value of，又功能的要求是要插入到before的位置，因此可以判斷當*p指向的不為before時都要繼續前進，BBBB = before。
每次前進時，指標的指標p會指向下一個節點中的next的位置，這樣在搜尋時可以利用 address of 直接取得要插入的目標位置，CCCC = &(*p)->next。
找到插入的位置後，*p = item就是將before的前一點的next指向item，最後必須將item與後面的list連接起來，所以DDDD = item->next。
延伸問題: 解釋程式碼運作原理
其實整段程式碼就是在對 list 的一些操作做測試。
先來說明以下 function 功能
my_assert
#define my_assert(test, message) \
do { \
if (!(test)) \
return message; \
} while (0)
這段程式在判斷給定的 test 是否通過，若未通過則回傳一段訊息通知。
list_reset
static list_t *list_reset(void)
{
for (size_t i = 0; i < N; i++) {
items[i].value = i;
items[i].next = NULL;
}
l.head = NULL;
return &l;
}
這段程式將一條 list 內的連接都斷開，也就是將list_item_t的next都設為 NULL，head也設為 NULL。
而在 test_list 則是最主要做測試的部分，其中又分為3段測試。
首先對 list 做 reset，然後去測試看 list 是否有被正常 reset 成功。
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
並且從 l->head 插入 N 個數，測試從開頭插入的操作。
並且插入方式如下:
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
可以發現他的第二個 argement 給的是l.head，代表說他的迴圈會馬上停在第一個位置，而item插入的位置就都會在最前面，也就是數字越大的節點會在越前面。
然後再去檢查插入完成後的 list 大小是否為 N，並且逐一檢查每個節點的 vlaue 是否有符合順序。
size_t k = N - 1;
list_item_t *cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k--;
cur = cur->next;
}
再來是測試從 list 尾部插入的操作
終止條件改成了NULL，也就是會往後找到最後一個節點的next為止，將item插入。
所以數字越大的節點會出現在越後方。
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
然後執行跟前面一樣的測試。
最後則是做 list 的 reset，完成後再做從 list 尾部的插入。
補完 list_size 功能
static int list_size(list_t *l)
{
if (!l->head)
return 0;
int cnt = 0;
list_item_t *cur = l->head;
while (cur) {
cur = cur->next;
cnt++;
}
return cnt;
}
延伸問題: 在現有的程式碼基礎上，撰寫合併排序操作
首先撰寫 merge 的操作
list_item_t *mergeTwo(list_item_t *L1, list_item_t *L2)
{
list_item_t *head;
list_item_t **ptr = &head;
for (; L1 && L2; ptr = &(*ptr)->next) {
if (L1->value < L2->value) {
*ptr = L1;
L1 = L1->next;
} else {
*ptr = L2;
L2 = L2->next;
}
}
*ptr = L1 ? L1 : L2;
return head;
}
再來遞迴做 divide
list_item_t *mergesort(list_item_t *head)
{
if (!head->next || !head)
return head;
list_item_t *slow = head;
for (const list_item_t *fast = slow->next; fast && fast->next;
fast = fast->next->next) {
slow = slow->next;
}
list_item_t *new_l = malloc(sizeof(list_item_t));
new_l = slow->next;
slow->next = NULL;
list_item_t *left = mergesort(head), *right = mergesort(new_l);
mergeTwo(left, right);
}
---=[ List tests
Before sorting: 99 92 61 11 58 54 16 83 94 11
After sorting: 11 11 16 54 58 61 83 92 94 99
ALL TESTS PASSED
Tests run: 2
測驗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;
根據註解，這段程式碼的目的是要找出二元搜尋樹中的 in-order predecessor ，而註解有說明了是要左子樹中最右邊的節點。
所以會一直往右子樹的節點去搜尋，直到某個節點的右子樹為 NULL
所以EEEE = (*pred_ptr)->r
而這就代表該節點為左子樹中最右邊的節點
FFFF = &(*pred_ptr)->r
延伸問題: 解釋程式碼運作原理，並嘗試補完程式碼，使其可獨立執行。
根據程式中的敘述可以得知，目的是想要實作一個memory allocator，並且以二元搜尋樹的資料結構去存放那些可用、閒置的記憶體區塊。
首先來分析一下remove_free_tree，根據敘述，我認為此函式的功能主要是移除那些準備要被使用或配置的記憶體區塊，
使用find_free_tree先找出要拿來使用的區塊
block_t **node_ptr = find_free_tree(root, target);
node_ptr為指標的指標，是指向存放target的指標變數，也就是某個父節點的l或r。
而根據找的目標節點狀態不同，也會有不同的處理方式。
1. 當要移除的節點有左子節點及右子節點時:
這時不能直接刪除，需要找到一個替代的節點，就是目標節點的左子樹中最右邊的節點。
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
而這時又分為兩種情況
當替代的節點就是欲移除的節點的左子節點時:
先用old_right指標指向欲移除節點的右子節點，在對node_ptr做 dereference 得到指向目標的指標，在將其指向替代節點，再將新的目標節點的右子節點指標指向old_right，維持二元搜尋樹的結構。
替代的節點位於左子樹的深處:
必須把替代節點先移除原本的位置，所以這邊需要呼叫remove_free_tree(&old_left, *pred_ptr)移除替代節點，再將其接回正確的位置。 這邊利用pred_node指標來保存被移除的替代節點。
/* 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);
2. 當要移除的節點只有左子節點或右子節點時(只有一個子節點):
判斷移除節點的子節點是左還是右，將那個子節點連結回去原本的二元樹。
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
3. 當要移除的節點沒有任何子節點時:
直接將指向target的指標設為 NULL ，段開連接。
將target移除後，要將目標節點指向右子樹和指向左子樹的指標設為 NULL，避免 dangling reference。
剩餘待補上..
延伸問題: 參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
Todo
