# 2023q1 Homework1 (quiz1)
contributed by < [slipet](https://github.com/slipet) >

<details>
<summary><font color=darkred>開發環境</font></summary>

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         48 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12s
  On-line CPU(s) list:   0-11
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 5 5600X 6-Core Processor
    CPU family:          25
    Model:               33
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            0
    Frequency boost:     enabled
    CPU max MHz:         4650.2920
    CPU min MHz:         2200.0000
    BogoMIPS:            7399.79
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr
                          sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good nopl non
                         stop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 sse4_1 s
                         se4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy a
                         bm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_
                         nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba ibrs ibpb stibp vmmcall
                          fsgsbase bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a rdseed adx smap clflushopt clwb sha
                         _ni xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local clz
                         ero irperf xsaveerptr rdpru wbnoinvd arat npt lbrv svm_lock nrip_save tsc_scale vmcb_cle
                         an flushbyasid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif v_spec_ct
                         rl umip pku ospke vaes vpclmulqdq rdpid overflow_recov succor smca fsrm
Virtualization features: 
  Virtualization:        AMD-V
Caches (sum of all):     
  L1d:                   192 KiB (6 instances)
  L1i:                   192 KiB (6 instances)
  L2:                    3 MiB (6 instances)
  L3:                    32 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-11

</details>

## 測驗 1

<details>
<summary>details</summary>

#include <stdint.h>
#include "list.h"

struct item {                         
    uint16_t i;
    struct list_head list;
};

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

static void list_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);
-   struct item *pivot = list_first_entry(head, AAA, BBB);
+   struct item *pivot = list_first_entry(head, item, list);
    list_del(&pivot->list);

    struct item *itm = NULL, *is = NULL;
-   CCC (itm, is, head, list) {
+   list_for_each_entry_safe (itm, is, head, list) { 
        if (cmpint(&itm->i, &pivot->i) < 0)
-           DDD (&itm->list, &list_less);
+           list_move (&itm->list, &list_less);
        else
-           EEE (&itm->list, &list_greater);
+           list_move (&itm->list, &list_greater);
    }

    list_sort(&list_less);
    list_sort(&list_greater);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
-   FFF(&list_greater, head);
+   list_splice_tail(&list_greater, head);
}

</details>

---

首先使用 `INIT_LIST_HEAD` 建立兩個空的鏈結串列 `list_less` 和 `list_greater` ， 所有元素會跟分別跟 pivot 比較，較小的會放入 `list_less`，較大的則會放入 `list_greater`。

digraph G {
    rankdir = LR
    node[shape=record];
    greater [label="greater", style=dashed, color=grey];
    h [label="head", style=dashed, color=grey];
    {
    rank = same
    less [label="less", style=dashed, color=grey];
    }
    subgraph cluster0 {
        4->2->6->1->9;
    }
    h -> 4 [style=dashed, color=grey];
    less -> greater [style=invis];
}

---
接著使用 `list_first_entry(head, type, member)` ，取出第一個元素作為 pivot ， 我們可以從 `list_first_entry(head, type, member)` 的宣告發現，第二個參數為 data type，因此 AAA 為 struct item ，第三個參數為 member name， BBB 為 list 。

digraph G {
    rankdir = LR
    node[shape=record];
    less [label="less", style=dashed, color=grey];
    greater [label="greater", style=dashed, color=grey];    
    {
    rank = same
    h [label="head", style=dashed, color=grey];
    pivot [label="pivot", style=dashed, color=grey];
    }
    subgraph cluster0 {
        2->6->1->9;
    }
    h -> 2 [style=dashed, color=grey];
    pivot -> 4;
    less -> greater [style=invis];
}

---

走訪整個鏈結串列，每個元素都會跟 pivot 比較，分別取出並放入 `list_less` 或 `list_greater` 。我們會需要走訪整個串列並且取出元素，因此 CCC 會是 list_for_each_entry_safe ， 從原本的串列取出並且放入其他串列使用 DDD = EEE = list_move ， 由於整個排序需要是 stable sorting ，因此這邊不能使用 list_move_tail。

