---
# System prepended metadata

title: 2023q1 Homework1 (quiz1)
tags: [linux2023]

---

---
tags: linux2023
---

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


## 開發環境

```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5599.85
```

## 測驗一

**延伸問題**
- [ ] 解釋程式碼運作原理
- [ ] 針對 [Quick sort](https://en.wikipedia.org/wiki/Quicksort) 提出程式碼的改進方案並實作
- [ ] 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
- [ ] ==BONUS==: 嘗試對 Linux 核心提出排序程式碼改進的貢獻

<s>快速排序法原本並不是一個 stable sort ，而是 unstable sort</s>
根據 [Wikipedia](https://en.wikipedia.org/wiki/Quicksort)，一般常見的 quicksort 並不是 stable sort，例如 [Lomuto partition scheme](https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme)，[Hoare partition scheme](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme)，但是也可以透過進行 [out-of-place](https://en.wikipedia.org/wiki/In-place_algorithm)，進行 stable 版本的 quick sort 實作，與一般需要 $O(nlogn)$ 空間複雜度的 in-place 版本不同，out-of-place 需要 $O(n)$ 的空間來儲存資訊，文中也提到可以透過 linked list 實作 stable sort 版本的 quick sort，但是此時是否有 [random access](https://en.wikipedia.org/wiki/Random_access) 就會非常重要。
>Although quicksort can be implemented as a stable sort using linked lists, it will often suffer from poor pivot choices without random access.
:::warning
這句不精準，其實不是演算法設計的問題，而是實作手段，可參照 Wikipedia (要看英文版，避免讀中文詞條，後者充斥許多錯誤) 的解釋。
:notes: jserv
>Fix it, Thanks!
:::

**結構體**
```c
struct item {                         
    uint16_t i;
    struct list_head list;
};
```

```c
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);
```
考慮到結構體的定義、 `list_first_entry` 的用途以及變數的宣告，可知 `AAA` = `item`，`BBB` = `list`

```c
CCC (itm, is, head, list) {
    if (cmpint(&itm->i, &pivot->i) < 0)
        DDD (&itm->list, &list_less);
    else
        EEE (&itm->list, &list_greater);
}
```
根據 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的定義，可以放入 4 個引數的僅有 `list_for_each_entry_safe` = `CCC` ，且 `DDD`、`EEE` 負責根據當前迭代到的值大於或是小於 `pivot` 來進行節點交換
- 當迭代到的值小於 `pivot` 的值 (`if` 條件滿足) 則將該節點移動至 `list_less` 節點後面，若否，則移動到 `list_greater` 節點後面
    - `DDD` = `EEE` = `list_move_tail`

透過遞迴的方式繼續對 `list_less`、 `list_greater` 做一樣的處理，此時注意到最後兩行為
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head)
```
代表每次回傳都是將已經排序好的 list 接在 `head` 後面，其中，首先將 `pivot` 放在 `head` 後，再將代表比 `pivot` 小的 `list_less` 放在 `head` 後面，最後一部將比 `pivot` 大的 `list_greater` 放在 `pivot` 右側，也就是目前由 `head` 開頭的 list 的最後面，故得知 `list_splice_tail` = `FFF`.

```graphviz
digraph g{
    node [shape=box];
    pivot[shape=plaintext]
    head[label=head][shape=circle]
    5[label=5];
    4[label=4];    
    2[label=2];
    3[label=3];
    1[label=1];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=same;
            head->5->4->2->3->1;
        }
    }
    pivot -> 5;
    subgraph less {
        {
            rank=same;
            less->none1;
        }
    }
    subgraph greater {
        {
            rank=same;
            greater->none2
        }
    }
}
```
```c
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);
```

```graphviz
digraph g{
    node [shape=box];
    pivot[shape=plaintext]
    head[label=head][shape=circle]
    5[label=5];
    4[label=4];    
    2[label=2];
    3[label=3];
    1[label=1];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=1;
            head->4->2->3->1;
        }
    }
    pivot -> 5;
    subgraph less {
        {
            rank=1;
            less->none1;
        }
    }
    subgraph greater {
        {
            rank=1;
            greater->none2
        }
    }
}
```

```c
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, head, list) {
    if (cmpint(&itm->i, &pivot->i) < 0)
        list_move_tail(&itm->list, &list_less);
    else
        list_move_tail(&itm->list, &list_greater);
}
```
```graphviz
digraph g{
    node [shape=box];
    pivot[shape=plaintext]
    head[label=head][shape=circle]
    5[label=5];
    4[label=4];    
    2[label=2];
    3[label=3];
    1[label=1];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=1;
            head->none1;
        }
    }
    pivot -> 5;
    subgraph less {
        {
            rank=1;
            less->4->2->3->1;
        }
    }
    subgraph greater {
        {
            rank=1;
            greater->none2
        }
    }
}
```
```c
list_sort(&list_less);
```
```graphviz
digraph g{
    node [shape=box];
    pivot[shape=plaintext]
    head[label=head][shape=circle]
    4[label=4];    
    2[label=2];
    3[label=3];
    1[label=1];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=same;
            head->4->2->3->1;
        }
    }
    pivot -> 4;
    subgraph less {
        {
            rank=same;
            less->none1;
        }
    }
    subgraph greater {
        {
            rank=same;
            greater->none2
        }
    }
}
```

```graphviz
digraph g{
    node [shape=box];
    pivot[shape=plaintext]
    head[label=head][shape=circle]
    4[label=4];    
    2[label=2];
    3[label=3];
    1[label=1];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=1;
            head->none1;
        }
    }
    pivot -> 4;
    subgraph less {
        {
            rank=1;
            less->2->3->1;
        }
    }
    subgraph greater {
        {
            rank=1;
            greater->none2
        }
    }
}
```

```graphviz
digraph g{
    node [shape=box];
    pivot[shape=plaintext]
    head[label=head][shape=circle]  
    2[label=2];
    3[label=3];
    1[label=1];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=1;
            head->none1;
        }
    }
    pivot -> 2;
    subgraph less {
        {
            rank=1;
            less->1;
        }
    }
    subgraph greater {
        {
            rank=1;
            greater->3
        }
    }
}
```
以此類推最後透過

```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);  
```
先把節點放進去，比節點大的放右邊，比節點小的放左邊，完成排序

```graphviz
digraph g{
    node [shape=box];
    head[label=head][shape=circle]   
    2[label=2];
    3[label=3];
    1[label=1];
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=same;
            head->1->2->3;
        }
    }
}
```

```graphviz
digraph g{
    node [shape=box];
    head[label=head][shape=circle]   
    4[label=4];
    2[label=2];
    3[label=3];
    1[label=1];
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=same;
            head->1->2->3->4;
        }
    }
}
```
```graphviz
digraph g{
    node [shape=box];
    head[label=head][shape=circle]   
    5[label=5];
    4[label=4];
    2[label=2];
    3[label=3];
    1[label=1];
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]

    subgraph cluster_0 {
        style=invis;
        {
            rank=same;
            head->1->2->3->4->5;
        }
    }
}
```


---

## 測驗二

**延伸問題**
- [ ] 解釋程式碼運作原理，指出設計和實作的缺失
- [ ] 比較測驗 `1` 和測驗 `2` 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快
- [ ] 提出效能改進方案，特別是避免依賴 `MAX_DEPTH`
- [ ] 引入 [Introsort](https://en.wikipedia.org/wiki/Introsort), 也就是 quick sort 和 heap sort (或其他可避免前者 $O(n^{2})$ 最差時間複雜度的演算法)。加入 heapsort 的原因為，當 quicksort 迭代 $2 \times \log n$ 次後還排序完成，那就很可能會得到 $O(n^{2})$ 時間複雜度。此時切換為 heap sort 能將其時間複雜度控制在 $O(n \log n)$


首先根據 [Optimized QuickSort](https://alienryderflex.com/quicksort/) 的所提及的方法與原版(這裡原版指的是網站指出的 wikipeida 版本)比較，包含了以下幾個優點
- 避免使用 function call ，減少 CPU 花在進入 function、離開 function 的時間
- 不使用 stack 來儲存資料，文中提及雖然 recursive 版本的 quick sort 看起來直觀簡單，但是會使用大量的 private stack 來儲存資料，會比起直接使用 `beg[]`、 `end[]` arrau 來的慢，且有機會造成 stack overflow，而文中提及的方法透過設定 `MAX_LEVELS` 來回傳 `NO` 來避免產生 failure
- 在每一輪中，原版會 `swap` 非常多次，但文中版本僅 swap pivot 以及某個節點一次
- 其他像是多次移動同個物件、冗餘的移動、和自己進行 swap 都在文中新版本有所改善


測驗 2 給定具有 `MAX_DEPTH = 512` 的 stack 來模擬遞迴的過程且使用 `INIT_LIST_HEAD` 來初始化 `head` (此處上端為 `stack[0]` 依次往下遞增為 `stack[1], stack[2] ... stack[MAX_DEPTH-1]`)

```c
struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
    INIT_LIST_HEAD(&stack[i]);
