---
tags: sysprog21
---
# 2021q1 Homework1 (quiz1)
contributed by < `akamayu-ouo` >
> [第一周測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)
```cpp
#define LLL left = &((*left)->next)
#define AAA &right
#define BBB &left
#define CCC \
list_concat(&result, pivot); \
list_concat(&result, right)
```
### list_concat
```cpp=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next);
*left = right;
}
```
假設這個函式被用以下方式呼叫
```cpp
list_concat(&X, Y);
```
因此 `left` 的初始值為 `&X`，`right` 則為 `Y` 。
#### X 為 NULL
此時的關係
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
r [label="right"]
l [label="left"]
x [label="X=NULL"]
node[shape=record];
a [label="{A|val|<next>}"]
b [label="{B|val|<next>}"]
dotdot [label="……",shape=none]
a:next:c -> b
b:next:c -> dotdot
l:c -> x
r:c -> a
}
```
跳過迴圈後執行 `*left = right;` ，將 `*left`（`X`）設成 `right` （`A` 的記憶體位置）。
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
r [label="right"]
l [label="left"]
x [label="X"]
node[shape=record];
a [label="{<struct> A|val|<next>}"]
b [label="{B|val|<next>}"]
dotdot [label="……",shape=none]
a:next:c -> b
b:next:c -> dotdot
l:c -> x
r:c -> a
x -> a:struct:n [weight=0]
{rank=same;l r}
}
```
回傳後的結果即為
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
x [label="X"]
node[shape=record];
a [label="{A|val|<next>}"]
b [label="{B|val|<next>}"]
dotdot [label="……",shape=none]
a:next:c -> b
b:next:c -> dotdot
x -> a [weight=0]
}
```
#### X 不為 NULL
進入函式時變數的關係如下：
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
r [label="right"]
l [label="left"]
x [label="X"]
node[shape=record];
a [label="{A|val|<next>}"]
b [label="{B|val|<next>NULL}"]
c [label="{C|val|<next>}"]
d [label="{D|val|<next>}"]
dotdot [label="……",shape=none]
a:next:c -> b
c:next:c -> d
d:next:c -> dotdot
l:c -> x
r:c -> c
x:c -> a
{rank=same; r x}
}
```
因為對指標 `A->B` 等價於 `(*A).B` ，第 3 行可以改寫成
```c
left = &((**left).next);
```
將 `*left` 、`**left` 以及 `(**left).next` 分別標注在圖上就是
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
l [label="left"]
x [label="X"]
node[shape=record];
a [label="{A|val|<next> (**left).next}"]
b [label="{B|val|<next>NULL}"]
a:next:c -> b
l:c -> x
x:c -> a
subgraph cluster1{x;label="*left";}
subgraph cluster2{a;label="**left";}
}
```
更新 `left` 後它會指向 `A.next`，此時 `**left` 即為 `A` 的下一個元素 `B` 。值得注意的是 `X` 的值維持不變，呼叫者仍有辦法以此找到 linked list 的起始點 `A`（然而在函數中已無法得知 `X` 的值了）。
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
l [label="left"]
x [label="X",color=grey60,fontcolor=grey60]
node[shape=record];
a [label="{A|val|<next>*left}"]
b [label="{B|val|<next>NULL}"]
a:next:c -> b
l -> a:next:n [weight=0]
x -> a [color=grey60]
subgraph cluster1{b;label="**left";}
}
```
重複 `left = &((**left).next);` ，直到 `*left` 的值是 NULL 。此時 `left` 指向以 `X` 為首的 linked list 中最後一個元素的 `next` 變數。
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
l [label="left"]
x [label="X",color=grey60,fontcolor=grey60]
node[shape=record];
a [label="{A|val|<next>}"]
b [label="{B|val|<next>*left=NULL}"]
a:next:c -> b
l:e -> b:next:n [weight=0]
x -> a [color=grey60]
}
```
跳出迴圈後執行 `*left = right;` ，將 `B.next` 設成 `right` 。
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
x [label="X",color=grey60,fontcolor=grey60]
r [label="right"]
l [label="left"]
node[shape=record];
c [label="{<struct> C |val|<next>}"]
d [label="{D|val|<next>}"]
a [label="{A|val|<next>}"]
b [label="{B|val|<next>*left}"]
dotdot [label="……",shape=none]
a:next:c -> b
c:next:c -> d
d:next:c -> dotdot
b:next:s -> c:struct:n [weight=0]
l:e -> b:next:n[weight=0]
r -> c
x -> a [color=grey60]
{rank=same;a c}
{rank=same;x r l}
}
```
回傳後呼叫者看到的結果如下
```graphviz
digraph {
rankdir=LR;
edge[arrowsize=0.7]
node[shape=oval];
x [label="X"]
node[shape=record];
c [label="{<struct> C |val|<next>}"]
d [label="{D|val|<next>}"]
a [label="{A|val|<next>}"]
b [label="{B|val|<next>}"]
dotdot [label="……",shape=none]
a:next:c -> b
c:next:c -> d
d:next:c -> dotdot
b:next:c -> c
x -> a
}
```
### Quick Sort
```cpp
void quicksort(node_t **list)
{
if (!*list)
return;
/* 選擇 pivot：從要排序的數字中選擇一個數字，此處直接使用第一個數字 */
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
/* 分割：將要排序的數字依照跟 pivot 的大小關係分為兩組（ pivot 不參與分組 ）*/
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? &right : &left, n);
}
/* 遞迴：用 quick sort 排好那兩組數字 */
quicksort(&left);
quicksort(&right);
/* 組合：以「不大於 — pivot — 大於」的順序組合在一起，得到排好的序列 */
node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot);
list_concat(&result, right);
*list = result;
}
```
用圖來解釋
- 選擇 pivot
```graphviz
digraph {
4 [shape=legend];
pivot;
pivot->4;
{rank=same; pivot 4}
rankdir=LR;
node[shape=legend]
4->7->3->8->2->6->9->1
}
```
- 分割成兩條 lists
```graphviz
digraph {
rankdir=LR;
node [shape=oval]
left right pivot
node[shape=legend]
pivot->4;
left->3->2->1
right->7->8->6->9
}
```
- 將其分別排序
```graphviz
digraph {
rankdir=LR;
node [shape=oval]
left right pivot
node[shape=legend]
pivot->4
left->1->2->3
right->6->7->8->9
}
```
- 重新接合
```graphviz
digraph {
rankdir=LR;
node [shape=oval]
node[shape=legend]
1->2->3->4->6->7->8->9
}
```
### Memory Leak
範例測試程式中，若檢查發現 linked list 沒有正確排序，程式會馬上結束，但沒有釋放記憶體，造成 memory leak。
```cpp
if (!list_is_ordered(list))
return EXIT_FAILURE;
list_free(&list);
return EXIT_SUCCESS;
```
將範例程式中的 `quicksort(&list)` 那行註解掉後使用 `valgrind --leak-check=full` 測試的結果如下：
```shell
==3686237== HEAP SUMMARY:
==3686237== in use at exit: 320 bytes in 20 blocks
==3686237== total heap usage: 21 allocs, 1 frees, 1,344 bytes allocated
==3686237==
==3686237== 320 (16 direct, 304 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==3686237== at 0x483E77F: malloc (vg_replace_malloc.c:307)
==3686237== by 0x1091A1: list_make_node_t (in /.../sysprog21/Week1/quiz1/main)
==3686237== by 0x1094BD: main (in /.../sysprog21/Week1/quiz1/main)
==3686237==
==3686237== LEAK SUMMARY:
==3686237== definitely lost: 16 bytes in 1 blocks
==3686237== indirectly lost: 304 bytes in 19 blocks
==3686237== possibly lost: 0 bytes in 0 blocks
==3686237== still reachable: 0 bytes in 0 blocks
==3686237== suppressed: 0 bytes in 0 blocks
==3686237==
==3686237== For lists of detected and suppressed errors, rerun with: -s
==3686237== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
```
從輸出資訊（第 8 與 9 行）可以看出沒有被收回的記憶體是由函式 `list_make_node_t` 透過 `malloc` 配置。
我將測試程式修改如下以避免 memory leak。
```diff
- if (!list_is_ordered(list))
- return EXIT_FAILURE;
+ const bool ordered = list_is_ordered(list);
list_free(&list);
- return EXIT_SUCCESS;
+
+ return ordered ? EXIT_SUCCESS : EXIT_FAILURE;
```
### Random
根據 [rand(3)](https://linux.die.net/man/3/rand)：
> If no seed value is provided, the rand() function is automatically seeded with a value of 1.
也就是說，若在呼叫 `rand()` 之前沒有用 `srand()` 設定過種子， `rand()` 的行為會跟使用 `1` 作為種子一樣。因此範例程式才會總是產生出一樣的測試資料。
我改用 [lrand48](https://linux.die.net/man/3/lrand48) 來產生亂數。
> All the functions work by generating a sequence of 48-bit integers, Xi, according to the linear congruential formula:
`Xn+1 = (aXn + c) mod m, where n >= 0`
>The parameter m = 2^48, hence 48-bit integer arithmetic is performed. Unless lcong48() is called, a and c are given by:
>`a = 0x5DEECE66D`
>`c = 0xB`
To Be Continued ...
Sign in with Wallet
Connect another wallet