# 2024q1 Homework2 (quiz1+2)
> contributed< `brian049` >
## Quiz1
### 測驗 `1`
**Optimized QuickSort — C Implementation (Non-Recursive)**
#### 填空及解釋運作原理
list_tail 函式藉由 while 迴圈迭代來找到 list 的尾端。
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &((*left)->next); // AAAA = (*left)->next
return *left;
}
```
欲求 list 的長度時，使用 while 迴圈迭代並計數來得到長度。
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &((*left)->next); // BBBB = (*left)->next
}
return n;
}
```
以下程式碼為實作 Quicksort 的主要部分。
```c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
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; // CCCC = p->next
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = list_tail(&left); // DDDD = list_tail(&left)
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right); // EEEE = list_tail(&right)
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
```
主要程式碼當中，一開始設定 `pivot` 為最左邊的節點，`p` 為 `pivot` 的下一個節點。再來判斷除了 `pivot` 以外的節點是否大於或是小於 `pivot` 的值，若是大於 `pivot` 則將該節點加到 `right` 序列當中，若是小於則加到 `left` 序列當中。
切割序列之後將整體序列分成三部分，第一部分首尾節點分別是 `left` 以及 `list_tail(&left)` ，第二部分為 `pivot` 單一節點，第三部分則是 `right` 以及 `list_tail(&right)`。
### 測驗 `2`
**Timsort**
#### 填空及解釋運作原理
在[測驗 2](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) 當中有指出 Timsort 與 merge sort 最大的差異在於「定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度，若長度太短，就用二分插入排序，將 run 後面的元素插入到前面的 run 裡面。」以及合併時採取 Galloping mode，進而降低 cache miss、降低記憶體開銷、降低比較次數。
以下程式碼為 timsort merge 的實作，用 `tail` 指標指向 `head` 來達到首尾相接的鏈結串列，若是 a 指向的節點的值小於或等於 b 節點的值，則將 a 指向的節點加到事先宣告的佇列當中，反之則將 b 指向的節點加入佇列，直到 a 或 b 佇列為空。
```c
static struct list_head *merge(void *priv,
list_cmp_func_t cmp,
struct list_head *a,
struct list_head *b)
{
struct list_head *head;
struct list_head **tail = &head; // AAAA = &head
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next; // BBBB = &a->next
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next; // CCCC = &b->next
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
以下程式碼將 `list` 佇列接到 `tail` 後面，並在最後將尾端與 `head` 相接，形成首尾相接的佇列。
```c
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 */
tail->next = head; // DDDD = tail->next
head->prev = tail; // EEEE = head->prev
}
```
以下程式碼是主要實作 timsort 的部份。逐一解說，先將環狀佇拆開成單向鏈結，在藉由 `find_run` 函式來切割出 run，再使用 `merge_collapse` 函式來對 run 進行檢查並整理，以確保堆疊中的 run 符合 timsort 的性質。
接下來使用 `merge_force_collapse` 函式對堆疊進行整理，再進行合併並重新接回雙向環狀鏈結。
```c
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 <= 1) { // FFFF = 1
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
}
```
## Quiz2
### 測驗 `1`
**Construct Binary Tree from Preorder and Inorder Traversal**
#### 填空及解釋運作原理
`hlist_add_head` 函式新增節點至鏈結的頭部並更新 `h` 指標。
```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; // AAAA = h->first
n->pprev = &h->first;
h->first = n;
}
```
以下程式碼藉由雜湊值來查找想要找的數值 `num`，利用 `hlist_for_each` 函式來比對，若找到則回傳當前的索引值 `idx`，沒有找到則回傳 -1。
```c
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, &heads[hash]) { // BBBB = &heads[hash]
struct order_node *on = list_entry(p, struct order_node, node); // CCCC = list_entry
if (num == on->val)
return on->idx;
}
return -1;
}
```
`node_add` 函式計算節計算雜湊值，再使用 `hlist_add_head` 來新增節點至對應雜湊的 `heads` 位置。
```c
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, &heads[hash]); // DDDD = &heads[hash]
}
```
### 測驗 `2`
**LRU cache**
#### 填空及解釋運作原理
`hlist_del` 函式將欲刪除之節點的前一個節點的指標指向欲刪除節點的下一個節點，來達到刪除節點的功能，而若是下一個節點存在，則更新該節點指向前一個節點的指標。
```c
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev; // EEEE = next->pprev
}
```
`lRUCacheFree` 函式利用 `list_for_each_safe` 來遍歷所有節點，並釋放節點所佔用的記憶體。
```c
void lRUCacheFree(LRUCache *obj)
{
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, link); // FFFF = link
list_del(&cache->link); // GGGG = &cache->link
free(cache);
}
free(obj);
}
```
`lRUCacheGet` 函式作用是在 LRUCache 中找尋指定值，若是找到則將 `cache->link` 放到最前面也就代表最近有被使用到。
```c
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(&cache->link, &obj->dhead); // IIII = &cache->link
return cache->value;
}
}
return -1;
}
```
`lRUCachePut` 函式分成兩部份，上半部找尋欲加入的 `key` 值是否存在於雜湊表當中，如果存在則將其移動到最前端來表示最近使用過，類似於 `lRUCacheGet` 函式的操作方式。
未存在於雜湊表時，也就是函式中的下半部，先檢查現有數量是否相等於 `capacity`，相等則代表快取已滿，此狀況就會刪除最少使用的數據，也就是最後一個節點，刪除後再新增新的 `key` 以及其 `value` 進快取。除此之外，若是快取未滿，就會將新的 `key` 以及其 `value` 加入到快取當中，並使當前數量 `obj->count` 加一。
```c
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, node); // JJJJ = node
if (c->key == key) {
list_move(&c->link, &obj->dhead); // KKKK = &c->link
cache = c;
}
}
if (!cache) {
if (obj->count == obj->capacity) {
cache = list_last_entry(&obj->dhead, LRUNode, link);
list_move(&cache->link, &obj->dhead);
hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);
} else {
cache = malloc(sizeof(LRUNode));
hlist_add_head(&cache->node, &obj->hhead[hash]);
list_add(&cache->link, &obj->dhead);
obj->count++;
}
cache->key = key;
}
cache->value = value;
}
```
### 測驗 `3`
**find_nth_bit**
#### 填空及解釋運作原理
ffs 目的是要找到第一個 set 的 bit。在定義中不斷使用 AND 操作來找第一個 1 的 bit 的位置。
```c
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
if ((word & 0xffffffff) == 0) { // AAAA = 0xffffffff
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;
}
```
`__clear_bit` 函式主要用於 `fns` 函式當中，目的是為了在找到第一個 set 的 bit 的時候，能夠透過清除 bitmap 中的指定 bit，並重複使用 `fns` 函式來找到第 n 個 set 的位置。
bit index 可以透過 `BIT_WORD` 巨集來獲得，再搭配 `addr` 記憶體空間，可得出指定 bit 的位元組。且運用 `BIT_MASK` 巨集得到 mask 用於清除指定 bit。
```c
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 &= ~mask; // BBBB = ~mask
}
```
`FIND_NTH_BIT` 把原本的資料以每 64 bit 為單位去作裁切，計算每段其中被設置的位元數量，若位元數量大於要找的位元數 `n` ，就代表目標位元就在該段內，直接返回。反之則將 `n` 減去位元數並進行下一個迴圈。
```c
#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 % BITS_PER_LONG) // CCCC = % \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
found: \
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
out: \
sz; \
})
```
Sign in with Wallet
Connect another wallet