# 2025q1 Homework2 (quiz1+2)
> contributed by <[davidshiao55](https://github.com/davidshiao55)>
## 2025q1
### 測驗 `1`
實作 `list_insert_before` 函式，其中測試程式碼，測試插入鏈結串列的頭和尾且利用串列大小和出入數列的排列來檢查程式碼執行結果。
```c
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;
}
```
實作同[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)中 `remove_list_node` 的做法，使用間接指標避免考慮特例情況：`before` 節點為 `head`。
當使用間接指標 `p` 指向 `head` 時可不用考慮是否需要更動 `head`，且不用紀錄一個 `prev` 指標執行插入並維持串列結構，在迴圈中每次迭代只需將 `p` 指向節點的 `next`，直接更動當前節點的 `next` 指標即可。
```c
static inline void list_insert_before (list_t *l, list_item *before, list_item *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
```
原始實作：當插入節點為第一個節點是會有例外情況產生，需要改變 `head` 指標
```graphviz
digraph LinkedList {
rankdir=LR; // Left to right
node [shape=record];
head [label="HEAD", shape=none];
// First node in the list
node0 [label="{ 10 | next }"];
node1 [label="{ 20 | next }"];
node2 [label="{ 30 | next }"];
node3 [label="{ 40 | NULL }"];
head -> node0;
// Continue the linked list
node0 -> node1;
node1 -> node2;
node2 -> node3;
}
```
間接指標實作：直接更改 `indirect` 避免掉了例外情況
```graphviz
digraph LinkedList {
rankdir=LR; // Left to right
node [shape=record];
indirect [label="INDIRECT", shape=none]
head [label="HEAD", shape=none];
// First node in the list
node0 [label="{ 10 | next }"];
node1 [label="{ 20 | next }"];
node2 [label="{ 30 | next }"];
node3 [label="{ 40 | NULL }"];
indirect -> head;
head -> node0;
// Continue the linked list
node0 -> node1;
node1 -> node2;
node2 -> node3;
}
```
原始實作：當插入節點到串列中時需維持一個 `prev` 指標來插入節點維持串列結構。
```graphviz
digraph LinkedList {
rankdir=LR; // Left to right
node [shape=record];
prev [label="PREV", shape=none];
curr [label="CURR", shape=none];
head [label="HEAD", shape=none];
// First node in the list
node0 [label="{ 10 | next }"];
node1 [label="{ 20 | next }"];
node2 [label="{ 30 | next }"];
node3 [label="{ 40 | NULL }"];
head -> node0;
prev -> node1;
curr -> node2;
// Continue the linked list
node0 -> node1;
node1 -> node2;
node2 -> node3;
}
```
間接指標實作：透過間接指標直接指向前一個節點的 `next` 直接更動 `next` 指標。
```graphviz
digraph LinkedList {
rankdir=LR; // Left to right
node [shape=record];
indirect [label="INDIRECT", shape=none]
head [label="HEAD", shape=none];
// First node in the list
node0 [label="{ 10 | next }"];
node1 [label="{ 20 | next }"];
node2 [label="{ 30 | <n> next }"];
node3 [label="{ 40 | NULL }"];
indirect -> node2:n;
head -> node0;
// Continue the linked list
node0 -> node1;
node1 -> node2;
node2 -> node3;
}
```
## 測驗 `2`
此程式依照 Binary Search Tree 的刪除節點方式，當刪除一個節點時會產生幾種不同情況：
1. 刪除節點為 leaf：直接刪除節點即可。
```graphviz
digraph Tree {
node [shape=circle];
// Original Tree
"50" -> "30";
"50" -> "70";
"30" -> "20";
"30" -> "40";
"70" -> "60";
"70" -> "80";
// Highlighting the removal of "20"
"20" [color=red, style=filled];
}
```
對應程式碼：
```c
else {
/* No children: remove the node. */
*node_ptr = NULL;
}
```
2. 刪除節點有一個非空子樹：刪除節點並讓其子樹取代原本位置。
```graphviz
digraph Tree {
node [shape=circle];
// Original Tree
"50" -> "30";
"50" -> "70";
"30" -> "20";
"20" -> "25";
"70" -> "60";
"70" -> "80";
// Highlight the node to be removed
"20" [color=red, style=filled];
}
```
對應程式碼：
```c
/* If the target node has one child, 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;
}
```
3. 刪除節點有兩非空子樹：尋找刪除節點 inorder predecessor 取代刪除節點。當中又分兩種情況，當 predecessor 是刪除節點的左子節點，或是在左子樹更深層。
```c
/* 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;
```
(1) 當 predecessor 是刪除節點的左子節點：用 predecessor 取代刪除節點後重新接上刪除節點的右子樹。
``` graphviz
digraph Tree {
node [shape=circle];
// Original Tree
"50" -> "30";
"50" -> "70";
"30" -> "20";
"30" -> "40";
"40" -> "35";
"70" -> "60";
"70" -> "80";
// Highlight the node to be removed
"30" [color=red, style=filled];
"20" [color=blue, style=filled];
}
```
對應程式碼：
```c
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);
}
```
(2)當 predecessor 在左子樹更深層中：將 predecessor 移除原本位置，再取代刪除節點，並接上刪除節點的左右子樹。
```graphviz
digraph Tree {
node [shape=circle];
// Original Tree
"50" -> "30";
"50" -> "70";
"30" -> "20";
"30" -> "40";
"40" -> "35";
"70" -> "60";
"70" -> "80";
"20" -> "25";
// Highlighting the node to be removed
"30" [color=red, style=filled];
"25" [color=blue, style=filled];
}
```
對應程式碼：
```c
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);
}
```
## 測驗 `3`
使用 linux list api 實作迭代快速排序法。
測試程式碼透過 `shuffle` 和 `list_is_ordered` 來檢測排序演算法的正確性。`shuffle` 演算法類似 lab0 中的 Fisher-Yates shuffle。
```c
/* shuffle array, only work if n < RAND_MAX */
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;
}
}
```
由於 linux kernel linked list 採用雙向環狀鏈結串列，在實作排序時不好維護，實作中先斷開環狀結構且只維護單向的鏈結串列，所以在排序後需重新建構環狀雙向鏈結串列。
```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;
}
```
有別於 [Optimized Quicksort](https://alienryderflex.com/quicksort/) 的實作，只維護 `begin` 一堆疊，使用 `list_tail` 在每次迴圈中重找 `end`，犧牲時間來換取空間的策略。
```diff
- node_t *begin[max_level], *end[max_level];
+ struct list_head *begin[max_level];
- node_t *L = begin[i], *R = end[i];
+ struct list_head *L = begin[i], *R = list_tail(begin[i]);
```
其餘操作同 [Optimized Quicksort](https://alienryderflex.com/quicksort/):
1. 將 `L` 和 `R` 指向當前堆疊上的兩端
2. 當 `L` 和 `R` 未相遇前，設最左邊元素為 `pivot` 使用指標 `p` 走訪當前堆疊上的串列將小於 `pivot` 的節點至於 `left` 串列，大於的至於 `right` 串列
3. 將 `left`，`pivot`，`right` 推上堆疊。
演算法分析：遞迴的快速排序透過分割再遞迴操作左右兩個分割來實作，在迭代快速排序中使用區域變數 `begin` 堆疊陣列來模擬遞迴呼叫。這個實作在時間複雜度仍跟遞迴呼叫一樣，但可以避免掉函式呼叫時間，空間複雜度則因為要確保在 Worst Case 也正確執行，必須讓堆疊空間寫死在 $O(n)$ 失去了遞迴呼叫中的平均 $O(logn)$。
## 2025q2
### 測驗 `1`
linux list api 遞迴快速排序法實作，將 `head` 的 `list_first_entry` 設為 `pivot` ，與第一次測驗中實作方法相同將大於 `pivot` 的插入一個串列，小於 `pivot` 的插入另一個串列，最後再用 `list_add`，`list_splice` 和 `list_splice_tail` 重構串列。
`list_for_each_entry_safe` 建構的迴圈中，若將 `list_move_tail` 換為 `list_move`，為何會無法滿足 stable sorting：`list_move` 會將插入元素加到串列的頭，但我們走訪原串列時是由左而右，若遇到相同元素則會造成 unstable。
改進 random_shuffle_array：使用 Fisher Yate 實作
```c
static inline void random_init_array(uint16_t *operation, uint16_t len)
{
// Step 1: Fill arr in ascending order
for (uint16_t i = 0; i < len; i++)
operation[i] = i;
// Step 2: Fisher–Yates shuffle
for (uint16_t i = 0; i < len; i++) {
// pick a random index from [0..i]
uint16_t j = get_unsigned16() % (i + 1);
// swap arr[i] and arr[j]
uint16_t tmp = operation[i];
operation[i] = arr[j];
operation[j] = tmp;
}
}
```
### 測驗 `2`
`clz2` 藉由 binary search 的方式尋找 leading zero。
mask：每次 shift 的量會是前一次的 $+2^{4-c}$，c 為 0 的時候不 shift。
0 -> 8 -> 12 -> 14
magic：剩兩 bit 的時候的最後結果
00 -> 2 + 2
01 -> 2 + 1
10 -> 2 + 0
11 -> 2 + 0
`sqrti` 先指出小於 x 的最小的 power of 4，利用 clz64 找出 MSB 的位元再對 ~1 做 mask 清除 LSB。
Sign in with Wallet
Connect another wallet