# 2018q3 Homework3 (list)
contributed by < [`datuiji`](https://github.com/datuiji) >
## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
- macro 在前置處裡階段就會被展開執行，而 function call 則在編譯時才被執行，所以以時間來說 macro 會比 function call 快。函式是拿時間換取空間的，透過執行時期在函式堆疊的切換，相同邏輯區塊只要抽出成為函式，則大家共用同一份程式即可(在記憶體中只有一份實體，較節省記憶體空間)。函式實務上還有另一個好處是可以取得函式位址，也就是說可以把函式當參數。而巨集則是拿空間換取時間，在編譯之前，前置處理器就將該程式替換至各個呼叫區塊，所以相同的邏輯在會重複出現在各個地方，但是由於執行時間不需要在函式堆疊切換，減少時間的耗損。
- 參考資料:
- [Macros vs Functions](https://www.geeksforgeeks.org/macros-vs-functions/)
- [Macros Compared To Functions](http://wiki.c2.com/?MacrosComparedToFunctions)
- [程式設計 微知識(二) 函式(function)與巨集(macro)](https://dotblogs.com.tw/ace_dream/2016/01/16/function_macro)
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
- typeof(x):回傳 x 的型態。用於比較資料型態是否相同。
- 因為 macro 在 preprocess 階段不會做 type checking 所以利用 typeof 可以有效的避免程式發生錯誤。

#define max(a,b) \
  ({ typeof (a) _a = (a); \
      typeof (b) _b = (b); \
    _a > _b ? _a : _b; })

### 解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

- offsetof 定義在 <linux/stddef.h> 中，用來計算某一個struct結構的成員相對於該結構起始位址的偏移量( offset )。(偏移 == 離起始位址有多遠的距離)
- container_of 定義在 <linux/kernel.h> 中，它需要引用 offsetof 巨集，它的作用是用來取得 struct 結構的起始點，只要知道該結構的任一個成員的位址，就可以使用 container_of 巨集來算出該結構的起始位址。
- 參考資料:
- [Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)
- [Linux Kernel: container_of 巨集](http://adrianhuang.blogspot.com/2010/01/linux-kernel-containerof.html)

### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
- 在 [linux/include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中可以看到註解有以下說明:

/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */

- 因為在 linux kernel 中常常會使用到 linked list ，所以先定義 list.h 會省去很多時間。另外操作特定的 linked list 時，例如 list_add_tail 時，如果已經知道 next 或是 prev 時，使用這些預先定義好的 function 可以更有效率的操作 linked list 。
### LIST_POISONING 這樣的設計有何意義？
- 在 [linux/include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中可以看到以下程式碼:

static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

static inline void hlist_del(struct hlist_node *n)
{
	__hlist_del(n);
	n->next = LIST_POISON1;
	n->pprev = LIST_POISON2;
}

- 另外在 [linux/include/linux/poison.h](https://github.com/torvalds/linux/blob/master/include/linux/poison.h) 中可以找到以下註解與程式碼，

/*
 * These are non-NULL pointers that will result in page faults
 * under normal circumstances, used to verify that nobody uses
 * non-initialized list entries.
 */
#define LIST_POISON1  ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x200 + POISON_POINTER_DELTA)

- list_del 除了呼叫 __list_del 之外，還會將 entry 的 prev/next 指標指向LIST_POISON1與 LIST_POISON2 這兩個特別位址。LIST_POISON1與 LIST_POISON2 被定義在 linux/poison.h 中，從註解上來看，當訪問到這兩個特別位址時會發生 page fault 。 LIST_POISON1 與 LIST_POISON2 用來標記那些沒有被初始化以及沒有在鍊表中的 list 項，讓它們不可被訪問。
- 參考資料:
- [Linux鏈結串列struct list_head 研究](https://myao0730.blogspot.com/2016/12/linux.html)
### linked list 採用環狀是基於哪些考量？
- 因為操作容易，不用考慮特殊情況，例如 Singly Linked List 需考慮前端或後端節點的處理方式，然而 Doublely Linked List 則不用考慮此特殊狀況。
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
- list_for_each

/**
 * list_for_each	-	iterate over a list
 * @pos:	the &struct list_head to use as a loop cursor.
 * @head:	the head for your list.
 */
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

- 由定義可以知道是在走訪整個鏈結串列，pos 為一個指標並指向第一個項目(head->next)，以此為起點一路訪問下去，終止條件是當 pos 指向 head 時，代表已經走訪完一圈。
- list_for_each_safe

/**
 * list_for_each_safe - iterate over a list safe against removal of list entry
 * @pos:	the &struct list_head to use as a loop cursor.
 * @n:		another &struct list_head to use as temporary storage
 * @head:	the head for your list.
 */
#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

- 在 list_for_each_safe 中發現多一個變數 n ，首先將 pos->next 存到 n，處理一個流程後再存回 pos，避免拜訪 list 過程中刪除了節點這種情況發生。
- 因此之拜訪 list 不刪除結點時，可以使用 list_for_each()，而當有刪除結點操作時，則要使用 list_for_each_safe()。
- 參考資料:
- [list_for_each()与list_for_each_safe()的区别](http://www.voidcn.com/article/p-fdjvxilx-ba.html)
- [Why do we need list_for_each_safe() in for deleting nodes in kernel linked list?
](https://stackoverflow.com/questions/9207850/why-do-we-need-list-for-each-safe-in-for-deleting-nodes-in-kernel-linked-list)
### for_each 風格的開發方式對程式開發者的影響為何？
- [ ]提示：對照其他程式語言，如 Perl 和 Python
-
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
- [ ] 提示: 對照看 Doxygen
-
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
-
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
-