# [2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 3 週測驗題
###### tags: `linux2020`

:::info
目的: 檢驗學員對 **[linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list)**, **[bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)**, **[指標操作](https://hackmd.io/@sysprog/c-pointer)** 的認知
:::

==[作答表單](https://forms.gle/puNw7kvhDwtzhwcV9)==

---

### 測驗 `1`

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

在 `__list` 結構體內雖僅有一個 `struct __list *addr` 指標型態的物件，但卻可實作雙向的 linked list，就是憑藉著上述的實作技巧。[XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的優勢很顯著，對空間的佔用更為精簡:

隨著資料處理量的增長，效益更明顯:

與尋常作法相比，佔用的儲存空間比值會趨近 $67\%$。

接著我們嘗試撰寫針對 [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);

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

請補完上述排序程式碼。

==作答區==

LL1 = ?
* `(a)` `right`
* `(b)` `left`
* `(c)` `merge`
* `(d)` `XOR(merge, left)`
* `(e)` `XOR(merge, right)`
* `(f)` `XOR(merge, left->addr)`
* `(g)` `XOR(merge, right->addr)`
* `(h)` `XOR(merge->addr, left)`
* `(i)` `XOR(merge->addr, right)`

LL2 = ?
* `(a)` `right`
* `(b)` `left`
* `(c)` `merge`
* `(d)` `XOR(merge, left)`
* `(e)` `XOR(merge, right)`
* `(f)` `XOR(merge, left->addr)`
* `(g)` `XOR(merge, right->addr)`
* `(h)` `XOR(merge->addr, left)`
* `(i)` `XOR(merge->addr, right)`

RR1 = ?
* `(a)` `right`
* `(b)` `left`
* `(c)` `merge`
* `(d)` `XOR(merge, left)`
* `(e)` `XOR(merge, right)`
* `(f)` `XOR(merge, left->addr)`
* `(g)` `XOR(merge, right->addr)`
* `(h)` `XOR(merge->addr, left)`
* `(i)` `XOR(merge->addr, right)`

RR2 = ?
* `(a)` `right`
* `(b)` `left`
* `(c)` `merge`
* `(d)` `XOR(merge, left)`
* `(e)` `XOR(merge, right)`
* `(f)` `XOR(merge, left->addr)`
* `(g)` `XOR(merge, right->addr)`
* `(h)` `XOR(merge->addr, left)`
* `(i)` `XOR(merge->addr, right)`

:::success
延伸問題:

1. 解釋上述 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 排序實作的原理，並指出其中可改進之處;
2. 在 Wikipedia 關於合併排序的詞目中，談及 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)，我們可知道一種最佳化策略是：在子序列大小達到 $S$ 時就不再繼續分割，此時這個 $S$ 為可完整放進處理器 cache 中的元素數量。每個大小為 $S$ 的子序列，都透過適用於小規模 in-place (即不需要額外配置記憶體) 排序演算法（如插入排序或泡沫排序）進行排序，以減少在記憶體內交換特定區域的次數。在小型子序列排序完畢後，再以典型的遞迴型合併排序完剩下的部份。
若可找到一個恰當的 $S$， 便能有效的同時利用到插入排序和合併排序的優點，並減少原始的合併排序當中 locality 不好的影響。請觀察你的硬體組態 (如 L1 data cache 的容量和行為)，以上述策略實作效率更好的 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 排序程式。過程中應該充分量化數據並進行視覺化處理。
3. 修改 [lab0-c](https://github.com/sysprog21/lab0-c) 裡頭的 [harness.c](https://github.com/sysprog21/lab0-c/blob/master/harness.c)，將原本內部使用的 doubly-linked list 換為 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list)，觀察記憶體佔用率的變化，可設計頻繁的 `test_malloc` / `test_free` 呼叫交錯情境。
:::

---

### 測驗 `2`

考慮以下 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)
        BB;
    newt->next = *link;
    *link = newt;
}

請補完程式碼。

==作答區==

AA = ?
* `(a)` `(link)->data < newt->data`
* `(b)` `*link->data < newt->data`
* `(c)` `(*link)->data < newt->data`
* `(d)` `**link->data < newt->data`

BB = ?
* `(a)` `link = &(*link)->next`
* `(b)` `*link = *link->next`
* `(c)` `(*link) = (*link)->next`
* `(d)` `link = (*link)->next`

:::success
延伸問題:
1. 解釋程式運作原理、對執行時間的影響 (考慮到 [branch predictor](https://en.wikipedia.org/wiki/Branch_predictor) 行為)，和指出其實作限制;
2. 在 Linux 核心找出運用類似的手法的程式碼並解說
* 提示: 可參見 [bfq_insert](https://elixir.bootlin.com/linux/v4.15/source/block/bfq-wf2q.c#L373) 和 [rb_link_node](https://elixir.bootlin.com/linux/v4.15/source/include/linux/rbtree.h#L105) 操作 [red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 的手法
:::

---