# 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>
```c
#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;
}
```
```diff
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`。
```graphviz
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 。
```graphviz
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。
走訪鏈結串列後會如下所示：
```graphviz
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` 排序完成並回傳：
```graphviz
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)` :
```graphviz
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)：
```graphviz
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 的尾端。
```graphviz
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>
```c
#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]:
```graphviz
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` 。
```graphviz
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]
```graphviz
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` 的部份:
```graphviz
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 --] 。
```graphviz
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]);` 會比較恰當。
```diff
- 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);
```
```graphviz
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)。
```c
#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 經過初始化過後會如下所示：
```graphviz
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>
```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;
... ...
}
```
</details>
```graphviz
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 。
```graphviz
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` 只向下一個位置。
```graphviz
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。
```graphviz
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>
```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 = &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>
---
Sign in with Wallet
Connect another wallet