# 2024q1 Homework2 (quiz1+2)
contributed by < [Petakuo](https://github.com/Petakuo) >
## 第一週測驗題
## [測驗1](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-1)
### 運作原理
定義變數 L 和 R 去紀錄整個鏈結串列完成一次排序需要交換的數量， L 和 R 分別會從左和右掃描，將小於和大於 pivot 的數量紀錄，並以 swap 對 pivot 、 L 及 R 進行順序交換，最後利用 `stack` 來模擬遞迴，而遞迴主要是在做合併的效果。
### 題目解析
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
此段程式碼是在找尋整個 list 的最尾端， `while` 是用來檢查 `left` 指向的節點以及該節點的 `next` 是否為空，若不為空，則 `left` 會逐一往後，直到空為止，因此 `AAAA` 的答案為 `(*left)->next` 。
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
此段程式碼是利用整數變數 `n` 來計算 list 的長度，在 `while` 中，若 `left` 可以繼續往下，則 `n` 會 +1 ，因此 `BBBB` 為 `(*left)->next` 。
```c
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
已知 `node_t *p = pivot->next` ，因此可以判斷出在此段程式碼中， `p` 應更新為 `p` 的下一個節點以進行疊代，所以 `CCCC` 為 `p->next` ，而下方 `list_add` 為一條件運算，若下一節點的值大於原本的 pivot 值，則 `n` 加入 `&right` 中，否則加入 `&left` 。
```c
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
```
在此段程式碼中，1、2行分別用來紀錄 `&left` 的第一和最後一個節點，3、4行紀錄 pivot 的位置，5、6行則紀錄了 `&right` 的第一和最後一個節點，因此 `DDDD` 為 `list_tail(&left)` ， `EEEE` 為 `list_tail(&right)` 。
## [測驗2](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)
### 運作原理
* `find_run` : 尋找出遞增的子串列，用此方法可以減少 merge 的次數。
* `merge_collapse` : 用來確保在 stack 的前3個 run 的長度是平衡的，主要的檢查有其二
* A 的長度要大於 B 和 C 的長度總和。
* B 的長度要大於 C 的長度。
* `merge_force_collapse` : 當 stack size >= 3 時，將子串列合併。
* `build_prev_link` : 此函式的功能為建立雙向的環狀鏈結串列，因此將每個節點的 `prev` 指向前一個節點，最後再將 head 和 tail 連接起來。
* `merge_final` : 此函式會比較 a 和 b 兩串列中的元素，並將較小的接在 tail 之後，為了確保此演算法為 stable ，在相等時會取 a ，最後再使用 `build_prev_link` : 將 b 所剩餘的元素接在 tail 之後。
### 題目解析
```c
struct list_head *head;
struct list_head **tail = AAAA;
```
因為 tail 為指標的指標，需指向合併後串列的 head 的指標，因此 `AAAA` 為 `&head` 。
```c
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB;
a = a->next;
if (!a) {
*tail = b;
break;
}
}
```
此段程式碼在比較子串列 `a` 和 `b` 的首個元素，如果 `a` 的較小，則 `*tail` 將更新為 `a` ，並且 tail 也會更新為下一個節點，因此 `BBBB` 為 `&a->next` ，而下一題的 `CCCC` 也為同樣道理，為 `&b->next` 。
```c
/* The final links to make a circular doubly-linked list */
DDDD = head;
EEEE = tail;
```
由於 `build_prev_link` 的功能是在建立雙向的環狀鏈結串列，在此程式碼的最後，需將 head 和 tail 連接起來，因此 `DDDD` 為 `tail->next` ， `EEEE` 為 `head->prev` 。
## 第二週測驗題
## [測驗1](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-1)
### 運作原理
* `hlist_add_head` : 將節點加入串列的頭部。
* `find` : 用來尋找 num 的位置，會先以制定的 hash function 來縮小範圍，直接決定出要進行搜索的串列，如此做法可將搜尋的時間複雜度由 O(n) 縮短為 O(1) 。
* `dfs` : 構建二元樹的主要函式，其 input 有
* `*preorder` : preorder 串列中的第一個位置。
* `pre_low` : 在遞迴中 preorder 的最低位置。
* `pre_high` : 在遞迴中 preorder 的最高位置。
* `*inorder` : inorder 串列中的第一個位置。
* `in_low` : 在遞迴中 inorder 的最低位置。
* `in_high` : 在遞迴中 inorder 的最高位置。
* `*in_heads` : 指向 Hash Table 的指標。
* `size` : Hash Table 的大小。
在此函式中，會先進行條件判斷，也就是 `pre_low` 不能大於 `pre_high` 且 `in_low` 不能大於 `in_high` 才會繼續進行。接著，利用 preorder list 的第一個節點為 root 的特性，在 inorder list 中找出該節點並分為左子樹及右子樹，再不斷地遞迴建構出二元樹。
* `node_add` : 與 `hlist_add_head` 相似，但此函式會先透過 hash function 的操作計算出欲操作的串列，再將節點加入該串列的頭部。
### 題目解析
```c
if (h->first)
h->first->pprev = &n->next;
n->next = AAAA;
n->pprev = &h->first;
h->first = n;
```
為了將 n 加入串列的頭部， `n->next` 應指向原始串列的頭部，因此 `AAAA` 為 `h->first` 。
```c
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;
```
此函式中 hash function 的設計為先將 `num` 取絕對值，再去 mod Hash Table 的大小，接著利用 `hlist_for_each` 走訪由 `hash` 得出的串列，因此 `BBBB` 為 `&head[hash]` ，而走訪該串列用的是 `CCCC` 函式，因此 `CCCC` 為 `list_entry` 。
```c
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 function 找出欲操作的串列，接著再將節點 `on` 加入該串列的頭部，因此`DDDD` 為 `&head[hash]` 。
## [測驗2](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-2)
### 運作原理
在 LRU Cache 的實作中，利用雜湊的技巧來降低讀取以及寫入的時間，並且透過 `hlist` 保存鍵值被使用的先後順序， LRU Cache 裡擁有 4 種資料 :
* `capacity` : Cache 最多能儲存的資料數量。
* `count` : Cache 目前所儲存的資料數量。
* `dhead` : 雙向鏈結串列，將所有資料連接。
* `hhead` : 為 `hlist` 之陣列，大小為 `capacity` 。
而較主要的實作函式為 :
* `lRUCacheGet` : 首先透過 hash function 取得欲尋找的值，令為 `hash` ，接著利用 `hlist_for_each` 在 `hhead[hash]` 所指向的串列進行搜索，目標是找到與傳入的 `key` 相同的 `cache->key` ，若有則回傳該值，沒有則會傳 -1 。
* `lRUCachePut` : 與`lRUCacheGet` 的概念類似，在寫入時若 `hhead[hash]` 已存在該 `key` 則更新 `value` ，若沒有則需檢查是否已達到 cache 的 `capacity` ，若已達到則需刪除近期最少被使用的點，若尚未被填滿則直接新增節點即可。
### 題目解析
```c
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
EEEE = pprev;
```
此程式碼的目的是在於利用指標刪除節點 `n` ，首先，將 `n` 的前一個節點的 next 指向 `n` 的下一個節點，且當 `n` 的下一個節點存在時，將下一個節點的 pprev 指標指向前一個節點的 next 指標，因此 `EEEE` 為 `next->pprev` 。
```c
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, FFFF);
list_del(GGGG);
free(cache);
}
free(obj);
```
此程式碼想要刪除 cache 中的所有節點，首先利用 `list_for_each_safe` 來走訪 `&obj->dhead` ，並透過 `list_del` 進行刪除的動作，由於 `pos` 在 `LRUNode` 的結構為 `link` ，因此 `FFFF` 為 `link` 且 `GGGG` 為 `&cache->link` 。
```c
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;
}
}
```
在這裡，由於是要將 `hhead[hash]` 的值取出，因此 `pos` 在 `LRUNode` 的結構為 `node` ，因此 `HHHH` 為 `node` ，而當條件成立時，會將串列取出並移至 `&obj->dhead` ，因此 `GGGG` 為 `&cache->link` 。
```c
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;
}
}
```
此程式碼與上一個概念相同，只是將取出改為寫入，因此 `JJJJ` 同為 `node` ，而 `KKKK` 為 `c->link` 。
## [測驗3](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)
### 運作原理
* `__ffs` : 利用類似於二分搜尋的方法來找出該 word 中第一個 1 ，首先將該 word 右半邊和全 1 做 `&` 運算，並額外新增一整數變數 `num` 來記錄以搜尋過的位元數，若運算結果等於 0 ，則表示右半邊無任何 1 存在， `num` 更新為右半邊長度的值，之後繼續做一樣的操作直到剩餘 1 個位元，再返回 `num` 即可。
* `__clear_bit` : 清除指定的位元，使用 `BIT_MASK` 巨集建立一 mask ，使要清除的位置為 1 ，其餘為 0 ，接著將該 mask 的位元進行反轉，再與原 word 做 `&` 運算即可將該位元清除。
* `fns` : 目的在找到從右邊數來第 `n` 個 1 的位置，概念為利用 `__ffs` 找到第一個 1 ，同時將 `n` - 1 ，並且當 `n` 不等於 0 時，利用 `__clear_bit` 將找到的位元刪除，如此重複做到 `n` = 0 時，即代表該次由 `__ffs` 找到的位元為原本 word 中右邊數來第 `n` 個 1 。
* `find_nth_bit` : 在一個記憶體區域中找到第 `n` 個 1 的位置，首先，利用 `GENMASK` 建立一 mask ，然後將記憶體地址與之做 `&` 運算，再利用 `fns` 找出最後的答案。
* `GENMASK(h, l)` : ` ((~0UL) - (1UL << (l)) + 1) ` 利用位元全為 1 的 word 減去最右邊位元為 1 並且左移 `l` 個位元的 word 所得到的答案為第 `l+1` 個位元為 0 ，其他為 1 的 word ，再將其 +1 可得右半邊 `l` 個位元為 0 ，其餘為 1 的 word ; `(~0UL >> (BITS_PER_LONG - 1 - (h)))` 將位元全為 1 的 word 往右移動 `BITS_PER_LONG - (1+h)` 個位元可得右半邊 `1+h` 個位元為 1 ，其餘為 0 的 word ，而將此兩 word 做 `&` 運算的結果為在兩者間的交集為 1 ，其餘為 0 的 word 。
### 題目解析
```c
if ((word & AAAA) == 0) {
num += 32;
word >>= 32;
}
```
此程式碼每次會用全 1 的 word 和輸入的 word 右半邊的位元做 `&` 運算，又因為此次為第一次運算，因此 `AAAA` 應存在 32 個位元，為 `0xffffffff` 。
```c
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
*p &= BBBB;
```
此程式碼的目的在於清除指定的位元，在透過 `BIT_MASK` 將該位元設定成 1 其餘為 0 後，則需對此 mask 做反轉並且和原 word 做 `&` 運算，因此 `BBBB` 為 `~mask` 。
```c
if (sz CCCC BITS_PER_LONG)
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);
```
此段條件是在確保記憶體的 `size` 並未超出定義的 `BITS_PER_LONG` 大小，因此 `CCCC` 為 `%` 。
Sign in with Wallet
Connect another wallet