# quiz3

:::danger
回頭看 ==[作業要求](https://hackmd.io/@sysprog/linux2020-homework3)==，共筆書寫格式有規範！
快去改。
:notes: jserv
:::

XOR 運算特性:
* $A \oplus A = 0$
* $A \oplus 0 = A$
* $A \oplus 1 = \neg A$
* $(A \oplus B) \oplus B = A$

以下程式碼是個 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的實作，在這樣的資料結構可表示為:

       1    2    3    4
data  HAT  CAT  EAT  BAT
link   2    2    6    3

要往下一格移動時，我們需要前一格在哪和這一格的位置。例如我們現在在 `HAT` (1), 已知前一格是 (0)，那麼下一格就是 `link(1) XOR 0` = `2 XOR 0` = 2，也就是 `CAT`。繼續，現在位於 `CAT` (2)，前一格在 (1)，於是下一格就是 `link(2) XOR 1` = `2 XOR 1` = 3，亦即 `EAT`，依此類推。只要當找出來的下一格是 (0) 就結束。

#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;
    }
}

insert: tail 的 addr 所紀錄的是前一個 element 的 address ，head 紀錄的addr是下一個位置，因為把在 head 前面的位置設 NULL 轉成 uintptr_t 為 0， 在下次 insert 的時候，才可以做前一個 element 的 address 與新的 element address 做 XOR

例如：

digraph xor_linked_list {
 rankdir=LR;
 node [shape=record];
 a [label="{ <data> 1 | <ref> 2}",width=1.2]
 b [label="{ <data> 2 | <ref> 1 XOR 3}",width=1.2];
 c [label="{ <data> 3 | <ref> 2 XOR 4}",width=1.2];
 d [label="{ <data> 4 | <ref> 3}",width=1.2];
 a:ref:c -> b:data [arrowhead=vee, dir=both];
 b -> a:ref [arrowhead=vee,dir=both];
 b:ref -> c:data [arrowhead=vee, dir=both];
 c -> b:ref [arrowhead=vee,dir=both];
 c:ref -> d:data [arrowhead=vee, dir=both];
 d -> c:ref [arrowhead=vee,dir=both];
}

address 4 是最新加入的 element 所以他的 addr 紀錄的是前一個的位置
下次再做 insert 時 4->addr = 4->addr(3) XOR 5

delete: 從 tail 開始刪除，每次把最後一個 element 的 addr 更新為前一個的位置

例如：
(1)

digraph xor_linked_list {
 rankdir=LR;
 node [shape=record];
 a [label="{ <data> 1 | <ref> 2}",width=1.2]
 b [label="{ <data> 2 | <ref> 1 XOR 3}",width=1.2];
 c [label="{ <data> 3 | <ref> 2 XOR 4}",width=1.2];
 d [label="{ <data> 4 | <ref> 3}",width=1.2];
 a:ref:c -> b:data [arrowhead=vee, dir=both];
 b -> a:ref [arrowhead=vee,dir=both];
 b:ref -> c:data [arrowhead=vee, dir=both];
 c -> b:ref [arrowhead=vee,dir=both];
 c:ref -> d:data [arrowhead=vee, dir=both];
 d -> c:ref [arrowhead=vee,dir=both];
}

(2)

digraph xor_linked_list {
 rankdir=LR;
 node [shape=record];
 a [label="{ <data> 1 | <ref> 2}",width=1.2]
 b [label="{ <data> 2 | <ref> 1 XOR 3}",width=1.2];
 c [label="{ <data> 3 | <ref> 2 }",width=1.2];
 d [label="{ <data> free | <ref> free}",width=1.2];
 a:ref:c -> b:data [arrowhead=vee, dir=both];
 b -> a:ref [arrowhead=vee,dir=both];
 b:ref -> c:data [arrowhead=vee, dir=both];
 c -> b:ref [arrowhead=vee,dir=both];
 c:ref -> d:data [arrowhead=vee, dir=both];
}

## 測驗一

接著我們嘗試撰寫針對 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的排序程式，採用遞增順序:

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);
    // 紀錄下一個位置 (等於變成 head )

    left = sort(left);
    right = sort(right);
    //切完 全部變一個一個 然後做 merge
    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);
//把left的下一個的 addr 變成下下個位置(等於把下一個變成 head)
            if (!merge) {//第一次
                start = merge = left;
                merge->addr = NULL;
            } else {
                merge->addr = LL1;
                // XOR(merge->addr,left)
                left->addr = LL2;
                //merge
                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;
                //XOR(merge->addr, right)
                right->addr = RR2;
                //merge
                merge = right;
            }
            right = next;
        }
    }

    return start;
}

## 解題思路

### LL1 = ?

這裡要從 left 那取一個到 merge 的 xor linked list 所以做一個 上述的 insert

merge->addr = XOR(merge->addr,left)

### LL2 = ?

接續上一步的 insert 把 addr 變成前一個位置(因為 xor linked list 最後的 addr 是前一個位置)

### RR1 = ?
同上述，情況變成 right
### RR2 = ?
同上述，情況變成 right

## 測驗二
考慮以下 singly-linked list 程式:

#include <stddef.h>
struct node {
    int data;
    struct node *next;
} *head;

void insert(struct node *newt) {
    struct node *node = head, *prev = NULL;
    while (node != NULL && node->data < newt->data) {
        prev = node;
        node = node->next;
    }
    newt->next = node;
    if (prev == NULL)
        head = newt;
    else
        prev->next = newt;
}

可透過以下 pointer to pointer 改寫 `insert` 函式，功能等價但更簡潔，如下:

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && AA)//(*link)->data < newt->data
        BB;//link = &(*link)->next
    newt->next = *link;
    *link = newt;
}

## 解題思路

### AA = ?

需要判斷 node 裡面的資料大小，這裡 link 為 pointer to pointer to node 型態，*link 是 pointer to node ， 要取 data 的話為 (*link)->data

### BB = ?

link 所指的位址要做更新，思路上為把 link 指向下一個位置， link = &((*link)->next) ，一開始覺得是 (*link) = (*link)->next 但是 *link 其實是 *node 存著 head ，這樣會把 head 指到的位置給改掉