# 2024q1 Homework2 (quiz1+2)
contributed by <ShawnXuanc>
## 第一週測驗
### 測驗`1`
#### 運作原理
測驗 `1` 的程式碼內容，實作一個非遞迴的快速排序，排序的對象為鏈結串列，使用 `node_t` 的指標陣列來模擬 `stack` 的部分
```c
int max_level = 2 * n;
...
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
```
在這次測驗中所使用的演算法為非遞回版本的 `quick sort` ，首先會先取得傳入的 `list` 長度，並將 `max_level` 設置為長度的兩倍即 `2 * n` ，並使用 `left` 跟 `right` 來暫存經由判斷比 `pivot` 大以及比 `pivot` 小的節點
```c
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);
}
...
}
```
迴圈中設定當前 `pivot` 並將 `p` 移動到 `pivot` 的下一個節點再將 `pivot` 斷開串列的連結，接下來在內層的 `while` 迴圈中可以看到會先將 `n` 指向目前鏈結串列中的第一個元素也就是 `p`，在移動將 `p` 的指標往前移動，最後依造與 `pivot` 的大小判斷分別將比 `pivot` 大的節點加入 `right` 比 `pivot` 小的節點加入 `left` 之中
* `p` 以及 `pivot`
```graphviz
digraph G {
{
rank = "same"
rankdir = "LR"
n1 [label="3", shape="square"]
n2 [label = "5", shape = "square"]
n3 [label = "1", shape = "square"]
n4 [label = "4", shape = "square"]
NULL1[label="NULL", shape="plain"]
NULL2[label="NULL", shape="plain"]
n1->NULL1
n2->n3->n4->NULL2
}
pivot[label="pivot", shape="plain"]
p[label="p",shape="plain"]
pivot->n1
p->n2
}
```
* 進入迴圈 `n = p` 以及 `p = p->next`
```graphviz
digraph G {
{
rank = "same"
rankdir = "LR"
n2 [label="5", shape="square"]
n3 [label="1", shape="square"]
n4 [label="4", shape="square"]
NULL1[label="NULL", shape="plain"]
n2->n3->n4->NULL1
}
n[label="n",shape="plain", fontcolor=orange]
p[label="p",shape="plain"]
n->n2
p->n3
}
```
* 將比 `pivot` 小的節點的放置到 `left` 比 `pivot` 大的節點的放置到 `right`
```graphviz
digraph G {
rank = "same"
rankdir = "LR"
right [label="right", shape="plain", fontcolor="red"]
pivot[label="pivot", shape="plain"]
left [label="left", shape="plain", fontcolor="blue"]
n1 [label="3", shape="square"]
n2 [label="5", shape="square"]
n3 [label="1", shape="square"]
n4 [label="4", shape="square"]
left->n3
pivot->n1
right->n4->n2
}
```
```c
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)
```
* 使用 `begin` 以及 `end` 來記錄 `left` 跟 `right` 的頭以及尾
```graphviz
digraph G {
{
rankdir = "LR"
rank="same"
n1[label="1", shape="square"]
}
begin[label="begin[i]", shape="plain", fontcolor="blue"]
end[label="end[i]", shape="plain", fontcolor="red"]
begin->n1
end->n1
}
```
```graphviz
digraph G {
{
rankdir = "LR"
rank="same"
pivot[label="3", shape="square"]
}
begin[label="begin[i+1]", shape="plain", fontcolor="blue"]
end[label="end[i+1]", shape="plain", fontcolor="red"]
begin->pivot
end->pivot
}
```
```graphviz
digraph G {
rankdir = "LR"
n1 [label="4", shape="square"]
n2 [label="5", shape="square"]
{
rank=same
begin[label="begin[i+2]", shape="plain", fontcolor="blue"]
begin->n1
}
{
rank=same
end[label="end[i+2]", shape="plain", fontcolor="red"]
end->n2
}
n1->n2
}
```
下一次開始的位置會從 `begin[i+2]` 開始並將鏈結串列進行切割直到剩下一個節點為止，接著依序將切割過後的串列加入到 `result`之中，形成一個排序好的鏈結串列
#### 改善方式
在這邊將長度設置為 `2 * n` 其實是沒有必要的，因為在將節點以指標陣列暫存時最多只會用到 `n` 個空間因此可以將 `max_level` 的大小進行調整來節省空間
而再將串列的尾部元素的位置賦值給 `end[i]` 時 會用到 `list_tail` 函式需要 `O(n)`的時間來遍歷整個串列，因此可以考慮使用其他的資料結構像是環狀的鏈結串列，用這樣的方式就可在 `O(1)` 的方式來取的串列的尾端
為了避免 `quick sort` 在 `partition` 的階段選擇到最大最小，可以有更多的`pivot` 選擇來進行優化以防止 `worst case`
### 測驗`2`
#### 運作原理
`Tim sort` 演算法結合了 `merge sort` 以及 `insert sort` 的合併方式，在排序一開始會先找尋序列中已經排序好的部份，藉由 `find_run`來尋找，若找到的串列為遞減的串列，會將串列反轉直到遇到遞增的並更新指標內容，若是遞增的串列，則將指針向後移動，直到遇到遞減的
```c
static struct pair find_run(void *priv,
struct list_head *list,
list_cmp_func_t cmp)
{
size_t len = 1;
struct list_head *next = list->next, *head = list;
struct pair result;
if (!next) {
result.head = head, result.next = next;
return result;
}
if (cmp(priv, list, next) > 0) {
/* decending run, also reverse the list */
struct list_head *prev = NULL;
do {
len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;
} while (next && cmp(priv, list, next) > 0);
list->next = prev;
} else {
do {
len++;
list = next;
next = list->next;
} while (next && cmp(priv, list, next) <= 0);
list->next = NULL;
}
head->prev = NULL;
head->next->prev = (struct list_head *) len;
result.head = head, result.next = next;
return result;
}
```
* `find_run` 會先比較串列的遞增關係找出已排序好的串列，若找到的是遞增的串列則回傳，若找到的是遞減的則進行反轉再回傳
```c
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;
}
```
下一步要藉由 `merge collapse` 來判斷串列是否有符合條件，若不符合則將兩個 `run` 進行合併，合併完離開函式之後，再將所有的 `runs` 進行合併
條件為要長度要符合：
1. A > B + C
2. B > C
## 第二週測驗
### 測驗`1`
藉由給定的二元樹前序以及中序來進行重建，而在測驗一中所使用節點的資料結構為 `hlist_node` ，在前面由一個 `hlist_head` 為開頭而後接著 `hlist_node`的形式這邊的 `pprev` 是以 `**preve` 的方式與前一個節點做連接，藉由這樣指標的指標可以省去在第一個 `hlist_node` 的 `pprev` 指向 `head` 時因結構不同無法指向的問題，也可以在操作上更加便利
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_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}", group = list];
node_3[label = "<m>hlist_node_3 | {<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;
node_1:p -> list_head:n;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> NULL;
}
```
在測驗的這個程式的大致想法為，先將二元樹的 `inorder` 的內容記錄到 `hash table`中儲存起來以便用O(1)的時間找到所對應的位置，再利用 `dfs` 遍歷 `preorder` 的內容，使用 `find` 來找到 `inorder` 與 `preorder` 所對應的位置來進行遞迴重新建立一顆二元樹
```c
static inline void node_add(int val,
int idx,
int size,
struct hlist_head *heads)
{
struct order_node *on = malloc(sizeof(*on));
on->val = val;
on->idx = idx;
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, &heads[hash]);
}
```
使用 `node_add` 函式來將節點加入到 `hlist` 中讓之後再進行 dfs 時可以快速的取的 `inorder` 的資訊
```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` 作為 `TreeNode` 的指標 `tn` 的 `val` 為 `preorder` 陣列中的元素在設定好 `tn` 的內容之後會使用 `find` 來找到 `inorder` 在 `hlist (Hash Table)` 中與 `preorder` 的值相對應的位置即為子樹中 `root` 的位置
藉由 `root` 的位置可以切割陣列的左右兩邊也就是 `[(tn->left) root (tn->right)]` 左右遞迴建立左子樹與右子樹
`tn->left` 的 `dfs` 參數 `idx - in_low`為在 `inorder` 陣列中從起點到所選擇的 `root` 的節點個數，用這樣的方式來取得 `pre_high` 的值就可以對應到左半邊的節點個數，另一邊 `tn->right` 同理也是
#### 改善方法
可以使用更簡單的資料結構來建立 `hash table` 而不用用到 `hlist_node` 這樣較為複雜的結構，以節省實作的複雜以及空間的利用
記憶體空間的釋放，在最後將二元樹重建之後未釋放 `hash table` 的記憶體空間，
可以在 `return` 之前將不使用的 `hash table` 釋放掉以避免記憶體洩露的問題
`hash function` 使用較為簡單的方式，可以考慮使用更為複雜的 `hash function` 來減少碰撞的發生
#### Linux 相關原始碼
[pre-order-walk](https://elixir.bootlin.com/linux/latest/source/kernel/cgroup/cgroup.c#L6047) 的應用在 cgroup/cgroup.c 裡面的一個函式 css_next_Descendant_pre
[cgroup_iter](https://elixir.bootlin.com/linux/latest/source/kernel/bpf/cgroup_iter.c#L204) 中有提供不同的探訪方式
[cgroup](https://elixir.bootlin.com/linux/latest/source/kernel/cgroup/cgroup.c) 的功能在於限制、控制與隔離 process 所使用到的系統資源包含
* 資源限制
* 優先權
* 結算
* 控制
### 測驗`2`
#### 運作原理
`LRU Cache` 的運作原理為最近最不常使用的會被替換掉，而每當有使用時會將使用的元素值更新，而當 `Cache` 的容量滿了的時候會進行移除，移除的對象即為最不常被使用的
```c
int lRUCacheGet(LRUCache *obj, int key)
{
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *cache = list_entry(pos, LRUNode, node);
if (cache->key == key) {
list_move(&cache->link, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
根據 `hash` 的值來判斷所要的 `key` 值是否存在於 `hlist` 之中若存在就將其移動到鏈結串列的最前端，代表為最新使用到的，如果不存在則回傳 `-1`
```c
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *cache = NULL;
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *c = list_entry(pos, LRUNode, node);
if (c->key == key) {
list_move(&c->link, &obj->dhead);
cache = c;
}
}
.....
}
```
函式用來將 `key` 值放入到 `cache` 之中，一開始會先計算 `hash`的值並判斷 `key`值是否存在於 `cache` 之中，如果存在會將 `key` 值在 `hash table` 之中的位置進行更新，也就是移動到前面的位置，代表為最新使用到的，並且記錄起來，以便判斷是否有找到
```c
if (!cache) {
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]);
} else {
cache = malloc(sizeof(LRUNode));
hlist_add_head(&cache->node, &obj->hhead[hash]);
list_add(&cache->link, &obj->dhead);
obj->count++;
}
cache->key = key;
}
cache->value = value;
```
接續上方的程式碼藉由 `cache` 來判斷是否有找到這個值，如果沒有找到的話則判斷目前 `cache` 的容量有沒有滿，如果滿了就將最後一個串列的元素移動到第一個代表刪除了最後一個節點並且新增一個節點，並刪除最後一個元素在 `hlist` 中的內容再加入
若 `cache` 的容量未達上限，則新增一個節點並更新 `hash table` 以及串列的內容，最後再把 `key` 跟 `value` 重新設定
#### 改善方式
#### Linux 相關原始碼
[LRU cache](https://elixir.bootlin.com/linux/latest/source/lib/lru_cache.c#L549)
### 測驗3
```c
#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
```
這個聚集的功能在於將位於 `nr` 位置的 `bit` 設置成 `1` 而 % BITS_PER_LONG 是要確保 `nr` 介於 `0 ~ BITS_PER_LONG - 1` 之間
```c
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
if ((word & 0xffffffff) == 0) {
num += 32;
word >>= 32;
}
#endif
if ((word & 0xffff) == 0) {
num += 16;
word >>= 16;
}
if ((word & 0xff) == 0) {
num += 8;
word >>= 8;
}
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
if ((word & 0x3) == 0) {
num += 2;
word >>= 2;
}
if ((word & 0x1) == 0)
num += 1;
return num;
}
```
用來找到 `word` 之中的第一個 `bit` 為 `1` 的位置，一開始先檢查是否為 `64` 位元的系統，使用 `num` 來記錄最低位元的位置依序判斷若沒找到就將 `word` 向右移直到找到 `bit` 為 `1` 的位置
```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);
}
```
函式的作用在於將指定的 `bit` 清除掉 `mask` 的用意在於設定要遮罩的位元位置，最後在用 `not` 的方式將其變成 `0`， 在用這個 `0` 為元的位置做 `and` 來將 `mask` 位置的位元消除成 `0`
```c
#define GENMASK(h, l) \
(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
```
這巨集的功能在於可以將 `h ~ l` 位元的位置設定成 `1` 其他設定成 `0`，在這個巨集中 `(~0UL)` 為一個位元皆為 `1` 的數 ，而 `1UL << (l))` 為將位置 `l` 設置成 `1` 再使用位元皆為`1` 的數去減掉第 `l` 個位置為 `1` 的數，使用這樣的方式可以獲得一個 `....111101111` 這樣的結果，最後再加上 `1` 就可以藉由進位的方式得到 `....111110000` ，得到 `l`之前皆為 `0`， 在用 `(~0UL >> (BITS_PER_LONG - 1 - (h))))` 可以想為將低位元的 `h + 1` 個位置都設定為 `1` 其他為 `0`也就是 `h = 2` 時右邊會是 `111`，藉由這樣的方式來將 `h ~ l` 的位元設定成 `１`
#### Linux 相關原始碼
[bitops](https://elixir.bootlin.com/linux/latest/source/arch/mips/lib/bitops.c) `linux kernel`
Sign in with Wallet
Connect another wallet