# 2023q1 Homework1 (quiz1)
contributed by < `SPFishcool` >

## 測驗一

### 運作原理
此為快速排序法，其程式碼分析如下：
- 程式開始時宣告兩個 `list_head` 為 `list_less` 與 `list_greater`，兩者為快速排序時依照 `pivot` 分類其他節點加到這兩條 linked list 上。

    //initial two heads
    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    //list_add "less" or "greater" by comparsion
    if (cmpint(&itm->i, &pivot->i) < 0)
        list_add (&itm->list, &list_less);
    else
        list_add (&itm->list, &list_greater);

- `pivot` 為 linked list 的第一個節點，取出後從原來的 list 上移除。

    struct item *pivot = list_first_entry(head, AAA, BBB);
    list_del(&pivot->list);

- 分類完後會分成兩條分別以 `list_less` 與 `list_greater` 為 head 的 linked list，接者對兩條 list 再進行快速排序，排序完最後將依照 `list_less` -> `pivot` -> `list_greater` 將原本的 list 接在一起。

    //do sort 
    list_sort(&list_less);
    list_sort(&list_greater);
    // merge this node
    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);

### 改進方案

### hybrid sort

## 測驗二

### 運作原理

此為「非遞迴」Quick Sort，原理是運用堆疊儲存每一次 partition 後的狀態。

    struct list_head stack[MAX_DEPTH];
    for (int i = 0; i < MAX_DEPTH; i++)
        INIT_LIST_HEAD(&stack[i]);

一開始會將原始 linked list 存入堆疊最底下

    int top = -1;
    list_splice_init(head, &stack[++top]);

用 `top` 來記錄目前堆疊高度，迴圈一開始會初始化 `partition` 並將目前 `top` 高度的 linked list 取出

        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &partition);

並與遞迴一樣，初始化 `list_greater` 、 `list_less`，取第一個數值當作 `pivot`

    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);
    struct item *pivot =
        list_first_entry(&partition, struct item, list);
    list_del(&pivot->list);
    INIT_LIST_HEAD(&pivot->list);

接下來將 `partition` 的節點依照大小分類至 `list_greater` 、 `list_less`

    GGGG (itm, is, &partition, list) {
        list_del(&itm->list);
        if (cmpint(&itm->i, &pivot->i) < 0)
            list_move(&itm->list, &list_less);
        else
            list_move(&itm->list, &list_greater);
    }

    HHHH (&pivot->list, &list_less);

上列 `GGGG` 應該是要將每個節點的值取出，除了 container 和 list 還有兩個變數，所以 `GGGG` 應該填 `list_for_each_safe`

`HHHH` 函式內是一個 node 和一個 list，`list_less` 內的節點是比 `pivot` 還小的節點，因此如果要將 `pivot` 加入 `list_less` 應該加在後面，所以 `HHHH` 為 `list_move_tail`。

    if (!list_empty(&list_greater))
        list_splice_tail(&list_greater, IIII);
    if (!list_empty(&list_less))
        list_splice_tail(&list_less, JJJJ);

接下來上述 `IIII`、`JJJJ` 與 `stack` 有關，由此可猜測這兩行是要將 `list_greater` 、 `list_less` 放入 `stack`，目前 `top` 是記錄到存放 list 的最高層，所以應該往上存入，因此 `IIII` 和 `JJJJ` 應為 `&stack[++top]` (`list_splice_tail` 內部要放 pointer)。
### 效能比較

### 改進方案

### Intro Sort

## 測驗三

