# 2024q1 Homework2 (quiz1+2)
contributed by < [yuyuan0625](https://github.com/yuyuan0625) >
## 第一週測驗
### 測驗一
**鏈結串列結構體 `node_t`:**
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
```graphviz
digraph node_t
{
node [shape= "record"];
rankdir= "LR";
subgraph cluster_0
{
label= "node_t";
node1 [label= "<head>value | next | {<left> left | <right> right}"];
}
}
```
**補齊程式碼**
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
此函式的目的是尋找鏈結串列的尾端，因此需要逐一走訪每個節點，`node_t **left` 為指標的指標，因此每一次迴圈都需要將 `left` 的值更新為指向下一個節點指標( `next` )的位址, 因此 `AAAA` 應為 `(*left)->next`
示意圖:
```graphviz
digraph initial
{
graph [fontsize=12, compound=true];
node [shape="box"];
rankdir = "LR"
"**left" [fontcolor=red, color=red, shape=plaintext]
"*head" [shape=plaintext];
{
rank=same;
"**left"->"*head" [color=red]
"*head"->node1 ;
}
{
node1->node2
node2->node3
}
}
```
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
此函式和 `list_tail()` 相同，每一次迴圈都需要往下一個節點走訪。
因此 `BBBB` 同為 `(*left)->next)`
```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);
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 = 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;
}
```
在此段程式碼中，
**內部迴圈**會由 `begin[i]->next` 循序走訪至 `end[i]`，並和 `pivot` 比較，若大於 `pivot` 加入 `right`，反之則加入 `left`。
因此，和前兩題相同，都是要循序走訪鏈結串列，`p = p->next`。
**外部迴圈**：將鏈節串列分為三段：
1.小於等於 `pivot`
2.`pivot`
3.大於等於 `pivot`
並分別將其串列開頭分別存在 `begin[i]` , `begin[i+1]` , `begin[i+2]`，並使用 `end[i]` , `end[i+1]` , `end[i+2]` 儲存串列尾端。
因此 `DDDD` 就是 `left` 鏈結串列的尾端，使用 `&list_tail(left)` 來獲得其位址。同理，`EEEE` 即為 `&list_tail(right)` 。
#### 延伸問題
1. 解釋上述程式碼的運作原理，提出改進方案並予以實作。
以實際例子解釋：
```graphviz
digraph initial
{
node [shape="box"];
rankdir = "LR";
begin0 [label= "begin[0]", shape= plaintext]
end0 [label= "end[0]", shape= plaintext]
node4 [label= "4"]
node3 [label= "3"]
node5 [label= "5"]
node1 [label= "1"]
NULL [shape="plaintext"]
{
node4->node3
node3->node5
node5->node1
node1->NULL
}
{
rank= same;
begin0->node4
}
{
rank= same;
end0->node1
}
}
```
選第一個節點 `4` 作為 `pivot` ，將 `pivot` 從串列移除，並比較後面所有節點和 `pivot` 的大小關係，將小於 `pivot` 的節點利用 `list_add` 加入 `left` ，大於 `pivot` 的節點加入 `right` 。
```graphviz
digraph L1
{
node [shape="plaintext"];
rankdir = "TB";
node4 [label= "4", shape="box"]
node3 [label= "3", shape="box"]
node5 [label= "5", shape="box"]
node1 [label= "1", shape="box"]
{
"begin[1]"->node4
node4->"end[1]" [dir=back]
}
{
left->node1
"begin[0]"->node1
node1->node3
node3->"end[0]" [dir=back]
}
{
right->node5
"begin[2]"->node5
node5 -> "end[2]" [dir=back]
}
}
```
`i += 2`，此時 `i=2`，`begin[2]==end[2]`，因此利用 `add_list` 將 5 加入 `result`，`i--`。
```graphviz
digraph res
{
rankdir = "LR"
node [shape="box"];
node5 [label= "5"]
result [shape=plaintext];
result->node5
}
```
`i=1` ，`begin[1]==end[1]`，將 4 加入`result`，`i--`。
```graphviz
digraph res
{
rankdir = "LR"
node [shape="box"];
node4 [label= "4"]
node5 [label= "5"]
result [shape=plaintext];
result->node4
node4->node5
}
```
`i=0` , 選 1 做 `pivot`，3 加入`right`, `i+=2`
```graphviz
digraph L2
{
node [shape="plaintext"];
rankdir = "TB";
node1 [label= "1", shape="box"]
NULL
node3 [label= "3", shape="box"]
{
"begin[1]"->node1
"end0[0]"->node1
}
{
left->NULL
"begin[0]"->NULL
"end[0]"->NULL
}
{
right->node3
"begin[2]"->node3
"end[2]"->node3
}
}
```
`i=2`，`begin[2]==end[2]`，將 3 加入 `result` ，`i--`
`i=1`，`begin[1]==end[1]`，`i--`
`i=0`，`begin[0]==end[0]`，將 1 加入 `result` ，`i--`
```graphviz
digraph res
{
rankdir = "LR"
node [shape="box"];
node1 [label= "1"]
node3 [label= "3"]
node4 [label= "4"]
node5 [label= "5"]
result [shape=plaintext];
result->node1
node4->node5
node3->node4
node1->node3
}
```
:::warning
**問題與改進方案**:
此程式每次都只挑選第一個節點作為`pivot` ,若剛好鏈結串列為遞增時,每次 `left`皆為 NULL , `right` 皆為為 `pivot` 以外的其他節點,這樣就會需要走訪每一個節點才會結束,時間複雜度為 $O(n^2)$
若要解決此問題,可以使用[median of three](https://stackoverflow.com/questions/7559608/median-of-three-values-strategy)或更進一步使用[median of median](https://en.wikipedia.org/wiki/Median_of_medians)來避免此問題。
**TODO**
:::
### 測驗二
`merge()` 會將 `a` , `b` 兩個已排序的鏈結串列合併成新的鏈結串列,一開始因為鏈結串列為空,要將 `**tail` 初始化為 `&head`。
接著利用迴圈比較 `a` , `b` 的第一個節點,將較小者加入新鏈結串列的尾部, 加入後要將 `tail` 指標向後移,下次加入節點時才能繼續加入鏈結串列尾端, 因此 `BBBB` 為 `&a->next`，`CCCC` 則為 `&b->next`。
**程式碼改進**
可將 for 迴圈替換成 while 迴圈,減少迴圈內 if 的判斷次數
```diff
- for (;;) {
+ while(a && b){
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB;
a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
} else {
*tail = b;
tail = CCCC;
b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
}
+ tail = &(*tail)->next;
}
+ *tail = (a) ? a : b;
```
`build_prev_link()` 會走訪每個節點,並且建立每個節點的 `prev` , 最後需要將頭尾相連。
```diff
- DDDD = head;
+ tail->next = head;
- EEEE = tail;
+ head->prev = tail;
```
在 `timsort()` 中，`stk_size` 表示 run 的個數,在合併的過程中 `stk_size` 會逐漸減少。因為是剩下最後一個 run 時才會需要用到 `build_prev_link()` 將鏈結串列的頭尾相接,所以可以推斷 `FFFF` 為 1。
:::warning
**問題與改進方案**:
此程式沒有採用題幹介紹的Galloping mode方法, 後續可以加入Galloping mode進行實做,並且比較兩者的差異
**TODO**
:::
---
## 第二週測驗
### 測驗一
```c
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`
```graphviz
digraph node_t
{
node [shape= "record"];
rankdir= "LR";
splines = false;
list_head [label= "<h>list_head | <f>first"]
node1 [label= "<self>node1 | {<p>pprev | <n>next}"]
node2 [label= "<self>node2 | {<p>pprev | <n>next}"]
NULL [shape= plaintext]
{rank = "min" list_head}
list_head -> node1 -> node2 [
weight = 10, style=invis
]
list_head:f->node1:self
node1:n->node2:self
node1:p->list_head:f
node2:n->NULL
node2:p->node1:n
}
```
```graphviz
digraph node_t
{
node [shape= "record"];
rankdir= "LR";
splines=false;
list_head [label= "<h>list_head | <f>first"]
node_n [label= "<self>node_n | {<p>pprev | <n>next}"]
node1 [label= "<self>node1 | {<p>pprev | <n>next}"]
node2 [label= "<self>node2 | {<p>pprev | <n>next}"]
NULL [shape= plaintext]
{rank = "min" list_head}
list_head -> node_n-> node1 -> node2 [
weight = 10, style=invis
]
list_head:f->node_n:self
node_n:n->node1:self [color=red]
node_n:p->list_head:f [color=orange]
node1:n->node2:self
node1:p->node_n:n [color=blue]
node2:n->NULL
node2:p->node1:n
}
```
```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, BBBB) {
struct order_node *on = CCCC(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
return -1;
}
```
此段程式是為了尋找 `num` 的位置,會先計算 hash 取得對應的 `hlist_head` ,接著逐一走訪該鏈結串列。由此可知 `BBBB` 為 `&head[hash]` , `CCCC` 為 `list_entry` 。
`dfs()`
本題的 input 為兩個 int 陣列 `preorder` 和 `inorder`。 在此函式中會使用 `*tn` 存取前序第一個節點的值,因為前序的第一個節點即為根節點, 並利用 `find()` 尋找此數值在中序的位置,左側為左子樹,右側為右子樹,再對左/右子樹繼續遞迴。
在下圖範例中, 會先查看 `preorder` 的第一個節點的值 3 ,在中序的位置 `idx` ,可知`idx = 1`。 `(idx - in_low)` 可以算出中序第一個節點和 `idx` 之間的間隔, 也就是左子樹的長度。而右子樹是從 `idx + 1` 到 `in_high` , 因此右子樹的長度為 `in_high - idx - 1` , 利用`pre_high - (in_high - idx - 1)` 即可獲得前序中左子樹的 head 位置。而中序內左子樹的範圍就是 `in_low` 到 `idx - 1` , 右子樹為 `idx + 1` 到 `in_high`。
```graphviz
digraph lists {
node [shape= "none"]
splines = false
preorder[shape = record, label = " <l0> 3 | <l1> 9 | <l2> 20 | <l3> 15 | <l4> 7 ",height=0.5, width=3];
inorder[shape = record, label = " <l0> 9 | <l1> 3 | <l2> 15 | <l3> 20 | <l4> 7 ",height=0.5, width=3];
pre[label = "preorder"];
inr[label = "inorder"];
idx [fontcolor="orange"]
p_left_h [label="pre_low + 1", fontcolor="red" ]
p_left_t [label="pre_low + (idx - in_low)", fontcolor="red" ]
p_right_h [label="pre_high - (in_high - idx - 1)", fontcolor="blue"]
p_right_t [label="pre_high", fontcolor="blue"]
i_left_h [label="in_low", fontcolor="red" ]
i_left_t [label="idx - 1", fontcolor="red" ]
i_right_h [label="idx + 1", fontcolor="blue"]
i_right_t [label="in_high", fontcolor="blue"]
pre -> preorder:l0;
inr -> inorder:l0;
idx -> inorder:l1;
preorder:l1 -> p_left_h [dir=back]
preorder:l1 -> p_left_t [dir=back]
p_right_h -> preorder:l2
p_right_t -> preorder:l4
inorder:l0 -> i_left_h [dir=back]
inorder:l0 -> i_left_t [dir=back]
i_right_h -> inorder:l2
i_right_t -> inorder:l4
}
```
```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, DDDD);
}
```
此函式目的是將新節點加入對應 hash 的串列中, 因此 `DDDD` 應為 `&head[hash]`
**在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討**
在 [/kernel/cgroup/cgroup.c](https://elixir.bootlin.com/linux/latest/source/kernel/cgroup/cgroup.c#L241) 中
```c
/* walk live descendants in pre order */
#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
```
### 測驗二
- `LRUCache` : `LRU` 緩存機制的主體結構。包含以下元素:
- `capacity`: cache 的最大容量
- `count` : cache 當前紀錄的資料筆數
- `dhead` : 儲存 LRU 快取中的節點，並按最近使用的順序排列。
- `hhead[]` : 一個型態為 `hlist_head` 的陣列, 儲存每個 hash 對應的串列 head 節點
- `LRUNode` : 是緩存中每個項目的結構，包含以下資料:
- `key` : 鍵值
- `value`: 數值
- `node` : 用於將此 cache 項目連接到 `hash` 的結構
- `link` : 用於將此 cache 項目連接到雙向鏈結的結構
```graphviz
digraph node_t
{
node [shape= "record"];
rankdir= "LR";
LRUCache [label= "{LRUCache | {capacity | count | <d>dhead | hhead[] }}"];
LRUNode [label= "{LRUNode | {key | value | node | link }}"];
}
```
```c
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next; //藍箭頭
if (next)
EEEE = pprev; //紅箭頭
}
```
此函式目的為刪除節點, 假設要刪除 `node2` ,要將 `*pprev` 也就是 `node1->next` 的值改為 `next (node3)`, 並且因為 `next` 存在,也要將 `next->pprev` 改為 `pprev (node1)`。
```graphviz
digraph node_t
{
node [shape= "record"];
rankdir= "LR";
splines = false
list_head [label= "<h>list_head | <f>first"]
node1 [label= "<self>node1 | {<p>pprev | <n>next}"]
node2 [label= "<self>node2 | {<p>pprev | <n>next}"]
node3 [label= "<self>node3 | {<p>pprev | <n>next}"]
NULL [shape= plaintext]
{rank = "min" list_head}
list_head -> node1 -> node3->NULL[
weight = 100, style=invis
]
list_head:f->node1:self
node1:n->node3:self [color=blue]
node1:p->list_head:f
node3:n->NULL
node3:p->node1:n [color=red]
}
```
```c
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);
}
```
此段程式碼目的為釋放 LRU 快取所占用的記憶體,
`pos` 的型態為 `list_head`, 由此可知其為 `LRUNode` 中的 `link`, `FFFF = link`。因為要將 `list` 刪除, 故 `GGGG` 應為 `&cache->link`。
```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, HHHH);
if (cache->key == key) {
list_move(IIII, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
此函式從快取中尋找給定 `key` 並獲取其對應的值 ，如果 `key` 存在於快取內則返回該值，並將該節點移動到鏈結串列的頭部 (表示最近使用)；如果不存在則返回 -1。
`pos` 的型態為 `hlist_node`, 因此可推論其為`LRUNode` 中的 `node` , 故 `HHHH` 為 `node`。而 `IIII` 是移動至另一串列的前端, 因此為 `&cache->list`。
```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, JJJJ);
if (c->key == key) {
list_move(KKKK, &obj->dhead);
cache = 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;
}
```
此函式將給定的鍵-值對(key–value pair)加入快取中,有以下三種情況
- 如果 key 已存在，則更新對應的值
- key 不存在會判斷容量是否已滿
- 若已滿則刪除鏈結串列尾部的節點(最久未使用)，然後將新的鍵-值對插入到鏈結串列的前端。
- 若未滿則配置新空間將節點加入串列前端以及加入 hash table 中，並將 count++ 。
因此不管 key 是新的還是已存在，對應的節點都會被移動到鏈結串列的前端。
`KKKK` 同樣為移動至另一串列的前端,故為 `&c->list` 。
:::warning
TODO
在 Linux 核心找出 LRU 相關程式碼並探討
:::
### 測驗三
`__ffs`
```c
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
if ((word & AAAA) == 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;
}
```
`__ffs()` 是用來查詢一個 `word` 中最低位 1 的所在位置, 若 (word & **0xffffffff**) == 0 即可知道較低的32位元內沒有任一位元為1, 因此將 `word` 右移 32 位元再進行檢查。
`__clear_bit`
```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 &= BBBB;
}
```
此段程式碼是透過 `BIT_MASK(nr)` 產生出只有第 `nr` 位為 1 ，其他位皆為 0 的遮罩，並利用此遮罩將該 `addr` 的第 `nr` 位清除。 故 `BBBB` 應為 `~mask` ，利用 ~ 運算將 mask 反轉成只有 `nr` 位為 0 ，即可達到清除該位元的效果。
`fns`
```c
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;
}
```
此段程式碼目的為找到第 n 個被設為 1 的位置，它會不斷地呼叫 `__ffs` 找到最低被設為 1 的位元，若還不是第 n 個就會使用 `__clear_bit` 將目前的位元清除，再繼續找下一個被設為 1 的位元。
`FIND_NTH_BIT`
```c
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);
}
```
運作原理:
先利用 `small_const_nbits` 比較要找的位數是否超過限制的 `size` ， 並利用 `GENMASK(h, l)` 將 h 到 l 間的位元變為 1和 `addr` 做 & 運算 ，若 `val` 有值代表 `addr` h 到 l 間有位元被設為1，因此再利用 `fns` 找到為 第 n 個被設為 1 的位元並回傳其位置。若不符合 `small_const_nbits` 就利用 `FIND_NTH_BIT` 來處理。
`FIND_NTH_BIT`
```c
#define FIND_NTH_BIT(FETCH, size, num) \
({ \
unsigned long sz = (size), nr = (num), idx, w, tmp; \
\
for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
if (idx * BITS_PER_LONG + nr >= sz) \
goto out; \
\
tmp = (FETCH); \
w = hweight_long(tmp); \
if (w > nr) \
goto found; \
\
nr -= w; \
} \
\
if (sz CCCC BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
found: \
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
out: \
sz; \
})
```
`FIND_NTH_BIT` 能夠搜尋超出單個 `BITS_PER_LONG` 長度的範圍。如果要查找的位元不在目前處理的字節中，能透過迴圈繼續在下一個 `BITS_PER_LONG` 長度的區塊中搜尋，直到找到該位為止。
因為 `size` 可能無法被 `BITS_PER_LONG` 整除，因此搜尋到最後一輪時應避免找到超出 `size` 範圍的字元，因此使用取餘數的方式找到最後一個字節所需要搜尋的字元數量，故 `CCCC` 應為 `%`。
Sign in with Wallet
Connect another wallet