# 2024q1 Homework2 (quiz1+2)
contributed by <[`padaray`](https://github.com/padaray)>
## 第一週測驗題
[題目連結](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗 `1`
參考資料是 [Optimized QuickSort](https://alienryderflex.com/quicksort/) ，此方法實作非遞迴的快速排序法
**鏈結串列結構**
```graphviz
digraph G {
subgraph cluster_1 {
node [shape=record];
hn1 [label="{ {left | right | next } | value : long }"];
label="node_t 1";
}
subgraph cluster_2 {
node [shape=record];
hn2 [label="{ {left | right | next } | value : long }"];
label="node_t 2";
}
hn1:next -> hn2
}
```
**快速排序法使用的函式**
1. `list_add`
此函式將節點 `node_t` 插入串列 `list` ，使節點 `node_t` 成為 `list` 串列的第一個節點，傳入的參數為 `**list` 原因是使用 `*list` 會複製一個 `list` 串列副本，因此要使用指標的指標來避免此問題
2. `list_tail`
此函式會逐一走訪每個節點，走訪到最後一個節點時，回傳該節點的記憶體位置，傳入的參數為 `**left` 原因是避免使用到條件判斷式，以此精簡程式碼
完整程式碼，已填空遮蔽部分 `AAAA`
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(*left)->next;
return *left;
}
```
3. `list_length`
初始化變數 `n` 為 0，逐一走訪每個節點，每走訪一個節點變數 `n` + 1，最後回傳變數 `n`
完整程式碼，已填空遮蔽部分 `BBBB`
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(*left)->next;
}
return n;
}
```
</br>
**快速排序法程式碼**
`quick_sort`
先呼叫函式 `list_length` 計算串列長度 `n`，以此得知堆疊所需要的配置的空間大小， `begin[]` 和 `end[]` 分別儲存串列的頭和尾，`result` 儲存排序後的串列， `left` 儲存小於 pivot 的節點， `right` 儲存大於 pivot 的節點
```c
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);
```
</br>
初始化變數 `L` 和 `R` 為 `begin[]` 和 `end[]` ， `L` 和 `R` 指向不同節點時，代表該串列節點數大於一，節點數不足二時，直接將該節點加入 `result` 串列
```cpp
if (L != R) {
...
} else {
if (L)
list_add(&result, L);
i--;
}
```
</br>
```graphviz
digraph{
rankdir=LR
node [shape=box,color=black]
pivot [shape=none,label=pivot]
p [shape=none,label=p]
pivot->node1
{rank=same;pivot;node1}
p->node2
{rank=same;p;node2}
node1->node2->node3->node4->node5[arrowhead=vee]
}
```
```graphviz
digraph{
rankdir=TD
node [shape=box,color=black]
pivot [shape=none,label=pivot]
p [shape=none,label=p]
pivot->node1
p->node2
node2->node3->node4->node5[arrowhead=vee]
{rank=same; node1; node2; node3; node4; node5;}
}
```
```c
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
```
</br>
從第二個節點開始逐一走訪，當此節點 `value` 小於 `pivot->value` 加入 `left` 串列，反之加入 `right` 串列，下圖為範例：
```graphviz
digraph{
rankdir=LR
node [shape=box,color=black]
{
left [shape=none,label=left]
pivot [shape=none,label=pivot]
right [shape=none,label=right]
}
right->9->8->10
left->2->6->4
pivot->7
}
```
```c
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
</br>
將 `left` 串列也就是比 `pivot` 小的節點儲存在堆疊下方，比 `pivot` 大的節點儲存在堆疊下方，並且把 `left` 和 `right` 串列清空，之後重複執行前面的步驟，下圖為範例：
```graphviz
digraph{
rankdir=LR
node [shape=box,color=black]
{
NULL1 [shape=none,label=NULL]
NULL2 [shape=none,label=NULL]
left [shape=none,label="left"]
stack0 [shape=none,label="stack[0]"]
stack1 [shape=none,label="stack[1]"]
stack2 [shape=none,label="stack[2]"]
right [shape=none,label="right"]
pivot [shape=none,label="pivot"]
}
right->NULL1
left->NULL2
stack0->2->6->4
stack1->7
pivot->7
stack2->9->8->10
}
```
```c
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
left = right = NULL;
i += 2;
```
</br></br>
### 測驗 `2`
## 第二週測驗題
[題目連結](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 `1`
題目為給定一個二元樹的前序(preorder)和中序(inorder)，以此重建二元樹
**hash key 結構**
```graphviz
digraph G {
subgraph cluster_1 {
node [shape=record];
hn1 [label="{ {**pprev | *next } }"];
label="hlish_node";
}
}
```
**hash table 結構**
**使用的函式：**
**`hlist_add_head`**
此函式是為了將一個 hash_key 插入 `h->first`。
- 若列表不為空，將 `first->pprev` 也就是本來節點一的 `pprev` 指向 `n->next` ， `n->next` 指向 `h->first` ， `n->pprev` 指向 `&h->first` ，最後 `h->first` 指向 `n`，即完成將新的節點，加入 `first` 第一個指向的地點。
- 實際方式如下方圖示：
```graphviz
digraph G {
rankdir = LR;
node [shape=record]
{
table [label="hash_table | |<ht1>hlist_head.first 1 | |..."];
hn0 [label="hlist_node_new | { <prev>pprev | <next>next}"];
hn1 [label="hlist_node1 | { <prev>pprev | <next>next }"];
hn2 [label="hlist_node2 | { <prev>pprev | <next>next}"];
NULL1 [shape=none,label=NULL];
}
table:ht1 -> hn1;
hn1:next -> hn2;
hn1:prev -> table:ht1;
hn2:next -> NULL1;
hn2:prev -> hn1:next;
}
```
```graphviz
digraph G {
rankdir = LR;
node [shape=record]
{
table [label="hash_table | |<ht1>hlist_head.first 1 | |..."];
hn0 [label="hlist_node_new | { <prev>pprev | <next>next}"];
hn1 [label="hlist_node1 | { <prev>pprev | <next>next }"];
hn2 [label="hlist_node2 | { <prev>pprev | <next>next}"];
NULL1 [shape=none,label=NULL];
}
table:ht1 -> hn1;
hn1:next -> hn2;
hn1:prev -> hn0:next [color=red];
hn2:next -> NULL1;
hn2:prev -> hn1:next;
}
```
```graphviz
digraph G {
rankdir = LR;
node [shape=record]
{
table [label="hash_table | |<ht1>hlist_head.first 1 | |..."];
hn0 [label="hlist_node_new | { <prev>pprev | <next>next}"];
hn1 [label="hlist_node1 | { <prev>pprev | <next>next }"];
hn2 [label="hlist_node2 | { <prev>pprev | <next>next}"];
NULL1 [shape=none,label=NULL];
}
table:ht1 -> hn1;
hn0:next -> hn1 [color=red];
hn0:prev -> table:ht1 [color=red];
hn1:next -> hn2;
hn1:prev -> hn0:next;
hn2:next -> NULL1;
hn2:prev -> hn1:next;
}
```
```graphviz
digraph G {
rankdir = LR;
node [shape=record]
{
table [label="hash_table | |<ht1>hlist_head.first 1 | |..."];
hn0 [label="hlist_node_new | { <prev>pprev | <next>next}"];
hn1 [label="hlist_node1 | { <prev>pprev | <next>next }"];
hn2 [label="hlist_node2 | { <prev>pprev | <next>next}"];
NULL1 [shape=none,label=NULL];
}
table:ht1 -> hn0 [color=red];
hn1:next -> hn2;
hn1:prev -> hn0:next;
hn2:next -> null;
hn2:prev -> hn1:next;
hn0:next -> hn1;
hn0:prev -> table:ht1;
}
```
**`node_add`**
此函式目的為加入一個新的節點進入 hash table。
- 初始化 `order_node` 的記憶體空間，傳入 `idx` 和 `val`，使用 hash 函式將存入的位置打亂，hash 函式是將 `val` 絕對值後除餘 `size` 值
- 最後用 `hlist_add_head` 函式插入 hash table
- 下方以 hash table `size` 為 5 ，`val` 為 4 為例：
```graphviz
digraph G {
rankdir = LR;
node [shape=record]
{
rank="same"
hash[label = "<h0>hlist_head.first 0 | <h1>hlist_head.first 1 | <h2>hlist_head.first 2 | <h3>hlist_head.first 3 | <h4>hlist_head.first 4"];
tex[label="hash table",shape=plaintext,fontcolor=black];
}
subgraph cluster_1 {
node [shape=record];
hn1 [label="{ {**pprev | *next } }"];
label="hlish_node";
node1[label="{val=4 | idx=0}",fontcolor=black];
}
hash:h4->hn1:next;
hn1:next->hash:h4;
}
```
**`dfs`**
此函式為深度優先演算法，主要目的是建構二元樹。
- 先使用 `find` 函式查找 `tn` 在 `inorder` 內的位置 `idx`
- 接著利用 `idx` 就可以知道左子樹是`in_low` 到 `idx-1`，右子樹是 `idx+1` 到 `in_hight` 。
- 最後將左子樹和右子樹放進 `dfs` 函式，回傳 `tn`
**主程式：**
**`buildTree`**
此函式目的為根據給定的前序和中序，建構一個二元樹，也就是題目要求。
- 使用 hash table 的原因是為了將搜尋的時間複雜度下降，因此一開始會將所有的值加入到 hash table 中
- 遞迴呼叫 `dfs` 函式建構左右子樹
</br>
### 測驗 `2`
實作 [LRU Cache](https://leetcode.com/problems/lru-cache/)
測驗二的 hash table 程式碼與測驗一相同，因此不多贅述。
**LRUNode 結構**：LRU Cache 中 Node 的結構，其中包含 key-value 對、list 結構和 hlist 結構
```graphviz
digraph G {
rankdir = LR;
node [shape=record]
subgraph cluster_1 {
node [shape=record];
label="LRUNode";
hn [label="{ **pprev | *next }"];
lh [label="{ *prev | *next }"];
node1[label="{ key | value }"];
}
}
```
**LRUCache 結構**：整個 LRU Cache，包括容量、當前儲存的數量...等
```graphviz
digraph LRUCache {
rankdir = LR;
node [shape=record]
subgraph cluster_1 {
node [shape=record];
label="LRUCache";
node1[label="{ capacity | count }"];
lh [label="{ *prev | *next }"];
hn [label="{ hhead[] }"];
}
hln1 [label="{ **pprev | *next }"];
hln2 [label="{ **pprev | *next }"];
hn->hln1->hln2
}
```
**LRU Cache 使用的函式：**
**`lRUCacheCreate`**
此函式用於創建一個空的 LRUCache。
- 輸入參數為 `capacity` 也就是 cache 的容量( `hlist_head` 串列的長度 )，初始化所有的變數，回傳一個完整 LRU Cache
**`lRUCacheFree`**
此函式用於刪除整個 LRU Cache。
- 使用 `list_for_each_safe` 函式走訪每個節點，同時斷開目前節點與串列的連結，並且釋放此節點空間
**`lRUCacheGet`**
此函式用於取得 key 在 LRUCache 中所對應的 value。
- 先將輸入的 `key` 值除餘 `LRUCache->capacity` 得到變數 `hash`
- 使用 `hlist_for_each` 函式走訪 `LRUCache->hhead[hash]` 的每個節點
- 若有和輸入變數 `key` 值相同的節點，則將此節點使用 `list_move` 函式移動到 `hhead[hash]` 串列的第一個節點
**`lRUCachePut`**
此函式用於在 LRUCache 中放入 key-value。
- 前半部操作與 `lRUCacheGet` 相似，若此 key 已經存在，則將此節點移動到串列的第一個。
- 當節點不存在時，判斷 LRUCache 是否已滿 ( count == capacity )，若已滿則使用 `list_move` 函式將最後節點移至第一個節點，使用 `hlist_del` 函式刪除此節點，最後用 `hlist_add_head` 函式加入新的節點。
- LRUCache 沒滿則直接插入新節點即可
### 測驗 `3`
**`const_hweightn`**: n = 8, 16, 32, 64
這四個巨集用來計算在一段二進制數列中，共有幾個位元為 1
**`FIND_NTH_BIT`**
這個巨集用來查看第 N 個 bit 為 0 或 1。
- 先計算 word 中被設置的位元數目，比較查找第 num 個被設置的位元。若找到則回傳該位元的索引值；否則，繼續往下個位元找。
**`__ffs`**
此函式全名為 find first bit，目的為找到第一個位元數為 1 的位置。
- `num` 變數用來計算第一個位元 1 的位置。先檢查第一個位元是否在後 32 個 bits，如果是 `num` + 32
- 檢查第一個位元 1 的位置是否在後 16 個 bits，如果是 `num` + 16，依此類推，持續執行檢查到最後一位。
**`fns`**
此函式全名為 find N'th set bit，目的為找到第 N 個位元數為 1 的位置。
- 先呼叫 `__ffs` 函式找到第一個位元數 1
- 呼叫 `__clear_bit` 函式清除該位元並且將 N - 1，持續上述動作直到 N 為 0
**主程式：**
**`find_nth_bit`**
此函式目的為在一段二進制數列中，找到第 N 個位元為 1 的位置。
- 先檢查要查找的第 `n` 位是否超過傳入的參數 `size` 的範圍
- 使用 `small_const_nbits` 確認要搜索的範圍是否不超過一個 word，是的話使用 `fnc` 函式找到 bit 為 1 的位置
- 要搜索的範圍超過一個 word 時，使用 `FIND_NTH_BIT` 函式確認第一個 bit 為 1 的位置
Sign in with Wallet
Connect another wallet