# 2024q1 Homework2 (quiz1+2)
contributed by < [han1018](https://github.com/Han1018) >
## 2024q1 第 1 週[測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
測驗一用於實作非遞迴版本的 quick sort。
```c
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
```
begin[] 和 end[] 是堆疊，用來存儲比較的範圍。left 和 right 是用來存儲分割範圍後的左右子節點。
```c
node_t *L = begin[i], *R = end[i];
```
每一輪排序中，使用 L 和 R 來表示此輪要排序的串列的開頭和結尾。變數 i 用於指示目前要處理的未完成排序串列的位置。
```c
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = p->next
list_add(n->value > value ? &right : &left, n);
}
```
用於比較的 Pivot 是從第一個元素取得的。用 p 來遍歷整個串列，將其與 pivot 的值進行比較，如果比 pivot 大就將其加入 right，如果小於等於就將其加入 left。
```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;
```
### 測驗二
## 2024q1 第 2 週[測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
目標：程式中使用了 `order_node` 表示 preoreder 和 inorder 的排序，並要求回傳重建的二元樹。
- 結構體 `order_node` : 用於表示 inorder 和 preorder 的 雜湊鏈結串列
- `static int find(int num, int size, const struct hlist_head *heads)` :
```c
if (num == on->val)
return on->idx;
}
```
給定了一個 hash list_head 和指定的目標值，遍歷整個鏈結串列如果找到與目標值相同的 Node 回傳其 index。
- `static inline void node_add` : 用於建立雜湊鏈結串列，將 inorder 的 value 計算出雜湊值放置對應的位置。
- `static struct TreeNode *dfs` : 依據 inorder 和 preorder 還原二元樹
```c
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);
```
根據 preorder 和 inorder 的特性找出 root、left、right node的過程如下：
1. 根據 preorder，第一個節點是根節點。
2. 根據 inorder，根節點的左邊是 left node，右邊是 right node。因此，可以遞迴地尋找 preorder 的 root，然後利用 root 找到 inorder 中左右兩節點的索引。接著，將這些索引套入遞迴中，以找出 preorder 的 root 、left 和 right node 的索引。
這樣的流程可以有效地根據 preorder 和 inorder 的特性來找出樹的結構。
- `static struct TreeNode *buildTree` :
還原二元樹的主流程：
1. 建立 鏈結串列雜湊表
2. 插入 inorder 的值至雜湊表
3. 用 preorder 和 inorder 比對找出左右根節點並建立二元樹
### 測驗二
```c
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;
```
實作中有兩個關鍵的結構體，一個是 LRUCache 另一個是 LRUNode。LRUCache 結構體中的雜湊表包含很多個 LRUNode
```c
LRUCache *lRUCacheCreate(int capacity)
```
```c
LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
capacity * sizeof(struct list_head));
```
這裡負責建立 LRUCache 結構體，上方 code 需修改為 capacity * sizeof(struct hlist_head)。
```c
void lRUCacheFree(LRUCache *obj)
```
這裡負責移除和釋放 LRUCache，以及 LRUCache 中的所有 LRUNode。
```c
int lRUCacheGet(LRUCache *obj, int key)
```
這裡負責從 LRUCache 中的雜湊表中檢索 key 的值並回傳。
```c
void lRUCachePut(LRUCache *obj, int key, int value)
```
這裡負責將 key 和 value 加進 LRUCache 的雜湊表或是更新已經有 key 的值。
### 測驗三
```c
static inline unsigned long __ffs(unsigned long word)
```
這裡的任務是尋找第一個位元（bit），Num 記錄了第一位的位置。從32個位元中開始尋找，一直追蹤到最後一個位元。例如，如果 AAAA = 0xFFFFFFFF，則 num + 32，表示在2^32 -1之前的位元都不是第一個位元，因此向右移動32位，然後繼續尋找2^16，一直追蹤到經過63個位元後結束。
```c
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
```
我們的目標是清除指定 mask 的值。addr 是要被清除的位址，nr 是一個 mask 用於清除 addr。清除的方法是 A &= ~mask，因為 mask 的值為1，將1反轉後再 and 就可以清除位元。因此 BBBB 是 ~mask。
```c
static inline unsigned long find_nth_bit(const unsigned long *addr,
unsigned long size,
unsigned long n)
```
目標是找出記憶體區域中第 N 個被設為1的位元索引位置。在計算時，需要將 size 切分為多個 BITS_PER_LONG，然後使用 hweight_long 函數進行計算。
Sign in with Wallet
Connect another wallet