# 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
* 補完以下程式碼

    #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`

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

    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`
* 實際結果：

            (*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`
* 實際結果：

            (*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`

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` 前的狀態

    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)$

    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)$

    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}$

        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 釋放

    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

    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 的幾個特性

    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 內只有一個元素

    if (!start || !start->addr)
        return start;

* 從變數名稱可以看出接下來可能是要把 Linked list 拆成兩個

    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)$

        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$

        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}$

        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`，遞迴呼叫，因為左邊都只有一個，所以每次的分開應該會長這樣

    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` 來解說

        list *next = left->addr;
        if (next)
            next->addr = XOR(left, next->addr);

        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}$

        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}"];
        }

        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==

        if (!merge) {
            start = merge = left;
            merge->addr = NULL;
        } else {
            merge->addr = LL1;
            left->addr = LL2;
            merge = left;
        }
        left = next;

        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`

    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，合併的概念如下

    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：
> - [ ] 第一題延伸問題
> - [ ] 第二題