# 2020q3 Homework1 (quiz1)
contributed by < `MingRuey` >
### **測驗1**
程式運作原理
---
### **add_entry**
---
先創造一個值為 new_value 的節點之後，用 assert 檢查新節點是否創成功。
> :warning: TODO: 研究為什麼 assert 在 ```new_node->value``` , ```new_node->next``` 賦值後面，而不是前面，這樣的寫法在 mallloc 失敗的時候行為是什麼?
接著理解如何用 pointer to pointer 在 linked list 的尾巴擺上剛剛創造的節點:
首先我們有個串列
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
}
```
接著研究 while 迴圈的判斷式 ```*indirect```，*indirect 的型態是 pointer *node_t ，在一開始 *indirect 會取出 head 的地址:
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
indirect [label="{indirect|**head\n=&(node_t *node1)}"]
indirect -> 1:address [color=red];
}
```
接著來看 ```indirect = &(*indirect)->next``` 一行， ```(*indirect)->next``` 的型態是 pointer *node ，指向 pseudo pointer 的 next ， & operator 使得 **indirect 的值為 next 地址** :
```graphviz
digraph indirect_next{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|<next>next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
indirect [label="{indirect|&((&node1)\-\>next)}"]
indirect -> 1:next [color=red];
}
```
這個過程會反覆到 *indirect 為 null pointer 為止，也就是如下圖的狀況:
```graphviz
digraph endgame{
rankdir=LR;
node [shape=record];
last [label="{<address>&|node ...|{value|next}|{...|<ref>&end}}"];
end [label="{<address>&end|node end|{value|<next>next}|{...|<ref>null}}"];
last:ref -> end:address [color=black];
indirect [label="{indirect|&((&end)\-\>next)}"]
indirect -> end:next [color=red];
}
```
離開迴圈之後， ```*indirect = new_node``` 讓 indirect 的內容，也就是 end 的 next 更新為新創造的 new_node，完成新增節點在結尾:
```graphviz
digraph endgame{
rankdir=LR;
node [shape=record];
last [label="{<address>&|node ...|{value|next}|{...|<ref>&end}}"];
end [label="{<address>&end|node end|{value|<next>next}|{...|<ref>&new}}"];
new [label="{<address>&new|node new|{value|next}|{...|<ref>null}}"];
last:ref -> end:address [color=black];
end:ref -> new:address [color=black];
indirect [label="{indirect|&((&end)\-\>next)}"]
indirect -> end:next [color=red];
}
```
### **find_entry**
---
find_entry 的運作相對來說比較簡單，一開始 current 指向 head 的地址:
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
current [label="{current|*head\n=&node1}"]
current -> 1:address [color=red];
}
```
接著研究 for loop 終止的條件 ```current && current->value != value``` 也就是 current 是 null pointer 或是 current 就是要尋找的值，搭配每圈 ```current = current->next``` 的更新，在 ```current->value == value``` 的情況下，會回傳當前的節點:
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
current [label="{current|&2\n=回傳值}"]
current -> 2:address [color=red];
}
```
另外一種情況則是 current 為 null pointer 跳出迴圈，也就是已經遍歷了整個串列的情況，此時就會回傳 null pointer:
```graphviz
digraph indirect{
rankdir=LR;
node [shape=record];
previous [label="{<address>&...|node ...|{value|next}|{...|<ref>&end}}"];
end [label="{<address>&end|node end|{value|next}|{end|<ref>null}}"];
previous:ref -> end:address [color=black];
current [label="{current|null\n=回傳值}"]
current -> end:ref [color=red];
}
```
### **remove_entry**
---
remove_entry 的寫法思路跟跟之前的 add_entry 相似，只差在 while loop 終止的判斷式以及離開迴圈之後的行動，我們先看終止條件 ```(*indirect) != entry``` :
```graphviz
digraph indirect_next{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|<next>next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
indirect [label="{indirect|&((&node1)\-\>next)}"]
indirect -> 1:next [color=red];
}
```
```*indirect``` 會取到 ```**indirect``` 指向的 next 的值 (第一次進行時則是 &head )，所以判斷式會與目標地址 ```*entry``` 比較，如果一樣才會離開迴圈。
接著離開迴圈之後的行為，```*indirect = entry->next``` 會把 indirect 指向的記憶體位置的內容以 ```entry->next``` 複寫:
```graphviz
digraph indirect_next{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|<next>next}|{1|<ref>&3}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 3:address [color=black];
2:ref -> 3:address [color=black];
indirect [label="{indirect|&((&node1)\-\>next)}"]
indirect -> 1:next [color=red];
}
```
另外我們注意包刮 entry 是 null pointer，或是 entry 沒找到的情況下，傳入 ```free(entry)``` 的內容會是 null pointer ，此時根據 C99 ，free 函式會什麼都不做，所以 remove_entry 在這兩個情況下都是安全的:
> C99 7.20.3.2.2
>
> The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation. If ptr is a null pointer, no action occurs. Otherwise, if
the argument does not match a pointer earlier returned by the calloc, malloc, or realloc function, or if the space has been deallocated by a call to free or realloc, the behavior is undefined.
### **swap_pair**
---
for loop 的初始條件 ```node_t **node = &head``` 讓我們產生與 add_entry 相同的初始狀態:
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
pnode [label="{node|&head\n=&(node_t *node1)}"]
pnode -> 1:address [color=red];
}
```
接著判斷條件 ```*node && (*node)->next``` 判斷當前的 node 與串列中下一個 node 都非 null pointer ，也就是節點存在，才會進行 for loop 內 swap 的動作，之後用 ```node = &(*node)->next->next``` 將 node 往前移動兩個節點:
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
pnode [label="{node|&(node_t *node1)\-\>next\-\>next\n=&node3}"]
pnode -> 3:address [color=red];
}
```
接著我們圖示化 swap 的過程:
```note_t *tmp = *node``` :
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>¤t|node current|{value|next}|{c|<ref>&after}}"];
2 [label="{<address>&after|node after|{value a|next}|{a|<ref>&upcomming}}"];
3 [label="{<address>&upcomming|node upcomming|{value|next}|{...|}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
pnode [label="{node|&(node_t *current)}"]
pnode -> 1:address [color=red];
tmp [label="{tmp|*node\n=node_t *current}"]
tmp -> 1:address [color=red];
}
```
```*node = (*node)->next``` :
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>¤t|node current|{value|next}|{c|<ref>&after}}"];
2 [label="{<address>&after|node after|{value a|next}|{a|<ref>&upcomming}}"];
3 [label="{<address>&upcomming|node upcomming|{value|next}|{...|}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
tmp [label="{tmp|node_t *current}"]
tmp -> 1:address [color=red];
pnode [label="{node|(*node)\-\>next\n=&(note_t *after)}"]
pnode -> 2:address [color=red];
}
```
```tmp->next = (*node)->next``` :
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>¤t|node current|{value|next}|{c|<ref>&upcomming}}"];
2 [label="{<address>&after|node after|{value a|next}|{a|<ref>&upcomming}}"];
3 [label="{<address>&upcomming|node upcomming|{value|next}|{...|}}"];
1:ref -> 3:address [color=black];
2:ref -> 3:address [color=black];
tmp [label="{tmp|node_t *current}"]
tmp -> 1:address [color=red];
pnode [label="{node|&(note_t *after)}"]
pnode -> 2:address [color=red];
}
```
```(*node)->next = tmp``` ，至此 after 跟 current 已經交換過來，也注意到這時候 node 如果照上述討論往前走兩個 node ，就指向了下一個要交換的節點 upcomming :
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>¤t|node current|{value|next}|{c|<ref>&upcomming}}"];
2 [label="{<address>&after|node after|{value a|next}|{a|<ref>¤t}}"];
3 [label="{<address>&upcomming|node upcomming|{value|next}|{...|}}"];
1:ref -> 3:address [color=black];
2:ref -> 1:address [color=black];
tmp [label="{tmp|node_t *current}"]
tmp -> 1:address [color=red];
pnode [label="{node|&(note_t *after)}"]
pnode -> 2:address [color=red];
}
```
### **reverse**
---
首先我們來看起串列的起頭是如何正確被反轉的，一開始 ```node_t *cursor``` 設為 NULL 以及 ```node_t *next = head->next``` :
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>&2}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
1:ref -> 2:address [color=black];
2:ref -> 3:address [color=black];
head [label="{head|&1}"];
head -> 1:address [color=red]
cursor [label="{cursor|NULL}"]cursor
next [label="{next|head\-\>next\n}"]
next -> 2:address [color=red]
}
```
接著反接的過程 (1) ```head->next = cursor``` :
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>NULL}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
2:ref -> 3:address [color=black];
head [label="{head|&1}"];
head -> 1:address [color=red]
cursor [label="{cursor|NULL}"];
next [label="{next|head\-\>next\n}"];
next -> 2:address [color=red];
}
```
反接的過程 (2) ```cursor = head``` :
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>NULL}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
2:ref -> 3:address [color=black];
head [label="{head|&1}"];
head -> 1:address [color=red]
cursor [label="{cursor|head}"]cursor
cursor -> 1:address [color=red]
next [label="{next|head\-\>next\n}"]
next -> 2:address [color=red]
}
```
反接的過程 (3) ```head = next``` :
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>NULL}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&3}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
2:ref -> 3:address [color=black];
head [label="{head|&2}"];
head -> 2:address [color=red]
cursor [label="{cursor|head}"]cursor
cursor -> 1:address [color=red]
next [label="{next|head\-\>next\n}"]
next -> 2:address [color=red]
}
```
我們可以看到 while loop 執行一次， head 指向的節點的 next 會指向 cursor 的值 (在第一次執行時是 NULL)，而且 head 跟 next 在結束的時候會指向 cursor 的下一個節點，所以再跑一次迴圈就會得到:
```graphviz
digraph init{
rankdir=LR;
node [shape=record];
1 [label="{<address>&1|node 1|{value|next}|{1|<ref>NULL}}"];
2 [label="{<address>&2|node 2|{value|next}|{2|<ref>&1}}"];
3 [label="{<address>&3|node 3|{value|next}|{...|<ref>}}"];
2:ref -> 1:address [color=black];
head [label="{head|&2}"];
head -> 3:address [color=red]
cursor [label="{cursor|head}"]cursor
cursor -> 2:address [color=red]
next [label="{next|head\-\>next\n}"]
next -> 3:address [color=red]
}
```
也就是每跑一次，可以完成 ```cursor``` 與 ```cursor->next``` 的反接 (第一次執行完成 head 與 NULL 的反接!)，並且把 head 與 next 指向下一個反接的節點，直到 head 為 null pointer 為止。
### 延伸問題 1 :
---
:::info
函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標;
:::
```c
void swap_pair(node_t **head)
{
for (node_t **current = head;
*current && (*current)->next;
current = &(*current)->next->next) {
node_t *tmp = *current;
*current = (*current)->next;
tmp->next = (*current)->next;
(*current)->next = tmp;
}
}
```
跟原本的 swap_pair 可以說幾乎沒有改動，只是請使用者把 ```node_t *head``` 的地址傳進來而已。
```c
void reverse(node_t **head)
{
node_t *cursor = NULL;
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
}
*head = cursor;
}
```
注意到改過的版本與原本幾乎一樣，如果比較程式，會發現只差在將原本程式碼中的 ```head``` 全部取代為 ```*head``` (並加上合適的括號)，以及最後的 ```return cursor``` 改為直接修改 head 的值 ```*head = cursor```。也就是使用者給我們一個 node_t* 的地址 (type = node_t**)，我們直接修改該地址的內容。
### 延伸問題 2 :
---
:::info
以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive;
:::
```c
/*
* Reverse linked-list 'head', attach the reversed end to tail.
*/
void rev_recursive(node_t **head, node_t *tail)
{
node_t *next = (*head)->next;
node_t *current = *head;
current->next = tail;
if (!next) { return; }
*head = next;
rev_recursive(head, current);
}
void reverse(node_t **head)
{
rev_recursive(head, NULL);
}
```
思路是將 reverse 重新想成一個函示 ```f(linked-list, node)```: 此函式輸入一個串列跟一個節點，將串列反轉，反轉之後將尾端接上輸入的節點。如此一來，我們原本的 reverse 就等價於 f(head, NULL)。而 ```f``` 可以被寫成遞迴的形式 :
```c
// Pseudo Code
f(head, node)
{
head->next = node;
if (head is end) { return; }
f(next node, head);
}
```
想到這點構造出上面給定的程式就不困難了，終止條件也非常簡單，就是 ```head->next``` 是 null pointer。
### 延伸問題 3 :
---
:::success
針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;
:::
```c
// Get length of single linked-list
int getlength(node_t *head)
{
int len = 0;
while (head) {
head = head->next;
len++;
}
return len;
}
// Move pointer k steps forward
void to_kth_node(node_t **start, int k)
{
while (k--) {
if (!(*start)) { break; }
*start = (*start)->next;
}
}
// Swap positions of two nodes in linked-list
void swap_inplace(node_t *node1, node_t *node2)
{
node_t tmp = *node1;
*node1 = *node2;
*node2 = tmp;
node2->next = node1->next;
node1->next = tmp.next;
}
// Fisher-Yates shuffle on single linked-list, inplace.
void fyshuffle(node_t **head)
{
unsigned int randseed = time(NULL);
node_t *current = *head;
for (int len = getlength(*head); len > 1; len--) {
int rnd = rand_r(&randseed) % len;
node_t *target = current;
to_kth_node(&target, rnd);
swap_inplace(target, current);
current = current->next;
}
}
```
設置好亂數的種子後，先將串列走一遍來取得長度 ```len```，迴圈就透過遞減 ```len```，來記錄下尚未「洗牌」的節點數量，如果超過兩個就進行後面的洗牌動作:
1. 從 [0, len) 中產生一個數字 ```rnd```
2. 創造一個指標指向最前端且尚未被洗牌過的節點 ```current```，並且往後移動 ```rnd``` 步，即程式碼中的 ```target```。
3. 接著就把最前端的節點 ```current``` 跟 ```target``` 交換，然後把 ```current``` 往後移動一步。
> :warning: TODO: (1) 設計測試驗證洗牌的均勻度 (2) 量測並試著減少記憶體用量
> :warning: TODO
rand_r 的[文件](https://linux.die.net/man/3/rand_r)指出:
> The function rand() is not reentrant, since it uses hidden state that is modified on each call. This might just be the seed value to be used by the next call, or it might be something more elaborate. In order to get reproducible behavior in a threaded application, this state must be made explicit; this can be done using the reentrant function rand_r().
=> 研究這段是什麼意思
Sign in with Wallet
Connect another wallet