---
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`
Sign in with Wallet
Connect another wallet