走訪鏈結串列後會如下所示：

digraph G {
    rankdir = LR
    node[shape=record];
    less [label="less", style=dashed, color=grey];
    greater [label="greater", style=dashed, color=grey];    
    {
    rank = same
    h [label="head", style=dashed, color=grey];
    pivot [label="pivot", style=dashed, color=grey];
    }
    subgraph cluster0 {
        less -> 2 -> 1 
        1 ->greater [style=invis];
        greater -> 6 -> 9
    }
    pivot -> 4;
}

---

分別對 `list_less` 和 `list_greater` 做 `list_sort` ，以 top-down 的方式分解子問題直到鏈結為空或只剩一個 node 。 最後將排序好的 `list_less` 和 `list_greater` 和 `pivot` 接回 head 。

`list_sort(&list_less)` 和`list_sort(&list_greater)` 已經將 `list_less` 和 `list_greater` 排序完成並回傳：

digraph G {
    rankdir = LR
    node[shape=record];
    less [label="less", style=dashed, color=grey];
    greater [label="greater", style=dashed, color=grey];    
    {
    rank = same
    h [label="head", style=dashed, color=grey];
    pivot [label="pivot", style=dashed, color=grey];
    }
    subgraph cluster0 {
        less -> 1 -> 2
        2 ->greater [style=invis];
        greater -> 6 -> 9
    }
    pivot -> 4;
}

* `list_add(&pivot->list, head)` :

digraph G {
    rankdir = LR
    node[shape=record];
    pivot [label="pivot", style=dashed, color=grey];
    {
    rank = same
    h [label="head", style=dashed, color=grey];
    }
    subgraph cluster0 {
        4
    }
    h -> 4 [style=dashed, color=grey];
    pivot:s -> 4:n [style=dashed, color=grey];
}

* list_splice(&list_less, head)：

digraph G {
    rankdir = LR
    node[shape=record];
    less [label="less", style=dashed, color=grey];
    pivot [label="pivot", style=dashed, color=grey];
    {
    rank = same
    h [label="head", style=dashed, color=grey];
    }
    subgraph cluster0 {
        1->2->4
    }
    h -> 1 [style=dashed, color=grey];
    pivot:s -> 4:n [style=dashed, color=grey];
}

* 接著要把 `list_greater` 插入 pivot 後面，也就是插入 `head` 的尾端，因此這邊使用 `list_splice_tail` 將 `list_greater` 的 nodes 插入 head 的尾端。

digraph G {
    rankdir = LR
    node[shape=record];
    less [label="less", style=dashed, color=grey];
    greater [label="greater", style=dashed, color=grey];    
    pivot [label="pivot", style=dashed, color=grey];
    {
    rank = same
    h [label="head", style=dashed, color=grey];
    }
    subgraph cluster0 {
        1->2->4->6->9
    }
    h -> 1 [style=dashed, color=grey];
    pivot:s -> 4:n [style=dashed, color=grey];
    less -> greater [style=invis];
}

## 測驗 2

<details>
<summary>details</summary>

#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head stack[MAX_DEPTH];
    for (int i = 0; i < MAX_DEPTH; i++)
        INIT_LIST_HEAD(&stack[i]);
    int top = -1;
    list_splice_init(head, &stack[++top]);

    struct list_head partition;
    INIT_LIST_HEAD(&partition);

    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &partition);
        if (!list_empty(&partition) && !list_is_singular(&partition)) {
            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);

            struct item *itm = NULL, *is = NULL;
            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);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);
        } else {
            top++;
            list_splice_tail(&partition, &stack[top]);
            while (top >= 0 && list_is_singular(&stack[top])) {
                struct item *tmp =
                    list_first_entry(&stack[top], struct item, list);
                list_del(&tmp->list);
                INIT_LIST_HEAD(KKKK);
                list_add_tail(&tmp->list, head);
            }
        }
    }
}

