# 2021q1 Homework1 (quiz1)
contributed by < [`andy78644`](https://github.com/andy78644) >
###### tags: `2021 linux`
## 程式運作原理
```clike=
typedef struct __node {
int value;
struct __node *next;
} node_t;
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
node_t[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
list[shape=plaintext,fontcolor=blue]
list->head->A
node_t->C
}
A->B->NULL1
C->NULL2
}
```
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
node_t[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
list[shape=plaintext,fontcolor=blue]
list->head->A
node_t->C
}
C->A->B->NULL1
}
```
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
node_t[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
list[shape=plaintext,fontcolor=blue]
list->head->C
node_t->C
}
C->A->B->NULL1
}
```
* 將 node_t 的 next 指向 list ，此動作即是將 node 插入 list 的前端
* 透過指標的指標改變 head指標所指向的位置
```clike=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
right[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=D]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
left[shape=plaintext,fontcolor=blue]
left->head->A
right->C
}
A->B->NULL1
C->D->NULL2
}
```
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
right[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=D]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
left[shape=plaintext,fontcolor=blue]
left->head->NULL1
right->C
}
A->B->NULL1
C->D->NULL2
}
```
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
right[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label="A"]
B[label=B]
C[label=C]
D[label=D]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
left[shape=plaintext,fontcolor=blue]
left->head->C
right->C
}
A->B->C->D->NULL2
}
```
* 先將 left 所指的指標的位置移到串列的最後一個也就是 NULL
* 再將 right 接上此位置以達到兩個串列的連接
* 因此 LLL 的答案為 left = &((*left)->next))
```clike=
void quicksort(node_t **list)
{
if (!*list)
return;
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? AAA : BBB, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
CCC;
*list = result;
}
```
* 第七行中選出 pivot 為串列的第一個
* 13~17行，分別比較串列內每個節點與 pivot 的大小，因此分別將 node 插入兩個串列中，而我們可以在後面24行的位置判斷出 left 應為比 pivot 小的串列， right 則是比 pivot 大的節點所形成的串列
* 19,20行中，分別利用遞迴再對 left 以及 right 做 quicksort 的排序
* 23,24行中，分別要將 left, right, pivot 接在一起，而 concat 是分別在第一個串列放在左邊以及第二個串列放在右邊，因此CCC的答案為 list_concat(&result, pivot); list_concat(&result, right)
```clike=
static bool list_is_ordered(node_t *list) {
bool first = true;
int value;
while (list) {
if (first) {
value = list->value;
first = false;
} else {
if (list->value < value)
return false;
value = list->value;
}
list = list->next;
}
return true;
}
static void list_display(node_t *list) {
printf("%s IN ORDER : ", list_is_ordered(list) ? " " : "NOT");
while (list) {
printf("%d ", list->value);
list = list->next;
}
printf("\n");
}
int main(int argc, char **argv) {
size_t count = 20;
node_t *list = NULL;
while (count--)
list = list_make_node_t(list, random() % 1024);
list_display(list);
quicksort(&list);
list_display(list);
if (!list_is_ordered(list))
return EXIT_FAILURE;
list_free(&list);
return EXIT_SUCCESS;
}
```
---
## 延伸問題
### 延伸 1 ：random()
* 在 man random() 裡面可以看到下面的敘述，裡面有提到在未給於參數時，會自動 srandom()的參數值設為1，如我們題目中我們使用 list_make_node_t(list, random() % 1024) 作為產生節點的函式，因此每次所產生的節點的數字皆會相同
> The random() function uses a nonlinear additive feedback random number generator employing a default table of size 31 long integers to return successive pseudo-random numbers in the range from 0 to RAND_MAX. The period of this random number generator is very large, approximately 16 * ((2^31) - 1).
```clike=
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
```
* 可在執行 random() 之前加入 srandom(time(0)) 來設定種子的位置， time(0) 則是當下時間，即可在每次程式執行產生不同的亂數
> The srandom() function sets its argument as the seed for a new sequence of pseudo-random integers to be returned by random(). These sequences are repeatable by calling srandom() with the same seed value. If no seed value is provided, the random() function is automatically seeded with a value of 1.
```clike=
1618318567
NOT IN ORDER : 9947 4657 1674 1897 4680 6351 6177 1230 1581 5226 2336 3686 3029 5107 5793 7878 4538 2487 5660 2589
IN ORDER : 1230 1581 1674 1897 2336 2487 2589 3029 3686 4538 4657 4680 5107 5226 5660 5793 6177 6351 7878 9947
1618318568
NOT IN ORDER : 7242 9223 9080 5045 3834 988 4930 6369 5993 6529 3122 7603 9895 7146 9295 8951 3019 744 9373 1984
IN ORDER : 744 988 1984 3019 3122 3834 4930 5045 5993 6369 6529 7146 7242 7603 8951 9080 9223 9295 9373 9895
744
```
:::info
[The GLIBC random number generator](https://www.mathstat.dal.ca/~selinger/random/)
這篇有提到在 random(3) man page 裡，有寫到產生亂數是使用 nonlinear 的方式，但實際在產生亂術的實作裡使用的還是 linear 的方式，不過如果是不同 seeed 的處理仍是 nonlinear，類似於 LCG 的方式
> The random(3) man page states, misleadingly, that "the random() function uses a non-linear additive feedback random number generator". This is not actually true, as the feedback is in fact linear modulo 232. The only slight non-linearity is introduced during the seeding stage, due to the fact that the seeding calculation is done modulo 231 - 1 and not modulo 231 or 232. This means that, although each generated random number depends linearly on previous numbers in the sequence, the random numbers as a whole do not depend linearly on the seed.
:::
---
### 延伸 2 :Optimized QuickSort - Non-Recursive
[Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)
在這邊文章所用到的非遞迴的 quicksort 實作
```cpp
bool quickSort(int *arr, int elements) {
#define MAX_LEVELS 1000
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R ;
beg[0]=0; end[0]=elements;
while (i>=0) {
L=beg[i]; R=end[i]-1;
if (L<R) {
piv=arr[L]; if (i==MAX_LEVELS-1) return NO;
while (L<R) {
while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R];
while (arr[L]<=piv && L<R) L++; if (L<R) arr[R--]=arr[L]; }
arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; }
else {
i--; }}
return YES;
}
```
文章內主要的想法是透過降低 function call 的次數來增進效能，由於 recursive 的方式會大幅增加 function call 的次數因此導致效能降低
> My implementation avoids function calls. Calling (and returning from) a function is time-consuming, and not because the content of the function takes time to execute — just getting into the function, and back out of it, uses processor time.
參考 [ambersun1234](https://hackmd.io/@ambersun1234/quiz1)並且與文章內提供的程式碼進行修改後
```cpp
#define MAX_LEVELS 100
void non_recursive_quicksort(node_t *list, node_t *tail) {
if (!list || list->previous == list)
return;
int i = 0;
node_t *l, *r;
node_t *beg[MAX_LEVELS], *end[MAX_LEVELS];
beg[0] = list;
end[0] = tail;
int pivot = list->value;
while (i >= 0) {
l = beg[i];
r = end[i];
if (l != r && l && r) {
pivot = l->value;
while (l != r && l && r) {
while (r->value > pivot && l != r) {
r = r->previous;
}
if (l != r) {
l->value = r->value;
l = l->next;
}
while (l->value < pivot && l != r)
l = l->next;
if (l != r) {
r->value = l->value;
r = r->previous;
}
}
l->value = pivot;
beg[i + 1] = l->next;
end[i + 1] = end[i];
end[i] = l;
i = i + 1;
} else
i--;
}
}
```
根據老師給予的方法中有提到可以將 `beg` 和 `end` 可以只使用其中一個，我將它改為 `stack` 分別儲存 beg 和 end 的位置來進行改善
```clike=
#define MAX_LEVELS 100
void non_recursive_quicksort(node_t *list, node_t *tail) {
if (!list || list->previous == list)
return;
int i = 0;
node_t *l, *r;
node_t *beg[MAX_LEVELS], *end[MAX_LEVELS], *stack[MAX_LEVELS];
beg[0] = list;
end[0] = tail;
stack[0] = list;
stack[1] = tail;
int pivot = list->value;
while (i >= 0) {
l = stack[i];
r = stack[i + 1];
if (l != r && l && r) {
pivot = l->value;
while (l != r && l && r) {
while (r->value > pivot && l != r) {
r = r->previous;
}
if (l != r) {
l->value = r->value;
l = l->next;
}
while (l->value < pivot && l != r)
l = l->next;
if (l != r) {
r->value = l->value;
r = r->previous;
}
}
l->value = pivot;
stack[i + 2] = l->next;
stack[i + 3] = stack[i + 1];
stack[i + 1] = l;
i = i + 2;
} else
i = i - 2;
}
}
```
---
### 延伸 3 : Linux 內的 linked-list
在 [ The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.list_sort) 可以查到有關 list_sort 的語法
為了使 avg 和 worst cast 皆可達到 O(nlogn) ，因此使用 merge sort 而非 quick sort (quick sort 的 worst case 達到 $n^2$)，而其中有說到為了避免 crash trashing 只要出現 2 個相同長度需要被 merge 的 list 即會馬上合併，而每個長度的數量會有一個 count 去進行紀錄，每個 bit 即代表不同長度
```clike=
void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, struct list_head *a, struct list_head *b))
```
> This mergesort is as eager as possible while always performing at least 2:1 balanced merges. Given two pending sublists of size 2^k, they are merged to a size-2^(k+1) list as soon as we have 2^k following elements.
Thus, it will avoid cache thrashing as long as 3*2^k elements can fit into the cache. Not quite as good as a fully-eager bottom-up mergesort, but it does use 0.2*n fewer comparisons, so is faster in the common case that everything fits into L1.
The merging is controlled by “count”, the number of elements in the pending lists. This is beautiully simple code, but rather subtle.
Each time we increment “count”, we set one bit (bit k) and clear bits k-1 .. 0. Each time this happens (except the very first time for each bit, when count increments to 2^k), we merge two lists of size 2^k into one list of size 2^(k+1).
可以從兩者 `list_add` 的函式中發現兩者使用的街市 `circular doubly linked list` ，在加入新的節點時皆須將 `head->prev` 指向新的節點，並且將 `node->next` 指向 `head` ，而兩者的差別就在 Linux list 中在將原本的最後那個節點要指向新結點用的 `WRITE_ONCE`
```clike=
struct list_head {
struct list_head *prev;
struct list_head *next;
};
// Linux list
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
//linux list
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
:::info
在 [linux/compiler.h](https://elixir.bootlin.com/linux/latest/source/tools/include/linux/compiler.h#L184) 可以找到對於 `WRITE_ONCE` 的註釋說明，在最後一段可以看到他主要有兩個用處，第一就是可以當作 process 間通信的功能，第二個就是在避免因為編譯器優化導致指令順序調動而產生錯誤
> Prevent the compiler from merging or refetching reads or writes. The compiler is also forbidden from reordering successive instances of READ_ONCE and WRITE_ONCE, but only when the compiler is aware of some particular ordering. One way to make the compiler aware of ordering is to put the two invocations of READ_ONCE or WRITE_ONCE in different C statements.
These two macros will also work on aggregate data types like structs or unions. If the size of the accessed data type exceeds the word size of the machine (e.g., 32 bits or 64 bits) READ_ONCE() and WRITE_ONCE() will fall back to memcpy and print a compile-time warning.
Their two major use cases are: (1) Mediating communication between process-level code and irq/NMI handlers, all running on the same CPU, and (2) Ensuring that the compiler does not fold, spindle, or otherwise mutilate accesses that either do not require ordering or that interact with an explicit memory barrier or atomic instruction that provides the required ordering.
```clike=
#define WRITE_ONCE(x, val) \
({ \
union { typeof(x) __val; char __c[1]; } __u = \
{ .__val = (val) }; \
__write_once_size(&(x), __u.__c, sizeof(x)); \
__u.__val; \
})
```
[WRITE_ONCE](https://stackoverflow.com/questions/34988277/write-once-in-linux-kernel-lists) 有更詳細的說明為什麼使用 `WRITE_ONCE`
:::
Sign in with Wallet
Connect another wallet