# 2025q1 Homework2 (quiz1+2)
contributed by < `bevmmf` >
## quiz1
### 測驗 `1`
singly linked list struct
```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_reset` 中，l.head 被設為 NULL => linked list 結構無dummy node
這份程式是一 singly linked list 的測試程式。主要用來測試 `list_insert_before` 。程式使用 macro 來進行斷言（assertion）和測試執行，並驗證 singly linked list 在不同插入情境下的行為。
1. 巨集定義 :
::: info
巨集（macro）是由前處理器（preprocessor）處理的一種機制，它會在編譯之前將程式碼中的巨集名稱替換為你定義的內容。這種替換是純粹的文字替換，不涉及函式呼叫的開銷
:::
```c
#define my_assert(test, message) \
do { \
if (!(test)) \
return message; \
} while (0)
```
`my_assert`：如果條件 `test` 不成立，返回錯誤訊息 `message`，否則繼續執行。
- assert 是一種放在程式中的一階邏輯，目的是為了標示與驗證程式開發者預期的結果－當程式執行到斷言的位置時，對應的斷言應該為真。若斷言不為真時，程式會中止執行，並給出錯誤訊息。
- `while(0)` 條件永遠為假，因此loop只執行一次
```c
#define my_run_test(test) \
do { \
char *message = test(); \
tests_run++; \
if (message) \
return message; \
} while (0)
```
`my_run_test` ：用來執行測試函數，並追蹤測試次數。如果測試失敗，會輸出錯誤訊息。
2. 全局變數
`items[N]` ： 一個包含 N(1000) 個 `list_item_t` 結構的陣列，用於測試中插入的項目。
`l` ： 一個 `list_t` 結構的實例，表示鏈結串列。
`tests_run` ： 追蹤測試次數，初始為 0。
3. 主要函數
```c
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_reset` ： 重置 `items` 陣列和鏈結串列 `l`，確保每次測試從乾淨的狀態開始。
```c
static char *test_list(void)
{
/* Test inserting at the beginning */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
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;
}
/* Test inserting at the end */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
k = 0;
cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k++;
cur = cur->next;
}
/* Reset the list and insert elements in order (i.e. at the end) */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "list size should be N");
return NULL;
}
```
`test_list` ： 核心測試函數，測試 `list_insert_before` 在不同情況下的行為。
- 分為三部分 :
1. 測試在 `l` 開頭插入 (每次插入都在 `l` 開頭（prepend），導致最後插入的元素（`items[999]`）成為頭部)
- 迴圈執行 `list_insert_before(&l, l.head, &items[i])` 1000 次：
- 初次插入時，`l.head` 為 NULL，假設 `list_insert_before` 將 `items[0]` 設為新頭。
- 第二次插入 `items[1]` 在 `l.head`（即 `items[0]`）之前，更新頭為 `items[1]`，`items[1].next = items[0]`。
- 確認最終大小為 1000。
- 檢查順序：從頭開始，值應為 999, 998, ..., 0（逆序）。
3. 測試在 `l` 結尾插入 (每次插入都在串列結尾（append）)
- 重置串列，確認初始大小為 0。
- 迴圈執行 `list_insert_before(&l, NULL, &items[i])` 1000 次：
- 假設 `position == NULL` 表示插入到結尾。
- 初次插入時，串列為空，`items[0]` 成為頭。
- 第二次插入 `items[1]` 在結尾，`items[0].next = items[1]`。
- 確認最終大小為 1000。
- 檢查順序：從頭開始，值應為 0, 1, ..., 999（正序）。
5. 重複測試在結尾插入（僅檢查大小）
- 確保多次插入到結尾的穩定性
- 若所有assert通過，返回 NULL，表示測試成功
```c
static char *test_suite(void)
{
my_run_test(test_list);
return NULL;
}
```
`test_suite` ： 使用 `my_run_test` 執行 `test_list` ，執行所有測試案例。若無錯誤，返回 NULL。
```c
int main(void)
{
printf("---=[ List tests\n");
char *result = test_suite();
if (result)
printf("ERROR: %s\n", result);
else
printf("ALL TESTS PASSED\n");
printf("Tests run: %d\n", tests_run);
return !!result;
}
```
`main` ：
- 輸出測試標題。
- 運行 `test_suite`，儲存結果。
- 若 `result` 非空，輸出錯誤訊息；否則輸出成功訊息。
- 顯示測試次數（應為 1）。
- 返回值：0（成功）或 1（失敗）。
```c
static inline void list_insert_before(List_t *l, //function signature
list_item_t *before,
list_item_t *item);
{
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
;
*p = item;
DDDD = before;
}
```
首先必須知道函式 `list_insert_before` 每個parameter的定義
- `@l` : 指向欲操作list的pointer
- `@before` :
> Pointer to the item before which the new item should be inserted
以上句子which指the item，因此before指向插入之new item之後的item位置
- `@item` : 要插入的new item
再來是函式運作邏輯 :
以 `before` = C 為例:
```graphviz
digraph G {
rankdir = LR;
node [shape=record];
A [label="A | {val | <next>next}"];
B [label="B | {val | <next>next}"];
C [label="C | {val | <next>next}"];
D [label="D | {val | <next>next}"];
node[shape=plaintext];
p [fontcolor = black ]
head [fontcolor = black ]
before [fontcolor = black ]
p -> head[];
head -> A[];
before -> C:C[]
A:next -> B:B;
B:next -> C:C;
C:next -> D:D;
}
```
for loop會遍歷 `l`，直到找到 `before` item
```graphviz
digraph G {
rankdir = LR;
node [shape=record];
A [label="A | {val | <next>next}"];
B [label="B | {val | <next>next}"];
C [label="C | {val | <next>next}"];
D [label="D | {val | <next>next}"];
node[shape=plaintext];
p [fontcolor = black ]
head [fontcolor = black ]
before [fontcolor = black ]
p -> head[color = red];
head -> A[];
before -> C:C[]
A:next -> B:B;
B:next -> C:C;
C:next -> D:D;
}
```
```graphviz
digraph G {
rankdir = LR;
node [shape=record];
A [label="A | {val | <next>next}"];
B [label="B | {val | <next>next}"];
C [label="C | {val | <next>next}"];
D [label="D | {val | <next>next}"];
node[shape=plaintext];
p [fontcolor = black ]
head [fontcolor = black ]
before [fontcolor = black ]
p -> A:next[color = red];
head -> A[];
before -> C:C[]
A:next -> B:B;
B:next -> C:C;
C:next -> D:D;
}
```
```graphviz
digraph G {
rankdir = LR;
node [shape=record];
A [label="A | {val | <next>next}"];
B [label="B | {val | <next>next}"];
C [label="C | {val | <next>next}"];
D [label="D | {val | <next>next}"];
node[shape=plaintext];
p [fontcolor = black ]
head [fontcolor = black ]
before [fontcolor = black ]
p -> B:next[color = red];
head -> A[];
before -> C:C[]
A:next -> B:B;
B:next -> C:C;
C:next -> D:D;
}
```
`*p = item;` 將`before`前一個item的 `next` 指向 new item，完成插入
```graphviz
digraph G {
rankdir = LR;
node [shape=record];
A [label="A | {val | <next>next}"];
B [label="B | {val | <next>next}"];
C [label="C | {val | <next>next}"];
D [label="D | {val | <next>next}"];
new [label="new | {val | <next>next}"];
edge1 [label="head", shape=point, width=0.1, height=0.1]; // 小圓點表示邊
edge2 [label="P", shape=point, width=0.1, height=0.1]; // 小圓點表示邊
edge3 [label="before", shape=point, width=0.1, height=0.1]; // 小圓點表示邊
edge1 -> A[label="head"];
edge2 -> B:next[label="P",color="red"];
edge3 -> C:C[label="before"]
A:next -> B;
B:next -> new;
C:next -> D;
}
```
`item->next = before;` 讓 new item 指向 `before` 所指向，確保 `l` 完整性
```graphviz
digraph G {
rankdir = LR;
node [shape=record];
A [label="A | {val | <next>next}"];
B [label="B | {val | <next>next}"];
C [label="C | {val | <next>next}"];
D [label="D | {val | <next>next}"];
new [label="new | {val | <next>next}"];
edge1 [label="head", shape=point, width=0.1, height=0.1]; // 小圓點表示邊
edge2 [label="P", shape=point, width=0.1, height=0.1]; // 小圓點表示邊
edge3 [label="before", shape=point, width=0.1, height=0.1]; // 小圓點表示邊
edge1 -> A[label="head"];
edge2 -> B:next[label="P",color="red"];
edge3 -> C:C[label="before"]
new:next -> C
A:next -> B;
B:next -> new;
C:next -> D;
}
```
再來是解題部分 :
AAAA : `&l->head`,因為是從頭開始遍歷，所以為指向`head`。又因p為指向指向item的pointer，因此除了取 `l` 的 `head` 之外還要取 `&` 。
BBBB : `before`,根據此函式signature comment可知欲插入的new item在`before`之前，因此遍歷的停止點應設在 `p` 指向 `before` 指向的item即跳出
CCCC : `&(*p)->next`,此好品味地函式使用指向指標的指標，目的是能夠不用判斷是否head條件。此寫法的核心即是讓指標的指標持續指向 `next`。
DDDD : `item->next`,根據此函式定義，將new item下一個指向before即完成
---
### 測驗 `2`
> 延伸問題 1
> 解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
#### 解釋程式碼運作的原理
此題背景為 dyynamic memory allocator 的實現，特別是顯式配置器（explicit allocator）。allocator 必須滿足多個條件，包括處理任意請求序列、立即滿足需求、僅使用heap空間、確保地址對齊（例如 32 位系統為 8 位元組對齊，64 位系統為 16 位元組對齊），並且不得修改已配置的區塊。目標是在吞吐率（單位時間內完成的配置和釋放請求數量）和空間利用率（$U_k = \frac{max_{i<k} P_i}{H_k}$ ，其中 $𝑃_i$ 是過去請求的有效荷載總和，$𝐻_k$ 是目前heap大小）之間找到平衡。為了提升空間區域性（spatial locality），allocator利用分頁（paging）特性，確保每個分頁僅存放特定大小類別（size-class）的空間，避免自由區塊地址分散導致效能下降。
為什麼選擇 BST 架構實作allocator?
1. 能夠快速搜尋合適區塊
當程式請求分配某個大小的記憶體時，分配器需要在自由區塊中找到一個足夠大的區塊。BST 的結構允許從根節點開始，根據請求大小快速決定向左還是向右搜尋，效率遠高於線性搜尋。
2. 支援動態操作
記憶體分配和釋放是動態的過程，自由區塊會不斷被加入或移除，而 BST 支援高效的插入和刪除操作
3. 可擴展性
當系統中的自由區塊數量變多時，BST 的搜尋時間只隨節點數量對數增長（𝑂(log𝑛)），比起逐一檢查所有區塊的線性結構（如linked-list，O(n)）更具優勢。
```c
#include <assert.h>
#include <stddef.h>
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);
/*
* Structure representing a free memory block in the memory allocator.
* The free tree is a binary search tree that organizes free blocks (of type block_t)
* to efficiently locate a block of appropriate size during memory allocation.
*/
void remove_free_tree(block_t **root, block_t *target)
{
/* Locate the pointer to the target node in the tree. */
block_t **node_ptr = find_free_tree(root, target);
/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
/* 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;
/* Verify the found predecessor using a helper function (for debugging).
*/
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);
/* If the predecessor is the immediate left child. */
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /* Replace target with its left child. */
(*node_ptr)->r = old_right; /* Attach the original right subtree. */
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
} else {
/* The predecessor is deeper in the left subtree. */
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* 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);
}
}
/* If the target node has one child (or none), simply splice it out. */
else if ((*node_ptr)->l || (*node_ptr)->r) {
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
} else {
/* No children: remove the node. */
*node_ptr = NULL;
}
/* Clear the removed node's child pointers to avoid dangling references. */
target->l = NULL;
target->r = NULL;
}
```
此題程式碼實現了一個基於二元搜尋樹（BST）的記憶體區塊管理系統
記憶體區塊 `block_t` 結構定義如下：
```c
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
```
- size：block的大小。
- l：左子節點pointer。
- r：右子節點pointer。
以下為未完成函式 :
```c
block_t **find_free_tree(block_t **root, block_t *target)
```
```c
block_t *find_predecessor_free_tree(block_t **root, block_t *node)
```
以下為函式 `remove_free_tree` :
目的是從 BST 中移除 target 節點，以下是函式signature
```c
void remove_free_tree(block_t **root, block_t *target)
```
- `block_t **root`：指向樹根的指標的指標，允許函數修改樹的根。
- `block_t *target`：要移除的目標節點。
1. 尋找目標節點
```c
block_t **node_ptr = find_free_tree(root, target);
```
返回指向 `target` 的指標，若 `target` 不存在，則undefined behavior（程式碼未處理此情況）
2. 處理有兩個子節點的情況
```c
if ((*node_ptr)->l && (*node_ptr)->r) {
```
特別處理的原因是 :
在 BST 中，移除有兩個子節點的節點需要找到一個替換節點，以維持 BST 的性質（左子樹所有 節點小於根，右子樹所有節點大於root）
替換節點通常是中序前驅（左子樹的最大節點）或中序後繼（右子樹的最小節點） [tree學習]()
- 尋找中序前驅(inorder predecessor)
- EEEE : `(*pred_ptr)->r`, 因為它會走訪 target 節點的 左子樹，找到其中的最右節點。
- FFFF : `&(*pred_ptr)->r` , 因為它代表如何向右子樹移動，即應該指向 pred_ptr 的 右子節點，直到找到最右節點。
```c
/* 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;
```
- 驗證中序前驅
- 調用 `find_predecessor_free_tree` 獲取中序前驅，並與 `pred_ptr` 指向的節點比較
- 使用 `assert` 進行調試，確保找到的中序前驅正確
```c
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);
```
- 替換目標節點
- case1 中序前驅是目標節點的直接左子節點
```c
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; // 將目標節點替換為其左子節點
(*node_ptr)->r = old_right; // 將原右子樹附加到新節點
assert(*node_ptr != (*node_ptr)->l); //assert 確保新節點不指向自己，避免循環引用。
assert(*node_ptr != (*node_ptr)->r);
}
```
- case2 中序前驅在左子樹的更深處
```c
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;
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
}
```
3. 處理有一個子節點或無子節點的情況
```c
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;
}
```
- 有一個子節點：
- 使用三元運算子選擇唯一的子節點（child）
- 三元運算子（Ternary Operator）: 用來簡化簡單的 `if-else`
```c
condition ? valueIfTrue : valueIfFalse
```
1. 一個條件（condition）
2. 條件為真的結果（value if true）
3. 條件為假的結果（value if false）
- 用子節點替換目標節點（`*node_ptr = child`）
- 無子節點
4. 清除被移除節點的指標
```c
target->l = NULL;
target->r = NULL;
```
- 將被移除節點（target）的左右子節點指針設為 NULL。避免懸空指針（dangling pointers），確保被移除的節點不再引用樹中的其他部分
fin
#### 補完程式碼並測試
`find_free_tree`
```c
block_t **find_free_tree(block_t **root, block_t *target) {
block_t **current = root; // Start from the root node
while (*current != NULL) { // Continue until the current node is NULL
if (target->size < (*current)->size) {
current = &(*current)->l;
} else if (target->size > (*current)->size) {
current = &(*current)->r;
} else {
if (*current == target) { // Check if the nodes are the same (same memory address)
return current;
} else {
return NULL; // Sizes are equal but not the same node, return NULL
}
}
}
return NULL; // Target node not found, return NULL
}
```
根據比較 `target` 與 `root` subtree大小往下找，直到size相同、address也同
`find_predecessor_free_tree`
```c
block_t *find_predecessor_free_tree(block_t **root, block_t *node) { //`node` 即 `target`
if (node == NULL || node->l == NULL) { // If the node is NULL or has no left child
return NULL; // Return NULL as there is no predecessor
}
block_t *pred = node->l; // Start from the left child
while (pred->r != NULL) { // Find the rightmost node in the left subtree
pred = pred->r; // Move to the right child
}
return pred; // Return the inorder predecessor
}
```
在 `node` 的left subtree 持續往右下找到底
```c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// block struct
typedef struct block {
size_t size;
struct block *l;
struct block *r;
} block_t;
// 查找target node
block_t **find_free_tree(block_t **root, block_t *target) {
block_t **current = root;
while (*current != NULL) {
if (target->size < (*current)->size) {
current = &(*current)->l;
} else if (target->size > (*current)->size) {
current = &(*current)->r;
} else {
if (*current == target) {
return current;
} else {
return NULL;
}
}
}
return NULL;
}
// 查找inorder predecessor
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
if (node == NULL || node->l == NULL) {
return NULL;
}
block_t *pred = node->l;
while (pred->r != NULL) {
pred = pred->r;
}
return pred;
}
// 移除target node
void remove_free_tree(block_t **root, block_t *target)
{
/* Locate the pointer to the target node in the tree. */
block_t **node_ptr = find_free_tree(root, target);
/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
/* Verify the found predecessor using a helper function (for debugging).
*/
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);
/* If the predecessor is the immediate left child. */
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /* Replace target with its left child. */
(*node_ptr)->r = old_right; /* Attach the original right subtree. */
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
} else {
/* The predecessor is deeper in the left subtree. */
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* 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);
}
}
/* If the target node has one child (or none), simply splice it out. */
else if ((*node_ptr)->l || (*node_ptr)->r) {
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
} else {
/* No children: remove the node. */
*node_ptr = NULL;
}
/* Clear the removed node's child pointers to avoid dangling references. */
target->l = NULL;
target->r = NULL;
}
// auxiliary_func1：insert node
void insert_free_tree(block_t **root, block_t *node) {
if (*root == NULL) {
*root = node; //insert
node->l = NULL;
node->r = NULL;
} else if (node->size < (*root)->size) {
insert_free_tree(&(*root)->l, node);
} else {
insert_free_tree(&(*root)->r, node);
}
}
// auxiliary_func2：：inorder traverse and print
void inorder_print(block_t *root) {
if (root != NULL) {
inorder_print(root->l);
printf("%zu ", root->size);
inorder_print(root->r);
}
}
int main() {
// create node
block_t *node1 = malloc(sizeof(block_t)); node1->size = 10;
block_t *node2 = malloc(sizeof(block_t)); node2->size = 5;
block_t *node3 = malloc(sizeof(block_t)); node3->size = 15;
block_t *node4 = malloc(sizeof(block_t)); node4->size = 3;
block_t *node5 = malloc(sizeof(block_t)); node5->size = 7;
// build BST
block_t *root = NULL;
insert_free_tree(&root, node1);
insert_free_tree(&root, node2);
insert_free_tree(&root, node3);
insert_free_tree(&root, node4);
insert_free_tree(&root, node5);
// print tree_org
printf("Original tree (in-order): ");
inorder_print(root);
printf("\n");
remove_free_tree(&root, node1);
printf("Tree after removing size 10: ");
inorder_print(root);
printf("\n");
free(node1);
free(node2);
free(node3);
free(node4);
free(node5);
return 0;
}
```
測試程式為插入節點 3, 5, 7, 10, 15，形成如下結構
假設 `target` 為10
```
10
/ \
5 15
/ \
3 7
```
移除 size = 10 的節點（root 有兩個子節點）。`remove_free_tree` 會用中序前驅（7）替換 10，結果如下：
```
7
/ \
5 15
/
3
```
> 延伸問題 2
> 參閱 [memory-allocators](https://github.com/mtrebi/memory-allocators)，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
---
### 測驗 `3`
> 延伸問題1
> 解釋上述程式碼運作原理
這題要求補全一個非遞迴的快速排序演算法實現，該實現基於鏈結串列，並使用堆疊模擬遞迴過程。
#### 先了解 non-recursive quick sort 運作
首先是所需的變數
1. `pivot` : 基準點
每次分割時選出來的一個節點，用來當作比較的基準(總是選當前子串列的第一個節點（也就是 `L`）)
- 此為 quick sort 的核心。每次分割完後，pivot 會被放在正確的位置(左邊都比它小，右邊都比它大)
2. `left` : 左邊子串列
是一個臨時的鏈結串列，用來裝所有比 pivot 小或等於 pivot 的節點
3. `right` : 右邊子串列
是一個臨時的鏈結串列，用來裝所有比 pivot 大的節點
4. `L` : 當前子串列的開頭
是當前正在處理的子串列的第一個節點
在每次分割開始時，`L` 從堆疊（`begin[]`）裡取出，然後被設為 pivot。`L` 告訴我們「從哪開始排序」
5. `R` : 當前子串列的結尾
6. `begin[]` : stack(記錄子串列開頭)
begin[] 是一個數組，當作堆疊用，裡面存的是每個待排序子串列的開頭節點。因為不用遞迴，我們需要一個地方記錄還沒處理完的子串列。begin[] 就像一個待辦清單。
每次分割後：
- begin[i] 存 left 的開頭。
- begin[i+1] 存 pivot。
- begin[i+2] 存 right 的開頭。
7. `end[]` : stack(記錄子串列結尾)
它搭配 begin[]，幫我們知道每個子串列的範圍（從哪到哪）
```c
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list);
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
參數：`node_t **list` 是一個指向鏈結串列頭部指針的指針
變數 :
`n`：串列的節點數量，通過 list_length(list) 計算。
`value`：用來儲存基準點（pivot）的值。
`i`：堆疊的索引，指的是當前正在處理的子串列位置。
`max_level`：堆疊的最大容量，設為 2 * n。這個值確保堆疊有足夠空間處理最壞情況下的分割。
`begin[]` 和 `end[]`：兩個陣列模擬堆疊，分別儲存每個待排序子串列的開頭和結尾節點。
`result`：最終排序完成的串列頭部，初始為 NULL。
`left` 和 `right`：用來暫存分割後的子串列，分別存放小於和不大於 pivot 的節點
stack初始化
```c
begin[0] = *list;
end[0] = list_tail(list);
```
- 將整個list作為第一個待排序的子串列
```graphviz
digraph g1 {
node[shape=plaintext];
"begin[0]" [fontcolor="brown"];
"end[0]" [fontcolor="brown"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n3 -> n1 -> n0 -> n2 -> n4 -> l0
}
"begin[0]" -> n3;
"end[0]" -> n4;
pivot -> n3;
L -> n3;
R -> n4;
p -> n1;
}
```
主循環
```c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
// 分割
} else {
// 合併
}
}
```
- 循環條件：當 `i >= 0` 時，表示stack中還有待處理的子串列。
- `L` 和 `R`：從堆疊中取出當前子串列的開頭（`begin[i]`）和結尾（`end[i]`）。
- 分支：
- 如果 `L != R`，子串列有多於一個節點，需要進行分割。
- 分割
```c
node_t *pivot = L; //選基準點（pivot）：選擇子串列的開頭 L 作為 pivot。
- 斷開 pivot：將 pivot->next 設為 NULL，使 pivot
value = pivot->value;
node_t *p = pivot->next; //準備遍歷：p 指向 pivot 後面的節點，作為分割的起點
pivot->next = NULL; //斷開 pivot：將 pivot->next 設為 NULL，使 pivot 成為獨立節點
```
```c
//分割子串列至left or right
while (p) {
node_t *n = p; //當前處理節點
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
- 更新堆疊
- 放入新子串列
- 重置：`left = right = NULL`，為下一次分割準備。
- 移動索引：`i += 2`，跳到 right 子串列的位置，下一次循環會先處理它。
:::info
每組子串列會佔用 `begin[]` 的三個位置
:::
```c
begin[i] = left;
end[i] = list_tail(left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(right);
left = right = NULL;
i += 2;
```
```graphviz
digraph g6 {
node[shape=plaintext];
"begin[0]" [fontcolor="brown"];
"end[0]" [fontcolor="brown"];
"begin[1]" [fontcolor="brown"];
"end[1]" [fontcolor="brown"];
"begin[2]" [fontcolor="brown"];
"end[2]" [fontcolor="brown"];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
}
"begin[0]" -> n1;
"end[0]" -> n2;
"begin[1]" -> n3;
"end[1]" -> n3;
"begin[2]" -> n4;
"end[2]" -> n4;
pivot -> n3 -> l1;
left -> n1 -> n0 -> n2 -> l3;
right -> n4 -> l2;
L -> n3;
R -> n4;
}
```
- 如果 `L == R`，子串列只有一個節點（或為空），直接處理並加入結果。
- 合併
```c
if (L)
list_add(&result, L);
i--;
```
- 處理單節點：
- 如果 `L != NULL`，表示這個子串列只有一個節點，將其加入 result。
- 如果 `L == NULL`，則跳過（空子串列）。
- 回退：`i--`，返回堆疊中上一個待處理的子串列。
- 最終更新
```c
*list = result;
```
將排序後的串列頭部 `result` 令 `list` 指向
#### 接下來將以上quick sort 改寫成以Linux 核心風格的doubly linked list 實作
##### 測試程式
1. `list_construct`
創建一個新的節點並將其插入到指定的鏈結串列中
```c
void list_construct(struct list_head *list, int n)
{
node_t *node = malloc(sizeof(node_t));
node->value = n;
list_add(&node->list, list);
}
```
2. `list_free`
```c
void list_free(const struct list_head *head)
{
node_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
free(entry);
}
}
```
釋放lsit中的所有節點記憶體
3. `list_is_ordered`
檢查list是否ascend
```c
static bool list_is_ordered(const struct list_head *head)
{
int value = list_entry(head->next, node_t, list)->value;
node_t *entry;
list_for_each_entry (entry, head, list) {
if (entry->value < value)
return false;
value = entry->value;
}
return true;
}
```
4. `shuffle`
將整數陣列的元素隨機打亂
```c
void shuffle(int *array, size_t n)
{
if (n <= 0)
return;
for (size_t i = 0; i < n - 1; i++) {
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
```
使用 [`Fisher-Yates` 演算法](https://hackmd.io/jrrJxtLmTjCvtwxyuPheIg)
- 從索引 i = 0 到 n - 2 遍歷陣列。
- 計算隨機索引 j，範圍從當前索引 i 到陣列末尾（n - 1）。
- j 的計算公式 `i + rand() / (RAND_MAX / (n - i) + 1)` 確保隨機選擇是均勻的
- 交換 array[i] 和 array[j] 的值。
5. `main`
```c
int main(int argc, char **argv)
{
struct list_head *list = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(list);
size_t count = 100000;
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i)
test_arr[i] = i;
shuffle(test_arr, count);
while (count--)
list_construct(list, test_arr[count]);
quick_sort(list);
assert(list_is_ordered(list));
list_free(list);
free(test_arr);
return 0;
}
```
初始化 `list`
準備100000筆測試數據放入 `test_arr`
將 `test_arr` 中測試數據放入插入 `list`
`quick_sort(list)` 排序
`assert(list_is_ordered(list)` 驗證升序結果
釋放 `list` 、 `test_arr`中的所有節點。
##### quick_sort
##### auxiliary funciton
1. `list_tail`
返回鏈結串列的尾部節點
```c
struct list_head *list_tail(struct list_head *head)
{
while (head && head->next)
head = head->next;
return head;
}
```
2. `list_length`
計算鏈結串列的長度
```c
int list_length(struct list_head *left)
{
int n = 0;
struct list_head *node;
list_for_each(node, left) n++;
return n;
}
```
3. `rebuild_list_link`
重建之前被斷開之雙向鏈結串列，重接回成circular雙向鏈結串列
```c
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; // GGGG
}
```
##### quick_sort 主體
```c
void quick_sort(struct list_head *list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
struct list_head *begin[max_level];
struct list_head *result = NULL, *left = NULL, *right = NULL;
begin[0] = list->next;
list->prev->next = NULL;
while (i >= 0) {
struct list_head *L = begin[i], *R = list_tail(begin[i]);
if (L != R) {
struct list_head *pivot = L;
value = list_entry(pivot, node_t, list)->value; // HHHH
struct list_head *p = pivot->next;
pivot->next = NULL; /* break the list */
while (p) {
struct list_head *n = p;
p = p->next;
int n_value = list_entry(n, node_t, list)->value; // IIII
if (n_value > value) {
n->next = right;
right = n;
} else {
n->next = left;
left = n;
}
}
begin[i] = left;
begin[i + 1] = pivot; // JJJJ
begin[i + 2] = right; // KKKK
left = right = NULL;
i += 2;
} else {
if (L) {
L->next = result;
result = L;
}
i--;
}
}
list->next = result;
rebuild_list_link(list);
}
```
1. 初始化
`int n = list_length(list)`：計算鏈結串列長度。
`int max_level = 2 * n`：設置堆疊最大層級為 2 * n，以應對最壞情況（完全不平衡的分割）。
`struct list_head *begin[max_level]`：堆疊數組，儲存待處理的子串列開頭。
`result, left, right`：分別用於儲存最終結果和分割後的左右子串列，初始化為 NULL。
`begin[0] = list->next`：將整個鏈結串列的開頭放入堆疊。
`list->prev->next = NULL`：斷開循環鏈結串列，轉為單向鏈結串列，便於後續操作。
2. 主循環
`while (i >= 0)`，表示堆疊中仍有待處理的子串列。
`L = begin[i]`：當前子串列的開頭。
`R = list_tail(begin[i])`：當前子串列的結尾。
- 分支：
- 如果 `L != R`，執行<font color="#AC19C9">分割</font>過程。
- 選 `pivot`
- 分割子串列
- 更新堆疊
- 如果 `L == R`，執行<font color="#AC19C9">合併</font>過程。
- 條件：if (L)，表示子串列只有一個節點。
- `L->next = result; result = L`：將單節點加入 result（頭插法）。
- `i--`：回退到堆疊中的上一個子串列。
## quiz2
### 測驗`1`
>延伸問題1：
>解釋上方程式碼運作原理，改進 `random_shuffle_array` 也探討 `list_for_each_entry_safe` 建構的迴圈中，若將 `list_move_tail` 換為 `list_move`，為何會無法滿足 stable sorting
#### 背景
通常傳統的quick sort為unstable(相同元素的相對順序可能改變)。此題目的為用linux 核心風格linked list做出stable的quick sort
#### 解釋
list struct
```c
#include <stdint.h>
struct listitem {
uint16_t i;
struct list_head list;
};
```
比較用的函式 `cmpint`
- 用來比較兩個 uint16_t 值，返回負數（< 0）、零（= 0）或正數（> 0），表示大小關係
```c
static inline int cmpint(const void *p1, const void *p2)
{
const uint16_t *i1 = (const uint16_t *) p1;
const uint16_t *i2 = (const uint16_t *) p2;
return *i1 - *i2;
}
```
##### auxiliary func
1. `ARRAY_SIZE` macro
計算陣列 x 的元素個數
```c
#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))
```
2. `getnum` 函式
生成一個偽隨機的 8 位元無符號整數（uint8_t），範圍在 0 到 255 之間
```c
static inline uint8_t getnum(void)
{
static uint16_t s1 = UINT16_C(2);
static uint16_t s2 = UINT16_C(1);
static uint16_t s3 = UINT16_C(1);
s1 *= UINT16_C(171);
s1 %= UINT16_C(30269);
s2 *= UINT16_C(172);
s2 %= UINT16_C(30307);
s3 *= UINT16_C(170);
s3 %= UINT16_C(30323);
return s1 ^ s2 ^ s3;
}
```
首先要先了解什麼是 `線性同餘生成器（LCG）`
線性同餘生成器（Linear Congruential Generator, LCG）是一種簡單的偽隨機數生成演算法
- 偽隨機（Pseudo-random）的定義 : 指生成的隨機數序列並不是真正的隨機，而是通過確定性演算法（deterministic algorithm）生成的。也就是給定相同的初始種子（seed），每次執行程式生成的隨機數序列是完全相同的
它的核心是使用一個遞迴公式來生成隨機數序列，公式如下：
$X_{n+1}=(a \cdot X_n+c)\ mod\ m$
- $X_n$ : 第 n 次生成的隨機數（種子，也就是getnum所設定的171、172、170）
- a：乘數（multiplier），一個整數。
- c：增量（increment），一個整數。
- m：模數（modulus），決定隨機數的範圍。
- $X_{n+1}$ : 下一個隨機數
再回來看函式即為
使用三個靜態變數 s1、s2、s3 作為隨機數種子，初始值分別為 2、1、1
每次調用時，根據線性同餘生成器（LCG）的變形更新種子：
`s1 = (s1 * 171) % 30269`
`s2 = (s2 * 172) % 30307`
`s3 = (s3 * 170) % 30323`
將更新後的 s1、s2、s3 進行xor（^）運算，返回結果作為隨機數。
3. `get_unsigned16`
生成一個 16 位元無符號整數（uint16_t）的偽隨機數，範圍在 0 到 65535 之間
```c
static uint16_t get_unsigned16(void)
{
uint16_t x = 0;
size_t i;
for (i = 0; i < sizeof(x); i++) {
x <<= 8;
x |= getnum();
}
return x;
}
```
- 初始化 x = 0，x 是 uint16_t 類型，佔 2 bytes。
- 迴圈執行 sizeof(x) 次（這裡 sizeof(x) = 2），每次：
- x <<= 8：將 x 左移 8 位元（相當於乘以 256），為新的隨機數騰出空間。
- x |= getnum()：調用 getnum() 獲取一個 8 位元隨機數，通過按位或（OR）添加到 x 的低 8 位。
- loop1：x 的低 8 位被填入第一個 getnum() 結果。
- loop2：x 左移後，低 8 位再填入第二個 getnum() 結果，形成完整的 16 位元數。
4. `random_shuffle_array`
將給定陣列 operations（長度為 len）的元素順序隨機打亂
```diff
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = 0; i < len; i++) {
/* WARNING biased shuffling */
uint16_t j = get_unsigned16() % (i + 1);
+ uint16_t temp = operations[i];
operations[i] = operations[j];
- operations[j] = i;
+ operations[j] = temp;
}
}
```
我認為此src有誤，應為swap，因此不應該為 `operations[j] = i;`
##### 測試程式
```c
int main(void)
{
struct list_head testlist;
struct listitem *item, *is = NULL;
size_t i;
random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values)); //values 為array
INIT_LIST_HEAD(&testlist);
assert(list_empty(&testlist));
for (i = 0; i < ARRAY_SIZE(values); i++) { //build linked-list with values
item = (struct listitem *) malloc(sizeof(*item));
assert(item);
item->i = values[i];
list_add_tail(&item->list, &testlist);
}
assert(!list_empty(&testlist));
qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint); //對 values array進行 C 標準庫之quick sort
list_quicksort(&testlist);
i = 0;
//驗證排序結果並free
list_for_each_entry_safe (item, is, &testlist, list) {
assert(item->i == values[i]);
list_del(&item->list);
free(item);
i++;
}
assert(i == ARRAY_SIZE(values));
assert(list_empty(&testlist));
return 0;
}
```
1. 準備數據：隨機打亂 values 數組，模擬無序輸入。
2. 構建串列：根據打亂後的數組創建一個無序鏈結串列。
3. 排序與驗證：
- 使用標準 qsort 對array排序，作為正確結果的參考。
- 使用 list_quicksort 對linked list排序。
- 逐一比較排序後的linked list與array，確保結果一致。
4. free 所有node
##### `list_quicksort` 主體
```c
static void list_quicksort(struct list_head *head)
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
list_quicksort(&list_less);
list_quicksort(&list_greater);
list_add(&pivot->list, head);
list_splice_tail(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
1. 檢查edge condition
2. 初始化臨時串列 `list_less`、`list_greater`
3. 選取並移除`pivot`
pivot 通常從串列頭部獲取第一個節點
4. 分割串列
```c
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
```
`list_move_tail`
src def
```c
/**
* list_move() - Move a list node to the beginning of the list
* @node: pointer to the node
* @head: pointer to the head of the list
*
* The @node is removed from its old position/node and add to the beginning of
* @head
*/
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
/**
* list_move_tail() - Move a list node to the end of the list
* @node: pointer to the node
* @head: pointer to the head of the list
*
* The @node is removed from its old position/node and add to the end of @head
*/
static inline void list_move_tail(struct list_head *node,
struct list_head *head)
{
list_del(node);
list_add_tail(node, head);
}
```
因為 stable sorting 定義為兩相等值在排序後相對順序不會改變。若出現兩個與pivot相等的node使用`list_move`，相對順序會被顛倒。
5. 遞迴呼叫自己 排序子串列
6. 將被移光的list開始合併所有子串列(先接pivot，再左子list，最後右子list)
### 測驗`2`
#### 首先了解 [digit by digit](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg?view#%E6%AA%A2%E8%A8%8E%E7%AC%AC%E4%BA%8C%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)，單純加減位移求平方根法
`clz32`
```c
static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};
unsigned clz2(uint32_t x, int c)
{
if (!x && !c)
return 32;
uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));
if (c == 3)
return upper ? magic[upper] : 2 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}
```
1. edge check 一開始x就是空的case
2. 依照c遞迴層數將 x 分為高位部分 upper 和低位部分 lower
- lower 取的部分應隨c增加，取 16、8、4、2。因此 mask[] 為 {0,8,12,14}
- c = 0：mask[0] = 0，遮罩 0xFFFF >> 0 = 0xFFFF（16 位）。
- c = 1：mask[1] = 8，遮罩 0xFFFF >> 8 = 0x00FF（8 位）。
- c = 2：mask[2] = 12，遮罩 0xFFFF >> 12 = 0x000F（4 位）。
- c = 3：應提取 2 位元，0xFFFF >> 14 = 0x0003，故 GGGG = 14
- upper 亦隨c增加，取 16、8、4、2
3. 當c == 3時upper、low取的是2 bit的值，也就是我們設計切割的最小單位。且magic[]為根據數值給leading zero數的查表
4. 若 upper 不為 0，遞迴處理 upper；若 upper 為 0，則累加高位的前導零數 (16 >> c)，並遞迴處理 lower (有upper就整場只看upper，否則看lower)
##### 驗證
以 `0x0001F000` 為例：
```c
c = 0：upper = 0x0001, lower = 0xF000，因 upper != 0，呼叫 clz2(0x0001, 1)。
c = 1：upper = 0x00, lower = 0x01，因 upper == 0，返回 16 >> 1 + clz2(0x01, 2) = 8 + clz2(0x01, 2)。
c = 2：upper = 0x00, lower = 0x01，因 upper == 0，返回 16 >> 2 + clz2(0x01, 3) = 4 + clz2(0x01, 3)。
c = 3：upper = 0x00, lower = 0x01，因 upper == 0，返回 0 + magic[1] = 0 + 1 = 1。
總計：8 + 4 + 1 = 13，符合 0x0001F000 的前導零數。
```
`clz64`
```c
static inline int clz64(uint64_t x)
{
/* If the high 32 bits are nonzero, count within them.
* Otherwise, count in the low 32 bits and add 32.
*/
return (x >> 32) ? clz32((uint32_t) (x >> 32)) : clz32((uint32_t) x) + 32;
}
```
`sqrti`
```c
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
/* clz64(x) returns the count of leading zeros in x.
* (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
* Rounding that index down to an even number ensures our starting m is a
* power of 4.
*/
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
返回值y : x的整數平方根，即 $[\sqrt x]$
`m` : mask，用於測試當前位元的貢獻
`y`：累積的平方根結果，初始值為 0
`shift`：用於計算初始遮罩 m 的位移量
```c
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
```
`total_bits - 1 - clz64(x)` ：取得 x 最高有效位的索引
`& ~1` ：將數值的最右邊一位 (最低位) 清零，確保結果為偶數
* `m = 1ULL << shift` ：初始化變數 `m` 為一個 4 的次方數 $4^k$
* `1ULL`：代表 1，並確保它是 `uint64_t` 類型 (unsigned long long)
* `shift`：是一個偶數，確保 `m` 是 $4^k$（平方數）
* `1ULL << shift`：將 1 左移 `shift` 位，等於 $2^{shift}$
**逐位逼近計算平方根**
```c
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
```
* 初始化 `m` 為 $4^k$，從最高位開始測試。
* 每次迴圈：
* `b = y + m`，嘗試將 `m` 加到 `y` 中。
* `y >>= 1`，將 y 右移一位，準備更新平方根的估計值。
* 如果 `x >= b`，說明 `b*b` 不超過 `x`，則：
* `x -= b`，更新剩餘數值。
* `y += m`，將 `m` 加到 `y` 中，表示這一位是有效的平方根部分。
* `m >>= 2`，每次 `m` 右移 `2` 位，因為平方數每次變化是 $4^n$。
節錄自 [liangchingyun](https://hackmd.io/lDt_J9PNStS3hNMT6P2hyg?both)
**範例分析**
```c
x = 36 (0b100100)
```
1. 初始化
```c
clz64(36) = 58 // 36 的二進位是 `0000...00100100`
shift = 4 // 64 - 1 - 58 = 5 // 5 & ~1 = 4`
m = 16 (0b10000) // m = 1 << 4 = 16
y = 0
```
2. 第一輪
```c
b = y + m // 0 + 16 = 16
y >>= 1 // y 仍為 0
x >= b // (36 >= 16) → x -= 16 → x = 20
y += m // y = 16
m >>= 2 // m = 4
```
3. 第二輪
```c
b = y + m // 16 + 4 = 20
y >>= 1 // y = 8
x >= b // (20 >= 20) → x -= 20 → x = 0
y += m // y = 12
m >>= 2 // m = 1
```
4. 第三輪
```c
b = y + m // 12 + 1 = 13
y >>= 1 // y = 6
x < b // (0 < 13) → x 不變
m >>= 2 // m = 0（迴圈結束）
```
最後 `y = 6`，即 `sqrt(36) = 6`。
### 測驗 `3`
#### 背景
LeetCode 的 Two Sum 問題要求在給定陣列 nums 和目標值 target 中，找到兩個元素的索引，使得它們的和等於 target。題目保證有且僅有一個解，且索引順序無關緊要。使用暴力法時間複雜度為 $O(n^2)$，顯然效率不高，因此我們採用 hash table 來優化至 O(n)
#### hash table struct
``` c
typedef struct {
int bits;
struct hlist_head *ht;
} map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
- `ht` 是包含多個 hlist_head 的陣列。每個 hlist_head.first 是對應 bucket 的開頭，指向該 bucket 的第一個 hlist_node
- bucket 就像一個「籃子」，裡面裝的是具有相同 hash 值的資料，在 hash table（雜湊表）中，bucket 是一個存儲單元（可以想像成一個「槽位」）。
- `bits` : 存儲 hash table 的位元數，用來計算 bucket 的總數。例如，若 bits 為 4，則 bucket 數量為 $2^4=16$
- `hash_key` 代表 hash table 中的一個鍵值對節點(bucket 內linked list中的一個節點)
#### auxiliary function
##### `map_init` : 創建並初始化 hash table
```c
map_t *map_init(int bits)
{
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
if (map->ht) {
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
- 使用 malloc 分配 map_t 結構的記憶體。若分配失敗，返回 NULL 表示錯誤。
- 設置參數：
- map->bits = bits，記錄 hash table 大小的位元數（後續用於計算 bucket 數量）。
- 分配 ht 陣列（hash table 的主結構），大小為 MAP_HASH_SIZE(map->bits)，通常定義為 $2^{bits}$
- 初始化 bucket：
- 若 ht 分配成功，遍歷每個 bucket，將其 first 指針設為 NULL，表示該 bucket 初始為空。
- 若 ht 分配失敗，釋放已分配的 map 記憶體，並將 map 設為 NULL。
- 返回值：
返回指向初始化好的 map_t 結構的指針，或在失敗時返回 NULL。
##### linux hash function
```c
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
輸入是key(val)輸出是索引
##### 檢索 `find_key` : 查找特定 key 的節點
```c
static struct hash_key *find_key(map_t *map, int key)
{
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
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 table 中查找特定鍵 key，返回對應的 hash_key 結構指針，若未找到則返回 NULL
##### 流程 :
- 定位 bucket：
使用 hash(key, map->bits) 計算 key 的 hash 值，獲取對應 bucket 的 hlist_head。
- 遍歷一bucket linked list：
從 head->first 開始，沿著 hlist_node 的 next 指針遍歷該 bucket 的鏈表。
對於每個節點，使用 container_of 宏從 hlist_node 獲取包含它的 hash_key 結構。
- 比對鍵：
若某個 hash_key 的 key 與輸入的 key 相等，返回該結構的指針。
- 未找到的情況：
若遍歷結束仍未找到匹配的鍵，返回 NULL。
##### `map_add` : 插入新 key 值對並維護 map
```c
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, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
$h->first = n;
n->pprev = &h->first;
}
```
###### 功能
map_add 將一個新的鍵值對 (key, data) 加入 hash table。
###### 實現細節
- 檢查重複：
先調用 find_key 檢查 key 是否已存在，若存在則直接返回，不插入重複鍵。
- 分配節點：
若 key 不存在，分配一個新的 hash_key 結構，設置 kn->key = key 和 kn->data = data。
- 定位 bucket：
使用 hash(key, map->bits) 計算 bucket 索引，獲取對應的 hlist_head。
- 插入bucket linked list開頭：
將新節點 n（即 kn->node）插入到 bucket 的linked list開頭：
- n->next 指向原來的 first。
- 若 first 不為空，更新 first->pprev 指向 n->next 的地址。
- 更新 h->first 為新節點 n。
- 設置 n->pprev 指向 h->first 的地址，維護雙向鏈接。
`map_deinit` : 釋放所有記憶體
```c
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 = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map->ht);
free(map);
}
```
##### 功能
map_deinit 釋放 hash table 及其所有節點的記憶體。
##### 實現細節
- 空檢查：
若 map 為 NULL，直接返回。
- 遍歷所有 bucket：
遍歷 `map->ht` 的每個 bucket（總數為 `MAP_HASH_SIZE(map->bits)`）。
- 釋放每個節點：
對於每個 bucket，從 head->first 開始遍歷鏈表：
- 使用 container_of 獲取 hash_key 結構。
- 記錄當前節點 n，並移動指針 p 到下一個節點。
- 若 n->pprev 為空（表示未被 hash），跳到 bail 直接釋放。
- 否則，執行移除操作：
- 更新前一節點的 next 指針（*pprev = next）。
- 若 next 存在，更新 next->pprev 指向 pprev。
- 將 n->next 和 n->pprev 設為 NULL，完成移除。
- 釋放 kn->data 和 kn 的記憶體。
- 釋放 hash table：
最後釋放 map->ht 陣列和 map 結構。
#### 主程式
`twoSum`
```c
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
if (!ret)
goto bail;
for (int i = 0; i < numsSize; i++) {
int *p = map_get(map, target - nums[i]);
if (p) { /* found */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
bail:
map_deinit(map);
return ret;
}
```
##### 功能
twoSum 解決 Two Sum 問題，找到陣列 nums 中和為 target 的兩個元素的索引，返回包含這兩個索引的陣列。
##### 實現細節
- 初始化：
- 使用 map_init(10) 創建 hash table（大小為 $2^{10}=1024$ )
- 設置 *returnSize = 0，初始化返回陣列大小。
- 分配返回陣列 ret（大小為 2），若失敗則跳到 bail。
- 遍歷陣列：
對於每個 nums[i]：
- 計算 target - nums[i]，並使用 map_get（假設存在，返回 data）查找是否有匹配的鍵。
- 若找到（p 不為 NULL），表示存在 nums[j] 使得 nums[i] + nums[j] == target：
- 設置 ret[0] = i（當前索引），ret[1] = *p（之前存儲的索引）。
- 設置 *returnSize = 2，結束循環。
- 若未找到：
- 分配一個 int 記憶體，存儲當前索引 i。
- 將 (nums[i], p) 插入 hash table。
- 清理：
無論是否找到解，跳到 `bail` 釋放 map。
Sign in with Wallet
Connect another wallet