</details>

---

使用 `stack[MAX_DEPTH]` 模擬堆疊，一開始時將 `head` 放到 stack[0]:

digraph G {
    rankdir = LR;
    node [shape=record];

    stack [label="<f5>stack[511]|<f4>... ...|<f3>stack[3]|<f2>stack[2]|<f1>stack[1]|<f0>stack[0]"];
    
    subgraph cluster0 {
        rank = same;
        4->2->6->1->9;
    }
    stack:<f0> -> 4 [style=dashed, color=grey];
    
}

---
進入 `while-loop` 後先將第一個元素當作 pivot 取出，接著跟前面一樣跟 pivot 比大小將剩下的元素分別放入 `list_less` 或 `list_greater` ，因此 GGG = `list_for_each_entry_safe` 。

digraph G {
    rankdir = LR
    node[shape=record];
    less [label="less", style=dashed, color=grey];
    greater [label="greater", style=dashed, color=grey];    
    {
    rank = same
    pivot [label="pivot", style=dashed, color=grey];
    }
    subgraph cluster0 {
        less -> 2 -> 1 
        1 ->greater [style=invis];
        greater -> 6 -> 9
    }
    pivot -> 4;
}

---

接著我們會將 pivot 插入 less 的尾端，並且將 `list_less` 和 `list_greater` 分別放回堆疊。 HHHH = `list_move_tail` ， IIII = &stack[++top] ， JJJJ = &stack[++top]

digraph G {
    rankdir = LR;
    node [shape=record];

    stack [label="<f5>stack[511]|<f4>... ...|<f3>stack[3]|<f2>stack[2]|<f1>stack[1]|<f0>stack[0]"];
    6->9;
    2->1->4;
    stack:<f1> -> 2:w [style=dashed, color=grey];
    stack:<f0> -> 6:w [style=dashed, color=grey];
    
}

---
我們不斷分解子問題直到 stack[top] 裡的 list 為空或是只有一個 node 後執行 `else` 的部份:

digraph G {
    rankdir = LR;
    node [shape=record];

    stack [label="<f5>stack[511]|<f4>... ...|<f3>stack[3]|<f2>stack[2]|<f1>stack[1]|<f0>stack[0]"];
    
    6->9;
    stack:<f3> -> 1:w [style=dashed, color=grey];
    stack:<f2> -> 2:w [style=dashed, color=grey];
    stack:<f1> -> 4:w [style=dashed, color=grey];
    stack:<f0> -> 6:w [style=dashed, color=grey];
    
}

在 `else` 裡的 `while-loop` 會不斷的將 stack pop 直到剩下未處理的子問題， pop 出來的 node 最後會插入 head 。 KKKK = &stack[top --] 。

digraph G {
    rankdir = LR;
    node [shape=record];

    stack [label="<f5>stack[511]|<f4>... ...|<f3>stack[3]|<f2>stack[2]|<f1>stack[1]|<f0>stack[0]"];
    h [label="head", style=dashed, color=grey];
    
    6->9;
    stack:<f0> -> 6:w [style=dashed, color=grey];
    
    h->1->2->4;
}

---
我們走訪整個鏈結串列後，對於 pivot 來說，它已經是排序完成的 node ， 因此再次加入 `list_less` 似乎不太合邏輯，會使得它在子問題中不斷被重複的比較。這邊改寫成 `list_splice_tail(&pivot->list, &stack[++top]);` 會比較恰當。

-   list_move_tail (&pivot->list, &list_less);
    if (!list_empty(&list_greater))
        list_splice_tail(&list_greater, IIII);
+   list_move_tail (&pivot->list, &list_less);    

