# 2024q1 Homework2 (quiz1+2)
contribute by < david965154 >
### 第 1 周測驗題
#### 測驗 `1`
```c
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
在問題代號 `CCCC` 迴圈中，目的為：走過每一節點，若其成員 `value` 大於 `pivot` 成員的 `value` ，則分配置鏈結串列 `right` ，否則為 `left` ，因此若要走過每一節點，則需以 `p = p->next` 達成。
觀察最外圈 `while` 迴圈，可以看到關鍵的
```c
node_t *L = begin[i], *R = end[i];
if (L != R) {
...
```
這裡是讓 `L` 指向 `begin[i]` ，而 `R` 指向 `end[i]` ，下一個判斷式為 `if (L != R)` ，這裡可以看到當 L 及 R 為同一點即無須進入分配 `right` 及 `left` 的區塊，是迴圈結束的關鍵。因此近一步來看 begin[i] 及 end[i] 為何
```c
begin[i] = left;
end[i] = DDDD;
```
可以看到其實 `begin[i]` 就是鏈結串列 `left` ，而因為 `left` 是指標，指著第一個節點，當然 `end[i]` 也就是指著鏈結串列 `left` 的尾部節點，因此要填入 **`list_tail(left)`** ， `end[i + 2]` 則填入 **`list_tail(right)`** ，如此一來，可以透過將原始鏈結串列，不斷透過與錨點（pivot）比較大小分左右鏈結串列，依序加入右鏈結串列、錨點再來左鏈結串列，達到 `quick sort` 的目的。
#### 測驗 `2`
`timsort.c` 內函式達成目標
```c
static inline size_t run_size(struct list_head *head)
```
透過是否有下個節點來回傳該鏈結串列長度，與 `queue.c` 實作時使用的結構大同小異，但是會在函式 `timsort` 內先將雙向循環鏈結串列從尾部與頭部斷開成為非循環狀態，因此可以達成這樣的計算判斷式
再來說明 `(head->next->prev)` 理應要指向一 `struct` ，但是這裡卻強制轉型為 `size_t` 型態，因此要從後方函式 `find_run` 看起，該函式在執行完的最後執行了 `head->next->prev = (struct list_head *) len;` ，他把 `size_t` `len` 轉型為 `struct` `list_head` ，再將鏈結串列長度資訊包含在已經斷開的 `(head->next->prev)` 。這樣在初始放入亂數在鏈結串列時，直接順便計算數量，並包含在鏈結串列內，無須在需要時逐一走訪鏈結串列計算節點數。
:::warning
補充 [std::size_t](https://en.cppreference.com/w/cpp/types/size_t)
> std::size_t can store the maximum size of a theoretically possible object of any type (including array).
:::
```c
static struct list_head *merge(void *priv,
list_cmp_func_t cmp,
struct list_head *a,
struct list_head *b)
```
這段就是用來 `merge` 兩個鏈結串列的，透過比較兩個鏈結串列最前方的節點並接上 head 達成。
```c
struct list_head *head;
struct list_head **tail = AAAA;
...
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB;
a = a->next;
if (!a) {
*tail = b;
break;
}
}
...
```
`tail` 用途顯然是用來接續 `head` 指向的鏈結串列，因此初始會指向指標 `head` ，若以一般使用 `pointer` 的方法改寫:
```c
struct list_head *head;
struct list_head *tail = head;
...
if (cmp(priv, a, b) <= 0) {
if(head)
tail = a;
else
tail->next = a;
tail = tail->next;
a = a->next;
if (!a) {
tail = b;
break;
}
}
...
```
這種寫法每次進迴圈皆須做一次比較，若改以第二種方法:在進入 `for` 迴圈時讓 `head` 有指向節點，而不是一個指標，因此先做一次 `cmp(priv, a, b)` ，讓他接上一節點再進入 `for` 迴圈。不過又會因此多寫一段，若改以指向指標的指標寫，那麼指標 `head` 與節點 `next` 接為指標，不必因為 `tail` 只能指向結構而分兩種情況。
```c
static void build_prev_link(struct list_head *head,
struct list_head *tail,
struct list_head *list)
```
這裡是將 `list` 裡的節點依序接上 `tail` ，最後再頭尾相連形成雙向循環鏈結串列。
```c
static void merge_final(void *priv,
list_cmp_func_t cmp,
struct list_head *head,
struct list_head *a,
struct list_head *b)
```
這裡也是 `merge` ，不過是將輸入的單向鏈節串列 `merge` 後同時轉為雙向鏈節串列，當其中鏈結串列比較完後統一將剩餘單向鏈結串列接至 `b` 再透過函式 `build_prev_link` 將 `b` 後方之單向鏈節串列轉為雙向鏈節串列。
```c
static struct pair find_run(void *priv,
struct list_head *list,
list_cmp_func_t cmp)
```
給定一 `list` 從頭開始選取兩個 `list->next` 與 `list` ，若後比前小 ( 即 `list->next` 比 `list` 小 ) 則 `list` 的指標 `next` 指向 `list` 原先的 `prev` 直到又遇到後比前大或 `list` 沒有 `next` 節點 ( 即 `list->next` 比 `list` 大 ) ，整段迴圈即停止，而若後比前大，則正常移動。同時，兩者在移動的同時皆會計算經過節點數量。
在最後 next 會指向 `NULL` 或是 `與上述順序相反的第一節點 `。
最後會產生一單向鏈結串列，而 head 指向其第一節點，的節點的指標 `prev` 將會指向 `NULL` ，而將鏈結串列長度資訊包含在不需要的 `(head->next->prev)` ，也就是第二個節點的指標 `prev`。
最後透過 `struct` `pair` 透過 `head` 及 `next` 指向此函式建立的單向鏈結串列及下一次的起點 `next` ( 即此次單向鏈結串列迴圈結束後的第一個節點 )。
```c
static struct list_head *merge_at(void *priv,
list_cmp_func_t cmp,
struct list_head *at)
```
這裡也是做 `merge` ，不過 `merge` 的兩鏈結串列結構較特殊，其中一鏈結串列為另一鏈結串列的首個節點使用 `prev` 指向其首個節點，因此有一鏈結串列的走訪方法為 `at` 往 `next` 方向移動，而另一鏈結串列為 `at->prev` 後往 `next` 方向移動。
兩鏈結串列合併後，將 `merge` 後之鏈結串列首個節點 `prev` 指向原先 `at->prev` 的 `prev` (即其中一項鏈結串列之原本指向的 `prev`) 指向的節點，再將鏈結串列第二個節點的 `prev` 指向鏈結串列長度。
```c
static struct list_head *merge_force_collapse(void *priv,
list_cmp_func_t cmp,
struct list_head *tp)
```
這裡就是 `merge` 不同串鏈結串列，不過因為 `merge` 的對象必須相鄰，因此同時會合併第 2 條鏈結串列的情況下，這裡會選擇較短的先與第 2 條做合併，因此可以達到每次合併都盡量以最少長度合併 (因為合併時所需的最大比較次數為兩鏈結串列之最大長度) ，而避免每次需與越來越長的鏈結串列合併時最大比較次數被該鏈結串列支配的情況。
```c
static struct list_head *merge_collapse(void *priv,
list_cmp_func_t cmp,
struct list_head *tp)
```
這裡是確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：
1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。
如 $A$ 的長度不大於 $B$ 加 $C$ 的總和（亦即 $A<=B+C$），且 $C$ 的長度小於 $A$，因此會選擇將 $C$ 與 $B$ 進行合併。甚至當需 merge 之鏈結串列超過 4 時 D 也會被納入考慮，如 $D<=C+B$ 。
```c
void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
```
這裡實際上就是應用各函式，分成四個部分
1. 斷開原始鏈結串列循環，成為非循環單向鏈結串列。
2. 開始透過 `find_run` 切分子鏈結串列，且在切的時候當切出超過 2 個子鏈結串列會以 `merge_collapse` 確保堆疊上的 run 長度保持平衡。
3. 在需 `merge` 子鏈結串列 `>=3` 時皆以 `merge_force_collapse` 進行合併。
4. 透過 `build_prev_link` 建立雙向鏈節並以 `merge_final` 合併剩餘二雙向鏈節串列。
如此一來便合併完各雙向循環鏈結串列並結束函式。
### 第 2 周測驗題
#### 測驗 `1`
在說明如何透過陣列的前序 (preorder) 和中序 (inorder) 形式，建立二元樹前，先來看一下儲存 hash table 的鏈結串列 (不過在這裡沒有用到) 。
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
`hlist_node` 就是一個由成員 : 指向結構的指標 `next` 及指向指向結構的指標的指標 `pprev` 的結構。
詳見 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)
```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 = h->first;
n->pprev = &h->first;
h->first = n;
}
```
這裡需要添加 `n` 指向的 `struct hlist_node` 至 `h->first` 指向的首個節點，而因為指標的指標 `pprev` 指向前一個節點指向下一個節點的指標 (即指向自身節點的指標) 因此若 `h->first` 有指向節點，則先將原始 `h->first` 指向的首個節點的 `pprev` 指向要新增的節點的 `next` 指標，為 "退位" 做準備，接下來把 `n->next` 指向 `h->first` 和 `n->pprev` 指向 `h->first` 的位置，最後將 `h->first` 指向 `n` 即完成新增節點至鏈結串列的動作。
接下來就是整段程式碼核心，建立二元樹。
```c
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)
```
簡單明瞭就是透過 `preorder` 及 `inorder` 陣列順序尋找對應位置關係建立二元樹，而 `pre_low, pre_high, in_low, in_high` 是用來儲存須建立的子樹在陣列中的範圍。
#### 測驗 `2`
```c
LRUCache *lRUCacheCreate(int capacity)
```
這裡先創建一個 capacity 數量的 `struct list_head` 不過這裡的 `malloc` 配置應該有誤
```c
LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
capacity * sizeof(struct list_head));
```
`LRUCache` 結構為
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
應要配置 `struct hlist_head hhead[]` 的空間，且在迴圈內部
```c
for (int i = 0; i < capacity; i++)
INIT_HLIST_HEAD(&cache->hhead[i]);
```
這裡會透過函式 `INIT_HLIST_HEAD` 將 capacity 個 `&cache->hhead[i]` 初始化，而 `INIT_HLIST_HEAD` 需要 `struct hlist_head *h` 作為參數，因此 malloc 應該改成
```c
LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
capacity * sizeof(struct hlist_head));
```
```c
void lRUCacheFree(LRUCache *obj)
```
這裡就是將所有配置的 `cache` 做移去並釋放記憶體的動作。
```c
int lRUCacheGet(LRUCache *obj, int key)
```
給予一 `key` 值，若在 cache 中找到便移去 `obj->dhead` 並回傳其 `value` 。用意是只要最近使用到就移去最近在使用之代表區域。
```c
void lRUCachePut(LRUCache *obj, int key, int value)
```
這裡前面類似函式 `lRUCacheGet` ，不過這裡是在給予一 `key` 值，找到對應的 `cache`，如果找布袋那就代表需要配置一節點給予放置，因此會判斷 `count` 是否等於 `capacity` ，若是則刪除最近沒使用到的，若非則配置一塊新的 `LRUNode` ，再將其 value 設為傳入參數 `value` 。
#### 測驗 `3`
```c
#define FIND_NTH_BIT(FETCH, size, num)
```
這裡要找一塊 bit 數為 size 的記憶體區塊，裡面第 num 個被 set 為 1 的位置，而計算時需要將 size 切分為多個 `BITS_PER_LONG` 再用 macro `hweight_long` 計算。
```c
static inline unsigned long __ffs(unsigned long word)
```
計算多少個連續 0 ，即為右移連續零後的第一個 1 之位置。
```c
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
```
清除位於指定記憶體位址中指定位的位元值（設置為 0）
```c
static inline unsigned long fns(unsigned long word, unsigned int n)
```
在 word (一個長整型數值) 中找到第 n 個設置位 (1 的位) 的位置。使用 `while` 迴圈不斷透過 `__ffs` 尋找，直到 `n` 為 0，結束。
```c
static inline unsigned long find_nth_bit(const unsigned long *addr,
unsigned long size,
unsigned long n)
```
使用上面的函式計算，若小於 `BITS_PER_LONG` 則無需使用函式 `FIND_NTH_BIT` 計算，直接對指向記憶體位置之值使用 macro `GENMASK` 產生長度為 size 的 mask，並使用 `fns` 計算。
Sign in with Wallet
Connect another wallet