owned this note
owned this note
Published
Linked with GitHub
# 2024q1 Homework2 (quiz1+2)
contributed by < `fatcatorange` >
# 第一周測驗題：
## 測驗一
在以下程式嗎中，應是要取得串列的尾端指標，因此此處透過 while 迴圈逐個向後，直到串列尾端，故 `AAAA` 應為 `(*left)->next`
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
同樣的，在`BBBB` 中，要求的是整個佇列的長度，因此同樣為 `(*left)->next`
接下來分析 quick_sort 的函式：
首先，初始時 begin[0] 為串列開頭，end[0] 則為串列尾端。
在每一輪開始時，將 pivot 設定 begin[i]，並由 pivot 的下一元素開始執行：
```c
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;
```
接下來，程式開始由pivot的下個元素開始，逐一比對當前節點的 value 值是否比 pivot 大，若是則加入 right（將該節點設為 right 的頭，並連接原本的 right head），否則加入 left 。
因此，此處 `CCCC` 應為 p->next。
之後就是將 left 和 right 加入陣列中，此處 begin[i] 為left，而 end[i] 會是這個部份的尾端，因此應為 list_tail(left)，而 begin[i+1]、end[i+1] 放入的是pivot， begin[i+2] 放入 right，尾端則同樣放入 list_tail(right)。
```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);
```
到這裡，已經將原本的 list 切成三部份：
begin[i] ~ end[i]:比 pivot 小的部份
begin[i+1] ~ end[i+1]:pivot 自己一個點
begin[i+2] ~ end[i+2]:比 pivot 大的部份
到下一輪時，會由 begin[i+2] 和 end[i+2] 開始一樣步驟，假設此時
begin[i+2] != end[i+2]: 重做剛才的步驟，再切成三等份
否則的話，代表這部份只剩下一個節點或零個節點：
若為一個節點，將該節點加入結果
然後將 i-- ，代表這個部份做完了
由於每次切割後都是 i+=2，也就是針對比 pivot 大的部份進行動作，因此最早被加進 result 的必定是最大的，而下個被加入的是第二大的，又因為每次插入都是插在頭節點前面，因此最後結果就會是一由小至大排序好的串列。
## 測驗二
測試程式碼：
`create_sample`: 創建一個鍊結串列，內容隨機。
`copy_list`: 創見一個 from 為開頭的串列的複製，並放入 space 陣列中
:::info
此處 space 是一個陣列，內容是一堆 element_t ，因此 space 指標才能直接進行 ++ 操作
:::
`compare`: 回傳兩節點內值的大小差距，並把 priv 指標內的值 +1。
`check_list`: 透過 `list_for_each_entry_safe` 巨集檢查所有節點是否有按照順序排列，因為此巨集會有一個 safe 指標會在每一輪先更新成 entry 的 next ，因此透過 safe 可以直接當成是 entry 的下一個節點。
此函式會檢查 3 項事項：
1. 是否按照順序排列，可透過檢查 entry 和 safe 節點的值得知
2. 是否為 stable (假如原本有兩個 1，以 1 和 **1**代表，若原本順序事先 1 才是 **1**，排序後不能變成先 **1** 才 1)，可以透過檢查 seq 得知，若後面的點 seq 比前面的節點的 seq 還大，代表並不是 stable。
>目前沒有找到 seq 第一次是在哪裡定義，其含意應是元素原始的出現順序
3. 節點數是否和原先串列的節點數相同。
接下來為 timsort 的程式碼部份：
首先，創建一個 head 指標，並且在一開始將 tail 指向 head 的位址，因此 AAAA 應為：
```c
&head
```
接下來，此處會透過指標的指標操作，先比較 a, b 兩節點的值，若 a 較小或相等，代表目前應該插入的是 a ，因此將執行 `*tail = a`，可參考下圖(省略部份未用到的節點內容)，假設初始有a, b 指標和 tail 指向 head 的位址：
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
alist_1 [label="{list_node_a1| next: list_head*\l |val:int = 1}", style=filled, fillcolor=lightblue];
alist_2 [label="{list_node_a2| next: list_head*\l |val:int = 3}", style=filled, fillcolor=lightblue];
alist_3 [label="{list_node_a3| next: list_head*\l |val:int = 5}", style=filled, fillcolor=lightblue];
a->alist_1->alist_2->alist_3
blist_1 [label="{list_node_b1| next: list_head*\l |val:int = 2}", style=filled, fillcolor=lightblue];
blist_2 [label="{list_node_b2| next: list_head*\l |val:int = 4}", style=filled, fillcolor=lightblue];
blist_3 [label="{list_node_b3| next: list_head*\l |val:int = 6}", style=filled, fillcolor=lightblue];
b->blist_1->blist_2->blist_3
tail->head
}
```
當 a->val 比 b->val 小時，先將 tail 指向的指標改為指向 a，在第一次時就是 head，因此變為：
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
alist_1 [label="{list_node_a1| next: list_head*\l| val:int = 1}", style=filled, fillcolor=lightblue];
alist_2 [label="{list_node_a2| next: list_head*\l| val:int = 3}", style=filled, fillcolor=lightblue];
alist_3 [label="{list_node_a3| next: list_head*\l| val:int = 5}", style=filled, fillcolor=lightblue];
a->alist_1->alist_2->alist_3
blist_1 [label="{list_node_b1| next: list_head*\l| val:int = 2}", style=filled, fillcolor=lightblue];
blist_2 [label="{list_node_b2| next: list_head*\l| val:int = 4}", style=filled, fillcolor=lightblue];
blist_3 [label="{list_node_b3| next: list_head*\l| val:int = 6}", style=filled, fillcolor=lightblue];
b->blist_1->blist_2->blist_3
tail->head->alist_1
}
```
接下來，改將 tail 指向 a->next 的指標，並將 a 改為 a->next，也就是改為：
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
alist_1 [label="{list_head_a1| <next>next: list_head*\l | val:int = 1}", style=filled, fillcolor=lightblue];
alist_2 [label="{list_head_a2| next: list_head*\l |val:int = 3}", style=filled, fillcolor=lightblue];
alist_3 [label="{list_head_a3| next: list_head*\l |val:int = 5}", style=filled, fillcolor=lightblue];
a->alist_2
alist_1->alist_2
blist_1 [label="{list_head_b1| next: list_head*\l |val:int = 2}", style=filled, fillcolor=lightblue];
blist_2 [label="{list_head_b2| next: list_head*\l |val:int = 4}", style=filled, fillcolor=lightblue];
blist_3 [label="{list_head_b3| next: list_head*\l |val:int = 6}", style=filled, fillcolor=lightblue];
b->blist_1->blist_2->blist_3
tail->alist_1:next[label = "指向 a1->next 的位址"]
}
```
:::info
此處的 tail 並非指向 list_head_a1 ，而是 list_head_a1 的 next 指標的位址，這樣等一下要進行插入時，可以直接修改 next 指標指向的位址。
:::
下一輪因為 b 指向的 b1 的值比 a 指向的 a2 的值小，因此是要插入 b1 的節點，這時可以透過修改 tail 指向的指標(也就是 a1 的 next)來達成，也就是變為：
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
alist_1 [label="{list_head_a1| next: list_head*\l| val:int = 1}", style=filled, fillcolor=lightblue];
alist_2 [label="{list_head_a2| next: list_head*\l| val:int = 3}", style=filled, fillcolor=lightblue];
alist_3 [label="{list_head_a3| next: list_head*\l| val:int = 5}", style=filled, fillcolor=lightblue];
a->alist_2->alist_3
alist_1->blist_1
blist_1 [label="{list_head_b1| next: list_head*\l| val:int = 2}", style=filled, fillcolor=lightblue];
blist_2 [label="{list_head_b2| next: list_head*\l| val:int = 4}", style=filled, fillcolor=lightblue];
blist_3 [label="{list_head_b3| next: list_head*\l| val:int = 6}", style=filled, fillcolor=lightblue];
b->blist_1->blist_2->blist_3
tail->alist_1
}
```
然後和前面一樣，tail 改為指向 b->next 指標的位址，並把 b 改為 b->next ， 因此會變成：
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
alist_1 [label="{list_head_a1| next: list_head*\l val:int = 1}", style=filled, fillcolor=lightblue];
alist_2 [label="{list_head_a2| next: list_head*\l val:int = 3}", style=filled, fillcolor=lightblue];
alist_3 [label="{list_head_a3| next: list_head*\l val:int = 5}", style=filled, fillcolor=lightblue];
a->alist_2->alist_3
alist_1->blist_1
blist_1 [label="{list_head_b1| <next> next: list_head*\l| val:int = 2}", style=filled, fillcolor=lightblue];
blist_2 [label="{list_head_b2| next: list_head*\l| val:int = 4}", style=filled, fillcolor=lightblue];
blist_3 [label="{list_head_b3| next: list_head*\l| val:int = 6}", style=filled, fillcolor=lightblue];
b->blist_2->blist_3
tail->blist_1:next[label="指向 b1->next的指標"]
}
```
依照這個步驟持續下去，最後就可以完成 merge
> 此處最值得注意的就是 merge 是透過指標的指標直接修改了目前 tail 節點的 next 指標指向的位址，因此就不需要額外配置空間。
因此， BBBB 應為 &(a->next)， CCCC 則為 &(b->next)
接下來， build_prev_link 將 list 串列接上 tail，因此程式開始時先將 tail->next = list
接下來，將list->prev 接上 tail，並且將 list 和 tail 往前，直到 list 為 NULL。
最後必須結束時 list 為 NULL，而 tail 會是最後一個節點，將 tail->next 接到 head，並將 head->prev 接到 tail 形成環狀鏈結串列。
DDDD 為 tail->next
EEEE 為 head->prev
list->prev = tail?
`merge_final`:將 a, b 兩串列 merge，每輪將較小的節點連接至要回傳的串列，如果 a 的節點先用盡，會用 `build_prev_link` 來連接剩下的 b 串列的節點，否則將 b 指標改為 a 後再做 `build_prev_link`
例如此情況 a 的節點已經用盡:
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
alist_1 [label="{list_head_a1| next: list_head*\l val:int = 1}", style=filled, fillcolor=lightblue];
head->alist_1
tail->alist_1
a->NULL
blist_1 [label="{list_head_b1| next: list_head*\l val:int = 2}", style=filled, fillcolor=lightblue];
blist_2 [label="{list_head_b2| next: list_head*\l val:int = 4}", style=filled, fillcolor=lightblue];
blist_3 [label="{list_head_b3| next: list_head*\l val:int = 6}", style=filled, fillcolor=lightblue];
blist_1->blist_2->blist_3
b->blist_1
}
```
則會將 b 串列和 head, tail 進行 `build_prev_link`
而如果是 b 串列先耗盡:
```graphviz
digraph QueueRelationships {
node [shape=record, fontname="Arial"];
// Define the queue context, which manages individual queues
alist_1 [label="{list_head_a1| next: list_head*\l val:int = 1}", style=filled, fillcolor=lightblue];
alist_2 [label="{list_head_a1| next: list_head*\l val:int = 7}", style=filled, fillcolor=lightblue];
alist_3 [label="{list_head_a1| next: list_head*\l val:int = 9}", style=filled, fillcolor=lightblue];
head->alist_1
tail->alist_1
a->alist_2->alist_3
blist_1 [label="{list_head_b1| next: list_head*\l val:int = 2}", style=filled, fillcolor=lightblue];
blist_2 [label="{list_head_b2| next: list_head*\l val:int = 4}", style=filled, fillcolor=lightblue];
blist_3 [label="{list_head_b3| next: list_head*\l val:int = 6}", style=filled, fillcolor=lightblue];
blist_1->blist_2->blist_3
alist_1->blist_1
b->alist_2
}
```
由於 b 也已經改成指向串列 a ，因此可以同樣透過
` build_prev_link(head, tail, b);`來完成串接後面的節點。
## find_run
在此函式中目標是要找出一組 run ，而其回傳值是一個 struct，內容包含該 run 的開頭和結尾。
例如，假設有以下節點，初始狀態為(藍色代表指標）：
```graphviz
digraph structs {
node[shape=record]
prev [label= "{prev}",style=filled,fillcolor=lightblue];
list [label= "{list}",style=filled,fillcolor=lightblue];
head [label= "head",style=filled,fillcolor=lightblue]
next [label= "next",style=filled,fillcolor=lightblue]
struct1 [label="<prev> prev|<data> data:6|<next> next"];
struct2 [label="<prev> prev|<data> data:4|<next> next"];
struct3 [label="<prev> prev|<data> data:5|<next> next"];
struct4 [label="<prev> prev|<data> data:7|<next> next"];
list->struct1
head->struct1
next->struct2
prev->NULL
struct1:next->struct2
struct2:prev->struct1
struct2:next->struct3
struct3:prev->struct2
struct3:next->struct4
struct4:prev->struct3
}
```
接下來就會檢查 list->data 和 next->data，這裡的狀況是 list 的值較大，因此會執行：
```c
len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;
```
執行上述步驟後，會變為以下狀況：
```graphviz
digraph structs {
node[shape=record]
prev [label= "{prev}",style=filled,fillcolor=lightblue];
list [label= "{list}",style=filled,fillcolor=lightblue];
head [label= "head",style=filled,fillcolor=lightblue]
next [label= "next",style=filled,fillcolor=lightblue]
struct1 [label="<prev> prev|<data> data:6|<next> next"];
struct2 [label="<prev> prev|<data> data:4|<next> next"];
struct3 [label="<prev> prev|<data> data:5|<next> next"];
struct4 [label="<prev> prev|<data> data:7|<next> next"];
list->struct2
head->struct1
next->struct3
prev->struct1
struct1:next->NULL
struct2:prev->struct1
struct2:next->struct3
struct3:prev->struct2
struct3:next->struct4
struct4:prev->struct3
}
```
接下來會檢查 list->data 是否仍大於 list->data 若是則繼續重複執行，否則跳離迴圈
這裡的範例已經不符合，因此離開迴圈，而離開後會在將 prev->next 設為 list，因此結果為：
```graphviz
digraph structs {
node[shape=record]
prev [label= "{prev}",style=filled,fillcolor=lightblue];
list [label= "{list}",style=filled,fillcolor=lightblue];
head [label= "head",style=filled,fillcolor=lightblue]
next [label= "next",style=filled,fillcolor=lightblue]
struct1 [label="<prev> prev|<data> data:6|<next> next"];
struct2 [label="<prev> prev|<data> data:4|<next> next"];
struct3 [label="<prev> prev|<data> data:5|<next> next"];
struct4 [label="<prev> prev|<data> data:7|<next> next"];
list->struct2
head->struct1
next->struct3
prev->struct1
struct1:next->NULL
struct2:prev->struct1
struct2:next->struct1
struct3:prev->struct2
struct3:next->struct4
struct4:prev->struct3
}
```
若單純只看 next 指標，程式已經成功找出了一組 run:
```graphviz
digraph structs {
node[shape=record]
struct1 [label="<prev> prev|<data> data:6|<next> next"];
struct2 [label="<prev> prev|<data> data:4|<next> next"];
struct1:next->NULL
struct2:next->struct1
}
```
而未設定好的 prev 指標則可在後續 merge 時透過`build_prev_link`設定，可以發現這麼做之後還會把 new 的節點反轉過來。
考慮另一情況，就是一開始 list->data <= next->data 時：
```graphviz
digraph structs {
node[shape=record]
prev [label= "{prev}",style=filled,fillcolor=lightblue];
list [label= "{list}",style=filled,fillcolor=lightblue];
head [label= "head",style=filled,fillcolor=lightblue]
next [label= "next",style=filled,fillcolor=lightblue]
struct1 [label="<prev> prev|<data> data:1|<next> next"];
struct2 [label="<prev> prev|<data> data:2|<next> next"];
struct3 [label="<prev> prev|<data> data:5|<next> next"];
struct4 [label="<prev> prev|<data> data:7|<next> next"];
list->struct1
head->struct1
next->struct2
prev->NULL
struct1:next->struct2
struct2:prev->struct1
struct2:next->struct3
struct3:prev->struct2
struct3:next->struct4
struct4:prev->struct3
}
```
此時，程式執行以下程式碼一輪後會是：
```c
do {
len++;
list = next;
next = list->next;
} while (next && cmp(priv, list, next) <= 0);
list->next = NULL;
```
```graphviz
digraph structs {
node[shape=record]
prev [label= "{prev}",style=filled,fillcolor=lightblue];
list [label= "{list}",style=filled,fillcolor=lightblue];
head [label= "head",style=filled,fillcolor=lightblue]
next [label= "next",style=filled,fillcolor=lightblue]
struct1 [label="<prev> prev|<data> data:1|<next> next"];
struct2 [label="<prev> prev|<data> data:2|<next> next"];
struct3 [label="<prev> prev|<data> data:5|<next> next"];
struct4 [label="<prev> prev|<data> data:7|<next> next"];
list->struct2
head->struct1
next->struct3
prev->NULL
struct1:next->struct2
struct2:prev->struct1
struct2:next->struct3
struct3:prev->struct2
struct3:next->struct4
struct4:prev->struct3
}
```
實際上，就是不需要做特別的事，因為原本就是按照順序的了，因此串列最後的狀況就會是
```graphviz
digraph structs {
node[shape=record]
prev [label= "{prev}",style=filled,fillcolor=lightblue];
list [label= "{list}",style=filled,fillcolor=lightblue];
head [label= "head",style=filled,fillcolor=lightblue]
next [label= "next",style=filled,fillcolor=lightblue]
struct1 [label="<prev> prev|<data> data:1|<next> next"];
struct2 [label="<prev> prev|<data> data:2|<next> next"];
struct3 [label="<prev> prev|<data> data:5|<next> next"];
struct4 [label="<prev> prev|<data> data:7|<next> next"];
list->struct4
head->struct1
next->NULL
prev->NULL
struct1:next->struct2
struct2:prev->struct1
struct2:next->struct3
struct3:prev->struct2
struct3:next->struct4
struct4:prev->struct3
}
```
不管是何種情況，最後要把 head 的 prev 改為 NULL 來切斷與前面的連接，並在最前面接上一個開頭`head->next->prev = (struct list_head *) len;`，最後將 head, next 回傳即可。
### timsort
有了前面那些函式，可以開始分析 timsort，首先，函式透過迴圈不斷找出 run ，當 run 數量達成一定條件（還在看...)時會先進行合併。
```c
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);
```
接下來，透過 `merge_force_collapse` 合併所有 run。
最後，因為剛才接上的可能有些是在 find_run 中的狀況一，其 prev 節點未設定好，透過 build_prev_link 調整好。
:::warning
後面的一些程式碼目前只能看懂大致架構..
:::
# 第二週測驗
## 測驗一
### list_add_head:
首先，此串列的結構應如下：
```graphviz
digraph structs {
node[shape=record]
head [label="h|<first> first",style="filled",fillcolor = "lightblue"];
struct1 [label="<prev> pprev|<data> data:6|<next> next"];
struct2 [label="<prev> pprev|<data> data:4|<next> next"];
struct3 [label="<prev> pprev|<data> data:5|<next> next"];
struct4 [label="<prev> pprev|<data> data:7|<next> next"];
struct1:next->struct2
struct1:prev->head:first
struct2:prev->struct1:next
struct2:next->struct3
struct3:prev->struct2:next
n->struct4
head:first->struct1
}
```
假設要把 n 指向的節點插入此串列的開頭，可以透過修改目前第一個節點的 pprev 指標，因為這個指標指向的是 h 的 first 指標，透過指標的指標可以直接修改，也就是改為指向 n 指向的節點的 next 指標的位址
```graphviz
digraph structs {
node[shape=record]
head [label="h|<first> first",style="filled",fillcolor = "lightblue"];
struct1 [label="<prev> pprev|<data> data:6|<next> next"];
struct2 [label="<prev> pprev|<data> data:4|<next> next"];
struct3 [label="<prev> pprev|<data> data:5|<next> next"];
struct4 [label="<prev> pprev|<data> data:7|<next> next"];
struct1:next->struct2
struct1:prev->struct4:next
struct2:prev->struct1:next
struct2:next->struct3
struct3:prev->struct2:next
n->struct4
head:first->struct1
}
```
接下來必須讓 n 指向的節點的 next 指標指向原本的第一個節點，並將 n 指向的節點的 pprev 指標指向為 h->first 的位址，並把 h->first 改為指向 n 指向的節點，也就是：
```graphviz
digraph structs {
node[shape=record]
head [label="h|<first> first",style="filled",fillcolor = "lightblue"];
struct1 [label="<prev> pprev|<data> data:6|<next> next"];
struct2 [label="<prev> pprev|<data> data:4|<next> next"];
struct3 [label="<prev> pprev|<data> data:5|<next> next"];
struct4 [label="<prev> pprev|<data> data:7|<next> next"];
struct1:next->struct2
struct1:prev->struct4:next
struct2:prev->struct1:next
struct2:next->struct3
struct3:prev->struct2:next
struct4:prev->head:first
struct4:next->struct1
n->struct4
head:first->struct4
}
```
這樣就完成了插入頭的行為，因此 `AAAA`應為 h->first。
### find：
~~首先，函式會先針對整個串列進行遍歷，根據 `hlist_for_each` 巨集， BBBB 的內容應為此串列的 head，因此應為 heads~~
傳入的 heads 應為一個包含多個 head 節點的陣列，因此 BBBB 應為 &(heads[hash])，代表到那個 bucket 去找是否存在資料。
在每一輪，函式創建一個 order_node pointer，由此處可知 CCCC 應為 list_entry。
此處是在檢查是否在指定的串列中找到該數，若有則回傳 index，否則回傳 1。
### node_add:
此函式用於將值插入某個 bucket，首先先分配一塊節點空間，接下來根據其值算出應該插在哪一個 bucket 後即可透過 node_add_head 插入，概念和前個函式相似， DDDD 應為 &(heads[hash])
## 測驗二
### hlist_del:
在此函式中要刪除特定的節點，因此透過修改 pprev 這個指標指向的位置來達成，具體如下，假設要刪除紅色節點：
```graphviz
digraph structs {
node[shape=record]
head [label="h|<first> first",style="filled",fillcolor = "lightblue"];
struct1 [label="<prev> pprev|<data> data:6|<next> next"];
struct2 [label="<prev> pprev|<data> data:4|<next> next"style="filled",fillcolor = "red"];
struct3 [label="<prev> pprev|<data> data:5|<next> next"];
struct4 [label="<prev> pprev|<data> data:7|<next> next"];
struct1:next->struct2
struct1:prev->struct4:next
struct2:prev->struct1:next
struct2:next->struct3
struct3:prev->struct2:next
struct4:prev->head:first
struct4:next->struct1
n->struct2
head:first->struct4
}
```
透過以下操作，串列變成：
```c
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
```
```graphviz
digraph structs {
node[shape=record]
head [label="h|<first> first",style="filled",fillcolor = "lightblue"];
struct1 [label="<prev> pprev|<data> data:6|<next> next"];
struct2 [label="<prev> pprev|<data> data:4|<next> next"style="filled",fillcolor = "red"];
struct3 [label="<prev> pprev|<data> data:5|<next> next"];
struct4 [label="<prev> pprev|<data> data:7|<next> next"];
struct1:next->struct3
struct1:prev->struct4:next
struct2:next->struct3
struct3:prev->struct2:next
struct4:prev->head:first
struct4:next->struct1
next->struct3
n->struct2
pprev->struct3:prev
head:first->struct4
}
```
接下來只要透過再修改 next 指標的 pprev 的指標改為指向 pprev，就可以完成移除該節點的操作：
```graphviz
digraph structs {
node[shape=record]
head [label="h|<first> first",style="filled",fillcolor = "lightblue"];
struct1 [label="<prev> pprev|<data> data:6|<next> next"];
struct2 [label="<prev> pprev|<data> data:4|<next> next"style="filled",fillcolor = "red"];
struct3 [label="<prev> pprev|<data> data:5|<next> next"];
struct4 [label="<prev> pprev|<data> data:7|<next> next"];
struct1:next->struct3
struct1:prev->struct4:next
struct2:next->struct3
struct3:prev->struct1:next
struct4:prev->head:first
struct4:next->struct1
next->struct3
head:first->struct4
}
```
因此， EEEE 應填入 next->pprev。
### LRUCacheFree:
此處在把 cache 內的節點釋放，因為其透過 list_for_each_safe 巨集，且 pos, n 為 list_head 型態的指標，因此 FFFF 的 member_name 應為 link。
而在刪除節點時，是要傳入該節點的 link 部份的指標，實際上就是 pos 指標，因此 GGGG 應為 pos。
### LRUCacheGet:
此處在抓取 cache 內某個節點並將其移動至最前面，因此 HHHH 部份應為 node，因為目前是在遍歷 hlist 而不是普通的 list 。
接下來就可以透過 list_move 來把 pos 指向的節點移動到前面
```c
void lRUCacheFree(LRUCache *obj)
{
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, node);
list_del(pos);
free(cache);
}
free(obj);
}
```
:::info
部份待補
:::
## 測驗三
巨集`__const_hweight8(w)`：
```c
#define __const_hweight8(w) \
((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
(!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
(!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
(!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))
```
這個巨集主要在計算共有多少個 bit 被設定成 1，首先假如有一個值 200，那麼他的二進位表示法為：
```
11001000
```
假設我們對這個數字進行
```c
(!!((w) & (1ULL << 0)))
```
相當於不進行左移，而其結果就是 200 & 1 的結果，那其實就是看：
```
11001000
00000001
--------
00000000
```
也就是看最後一位元是否為 1 ，此處是否，因此回傳 0 。
至於`!!`的用意，以另一個例子來看，如 (!!((w) & (1ULL << 3)))
```
11001000
00001000
--------
00001000
```
這時會回傳結果 8 ，但不能直接把 8 加上去，因此首先透過 ！ 符號，當結果 > 0 時就會變為 0 ，否則變為 1。
因此， !! 符號的用意為：
```
!!8->!0->1
```
也就是當結果 > 0 時變 1 ，否則不變。
因此，做 8 次就是取前８位元不為０的 bit 數。
而 `__const_hweight16` 實際上就是做兩次，但第一次做前 8 位元，第二次做後 8 位元。
後面也都相同，例如 `__const_hweight32` 就做兩次 `__const_hweight16`
`__const_hweight64(w)` 就做兩次 `__const_hweight32`
__ffs 主要功能就是找到第一個不為 1 的在第幾位，因為概念類似，此處假設只有 8-bit
```c
if ((word & 0xff) == 0) {
num += 8;
word >>= 8;
}
```
假如對 10010000 做這個操作：
```
num = 0
10010000
11111111
--------
10010000
```
此處不為 0 ，因此繼續往下：
```c
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
```
```
num = 0
10010000
00001111
--------
00000000
```
此處為答案為 0 ，因此執行 if 內的行為後繼續往下：
```c
if ((word & 0x3) == 0) {
num += 2;
word >>= 2;
}
```
```
num = 4
00001001
00000011
--------
00000001
```
此處不為 0 ，因此繼續往下：
```c
if ((word & 0x1) == 0)
num += 1;
```
```
num = 4
00001001
00000001
--------
00000001
```
仍不為 0 ，中止條件，因此答案為 4
由上述規律，可判斷 AAAA 為 0xffffffff
## __clear_bit
這個函式在清掉 index nr 的 bit， 首先 BIT_MASK(nr) 巨集將返回一個值，其 bit 除了 nr 外皆為 0，例如：
```
BIT_MASK(5)
->000...00100000
```
因此，透過 *p &= ~mask 即可完成 clear_bit，例如：
```
nr = 5
*addr = 11110111
```
其mask:
```
00100000
```
而 *addr & ~mask 即為：
```
11010111
```
因此， BBBB 應為 ~mask。
## fns
這個函式是尋找第 n 個 set bit，概念其實比較簡單，例如假如要找第 2 個：
```
11010011
```
先透過 ffs 找到第一個，之後把這個 bit 用 clear_bit 清掉
```
11010010
```
之後再找一次 ffs 就是答案，假如要找第 n 個，就是做 n-1 次 ffs和 clear_bit 後，再做一次 ffs 的結果就是答案。
Sign in with Wallet
