# 2020q1 Homework3 (quiz3)
contribute by < `simpson0114` >
###### tags: `linux2020`

:::danger
列於 [作業區](https://hackmd.io/@sysprog/linux2020-homework3) 的網址應以發布後的瀏覽模式所得的超連結，請注意規範
:notes: jserv
:::

## 測試環境

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"

$ cat /proc/version
Linux version 5.3.0-42-generic (buildd@lcy01-amd64-019) 
(gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1)) 
#34~18.04.1-Ubuntu SMP Fri Feb 28 13:42:26 UTC 2020

## 作業要求
- [x]重新回答第 3 周測驗題
- [ ]解釋上述 XOR linked list 排序實作的原理，並指出其中可改進之處
- [ ]請觀察你的硬體組態 (如 L1 data cache 的容量和行為)，以上述策略實作效率更好的 XOR linked list 排序程式。
- [ ]修改 lab0-c 裡頭的 harness.c，將原本內部使用的 doubly-linked list 換為 XOR linked list，觀察記憶體佔用率的變化
- [ ]解釋程式運作原理、對執行時間的影響 (考慮到 branch predictor 行為)，和指出其實作限制
- [ ]在 Linux 核心找出運用類似的手法的程式碼並解說

## 測驗題
### 測驗`1`
這題主要再探討 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的實作，而題目都位於 `list *sort(list *start)` 這個 function 內，這個 function 主要的功能就是將 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 以及 merge sort 進行遞增順序的排序。

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

可以看到 `if (!right || (left && left->data < right->data))` 代表著要將 left 的放進 merge 中，因此 merge 的新 address 就會是 merge 的 adress XOR left，因此 LL1 的答案就是：
> LL1 = XOR(merge->addr, left)

同時也要將 left 的 address 更新，因此 LL2 的答案為:
> LL2 = merge

至於 `else` 就是將 right 放進 merge 中，而方法與上述相同，因此 RR1 及 RR2 的答案為：
> RR1 = XOR(merge->addr, right)
> RR2 = merge

### 測驗`2`
這題主要是將 single-linked list 的 `insert` 函式改寫的更加簡潔

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

這個 while 迴圈需要不斷重複直到跑完或 newt 的 value 小於 link 的 value ，而且 `*link` 必須用括號包住，否則會變成，`link->data` 的指標，因此 `AA` 的答案為：
> AA = (*link)->data < newt->data

:::warning
自 C99 規格書摘錄 operator 搭配的優先權議題
:notes: jserv
:::

而迴圈內要不斷往 `link` 的 next 跑，所以 BB 的答案為：
> BB = link = &(*link)->next

## XOR linked list 實作原理
XOR linked list 是利用 XOR 的特性將 linked list 透過 address 和 value 進行雙向鏈結。