# 2024q1 Homework2 (quiz1+2)
contributed by < `wu81177` >
# [第一周測驗題](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97)
## 測驗一
參考 Optimized QuickSort — C Implementation (Non-Recursive)，實作非遞迴 (non-recursive; iterative) 的快速排序法。此處提到的方法是以 swap 為主體，利用 L 與 R 去紀錄需交換的數量，再用 begin[] 與 end[] 作為堆疊，用來紀錄比較的範圍
### `node_t`
```clike
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
可以看到此結構用於單向鏈節串列，而 `left` 和 `right` 是在遞迴版本 quick sort 會使用，在非遞迴版則沒有使用到
### `list_tail`
```clike
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &((*left)->next);
return *left;
}
```
其目的是要找到鏈節串列的最後一個節點
在以下程式碼被使用： `end[0] = list_tail(list)` ，其中 `list` 為指向頭的指標，被帶入 `left` ，因此可以推斷 `AAAA` 為 `(*left)->next` 才會使得 `left` 從頭出發在迴圈中前進，當 `left` 間接指向最後第二個節點時會再前進最後一步，這時 `(*left)->next` 為 NULL 結束迴圈
### `list_length`
```clike
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &((*left)->next);
}
return n;
}
```
這個函式是要走訪鏈節串列，過程中計數，最後回傳節點個數
同理， `BBBB` 也是 `(*left)->next` ，這樣才能走訪鏈節串列
而由於迴圈中止條件是找到空指標，此函式不能用於環狀鏈節串列
### 非遞迴 `quick_sort`
運用 Optimized QuickSort — C Implementation (Non-Recursive) 所實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼
值得注意的是，此版本使用 `begin[]` 和 `end[]` 作為堆疊去取代遞迴的功能
若 L 不等於 R ，走訪 `begin[i]` 指向的鏈結串列，因此 `CCCC` 是 `&p->next`
而 `list_add(n->value > value ? &right : &left, n)` 可以看出 `left` 和`right` 為被 `pivot` 分開節點的鏈節串列入口，最後存到 `begin[]` ，如圖：
```graphviz
digraph structs {
node[shape=plaintext];
struct100 [label= "original :",color =black];
node[shape=box];
struct0 [label= "4",color =black];
struct1 [label= "1",color =black];
struct2 [label= "3",color =black];
struct3 [label= "5",color =black ];
struct4 [label= "2",color =black];
struct5 [label= "7",color =black];
node[shape=plaintext];
{
rank="same";
struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5 -> "NULL"
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
struct100 [label= "after first split :",color =black];
node[shape=box];
struct1 [label= "1",color =black];
struct2 [label= "3",color =black];
struct4 [label= "2",color =black];
node[shape=plaintext];
{
rank="same";
"begin[0]" -> struct1 -> struct2 -> struct4 ->NULL
}
}
```
```graphviz
digraph structs {
node[shape=box];
struct1 [label= "4",color =black];
node[shape=plaintext];
{
rank="same";
"begin[1]" -> struct1 ->NULL
}
}
```
```graphviz
digraph structs {
node[shape=box];
struct1 [label= "5",color =black];
struct2 [label= "7",color =black];
node[shape=plaintext];
{
rank="same";
"begin[2]" -> struct1 ->struct2 ->NULL
}
}
```
而對所有 i ，`end[i]` 則指向 `begin[i]` 所指鏈節串列的最後一個節點，因此 `DDDD` 為 `list_tail(&left)`，`EEEE` 為 `list_tail(&right)`
### 避免最差情況
Quick sort 的最差情況就是每次 pivot 都選擇到待排序數列的最小（或最大）值，如此一來每次切割只能將一節點排序，需要切割 $n$ 次，每次切割的代價為 $O(n)$ ，因此最差情況的時間複雜度為 $O(n^2)$
通常發生在已經大致排序完的數列，有幾種方法可以解決：
1. 三數取中法：選擇數列頭尾和中間三者的中位數作為 pivot
2. 隨機選擇法：隨機選擇數列中某元素作為 pivot
3. 混用插入排序：當數列切割至長度小於某值改用插入排序法
### 使用 Linux 核心風格的 List API 改寫
若要使用 linux/list.h 來實作， `node_t` 應該要改為以下這樣，加入 `list_head` 用來串連鏈節串列
```diff=
typedef struct {
- struct __node *left, *right;
- struct __node *next;
+ struct list_head list;
long value;
} node_t;
```
其他操作函式可參考上次作業 [lab0-c](https://github.com/wu81177/lab0-c/blob/master) 的部份，做以下取代
1. `void list_add(node_t **list, node_t *node_t)`
=> `static inline void list_add(struct list_head *node, struct list_head *head)`
2. `list_tail`的部份由於 `list_head` 是雙向的，只需要從 `head` 往前一步，做以下改寫：
```
node_t *list_tail(struct list_head *head)
{
node_t *left = list_entry(head->prev, node_t, list);
return *left;
}
```
3. `int list_length(node_t **left)`
=> `int q_size(struct list_head *head)`
4. `void list_free(node_t **list)`
=> `void q_free(struct list_head *head)`
5. `node_t *list_construct(node_t *list, int n)`
=> `bool q_insert_head(struct list_head *head, char *s)`
快速排序的程式的部份只要再根據以上取代做一些調整就能完成實作
## 測驗二
### Timsort
結合插入排序和合併排序，對於部分已排序的資料有出色的表現
1. 切割已排序的子數列 (run):
* 將數列拆分成單調的子數列，在此子數列稱為 run
* 將遞減的 run 反轉，使全部 run 遞增
2. 選擇 minrun ：
* 若 run 的數量等於或者略小於 2 的冪，效率會最高
* 為了滿足上一點，定義 minrun 表示 run 的最小長度
* 若長度太短就用二分插入排序，將後面的元素插入前面的 run
* 實際操作中，將 n 不斷除以 2 直到 n 小於預設的最小合併長度（MIN_MERGE），只要有任何一次不能整除 2，最終結果就加一
3. 使用堆疊：
* 為了避免使用大量記憶體，採用一組堆疊來暫存 run
* 運用 `merge_collapse` 函式來檢查堆疊頂端的 3 個 run 是否平衡，並且決定是否合併
4. Galloping mode：
* 合併相鄰子數列時，使用臨時記憶區域，大小設定為兩個子數列中較短者的長度
* 暫存較短者 A，找較長者 B 首元素在其排序位置，將小於 B 的部份放回A ，在剩餘 A 中找在 B 中位置，反覆進行
### `timsort.c`
#### `merge`
此函式用於合併兩個有序的 run ，頭分別為 a 和 b
`struct list_head *head` 用來表示合併後 run 的頭部
`struct list_head **tail` 為指向新 run 尾部的指標，一開始應指向頭部，等待後面更新，因此 `AAAA` 為 `&head`
```clike
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
```
上面為 a, b 兩數列比較元素大小的部份，較小或相等時應把尾部設為 a 的元素，反之設為 b 的元素，這樣才能排進合併後的數列，所以 `BBBB` 應為 `&a->next` ， `CCCC` 應為 `&b->next` ，直到有一方先結束，把另一個數列剩下的部份接上去再退出迴圈，完成合併
#### `build_prev_link`
```clike
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;
EEEE = tail;
}
```
這個函式是用於將 `list` 中的元素逆向走訪，放置到 `head` 和 `tail` 之間的環狀鏈節串列 ，因此迴圈走訪完後根據註解的提示，要將 `head` 和 `tail` 雙向串連，因此 `DDDD` 為 `tail ->next` ， `EEEE` 為 `head->prev`
#### `timsort`
```clike
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) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
}
```
此函式是timsort 演算法的主要函式，將一個雙向鏈表進行排序
在 do-while 迴圈中透過 `find_run` 找到 `list` 中的 run 並使用 `merge_collapse` 確保堆疊上的 run 長度保持平衡
當 `list` 被讀取完後使用`merge_force_collapse` 強制執行堆疊的合併，以確保堆疊中的 runs 長度平衡
最後階段如果 `stk_size` 小於 `FFFF` ，則不用再合併，否則要用 `merge_final` 執行最後合併，因此 `FFFF` 應為 1
# [第二周測驗題](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97)
## 測驗一
給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹
前序：訪問順序是「根左右」
中序：訪問順序是「左根右」
後序：訪問順序是「左右根」
因此前序越前面的數在樹的越上面，中序越前面數越左邊
題目程式中使用深度優先搜尋函數 `dfs` 建構二元樹，並在 `buildTree` 函式中建立雜湊表給 `dfs` 查找
### `dfs`
```clike=
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;
}
```
preorder：前序走訪結果陣列
pre_low 和 pre_high：前序走訪結果陣列的當前走訪範圍
inorder：中序走訪結果陣列
in_low 和 in_high：中序走訪結果陣列的當前走訪範圍
in_heads：中序走訪的 hlist 頭部陣列
size：中序走訪結果陣列的大小
這個函式遞迴過程中每一次都在前序走訪中取得當前的根節點，並在中序走訪中找到根節點的位置，然後遞迴構建左子樹和右子樹直到當前範圍為空，建構完成整個二元樹
### `hlist`
```clike
struct hlist_node {
struct hlist_node *next, **pprev;
};
struct hlist_head {
struct hlist_node *first;
};
static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
h->first = NULL;
}
```
hlist 指的是雜湊表鏈節串列，當發生碰撞時便會以 hlist 儲存元素，這裡以 `hlist_node` 定義了節點，根據 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-hash-table-%E5%AF%A6%E4%BD%9C)，可以看到和 `next` 不同的是 `pprev` 為間接指標指向前一個元素的 next ，如此一來就可以消除第一個元素的特例， list_head 中的 `first` 和一般元素中的 `next` 無異
若是用典型的雙向鏈節串列，當要移除第一個節點時，必須做出額外的操作來更新 list_head 指向的節點，除了移除的目標之外，還必須傳入 list_head
最後，`hlist_head` 作為鏈節串列的頭，也代表了雜湊表的一個 bucket ，包覆在 `hlist_node` 外面
每當要使用一個 bucket 的時候，便會用 `INIT_HLIST_HEAD` 初始化，供日後連接元素
### `hlist_add_head`
```clike
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;
}
```
每當要加入一個元素進入 hlist 便會使用這個函式將新元素作為 `first`
函式首先判斷 `first` 是否為空，若不為空就代表 `first` 已經存在元素，函式結束前會被新元素推擠到第二個，因此 `AAAA` 應為 `h->first`
若 `first` 為空一樣成立 `AAAA` 為 `h->first` 一樣成立，所以最後一個元素的 `next` 才會指向 NULL
```graphviz
digraph G {
rankdir = LR;
//splines = false;
node[shape = "record"]
list_head[label = "<m>hlist_head | <n>first | {<p>pprev | <q>next}"]
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];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 -> node_2 [
weight = 10, style = invis
]
list_head:q -> node_1:m;
node_1:p -> list_head:q;
//list_head:p -> list_head:n;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> NULL;
}
```
### `find`
```
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;
}
```
此函數是用來在一個 bucket 鏈節串列中用來找到某個 `num` 對應的索引值 `idx` ，
透過 `num` 絕對值對 `size` 取餘數後得到 hash 值，從 `struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads))` 可以看出 `in_heads` 是一指標陣列，用來指向結構， `in_heads` 會用來代入 `find` ，因此可以推斷 hash 值是作為此陣列的索引，因此 `BBBB` 應為 `heads[hash]`
而 `CCCC` 應為 `list_entry` ，因為要從 `hist_node` 找到外層的 `on` 才能進入找到裡面的 `val`
### node_add
```
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);
}
```
此函式的目的是為了將新的 `order_node` 加入到 hlist ，將 `val` 和 `idx` 寫入後，接下來與上段同理， hash 值應作為陣列索引，因此 `DDDD` 應為 `heads[hash]`
## 測驗二
LRU Cache（Least Recently Used Cache）是一種常見的快取管理策略。在這種策略下，每當訪問一個資料時，就會將該資料移到快取的頭部，表示這個資料最近被使用過，當快取已滿時，會將最近最少使用的的資料，也就是最尾部的資料刪除以釋放空間給新的資料，這樣的做法是假設最近使用的資料更有可能在未來被再次使用
在題目程式碼中，為了降低搜尋的時間複雜度，使用雜湊表，結構和上一題類似，函式和結構是以 hlist 為關鍵字，而串連 LRU Cache 的鏈節串列以 list 為關鍵字
### `hlist_del`
```clike
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
EEEE = pprev;
}
```
這題 hlist 的部份和上一題一樣，唯獨多了 `hlist_del` 的部份，作用就是移除 hlist 中的節點，函式最後的 `if` 是處理當節點為最後一個的特例，當 `next` 不為空的時候代表不是最後一個節點，這時 `pprev` 應改為前面節點的 `pprev` ，應此 `EEEE` 應為 `next->pprev`
### `LRUCache` & `LRUNode`
```clike
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
第一個結構用來代表一個 cash ， `hhead` 陣列內的每個元素代表雜湊表的一個 bucket， `dhead` 則是 LRUChe 的頭
而 `LRUNode` 代表一個元素， `node` 用在雜湊表的連接， `link` 則用在 LRU 順序的連接，一個 `LRUNode` 有兩種指標串連
### `lRUCacheFree`
```clike
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);
}
```
這段程式碼是釋放 LRUCache 的結構和其包含的所有節點
首先通過 list_for_each_safe 走訪 `dhead` ，因此 `FFFF` 應為 `link` ，這樣才能一次走訪全部，若是用 `node` 走訪要以 `hhead` 陣列的多個元素為入口
參考 `list_del` 的函式定義，`GGGG` 應為 `pos` ，刪除當前節點
### `lRUCacheGet`
```clike
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;
}
```
此函式用於從 LRU 快取中獲取給定 key 的值，先取餘數找到 hash 值，在 `hhead` 找到對應的 bucket 然後走訪 hlist ，相較於 `lRUCacheFree` 要走訪全部，此函式只需要找到一個節點，因此使用雜湊表的指標路線走訪， `HHHH` 應為 `node` ，而參考 `list_move` 的函式定義， `IIII` 應為 `pos`
### `lRUCachePut`
```clike
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;
}
}
```
此函式用於在 LRU 快取中插入或更新給定 key 和 value 的節點，和前段同理， `JJJJ` 應為 `node` ，`KKKK` 應為 `pos`
## 測驗三
### `__ffs`
```clike
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;
}
```
這個函式是用來找到 `word` 中最低位1的位置
由於不知道 `word` 是32位還是64位，所以先用 #if-#endif 判斷如果 `word` 長度是64，就看後面32位是否都是0，如果是 `num` 就加32，然後右移32位，因此 `AAAA` 應該要是二進位的32個1，也就是 `0xffffffff` 8個 f
後面同理，逐項以二的冪遞減檢查，把0排除，如此就能找到最低位1的位置
### `__clear_bit`
```clike
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;
}
```
用來把指定位元變成0
`mask` 是在指定位元為1，其他為0
透過 `p` 定位到要操作的 word
最後用 mask 將指定位置歸0，但 mask 是將指定位置標記為1，因此若要用&來操作要先把 `mask` 反轉，因此 `BBBB` 應為 `~mask`
### `fns`
```clike
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;
}
```
這個函式在 `word` 中尋找第 `n` 個被設置為 1 的位元的位置，如果找到了就返回該位置
過程中使用 `__ffs` 找到最低位1，然後把找到的1用 `__clear_bit` 歸零，直到找到第 n 個就回傳位置
### `find_nth_bit`
此函式可找出指定的記憶體空間找出第 N 個設定為1的位元
* `addr` : 指向陣列的指標
* `size` : 陣列的位元大小
* `n` :要找的第 N 個被設定的位元
函式首先判斷如果 `n` 大於或等於 `size`，就直接返回 `size`，因為沒有更多的位元可以搜尋
接下來判斷如果 size 是一個小型且常數的值（ `small_const_nbits(size)` 為真），就執行一個快速的位元操作。它從 `addr` 指向的位元陣列中取出 `size` 位元，然後使用 `GENMASK(size - 1, 0) ` 將除最低位元外的所有位元設定為 1。最後使用 `fns` 找到第 N 個被設定為 1 的位元的位置並回傳
如果 `small_const_nbits(size)` 不為真則執行 `FIND_NTH_BIT` 巨集：
```clike
#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; \
})
```
前面的迴圈在給定的位元陣列中進行迭代，過程計算 1 的位元的數量，直到找到第 N 個 1 或超過位元陣列的大小，而迴圈的條件 `(idx + 1) * BITS_PER_LONG <= sz` 保證每次迭代都在有效的位元陣列範圍內，而在迴圈內用 `w = hweight_long(tmp)` 來找到每次迭代中被設置為 1 的位元數
如果位元陣列的大小 `sz` 不是 `BITS_PER_LONG` 的整數倍時，對位元陣列的餘數位元，因此 `CCCC` 應為 ％
再來用 `tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz)` 留下餘數位元的部份
最後 `sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz)` 算出已檢查過都是 0 的 word 數乘以 64 加上最後一個 word 找到 1 的長度，就是答案，而 min 的作用是確保不超過 sz
Sign in with Wallet
Connect another wallet