# 2024q1 Homework2(quiz1+quiz2)
contributed by < [`kkkkk1109`](https://github.com/kkkkk1109) >
## 2024q1 第一周測驗題
### 測驗 `1`
此題主要為參考[Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)的方式，來實作非遞迴的快速排序法。
傳統的快速排序法:
```clike
void sort(int arr[], int beg, int end)
{
if (end > beg + 1)
{
int piv = arr[beg], l = beg + 1, r = end;
while (l < r)
{
if (arr[l] <= piv)
l++;
else
swap(&arr[l], &arr[--r]);
}
swap(&arr[--l], &arr[beg]);
sort(arr, beg, l);
sort(arr, r, end);
}
}
```
將所需要排序的陣列輸入，並選擇 `beg` 和 `end` 當作陣列中需要排序的開頭和結尾。主要由以下步驟組成
1. 將 `piv` 值設為 `arr[beg]`，也就是第一個元素， `l` 為第二個元素， `r` 為最後一個元素。
2. 當 `l` < `r` 時，查看 `arr[l]` <= `piv` 是否成立，成立的話，則 `l++` ，查看下個元素；若不成立的話，則將 `arr[l]` 的值和 `arr[r-1]` 的值互換 。
3. 當 `l` == `r` 時，則代表目前 `l` 左方所有元素均<= `piv` ，而右方所有元素均> `piv`。 將 `arr[beg]` 和 `arr[l-1]` 的值交換，將 `piv` 放到中間。
4. 將 `piv` 左，右方的值當成全新陣列，呼叫 `sort` 進行遞迴排序。
而此題則是將第四步的遞迴方式，改成使用兩個 `stack` 來儲存要進行排序的 `beg` 和 `end` ，分別記錄到堆疊 `begin` 和 `end`。
將 `pivot` 設為第一位，並將 `L` 從左到右計算有幾個小於 `pivot` 的數， `R` 則是從右往左掃。
找到之後，將 `R` 放到 `head` ，`L` 放到 `R` ， `pivot` 放到 `L` 。
現在，又可以在對左方紅色和右方藍色的序列進行排序
```graphviz
digraph structs {
node[shape=plaintext];
//pivot [fontcolor="red"];
//L [fontcolor="blue"];
//R [fontcolor="blue"];
//p [fontcolor="black"];
NULL [fontcolor="black"];
begin_L [fontcolor="red"];
end_L [fontcolor="red"];
begin_R [fontcolor="red"];
end_R [fontcolor="red"];
node[shape=box];
struct0 [label= "2"color =red];
struct1 [label= "1"color =red];
struct2 [label= "3"color =red];
struct3 [label= "4",color =green style=filled];
struct4 [label= "5"color =blue];
struct5 [label= "7"color =blue];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
struct4 -> struct5
struct5 -> NULL
}
end_L -> struct2;
begin_L -> struct0;
end_R -> struct5;
begin_R -> struct4;
//L -> struct0;
//R -> struct4;
//p -> struct1;
}
```
而 `begin_L` 、`end_L`、`begin_R`、`end_R` 則是以 `stack` 的方式儲存
```graphviz
digraph structs {
node[shape=plaintext];
begin [fontcolor="black"];
end [fontcolor="black"];
node[shape=box];
struct1 [label= "2"color =red];
struct2 [label= "3"color =red];
struct4 [label= "5"color =blue];
struct5 [label= "7"color =blue];
begin -> struct1;
struct1 -> struct4;
end ->struct2;
struct2 ->struct5;
//L -> struct0;
//R -> struct4;
//p -> struct1;
}
```
下次會取 `begin[i]` 和 `end[i]` 之間的序列來進行排序，做完再 `pop` 取下一序列排序。
* **`AAAA`** 於 `list_tail` 當中，可知是要找尋序列的尾巴，在 `while` 迴圈中前往下個節點，因此為 `(*left)->next` 。
此舉是否會影響所輸入的指標的指標?
使用測驗一的範例 產生 `list` 且不使用 `shuffle`，並顯示出 `list` 和 `tail` 的值。
```
list value is: 0 ,tail value is: 4
```
可知不會影響輸入的指標的指標，除非去影響了 `*left` 的值，也就是儲存 `left` 的地址。
將 `list_tail` 改成以節點為輸入
```clike
node_t *list_tail(node_t *left)
{
while ((left) && (left)->next)
left = ((left)->next);
return left;
}
```
並在呼叫時以節點為輸入，結果仍相同。
```
list value is: 0 ,tail value is: 4
```
因此得出，兩中寫法均可以達成找到 `tail` 的目的，且不改變 `left` 的值。
* **`BBBB`** 也為 `(*left)->next`，因為要去尋找序列的長度，因此也是在 `while` 迴圈當中找到最後一個節點。
* **`CCCC`** 、 **`DDDD`**、 **`EEEE`**
在 `quick_sort` 中 ，以下部分為初始宣告，可以看到 `begin[0]` 和 `end[0]` 位於 `list` 的開頭和尾巴。
```clike
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);
```
在 `while (p)` 中，動作為逐一比較串列中的節點和 `pivot` 的值，並加入 `left` 序列 和 `right` 序列中，因此可以得知 `CCCC` 應為前往下個節點，也就是 ` p->next`。
而在 `while(i >= 0)` 的迴圈當中，`L` 和 `R` 分別為 `begin[i]` 和 `end[i]` 因此可以判定 `begin[i]` 和 `end[i]` 為輸入序列的頭尾， **`CCCC` 為 `list_tail(&left)`** ， **`DDDD` = `list_tail(&right)`**。
### 延伸問題
改進 `quicksort`
1. `max_level` 是否需要達到 `2n` ?
由於 `quick_sort` 會不斷的分割成更小的序列，因此 `max_level` 不可能大於 `n` ，將其設為 `n` 即可。
2. 是否需要 `end` 來存取序列尾巴?
實際看程式碼可發現，`end[i]` 是在此次排序結束時，透過 `list_tail` 來賦值的，可改成於排序開始時，利用 `list_tail(&L)` 來獲得 `R`。
```diff
void quick_sort(node_t **list)
{
- int max_level = 2 * n;
+ int max_level = n;
- node_t *begin[max_level], *end[max_level];
+ node_t *begin[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
- end[0] = list_tail(list);
while (i >= 0) {
- node_t *L = begin[i], *R = end[i];
+ node_t *L = begin[i], *R = list_tail(&L);
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 = CCCC;
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
- end[i] = DDDD;
begin[i + 1] = pivot;
- end[i + 1] = pivot;
begin[i + 2] = right;
- end[i + 2] = EEEE;
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
使用 `clock` 查看運行時間，發現幾乎沒什麼變
### 測驗 `2`
Timsort 致力於從以下三個方面，改進合併排序演算法：
1. 加快合併（merge）過程
2. 減少進行合併的次數。
3. 在某些特定情況下，尋找比合併排序更有效的排序方法
`minrun` : 在合併過程中，run至少要有的長度，而決定方式為讓 `run` 的個數為 **2的冪**，以達到合併時兩個run的數量不會相差太大
`merge_collapse` : 以確認堆疊上的 `run` 長度保持平衡，也保持排序的穩定性
`Galloping mode` : 以 `temp` 為暫存記憶區，將較短的數列放入，並比較另一數列的首個元素，小於首個元素的可以搬離temp，將剩餘的數列進行比較。
傳統合併排序的問題:
* 每層合併需要掃過整個序列，對cache不友善
* 雖然已遞迴的方式，在於連續記憶體中較友善，但於非連續記憶體則較有可能造成cache miss
Timsort改進:
* 非遞迴版本合併排序的改進，邊走訪編合併，而非走訪完再合併。
* 對兩個 runs 中重疊部分合併即可，減少必較的次數。
`list_cmp_func_t` : 藉由回傳值，決定決定兩元素的排序。
> The comparison function cmp must return > 0 if a should sort after b ("a > b" if you want an ascending sort), and <= 0 if a should sort before b or their original order should be preserved. It is always called with the element that came first in the input in a, and list_sort is a stable sort, so it is not necessary to distinguish the a < b and a == b cases.
:::spoiler code
```clike
/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H
#include <linux/types.h>
struct list_head;
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
const struct list_head *, const struct list_head *);
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif
```
:::
* **`AAAA`** 、 **`BBBB`** 、 **`CCCC`**
於 `merge` 中，宣告了 指標 `head` 和 指標的指標 `tail`，可猜測 `head` 為合併後要回傳的 `list_head`，並藉由 `tail` 來連接後續節點，因此 `AAAA` 應為 `&head` 。而迴圈中，以 `cmp` 來決定 `a` 和 `b` 的排序
`cmp` <= 0 : `a` 排序於 `b` 的前方
`cmp` > 0 : `a` 排序於 `b` 的後方
因此可以得知， `*tail` 會指向要放入的節點， `tail` = `BBBB` 和 `CCCC`，為前往**下個地址的指標**的指標，所以為 `&(a->next)` 和 `&(b ->next)`。
```
struct list_head *head;
struct list_head **tail = AAAA;
```
* **`DDDD`** 、 **`EEEE`**
`build_prev_link` 用來建立串列的 `prev` 指標，而最後兩行為建立雙向環狀鏈結，因此 `DDDD` 要指向 `head` 的話，應為 `tail->next` ， 而 `EEEE` 即為 `head -> prev`。
* **`FFFF`**
由於做完 `merge_force_collapse` 後，會只剩兩個 `run` 尚未合併，因此 `FFFF` 應為 `2` 。
### 延伸問題
**`timsort` 的 程式碼解釋**
```clike
void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
stk_size = 0;
struct list_head *list = head->next, *tp = NULL;
if (head == head->prev)
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
`timsort` 引入了 `priv??` 、 ` head` 、 `cmp`，使用 `stk_size` 來追蹤目前 `run` 的個數，並檢查輸入的序列是否只有一個元素，接下來將環狀鏈結斷開。
```clike
do {
/* Find next run */
struct pair result = find_run(priv, list, cmp);
result.head->prev = tp;
tp = result.head;
list = result.next;
stk_size++;
tp = merge_collapse(priv, cmp, tp);
} while (list);
```
接著開始找 `run` ，定義一個 `result` 為找到的 `run` ，接著來看 `find_run` 的內容。
* **`find_run`**:
目的為在給定的串列中選出適合的 `run` ，將以 `ascend` 排序好的元素結合成一個 `run` 。
1. 若有個串列 [1、3、8、5、2]，比較 `list` = [1] 和 `next` = [3]， 此時 `cmp` <= 0 ，代表為 `ascend` 排序， `run` = [1、3]，
2. 再看下個元素是否也構成 `ascend` ，直到不成立。此時所選出的 `run` 為 [1、3、8]，而 `result` 中的 `head` 會存取 [1] 的指標， `next` 則指向 [5] ，代表此 `run` 的下一點。
3. 下一次再呼叫 find_run 的話， 則會從 [5] 開始找，而下一個 [5、2] 構成 descend ，會將此串列反轉成 [2、5]，而原先 `head` 指向 [5] ，則會改成指向 [2]。而此輪的 `run` 為[2、5]。
回到 `timsort` 的程式碼中，以`result` 來指向此 `run`，並令 `tp` 為上個run，且此 `result` 的 `head->prev` 為 `tp`。下面為多個 `run` 的示意圖
```graphviz
digraph structs {
node[shape=plaintext];
//head1 [fontcolor="black"];
//head2[fontcolor="black"];
//head3 [fontcolor="black"];
NULL [fontcolor="black"];
node[shape=box];
result1 [label= "result1.head"];
result2 [label= "result2.head"];
result3 [label= "result3.head"];
run1 [label= "[1、2、5]"];
run2 [label= "[4、8、9]"];
run3 [label= "[2、3]"];
result2->result1 ;
result3->result2 ;
result1->NULL ;
result2->run2 ;
result3->run3 ;
result1->run1 ;
}
```
接下來會呼叫 merge_collapse，來進行 `run` 的合併
* **`merge_collapse`**:
```clike
static struct list_head *merge_collapse(void *priv,
list_cmp_func_t cmp,
struct list_head *tp)
{
int n;
while ((n = stk_size) >= 2) {
if ((n >= 3 &&
run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
(n >= 4 && run_size(tp->prev->prev->prev) <=
run_size(tp->prev->prev) + run_size(tp->prev))) {
if (run_size(tp->prev->prev) < run_size(tp)) {
tp->prev = merge_at(priv, cmp, tp->prev);
} else {
tp = merge_at(priv, cmp, tp);
}
} else if (run_size(tp->prev) <= run_size(tp)) {
tp = merge_at(priv, cmp, tp);
} else {
break;
}
}
return tp;
}
```
* 若目前只有 2 個 `run` ，則合併
* 若大於 2 個，則以以下判斷來讓 `run` 的長度平衡
以 A、B、C為堆疊頂端的 3 個 `run` 須保持以下原則來合併
* A > B + C
* A > C
`run_size(tp->prev->prev)` 、`run_size(tp->prev)`、`run_size(tp)` 即為 A、B、C 三個 `run` ，並依照上述情況進行判斷並合併。
而呼叫的 `merge_at` 會將所引入的 `tp` 和上個 `run` 進行合併。
，依照上述的合併方式，最後會剩餘 3 個 `run` ，以 `merge_forece_collapse` 來將剩餘的 `run` 合併，直到剩餘 2 個 `run`，將兩個 `run` 以 `build_prev_link` 來連成環狀序列，再呼叫`merge_final` 來將兩序列合併。
* 或許可改進的點: 為何要先接成環狀序列再合併呢? 若先合併會發生什麼事
## 2024q1 第二周測驗題
### 測驗 `1`
此題為[LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)，得到對同一二元樹的前序(preorder) 和 中序(inorder) 的形式，來建構二元樹。
* **`AAAA`**
於 `hlist_add_head` 中，可知是將節點 `n` 加入 `h` 後面，另`ｎ` 為此串列的第一個節點。參考[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)可知，`next` 指向下個節點的地址，而 `pprev` 則指向前個節點指向自身地址的指標。因此 `AAAA` 應為 `h->first`。
* **`BBBB`** 、 **`CCCC`**
`find` 為找尋雜湊表中的對應的值，使用 `h_list_for_each` 來逐一走訪串列，因此 `BBBB` 應為 `heads[hash]` 。而 `CCCC` 應為 `list_entry`，用以找尋 `struct order_node` 的 `val`。
* **`DDDD`**
於 `node_add` 中，可以看出是要增加一個節點，引用到了 `hlist_add_head` ，代表此節點是要加在 `head` 後方，因此 `DDDD` 即為 `heads[hash]`。
### 延伸問題
參考 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)
首先，`hlist_node` 為 Linux 核心中，處理 hash 數值的結構
```clike
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
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:ht1 -> hn1
hn1:next -> hn2
hn2:next -> null1
hn2:prev:s -> hn1:next:s
map:ht5 -> hn3
hn3:next -> null2
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
}
```
以 `next` 來指向下個節點， `pprev` 來指向上個節點的`next` 的指標，以此方式來避免移除節點需要考量多個情境。
此題使用了 `hash table` 結構來完成 `order_node` 的設計，如下圖
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="hlist_head|<hd1>hhead[1].first |<hd2>hhead[2].first|hhead[3].first |... |hhead[size] "];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="<hn>hlist_node | {<prev>pprev | <next>next}"];
label="order_node 1"
val [label="val"];
idx [label="idx"];
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="<hn>hlist_node | {<prev>pprev | <next>next}"];
label="order_node 2"
val2 [label="val"];
id2x [label="idx"];
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="<hn>hlist_node | {<prev>pprev | <next>next}"];
label="order_node 3"
val3 [label="val"];
id23 [label="idx"];
}
map:hd1->hn1:hn
hn1:next -> hn2:hn;
hn1:prev -> map:hd1[color = red]
hn2:prev -> hn1:next[color = red]
hn2:next -> null1;
map:hd2->hn3:hn
hn3:prev -> map:hd2[color = red]
hn3:next -> null2;
}
```
接下來介紹各個操作
* **`hlist_add_heads`** : 將新節點加入至雜湊的 `hlist_head` 的第一位。
* **`node_add`** : 創建一個新的 `order_node` ，賦值後，找到其對應的 `hlist_head` 加入。
* **`TreeNode *buildTree`** :
首先，創立一個雜湊表，大小以 `inorderSize` 定義，並且於 `node_add` 將 `inorder` 中的順序和數值填入，並利用 `hash` 來找到對應的 `hlist_head` 加入。
```clike
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
for (int i = 0; i < inorderSize; i++)
INIT_HLIST_HEAD(&in_heads[i]);
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
}
```
接下來 呼叫 `dfs` 進行 [深度優先搜索](https://en.wikipedia.org/wiki/Depth-first_search)
`dfs`:
首先，先查看 `pre_low`、 `pre_high` 、 `pre_low` 和 `pre_high `來判斷範圍是否合理
```clike
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;
.....
}
```
利用 `find` 找尋此數於 `inorder` 中的 `inx` ，原因如下
preorder = [**3** 9 20 15 7];
inorder = [9 **3** 15 20 7];
由於 `preorder` 中，第一個數字會是 `root`， `inorder` 中 `root` 的左、右方分別代表左、右子樹，在此情境可以知道 [9] 為左子樹，[15 20 7] 為右子樹，且左子樹的 `root` 為 [9]，右子樹的 `root` 為 [20]。
```clike
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;
```
得到左右子樹的 `root` 和範圍後，即可透過遞迴的方式進行 `dfs` ，最後建立二元樹。
#### Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討
什麼是 `cpgroups`?
> cgroups (control groups)是Linux kernel內建的一個機制，可以以進程為最小單位，對可使用的CPU、memory、裝置I/O等資源進行限制、分割。
在[bpf: rstat: cgroup hierarchical stats](https://lwn.net/Articles/904093/)，可以看到對於 `cgroup walk` 的相關敘述
> This patch series allows for using bpf to collect hierarchical cgroup
stats efficiently by integrating with the rstat framework. The rstat
framework provides an efficient way to collect cgroup stats percpu and
propagate them through the cgroup hierarchy.
> The stats are exposed to userspace in textual form by reading files in
> bpffs, similar to cgroupfs stats by using a cgroup_iter program.
> cgroup_iter is a type of bpf_iter. It walks over cgroups in four modes:
> - walking a cgroup's descendants in pre-order.
> - walking a cgroup's descendants in post-order.
> - walking a cgroup's ancestors.
> - process only a single object.
>
> If no order is specified, the default order is pre-order.
說明可使用 `bps` 的方式來蒐集不同階層的 `cgroup` ，並以四種方式來禁行走訪，若未特殊設定的話，會以 `pre-order` 的方式走訪。
[`kernel/cgroup/cgroup.c` ](https://elixir.bootlin.com/linux/latest/source/kernel/cgroup/cgroup.c#L704)中，巨集 `cgroup_for_each_live_descendant_pre` 以 `pre-order` 的方式進行走訪
```clike
#define cgroup_for_each_live_descendant_pre(dsct, d_css, cgrp) \
css_for_each_descendant_pre((d_css), cgroup_css((cgrp), NULL)) \
if (({ lockdep_assert_held(&cgroup_mutex); \
(dsct) = (d_css)->cgroup; \
cgroup_is_dead(dsct); })) \
; \
else
```
又引用了另一個在[`include/linux/cgroup.h`](https://elixir.bootlin.com/linux/latest/source/include/linux/cgroup.h#L240) 中的巨集 ` css_for_each_descendant_pre(pos, css)`，並且有以下說明
> css_for_each_descendant_pre - pre-order walk of a css's descendants
@pos: the css * to use as the loop cursor
@root: css whose descendants to walk
Walk @root's descendants. @root is included in the iteration and the
first node to be visited. Must be called under rcu_read_lock().
> If a subsystem synchronizes ->css_online() and the start of iteration, a
> css which finished ->css_online() is guaranteed to be visible in the
> future iterations and will stay visible until the last reference is put.
> A css which hasn't finished ->css_online() or already finished
> ->css_offline() may show up during traversal. It's each subsystem's
> responsibility to synchronize against on/offlining.
> For example, the following guarantees that a descendant can't escape
> state updates of its ancestors.
```clike
my_online(@css)
{
Lock @css's parent and @css;
Inherit state from the parent;
Unlock both.
}
my_update_state(@css)
{
css_for_each_descendant_pre(@pos, @css) {
Lock @pos;
if (@pos == @css)
Update @css's state;
else
Verify @pos is alive and inherit state from its parent;
Unlock @pos;
}
}
```
說明可以利用 `pre-order` 的方式來保證子節點可以在父節點更新後再進行狀態繼承。
### 測驗 `2`
此題為針對 [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/)，提出 LRU 的 C 實作
* **`EEEE`**
`hlist_del` 為刪除節點 `n`， 而 `next` 為 `n` 的下一節點，由於 `pprev` 為指向前一節點指向自身的指標，因此 `EEEE` 應為 `next-> pprev`
* **`FFFF`** 、 **`GGGG`**
`lRUCacheFrere` 用以釋放快取記憶體， 使用`list_entry` 來找到 `struct LRUNode` ，`FFFF` 應為 `link` ，為 `LRUNode` 中定義的 `list_head`， `GGGG` 為 `pos` ，及刪除目前的 `list_head` 。
* **`HHHH`** 、 **`IIII`**
`lRUCacheGet` 用以獲得快取中的值，`HHHH` 應為 `node` 。若 `key` 符合，則呼叫 `list_move` ，將節點移出並放入串列中， `IIII` 為 `pos` ，及此節點的 `list_head`。
* **`JJJJ`** 、 **`KKKK`**
`lRUCachePut` 將資料放入快取，`JJJJ` 應為 `node` 。若 `key` 符合，則呼叫 `list_move` ，將節點移出並放入串列中， `KKKK` 為 `pos` ，及此節點的 `list_head`。
### 延伸問題
解釋 [LRU Cache](https://leetcode.com/problems/lru-cache/) 的實作
* **`lRUCacheCreate`**: 用以創造快取空間。
* **`lRUCachePut`**: 將資料放入快取。
以 `key` 來取得 `hash_index` ，並查看 `hash` 所對應到的 `hlist_node` 中有無此`key`
1. 有對應到，將值 `value` 存入
2. 無對應到，且記憶體已滿。以 `list_last_entry` 查看 `dhead` 所存取的最後一個快取， 使用`list_move` 插入到 `dhead` 的第一位，並將此 `node` 和原始的 `hhead[hash]` 斷開，再接入新的 `hhead[hash]`。
3. 無對應到，且記憶體未滿，代表還可以再開新的快取空間，則開新快取空間，並連結其雜湊表。
* **`lRUCacheGet`**: 將資料放入快取。
以 `key` 來取得 `hash_index` ，並找此 `hash`是否有key的值，並將其放置於 `dhead` 的第一位。
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="LRUCache |<dh>dhead |hhead[1] |hhead[2] |hhead[3] |... |hhead[capacity] "];
node[shape=none]
null1 [label=NULL]
null2 [label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="<nd>hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="<nd>hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="<nd>hlist_node | {<prev>pprev | <next>next}"];
label="hash_key 3"
}
map:ht1 -> hn1
hn1:next -> hn2
hn2:next -> null1
hn2:prev:s -> hn1:next:s
map:ht2 -> hn3
map:dh->hn1[color=red]
hn1:nd->hn2[color=red]
hn2:nd->hn3[color=red]
hn3:next -> null2
hn1:prev:s -> map:ht1
hn3:prev:s -> map:ht5
}
```
可以發現在無論在 `lRUCacheGet` 或 `lRUCachePUT` 中，都會進行 `list_move`，將節點連接至 `dhead` 的頭，可知最少用到的，即為 `dhead` 的 `tail`，可以 `LRU` 的原則，將最少次使用到的快取給替換掉，也可以在 `lRUCachePUT` 的第二個情況看見，將 `list_last_entry` 的快取節點給替換掉。
### 測驗 `3`
使用 `find_nth_bit` 可在指定的記憶體空間找出第 N 個設定的位元 (即 1)，完成程式碼實作。
* `BITMAP_LAST_WORD_MASK` :
```clike
#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
```
`~0UL` 為產生一個全為1的遮罩，`(BITS_PER_LONG - 1)` 為確保 right shift 最多就是 63，和 `-nbit` 做 `&` 運算則可以計算要 right shift 多少位元。
> BITMAP_LAST_WORD_MASK(5) = 0x1f = 0b11111
* `BITMASK` :
```clike
#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
```
`(nr) % BITS_PER_LONG)` 取得 要left shift 幾個位元， 確保不會超出最長位元。
> BIT_MASK(5) = 0x20 = 0b10 0000
* `BIT_WORD` :
```clike
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
```
計算 `nr` / `64` 的商，可能用來計算 `offset` ?
* `__const_hweight8` :
```clike
#define __const_hweight8(w) \
((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
(!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
(!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
(!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))
```
用來計算此數二進位由幾個 `1` 所組成，即為 `hamming weight`
> __const_hweight8(63) = 6 = 0b10 0000
> 63 = 0b111111
可用在 `__const_hweight16` 、 `__const_hweight32` 、 `__const_hweight64`，計算不同長度的 `hamming weight`。
* `AAAA` :
位於 `static inline unsigned long __ffs(unsigned long word)` 中，用以找尋 `first bit`。透過不同的 `bitmask` 來計算0的個數，而 `AAAA` 應為找尋較低 32 位元是否為 0 ，若為 0， 則可以直接將計算數 `num` 加 32 ，接下來是尋找較高位元。因此， `AAAA` 為 `0xffffffff`。
> __ffs(0x2000) = 13
* `__clear_bit` :
由名稱可知，其目的為刪除特定的bit，但是不確定是一個還是多個，因此，查看 此巨集使用的時機。
```clike
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word) {
unsigned int bit = __ffs(word);
if (n-- == 0)
return bit;
__clear_bit(bit, &word);
}
return BITS_PER_LONG;
}
```
在 `fns` 中，可以看到對於輸入的 `word` ，會先進行 `ffs` ，找到第一個set，並查看 `n-1` 是否為零，成立即代表這個 `bit` 是想要找到的第`n` 個 `bit` 。不成立則呼叫 `clear_bit` 再重新進入迴圈。因此 `clear_bit` 應該是要刪除目前的 `first set bit` ，再重新做 `ffs` 找下一個 `set bit`。
```clike
#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
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 &= BBBB;
}
```
另外，若考量到所要刪除的 `bit` 大於 `BITS_PER_LONG` 的話，則會使用巨集 `BIT_WORD` 來對 `address` 進行偏移，可以看到使用了 `p` 存取需要偏移的地址，再取值進行 `~` 操作，來去除特定的 `bit`。
* `BBBB` :
由以上可知 `BBBB` 應為 `~mask` ，也就是除了這個 `bit` 以外的位數均為 `1` ，來將 `first set bit` 給去除。
接下來開始進行於記憶體空間中找尋第 N 個`bit`。
* `find_nth_bit` :
`addr` : 開始找尋的地址
`size` : 選擇要從幾位中尋找
`n` : 要找尋第幾個 `bit`
```clike
static inline unsigned long find_nth_bit(const unsigned long *addr,
unsigned long size,
unsigned long n)
{
if (n >= size)
return size;
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
return val ? fns(val, n) : size;
}
return FIND_NTH_BIT(addr[idx], size, n);
}
```
**1. 若 `n` >= `size` ，則 return size，因為找尋的 `bit` 已超過範圍。**
**2. 查看 `small_const_nbits(size)` 是否成立**
* `small_const_nbits` :
```clike
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
```
於 [`include/linux/bitmap.h`](https://android.googlesource.com/kernel/msm/+/android-msm-hammerhead-3.4-marshmallow-mr2/include/linux/bitmap.h) 中，可看到此巨集廣泛出現，並可以在 `include/asm-generic/bitsperlong.h` 中找到定義
>small_const_nbits(n) is true precisely when it is known at compile-time
that BITMAP_SIZE(n) is 1, i.e. 1 <= n <= BITS_PER_LONG. This allows
various bit/bitmap APIs to provide a fast inline implementation. Bitmaps
of size 0 are very rare, and a compile-time-known-size 0 is most likely
a sign of error. They will be handled correctly by the bit/bitmap APIs,
but using the out-of-line functions, so that the inline implementations
can unconditionally dereference the pointer(s).
可知此操作在編譯時期時，是否已得到此數，並檢查是否在 `BITS_PER_LONG` 和 1 之間；而 0 的話就代表可能是錯誤，畢竟不會有人要找第 `0` 個 bit，最後再交由外部的操作來進行 `bit` 運算，避免 `inline` 操作出現錯誤。
因為目前確定 `size` 介於 1 ~ 64 之間，僅看 `size` 大小即可，使用巨集 `GENMASK` 來產生 `size` 大小的 `bitmask`。再呼叫 `fns` 計算。
**3. `size` 大於 `BIT_PER_LONG` 的情況 :**
引用巨集 `FIND_NTH_BIT` 來進行超出記憶體範圍的找尋。
首先，先判斷
`idx * BITS_PER_LONG + nr >= sz` : 檢查目標是否在範圍內，若超過則返回 `size`。
接著，查看目前的 `tmp` 的 `hamming_weight` ，若大於 `nr` 的話，則代表可以在此範圍內找出解答，
若找不到的話，則進行 `nr-=w` ，來前往下個
最後，當迴圈結束後，檢查 `sz` 是否能夠被 `BITS_PER_LONG` 整除，利用巨集 `BITMAP_LAST_WORD_MASK` 保留 `size` 位的 `bit` ，同時 `size` 外的 `bit` 為零。因此 `CCCC` 為 `%` 。
最後返回 `sz` 為輸出。
Sign in with Wallet
Connect another wallet