# 2024q1 Homework2 (quiz1+2)
contributed by < [yy214123](https://github.com/yy214123) >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 13th Gen Intel(R) Core(TM) i5-13600KF
CPU family: 6
Model: 183
Thread(s) per core: 2
Core(s) per socket: 14
Socket(s): 1
Stepping: 1
CPU max MHz: 5100.0000
CPU min MHz: 800.0000
BogoMIPS: 6988.80
Virtualization: VT-x
L1d: 544 KiB (14 instances)
L1i: 704 KiB (14 instances)
L2: 20 MiB (8 instances)
L3: 24 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-19
```
## 填寫 Google 表單時獲得的啟發
### Dangling Pointer
在 [基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/@sysprog/c-std-security) 的主題(二)中討論了有關 Dangling Pointer 的議題，其中提到：**在使用指標時，安全起見應該要記得將不用的指標在 free() 後設為 NULL。** 重新審視了我在 [lab0-c](https://github.com/yy214123/lab0-c) 的程式後，發現部份函式都有釋放指標的行為，而釋放後我卻沒有將其指向 NULL，如此會有造成 Dangling Pointer 的風險。
對此我進行了以下修改:
```diff
free(head);
+ head = NULL;
free(new);
+ new = NULL
```
## 第一周測驗
### 測驗一
```clike
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &((*left)->next);
return *left;
}
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &((*left)->next);
}
return n;
}
```
在這兩個函式中，我們處理的是一個鏈結串列結構，其中 node_t 是串列節點的結構定義。這些函式通過間接指標（即指向指針的指針）作為參數來操作鏈表。允許函式直接修改指向鏈表頭部的指針。
```list_tail``` 的目的是找到並回傳串列的最末節點。它透過迴圈遍歷串列，每次迭代都檢查當前節點的下一個節點是否存在。當下一個節點不存在時，當前節點即為串列的最末節點。
```list_length``` 的目的是計算串列中的節點數量。透過遍歷串列的每個節點，每遍歷一個節點就將計數器 n 增加 1。當遍歷完所有節點後，函式回傳計數器 n 的值即為串列的長度。
```clike
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 = p->next;
list_add(n->value > value ? &right : &left, n);
}
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;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
```
這邊花了很多時間來紙筆追蹤，一開始搞不懂他的邏輯，一直卡在 else 判別式的地方。後續仔細觀察 begin 各個索引指向的串列後，才逐漸理解整個架構的運作模式。
可將每三個 begin 索引看作一組處理單元，其中每組的中心點是一個基準值 （pivot），這個節點左側的串列包含所有小於基準值的節點，而右側則包含所有大於基準值的節點。演算法的執行流程傾向於先處理基準值右側的部分，也就是那些大於基準值的節點。對於大於基準值的每個部分，演算法繼續將其細分為更小的三元組（左、中、右），依此類推，直到只剩下單一節點。一旦某個大於基準值的部分被細分到只包含一個節點，該節點就會被加入到最終的 result 中 。
:::success
延伸問題:
1.解釋上述程式碼的運作原理，提出改進方案並予以實作。
:::
:::success
延伸問題:
2.使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
:::
#### 考慮時間複雜度
在 **worst case** 情況下，會因為 pivot 的緣故，導致快速排序的時間複雜度為 $\mathcal{O}(n^2)$，可以透過選擇更好的 pivot 來避免此問題。
**解決方法一**：以 Middle of three 挑選 pivot
```graphviz
digraph G {
node [shape=record, height=.1];
array [label="<f0> 4|<f1> 7|<f2> 2|<f3> 5|<f4> 9|<f5> 1|<f6> 6", style=filled, color=lightgrey];
pivot [label="Pivot: 5", shape=box, style=filled, color=lightblue];
start [shape=none, label=""];
end [shape=none, label=""];
start -> array:f0 [label="First"];
array:f3 -> pivot [label="Middle of three\n(4, 5, 6)"];
end -> array:f6 [label="Last"];
}
```
**解決方法二**：以 Median of Medians 挑選 pivot
```graphviz
digraph G {
node [shape=record, height=.1];
subgraph cluster_0 {
label="Array";
color=lightgrey;
array [label="1|2|3|4|5|6|7|8|9|10|11|12|13|14|15", style=filled];
}
subgraph cluster_1 {
label="Groups of 5";
color=lightgrey;
group1 [label="1|2|3|4|5", style=filled];
group2 [label="6|7|8|9|10", style=filled];
group3 [label="11|12|13|14|15", style=filled];
}
subgraph cluster_2 {
label="Medians of Groups";
color=lightgrey;
median1 [label="3", shape=box, style=filled, color=lightblue];
median2 [label="8", shape=box, style=filled, color=lightblue];
median3 [label="13", shape=box, style=filled, color=lightblue];
}
subgraph cluster_3 {
label="Median of Medians";
color=lightgrey;
pivot [label="Pivot: 8", shape=box, style=filled, color=red];
}
array -> group1 [label="Divide"];
array -> group2;
array -> group3;
group1 -> median1 [label="Find median"];
group2 -> median2;
group3 -> median3;
median1 -> pivot [label="Choose median"];
median2 -> pivot;
median3 -> pivot;
}
```
#### 考慮空間複雜度
原先程式碼使用了額外的 ```begin```、```end```來追蹤子串列，又使用 ```left```、```right```來存分割後的結果，能以 in-place partitioning 的角度出發去改善。
### 測驗二
:::success
延伸問題：
1.解釋上述程式碼的運作原理，提出改進方案並予以實作。
:::
在 `timsort` 函式中，第一行宣告了：
```c
stk_size = 0;
```
接著去搜尋其定義方式：
```c
static size_t stk_size;
```
原先不懂 size_t 為何，在 `stddef.h` 中找到了其定義：
```c
typedef __SIZE_TYPE__ size_t;
```
這點在 [C99](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 之 [6.5.3.4] 第4點也有提及。
:::info
The value of the result is implementation-defined, and its type (an unsigned integer type)
is size_t, defined in <stddef.h> (and other headers).
:::
延伸問題中提到使用 Linux 核心風格的 List API 改寫，一開始判斷是否為 empty 的判斷式就能改進：
```diff
- if (head == head->prev)
+ if (!head || list_empty(head) || list_is_singular(head))
return;
```
首先是 `find_run` 這個函式，其功能為在串列中尋找連續遞增或遞減的序列（run），並根據這個序列是遞增還是遞減來相應地處理鏈表。如果序列是遞減的，函式會將其內的節點反轉，使之成為遞增序列，此處有可以改善的空間，上述反轉的操作可以搭配 `q_reverse` 來使程式碼更精簡。
以一個簡單的範例來追蹤程式碼：
```graphviz
digraph G {
rankdir =LR
node [shape=record];
Node0 [label="<f0> head"];
Node1 [label="<f0> 5"];
Node2 [label="<f0> 2"];
Node3 [label="<f0> 3"];
Node4 [label="<f0> 7"];
Node5 [label="<f0> 6"];
Node6 [label="<f0> 1"];
Node7 [label="<f0> head"];
// Node0 <-> Node1
Node0:f0 -> Node1:f0 [color="red"];
Node1:f0 -> Node0:f0 ;
// Node1 <-> Node2
Node1:f0 -> Node2:f0 [color="red"];
Node2:f0 -> Node1:f0 ;
// Node2 <-> Node3
Node2:f0 -> Node3:f0 [color="red"];
Node3:f0 -> Node2:f0 ;
// Node3 <-> Node4
Node3:f0 -> Node4:f0 [color="red"];
Node4:f0 -> Node3:f0 ;
// Node4 <-> Node5
Node4:f0 -> Node5:f0 [color="red"];
Node5:f0 -> Node4:f0 ;
// Node5 <-> Node6
Node5:f0 -> Node6:f0 [color="red"];
Node6:f0 -> Node5:f0 ;
// Node6 <-> Node7
Node6:f0 -> Node7:f0 [color="red"];
Node7:f0 -> Node6:f0 ;
}
```
待補
:::success
延伸問題：
2.將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
:::
> [commit ce2f8f4](https://github.com/sysprog21/lab0-c/commit/ce2f8f4888535b7e7010d4c52417b94cd4a9bc7c)
先前已完成透過 option 命令修改 sort_type 之值，根據其值選擇要使用 merge_sort 或 list_sort 進行佇列排序操作。此次更新加入 timsort 並對程式碼做了下方更動。
```diff
- add_param("sort_type", &sort_type, "0 for merge_sort, 1 for list_sort",NULL);
+ add_param("sort_type", &sort_type, "0 for merge_sort, 1 for list_sort, 2 for timsort",NULL);
```
```diff
/* Sort elements of queue in ascending order */
extern int sort_type;
void q_sort(struct list_head *head, bool descend)
{
switch (sort_type) {
case 0:
merge_sort(head);
break;
case 1:
list_sort(head, cmp);
break;
+ case 2:
+ timsort(head, cmp);
+ break;
default:
printf("Unknown sort type.\n");
break;
}
if (descend)
q_reverse(head);
}
```
詳細的效能評比，我將其更新於 [2024q1 Homework1 (lab0) - 嘗試將 Timsort 引入到 lab0-c](https://hackmd.io/yI-Rh8l7Q9uzWhQgBQbsnQ?view#%E5%98%97%E8%A9%A6%E5%B0%87-Timsort-%E5%BC%95%E5%85%A5%E5%88%B0-lab0-c) 中。
## 第二周測驗
[2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 `1`
:::success
解釋程式碼的運作原理。
:::
```clike
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
if (h->first)
h->first->pprev = &n->next;
n->next = AAAA;
n->pprev = &h->first;
h->first = n;
}
```
**`AAAA` 應填入 `h->first`。**
假設目前串列中還沒有節點（不會執行 if 判別式），根據：
```clike
static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
h->first = NULL;
}
```
所以初始 first 會指向 NULL：
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>hlist_head | <n>first"]
NULL[shape = plaintext, label = "NULL", group = list]
list_head:n -> NULL;
}
```
現在執行第一次的 `hlist_add_head`，因 `AAAA` 填入 `h->first` 所以：
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>hlist_head | <n>first"]
NULL[shape = plaintext, label = "NULL", group = list]
list_head:n -> NULL;
}
```
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
node_1:n -> NULL;
}
```
接著執行`n->pprev = &h->first;`
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>hlist_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 [
weight = 10, style = invis
]
node_1:p -> list_head:n;
node_1:n -> NULL;
}
```
最後執行 `h->first = n;`
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>hlist_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 [
weight = 10, style = invis
]
list_head:n -> node_1:m;
node_1:p -> list_head:n;
node_1:n -> NULL;
}
```
若再次執行 `hlist_add_head` 插入 `hist_node_2` 節點，這次會執行 if 判別式部份。
`h->first->pprev` 即 `hist_node_1` 的 pprev，將其指向 `hist_node_2` 的 next。
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>hlist_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", ];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 [
weight = 10, style = invis
]
list_head:n -> node_1:m;
node_1:p -> node_2:n;
node_1:n -> NULL;
}
```
接著依序執行：
```clike
n->next = h->first;
n->pprev = &h->first;
h->first = n;
```
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>hlist_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", ];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_2 -> node_1 [
weight = 10, style = invis
]
list_head:n -> node_2:m;
node_2:p -> list_head:n
node_2:n -> node_1:m
node_1:p -> node_2:n;
node_1:n -> NULL;
}
```
以相同範例，Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]。
首先呼叫 `buildTree`，參數代入上方範例的 preorder 及 inorder，兩者 size 均為 5，前 3 行程式碼如下：
```clike
struct hlist_head *in_heads = malloc(5 * sizeof(*in_heads));
for (int i = 0; i < 5; i++)
INIT_HLIST_HEAD(&in_heads[i]);
```
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
nullNode [label="NULL", shape=plaintext];
map [label="in_heads |<ht0>first |<ht1>first |<ht2>first |<ht3>first |<ht4>first"];
map:ht0 -> nullNode;
map:ht1 -> nullNode;
map:ht2 -> nullNode;
map:ht3 -> nullNode;
map:ht4 -> nullNode;
}
```
接著是
```clike
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
```
在 `node_add` 中會去計算 inorder 的各元素應放入哪格 in_heads 中：
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="in_heads |<ht0>first |<ht1>first |<ht2>first |<ht3>first |<ht4>first"];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
null3 [label=NULL]
null4 [label=NULL]
null5 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:0;val:3"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:1;val:9"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:2;val:20"
}
subgraph cluster_4 {
style=filled;
color=lightgrey;
node [shape=record];
hn4 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:3;val:15"
}
subgraph cluster_5 {
style=filled;
color=lightgrey;
node [shape=record];
hn5 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:4;val:=7"
}
map:ht0 -> hn3;
hn3:prev:s -> map:ht0;
hn3:next -> hn4;
hn4:prev:s -> hn3:next
hn4:next -> null1;
map:ht1 -> hn5;
hn5:prev:s ->map:ht1;
hn5:next -> null2;
map:ht2 -> hn1;
hn1:prev:s ->map:ht2;
hn1:next -> null3;
map:ht3 -> hn2;
hn2:prev:s ->map:ht3;
hn2:next -> null4;
map:ht4 -> null5;
}
```
起初用上方的圖去進行後續的 dfs 遞迴，發現結果與預期的有落差，重新看過程式碼後發現我 idx 的編號是依照 prorder 的元素順序，正確來說在 `INIT_HLIST_HEAD` 及 `node_add` 是以 inorder 的元素順序才對，故上方的圖片應如下修正：
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="in_heads |<ht0>first |<ht1>first |<ht2>first |<ht3>first |<ht4>first"];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
null3 [label=NULL]
null4 [label=NULL]
null5 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:1;val:3"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:0;val:9"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:2;val:15"
}
subgraph cluster_4 {
style=filled;
color=lightgrey;
node [shape=record];
hn4 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:3;val:20"
}
subgraph cluster_5 {
style=filled;
color=lightgrey;
node [shape=record];
hn5 [label="hlist_node | {<prev>pprev | <next>next}"];
label="idx:4;val:=7"
}
map:ht0 -> hn3;
hn3:prev:s -> map:ht0;
hn3:next -> hn4;
hn4:prev:s -> hn3:next
hn4:next -> null1;
map:ht1 -> hn5;
hn5:prev:s ->map:ht1;
hn5:next -> null2;
map:ht2 -> hn1;
hn1:prev:s ->map:ht2;
hn1:next -> null3;
map:ht3 -> hn2;
hn2:prev:s ->map:ht3;
hn2:next -> null4;
map:ht4 -> null5;
}
```
接著是 `dfs` 的部份，這邊我覺得蠻困難的，一開始對遞迴呼叫中傳入的參數運算很混亂，這邊以另一個例子來追蹤：
> preorder = [A, B, D, E, C, F, G]
> inorder = [D, B, E, A, F, C, G]
根據建構二元數的規則，我們可以得知根節點為 `A` ，先看第一個遞迴呼叫：
```clike
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
in_low, idx - 1, in_heads, size);
```
* `pre_low + 1`：根節點 `A` 之左子樹其起始索引於 preorder 中的 `pre_low + 1`，即根節點 `A` 的下個位置。
* `idx - in_low`： `idx` 為 `A` 在 inorder 中的索引，經由 `idx - in_low` 可以計算出根節點 `A` 之左子樹節點總數（即 3 個）。
由上方兩點可知左子樹在 preorder 中從索引 `pre_low + 1`（即 1） 開始且長度為`idx - in_low` （即 3）。所以可以知道結束的索引位於 `pre_low + 1 + (idx - in_low) - 1`，將其化簡後可得 `pre_low + (idx - in_low)`。
```clike
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
idx + 1, in_high, in_heads, size);
```
先將 `pre_high - (in_high - idx - 1)` 改為 `pre_high - (in_high - idx ) + 1`，我覺得這樣解釋比較清晰。
* `in_high - idx`： `idx` 為 `A` 在 inorder 中的索引，經由 `in_high - idx` 可以計算出根節點 `A` 之右子樹節點總數（即 3 個）。
所以由 `pre_high - (in_high - idx ) + 1` 可以得知右子樹在 preorder 的起始索引（即 4）。
綜合上述可以理解為每次呼叫遞迴時會傳入左右子樹的**起始索引**及**結束索引**。
:::success
#### 撰寫完整的測試程式。
:::
目前的設想是撰寫 preorder traversal 及 inorder traversal 的遞迴程式碼，倘若由 preorder 序列及 inorder 序列所構建的 BT 是正確的，對該 BT 進行 preorder traversal 及 inorder traversal 後會與原先的序列相同。
:::success
#### 指出其中可改進之處並實作。
:::
> [commit 5b568bb](https://github.com/yy214123/M02-quiz1-2/commit/5b568bbe9b5e4b89d0b68efff54511135f19f683)
此次提交先上傳原始的程式碼。
參考教材 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)，原始程式的雜湊函數採 Division method，應可用教材所提及的 Multiplication Method 來改進。
:::warning
我對於 Multiplication Method 的 bits 部份有疑惑，不知道該如何代入什麼值。
:::
> [commit 5333c09](https://github.com/yy214123/M02-quiz1-2/commit/5333c09b2b596a4cac5c5fb2689543a657358702)
> 此次更新加入了教材中的 Multiplication Method 雜湊函數。這個版本的程式碼目前有 bug 須修正
> [commit b2d2080](https://github.com/yy214123/M02-quiz1-2/commit/b2d2080061be7c49bb8a0eaadc445cd9631aaf2f)
> 此次更新修復了原先的 bug，逐步偵錯後發現是 `INIT_HLIST_HEAD(&in_heads[i])` 這部份的迭代次數設置有誤，原先的次數是 `inorderSize `應該配合 `bits` 的設計調整，否則會出現計算後的 `hash` 值找不到對應的 bucket。
原先提及對 Multiplication Method 的 bits 部份有疑惑，目前是以下方方式撰寫，但我不清楚是否正確：
```clike
int bits =ceil(log2(size));
int hash = (num < 0 ? hash_32(-num, bits) : hash_32(num, bits));
```
如果上方是正確的，那麼這部份也還有改進空間，可參考 [第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3) 測驗 `1` 提及的方法改進。
### 測驗 `2`
:::success
解釋程式碼的運作原理。
:::
```clike
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
EEEE = pprev;
}
```
`EEEE` 應填入 `next->pprev`。間接指標 `pprev` 會指向一個**指著自身節點的指標**，根據 if 判別條件，如果刪除的節點並非最末節點，將欲刪除節點之下一節點的 `pprev` 指向其自身。
```clike
void lRUCacheFree(LRUCache *obj)
{
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, FFFF);
list_del(GGGG);
free(cache);
}
free(obj);
}
```
這邊一開始填的答案都錯，因為我只看了 `lRUCacheCreate` 的程式架構，但實際上這邊的 `INIT_LIST_HEAD` 及 `INIT_HLIST_HEAD` 還未將節點彼此串接起來，應先理解 `lRUCachePut` 的運作邏輯後才回過頭來完成此部份。
仔細研究整個程式架構後，發現這個測驗蠻有趣的，本質上是兩個獨立的結構體，一個（hlist）利用雜湊函數的方式來降低搜尋節點的成本，一個（list）用雙向環狀鍊結串列來維護 LRU 的特性，將最近使用過的節點透過 `list_move` 來調整該節點之優先權。
理解整體架構後，回過頭看 `lRUCacheFree` 就清晰許多，可以看到：
`list_for_each_safe (pos, n, &obj->dhead)`
而 dhead 是維護 LRU 的雙向環狀鍊結串列的頭部，故 `FFFF` 應填入 `link`，而 `GGGG` 應該填入 `&cache->link`。
:::success
撰寫完整的測試程式。
:::
:::success
指出其中可改進之處並實作。
:::
雜湊函數也有改進空間，原始程式碼採 Division method，同測驗 `1` 可將其改為 Multiplication Method。
### 測驗 `3`
:::success
解釋程式碼的運作原理。
:::
一開始對 `small_const_nbits`中的`__builtin_constant_p` 感到疑惑，翻閱 [GCC 官方文件](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)及重新觀看[第 2 週課程 [34:07]](https://www.youtube.com/watch?v=WYcexo6T3UI&t=609s)後，才了解其功能。此函式會在編譯時期檢查某個表示式是否為常數。
Sign in with Wallet
Connect another wallet