# 2025q1 Homework2 (quiz1+2)
contributed by <`I-Ying-Tsai`>
## quiz1
### 測驗 1
這題要求我們利用 `list_insert_before` 涵式來測試好品味的 `linked list` 結構
```c
#include <stddef.h>
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
```
根據 `list_insert_before` 涵式的要求，可以得到：
AAAA : `&l->head` , 因為涵式接受的是 `Node** head` <所以我們需要傳入的是 `head` 的地址，而 `head` 又是第一個節點的地址，這也是指標的指標的應用。
BBBB : `before` , 因為在 `list_insert_before` 函式中，我們希望在 `entry` 之前插入新節點 `new_node`，因此我們需要確保 `new_node` 指向 `entry`，而前一個節點（`prev`）指向 `new_node`。
CCCC : `&(*p)->next` , 因為我們希望透過 `pointer to pointer (Node** p)` 來修改鏈結串列的結構，特別是當 `entry` 不是 `head` 的情況下，我們需要找到 `entry` 的前一個節點，並調整它的 `next` 指標，讓 `new_node` 正確插入。
DDDD : `item->next` , 因為 `*p = item;` 讓 `prev->next` 指向 `item。 item->next = before;` 讓 `item` 連接到 `entry`。
#### 延伸問題 : 解釋上方程式碼運作原理
這段程式碼的目的是 在單向鏈結串列中，找到 `entry` ，並在其之前插入 `item`。
#### 延伸文題 : 在現有的程式碼基礎上，撰寫合併排序操作
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// 找到鏈結串列的中間點並拆分
void split_list(Node* source, Node** front, Node** back) {
Node* slow = source;
Node* fast = source->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
*front = source;
*back = slow->next;
slow->next = NULL;
}
// 合併兩個排序後的鏈結串列
Node* sorted_merge(Node* a, Node* b) {
if (!a) return b;
if (!b) return a;
Node* result = NULL;
if (a->data <= b->data) {
result = a;
result->next = sorted_merge(a->next, b);
} else {
result = b;
result->next = sorted_merge(a, b->next);
}
return result;
}
// 合併排序主函式
void merge_sort(Node** head_ref) {
Node* head = *head_ref;
if (!head || !head->next) return;
Node *a, *b;
split_list(head, &a, &b);
merge_sort(&a);
merge_sort(&b);
*head_ref = sorted_merge(a, b);
}
// 插入新節點到鏈結串列
void push(Node** head_ref, int new_data) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
// 列印鏈結串列
void print_list(Node* head) {
while (head) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// 測試
int main() {
Node* head = NULL;
push(&head, 4);
push(&head, 2);
push(&head, 7);
push(&head, 1);
push(&head, 9);
push(&head, 3);
printf("原始鏈結串列:\n");
print_list(head);
merge_sort(&head);
printf("排序後的鏈結串列:\n");
print_list(head);
return 0;
}
```
----
### 測驗 2
`block_t` :
```c
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
```
`size_t size;` :
記錄當前記憶體區塊的大小。
`struct block *l;` :
指向 左子節點（left child），即 小於當前區塊大小的記憶體區塊。
`struct block *r;` :
指向 右子節點（right child），即 大於當前區塊大小的記憶體區塊。
---
`find_free_tree()` :
```c
block_t **find_free_tree(block_t **root, block_t *target);
```
搜尋 `target` 在 `free tree` 中的位置，回傳指向該區塊的指標。這個函式的作用是幫助 `remove_free_tree()` 定位到 `target` 在 二元搜尋樹（`BST`） 中的節點，以便進行刪除或合併。
---
`find_predecessor_free_tree()` :
```c
block_t *find_predecessor_free_tree(block_t **root, block_t *node);
```
尋找小於 `node->size` 的最大節點。這個函式的結果用於 刪除 `target` 節點時，找到適合替換 `target` 的節點。
---
`remove_free_tree()`
```c
void remove_free_tree(block_t **root, block_t *target)
```
從二元搜尋樹（`BST`）中移除 `target`，並確保 `BST` 結構保持完整。
刪除一個節點時，可能發生三種情況：
1.`target` 沒有子節點 → 直接刪除。
2.`target` 只有一個子節點 → 讓 `target` 的父節點直接指向 `target` 的子節點。
3.`target` 有兩個子節點 → 找到 `target` 的 `predecessor` 來替代 `target`，保持 `BST` 屬性。
---
EEEE : `(*pred_ptr)->r` , 因為它會走訪 `target` 節點的 左子樹，找到其中的最右節點。
FFFF : `pred_ptr` , 因為它代表如何向右子樹移動，即應該指向 `pred_ptr` 的 右子節點，直到找到最右節點。
#### 延伸閱讀 : 解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
這段程式碼的目的是 管理樹狀結構的記憶體區塊，其中 `block_t` 作為 二元搜尋樹（`BST`）節點，用來管理空閒記憶體區塊（`free block`）。主要功能包括：
`find_free_tree()`：在樹中尋找 指定大小的記憶體區塊。
`find_predecessor_free_tree()`：尋找 指定節點的 `predecessor`。
`remove_free_tree()`：從 `BST` 中 移除記憶體區塊，並維持 `BST` 屬性。
補完程式碼：
```c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
// 在二元搜尋樹中尋找適合大小的 free block
block_t **find_free_tree(block_t **root, block_t *target) {
block_t **current = root;
while (*current) {
if ((*current)->size == target->size) {
return current;
} else if ((*current)->size > target->size) {
current = &(*current)->l;
} else {
current = &(*current)->r;
}
}
return NULL;
}
// 找到左子樹的最右節點
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
if (!node || !node->l) return NULL;
block_t *pred = node->l;
while (pred->r) {
pred = pred->r;
}
return pred;
}
// 從 free tree 中移除一個節點
void remove_free_tree(block_t **root, block_t *target) {
block_t **node_ptr = find_free_tree(root, target);
if (!node_ptr || !*node_ptr) return;
// 如果節點有兩個子節點
if ((*node_ptr)->l && (*node_ptr)->r) {
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r) // EEEE
pred_ptr = &(*pred_ptr)->r; // FFFF
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr;
(*node_ptr)->r = old_right;
} else {
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
remove_free_tree(&old_left, *pred_ptr);
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
}
}
// 只有一個子節點
else if ((*node_ptr)->l || (*node_ptr)->r) {
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
}
// 沒有子節點
else {
*node_ptr = NULL;
}
target->l = NULL;
target->r = NULL;
}
// 插入新節點到 free tree
void insert_free_tree(block_t **root, block_t *node) {
if (!*root) {
*root = node;
node->l = node->r = NULL;
return;
}
if (node->size < (*root)->size) {
insert_free_tree(&(*root)->l, node);
} else {
insert_free_tree(&(*root)->r, node);
}
}
// 輔助函式：中序走訪列印二元搜尋樹
void inorder_traversal(block_t *root) {
if (root) {
inorder_traversal(root->l);
printf("%zu ", root->size);
inorder_traversal(root->r);
}
}
```
---
#### 延伸閱讀 : 參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
```shell
i-ying-tsai@i-ying-tsai-G5-KF5:~/quiz1/memory-allocators/build$ cmake ..
-- The CXX compiler identification is GNU 13.3.0
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- The C compiler identification is GNU 13.3.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Configuring done (0.4s)
-- Generating done (0.0s)
-- Build files have been written to: /home/i-ying-tsai/quiz1/memory-allocators/build
i-ying-tsai@i-ying-tsai-G5-KF5:~/quiz1/memory-allocators/build$ make
[ 25%] Building C object CMakeFiles/quiz2.dir/quiz2.c.o
[ 50%] Building CXX object CMakeFiles/quiz2.dir/src/StackAllocator.cpp.o
/home/i-ying-tsai/quiz1/memory-allocators/src/StackAllocator.cpp: In member function ‘virtual void* StackAllocator::Allocate(std::size_t, std::size_t)’:
/home/i-ying-tsai/quiz1/memory-allocators/src/StackAllocator.cpp:39:39: warning: narrowing conversion of ‘padding’ from ‘std::size_t’ {aka ‘long unsigned int’} to ‘char’ [-Wnarrowing]
39 | AllocationHeader allocationHeader{padding};
| ^~~~~~~
[ 75%] Building CXX object CMakeFiles/quiz2.dir/src/PoolAllocator.cpp.o
[100%] Linking CXX executable quiz2
[100%] Built target quiz2
i-ying-tsai@i-ying-tsai-G5-KF5:~/quiz1/memory-allocators/build$ ./quiz2
原始 free tree: 5 10 15 20 30
移除 size 10
更新後 free tree: 5 15 20 30
移除 size 20
更新後 free tree: 5 15 30
```
---
### 測驗 3
`node_t` :
```c
typedef struct __node {
long value;
struct list_head list;
} node_t;
```
`value`：儲存節點的值（數值）。
`list`：使用 `Linux Kernel list_head` 來管理鏈結串列。
---
`list_entry` :
```c
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
```
`ptr`：指向 `struct list_head` 的指標（即 `next` 或 `prev`）。
`type`：包含 `struct list_head` 的結構體類型（如 `node_t`）。
`member`：`struct list_head` 在 `type` 結構中的成員名稱（如 `list`）。
它會從 `list_head` 的指標 `ptr`，計算出 `type` 結構體的起始位置。
---
GGGG :` head->prev` , 因為需要確保雙向鍊結串列可以閉合。
HHHH : `list_entry(pivot,node_t,list)->value` , 因為它要取出 `pivot` 節點的 `value`。
IIII : `list_entry(n,node_t,list)->value` , 因為它要取出 `n` 節點的 `value`。
JJJJ : `pivot` , 因為當快速排序拆分鏈結串列時，pivot 作為 新的中間點，用來重新組合。
KKKK : `right` , 因為這個快速排序是從 `right` 部分開始排序，所以 `right` 需要先被放到 `begin[i + 2]`。
---
#### 延伸閱讀 : 解釋上述程式碼運作原理
---
#### 延伸閱讀 : 研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
---
## quiz 2
### 測驗 1
Sign in with Wallet
Connect another wallet