contributed by < `chloe0919` >
## 第 1 週測驗題
### 測驗一 : 實作非遞迴 (non-recursive; iterative) 的快速排序法
#### 運作原理
主要流程是先利用 `L` 與 `R` 決定出序列的頭尾，再以序列中的第一個節點作為 `pivot`，然後從 `pivot->next` 開始逐一走訪佇列，判斷節點和 `pivot` 之間的大小關係，而 `begin[]` 與 `end[]` 作為堆疊，用來紀錄比較的範圍
根據 `list_construct` 可以建立出以下的單向鏈串列
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
subgraph cluster_a
{
label = "node_1";
node1 [label="<head>value = 4|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_b
{
label = "node_2";
node2 [label="<head>value = 1|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_c
{
label = "node_3";
node3 [label="<head>value = 7|*next|{<left> *left |<right> *right}"];
}
subgraph cluster_d
{
label = "node_4";
node4 [label="<head>value = 5|*next|{<left> *left |<right> *right}"];
}
NULL1[label=NULL,shape=plaintext]
node1:"*next"->node2:"*next" [lhead=cluster_b];
node2:"*next"->node3:"*next" [lhead=cluster_c];
node3:"*next"->node4:"*next" [lhead=cluster_d];
node4:"*next" -> NULL1
}
```
使用以下序列作為範例 ：
```graphviz
digraph graphname{
node[shape=box]
{
rankdir = LR
A[label=4]
B[label=1]
C[label=7]
D[label=5]
NULL[label=NULL,shape=plaintext]
A->B->C->D->NULL
}
rankdir = "LR"
// L[shape=plaintext,fontcolor=red]
// R[shape=plaintext,fontcolor=red]
// 0[shape=plaintext,fontcolor=white]
// 1[shape=plaintext,fontcolor=white]
// L->0[color=red,style=dotted];
// 0->1[color=white];
// 1->R[dir=back,color=red,style=dotted];
}
```
接下來逐步解釋 `quick_sort` 的實作流程，首先以下列程式碼初始化指標 ：
```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);
```
假設目前 `i = 0` ：
進入 `while` 將 `L` 和 `R` 指向該子序列的頭和尾，並且以 `L` 也就是序列的起始當作 `pivot` 開始進入第一次迭代
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=4]
B[label=1]
C[label=7]
D[label=5]
NULL[label=NULL,shape=plaintext]
A->B->C->D->NULL
{
rank="same";
L[label="L",shape=plaintext,fontcolor=red]
pivot[label="pivot",shape=plaintext,fontcolor=blue]
pivot->L[color=blue]
L->A[color=red];
}
{
rank="same";
R[label="R",shape=plaintext,fontcolor=red]
R->D[color=red];
}
}
```
接下來執行 `pivot->next = NULL` 打斷 `pivot` 和其他節點的鏈結，並且使用指標 `n` 執行下列程式碼
```diff
while (p) {
node_t *n = p;
- p = CCCC;
+ p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
指標 `n` 每次都會往前一步去判斷該節點和 `pivot` 之間的大小關係
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=4]
B[label=1]
C[label=7]
D[label=5]
NULL[label=NULL,shape=plaintext]
A->B[color=white,arrowsize=0.00000000000000001]
B->C->D->NULL
{
rank="same";
pivot[label="pivot",shape=plaintext,fontcolor=blue]
pivot->A[color=blue];
}
{
rank="same";
n[label="n",shape=plaintext,fontcolor=red]
n->B[color=red];
}
0[shape=plaintext,fontcolor=white]
n->0[color=red,style=dotted];
}
```
再執行 `list_add(n->value > value ? &right : &left, n)` ，將大於 `pivot` 的點放入 `right` 中，其餘放入 `left`
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=4]
B[label=1]
C[label=7]
D[label=5]
A->B[color=white,arrowsize=0.00000000000000001]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
{
rank="same";
pivot[label="pivot",shape=plaintext,fontcolor=blue]
pivot->A[color=blue];
}
left[label=left,shape=plaintext]
{rank=same left->B->NULL1};
right[label=right,shape=plaintext]
{rank=same right->D->C->NULL2};
left->right[color=white]
}
```
之後將 `left` 的頭尾分別放入 `begin[0]` 和 `end[0]` 之中，`right` 的頭尾分別放入 `begin[2]` 和 `end[2]` ，而 `begin[1]` 和 `end[1]` 則是都放入 `pivot`
進入下一次迭代 `i = 2` ，因為 `node_t *L = begin[2], *R = end[2]`，代表先從堆疊的最上方，也就是上述 `right` 指到的子序列開始進行處理 ：
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
C[label=7]
D[label=5]
NULL2[label=NULL,shape=plaintext]
D->C->NULL2;
{
rank="same";
L[label="L",shape=plaintext,fontcolor=red]
L->D[color=red];
}
{
rank="same";
R[label="R",shape=plaintext,fontcolor=red]
R->C[color=red];
}
}
```
因為 `L != R` 所以以第一個節點當作 `pivot`，並且和之前的流程一樣進行 `left` 和 `right` 的分類，並且把 `left` 的頭尾分別放入 `begin[2]` 和 `end[2]` 之中，`right` 的頭尾分別放入 `begin[3]` 和 `end[3]` ，而 `begin[4]` 和 `end[4]` 則是都放入 `pivot`
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
C[label=7]
D[label=5]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
{
rank="same";
pivot[label="pivot",shape=plaintext,fontcolor=blue]
pivot->D[color=blue];
}
{
rank="same";
left[label="left",shape=plaintext]
left->NULL2;
}
{
rank="same";
right[label="right",shape=plaintext]
right->C->NULL1;
}
pivot->left->right [color=white]
}
```
此時因為 `L == R` 所以不會進入 `while` ，目前堆疊存放的節點情形為以下 ：
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=4]
B[label=1]
C[label=7]
D[label=5]
NULL[label=NULL,shape=plaintext]
A->B->C->D->NULL[color=white,arrowsize=0.00000000000000001]
begin0[label="begin[0]",shape=plaintext, group = g2]
begin1[label="begin[1]",shape=plaintext, group = g2]
begin2[label="begin[2]",shape=plaintext, group = g2]
begin3[label="begin[3]",shape=plaintext, group = g2]
begin4[label="begin[4]",shape=plaintext, group = g2]
{rank="same"; begin0->B}
{rank="same"; begin1->A}
{rank="same"; begin3->D}
{rank="same"; begin4->C}
{rank="same"; begin2->NULL}
end0[label="end[0]",shape=plaintext, group = g1]
end1[label="end[1]",shape=plaintext, group = g1]
end2[label="end[2]",shape=plaintext, group = g1]
end3[label="end[3]",shape=plaintext, group = g1]
end4[label="end[4]",shape=plaintext, group = g1]
{rank="same"; end0->B}
{rank="same"; end1->A}
{rank="same"; end3->D}
{rank="same"; end4->C}
{rank="same"; end2->NULL}
}
```
之後執行下列程式碼從 `i = 4` 開始向下遞減，每一次都將 `L` 也就是堆疊中 `begin[i]` 以指令 `list_add` 將節點加入至 `result` 中，直到所有的堆疊都被加入完成，也就是 `i = 0` 的時候
```c
else {
if (L)
list_add(&result, L);
i--;
}
```
最後完成非遞迴的快速排序法的實作
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=1]
B[label=4]
C[label=5]
D[label=7]
NULL[label=NULL,shape=plaintext]
A->B->C->D->NULL
}
```
#### 改進方案 ：
##### 針對堆疊空間 ：
###### 參考筆記 ：[csotaku0926](https://hackmd.io/@csotaku0926/linux2024-homework2)
在 `quick_sort()` 加入 `count_i` 計算最大的 i ，而 `count + 1` 則代表堆疊使用到的總數
```diff
left = right = NULL;
i += 2;
+ count_i = max(count_i, i);
```
我的思考方式是先考慮最差的空間使用情況，因為程式的操作為：**將大於 `pivot` 的點放入 `right` 中，其餘放入 `left`**，若每次 pivot 都是選到最小的，則會使 `left` 每次都為空，其餘資料都會放入 `right` ，因為堆疊的判斷條件是先考慮最上面的資料，也就是 `right` 是否為只剩一個點，來決定是不是繼續擴增堆疊的高度，考慮以下資料：
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=0]
B[label=2]
C[label=4]
G[label=3]
H[label=1]
NULL[label=NULL,shape=plaintext]
A->B->C->G->H->NULL
}
```
`pivot` 隨著迭代輪流順序會是 0 -> 1 -> 2 -> 3 ，總共有 4 個節點當過 `pivot` ，此時最大的 i 為 $2\times4 = 8$，所以總共需要 9 個空間
因此可以計算出最差的空間使用情形為 `int max_level = 2 * n - 1`
##### 針對 `pivot` 的選擇 避免最差情況 ：
另外目前在 `pivot` 的選擇上採取的方式是**選擇第一筆的資料**，若能採用隨機採取的方式選擇 `pivot` ，能避免上述例子的情況，定義以下函式，使用 `rand_idx` 決定所選擇的 `pivot` 節點所在的索引，並且使用指標 `prev` 指向 `pivot` 的前一點，之後截斷 `prev` 和 `curr` 的鏈結，最後利用 `list_add` 將 `curr` 移到最前面
```c
void rand_p(node_t **b) {
node_t *prev = *b;
node_t *curr = prev;
int c = list_length(b);
int rand_idx = rand() % c;
while (rand_idx > 1) {
prev = prev->next;
rand_idx--;
}
if (rand_idx != 0) {
curr = prev->next;
prev->next = curr->next;
list_add(b, curr);
}
}
```
使用經過 `rand_p` 函式決定的 `pivot`，這邊要注意的是若只有兩個點則一律採取開頭的點為 `pivot` ，因為只有兩節點不管選擇哪個並不會影響效能，可以減少一次 rand_p() 函式的應用 ：
```diff
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
+ if (L->next != R)
+ rand_p(&L);
node_t *pivot = L;
value = pivot->value;
```
接下來使用 `lab0-c` 的 `cpucycles()` 在 `quick_sort(&list)` 的前後，看 cpucycles 的變化
```diff
+ int64_t before = cpucycles();
quick_sort(&list);
+ int64_t after = cpucycles();
```
以下分別為 count 由 10 到 100000，有無使用 `rand_p` 時實際有使用到的堆疊層數 (max lengh) 和 elasped cycles ：
```
//rand_p
count : 10
max lengh : 9
elasped cycles : 8280
---------------------------------------------
count : 100
max lengh : 17
elasped cycles : 34704
---------------------------------------------
count : 1000
max lengh : 29
elasped cycles : 416376
---------------------------------------------
count : 10000
max lengh : 35
elasped cycles : 6179688
---------------------------------------------
count : 100000
max lengh : 47
elasped cycles : 119624148
```
```
//No rand_p
count : 10
max lengh : 5
elasped cycles : 10188
---------------------------------------------
count : 100
max lengh : 15
elasped cycles : 29592
---------------------------------------------
count : 1000
max lengh : 27
elasped cycles : 272448
---------------------------------------------
count : 10000
max lengh : 39
elasped cycles : 4144320
---------------------------------------------
count : 100000
max lengh : 49
elasped cycles : 73245168
```
可以看到若有選擇到好的 `pivot` ，所需要的堆疊空間也會減少，隨著 max lengh 的下降，elasped cycles 也明顯下降許多，尤其是在 count 數多的時候減少一格就會減少很多 cycles
#### 使用 Linux 核心風格的 List API ：
程式碼在 [41c3f48](https://github.com/chloe0919/linux_hw2/commit/41c3f48c758914c55422cb5d9b11f09063c392d2?diff=unified&w=0) ，使用和 `lab0-c` 一樣的結構：
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
subgraph cluster_b
{
label = "element_t";
node1 [label="value"];
node2 [label="{<prev> prev |<next> next}"];
}
}
```
### 測驗二 : Timsort
考慮以下資料 :
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=1]
B[label=2]
C[label=3]
D[label=5]
E[label=4]
F[label=7]
G[label=8]
NULL[label=NULL,shape=plaintext]
A->B->C->D->E->F->G->NULL
}
```
首先使用 `find_run` 找出每一個 run ,並且如果是降序排列就將此 list 反轉成升序排列，以下呈現所有 run 的都被找出來的示意圖
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=1]
B[label=2]
C[label=3]
D[label=4,color=blue]
E[label=5,color=blue]
F[label=7,color=red]
G[label=8,color=red]
NULL[label=NULL,shape=plaintext]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
A->B->C
{rank = same C->NULL1}
C->D[color=white]
D->E
{rank = same E->NULL2}
E->F[color=white]
F->G
{rank = same G->NULL}
}
```
操作的流程為每次 `find_run` 後會找到一個 run , 接下來使用 `result.head` 和 `result.next` 記錄整個 run 的頭尾，並且會記錄該 run 的長度在 `head->next->prev` 當中
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
A[label=1]
B[label=2]
C[label=3]
D[label=5]
NULL[label=NULL,shape=plaintext]
A->B->C
{rank = same C->NULL}
C->D[color=white]
"result.head"[fontcolor=red,color=red];
"result.next"[fontcolor=red,color=red];
{rank=same "result.head"->A}
{rank=same "result.next"->D}
"result.head"->"result.next"[color=white]
}
```
之後使用建立一個結構`list_head` 的指標 `tp` 並且使用 `merge_collapse` 檢查 3 段 run 的長度是否滿足以下原則：
1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。
`merge_collapse` 的檢查流程如下 :
假設有三個 run ，長度分別為 A : 3 、B : 2 、C : 2，此時 `tp` 會記錄每個 run 的起始節點，而且每個 `tp` 指向最新個的 run
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
1[label=1,color=forestgreen]
2[label=2,color=forestgreen]
3[label=3,color=forestgreen]
4[label=4,color=dodgerblue4]
5[label=5,color=dodgerblue4]
7[label=7,color=darkgoldenrod3]
8[label=8,color=darkgoldenrod3]
A[label=A,shape=plaintext]
B[label=B,shape=plaintext]
C[label=C,shape=plaintext]
A->1->2->3
B->4->5
C->7->8
// A->B->C[color=white]
"tp"[fontcolor=red,color=red];
"tp->prev"[fontcolor=red,color=red];
"tp->prev->prev"[fontcolor=red,color=red];
"tp"->"tp->prev"->"tp->prev->prev"
{rank=same "tp"->C}
{rank=same "tp->prev"->B}
{rank=same "tp->prev->prev"->A}
}
```
當最新的兩個 run (即 B、C )相加長度大於最舊的那個 ( A )，且 C 的長度大於 A 就將 A、B 合併，否則 B、C 合併，也就是合併最小的兩個 run
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
1[label=1,color=forestgreen]
2[label=2,color=forestgreen]
3[label=3,color=forestgreen]
4[label=4,color=dodgerblue4]
5[label=5,color=dodgerblue4]
7[label=7,color=dodgerblue4]
8[label=8,color=dodgerblue4]
A[label=A,shape=plaintext]
B[label=B,shape=plaintext]
A->1->2->3
B->4->5->7->8
// A->B->C[color=white]
"tp"[fontcolor=red,color=red];
"tp->prev"[fontcolor=red,color=red];
"tp"->"tp->prev"
{rank=same "tp"->B}
{rank=same "tp->prev"->A}
}
```
這時候因為 `run_size(tp->prev) <= run_size(tp)` 所以還會再執行一次 `tp = merge_at(priv, cmp, tp)` 進行合併
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
1[label=1,color=forestgreen]
2[label=2,color=forestgreen]
3[label=3,color=forestgreen]
4[label=4,color=forestgreen]
5[label=5,color=forestgreen]
7[label=7,color=forestgreen]
8[label=8,color=forestgreen]
A[label=A,shape=plaintext]
A->1->2->3->4->5->7->8
"tp"[fontcolor=red,color=red];
{rank=same "tp"->A}
}
```
最後使用 `merge_force_collapse` 合併所有的 run 到總數 < 3，最後用 `stk0` 和 `stk1` 表示最後剩下的 run ，若只剩 1 個 run 就直接使用 `build_prev_link` 建立回原本的鏈結，若還有兩個 run 就使用 `merge_final` 合併即完成 `Timsort`
```c
/* The final merge; rebuild prev links */
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
if (stk_size <= 1) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
```
## 第 2 週測驗題
### 測驗一 : dfs
根據 [Linux 核心的 hash table 實作](https://hackmd.io/rpIi8FeqQ9eBJ-UTFgb--A?view) `hlist_node` 用以處理 hash 數值碰撞，其中 `pprev` 指向**指著自身節點的指標**
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
#### hlist_add_head
操作流程如下 :
1. 先將 `n->next` 指向原始未插入節點前的第一個點，也就是 `h->first`
2. 再將 `n->pprev` 指向 `&h->first`
3. 最後再將 n 點插入到 `h->first`
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>n | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_3[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 -> node_2 -> node_3[
weight = 10, style = invis
]
list_head:n -> node_1:m[color=red,label="3",fontcolor=red];
node_1:p -> list_head:n[color=red,label="2",fontcolor=red];
node_1:n -> node_2:m[color=red,label="1",fontcolor=red];
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> NULL;
}
```
#### find
```c
static int find(int num, int size, const struct hlist_head *heads)
{
struct hlist_node *p;
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) {
struct order_node *on = container_of(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
return -1;
}
```
首先計算出雜湊值 hash，再執行 `hlist_for_each` 根據 hash 找到對應的鏈結串列串列，並且使用 `container_of` 算出記憶體位置，以 `if` 判斷是否為正在尋找的數字
#### dfs
```c
static struct TreeNode *dfs(int *preorder,
int pre_low,
int pre_high,
int *inorder,
int in_low,
int in_high,
struct hlist_head *in_heads,
int size)
{
if (in_low > in_high || pre_low > pre_high)
return NULL;
struct TreeNode *tn = malloc(sizeof(*tn));
tn->val = preorder[pre_low];
int idx = find(preorder[pre_low], size, in_heads);
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
in_low, idx - 1, in_heads, size);
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
idx + 1, in_high, in_heads, size);
return tn;
}
```
以 `tn->val` 記錄前序的第一筆資料作為樹的根節點，並使用 `find` 找到對應在中序的索引，在各以 `tn->left` 和 `tn->right` 去遞迴尋找左子樹和右子樹
左右子樹各自需考慮的 `pre_low`、`pre_high`、`in_low`、`in_high` 為 :
* 左子樹 :
* `pre_low` : 為原本的 `pre_low` $+1$ ( 從根節點下一點開始 )
* `pre_high` : 先算出 `idx - in_low` 代表根節點左邊的元素個數，之後 `pre_low + (idx - in_low)` 為前序考慮的最高索引
* `in_low` : 原本的最低索引
* `in_high` : 根節點的左邊
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
i3[label=3,shape=circle,color=red]
i9[label=9,shape=circle]
i20[label=20,shape=circle]
i15[label=15,shape=circle]
i7[label=7,shape=circle]
inorder->i9->i3->i15->i20->i7;
preorder[label=preorder,shape=plaintext]
inorder[label=inorder,shape=plaintext]
p3[label=3,shape=circle,color=red]
p9[label=9,shape=circle]
p20[label=20,shape=circle]
p15[label=15,shape=circle]
p7[label=7,shape=circle]
preorder->p3->p9->p20->p15->p7;
pre_low[label=pre_low,shape=plaintext,fontcolor=deepskyblue2]
{rank = same pre_low->p9}
pre_high[label=pre_high,shape=plaintext,fontcolor=deepskyblue2]
{rank = same pre_high->p9}
in_low[label=in_low,shape=plaintext,fontcolor=deepskyblue2]
{rank = same in_low->i9}
in_high[label=in_high,shape=plaintext,fontcolor=deepskyblue2]
{rank = same in_high->i9}
}
```
* 右子樹 :
* `pre_low` : 一樣先算出 `in_high - idx` 代表根節點右邊元素個數，再以 `pre_high - (in_high - idx) + 1` 算出最前序考慮的最低範圍的索引
* `pre_high` : 原本的最高索引
* `in_low` : 根節點的右邊
* `in_high` : 原本的最高索引
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
i3[label=3,shape=circle,color=red]
i9[label=9,shape=circle]
i20[label=20,shape=circle]
i15[label=15,shape=circle]
i7[label=7,shape=circle]
inorder->i9->i3->i15->i20->i7;
preorder[label=preorder,shape=plaintext]
inorder[label=inorder,shape=plaintext]
p3[label=3,shape=circle,color=red]
p9[label=9,shape=circle]
p20[label=20,shape=circle]
p15[label=15,shape=circle]
p7[label=7,shape=circle]
preorder->p3->p9->p20->p15->p7;
pre_low[label=pre_low,shape=plaintext,fontcolor=deepskyblue2]
{rank = same pre_low->p20}
pre_high[label=pre_high,shape=plaintext,fontcolor=deepskyblue2]
{rank = same pre_high->p7}
in_low[label=in_low,shape=plaintext,fontcolor=deepskyblue2]
{rank = same in_low->i15}
in_high[label=in_high,shape=plaintext,fontcolor=deepskyblue2]
{rank = same in_high->i7}
}
```
### 測驗二 : LRU
#### 資料結構 :
使用 `LRUCache` 儲存 LRUCache 的結構
* `capacity` : 快取的容量大小
* `count` : 目前存放的數量
* `dhead` : 串接所有資料的 `list_head`
* `hhead` : 處理碰撞的 `hlist_head`
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
示意圖 :
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
subgraph cluster_a
{
label = "LRUCache";
node1 [label="<head>capacity|count|{<prev> dhead |<next> hhead[]}"];
}
map [label="<head>hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> "];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 3"
}
map:ht0 -> hn1
hn1:next -> hn2
hn2:next -> null1
hn2:prev:s -> hn1:next:s
map:ht4 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht0
hn3:prev:s -> map:ht4
node1:"next"->map:head;
}
```
使用 `LRUNode` 儲存節點的結構
* `node` : 用來儲存碰撞的串列元素
* `link` : 記錄在 `dhead` 中的位置
```c
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
#### lRUCacheGet
首先使用 key 計算出所對應的雜湊值，然後用 `hlist_for_each` 逐一走訪 `obj->hhead[hash]` 所有元素並且以 `cache` 記錄每個元素 link 類型指向的結構體，當尋找到所對應 key 值節點後，需要將 `&cache->link` 也就是找到節點的串接往前挪移，更新該節點的使用情形，代表他才剛被使用過，因此在 `dhead` 當中存放的位置也就是節點的更新順序，越後面的節點代表越久沒有被使用到的節點
```c
if (cache->key == key) {
list_move(&cache->link, &obj->dhead);
return cache->value;
}
```
#### lRUCachePut
一開始和 `lRUCacheGet` 的操作類似，只不過是先去尋找 cache 中是否已經有存在相同 key 的節點了，如果有的話一樣要更新節點在 `dhead` 的順序，假設現在要尋找 key 3 ，而且已經存在在 hash table 中，所以需要將 `dhead` 中 hey 3 的順序往前挪動 :
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
subgraph cluster_a
{
label = "LRUCache";
node1 [label="<head>capacity|count|{<prev> dhead |<next> hhead[]}"];
}
map [label="<head>hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> "];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
label="key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
label="key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
label="key 3"
}
map:ht0 -> hn1
hn1:next -> hn2
hn2:next -> null1
hn2:prev:s -> hn1:next:s
map:ht4 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht0
hn3:prev:s -> map:ht4
node1:"next"->map:head;
node [shape=record];
dh1 [label="<h>key1 | {<prev>pprev | <next>next}"];
dh2 [label="<h>key2 | {<prev>pprev | <next>next}"];
dh3 [label="<h>key3 | {<prev>pprev | <next>next}",color=red];
// {rank = "min" list_head}
dh1 -> dh2 -> dh3[
weight = 10, style = invis
]
dh1:next -> dh2[dir=both];
dh2:next -> dh3[dir=both];
dh3:s->dh1:sw[color=red];
node1:"prev"->dh1
}
```
如果 cache 為空，代表該 key 並不存在在 cache 中，此時會有下列兩種情況 :
1. **cache 容量使用==已達到==限制**，需要使用 `list_last_entry` 尋找 `dhead` 中最後面的節點 ( 代表最不常被使用到 )，並且使用 `list_move` 移到最前面後再將他移除，最後使用 `hlist_add_head` 將要加入的節點加入到最前面，原因是該節點才剛被加入，所以是最近最常被使用到的
```c
if (obj->count == obj->capacity) {
cache = list_last_entry(&obj->dhead, LRUNode, link);
list_move(&cache->link, &obj->dhead);
hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);
}
```
2. **cache 容量使用==未達==限制**，可以直接加入，使用 `malloc` 建立一個新的記憶體空間並且分別使用 `hlist_add_head` 和 `list_add` 將 cache 放入到對應 hash 的 head 以及 `dhead` 最前面
```c
else {
cache = malloc(sizeof(LRUNode));
hlist_add_head(&cache->node, &obj->hhead[hash]);
list_add(&cache->link, &obj->dhead);
obj->count++;
}
```
最後兩種情況分別處理完成後，還需要將 key 和 value 分別放入 `cache->key` 和 `cache->value` 中
### 測驗三 : 在指定的記憶體空間找出第 N 個設定的位元
此測驗的內建巨集和函式比較多，所以首先要了解以下的巨集 :
#### small_const_nbits
定義如下，操作方法為使用 `__builtin_constant_p` 檢查 `nbits` 是否在編譯時是否為常數，另外還有 `nbits` 是否介於 0 ~ BITS_PER_LONG 之間
```c
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
```
`GENMASK(h, l)` 作用是依據給定的範圍 $(h,l)$，產生連續的 bitmask ，所以 `GENMASK(size - 1, 0)` 的結果會是右邊 `size` 個 bit 為 1，其餘的位元都設成 0
#### __ffs
目的是找到 word **從右邊數來的第一個 set bit 的位置**，首先會先計算出 `word & 0xffffffff` 並且判斷是否為 0，這個動作是為了從高位元開始尋找是否有位於向右數來第 32 位的 bit
特別要注意的是要先以 `#if BITS_PER_LONG == 64` 判斷是否是 64 位元架構，之後一樣由高往低位元判斷
```c
if ((word & 0xffffffff) == 0) {
num += 32;
word >>= 32;
}
```
#### BIT_MASK
獲得只有第 nr 個 bit 為 1 的 mask
```c
#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
```
#### BIT_WORD
計算 nr 在第幾個 word
```c
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
```
#### __clear_bit
再來嘗試理解 `__clear_bit` 的操作，首先使用 `BIT_MASK` 設定一個 mask而且只有第 nr 個 bit 為 1，再來定義一個指標 p 並使用 `BIT_WORD` 去計算 nr 是屬於第幾個 word 且將 p 指向 addr 中 nr 所屬的 word，取 ~mask 是為了獲得只有第 nr 為 0 其他為 1 的遮罩，最後執行 `*p &= ~mask` 就能將 addr 中，第 nr 個 bit 清除成 0
```c
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
*p &= ~mask;
}
```
理解 `__ffs` 和 `__clear_bit` 後可以嘗試追蹤一次 `fns` 的操作
###### 參考筆記 : [HenryChaing](https://hackmd.io/@Henry0922/linux2024-homework2#%E6%B8%AC%E9%A9%97%E4%B8%89%E4%BD%9C%E7%AD%94%E5%8D%80)
```
假設 nr 為 4
word = 10010111
------iteration 1-------------------
bit = 0
n = 3
__clear_bit(0, &word) -> 10010110
------iteration 2-------------------
bit = 1
n = 2
__clear_bit(1, &word) -> 10010100
------iteration 3-------------------
bit = 2
n = 1
__clear_bit(0, &word) -> 10010000
------iteration 4-------------------
bit = 4
n = 0
return 4
```
Sign in with Wallet
Connect another wallet