# 2021q1 Homework (quiz1)
###### tags: `linux2021` ,`linked list`
contributed by < [cymb103u](https://github.com/cymb103u) >
* [第1週測驗題目](https://hackmd.io/@sysprog/linux2021-quiz1)
----
- [x] 1.解釋程式原理
- [ ] 2.引入其他 Pseudorandom number generator
- [x] 3.非遞迴呼叫改寫
- [ ] 4.[仿效 linux-list 並改寫](#延伸問題)
- [ ] 5.思考高效率的 linked list 排序演算法
- [ ] [rbtree](#Tree-sort)
----
## 1. 解釋程式運行原理
* 給定之 data structure，為單向 linked list，typedef 為 `node_t`
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
> * 題目預期 : 已知不存在 circular (環狀結構)，下方程式碼嘗試對該單向 linked list 進行 Quick sort，預期依據遞增順序。
* [static inline 舉例說明](https://medium.com/@hauyang/%E6%88%91%E6%9C%89%E6%89%80%E4%B8%8D%E7%9F%A5%E7%9A%84-static-inline-b363892b7450)
```cpp=
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
* `list_add_node_t` 函式是將 `node_t` 節點加入到 `*list` 之前，並將 `*list` 原本的值更新為 `node_t` 指向整個串列的最前端。
*
```diff=5
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
- LLL;
+ left = &((*left)->next);
*left = right;
}
```
### 1. LLL = `left = &((*left)->next)`
`list_concat()` function 的功用為串接兩個 list。根據給定的 implement 推測它是要走訪 left list 到 end（NULL），再將左右 list 接在一起。而給定的 input `left` 為 `pointer to pointer to node_t`; `right` 則是 `pointer to node_t`。
```graphviz
digraph graphname{
node[shape=box]
"**left"[shape=plaintext,fontcolor=blue]
right[shape=plaintext]
rankdir=LR
{
rankdir = LR
node1[label="(*left) node1"]
node2[label=node2]
nodeN[label=nodeN]
rnode[label=rnode]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
"**left"->node1
}
node1->node2->nodeN->NULL1
right->rnode->NULL2
}
```
一開始以為是 `*left = (*left)->next`，但這樣子實際上會改變 `left` 所指向的 address 裡面的值 ( pointer to node_t )，而非改變 `left` 所指向的 address
```graphviz
digraph graphname{
node[shape=box]
"**left"[shape=plaintext,fontcolor=blue]
right[shape=plaintext]
rankdir=LR
{
rankdir = LR
node2[label="(*left) node2"]
nodeN[label=nodeN]
rnode[label=rnode]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
"**left"->node2
}
node2->nodeN->NULL1
right->rnode->NULL2
}
```
所以應該使用 `left = &((*left)->next)` 來更新 `left` 所指向的 address
* 1
```graphviz
digraph graphname{
node[shape=box]
"**left"[shape=plaintext,fontcolor=blue]
right[shape=plaintext]
rankdir=LR
{
rankdir = LR
node1[label=node1]
node2[label="(*left) node2"]
nodeN[label=nodeN]
rnode[label=rnode]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
"**left"->node2
}
node1->node2->nodeN->NULL1
right->rnode->NULL2
}
```
* 2
```graphviz
digraph graphname{
node[shape=box]
"**left"[shape=plaintext,fontcolor=blue]
right[shape=plaintext]
rankdir=LR
{
rankdir = LR
node1[label=node1]
node2[label=node2]
nodeN[label=nodeN]
rnode[label=rnode]
NULL1[label="(*left) NULL",shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
"**left"->NULL1
}
node1->node2->nodeN->NULL1
right->rnode->NULL2
}
```
* 3
```graphviz
digraph graphname{
node[shape=box]
"**left"[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
node1[label=node1]
node2[label=node2]
nodeN[label=nodeN]
rnode[label="(*left)rnode"]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
"**left"->rnode
}
node1->node2->nodeN->rnode->NULL1
}
```
:::info
Reference :
* [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list)
:::
```diff=11
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);
+ list_add_node_t(n->value > value ? &right : &left, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
- CCC;
+ list_concat(&result, pivot); list_concat(&result, right);
*list = result;
}
```
### 2. AAA =`&right`, BBB = `&left`
* 在這個 quicksort implement 裡，是以 `recursion`來進行。 所以用 `!*list` 來檢查是否要將這個函式中止。
* 而在 16~19 行看到將串列的開頭當做 `pivot` 取出後並將其 next 指向 NULL 來使它獨立
* 在找到一個 pivot 後比它大的放到`right`, 比它小的則是放到 `left`，所以 AAA 填入 `&right` BBB 填入 `&left`
* 並以遞迴的方式來繼續排序 `left` 和 `right`
### 3. CCC = `list_concat(&result, pivot); list_concat(&result, right);`
在最後將分開的 list 以 `list_concat()` 做串接，並將`*list` 指向為 result 。
----
## 2.引入其他 [Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)
* 延伸：透過 `time(NULL)` 引入時間參數，來產生 random seed.
* [初探 Linux kernel 亂數產生器 – random generator](https://reurl.cc/undefined)
* [linD026](https://hackmd.io/@linD026/2021q1_quiz1#random-%E5%95%8F%E9%A1%8C)
----
## 3.非遞迴呼叫改寫
:::info
Reference :
1. [Optimized QuickSort — C Implementation (Non-Recursive)
](https://alienryderflex.com/quicksort/)
2. [Iterative Quick Sort](https://www.geeksforgeeks.org/iterative-quick-sort/)
:::
在原本的程式碼使用 recursive function 時,會需要 [function call stack ](https://en.wikipedia.org/wiki/Call_stack) 來紀錄變數、return address 等資訊，並且造成 overhead 減慢速度，所以採用 iterative 來做改寫。
> asd
>
```cpp=
void quicksort_iter(node_t **list)
{
if (!*list)
return;
node_t *stack[MAX_LEVELS];
int top = -1;
stack[++top] = *list;
node_t *partition = NULL;
node_t *result = NULL;
while (top >= 0) {
partition = stack[top--];
if (partition && partition->next != NULL) {
node_t *pivot = partition;
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 ? &right : &left, n);
}
// pivot handling
list_concat(&left, pivot);
// left and right
if (right)
stack[++top] = right;
if (left)
stack[++top] = left;
} else {
/* single pviot*/
top++;
while (top >= 0 && stack[top]->next == NULL) {
node_t *tmp = stack[top--];
list_concat(&result, tmp);
}
}
}
*list = result;
}
```
----
## 延伸問題
2. 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
3. Linux 核心內部也有 linked list 實作，但是 circular doubly-linked list，[linux-list](https://github.com/sysprog21/linux-list) 仿效 Linux 核心的實作並予以簡化，在 `examples/` 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
* 參考資料: [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
4. 研讀 Ching-Kuang Shene ([冼鏡光](https://zh.wikipedia.org/zh-tw/%E5%86%BC%E9%8F%A1%E5%85%89)) 教授撰寫的 [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中
## test
* cppcheck
Sign in with Wallet
Connect another wallet