# 2019q3 Homework3 (list)
contributed by < `uccuser159` >
## 自我檢查清單
* **為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？**
使用 macro 可以在程式被編譯前就先處理定義的函式或數值，例如：
```css=
#define POWER(x) (x)*(x)*(x)
```
* 使用 macro 會占用較多的記憶體，但程式的控制權不用轉移(即不需要 stack 的push 或 pop)，所以程式執行速度較快，有儲存空間的成本。
* 使用 function call 會占用較少的記憶體，但程式的控制權需要轉移(即需要 stack 的push 或 pop)，所以程式執行速度較慢，有執行時間的成本。
因為 linked list 要用到很多函式來執行一個 task ，所以適合使用 macro 來定義函式來增加執行效率。
* **Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量**
* **GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色**
> [gcc manual](https://gcc.gnu.org/onlinedocs/gcc-9.2.0/gcc.pdf) [6.7] 提到 Another way to **refer to the type of an expression** is with **typeof**
`typeof` 會參考表示式的型態，其宣告方式有兩種：
* With an expression
`typeof (x[0](1))`
假設 x 為陣列透過指標的方式傳入function中，則得到 function 回傳值的 type
* With a type
`typeof (int *)`
得到的 type 是 pointers to int
因為macro本身沒辦法做型態檢查，只是單純的將值帶入並展開，使用 typeof 的話可以讓 macro 在不同 type 的變數皆可以使用，會變得更有彈性。
* **解釋以下巨集的原理**
```cpp
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
`container_of`可以在 struct 中只知道某一 struct 成員的位址的情況下，抓出此 struct 的起始位址。例如：
```cpp=
/* The student structure definition */
typedef struct student {
char name[16];
int id;
char addr[64];
char phone_num[16];
}STUDENT, *STUDENT_PTR;
```
根據上面的 struct ，若我們知道的是某個 student 的 phone_num，要找出此為 student 和 id ，就可以使用`container_of`：
```cpp=
void print_id (char *phone){
STUDENT_PTR someone = NULL;
someone = container_of(phone,struct student,phone_num);
return;
}
```
在 `print_id` 函式中， phone 即為某學生的電話，而`container_of`做了以下這些事：
`(type *) 0)->member`：
將 0 轉成指向 "student" 這個 struct 型態的 pointer，並將 poniter 指向 phone_num
`__typeof__(((type *) 0)->member)`：
取得 phone_num 的 type
`__typeof__(((type *) 0)->member) *__pmember`:
宣告一個型態為 phone_num 的指標 __pmember
`__typeof__(((type *) 0)->member) *__pmember = (ptr)`:
__pmember 得到 phone 的位址
* [offsetof](https://elixir.bootlin.com/linux/latest/source/include/linux/stddef.h#L15) 定義在 </include/linux/stddef.h> 中，用來計算某一個 struct 的成員相對於該結構起始位址的偏移量( offset )
`offsetof(type, member)`：
計算 struct 開頭到 phone_num 這個成員的偏移量
`(type *) ((char *) __pmember - offsetof(type, member))`
得到 struct 的起始位置，並轉成 "student" 這種 struct 型態
* Reference
-[Linux Kernel: container_of 巨集](http://adrianhuang.blogspot.com/2010/01/linux-kernel-containerof.html)
* **除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？**
list.h 內都是 macro 或是 static inline 的宣告，都可以降低時間複雜度，讓執行效能增加，且可以簡化程式設計，像一個功能塊，例如想要檢查一個 linked list 是否為空的，就可以使用`list_empty`，註解提到 Return: 0 - list is not empty !0 - list is empty
```css=
/**
* list_empty() - Check if list head has no nodes attached
* @head: pointer to the head of the list
*
* Return: 0 - list is not empty !0 - list is empty
*/
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
* **LIST_POISONING 這樣的設計有何意義？**
在`list_del()`中：
```cpp=
/**
* list_del() - Remove a list node from the list
* @node: pointer to the node
*
* The node is only removed from the list. Neither the memory of the removed
* node nor the memory of the entry containing the node is free'd. The node
* has to be handled like an uninitialized node. Accessing the next or prev
* pointer of the node is not safe.
*
* Unlinked, initialized nodes are also uninitialized after list_del.
*
* LIST_POISONING can be enabled during build-time to provoke an invalid memory
* access when the memory behind the next/prev pointer is used after a list_del.
* This only works on systems which prohibit access to the predefined memory
* addresses.
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
表示當我們在刪除 linked list 的某個 node 時，因為此 node 只是脫離原本的 linked list，記憶體沒有被釋放掉，反而指向`LIST_POISONING`這個位址，用意為防止讓程式設計者在已被移除的 node 再被用來執行 linked list 相關操作。
* **Linked list 採用環狀是基於哪些考量？**
使用環狀 linked list 演算法較一般的 linked list 來的容易，彈性也較大，因為沒有第一個或是最後一個的問題，操作環狀 linked list 並不因為操作位置的不同而需要有不同的解決方法，例如`list_del`並不會因為 node 的位置不同，而有不同的操作。
* **什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現**
* **什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？**
* **list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？**
這兩個巨集都是走訪 linked list 用的，但是delete 這項操作只能在 list_for_each_safe 中：
```cpp=
/**
* list_for_each_safe - iterate over list nodes and allow deletes
* @node: list_head pointer used as iterator
* @safe: list_head pointer used to store info for next entry in list
* @head: pointer to the head of the list
*
* The current node (iterator) is allowed to be removed from the list. Any
* other modifications to the the list will cause undefined behavior.
*/
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
由於 list_for_each_safe 會預先儲存當前 node 的下一個 node(safe node)，所以即使在當回的迴圈中將 node 才 linked list 中移除，也可以繼續走訪到下一個節點(safe node)
* **for_each 風格的開發方式對程式開發者的影響為何？**
for_each 這種風格的開發方式就像目前深度學習工具 [Keras](https://keras.io/getting-started/functional-api-guide/) 一樣，有許多的API 可供程式開發者使用，可以把原本很複雜的東西用成一個 function 變的簡單易懂，從簡單到複雜，都一步步的指引與解釋。
* **tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？**
unit test 的作用即是在測試每個 list.h 所定義的功能是否執行正確，以`list_del.c`為例，即是在測試 list.h 的 `list_del()`：
```cpp=
#include <assert.h>
#include "list.h"
#include "common.h"
int main(void)
{
struct list_head testlist;
struct listitem item;
INIT_LIST_HEAD(&testlist);
assert(list_empty(&testlist));
list_add(&item.list, &testlist);
assert(!list_empty(&testlist));
list_del(&item.list);
assert(list_empty(&testlist));
return 0;
}
```
此精神即是"Divide and conquer"，將 list.h 的每個 function 先個別拿出來做測試。
* **tests/ 目錄的 unit test 可如何持續精進和改善呢？**
* 參考資料
[rex662624, e94046165 的共筆](https://hackmd.io/@k3hMyB9FTOyoCTcooh_YFA/SyFUZ6YTz?type=view)
Sign in with Wallet
Connect another wallet