digraph G {
    rankdir = LR;
    node [shape=record];

    stack [label="<f5>stack[511]|<f4>... ...|<f3>stack[3]|<f2>stack[2]|<f1>stack[1]|<f0>stack[0]"];
    6->9;
    2->1;
    stack:<f2> -> 2:w [style=dashed, color=grey];
    stack:<f1> -> 4:w [style=dashed, color=grey];
    stack:<f0> -> 6:w [style=dashed, color=grey];
    
}

## 測驗 3
從說明可以知道要獲得下一個 node 的位置，必須透過本身的位置跟前一個指標的位置做互斥或運算，我們可以從 `address_of` 可以看出來是用 `XOR_COMP` 運算後獲得位置，因為指標本身是不能做 +- 之外的運算的，我們必須要將指標轉型成 `uintptr_t` ，算完的結果再轉回 `xor_node_t *` 。LLL = (uintptr_t)(a) ^ (uintptr_t)(b)。

#define XOR_COMP(a, b) ((xor_node_t *) ((uintptr_t)(a) ^ (uintptr_t)(b)))

static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
    assert(n1 && n2);
    return XOR_COMP(n1, n2);
}

---
從 `xor_node_t` 、 `xor_list_t` 、 `test_node` 的資料結構定義可以得知，在 `main` 中 list 和 test_node 經過初始化過後會如下所示：

digraph list_ele {
    rankdir=LR;
    node[shape=record];
    subgraph cluster_0 {
        label = "test_node" 
        test_node [label="value|{<addr>NULL}", style=bold];
    }
    
    subgraph cluster_1 {
        rank = same
        label = "list" 
        count [label="count=0", style=bold];
        head [label="<head>head |<cmp> cmp", style=bold];
        tail [label="<tail>tail |<cmp> cmp", style=bold];
        head:cmp:e -> tail:tail:w[arrowhead=normal, arrowtail=normal];
        tail:cmp:w -> head:head:e[arrowhead=normal, arrowtail=normal];
        count -> head [style = invis]
    }
    test_node ->count [style = invis]
    
}

---
在 `for-loop` 中會不斷的新增 `test_node` 並且使用 `xorlist_add` 往 `list` 加入新的節點。

當 list 為空時，當我們呼叫 `xorlist_add` 加入節點， `xorlist_add` 中前半段程式碼我們可以如圖所示：

<details>
<summary>details</summary>

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

</details>

digraph list_ele {
    rankdir=LR;
    node[shape=record];
    subgraph cluster_0 {
        label = "xor_node_t" 
        new [label="{<addr>n}|{<cmp>cmp}", style=bold];
    }
    
    subgraph cluster_1 {
        rank = same
        label = "list" 
        
        head [label="<head>head |<cmp> cmp", style=bold];
        tail [label="<tail>tail |<cmp> cmp", style=bold];
        head:cmp:e -> tail:tail:w[arrowhead=normal, arrowtail=normal];
        tail:cmp:w -> head:head:e[arrowhead=normal, arrowtail=normal];
        count [label="count=0", style=bold];
        tail -> count [style = invis]
    }
    n [label="node", style=dashed, color=grey];
    n:e -> tail:tail:n [style=dashed, color=grey];
    
    real_next [label="real_next", style=dashed, color=grey];
    real_next:n->n:s[style = invis]
    
    real_prev [label="real_prev", style=dashed, color=grey];
    real_prev:e -> head:head:w [style=dashed, color=grey];

    real_next:e -> tail:tail:n [style=dashed, color=grey];
    new ->real_next [style = invis]
}

這裡我們可以發現， node 這個變數其實是多餘的， node 在這個函式只有只有用在 `if-else` 而且會等價於 `real_prev->cmp` 。

當我們要往 head 新增一個節點 n 時， `real_prev->cmp = n` 這行會將 `real_prev` 的 cmp 指到 n 也就是 head->cmp 。

