# 2025q1 Homework2 (quiz1+2)
contributed by < [otischung](https://github.com/otischung) >
## [Quiz 1](https://hackmd.io/@sysprog/linux2025-quiz1)
### [測驗 1-1](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-1)
補完之程式碼如下所示
```cpp=
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
/**
* Inserts a new item into the list before a specified item.
*
* This function traverses the list to locate the position immediately before the item pointed to by @before and inserts @item in that position.
* The time complexity is O(n), where n is the number of stepsneeded to reach @before fromthe head of the list.
*
* Parameters:
* @l : Pointer to the list.
* @ before : Pointer to the item before which the new item should be inseted.
* - If @before is the head of the list, the new item is inserted at the front.
* - If @before is NULL, the new item is appended to the end of the list.
* - In all other cases, behavior is undefined if @before does not belong to @l.
* @item : The new list item to be inserted.
*/
static inline void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next) // AAAA, BBBB, CCCC
;
*p = item;
item->next = before; // DDDD
}
```
由於 `l->head` 與 `list_item_t *before` 都是 `struct list_item *`，因此我們只需要紀錄這些指標的位址，透過 dereference 即可操作該記憶體內容。
因此，我們的操作步驟如下：
1. 從頭開始，鏈結串列是由 `l->head` 所紀錄，其型態是 `list_item_t *`，故其位址為 `&l->head`，其型態是 `list_item_t **`。
2. 搜尋 `*p` 是否等於目標 `before`，若相同則下一步，若不同則將 `*p` 的下一個 `(*p)->next` 的位址紀錄起來 `&(*p)->next`。
3. 將 `*p` 所指之處放入 `item`，並將 `item->next` 記成 `before`。
我們分析以下三種情況
1. 插入在鏈結串列之頭
這種情況的話，`p = &l->head`，因此，執行插入的時候，`*p = l->head = item`，再把 `item->next` 紀錄成 `before`，也就是之前的頭。
2. 插入在鏈結串列之中間部份
3. 插入在鏈結串列之尾
這種情況的話，`before = NULL`，所以最後 `*p = NULL`，`**p` 指向最後一個元素的位址，因此將最後一個元素的 `next`，也就是 `*p`，指向 `item`，並將 `item` 的下一個指向 `NULL`，而此時 `before = NULL`，因此不違反原先的設定。
由此證明，以上程式碼具有一般性，不須做其他額外處理。
### [測驗 1-2](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-2)
補完之程式碼如下所示
```cpp
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) // EEEE
pred_ptr = &(*pred_ptr)->r; // FFFF
...
}
...
}
```
要找到最右邊的 node，就從左邊一路掃到右邊就可以了。
### [測驗 1-3](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)
補完之程式碼如下所示
```cpp
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
}
void quick_sort(struct list_head *head)
{
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);
}
```
首先，`rebuild_list_link()` 只在 `quick_sort()` 最後一行執行，而觀察 `quick_sort()` 只有處理 `next`，並未處理 `prev`，因此判定此 `rebuild_list_link()` 是為了補上 `prev`。
因此，我們定義 `prev` 為第一個元素，`node` 為第二個元素，透過雙向環狀 linked-list 依序處理，即可推斷 GGGG 為何。
HHHH 與 IIII 皆是利用 `container_of` macro 取得 `node_t` 的位址，再取得該 node 的值。
JJJJ 與 KKKK 皆為圖例所示，依序為 `left`, `pivot`, 與 `right`。
## [Quiz 2](https://hackmd.io/@sysprog/linux2025-quiz2)
### [測驗 2-1](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-1)
補完之程式碼如下所示
```cpp
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); // AAAA
list_del(&pivot->list); // BBBB
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); // CCCC
}
list_quicksort(&list_less);
list_quicksort(&list_greater);
list_add(&pivot->list, head); // DDDD
list_splice(&list_less, head); // EEEE
list_splice_tail(&list_greater, head); // FFFF
}
```
其實對於 AAAA 來說，選擇 pivot 可以是任意的，不過在選項中，可以使用 `container_of` 得出「一個」 node 的 macro，只有 `list_first_entry`，那麼他就是唯一解。
與[測驗 1-3](#測驗-1-3) 不同的是，這裡使用遞迴的方式實作，額外準備兩個 list 做遞迴。
取出 pivot 後，將 pivot 移出 list，之後將每個 node 與 pivot 作比較，分別移入兩個 lists。
至此，原本的 head 已經沒有東西了。
遞迴解完之後，先把 pivot 放回 head，再把左邊 list 插入頭段，最後把右側 list 插入尾段。
### [測驗 2-2](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-2)
補完之程式碼如下所示
```cpp
static const int mask[] = {0, 8, 12, 14}; // {0, 8, 12, GGGG}
static const int magic[] = {2, 1, 0, 0}; // {HHHH, 1, 0, IIII}
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) // JJJJ
return upper ? magic[upper] : 2 + magic[lower]; // KKKK
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1); // LLLL
}
#define clz32(x) clz2(x, 0)
```
這個實作是使用遞迴呼叫求解 counting leading zero，直到剩下 2 bits 為止。
每次都將目前的位元平分成 upper 與 lower
| c | upper/lower 位元數 |
| - | ----------------- |
| 0 | 16 |
| 1 | 8 |
| 2 | 4 |
| 3 | 2 |
- 當 upper 非 0，則繼續尋找 upper，忽略 lower。
- 當 upper 為 0，則繼續尋找 lower，將目前 upper 的位元數加進來。
當 `c == 3` 時，則 upper 與 lower 只剩下 `0b00`, `0b01`, `0b10`, `0b11` 三種可能，而這些數字的開頭分別有 `{2, 1, 0, 0}` 個 0，因此，當 `c == 3` 時，
- 當 upper 非 0，則返回 upper 有幾個 0。
- 當 upper 為 0，則返回 lower 有幾個 0，加上 upper 的部分，有 2 個 0。
接下來，我們補完開平方根的程式碼
```cpp
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; // MMMM
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1; // NNNN
if (x >= b) {
x -= b;
y += m;
}
m >>= 2; // PPPP
}
return y;
}
```
我們的目標是要找到一個最大的數字 $y$ 使得 $y^2 \le x$。
我們知道對於所有正整數與 0 可以以二進位表示，即
$$
y = a_n 2^n + a_{n-1} 2^{n-1} + ... + a_1 2^1 + a_0 2^0
$$
對於所有 $n$ 為正整數或 0，$a_n$ 為 0 或 1。
因此，對於所有 $y$，找到最大的 $n$ 使得 $(2^n)^2 \le x$，由此開始進行二分搜尋法，繼續尋找 $n - 1$, $n - 2$, ..., $1$, $0$，即可得到
$$
y^2 = (a_n 2^n + a_{n-1} 2^{n-1} + ... + a_1 2^1 + a_0 2^0)^2 \le x
$$
由於我們總是從 $(2^n)^2 = 4^n$ 開始搜尋，因此 `shift` 必定是偶數，而又因為我們的起始項不超過 $x$，因此我們總是向下取偶數，這等同於將 LSB mask 成 0，即 `& ~1`。
接下來，我們看一下 $x = 170$ 的例子，170 在二進位表示成 `0xAA`，因此 `shift == 6`，此時我們有 $m = (2^3)^2$, $y = 0$, $b = y + m = (2^3)^2$，
$$
64 = (2^3)^2 \le 170
$$
由於 $64 \le 170$，所以 $y = 2^3$。
接下來，我們搜尋 $(2^3 + 2^2)^2 \le 170$ 是否正確
$$
144 = (2^3 + 2^2)^2 \le 170
$$
$$
196 = (2^3 + 2^2 + 2^1)^2 > 170
$$
$$
169 = (2^3 + 2^2 + 2^0)^2 \le 170
$$
我們將等式做展開
$$
\begin{aligned}
144 = (2^3 + 2^2)^2 &\le 170 \\
144 = (2^3)^2 + (2(2^3) + (2^2)) (2^2) &\le 170 \\
144 - (2^3)^2 = 2(2^3)(2^2) + (2^2)^2 &\le 170 - (2^3)^2 \\
80 = 2(2^3)(2^2) + (2^2)^2 &\le 106 \\
196 = (2^3 + 2^2 + 2^1)^2 &> 170 \\
196 = (2^3 + 2^2)^2 + 2(2^3 + 2^2)2^1 + (2^1)^2 &> 170 \\
169 = (2^3 + 2^2 + 2^0)^2 &\le 170
\end{aligned}
$$
Sign in with Wallet
Connect another wallet