# 2023q1 Homework1 (quiz1)
[quiz1](https://hackmd.io/@sysprog/linux2023-quiz1)
## 測驗 1
### 解釋上述程式碼運作原理
初始狀態：
```graphviz
digraph {
rankdir=LR
head[shape=none]
head -> 4 -> 1 -> 3 -> 5 -> 2 -> 7
}
```
Step 0, `head` list 進入 `list_sort`，初始化 `list_less` 和 `list_greater`。
```c
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
```graphviz
digraph {
rankdir=LR
head, list_less, list_greater[shape=none]
head -> 4 -> 1 -> 3 -> 5 -> 2 -> 7
list_less
list_greater
}
```
Step 1, 從 `head` 移出第一個節點設為 `pivot`。
```c
struct item *pivot = list_first_entry(head, struct item, list);
list_del(&pivot->list);
```
```graphviz
digraph {
rankdir=LR
head, pivot, list_less, list_greater[shape=none]
head -> 1 -> 3 -> 5 -> 2 -> 7
pivot -> 4
list_less
list_greater
}
```
Step 2, 遍歷所有節點，並和 `pivot` 比較大小分別放到 `list_greater` 和 `list_less` list
```c
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
list_move_tail (&itm->list, &list_less);
else
list_move_tail (&itm->list, &list_greater);
}
```
```graphviz
digraph {
rankdir=LR
head, pivot, list_less, list_greater[shape=none]
head
pivot -> 4
list_less -> 1 -> 3 -> 2
list_greater -> 5 -> 7
}
```
Step 3, 把 `list_greater` 和 `list_less` 作為 `list_sort` 的參數 recursive 執行 Step 0 至 2。返回的是已排序完成的 `list_greater` 和 `list_less` 。
```c
list_sort(&list_less);
list_sort(&list_greater);
```
```graphviz
digraph {
rankdir=LR
head, pivot, list_less, list_greater[shape=none]
head
pivot -> 4
list_less -> 1 -> 2 -> 3
list_greater -> 5 -> 7
}
```
Step 4, 把 `pivot` 接回 `head`；然後把 `list_less` 接回 `head` 的開頭；最後把 `list_greater` 接回 `head` 的尾部。排序完成。
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
```
```graphviz
digraph {
rankdir=LR
head, pivot, list_less, list_greater[shape=none]
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 7
pivot -> 4
list_less -> 1
list_greater -> 5
}
```
### 針對 Quick sort 提出上述程式碼的改進方案並實作
Quick sort 的 worst-case 是 $O(n^2)$。可以使用 Hybrid sort 採用截長補短的策略，融合兩項或更多排序演算法，這樣的案例包含 Timsort 和 Introsort。
## 測驗 2
### 解釋上方程式碼運作原理，指出設計和實作的缺失
程式碼用了 Divide and Conquer 策略進行排序；並且用一個 `stack` 陣列摸擬和取代了 recursive 的 function call stack。
初始狀態：
```graphviz
digraph {
rankdir=LR
head[shape=none]
head -> 4 -> 1 -> 3 -> 5 -> 2 -> 7
}
```
變數初始化：
```c
struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
INIT_LIST_HEAD(&stack[i]);
int top = -1;
list_splice_init(head, &stack[++top]);
struct list_head partition;
INIT_LIST_HEAD(&partition);
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
4 -> 1 -> 3 -> 5 -> 2 -> 7
stack:f0 -> 4
}
head[shape=none]
partition[shape=none]
top[shape=none label="top = 0"]
}
```
進入 while 迴圈，把 `stack` 把最後一個 list 指派給 `partition`：
```c
while (top >= 0) {
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
}
head[shape=none]
partition[shape=none]
partition -> 4 -> 1 -> 3 -> 5 -> 2 -> 7
top[shape=none label="top = -1"]
}
```
`partition` 長度大於 1，進入 Divide 分支，分出 `list_less` 和 `list_greater` lists：
```c
if (!list_empty(&partition) && !list_is_singular(&partition)) {
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe(itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
}
head[shape=none]
partition,pivot,list_less,list_greater[shape=none]
partition
pivot -> 4
list_less -> 1 -> 3 -> 2
list_greater -> 5 -> 7
top[shape=none label="top = -1"]
}
```
把 `list_less` 和 `list_greater` lists 放到 `stack` 陣列：
```c
list_move_tail (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, &stack[++top]);
if (!list_empty(&list_less))
list_splice_tail(&list_less, &stack[++top]);
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
1 -> 3 -> 2 -> 4
5 -> 7
stack:f0 -> 5
stack:f1 -> 1
}
head[shape=none]
partition[shape=none]
top[shape=none, label="top = 1"]
}
```
從 `stack` 取出最後一個 list 指派給 `partition` 再進行 Divide：
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
}
head[shape=none]
partition[shape=none]
partition -> 1 -> 3 -> 2 -> 4
top[shape=none, label="top = 0"]
}
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
}
head[shape=none]
partition,pivot,list_less,list_greater[shape=none]
partition
pivot -> 1
list_less
list_greater -> 3 -> 4 -> 2
top[shape=none, label="top = 0"]
}
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
1
3 -> 4 -> 2
stack:f0 -> 5
stack:f1 -> 3
stack:f2 -> 1
}
head[shape=none]
top[shape=none, label="top = 2"]
}
```
再從 `stack` 取出最後一個 list 指派給 `partition`：
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
3 -> 4 -> 2
stack:f0 -> 5
stack:f1 -> 3
}
head[shape=none]
partition[shape=none]
partition -> 1
top[shape=none, label="top = 1"]
}
```
當 `partition` 的長度少於等於 1 時，便進入 Conquer 分支。把 `partition` 放回 `stack`。再從 `stack` 的尾端把連續的長度少於等於 1 的 list 接回 `head`。
```c
} else {
top++;
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp =
list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(&stack[top--]);
list_add_tail(&tmp->list, head);
}
}
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
3 -> 4 -> 2
stack:f0 -> 5
stack:f1 -> 3
}
head[shape=none]
partition[shape=none]
top[shape=none, label="top = 1"]
head -> 1
}
```
繼續從 `stack` 取出最後一個 list 指派給 `partition` 再進行 Divide：
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
}
head[shape=none]
partition[shape=none]
top[shape=none, label="top = 0"]
partition -> 3 -> 4 -> 2
head -> 1
}
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
}
head[shape=none]
partition,pivot,list_less,list_greater[shape=none]
head -> 1
partition
pivot -> 3
list_less -> 2
list_greater -> 4
top[shape=none, label="top = 0"]
}
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
stack:f1 -> 4
stack:f2 -> 2 -> 3
}
head[shape=none]
top[shape=none, label="top = 2"]
head -> 1
}
```
繼續從 `stack` 取出最後一個 list 指派給 `partition` 再進行 Divide：
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
stack:f1 -> 4
stack:f2
}
head[shape=none]
partition[shape=none]
top[shape=none, label="top = 1"]
partition -> 2 -> 3
head -> 1
}
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
stack:f1 -> 4
stack:f2
}
head[shape=none]
partition,pivot,list_less,list_greater[shape=none]
head -> 1
partition
pivot -> 2
list_less
list_greater -> 3
top[shape=none, label="top = 1"]
}
```
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f3>3|..."]
}
5 -> 7
stack:f0 -> 5
stack:f1 -> 4
stack:f2 -> 3
stack:f3 -> 2
}
head[shape=none]
top[shape=none, label="top = 3"]
head -> 1
}
```
繼續從 `stack` 取出最後一個 list 指派給 `partition`：
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
stack:f1 -> 4
stack:f2 -> 3
}
head[shape=none]
partition[shape=none]
top[shape=none, label="top = 2"]
partition -> 2
head -> 1
}
```
當 `partition` 的長度少於等於 1 時，便進入 Conquer 分支。把 `partition` 放回 `stack`。再從 `stack` 的尾端把連續的長度少於等於 1 的 list 接回 `head`。
```graphviz
digraph {
rankdir=LR
subgraph cluster0 {
rankdir=LR
peripheries=0
subgraph cluster_stack {
label="stack"
peripheries=0
stack [shape="record"]
stack [label="<f0>0|<f1>1|<f2>2|<f2>..."]
}
5 -> 7
stack:f0 -> 5
}
head[shape=none]
partition[shape=none]
top[shape=none, label="top = 0"]
head -> 1 -> 2 -> 3 -> 4
}
```
繼續上述 Divide and Conquer 操作，直至 `stack` 為空 (top < 0) 時，便返回排序好的 `head` list。
### 提出效能改進方案，特別是避免依賴 MAX_DEPTH
採用 linked list 取代 stack 陣例，便可不需要 MAX_DEPTH。
## 測驗 3
### 解釋上述程式碼運作原理，指出其實作缺陷並改進
```graphviz
digraph {
subgraph cluster_p {
label="prev"
peripheries=0
p [shape="record"]
p [label="{<f0>value|<f1>*cmp}"]
}
subgraph cluster_c {
label="n"
peripheries=0
c [shape="record"]
c [label="{<f0>value|<f1>*cmp}"]
}
subgraph cluster_n {
label="next"
peripheries=0
n [shape="record"]
n [label="{<f0>value|<f1>*cmp}"]
}
}
```
注意看，節點的 `xor_node_t *cmp` 指標並沒有指向任何節點，只是用來記錄前後節點記憶體位址 XOR 後的值。
```c
n.xornode->cmp = XOR_COMP(&prev.xornode, &next.xornode);
````
根據 $(A \oplus B) \oplus B = A$ 特性。`next` 和 `prev` 便可透過以下方式取得。
```c
container_of(next, struct test_node, XOR_COMP(n.xornode->cmp, &prev.xornode));
container_of(prev, struct test_node, XOR_COMP(n.xornode->cmp, &next.xornode))
```
因為可以透過以上方式找到前和後的節點，所以 XOR linked list 可以實作出 doubly linked list。
Sign in with Wallet
Connect another wallet