```
```graphviz
digraph list_head {
    rankdir=LR
    node[shape=record, style=bold];
    stack [label="stack|{<prev1>prev|<next1>next}|{<prev2>prev|<next2>next}|...|{<prevn>prev|<nextn>next}"];
    {rank=same; stack:prev1; stack:next1;}
    {rank=same; stack:prev2; stack:next2;}
    {rank=same; stack:prevn; stack:nextn;}
    stack:next1:e -> stack:prev1:w[arrowhead=normal, arrowtail=normal, dir=both];
    stack:next2:e -> stack:prev2:w[arrowhead=normal, arrowtail=normal, dir=both];
    stack:nextn:e -> stack:prevn:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```

把尚未排序好的 list 放進 stack 中
```c
int top = -1;
list_splice_init(head, &stack[++top]);
```
```graphviz
digraph list_head {
    rankdir=LR
    node[shape=record, style=bold];
    4[label=4];    
    5[label=5];
    6[label=6];
    2[label=2];
    8[label=8];
    3[label=3];
    1[label=1];
    7[label=7];
    stack [label="stack|{<prev1>prev|<next1>next}|{<prev2>prev|<next2>next}|...|{<prevn>prev|<nextn>next}"];
    {rank=same; stack:prev1; stack:next1;}
    {rank=same; stack:prev2; stack:next2;}
    {rank=same; stack:prevn; stack:nextn;}
    stack:next1:e ->4->5->3->6->2->8->1->7
    stack:next2:e -> stack:prev2:w[arrowhead=normal, arrowtail=normal, dir=both];
    stack:nextn:e -> stack:prevn:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
- 執行完上述程式碼時時 `top` 為 `0`，進入 `while` 迴圈

```c
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
```
```graphviz
digraph g{
    node [shape=record];
    rankdir=LR
    partition[label=partition][shape=plaintext]
    4[label=4];    
    5[label=5];
    6[label=6];
    2[label=2];
    8[label=8];
    3[label=3];
    1[label=1];
    7[label=7];
    partition->4->5->6->2->8->3->1->7
}
```
- 執行完上述程式碼時時 `top` 為 `-1`，且符合第一個 `if` 條件，進入 `if` 迴圈

```c
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);
```



```graphviz
digraph g{
    rankdir=LR
    node [shape=box];
    pivot[shape=plaintext]
    partition[label=partition][shape=plaintext]
    4[label=4];    
    5[label=5];
    6[label=6];
    2[label=2];
    8[label=8];
    3[label=3];
    1[label=1];
    7[label=7];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    none1[label=""][shape=plaintext]
    none2[label=""][shape=plaintext]
    pivot->4
    partition->5->6->2->8->3->1->7
    less->none1
    greater->none2
}
```

首先把 `head` 當我 pivot ，從對 list 左邊開始找，找到小於 pivot 的值就會放入，(文中使用 `beg[]`， `end[]` 紀錄比較過程)， linked list 則透過與測驗 1 一樣的 `list_less`、`list_greater` 來儲存資訊。

```c
GGGG (itm, is, &partition, list) {
    ...
    }
```
- 與測驗一相同， `GGGG` 為 `list_for_each_entry_safe`


將各個節點和 `pivot` 比大小並將對應結果分別放到 `list_less` 以及 `list_greater`
```c
list_for_each_entry_safe(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);
}
```
```graphviz
digraph g{
    rankdir=LR
    node [shape=box];
    pivot[shape=plaintext]
    partition[label=partition][shape=plaintext]
    4[label=4];    
    5[label=5];
    6[label=6];
    2[label=2];
    8[label=8];
    3[label=3];
    1[label=1];
    7[label=7];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    none1[label=""][shape=plaintext]
    pivot->4
    partition->none1
    less->1->3->2
    greater->7->8->6->5
}
```

接著將 `pivot` 如同測驗 1 一樣在將 `less` 和 `greater` 合併時 `pivot` 會在中間，所以根據題目是將 `pivot` 放在 `less` 的某處，應為 `less` 的尾端

```c
HHHH (&pivot->list, &list_less);
```
- 故 `HHHH` 為 `list_move_tail`


```graphviz
digraph g{
    rankdir=LR
    node [shape=record];
    4[label=4];    
    5[label=5];
    6[label=6];
    2[label=2];
    8[label=8];
    3[label=3];
    1[label=1];
    7[label=7];
    less[label=less][shape=plaintext]
    greater[label=greater][shape=plaintext]
    less->1->3->2->4
    greater->7->8->6->5
}
```

再來就是和測驗 1 不同的部份，透過 `stack` 取代遞迴的過程，故將 `less` 以及 `greater` 放進去 `stack` (記得在此處 `top` 為 `-1`，為原本放未排序的 list 的地方，取出來做處理得時候有 -1)，在推進去 `stack` 時為 `&stack[++top]`
- 考試的時候寫成 `&stack[top++]`，不夠細心

```c
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[++top]`

```graphviz
digraph list_head {
    rankdir=LR
    node[shape=record, style=bold];
    4[label=4];    
    5[label=5];
    6[label=6];
    2[label=2];
    8[label=8];
    3[label=3];
    1[label=1];
    7[label=7];
    stack [label="stack|{<prev1>prev|<next1>next}|{<prev2>prev|<next2>next}|...|{<prevn>prev|<nextn>next}"];
    {rank=same; stack:prev1; stack:next1;}
    {rank=same; stack:prev2; stack:next2;}
    {rank=same; stack:prevn; stack:nextn;}
    stack:next1:e ->7->8->6->5;
    stack:next2:e ->1->3->2->4;
    stack:nextn:e -> stack:prevn:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
因為 `top` 值在推送進 stack 時有增加，所以 `while` 迴圈會持續運作，接著會對 `1 -> 3 -> 2 -> 5` 這個 list 做上述一樣的動作，持續到第一個 `if` 條件不滿足，也就是不滿足
```c
if (!list_empty(&partition) && !list_is_singular(&partition))
```
- 代表從 `stack` 取出的節點為空或者是只有一個節點，此時進入 `else` 條件，

在第一次進入 `else` 前的 `stack` 樣子為

```graphviz
digraph list_head {
    rankdir=LR
    node[shape=record, style=bold];
    4[label=4];    
    5[label=5];
    6[label=6];
    2[label=2];
    8[label=8];
    3[label=3];
    1[label=1];
    7[label=7];
    partition[label=partition][shape=plaintext]
    stack [label="stack|
    {<prev1>prev|<next1>next}|
    {<prev2>prev|<next2>next}|
    {<prev3>prev|<next3>next}|
    {<prev4>prev|<next4>next}|
    {<prev5>prev|<next5>next}|
    ...|
    {<prevn>prev|<nextn>next}"];
    stack:next1:e ->7->8->6->5;
    stack:next2:e ->3->2->4;
    partition->1;
}
```
偵測到 `stack` 的最頂端 (尚未從 `stack` 取出的圖中最下面)，僅有一個節點 `1`，取出後 (此時的 `top` 會在指向 `3->2->4` 的位置，因為在切出 `partition` 的時候有做 `top--` 的動作)進入 `else` 條件首先要先 `top++` push `top` 一格

```c
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);
}
```
一進入後會將剛剛判斷為只有一個節點的 `partition` 放回 `stack[top]`，注意到題目中進行 `list_del(&tmp->list)` 且後面有 `list_add_tail(&tmp->list, head)`，代表已經將該節點放到 `head` 後面，以完成排序的部份，故 `KKKK` 必須對 `stack` pop 一格，`KKKK` = `&stack[top--]`

總結進入到 `else` 才會透過 `list_add_tail(&tmp->list, head);` 將排序好的節點放到 `head` 後面，且進入 `else` 的條件為此時 `stack[top]` 的位置僅有一個節點，且根據上述過程，`stack[top]` 必為未排序的 list 中最小的那個節點 (在推進去 `stack` 的時候是先推 `greater` 後再推 `less`，所以比較小的節點會在上面)，以此依序將最小的節點接在 `head` 後面完成排序。

---

## 測驗三

**延伸問題**
- [ ] 解釋上述程式碼運作原理，指出其實作缺陷並改進
- [ ] 在上述 XOR linked list 的基礎，實作測驗 `1` 和 `2` 提及的快速排序演算法，注意要引入你改進效能的版本
- [ ] 修改 `xorlist_destroy`，使其不急著釋放記憶體，而搭配 [atexit(3)](https://man7.org/linux/man-pages/man3/atexit.3.html) 並在程式即將結束執行時，才批次處理資源釋放

在關鍵巨集中
```c
#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))
```
根據函式名稱以及在程式內的用途知其為將 `a` 和 `b` 做 exclusive or 運算
- `LLLL` = `(uintptr_t)(a) ^ (uintptr_t)(b)`

另一個常用函式為 `address_of`，在透過 `assert` 確認 `n1`、`n2` 都為非 0 值後搭配 `XOR_COMP` 巨集進行 exclusive or 運算回傳下一個節點地址。
```c
static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
    assert(n1 && n2);
    return XOR_COMP(n1, n2);
}
```

XOR List 的迭代過程透過前一個的地址以及這一格的 `link` 進行 `xor` 運算來獲得下一格的位址，也就是說當前位置的 `link` 可以透過前後兩個點的地址進行 `xor` 運算得到

根據上述，程式內也定義了 `xor_list_t` 來代表 list 所需的資訊

```c
typedef struct _xor_list_struct {
    xor_node_t head, tail;
    uint32_t count;
} xor_list_t;
```
- 根據前面敘述，要拿到當前節點的 `link` ，需要前後兩個點的地址，所以在這裡也直接定義了 `head` 以及 `tail` 代表 `list` 的頭尾

```graphviz
digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    subgraph cluster_0 {
        node [shape=record];
        head [label="{head}"];
        tail [label="{tail}"];
        count [label="count"][shape=plaintext];
        style=bold;
        label=list
    }
}
```


查看 `xorlist_for_each` 巨集
```c
#define xorlist_for_each(node, rp, rn, list)                        \
    for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
         rn = address_of(rp, node->cmp), rp = node, node = rn)
