# 2024q1 Homework2 (quiz1+2)
**contributed by < `RRbell1027` >**
## 第 1 週測驗題
### 測驗 1
首先看到鏈結串列結構體：
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
* 由於測驗一中沒有用到 `left` 和 `right` ，所以暫且忽略。
```graphviz
digraph example {
rankdir=LR;
node[shape=none, label=<<table border="0" cellspacing="0">
<tr>
<td port="value" border="1">value</td>
<td port="next" border="1">next</td>
</tr>
</table>>];
a:next -> b;
b:next -> c;
c:next -> null;
}
```
#### AAAA:
分析鏈結串列的操作函式：
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
* 從函數名稱，推測是回傳**鏈結串列的最後一個節點的指標**。
* 常見的演算法為：利用 `next` 指標判斷當前節點是否為最後一個節點，進而用 `while` 迴圈從第一個指標訪問到最後一個指標。
* 因此，迴圈中指派給 `left` 的值為**指向下個節點的指標**的地址 `&((*left)->next)`。
```graphviz
digraph example {
rankdir=LR;
node[shape=none, label=<<table border="0" cellspacing="0">
<tr><td port="value" border="1">value</td>
<td port="next" border="1">next</td></tr>
</table>>];
headptr[shape=rect, label="head"]
left[shape=rect, label="left"]
null[label="null"]
left -> headptr [constraint=false];
headptr -> a;
a:next -> b;
b:next -> c;
c:next -> null;
}
```
```graphviz
digraph example {
rankdir=LR;
node[shape=plaintext, label=<<table border="0" cellspacing="0">
<tr><td port="value" border="1">value</td>
<td port="next" border="1">next</td></tr>
</table>>];
headptr[shape=rect, label="head"]
left[shape=rect, label="left"]
null[label="null"]
left -> a:next [constraint=false];
headptr -> a;
a:next -> b;
b:next -> c;
c:next -> null;
}
```
#### BBBB:
分析以下鏈結串列操作函式：
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
* 從函式名稱推測功能為回傳鏈結串列長度。
* 每訪問一個節點計數器 `n` 加一。
* 與上題相同，left 要被指派**指向下一個節點的指標**的地址 `&((*left)->next)`。
#### CCCC, DDDD, EEEE:
* 首先分析非遞迴快速排序法[Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)：
* 函數利用 `begin` 和 `end` 兩個堆疊儲存遞迴呼叫時的引數，分別代表著該次呼叫要處理的陣列的第一個索引和最後一個索引。
```diff
- sort(arr, beg, l);
- sort(arr, r, end);
+ beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; /* beg[i] doesn't change */
```
* 接者分析鏈結串列的改寫：
```c
list_add(n->value > value ? &right : &left, n);
```
* 鏈結串列並非像陣列一樣通過元素互換將元素二分到陣列前後。而是將鏈結串列**拆分成兩個鏈結串列**，在各自做排序。
```graphviz
digraph {
rankdir=LR;
node[shape=rect];
pivot[shape=none]
3->2->4->5->1;
pivot->3[constraint=false]
}
```
* 變成：
```graphviz
digraph {
node[shape=none];
{node[shape=rect]; rank="same"; 2->1; 3; 4->5;}
pivot->3;
left->2;
right->4
}
```
* 結合上述分析，`DDDD` 和 `EEEE` 為 `left` 和 `right` 鏈結串列的最後一個節點的指標。
```graphviz
digraph {
node[shape=none];
{node[shape=rect]; rank="same"; 2->1; 3; 4->5;}
pivot->3;
left->2;
right->4;
DDDD->1;
EEEE->5;
}
```
```c
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = lsit_tail(&right);
```
* 而 `CCCC` 則是 p 的下一個節點的指標：
```c
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
#### list_head API 實作版：
* 改寫 `node_t` 結構體，讓 `list.h` 支援 `node_t`：
```diff
typedef struct __node {
struct __node *left, *right;
- struct __node *next;
+ struct list_head *list;
long value;
} node_t;
```
* 刪除測驗 1 程式碼中的 `end` 堆疊：
* 這個堆疊只用來存放鏈結串列尾節點，大可以在下一次的迭代中尋找。
* 利用 `list_is_singular` 和 `list_empty` 取代 `begin[i] == end[i]` 的判斷。
```diff
- 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);
+ stk[i] = left;
+ stk[i+1] = mid;
+ stk[i+2] = right;
```
* 利用 `list_for_each_entry_safe` 取代 `while(p)` 迴圈。
```diff
- while (p) {
- node_t *n = p;
- p = p->next;
+ node_t *node, *safe;
+ list_for_each_entry_safe (node, safe, li, list) {
```
* 快速排列排列完整程式碼：
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
/* q_size returns the size of @head */
int i = 0, size = q_size(head);
LIST_HEAD(result);
struct list_head **stk = malloc(size * sizeof(struct list_head *));
stk[i] = head;
while (i >= 0) {
struct list_head *li = stk[i];
if (list_empty(li)) {
i--;
continue;
}
if (list_is_singular(li)) {
list_add(li->next, &result);
i--;
continue;
}
struct list_head *left = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(left);
struct list_head *mid = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(mid);
struct list_head *right = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(right);
node_t *pivot = list_first_entry(li, node_t, list);
list_del(&pivot->list);
list_add(&pivot->list, mid);
long value = pivot->value;
node_t *node, *safe;
list_for_each_entry_safe (node, safe, li, list) {
list_del(&node->list);
list_add(&node->list,
((value > node->value) ^ descend) ? left : right);
}
stk[i] = left;
stk[i+1] = mid;
stk[i+2] = right;
i += 2;
}
list_splice(&result, head);
}
```
---
### 測驗 2
#### AAAA：
```c
struct list_head *head;
struct list_head **tail = &head; /* AAAA */
/* merge two list */
return head;
```
* 因為中間合併演算法中沒有 `head` 只有 `tail` ，判斷 `tail` 被指派了 `head` 或 `head->next` 的地址。因為 `head` 尚未被分配空間，因此不可能是 `head->next`。
#### BBBB, CCCC:
* 這裡的合併邏輯類似 galloping mode ，比較兩鏈結串列的頭指標，將較小的(假設升冪排列)元素放進暫存鏈結串列中：
```graphviz
digraph {
rankdir = LR
{
node[shape=rect]; 1; 4; 5;
3[fillcolor=gray, style=filled];
2[fillcolor=gray, style=filled];
};
{node[shape=none]; a; b; tmp;};
tmp->1;
a->2->5;
b->3->4;
}
```
* 例如上圖，$2 < 3$，所以將 $2$ 加入到 `tmp` 鏈結串列的尾端。
```graphviz
digraph {
rankdir = LR
{
node[shape=rect]; 1; 4; 5;
3[fillcolor=gray, style=filled];
2[fillcolor=gray, style=filled];
};
{node[shape=none]; a; b; tmp;};
tmp->1->2;
a->5;
b->3->4;
}
```
* 接著解析程式碼。推測出 `tail` 是 tmp 的末節點的 `next` 指標。
* BBBB 可以是 `&(*tail)->next` 或 `&a->next` ，根據表單答案選後者。
```c
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next; /* BBBB */
a = a->next;
```
* CCCC 同理：
```c
*tail = b;
tail = &b->next; /* CCCC */
b = b->next;
```
#### DDDD, EEEE:
* 註釋寫的很清楚，這兩行程式碼是為了將鏈結串列變回環狀鏈結串列。
* 也就是頭接尾，尾接頭。
```c
/* The final links to make a circular doubly-linked list */
tail->next /* DDDD */ = head;
head->prev /* EEEE */ = tail;
```
#### FFFF:
* `merge_force_collapse` 會確保剩下 $1$ 或 $2$ 個鏈結串列。
* 若剩下 $1$ 個，放回 `head`。 $2$ 個則還要再合併一次。
```c
if (stk_size <= 1 /* FFFF */) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
```
#### 分析 Timsort 程式碼：
* 程式碼利用排序時不需要用到 `prev` 的特性，把 `prev` 指標發揮的淋漓盡致。
* 先將單一鏈結串列拆分成數個已排序的鏈結串列，並利用頭節點的 `prev` 將其串在一起。
* 每個排序好的鏈結串列的大小會存放在第二個節點的`prev`。
* 例如：
```graphviz
digraph {
rankdir=LR;
node[shape=rect];
4->5->6->2->3->1 [label=next];
1->3->2->6->5->4 [label=prev];
}
```
* 在不經過 `merge_collapse` 下，將變成：
```graphviz
digraph {
rankdir=LR;
node[shape=rect];
4->5->6 [label=next]; 2->3[label=next];
1->2->4[constraint=false, label=prev];
{
node[shape=none];
size1[label=3];
size3[label=2];
null1[label=null];
null2[label=null];
null3[label=null];
}
5->size1[label=prev, constraint=false];
3->size3[label=prev, constraint=false];
6->null1[label=next];
3->null2[label=next];
1->null3[label=next];
}
```
* 過程中，將滿足條件的鏈結串列先合併。
* 合併結束後，呼叫 `build_prev_link` 將 `prev` 指標恢復正常。
---
## 第 2 周測驗題
### 測驗 1
#### AAAA:
* 看完[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)後觀察函式：
```graphviz
digraph {
rankdir=LR
splines=line;
node[shape=record];
h[label="h|<p>first"];
first_node[label="<h>first_node|{<p>pprev|<n>next}"];
n[label="<h>n|{<p>pprev|<n>next}"];
other[label="..."]
h:p->first_node:h;
first_node:p->h:p;
first_node:n->other;
}
```
* 函式回傳後，期望結果為：
```graphviz
digraph {
rankdir=LR
splines=line;
node[shape=record];
h[label="h|<p>first"];
first_node[label="<h>first_node|{<p>pprev|<n>next}"];
n[label="<h>n|{<p>pprev|<n>next}"];
other[label="..."]
h:p->n:h;
n:p->h:p;
n:n->first_node:h;
first_node:p->n:n;
first_node:n->other;
}
```
* 所以，結果為：
```c
if (h->first)
h->first->pprev = &n->next;
n->next = h->first; /* AAAA */
n->pprev = &h->first;
h->first = n;
```
#### BBBB:
```c
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, BBBB) {
```
* 由這兩行可以看出，雜湊函式採用求餘法，其中 `size` 是雜湊表的長度， `num` 是鍵值，碰撞採用單向鏈結串列處理。
* 所以 `BBBB` 是該鍵值對應到的鏈結串列頭節點，也就是 `&heads[hash]` 。
#### CCCC:
```c
hlist_for_each (p, BBBB) {
struct order_node *on = CCCC(p, struct order_node, node);
```
* 從參數判斷這是 `container_of` 巨集的重新定義，往前翻找可以找到 `list_entry` 。
#### DDDD:
```c
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, DDDD);
```
* 同 `BBBB` 。
#### 程式碼邏輯：
* 從前序排列的第一項可以得到子樹的樹根，第二項為右子樹樹根。
* 從中序排列可以得到左子樹和右子樹的節點和節點數。
* 藉由左子樹節點數，可以回推左子樹樹根。
```graphviz
digraph {
pre[shape=none, label=<<table border="0" cellspacing="0">
<tr>
<td>preorder: </td>
<td border="1" bgcolor="lightblue">3</td>
<td border="1" bgcolor="green">9</td>
<td border="1" bgcolor="green">5</td>
<td border="1" bgcolor="red">20</td>
<td border="1" bgcolor="red">15</td>
<td border="1" bgcolor="red">7</td>
</tr>
</table>>];
in[shape=none, label=<<table border="0" cellspacing="0">
<tr>
<td>inorder: </td>
<td border="1" bgcolor="green">9</td>
<td border="1" bgcolor="green">5</td>
<td border="1" bgcolor="lightblue">3</td>
<td border="1" bgcolor="red">15</td>
<td border="1" bgcolor="red">20</td>
<td border="1" bgcolor="red">7</td>
</tr>
</table>>];
}
```
```graphviz
digraph {
3->9->5;
3->20->15
20->7
}
```
* 利用雜湊表紀錄中序排列，以降低演算法搜尋中序時的時間複雜度。
### 測驗 2
#### EEEE:
```c
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
EEEE = pprev;
}
```
* 從函式名稱推測功能為刪除節點，例如：
```graphviz
digraph {
rankdir=LR
splines=line;
node[shape=record];
prev[label="<h>prev_node|{<p>pprev|<n>next}"];
n[label="<h>n|{<p>pprev|<n>next}"];
next[label="<h>next_node|{<p>pprev|<n>next}"];
prev:n->n:h;
n:p->prev:n;
n:n->next:h;
next:p->n:n;
}
```
* 變成
```graphviz
digraph {
rankdir=LR
splines=line;
node[shape=record];
prev[label="<h>prev_node|{<p>pprev|<n>next}"];
n[label="<h>n|{<p>pprev|<n>next}"];
next[label="<h>next_node|{<p>pprev|<n>next}"];
prev:n->next:h;
next:p->prev:n;
}
```
所以 `EEEE` 為 `next->pprev` 。
#### FFFF:
```c
struct list_head *pos, *n;
LRUNode *cache = list_entry(pos, LRUNode, FFFF);
```
* LRUNode 的定義
```c
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
* 唯一符合資料型態為 `list_head` 的子物件為 `link` 。
#### GGGG:
```c
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, link /*FFFF */);
list_del(GGGG);
free(cache);
}
free(obj);
```
* 程式碼會先把當前節點從鏈結串列中刪除再釋放記憶體空間。
* `GGGG` 是當前節點的指標(地址)，也就是 `pos` 或 `&cache->link` 。
#### HHHH:
```c
struct hlist_node *pos;
LRUNode *cache = list_entry(pos, LRUNode, HHHH);
```
* 同 `FFFF` ，找出 `LRUNode` 中資料型態為 `hlist_node` 的子物件，也就是 `node` 。
#### IIII:
```c
list_move(IIII, &obj->dhead);
```
* 程式碼目的是將最新使用過的雜湊值放到鏈結串列的頭節點，如此一來，尾節點就會是最久沒用過的節點。
* 因此，`IIII` 就是 `lRUCacheGet` 函式找到的節點的 `list_head` 指標(地址)： `&cache->link` 。
#### JJJJ:
```c
struct hlist_node *pos;
LRUNode *c = list_entry(pos, LRUNode, JJJJ);
```
* 同 `HHHH` 。
#### KKKK:
* 同 `IIII` ，`KKKK` 為 `&c->link` 。
#### 程式碼邏輯：
* LRUCache 目標是將最久沒使用的鍵值移除快取。
* 利用佇列紀錄鍵值最新的使用順序（在此，使用佇列這個名詞是因為 FIFO 的特性），雜湊表降低檢索的時間複雜度。
* 一個節點同時擁有佇列和雜湊表的鏈結串列。
* 例如：黑色為雜湊表的鏈結串列邊，紅色為佇列的邊：
```graphviz
digraph {
rankdir=LR
hlist[shape=record, label="<t>|<b>"];
hlist:t->2->4;
hlist:b->1;
2->1->4[color=red]
}
```
* 此圖鍵值的最新使用順序可以用佇列看出：$4$->$1$->$2$ 。優先移除 $4$ 的節點。
#### Linux Kernel 對 LRU Cache 的實作：
* 觀察到 [linux/include/linux/lru_cache.h](https://github.com/torvalds/linux/blob/master/include/linux/lru_cache.h#L164) 函式庫對 LRU Cache 的實作。
```c
struct lru_cache {
/* the least recently used item is kept at lru->prev */
struct list_head lru;
struct list_head free;
struct list_head in_use;
```
* `lru_cache` 將資源分成了三類(註釋取自 `struct lc_element`)：
```c
list is on one of three lists:
in_use: currently in use (refcnt > 0, lc_number != LC_FREE)
lru: unused but ready to be reused or recycled
(lc_refcnt == 0, lc_number != LC_FREE),
free: unused but ready to be recycled
(lc_refcnt == 0, lc_number == LC_FREE),
```
* 提供了以下幾個主要的 API：
* lc_create: 創建 LRU Cache ，並將所有資源放入 `free` 。
* lc_get: 請求特定資源，如果雜湊表中沒有，回收一個資源並分派出去，放入 `in_use`。
* lc_put: 資源使用完畢但是未來可能用到，將資源放入 `lru` 。
* lc_del: 資源使用完畢且不會再用到，將資源 free() 並放入 `free` 。
* 其中， `lc_get` 在分派新資源時，會調用 `lc_prepare_for_change` ，優先選擇 `free` 中的資源，若 `free` 為空，從 `lru` 選擇最後一個（最久沒被用過的）資源。
```c
if (!list_empty(&lc->free))
n = lc->free.next;
else if (!list_empty(&lc->lru))
n = lc->lru.prev;
```
* 舉個例子：DFTL (Demand-based Flash Translation Layer)
* 開機時，電腦會將**邏輯地址與物理地址的對照表 (FTL)** 從固態硬碟加載到記憶體中，加速電腦對固態硬碟資料的讀取。
* 然而，隨著固態硬碟容量的增加， FTL 的大小以達到 GB 級別，對記憶體造成很大的負擔。
* 因此，如今普遍只存放部分 FTL ，並利用 LRU Cache 機制更新記憶體上 FTL 內容。
* 若短時間內對同一筆資料做多次讀取，依舊可以保持原先的效率。
### 測驗 3
#### AAAA:
* 根據註釋，`__ffs` 函式功能是找出字元串從右數來的第一個 $1$ 。
* 程式碼邏輯類似二分搜尋法，利用字元串遮罩將字元串切半，判斷目標在字元串的左半還是右半 。
* 假設字串最大長度為 $8$
```graphviz
digraph {
a[shape=record, label="{x|x|x|x|x|x|x|x}"];
and[shape=none, label="&"]
b[shape=record, label="{0|0|0|0|1|1|1|1}"];
equal[shape=none, label="="]
c[shape=record, label="{0|0|0|0|x|x|x|x}"];
}
```
* 這個遮罩下，如果沒有 $1$ 在右半，字元串會變成 $0$ 。
* 類似的邏輯常用在子網路 ip 的區分上，利用子網路遮罩判斷兩個 ip 是否在同一個子網路底下。
```c
#if BITS_PER_LONG == 64
if ((word & AAAA) == 0) {
num += 32;
word >>= 32;
```
* 回到測驗程式碼，字串長度為 $64$ ，因此 `AAAA` 為 `0xffffffff` 。
#### BBBB:
* 從函式名稱推測為將特定字元清零。
```c
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
*p &= BBBB;
```
* `BIT_MASK` 會創造所有字元為 $0$ ，只有目標位元為 $1$ 的字元串。
* 目標是讓目標字元和 $0$ 做 AND 清零，其餘和 $1$ 做 AND 保持不變。
* 所以 `BBBB` 為 `~mask` 。
#### CCCC:
* 函式功能為找出字元串第 n 個 $1$ 的位置。
* 程式碼為了減少負擔，會在鎖定目標在長度 `BITS_PER_LONG` 的範圍中之後，再使用 `fns` 函式的 `while` 迴圈尋找。
* 方法為：先尋找前 `BITS_PER_LONG` 位元中有幾個 $1$ ，如果少於要求，再往後搜尋。
* 例如，假設一次搜索範圍為 $4$ 位元， n 為 $3$ ：
```graphviz
digraph {
rankdir=LR;
bit[shape=none, label=<<table border="0" cellspacing="0">
<tr>
<td border="1">0</td>
<td border="1">1</td>
<td border="1">1</td>
<td border="1">0</td>
<td border="1">0</td>
<td border="1">1</td>
<td border="1">0</td>
<td border="1">1</td>
<td bgcolor="gray" border="1">1</td>
<td bgcolor="gray" border="1">0</td>
<td bgcolor="gray" border="1">1</td>
<td bgcolor="gray" border="1">0</td>
</tr>
</table>>];
}
```
* 這裡只找到 $2$ 個 $1$ ，所以向後搜尋：
```graphviz
digraph {
rankdir=LR;
bit[shape=none, label=<<table border="0" cellspacing="0">
<tr>
<td border="1">0</td>
<td border="1">1</td>
<td border="1">1</td>
<td border="1">0</td>
<td bgcolor="gray" border="1">0</td>
<td bgcolor="gray" border="1">1</td>
<td bgcolor="gray" border="1">0</td>
<td bgcolor="gray" border="1">1</td>
<td border="1">1</td>
<td border="1">0</td>
<td border="1">1</td>
<td border="1">0</td>
</tr>
</table>>];
}
```
* 累積已經有 $4$ 個 $1$ 了，所以確認目標在這 $4$ 個位元內。
```c
if (sz CCCC BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);
```
* 這兩行指令發生在最後一次範圍搜索時：
* 如果 `size` 不是 `BITS_PER_LONG` 的倍數，就用 `fns` 函式
* 如果 `size` 是 `BITS_PER_LONG` 的倍數，表示上一次的搜索是最後一次，於是將 `tmp` 全部設成 $1$，`fns` 回傳 $0$ ，減少運算次數。
* 因此， `CCCC` 為 `%` 。
Sign in with Wallet
Connect another wallet