# 2020q1 Homework3 (quiz3)
contributed by < `ZhuMon` >
###### tags: `linux2020`
:::danger
`2020q1` 的意思是 2020 年的第 1 季,顯然我們的開學日就在這範圍
:notes: jserv
:::
:::info
原來如此,之後會注意
:::
> [第 3 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz3)
## 測驗 `1`
> 本文皆以 addr(a) 代表 a 的位址, link(a) 代表 a->addr
### 題目
:::spoiler
* 補完以下程式碼
```cpp
#include <stdint.h>
typedef struct __list list;
struct __list {
int data;
struct __list *addr;
};
#define XOR(a, b) ((list *) ((uintptr_t) (a) ^ (uintptr_t) (b)))
void insert_node(list **l, int d) {
list *tmp = malloc(sizeof(list));
tmp->data = d;
if (!(*l)) {
tmp->addr = NULL;
} else {
(*l)->addr = XOR(tmp, (*l)->addr);
tmp->addr = *l;
}
*l = tmp;
}
void delete_list(list *l) {
while (l) {
list *next = l->addr;
if (next)
next->addr = XOR(next->addr, l);
free(l);
l = next;
}
}
list *sort(list *start)
{
if (!start || !start->addr)
return start;
list *left = start, *right = start->addr;
left->addr = NULL;
right->addr = XOR(right->addr, left);
left = sort(left);
right = sort(right);
for (list *merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
list *next = left->addr;
if (next)
next->addr = XOR(left, next->addr);
if (!merge) {
start = merge = left;
merge->addr = NULL;
} else {
merge->addr = LL1;
left->addr = LL2;
merge = left;
}
left = next;
} else {
list *next = right->addr;
if (next)
next->addr = XOR(right, next->addr);
if (!merge) {
start = merge = right;
merge->addr = NULL;
} else {
merge->addr = RR1;
right->addr = RR2;
merge = right;
}
right = next;
}
}
return start;
}
```
:::
## 解析 XOR linked list 運作機制
:::danger
HackMD 內文的縮排 (indention) 深度不要太深,不然難以編輯和檢測語法問題
:notes: jserv
:::
:::info
好的,會再思考一下架構
:::
### `insert_node`
```cpp=11
void insert_node(list **l, int d) {
list *tmp = malloc(sizeof(list));
tmp->data = d;
if (!(*l)) {
tmp->addr = NULL;
} else {
(*l)->addr = XOR(tmp, (*l)->addr);
tmp->addr = *l;
}
*l = tmp;
}
```
* 從 function 名稱可以猜出這個 function 可能是要在 linked list 插入一個 node
* 這個 function 傳入的參數有兩個,一個是 `list **l`,一個是 `int d`
* `*l` 指向的 node 有三種可能
1. linked list 最前面的 node
2. linked list 中間的 node (除了最前面以及最後面的任何 node)
3. linked list 最後面的 node
> 1. 粗略地往下掃過,在 `insert_node()` 中,沒有看到將 `*l` 移動很多步的程式碼( e.g. `while`、`for`),所以可以判定新的 node 會在 `*l` 的旁邊
> 2. 由於 XOR linked list 為變相的 doubly linked list,所以第 1 項與第 3 項是相同的
* `d` 可以從第 13 行 `tmp->data = d` 得知是新 node 的 data
* 接下來思考 if-else 的功用
* 進入第 16 行的條件是 `*l` 為 `NULL`,也就是傳入的 linked list 為空,於是將新增的 node: `tmp` 的 `addr` 設為 `NULL`
* 若是 linked list 不為空,則進入第 18 行
* 從 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 可以知道,每次新增一個 node 必須將 `addr` 指定為前後兩個 node address 的 XOR
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
a [label="{ <data> a | <ref> 0 ⨁ &b }"];
b [label="{ <data> b | <ref> &a ⨁ &c}"];
c [label="{ <data> c | <ref> &b ⨁ 0}"];
}
```
> 以數學描述如下
> $link(a) = 0 \oplus addr(b)$ = addr(b)
> $link(b) = addr(a) \oplus addr(c)$
> $link(c) = addr(b)$
* case 1 : `*l` 指向 `a` (linked list 的第一個 node)
* 預期結果:
* 插入新的 node 到 linked list 的前端
> $link(tmp) = addr(a)$
> $link(a) = addr(tmp) \oplus addr(b)$
> $link(b) = addr(a) \oplus addr(c)$
> $link(c) = addr(b)$
* `*l` 最後會指向 `tmp`
* 實際結果:
```cpp=18
(*l)->addr = XOR(tmp, (*l)->addr);
tmp->addr = *l;
```
* initial
> $link(*l) = link(a) = 0 \oplus addr(b)$ = addr(b)
* ==line 18==
> $\begin{split}
link'(*l) &= addr(tmp) \oplus link(*l) \\
&= addr(tmp) \oplus 0 \oplus addr(b) \\
&= addr(tmp) \oplus addr(b)
\end{split}$
* ==line 19==
> $link(tmp) = addr(*l) = addr(a)$
* `*l = tmp;`
* <span style="color:green">符合設想</span>
* case 2 : `*l` 指向 b (linked list 的中間 node)
* 預期結果:
* 插入新的 node 到 linked list 的中間(b 的前面或後面)
> $link(a) = addr(b)$
> $link(b) = addr(a) \oplus addr(tmp)$
> $link(tmp) = addr(b) \oplus addr(c)$
> $link(c) = addr(tmp)$
or
> $link(a) = addr(tmp)$
> $link(tmp) = addr(a) \oplus addr(tmp)$
> $link(b) = addr(tmp) \oplus addr(c)$
> $link(c) = addr(b)$
* `*l` 指向 `b` 或 `tmp`
* 實際結果:
```cpp=18
(*l)->addr = XOR(tmp, (*l)->addr);
tmp->addr = *l;
```
* initial
> $link(*l) = link(b) = addr(a) \oplus addr(c)$
* ==line 18==
> $\begin{split} link'(*l) &= addr(tmp) \oplus link(*l) \\
&= addr(tmp) \oplus addr(a) \oplus addr(c)
\end{split}$
* ==line 19==
> $link(tmp) = addr(*l) = addr(b)$
* <span style="color:red">與設想不同</span>
* case 3
* 可視為 case 1 的 reverse
* 結論
* `insert_node` 會在 linked list 插入一個 node,視傳入的 `*l` 位置為何
* 若是傳入的 `*l` 為第一個,則在前面插入;若是最後一個,則在最後插入
* 最後會將 `*l` 指向新 node
### `delete_list`
```cpp=24
void delete_list(list *l) {
while (l) {
list *next = l->addr;
if (next)
next->addr = XOR(next->addr, l);
free(l);
l = next;
}
}
```
* 從字面上可以猜到這個 function 用來將整個 linked list 刪除
* 若傳入的 linked list : `l` 存在,才進入 `while`
* 要在 XOR linked list 中移動,必須使用以下特性
* $A \oplus 0 = A$
* $A \oplus A = 0$
* 將自己存放的 data 與前一個 node 的 address 作 XOR,可以得到下一個 node
* 進入 `while` 前的狀態
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
l -> a
a [label="{ <data> a | <ref> &b }"];
b [label="{ <data> b | <ref> &a ⨁ &c}"];
c [label="{ <data> c | <ref> &b}"];
}
```
> 以 addr(a) 代表 a 的位址, link(a) 代表 a->addr
> $link(a) = addr(b)$
> $link(b) = addr(a) \oplus addr(c)$
> $link(c) = addr(b)$
* 進入 `while` 後,會由一個指標 `next` 存放 $link(l)$
```cpp=26
list *next = l->addr;
if (next)
next->addr = XOR(next->addr, l);
free(l);
l = next;
```
> $next = link(l)$
> 若 `l` 指向 `a`
> >$link(l) = link(a)$
>
> $next = link(a) = addr(b)$
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
l -> a;
next -> b:data;
a [label="{ <data> a | <ref> &b }"];
b [label="{ <data> b | <ref> &a ⨁ &c}"];
c [label="{ <data> c | <ref> &b}"];
}
```
* `next` 存在,進入 ==line 28==
> $\begin{split}
> link'(next) &= link(next) \oplus addr(l) \\
> &= link(addr(b)) \oplus addr(a) \\
> &= link(b) \oplus addr(a) \\
> &= (addr(a) \oplus addr(c)) \oplus addr(a) \\
> &= (addr(a) \oplus addr(a)) \oplus addr(c) \\
> &= 0 \oplus addr(c) \\
> &= addr(c)
> \end{split}$
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
l -> a;
a [label="{ <data> a | <ref> &b }"];
b [label="{ <data> b | <ref> &c}"];
next -> b:data;
c [label="{ <data> c | <ref> &b}"];
}
```
可以發現 `if` 裡,會將 `next` 指向的 node 的 link 設為下一個 node 的 address
* ==line 29== 將 `l` 指向的 node 釋放
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
l;
b [label="{ <data> b | <ref> &c}"];
next -> b:data;
c [label="{ <data> c | <ref> &b}"];
}
```
* ==line 30== 將 `l` 指向 `next` 指向的 node
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
l -> b;
b [label="{ <data> b | <ref> &c}"];
next -> b;
c [label="{ <data> c | <ref> &b}"];
}
```
* 以此類推,會將整個 linked list 走完,並釋放
### XOR Linked List 特性
從前面兩個 function 可以歸納出 XOR Linked List 的幾個特性
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
a [label="{ <data> a | <ref> &b }"];
b [label="{ <data> b | <ref> &a ⨁ &c}"];
c [label="{ <data> c | <ref> &b ⨁ &d}"];
d [label="{ <data> d | <ref> &c }"];
}
```
1. 第一個 node 和最後一個 node 存放的 link 都是該 node 的前一個 node 的 address
2. XOR Linked List 是一個雙向 Linked List,且可以藉由同樣步驟從第一個或最後一個走完整個 List
3. 在中間的 node 想要移動,需要有上一個 node 的 address
### 解題思路
* 一開始 `if` 內判斷傳入的 `start` 是否存在,以及是否超過一個以上的元素
> 可參照 `insert_node()`
> 若 `start->addr` 為 `NULL`,則代表 list 內只有一個元素
```cpp=36
if (!start || !start->addr)
return start;
```
* 從變數名稱可以看出接下來可能是要把 Linked list 拆成兩個
```cpp=39
list *left = start, *right = start->addr;
left->addr = NULL;
right->addr = XOR(right->addr, left);
```
* 用看的可能一時無法知道接下來程式碼的用途,所以試著用數學運算
> 以下為已知
> $link(a) = addr(b)$
> $link(b) = addr(a) \oplus addr(c)$
> $link(c) = addr(b)$
* ==line 39== 設定 pointer
> $left = addr(a), right = link(a) = addr(b)$
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
left -> a;
a [label="{ <data> a | <ref> &b}"];
right -> b;
b [label="{ <data> b | <ref> &a ⨁ &c}"];
c [label="{ <data> c | <ref> &b}"];
}
```
因為第一個以及最後一個 node 所存放的 link 都是其旁邊的 node address,所以 `right` 可以輕易地藉由 `start->addr` 得到第二個 node address
* ==line 40~41== 斷開 Linked list
> $link'(left) = addr(a) = NULL$
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
left -> a;
a [label="{ <data> a | <ref> NULL}"];
right -> b;
b [label="{ <data> b | <ref> &a ⨁ &c}"];
c [label="{ <data> c | <ref> &b}"];
}
```
> $\begin{split}link'(right) &= link(right) \oplus addr(left) \\
> &= link(b) \oplus addr(a) \\
> &= (addr(a) \oplus addr(c)) \oplus addr(a) \\
> &= addr(c)
> \end{split}$
```graphviz
digraph linked_list{
rankdir=UD;
node [shape=record];
left -> a;
a [label="{ <data> a | <ref> NULL}"];
right -> b;
b [label="{ <data> b | <ref> &c}"];
c [label="{ <data> c | <ref> &b}"];
}
```
* 接下來分別將 `left`、`right` 丟進 `sort`,遞迴呼叫,因為左邊都只有一個,所以每次的分開應該會長這樣
```graphviz
graph tree{
rankdir=UD;
node [shape=record];
a1 [label="a | b | c | ..."];
a1 -- b1;
a1 -- b2;
b1 [label="a"];
b2 [label="b|c| ..."];
b2 -- c1;
b2 -- c2;
c1 [label="b"];
c2 [label="c| ..."];
}
```
* 進入重頭戲: `for`
* ==line 48~50== 和 ==line 62~64== 可以一起看,又因為 `left` 經過遞迴呼叫後,都只會剩下一個 node,所以 ==line 49== 的 `if` 根本不會進入,是以 `right` 來解說
```cpp=48
list *next = left->addr;
if (next)
next->addr = XOR(left, next->addr);
```
```cpp=62
list *next = right->addr;
if (next)
next->addr = XOR(right, next->addr);
```
> $next = link(right)$
> $\begin{split}link'(next) &= addr(right) \oplus link(next) \\
> &= addr(a) \oplus addr(a) \oplus addr(c) \\
> &= addr(c)
> \end{split}$
```graphviz
digraph linked_list {
rankdir=UD;
node [shape=record];
right -> a;
a [label="{<data> a | <ref> &b}"];
next -> b;
next -> c [style=invis];
b [label="{<data> b | <ref> &a ⨁ &c}"];
c [label="{ <data> c | <ref> &b}"];
}
```
```graphviz
digraph linked_list {
rankdir=UD;
node [shape=record];
right -> a;
a [label="{<data> a | <ref> &b}"];
next -> b;
next -> c [style=invis];
b [label="{<data> b | <ref> &c}"];
c [label="{ <data> c | <ref> &b}"];
}
```
這三行將 `next` 指向 `right` 隔壁的 node,若直接取用 `right->addr` 當作下一個 node 的 address ,`right` 必定為最前面的 node 或是 link 存放下一個 node 的 address,所以
* 終於要來解題了,==line 52~60== 和 ==line66~74== 是對稱的,所以也可以一起看。
* 這裡第一個 `if` 限制 `merge` 為 `NULL` 時才能進入,掃過整個 `for` ,並沒有看到將 `merge` 重設為 `NULL`,也就是說只有第一次進入才有可能進入第一個 `if`
> 只有將 `merge` 設為 `left`, `left` 為 `NULL` 又不可能進入 ==line 48==
```cpp=52
if (!merge) {
start = merge = left;
merge->addr = NULL;
} else {
merge->addr = LL1;
left->addr = LL2;
merge = left;
}
left = next;
```
```cpp=66
if (!merge) {
start = merge = right;
merge->addr = NULL;
} else {
merge->addr = RR1;
right->addr = RR2;
merge = right;
}
right = next;
```
* 假設第一次進入 `for` 是進入 ==line 66== 的 `else`。
* 進入 ==line 67==,將 `start` 和 `merge` 都設為 `right` 所指向的 node,並且斷掉與其他 node 的連結,然後 `right` 指向 `next`
```graphviz
digraph linked_list {
rankdir=UD;
node [shape=record];
left -> a;
a [label="{<data> a | <ref> NULL}"];
#a -> right [style=invis];
right -> b [style=dashed];
b [label="{<data> b | <ref> NULL}"];
right -> c;
next -> d [style=invis];
start -> b;
merge -> b;
next -> c;
c [label="{<data> c | <ref> &d}"]
d [label="{<data> d | <ref> &c}"];
}
```
* 假設第二次的 `for` 是 `a->data < c->data`,也就是說會進入 ==line 48==,將 Linked list 分開後,應該要合起來,所以應該要想辦法將 `left` 接到 `merge` 或 `start` 後面
* ==line 56== 更動的是 `merge->addr`,也就是說 `LL1` 要存放上一個(`NULL`)的位址以及下一個(`left`)的位址的 XOR
* 由於要進行推廣,所以上一個 node 的位址不能設為 `NULL`
* 要得到上一個 node 的位址可以直接拿 `merge` 的 link,因為正常的 XOR Linked list 最後一個 node 的 link 一定是上一個 node 的 address
* 因此
:::success
`LL1 = XOR(merge->addr, left)`
:::
* ==line 57== 更動的是 `left->addr`,可以從上圖看到此時 `left->addr` 為 `NULL`,由於 `left` 即將成為最後一個 node,所以必定存放上一個 node 的 address,也就是 `merge`
:::success
`LL2 = merge`
:::
* ==line 58== 將 `merge` 向前移動
* 因為對稱,所以 `LL3` 和 `LL4` 可以此類推
:::success
`LL3 = XOR(merge->addr, right)`
:::
:::success
`LL4 = merge`
:::
* 最後將 `start` 回傳,合併 Linked List,合併的概念如下
```graphviz
digraph tree{
rankdir=UD;
node [shape=record];
b1;
a1 [label="2"];
a2 [label="1"];
a1 -> b1;
a2 -> b1;
b2 [label="3"];
b1 [label="1 | 2"];
b1 -> c1;
b2 -> c1;
c1 [label="1 | 2 | 3"];
c2 [label="4"];
c1 -> d1;
c2 -> d1;
d1 [label=" 1 | 2 | 3 | 4"]
}
```
* 也就是一個 Insertion Sort
---
## 測驗 `2`
> TODO:
> - [ ] 第一題延伸問題
> - [ ] 第二題