# 2020q3 Homework1 (quiz1)
contributed by < `grb72t3yde` >
###### tags: `sysprog2020`
---
## 測驗題目
* [2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
## 程式運作原理解釋
### `add entry`函式
* 在此函式中, 我想解釋 **a pointer to a pointer 的引數如何直接對list進行操作**; 因此, 我使用gdb追蹤兩個node的插入行為, 並搭配Graphviz圖像化呈現
1. 首先, 我們在 main function 中的第一個 `add_entry(&head, 72);` call (line 7), step into 進去看
```cpp=
int main(int argc, char const *argv[])
{
node_t *head = NULL;
print_list(head);
add_entry(&head, 72);
add_entry(&head, 101);
...
```
```cpp=
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
assert(new_node); //AA1
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node; //AA2
}
```
進到函式內`node_t **indirect = head;`這行時發現head以及其dereference如下:
![](https://i.imgur.com/1aE56oL.png)
此時狀況以圖形呈現如下, 其中add_entry中的head的位址位於`0x7fffffffdc48`
![](https://i.imgur.com/gAUb38C.png)
2. 接著觀察 `new_node` 在 `malloc` 並將 new_value copy 進去後 (line 5, 6, 7)的情況
![](https://i.imgur.com/ikkPGbG.png)
新配置的間位址在 `0x5555555596b0`; value 已經被assigned為72, 且 `next` 指向 NULL, 如下圖:
![](https://i.imgur.com/Kf5qKdj.png)
3. 由上圖得知, 對 indirect 做 dereference 會得到 main:head 指標, 且其原先指向NULL; 因此第一次插入會直接從 while loop 跳出, 將* indirect指向new_node所指向的位址 (i.e. `0x5555555596b0`) 以完成插入, 如下圖:
![](https://i.imgur.com/FjXZCkU.png)
4. 繼續追蹤`add_entry(&head, 101);`, step into進去看
![](https://i.imgur.com/Ayda7Se.png)
發現malloc為new_node指標配置了別的位址 `0x5555555596d0`, add_entry:head依然指向由引數傳入的reference
5. 此時*indirect為TRUE, 進入while loop body, 來看一下 `indirect = &(*indirect)->next;` 有什麼作用:
![](https://i.imgur.com/58Ve0Qg.png)
注意此處將indirect dereference得到 `0x5555555596b0`, 再以->取得next屬性, 最後用reference of運算子, 變成如下圖:
![](https://i.imgur.com/LiVyH8c.png)
6. 最後一樣用* indirect得到next來將其指向新空間, 完成插入
![](https://i.imgur.com/h8L0eyk.png)
### `remove entry`函式
## 問題
* assert(new_node)在 `AA1` 才做可能造成第六, 七行的 NULL pointer dereference?