owned this note
owned this note
Published
Linked with GitHub
# 2024q1 Homework2 (quiz1+2)
contributed by < `SimonLee0316` >
## 第一週測驗題
### 測驗一
list_tail : 回傳最後一個節點
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(*left->next);
return *left;
}
```
list_length : 計算 list 長度
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(*left->next);
}
return n;
}
```
:::danger
再次闡述你的洞見。
:::
### 測驗二
#### merge
:::danger
改進你的漢語表達，用字務求明確清晰。
:::
合併兩條鏈結串列如果一方值較大則它排在前面，值較小的鏈結串列往後移，依此類推
```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;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
#### build_prev_link
將原本單向鏈結串列串回雙向
```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;
head->prev = tail;
}
```
#### timsort
:::danger
在你列出程式碼 (不該急著「舉燭」) 之前，闡述 Timsort 的特性、針對鏈結串列的場景該做什麼調整，還有你在程式碼中發現什麼 (亦即你的「洞見」)，進行分析和解說。程式碼的列舉是為了討論，倘若你不做這件事，根本沒必要列出程式碼。
:::
透 find run 來找到所有的 run 並加入佇列，並檢查佇列內容如果頂端三個佇列不能滿足
$1.A < B+C$
$1.B < C$
則先做合併使它能夠保證長度的平衡
找到所有的 run 之後，在將所有的 run 合併，最後將單向鍊結串列串回雙向
---
## 第二周測驗題
### 測驗一
hlist_add_head
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
將一個的新的節點插入到 hlist 的開頭處。
```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;
}
```
find
在 list 找某個特定的值
```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]) {
struct order_node *on = container_of(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
return -1;
}
```
node_add
```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]);
}
```
圖解
preorder : 3 9 20 15 7
inorder : 9 3 15 20 7
```graphviz
digraph a{
3
3->9
subgraph cluster0{
9
}
3->7
subgraph cluster1{
7
20
15
}
}
```
```graphviz
digraph b{
3
3->9
3->20
subgraph cluster1{
7
20
15
}
}
```
```graphviz
digraph b{
3
3->9
3->20
20->15
subgraph cluster1{
7
15
}
}
```
```graphviz
digraph c{
3
3->9
3->20
20->15
20->7
subgraph cluster1{
7
}
}
```
```graphviz
digraph d{
3
3->9
3->20
20->15
20->7
}
```
### 測驗二
hlist_del
刪掉 n 節點
```c
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}
```
lRUCacheFree
刪掉所有節點所代表的結構並釋放節點指標(包括自己)
```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);
list_del(&cache->link);
free(cache);
}
free(obj);
}
```
lRUCacheGet
在 `LRUCache` 裡面找 key 值為 `key`，並把它移到最前面代表最近被存取(LRU)
雜湊函數為取餘數
```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, link);
if (cache->key == key) {
list_move(&cache->link, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
:::danger
不要只是「舉燭」，你的洞見在哪？指出上述程式碼的原理和缺失，並著手改進。
:::
LRUCacheput
在 LRUCache 根據 hash key 放入值，
如果不存在 key 則 刪掉最後一個元素(最不常被用到)
如果已經存在更新他到最前面代表最近被存取
```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, link);
if (c->key == key) {
list_move(&c->link, &obj->dhead);
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;
}
```
圖解
雜湊函數 `hash = key % obj->capacity;`
```graphviz
digraph LRUcache {
node [shape=record]
rankdir=LR
subgraph cluster_a {
label = LRUCache;
struct0 [label="capacity"];
struct1 [label="count"];
struct2 [label="dhead | {<prev>prev | <next>next}"];
struct3 [label="<head>hhead[0] | <head1>hhead[1] | ..."];
}
subgraph cluster_b {
label = LRUNode1;
struct4 [label="key"];
struct5 [label="value"];
struct6 [label="link | {<prev>prev | <next>next}"];
struct7 [label="node | {<prev>pprev | <next>next}"];
}
struct2:next->struct6:link
struct2:prev->struct6:link
struct6:next->struct2:dhead
struct6:prev->struct2:dhead
struct3:head->struct7
struct7:next->{NULL[shape=none, fontcolor=black]}
struct7:prev->struct3:head
label="Data structure";
}
```
```graphviz
digraph{
node[shape=record]
rankdir=LR
subgraph cluster_a {
label = LRUCache;
struct3 [label="<head>hhead[0] | <head1>hhead[1] | ..."];
}
subgraph cluster_b {
label = LRUNode1;
struct4 [label="2"];
struct5 [label="2"];
}
struct3:head->struct4
label="lRUCachePut 2"
}
```
```graphviz
digraph{
node[shape=record]
rankdir=LR
subgraph cluster_a {
label = LRUCache;
struct0 [label="<head>hhead[0] | <head1>hhead[1] | ..."];
}
subgraph cluster_b {
label = LRUNode1;
struct1 [label="2"];
struct2 [label="2"];
}
subgraph cluster_c {
label = LRUNode2;
struct3 [label="3"];
struct4 [label="3"];
}
struct0:head->struct1
struct0:head1->struct3
label="lRUCachePut 3"
}
```
```graphviz
digraph{
node[shape=record]
rankdir=LR
subgraph cluster_a {
label = LRUCache;
struct0 [label="<head>hhead[0] | <head1>hhead[1] | ..."];
}
subgraph cluster_b {
label = LRUNode1;
struct1 [label="2"];
struct2 [label="2"];
}
subgraph cluster_c {
label = LRUNode2;
struct3 [label="3"];
struct4 [label="3"];
}
subgraph cluster_d {
label = LRUNode2;
struct5 [label="6"];
struct6 [label="6"];
}
struct0:head->struct5
struct5->struct1
struct0:head1->struct3
label="lRUCachePut 6"
}
```
```graphviz
digraph{
node[shape=record]
rankdir=LR
subgraph cluster_a {
label = LRUCache;
struct0 [label="<head>hhead[0] | <head1>hhead[1] | ..."];
}
subgraph cluster_b {
label = LRUNode1;
struct1 [label="2"];
struct2 [label="2"];
}
subgraph cluster_c {
label = LRUNode2;
struct3 [label="3"];
struct4 [label="3"];
}
subgraph cluster_d {
label = LRUNode2;
struct5 [label="6"];
struct6 [label="6"];
}
struct0:head->struct1
struct1->struct5
struct0:head1->struct3
label="lRUCacheGet 2"
}
```
```graphviz
digraph{
node[shape=record]
rankdir=LR
subgraph cluster_a {
label = LRUCache;
struct0 [label="<head>hhead[0] | <head1>hhead[1] | ..."];
}
subgraph cluster_b {
label = LRUNode1;
struct1 [label="4"];
struct2 [label="4"];
}
subgraph cluster_c {
label = LRUNode2;
struct3 [label="3"];
struct4 [label="3"];
}
subgraph cluster_d {
label = LRUNode2;
struct5 [label="2"];
struct6 [label="2"];
}
struct0:head->struct1
struct1->struct5
struct0:head1->struct3
label="lRUCachePut 4"
}
```
### 測驗三
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
用 binary search 方式找到第一個不為 0 的位元，如果滿足為 0 的情況代表那半邊都是 0，`num` 加上半邊的數量，`word` 再往右移半邊的數量，直到移完
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
```c
#if BITS_PER_LONG == 64
if ((word & 0xFFFFFFFF) == 0) {
num += 32;
word >>= 32;
}
```
`__clear_bit`
* BIT_MASK 作用將除了指定位元外的都清成 0(位元索引從 0 開始)
* BIT_WORLD 回傳指定位元索引加上開始位置
* 與反轉後的 mask 做 and 後指定位元就是 0
```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;
}
```
Sign in with Wallet
