# 2025q1 Homework2 (quiz1+2)
contributed by < [`JeepWay`](https://github.com/JeepWay) >
## quiz1 測驗1
主要差異部分如下
```cpp
/* Test inserting at the beginning */
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
/* Test inserting at the end */
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
```
可以發現兩種函式的差異在於傳入的第二個參數，分別是 `l.head` 和 `NULL`，故可以推測第二個參數是要插入的節點的新 `next`。
`list_insert_before` 函式如下
```cpp
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;
}
```
因為是單向鏈結串列，所以 `p` 是 `list` 的 `head`。而 `item` 也就是插入的節點。
`*p = item;` 是在 assign 新的 head，也就是插入的 `item`。
`list_item_t **p;` 這種操作是指標的指標，方便之處在於可以不用回傳的新 head 的地址，所以該函式的回傳型態才會是 `void`。如果不使用指標的指標，就要向 LeetCode 的題目一樣回傳新 head 的地址。
`p = AAAA;` 目的是初始化 `p` 傳入的 head 的地址，所以 `AAAA` 是 `&l->head`。
`*p != BBBB` 是在偵測是否到達要插入的位置，也就是傳入的 `before`，所以 BBBB 是 `before`
`DDDD = before` 是在更新 `head->next`，所以 DDDD 是 `(*p)->next` 或者 `item->next`。
CCCC 一定式移動 `p` 到下一個節點，所以是 `&(*p)->next`。
| 名稱 | 程式碼 |
| ---- | ------------------------------ |
| AAAA | `&l->head` |
| BBBB | `before` |
| CCCC | `&(*p)->next` |
| DDDD | `(*p)->next` 或者 `item->next` |
### 視覺化展現
當使用 `list_insert_before(&l, l.head, &items[i]);` 把節點插入到含有一個節點的鏈結串列的 head 時，各指標與節點的關係圖如下。
```graphviz
digraph G {
rankdir = LR
node[shape=record];
param [label="<head>l|<p>p|<before>before"]
new_item [label="new item", style=dashed, color=grey];
subgraph cluster0 {
item1->NULL;
}
param:head -> item1 [style=dashed, color=grey];
param:p -> item1 [style=dashed, color=grey];
param:before -> item1:s [style=dashed, color=red];
}
```
在插入完成後，各指標與節點的關係圖如下。
```graphviz
digraph G {
rankdir = LR
node[shape=record];
param [label="<head>l|<p>p|<before>before"]
subgraph cluster0 {
"new item"->item1->NULL;
}
param:head -> "new item" [style=dashed, color=grey];
param:p -> "new item" [style=dashed, color=grey];
param:before -> item1:s [style=dashed, color=red];
}
```
當使用 `list_insert_before(&l, NULL, &items[i]);` 把節點插入到含有一個節點的鏈結串列的 head 時，各指標與節點的關係圖如下。
```graphviz
digraph G {
rankdir = LR
node[shape=record];
param [label="<head>l|<p>p|<before>before"]
new_item [label="new item", style=dashed, color=grey];
subgraph cluster0 {
item1->NULL;
}
param:head -> item1 [style=dashed, color=grey];
param:p -> item1 [style=dashed, color=grey];
param:before -> NULL:s [style=dashed, color=red];
}
```
在插入完成後，各指標與節點的關係圖如下。
```graphviz
digraph G {
rankdir = LR
node[shape=record];
param [label="<head>l|<p>p|<before>before"]
subgraph cluster0 {
item1 -> "new item" -> NULL;
}
param:head -> item1 [style=dashed, color=grey];
param:p -> "new item" [style=dashed, color=grey];
param:before -> NULL:s [style=dashed, color=red];
}
```
### 延伸問題 : 解釋上方程式碼運作原理
* `main()` -> `test_suite()` -> `my_run_test()` 巨集 -> `test_list()`
1. `list_reset()` 重節節點
2. 將重置後的 N 個節點依序插入到鏈結串列 `l` 的 head，然後檢查插入節點數和節點順序是否符合預期。
3. `list_reset()` 重節節點
4. 將重置後的 N 個節點依序插入到鏈結串列 `l` 的 tail，然後檢查插入節點數和節點順序是否符合預期。
5. `list_reset()` 重節節點
6. 將重置後的 N 個節點依序插入到鏈結串列 `l` 的 tail，檢查檢查插入節點數是否為 `N`。
### 延伸問題 : 撰寫合併排序操作
使用 top-down 方法實作 merge sort
## quiz1 測驗2
* `0x0`（最低地址）：這部分通常是未使用的（標記為 "UNUSED"），因為操作系統通常會將地址 0 保留為無效地址，以捕捉 null pointer error。
* `0x400000`：表示虛擬記憶體空間中的某個起始點（通常 Linux 系統中可執行文件的地址從 `0x400000` 開始）。
* Read-only segment：存放進程的可執行程式碼和唯讀數據
* `.text`：存放程式碼，如機器碼。
* `.rodata`：存放唯讀數據，例如字符串（string literals）。
* `.init`：存放程式初始化相關的數據。
* Read/write segment：存放行程（process）的全局變數和靜態變數：
* `.data`：存放已初始化的全局變數和靜態變數。
* `.bss`：存放未初始化的全局變數（這些變數在程式啟動時會被初始化為 0）。
* Run-time heap：這部分記憶體是用來動態分配的（通過 `malloc` 函數創建）。
* heap 從低地址往高地址增加。
* heap 的當前頂端由一個指標 `brk` 標記，這是 OS kernel 用來追踪 heap 邊界的地址。當程式需要更多空間時，會通過系統調用（如 `sbrk` 或 `brk`）來移動這個邊界。
* Memory-mapped region for shared libraries：用於映射共享函式庫（C 標準函式庫 `libc`）的記憶體。
* 共享函式庫包含程式運行時需要的函數和數據（例如 `printf` 函數）。
* 這部分的記憶體空間允許 process 訪問這些共享資源，而無需將整個函式庫複製到 process 的記憶體中。
* User stack：
* stack 從高地址向低地址增加。
* stack 用於存放函數調用的局部變數、返回地址等。
* `stack pointer` (`%rsp`) 指向 stack 的當前頂部 (往低地址)。
* Kernel virtual memory：保留給 OS kernel 使用的，普通用戶 process 無法直接訪問（標記為 "Memory invisible to user"），若要使用則須使用 kernel 提供出來的 api 來間接操作，例如系統呼叫。
```cpp
/* 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 (中序前繼節點) 即目標節點的左子樹中最右邊的節點。所以 `pred_ptr` 就是一直往右子節點移動，直到 `pred_ptr` 為 leaf 為止。
| 名稱 | 程式碼 |
| ---- | ------- |
| EEEE | `(*pred_ptr)->r` |
| FFFF | `&(*pred_ptr)->r` |
### 程式碼解釋
* `remove_free_tree(block_t **, block_t *)`：從二元樹中移除指定節點。
* `find_free_tree(root, target)`：找到目標節點 `target` 在二元樹中的地址，返回指向該節點的指標的指標（`node_ptr`）。
* 移除時有分三種情況，(1) 目標節點有**兩個子節點**：
1. 找到中序前繼節點 `pred_ptr`。並使用 `find_predecessor_free_tree` 檢查 `pred_ptr` 是否為預期的中序前繼節點。
2. 找到合適的子節點來替換目標節點的在二元樹中地址。
* 如果中序前繼節點是目標節點的左子節點，則直接替換，並更新原本右子樹的鏈結。
* 如果中序前繼節點不是目標節點的左子節點，則先使用 `remove_free_tree()` 移除把中序前繼節點從二元樹中移除，再把它替換到目標節點所在的位置，然後再重新連接原本的左右子樹。
* (2) 日標節點有**一個子節點**：將目標節點在二元樹中的地址替換為左右節點的其中一個。
* (3) 日標節點**沒有子節點**：設定目標節點在二元樹中的地址為 `NULL`。
* 設定目標節點的左右節點指標為 `NULL`，避免非預期的 reference。
### 嘗試補完程式碼
```cpp
block_t **find_free_tree(block_t **root, block_t *target) {
block_t **current = root;
while (*current && *current != target) {
if (target->size < (*current)->size)
current = &(*current)->l;
else
current = &(*current)->r;
}
return current;
}
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
block_t *current = node->l;
while (current->r)
current = current->r;
return current;
}
```
## quiz1 測驗3
## quiz2 測驗1
Sign in with Wallet
Connect another wallet