# 2024q1 Homework2 (quiz1+2)
contributed by < [mesohandsome](https://github.com/mesohandsome) >
## 第 1 周測驗題測驗 1
### `list_tail()`
這裡使用間接指標來操作，這個函式用來找到串列的結尾，所以要不斷將指標向後更新，因此 `AAAA` 這邊為 `(*left)->next`
```graphviz
digraph G {
node [shape = box, fontname = "Times-Roman"];
rankdir = LR;
indirect [label = "indirect"];
head [label = "head"];
node1 [label = "node1"];
node2 [label = "node2"];
subgraph cluster_1 {
label = "linked list";
head -> node1 -> node2;
};
indirect -> head;
}
```
```graphviz
digraph G {
node [shape = box, fontname = "Times-Roman"];
rankdir = LR;
indirect [label = "indirect"];
head [label = "head"];
node1 [label = "node1"];
node2 [label = "node2"];
subgraph cluster_1 {
label = "linked list";
head -> node1 -> node2;
};
indirect -> node1;
}
```
```diff
while ((*left) && (*left)->left)
- left = &(AAAA);
+ left = &((*left)->next);
return *left;
```
### `list_length()`
`list_length()` 也使用間接指標，用來查找整個串列的長度，當中的 left 指標必須向後更新，因此 `BBBB` 為`(*left)->next`
```diff
while (*left) {
++n;
- left = &(BBBB);
+ left = *((*left)->next);
}
```
### `quick_sort()`
程式中取第一個元素當成 pivot，因此這邊將 pivot 往後的元素以大小分成左右兩側，將 pivot 向後移，所以 `CCCC` 為 `p->next` 將指標更新
```graphviz
digraph G {
node [shape = box, fontname = "Times-Roman"];
rankdir = LR;
rank = "same";
4 -> 1 -> 3 -> 5 -> 2 -> 7;
pivot [shape = plaintext, fontname = "Times-Roman"];
pivot;
{
rank = same;
pivot -> 4;
};
}
```
接著把左側放在 i、中間放 pivot、右側放 i + 2，每回合的操作結束就將目前的 index + 2，直到將右側分割完畢，就會從右側依序退回到左側還沒分割的部分並且把已經分割且排序好的元素加回到保存結果的串列中，再繼續重複將剩下的都排序好
```graphviz
digraph G {
node [shape = box, fontname = "Times-Roman"];
subgraph cluster_1 {
label = "i";
1 -> 3 ->2;
};
subgraph cluster_2 {
label = "i + 1";
4;
};
subgraph cluster_3 {
label = "i + 2";
5 -> 7;
};
}
```
```graphviz
digraph G {
node [shape = box, fontname = "Times-Roman"];
subgraph cluster_1 {
1 -> 3 -> 2;
};
subgraph cluster_2 {
4;
};
subgraph cluster_3 {
label = "i";
NULL;
};
subgraph cluster_4 {
label = "i + 1";
5;
};
subgraph cluster_5 {
label = "i + 2";
7;
};
}
```
```diff
while (p) {
node_t *n = p;
- p = CCCC;
+ p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
`begin[]` 和 `end[]` 分別放串列的開頭與結尾，所以 `DDDD` 與 `EEEE` 分別為 `list_tail(&left)` 和 `list_tail(&right)`
```diff
begin[i] = left;
- end[i] = DDDD;
+ end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
- end[i + 2] = EEEE;
+ end[i + 2] = list_tail(&right);
```
## 第 1 周測驗題測驗 2
### `merge()`
這裡也使用到間接指標，所以 `AAAA` 為 `&head`
```diff
struct list_head *head;
- struct list_head **tail = AAAA;
+ struct list_head **tail = &head;
```
比較過後，把適合的節點合併到 `tail` 中，然後將 `tail` 向後移動以添加新的節點，所以 `BBBB` 和 `CCCC` 分別為 `&a->next` 和 `&b->next`
```diff
if (cmp(priv, a, b) <= 0) {
*tail = a;
- tail = BBBB;
+ tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
- tail = CCCC;
+ tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
```
### `build_prev_link()`
將 `head` 與 `tail` 的關係建立好，形成環狀的雙向佇列
所以 `DDDD` 和 `EEEE` 為 `tail->next` 和 `head->prev`
```diff
- DDDD = head;
- EEEE = tail;
+ tail->next = head;
+ head->prev = tail;
```
### `timsort()`
下面進行最後一次合併，因此當堆疊的大小是小於或等於 1 時，就要將他們的頭尾連接上，形成環狀的佇列
所以 `FFFF` 的值為 1
```diff
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
- if (stk_size <= FFFF) {
+ if (stk_size <= 1) {
build_prev_link(head, head, stk0);
return;
}
```
## 第 2 周測驗題測驗 1
### `hlist_add_head()`
把新加入的節點與原本的開頭連接上，所以 `n->next` 為 `h->first`
```diff
if (h->first)
h->first->pprev = &n->next;
- n->next = AAAA;
+ n->next = h->first;
n->pprev = &h->first;
h->first = n;
```
### `find()`
找到當前的 hash value 後，在 hash 的此欄位中查找後面所有的節點，所以 `hlist_for_each` 使用的起始為 `&heads[hash]`
為了取得節點的資訊，需要用 `list_entry` 取出
```diff
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);
+ hlist_for_each (p, &heads[hash]) {
+ struct order_node *on = list_entry(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
```
### `node_add()`
找出 hash value 後，要將新節點增加在這個欄位中，所以 `DDDD` 為 `&heads[hash]`
```diff
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);
+ hlist_add_head(&on->node, &heads[hash]);
```
## 第 2 周測驗題測驗 2
### `hlist_del()`
因為不會有第一個節點的 `pprev` 指向 `NULL` 的狀況，所以可以直接將前一項與後一項相接，因此 `EEEE` 為 `next->pprev`
```diff
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
- EEEE = pprev;
+ next->pprev = pprev;
```
### `lRUCacheFree()`
要將 `list_head` 串列中的節點都刪除，`pos` 在 `LRUNode` 結構中的指標為 `link`，而要再將這個連結關係從串列中移除，`GGGG` 為 `&cache->link`
```diff
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
- LRUNode *cache = list_entry(pos, LRUNode, FFFF);
- list_del(GGGG);
+ LRUNode *cache = list_entry(pos, LRUNode, link);
+ list_del(&cache->link);
free(cache);
}
free(obj);
```
### `lRUCacheGet()`
要將 hash 中的某個欄位取出，這裡 `pos` 在 `LRUNode` 中的指標為 `node`，找到後再使用 `list_move` 將整個串列取出，`IIII` 為 `&cache->link`
```diff
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
- LRUNode *cache = list_entry(pos, LRUNode, HHHH);
+ LRUNode *cache = list_entry(pos, LRUNode, node);
if (cache->key == key) {
- list_move(IIII, &obj->dhead);
+ list_move(&cache->link, &obj->dhead);
return cache->value;
}
}
```
### `lRUCachePut()`
和上面的 `HHHH` 以及 `IIII` 相同，所以 `JJJJ` 為 `node`，`KKKK` 為 `&c->link`
```diff
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);
+ LRUNode *c = list_entry(pos, LRUNode, node);
if (c->key == key) {
- list_move(KKKK, &obj->dhead);
+ list_move(&c->link, &obj->dhead);
cache = c;
}
}
```
## 第 2 周測驗題測驗 3
### `__ffs()`
找出第一個 bit，這邊是應用二分搜尋法，所以 `AAAA` 為 `0xffffffff`
```diff
- if ((word & AAAA) == 0) {
+ if ((word & 0xffffffff) == 0) {
num += 32;
word >>= 32;
}
```
### `__clear_bit()`
先產生一個 mask 在指定 bit 上為 1，最後再將目前的值與 `~mask` 以 and 將此 bit 清除，所以 `BBBB` 為 `~mask`
```diff
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;
+ *p &= ~mask;
}
```
### `FIND_NTH_BIT()`
這邊的判斷是為了避免操作到有效位元以外的位數
```diff
- if (sz CCCC BITS_PER_LONG) \
+ if (sz % BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
```
Sign in with Wallet
Connect another wallet