此為一個 XOR list 的實作程式碼，其 function 的實作原理與 linux 的 [list.h](https://github.com/SPFishcool/lab0-c/blob/master/list.h) 相似，只是其鏈結原理不一樣。

XOR list 只有一個 pointer，其 pointer 並不是真的指到一個 node 的所在位址，而是兩個 node 位址做 XOR 運算的結果，藉由 XOR 的特性（`a ^ (a ^ b)` = `b`），只要知道兩個相鄰的 node，就可以藉由 XOR 運算指到這條 linked list 的所有 node。

在測驗三的程式裡，`XOR_COMP` 就是將兩個 pointer 作 XOR 運算的 function。

#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))

要將 pointer 做運算，必須先將 type 轉變為 `uintptr_t`，所以 `LLLL` 應為 `(uintptr_t) a ^ (uintptr_t) b`。

接下來 XOR list 有三個 `struct`： `xor_node_t` 、 `xor_list_t` 、 `test_node`

- `_xorlist_node` 裡存的是 `*cmp`，就是前面提到的 pointer。

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    cmp [label="cmp"];
}

- `_xor_list_struct` 是整條 list 的 head，裡面存有 `count` 、`head` 、 `tail`，其中 `head` 和 `tail` 是分別指向 list 第一個和最後一個的 `_xorlist_node` 結構，並不是儲存 XOR 運算的結果。

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    subgraph cluster_0 {
        count [label="{count}"];
        head [label="{head}|{<cmp>cmp}"];
        tail [label="{tail}|{<cmp>cmp}"];
        label=xor_list_t
    } 
}

- `test_node` 則是 `_xorlist_node` 的 container

digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    subgraph cluster_0 {
        value [label="{value}"];
        cmp [label="{xornode}|{<cmp>cmp}"];
        label=test_node;
    } 
}

知道了 XOR list 的運算原理，最後來看 `xorlist_add`

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    if (node == &list->tail)
        real_next = MMMM;
    else
        real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
    list->count++;

    return 0;
}

程式裡 `real_next` 從第 8 行可以知道它一直指向 head，而 node 指向 `head->cmp` 所指，也就是 list 的第一個元素，若 list 沒有任何元素 `head->cmp` 會指向 `tail`，而 `tail->cmp` 也會指向 `head`，因此 `MMMM` 為 list 沒有任何元素時，`real_next` 應指向 `&tail_next`

    digraph list {
        rankdir=LR;
        node[shape=record, style=bold];
        subgraph cluster_0 {
            count [label="{count = 0}"];
            {rank=same; count}
            head [label="{head}|{<cmp>cmp}"];
            {rank=same; head}
            tail [label="{tail}|{<cmp>cmp}"];
            {rank=same; tail}
            label=list
        }
        head:cmp -> tail:w
        tail:cmp -> head:e
    }

接下來將 `n` 加入這個 list 的第一個位址，第 14、15 行先將 `real_prev->cmp` (`head` 的 `cmp`) 指向 `n`， `n->cmp` 設為 `head` $\oplus$ `prev_next`

第 16 行可以假設一下：
- 目前第一個元素（假設是 `a`）的 `cmp` 可能為 `head` $\oplus$ `b` ，今天我們要插入元素 `c`
- 已經把 `head->cmp = c` 、 `c->cmp = head ^ a`
- 最後要重設 `a->cmp`，原本的值會是 `head` $\oplus$ `b`，意思是 prev 為 `head`，next 為 `b`
- `c` 插進來後要將 `a->cmp` 改成 `c` $\oplus$ `b`，首先可以先 `real_prev` (`head`) $\oplus$ `a->cmp`，這樣做 `head` 就會消去只剩下 `b`
- 最後 `c` $\oplus$ `a->cmp` 就完成了

因此 `PPPP` 會是 `real_next->cmp`。

    digraph list {
        rankdir=LR;
        node[shape=record, style=bold];
        subgraph cluster_0 {
            count [label="{count = 1}"];
            {rank=same; count}
            head [label="{head}|{<cmp>cmp}"];
            {rank=same; head}
            tail [label="{tail}|{<cmp>cmp}"];
            {rank=same; tail}
            label=list
        }
        cmp [label="{C}|{<cmp>A ⊕ B}"];
        n[shape=plaintext]
        node_[shape=plaintext]
        real_prev[shape=plaintext]
        real_next[shape=plaintext]
        head:cmp -> cmp
        tail:cmp -> cmp
        real_prev -> head
        node_ -> tail
        real_next -> tail
        n -> cmp 
    }