# 2024q1 Homework2 (quiz1+2)
contributed by <[yulin0625](https://github.com/yulin0625)>
## 第一週測驗題
[2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-1)
### 測驗 1
#### 補完程式碼、程式碼解析
`list_tail`
```diff
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
- left = &(BBBB);
+ left = &(left->next);
return *left;
}
```
解釋: 這個函式的功能是找到鏈結串列的最後一個節點，並回傳該鏈結串列的最後一個節點的指標。
圖示說明:
**Initial:**
```graphviz
digraph {
node [shape=box]
rankdir = LR;
left[shape=plaintext,fontcolor=red];
N1[label=A]
Addr1[label="&A", shape=plaintext];
left_next[label="(*left)->next",shape=plaintext,fontcolor=blue];
N2[label=B];
Addr2[label="&B", shape=plaintext];
N3[label=C];
Addr3[label="&C", shape=plaintext];
NULL1[label="NULL", shape=plaintext];
{rank=same; left->Addr1->N1}
{rank=same; left_next->Addr2->N2}
{rank=same; Addr3->N3}
N1->N2->N3->NULL1;
}
```
**Step1:**
```graphviz
digraph {
node [shape=box]
rankdir = LR;
left[shape=plaintext,fontcolor=red];
N1[label=A]
Addr1[label="&A", shape=plaintext];
N2[label=B];
Addr2[label="&B", shape=plaintext];
left_next[label="(*left)->next",shape=plaintext,fontcolor=blue];
N3[label=C];
Addr3[label="&C", shape=plaintext];
NULL1[label="NULL", shape=plaintext];
{rank=same; Addr1->N1}
{rank=same; left->Addr2->N2}
{rank=same; left_next->Addr3->N3}
N1->N2->N3->NULL1;
}
```
**Step2:**
```graphviz
digraph {
node [shape=box]
rankdir = LR;
left[shape=plaintext,fontcolor=red];
N1[label=A]
Addr1[label="&A", shape=plaintext];
N2[label=B];
Addr2[label="&B", shape=plaintext];
N3[label=C];
Addr3[label="&C", shape=plaintext];
NULL1[label="NULL", shape=plaintext];
{rank=same; Addr1->N1}
{rank=same; Addr2->N2}
{rank=same; left->Addr3->N3}
N1->N2->N3->NULL1;
}
```
`list_length`
```diff
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
- left = &(BBBB);
+ left = &((*left)->next);
}
return n;
}
```
解釋: 原理與 `list_tail` 相同，當 `left` 每間接指到一個節點，計數器 `n` 就會增加一，函釋回傳值為該鏈結串列的長度。
`quick_sort`
```diff
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;
+ p = p->next;
list_add(n->value > value ? &right : &left, n);
begin[i] = left;
- end[i] = DDDD;
+ end[i] = &list_tail(left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
- end[i + 2] = EEEE;
+ end[i + 2] = &list_tail(right);
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
解釋: 此函式是運用 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 所實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼。
排序過程:
1. 迴圈 while (i >= 0) 用於走訪和排序鏈結串列的不同部分
2. 在迴圈內，選擇串列的第一個節點作為 pivot
3. 走訪 pivot 後的所有節點，並與 pivot 比較值的大小，若較小則將該節點加入 left 串列，否則加入 right 串列
4. 更新 begin 和 end 堆疊
5. 若達到一個只有一個節點的子列表，則將該節點添加到 result 串列中
圖示說明:
- 選擇第一個節點(節點4)作為 pivot
```graphviz
digraph {
node [shape=box]
rankdir = LR;
pivot[shape=plaintext,fontcolor=red];
N1[label=4];
N2[label=1];
N3[label=3];
N4[label=5];
N5[label=2];
N6[label=7];
NULL1[label="NULL", shape=plaintext];
{rank=same; pivot->N1}
N1->N2->N3->N4->N5->N6->NULL1;
}
```
- 走訪pivot 後的所有節點，根據它們的值相對於 pivot 的大小，將它們分到 left 或 right 子串列
此時的 left, pivot, right:
```graphviz
digraph {
rankdir = LR;
node[shape=plaintext];
left[fontcolor=blue];
pivot[fontcolor=red];
right[fontcolor=blue];
node [shape=box]
L1[label="2"];
L2[label="3"];
L3[label="1"];
P1[label="4"];
R1[label="7"];
R2[label="5"];
left->L1->L2->L3
pivot->P1
right->R1->R2
}
```
- 更新 begin、end 堆疊，並將 `i = i + 2`
- 將begin[i] 設為 left
- 將begin[i + 1] 設為 pivot
- 將begin[i + 2] 設為 right
```graphviz
digraph {
rankdir = TB;
node[shape=plaintext];
begin0[label="begin[0]"];
begin1[label="begin[1]"];
begin2[label="begin[2]"];
end0[label="end[0]"];
end1[label="end[1]"];
end2[label="end[2]"];
left[fontcolor=blue];
pivot[fontcolor=red];
right[fontcolor=blue];
node [shape=box];
L1[label="2"];
L2[label="3"];
L3[label="1"];
P1[label="4"];
R1[label="7"];
R2[label="5"];
begin0->L1
{rank=same;left->L1->L2->L3}
end0->L3
begin1->P1
{rank=same;pivot->P1}
end1->P1
begin2->R1
{rank=same;right->R1->R2}
end2->R2
}
```
- 此時 i=2，演算法會對 begin[2] 堆疊所存的 right 串列進行走訪，並選擇節點7，作為 pivot
```graphviz
digraph {
rankdir = LR;
node[shape=plaintext]
pivot[fontcolor=red];
node [shape=box]
N1[label=7];
N2[label=5];
pivot->N1
N1->N2;
}
```
- 此時的 begin、end 堆疊
```graphviz
digraph {
rankdir = TB;
node[shape=plaintext];
begin0[label="begin[0]"];
begin1[label="begin[1]"];
begin2[label="begin[2]"];
end0[label="end[0]"];
end1[label="end[1]"];
end2[label="end[2]"];
left[fontcolor=blue];
pivot[fontcolor=red];
right[fontcolor=blue];
node [shape=box];
L1[label="5"];
P1[label="7"];
R1[label="NULL"];
begin0->L1
{rank=same;left->L1}
end0->L1
begin1->P1
{rank=same;pivot->P1}
end1->P1
begin2->R1
{rank=same;right->R1}
end2->R1
}
```
- 當 begin 與 end 相等(left == right 時)，將節點加入 result 串列，並將 `i--`
```graphviz
digraph {
rankdir = LR;
node[shape=plaintext]
result;
NULL;
node [shape=box]
N1[label=5];
N2[label=7];
result->N1->N2->NULL;
}
```
- 重複直到所有節點排序完成
**可改進之處:**
目前演算法每次都取第一個節點為 pivot ，若遇到已完成排序的鏈結串列時，就會成為 worst case，時間複雜度為O(n²)
解決方法:
1. Middle-of-Three: 令 middle = (left + right) /2，比較 left、middle 與 right 這三筆資料，排出中間值，再將中間值與 left 做交換
2. Random Pivot Selection: 用亂數選取的方式，隨機挑一個值作為 pivot，降低發生 Worst Case 的機率
3. [Median-of-Medians](https://www.wikiwand.com/en/Median_of_medians)
### 測驗 2
```diff
static struct list_head *merge(void *priv,
list_cmp_func_t cmp,
struct list_head *a,
struct list_head *b)
{
struct list_head *head;
- struct list_head **tail = AAAA;
+ struct list_head **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
- tail = BBBB;
+ tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
- tail = CCCC;
+ tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
```diff
static void build_prev_link(struct list_head *head,
struct list_head *tail,
struct list_head *list)
{
tail->next = list;
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
/* The final links to make a circular doubly-linked list */
- DDDD = head;
+ tail->next = head;
- EEEE = tail;
+ head->prev = tail;
}
```
```diff
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;
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);
/* End of input; merge together all the runs. */
tp = merge_force_collapse(priv, cmp, tp);
/* 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 <= FFFF) {
+ if (stk_size <= 1) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
}
```
運作原理:
## 第二週測驗題
[2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 1
`hlist_add_head`: 此函式的功能為將新的節點加入串列的前端。新節點的 next 應指向原本的第一個節點，所以 `AAAA` 為 `h->first`
```diff
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
if (h->first)
h->first->pprev = &n->next; // 1
- n->next = AAAA;
+ n->next = h->first; // 2
n->pprev = &h->first; // 3
h->first = n; // 4
}
```
```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 [label=4]
node_n:n->node1:self [label=2]
node_n:p->list_head:f [label=3]
node1:n->node2:self
node1:p->node_n:n [label=1]
node2:n->NULL
node2:p->node1:n
}
```
`find`
```diff
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) {
+ hlist_for_each (p, &head[hash]) {
- struct order_node *on = CCCC(p, struct order_node, node);
+ 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`
概念: 由前序可知哪個節點在上面 (越前面的越上面)、由中序可知哪個節點靠左(越前面的越左邊)，於是可得知前序的第一個元素一定是 root 的值，且該元素對應到中序後，左邊的值就在左邊，右邊的值就在右邊。
解釋: 此函式會先取前序的第一個節點，並利用 `find` 尋找該節點的值出現在中序的哪個位置，並將左側的節點當成左子樹的 root 、 左側的節點當成右子樹的 root，繼續遞迴再尋找，直到 inorder 中找不到對應元素。
圖示說明:
- 若前序為: [3, 9, 20, 15, 7]，中序為: [9, 3, 15, 20, 7]
- 先查看前序的第一個節點的值 3 ,在中序的位置 `idx`，此時 `idx = 1`
- 左子樹的長度為中序第一個節點和 `idx` 之間的間隔，也就是 `(idx - in_low)` ，因此左子樹的範圍為 `pre_low + 1` 至 `pre_low + (idx - in_low)`
- 而右子樹的長度為 `idx` 到中序最後一個節點的間隔，也就是 `in_high - (idx + 1)`，因此右子樹在前序的範圍為 `pre_high - (in_high - idx - 1)` 至 `pre_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", fontsize="20"];
inr[label = "inorder", fontsize="20"];
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
}
```
### 測驗 2
LRU(Least Recently Used Cache) 是一種快取的實做方式，概念是儲存最近用過的內容，如果越常被使用，內容會被擺在 List 越前方的位置。如果快取滿了，則會從 List 最末端元素開始移除。
- `LRUCache` : `LRU` 緩存機制的主體結構。包含以下元素:
- `capacity`: cache 的最大容量
- `count` : cache 當前紀錄的資料筆數
- `dhead` : 儲存 LRU 快取中的節點，並按最近使用的順序排列。
- `hhead[]` : 儲存每個 hash 對應串列的 head 節點
- `LRUNode` : 是緩存中每個項目的結構，包含以下元素:
- `key` : 鍵值
- `value`: 數值
- `node` : 用於將此 cache 項目連接到 `hash` 的結構
- `link` : 用於將此 cache 項目連接到雙向鏈結串列的結構
`lRUCacheGet`: 讀取快取
```diff
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);
+ LRUNode *cache = list_entry(pos, LRUNode, node);
if (cache->key == key) {
- list_move(IIII, &obj->dhead);
+ list_move(&cache->list, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
先將 `key` 丟入 hash function 進行計算得到對應的 hash 值。接著從快取中尋找 `key` 。如果 `key` 存在於快取內則返回該值，並將該節點移動到鏈結串列的頭部 (表示最近使用)；如果不存在則返回 -1。
`lRUCachePut`: 寫入快取
```diff
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);
+ LRUNode *c = list_entry(pos, LRUNode, node);
if (c->key == key) {
- list_move(KKKK, &obj->dhead);
+ list_move(&c->link, &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++`
### 測驗 3
目的: 找出 word 參數中最低位的1所在的位置（從0開始計算）
`__ffs`
```diff
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
- if ((word & AAAA) == 0) {
+ 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;
}
```
`__ffs()` 是用來查詢一個 `word` 中最低位 1 的所在位置, 若 (word & **0xffffffff**) == 0 即可知道較低的32位元內沒有任一位元為1, 因此將 `word` 右移 32 位元再進行檢查。
`__clear_bit`
```diff
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;
+ *p &= ~mask;
}
```
此段程式碼是透過 `BIT_MASK(nr)` 產生出只有第 `nr` 位為 1 ，其他位皆為 0 的遮罩，並利用 ~ 運算將 mask 反轉成只有 `nr` 位為 0，最後利用反轉後的遮罩與 `addr` 做 bitwise and，將該 `addr` 的第 `nr` 位清除。
`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