```
- 可以看到在迭代的過程中 `rn` 為下一個節點的地址，是透過 `rp` (前一個節點的地址) 和 `node->cmp` (當前節點的 link) 做 `xor` 運算得到。

在 `main` 中，先將 0~100 的值透過 `xorlist_add` 加入到 `list` 中，

```c
xornode_init(&new->xornode);
new->value = i;
xorlist_add(&list, &new->xornode);
```

```graphviz
digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    null[shape=plaintext]
    subgraph cluster_0 {
        node [shape=record];
        head [label="{head}"];
        tail [label="{tail}"];
        count [label="count"][shape=plaintext];
        style=bold;
        label=list
    }
    subgraph cluster_1 {
        label="new node 1"
        value[label=value]
        xornode[label="xornode|{<cmp>cmp}" ]
    }
    head->xornode:cmp
    xornode:cmp->null
}
```

```graphviz
digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    null[label=null][shape=plaintext]
    subgraph cluster_0 {
        node [shape=record];
        head [label="{head}"];
        tail [label="{tail}"];
        count [label="count"][shape=plaintext];
        style=bold;
        label=list
    }
    subgraph cluster_1 {
        label="new node 1"
        value[label=value]
        xornode[label="<label>xornode|{<cmp>cmp}" ]
    }
    subgraph cluster_2 {
        label="new node 2"
        value2[label=value]
        xornode2[label="<label>xornode|{<cmp>cmp}" ]
    }
    head->xornode:label
    xornode:cmp->xornode2:label
    xornode2:cmp->null
}
```
這裡的 `cmp` 若是要取得下一個節點的地址則需要與前一個節點地址做 `xor`

考慮題目及，題目給的參考執行輸出，
```c
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;
}
```
- 題目 `MMMM` 用以處理初始的條件，在進入 `xorlist_add` 之前已經呼叫過 `XORLIST_INIT(h)` 巨集，將 `head` 以及 `tail` 的 `cmp` 互相設定為對方，在初始條件下 `real_next` 即為 `list_tail`，故 `MMMM` = `&list->tail`，此時這個 `if-else` 條件似乎顯得沒必要? 可直接使用 `real_next` = `node` 做取代 (待驗證)

考慮到若 `if` 條件滿足，則代表 `node = real_prev->cmp` 為 `&list->tail`，此時 `node` 等價於 `&list_tail` ，因為是將新的節點 `n` 插入至 list 的第一個節點，且 `node` 指向 `real_prev` 的壓縮地址 (`cmp`)，因為是 `head` 的關係所以壓縮地址必為下一個節點地址，同時 `node` 也會是，故直接省略 `if` 條件也可以正常執行

```diff
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_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;
}
```


根據題目顯示，`list_add` 是新增節點在 list 的頭

進入 `list_add` 初始狀態如圖 `A`、`B` 為該節點地址
```graphviz
digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    head[label="A|{<cmp>cmp=B}"];
    tail[label="B|{<cmp>cmp=A}"];
    head:cmp->tail:cmp[dir=both]
}
```
在初始狀態新增一個節點地址為 `C` 後的結果應為
```graphviz
digraph list {
    rankdir=LR;
    node[shape=record, style=bold];
    head[label="A|{<cmp>cmp=B}"];
    tail[label="B|{<cmp>cmp=C}"];
    node1[label="C|{<cmp>cmp=A \oplus B}"]
    n[label="n"][shape=plaintext]
    rn[label="real_next"][shape=plaintext]
    rp[label="real_prev"][shape=plaintext]
    head:cmp->node1:cmp[dir=both]
    node1:cmp->tail:cmp[dir=both]
    n->node1
    rn->tail
    rp->head
}
```

- 而 `PPPP` 用以更新 `real_next->cmp` 的值，從 xor-list 的方法知道該節點的 `cmp` 為前後節點地址做 `xor` 運算

```c
real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
```
此時要讓 `real_next->cmp` 從 A 更新為 C，進行運算 $C \oplus (A\oplus PPPP)$，此時 `PPPP` 應為 A ，用以消除 A (因為 $A\oplus A = 0$)，故 `PPPP` 為 `real_next->cmp`