digraph list_ele {
    rankdir=LR;
    node[shape=record];
    real_next [label="real_next", style=dashed, color=grey];
    n [label="node", style=dashed, color=grey];
    subgraph cluster_1 {
        rank = same
        label = "list" 
        
        head [label="<head>head |<cmp> cmp", style=bold];
        tail [label="<tail>tail |<cmp> cmp", style=bold];
        new [label="<addr>n |<cmp> cmp", style=bold];
        head:cmp:e -> new:addr:w[arrowhead=normal, arrowtail=normal];
        tail:cmp:w -> head:head:e[arrowhead=normal, arrowtail=normal];
        count [label="count=0", style=bold];
        new -> tail [style = invis]
        tail -> count [style = invis]
    }
    real_next:s -> tail:tail:n [style=dashed, color=grey];
    n:e -> tail:tail:w [style=dashed, color=grey];

    
    real_prev [label="real_prev", style=dashed, color=grey];
    real_prev:e -> head:head:w [style=dashed, color=grey];
    
}

`n->cmp = XOR_COMP(real_prev, real_next)`: 利用 XOR_COMP 計算 n ^ head 得到下一個位置，用 `n->cmp` 只向下一個位置。

digraph list_ele {
    rankdir=LR;
    node[shape=record];
    real_next [label="real_next", style=dashed, color=grey];
    n [label="node", style=dashed, color=grey];
    subgraph cluster_1 {
        rank = same
        label = "list" 
        
        head [label="<head>head |<cmp> cmp", style=bold];
        tail [label="<tail>tail |<cmp> cmp", style=bold];
        new [label="<addr>n |<cmp> cmp", style=bold];
        head:cmp:e -> new:addr:w[arrowhead=normal, arrowtail=normal];
        tail:cmp:w -> head:head:e[arrowhead=normal, arrowtail=normal];
        new:cmp:e -> tail:tail:w[arrowhead=normal, arrowtail=normal]
        count [label="count=0", style=bold];
        new -> tail [style = invis]
        tail -> count [style = invis]
    }
    real_next:s -> tail:tail:n [style=dashed, color=grey];
    n:e -> tail:tail:w [style=dashed, color=grey];
    
    real_prev [label="real_prev", style=dashed, color=grey];
    real_prev:e -> head:head:w [style=dashed, color=grey];
    
}

`real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP))`: 這行是要將 tail 的 cmp 更新成插入的 n ，因此 PPPP = real_next->cmp。

digraph list_ele {
    rankdir=LR;
    node[shape=record];
    real_next [label="real_next", style=dashed, color=grey];
    n [label="node", style=dashed, color=grey];
    subgraph cluster_1 {
        rank = same
        label = "list" 
        
        head [label="<head>head |<cmp> cmp", style=bold];
        tail [label="<tail>tail |<cmp> cmp", style=bold];
        new [label="<addr>n |<cmp> cmp", style=bold];
        head:cmp:e -> new:addr:w[arrowhead=normal, arrowtail=normal];
        
        new:cmp:e -> tail:tail:w[arrowhead=normal, arrowtail=normal]
        count [label="count=0", style=bold];
        new -> tail [style = invis]
        tail -> count [style = invis]
    }
    real_next:s -> tail:tail:n [style=dashed, color=grey];
    n:e -> tail:tail:w [style=dashed, color=grey];
    
    real_prev [label="real_prev", style=dashed, color=grey];
    real_prev:e -> head:head:w [style=dashed, color=grey];
    
    tail:cmp:w -> new:addr:e[arrowhead=normal, arrowtail=normal];
    
}

最後更新 count = 1。

我們可以發現透過跟 prev 或 next 跟一個 cmp 指標做 XOR 運算就可以達到雙向的走訪鏈結串列，大大的減少記憶體的使用，但是缺點可能是程式碼的邏輯可能會變得比較複雜。

<details>
<summary>details</summary>

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 = &list->tail;
    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, real_next->cmp));
    list->count++;

    return 0;
}

</details>

---