# 2024q1 Homework2 (quiz1+2)
contributed by < [ChenFuhuangKye](https://github.com/kyehuang) >
## 2024q1 第 1 週測驗題
### 測驗 `1`
> commit [60f92f8](https://github.com/kyehuang/linux_api/commit/60f92f8b0ae4577b87417bd2bfc2ec3438b23de8)
>
首先考慮 node_t 的結構，他利用 `next` 連接下一個 node， `left` 連接左邊的 node 以及 `right` 連接右邊的 node。
```graphviz
digraph structs {
node[shape=record];
struct0 [label="{<left>left|<right>right}|<next>next|<data>value",color=purple]
rankdir=LR;
node[shape=box];
}
```
在 `list_tail` 函數功能是要走到 list 的尾端，如下兩圖
```c
node_t *list_tail(node_t **left)
```
```graphviz
digraph structs {
node[shape=record];
struct0 [label="{<left>left|<right>right}|<next>next|<data>value",color=purple]
struct1 [label="{<left>left|<right>right}|<next>next|<data>value",color=purple]
struct2 [label="{<left>left|<right>right}|<next>next|<data>value",color=purple]
struct3 [label= "pointer"];
rankdir=LR;
node[shape=box];
struct3->struct0:n
struct0:next -> struct1:n [color=red];
struct1:next -> struct2:n [color=red];
}
```
```graphviz
digraph structs {
node[shape=record];
struct3 [label= "pointer"];
struct0 [label="{<left>left|<right>right}|<next>next|<data>value",color=purple]
struct1 [label="{<left>left|<right>right}|<next>next|<data>value",color=purple]
struct2 [label="{<left>left|<right>right}|<next>next|<data>value",color=purple]
rankdir=LR;
node[shape=box];
struct3->struct1:n
struct0:next -> struct1:n [color=red];
struct1:next -> struct2:n [color=red];
}
```
因此需要利用 next 找下一個 node 位置直到尾端。
```diff
while ((*left) && (*left)->next)
- left = &(AAAA);
+ left = &((*left)->next);
```
`list_length` 是要計算出 list 的長度，如同 list_tail 一樣，計算走到尾端的次數即可。
```diff
while (*left) {
++n;
- left = &(BBBB);
+ left = &((*left)->next);
}
```
在 quick_sort 中，會先找到 pivot ，並且將 p 指向 pivot 的 next 再將其的 next 改成 null 。
```graphviz
digraph structs {
node[shape=record];
node[shape=box];
struct0 [label= "pivot"];
struct1 [label= "p"];
struct2 [label= "node1"];
struct3 [label= "node2"];
struct4 [label= "node3"];
struct5 [label= "node4"];
{ rank=same; struct2 -> struct3 }
{ rank=same; struct3 -> struct4 }
{ rank=same; struct4 -> struct5 }
struct0 -> struct2 [color=red];
}
```
```graphviz
digraph structs {
node[shape=record];
node[shape=box];
struct0 [label= "pivot"];
struct1 [label= "p"];
struct2 [label= "node1"];
struct3 [label= "node2"];
struct4 [label= "node3"];
struct5 [label= "node4"];
{ rank=same; struct3 -> struct4 }
{ rank=same; struct4 -> struct5 }
struct0 -> struct2 [color=red];
struct1 -> struct3 [color=red];
}
```
而 p 要跟前面的 list_tail 走過全部的 node 直到尾端，因此要改成這樣，讓 p 走到每一個 node直到尾部。
```diff
while (p) {
node_t *n = p;
- p = CCCC;
+ p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
找到 node 時會利用 list_add 將其分到 left 或是 right，假設 node2 的 value 比 node1 小，因此 node2 會分到 left。
```graphviz
digraph structs {
node[shape=record];
node[shape=box];
struct0 [label= "pivot"];
struct1 [label= "p"];
struct2 [label= "node1"];
struct3 [label= "node2"];
struct4 [label= "node3"];
struct5 [label= "node4"];
left [label= "left"];
right [label= "right"];
{ rank=same; struct3 -> struct4 }
{ rank=same; struct4 -> struct5 }
struct0 -> struct2 [color=red];
struct1 -> struct3 [color=red];
}
```
```graphviz
digraph structs {
node[shape=record];
node[shape=box];
struct0 [label= "pivot"];
struct1 [label= "p"];
struct2 [label= "node1"];
struct3 [label= "node2"];
struct4 [label= "node3"];
struct5 [label= "node4"];
left [label= "left"];
right [label= "right"];
{ rank=same; struct4 -> struct5 }
struct0 -> struct2 [color=red];
struct1 -> struct4 [color=red];
left -> struct3 [color=red]
}
```
當 p 走完全部的 node 時，會把除了 pivot 指向的 node，分配到 left 及 right，如下圖。
```graphviz
digraph structs {
node[shape=record];
node[shape=box];
struct0 [label= "pivot"];
struct1 [label= "p"];
struct2 [label= "node1"];
struct3 [label= "node2"];
struct4 [label= "node3"];
struct5 [label= "node4"];
left [label= "left"];
right [label= "right"];
struct0 -> struct2 [color=red];
right -> struct4 [color=red];
left -> struct3 [color=red];
{ rank=same; struct3 -> struct5 }
}
```
接著再存入 begin 及 end 陣列中，在陣列中如果其 index 相同代表其為同一個鏈結， begin 為鏈結頭部而 end 為鏈結尾端。如下兩圖。
> 圖一 切分前。
```graphviz
digraph structs {
node[shape=record];
end [label="{end |<0>0}", color=purple];
begin [label="{begin |<0>0}", color=purple];
node[shape=box];
struct0 [label= "pivot"];
// struct1 [label= "p"];
struct2 [label= "node1"];
struct3 [label= "node2"];
struct4 [label= "node3"];
struct5 [label= "node4"];
{ rank=same; struct2 -> struct3 }
{ rank=same; struct3 -> struct4 }
{ rank=same; struct4 -> struct5 }
struct0 -> struct2 [color=red];
// struct1 -> struct3 [color=red];
end:0 -> struct2
begin:0 -> struct5
}
```
> 圖二 切分後
```graphviz
digraph structs {
node[shape=record];
end [label="{end |<0>i|<1>i+1|<2>i+2}", color=purple];
begin [label="{begin |<0>i|<1>i+1|<2>i+2}", color=purple];
node[shape=box];
struct3 [label= "node2"];
struct5 [label= "node4"];
struct4 [label= "node3"];
struct2 [label= "node1"];
{ rank=same; struct3 -> struct5 }
end:0 -> struct3
begin:0 -> struct5
end:1 -> struct2
begin:1 -> struct2
end:2 -> struct4
begin:2 -> struct4
}
```
左邊鏈結的開頭會存在 begin 中的第 i 個位置， 中間鏈結的開頭會在 begin 中的第 i+1 個位置， 右邊鏈結的開頭會在 begin 中的第 i+2 個位置
所以 end 要存的是每條鏈結的尾端，可以利用 list_tail 找到尾端。
```diff
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);
```
### 測驗 `2`
> commit [6ea4c9e](https://github.com/ChenFuhuangKye/linux_api/commit/6ea4c9e6fd64ae6ba09be7936d6371215c3a2b2d)
在 `merge` 中， tail 會隨著 node 插入指向下一個位置。
因此 tail 的初始質會是 head 的位置， tail 是間接指標，所以要用 & 來取址。
```diff
struct list_head *head;
- struct list_head **tail = AAAA;
+ struct list_head **tail = &head;
```
在比較過後，需要將插入的節點存入 tail 中，接著 tail 需要移動到下一個位置，以存入下一個節點。
```diff
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;
}
}
}
```
`build_prev_link` 是要建立一個環狀的鏈結。
```c
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
```
這段先將 list 皆在 tail 後面，直到結束。
最後需要將頭尾接在一起。
```diff
- DDDD = head;
+ tail->next = head;
- EEEE = tail;
+ head->prev = tail;
```
在 `timsort` 中，在進行最後合併之前，如果推疊的大小為 0 或是 1 需要呼叫 `build_prev_link` 建立一個環狀的鏈結。
```diff
-if (stk_size <= FFFF) {
+if (stk_size <= 1) {
build_prev_link(head, head, stk0);
return;
}
```
## 2024q1 第 2 週測驗題
### 測驗 `1`
`hlist_add_head` 是將新的節點插在在 head 後面。
因此新的節點後面要接 head 原本的節點。
```diff
-n->next = AAAA;
+n->next = h->first;
```
在 `find` 中，找到想要查詢的哈希值，在利用 `hlist_for_each` 遍歷，`hlist_for_each` 接的 head 要是指標，所以要加上取址 `&`。
下一行要找到 on 指向的位置，可以利用 `list_entry` 找到。
```diff
-hlist_for_each (p, BBBB) {
- struct order_node *on = CCCC(p, struct order_node, node);
+hlist_for_each (p, &heads[hash]) {
+ struct order_node *on = list_entry(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
```
在 `node_add` 中呼叫 `hlist_add_head` 將節點插在指定哈希值 head 的後面。
```diff
int hash = (val < 0 ? -val : val) % size;
- hlist_add_head(&on->node, DDDD);
+ hlist_add_head(&on->node, &heads[hash]);
```
### 測驗 `2`
`hlist_del` 是刪除指定節點，這邊要注意的是 pprev ，是指向上一個節點的 next 位置。因此 `*pprev = next;`這行已經指定節點前一個節點指向下一個節點，但沒有考慮到下一個節點指回前一個節點，因此當有下一個節點時，需要接回去。
```diff
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
- EEEE = pprev;
+ next->pprev = pprev;
```
在 `lRUCacheFree` 中，想要找到 LRUNode 節點。
首先考慮 LRUNode 的資料結構。
```c
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
由於 pos 的資料結構是 list_head ，所以其 member 為 link。
找到節點之後，想要將該節點刪除，先利用 `list_del` 從鏈結剔除，再把空間釋放。由於 LRUNode 中的 link 不是指標，因此要加上取址符號。
```diff
list_for_each_safe (pos, n, &obj->dhead) {
- LRUNode *cache = list_entry(pos, LRUNode, FFFF);
- list_del(GGGG);
+ LRUNode *cache = list_entry(pos, LRUNode, link);
+ list_del(&cache->link);
free(cache);
}
```
在 `lRUCacheGet`中，也想要找 LRUNode 節點。
但是這邊的 pos 的資料結構是 hlist_node ，所以其 member 為 node。找到適合的節點後，要移動到 head 後面，由於 LRUNode 中的 link 不是指標，因此要加上取址符號。
```diff
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->link, &obj->dhead);
return cache->value;
}
}
```
最後在 `lRUCachePut` 也想要找到節點並移動適合的節點到 head 後方，如同 `lRUCacheGet` 作法一樣。
```diff
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;
}
}
```
### 測驗 `3`
`__ffs` 是利用二元搜尋法，尋找 word 中第一個為 1 的位。
如果 word 前 32 位有 1，但是後 32 接為 0 ，才需要將 word 往右移動 32 位。 因此 word 需要跟 32 個 1 做 and 運算。
```diff
-if ((word & AAAA) == 0) {
+if ((word & 0xffffffff) == 0) {
num += 32;
word >>= 32;
}
```
`__clear_bit` 是將 word 中指定的位元設成 0 。
先產生一個 mask 並且其指定的位元設成 1 ，由於要將目標值的址定位元設為 0 ，因此取 ~mask 與目標值做 and 運算。
```diff
- *p &= BBBB;
+ *p &= ~mask;
```
在 `FIND_NTH_BIT` 中，為了避免使用的有效位元之外的數字
```diff
-if (sz CCCC BITS_PER_LONG)
+if (sz % BITS_PER_LONG)
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);
```
Sign in with Wallet
Connect another wallet