---
tags: linyunwen
---

# 2018q1 Homework5 (list)
###### tags: `linyunwen`
contributed by <`LinYunWen`>
- [D05: list](https://hackmd.io/s/HkxZbJzif)

## 生日悖論
### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
- 理解
- 因為如文章裡面所述說道的，直觀上會認為機率就是 $\frac{n}{365}$ ，但是實際上，我們所要找的是```兩人生日相同的機率是多少。而不是你進入了一個有著 22 個人的房間，房間裡有人會和你有相同生日的機率```，因此我們先照文章中所假設的人數為 23 人。
- 接下來就是選擇生日，因為第一個人可以從 365 中任選一天，所以是 $\frac{365}{365} = 1$ ，第二個人因為不能重複，所以它只能從 365 天中的其他 364 天，故是 $\frac{364}{365}$
- 以此類推，依序就會是 $\frac{363}{365}$ 、 $\frac{362}{365}$ 、 $\frac{361}{365}$ ... ，因為只有23個人，所以最後到 $\frac{343}{365}$
- 因此這 23 人不在同一天生日的機率是
$$\frac{365}{365} \times \frac{364}{365} \times \frac{364}{365} ... \frac{343}{365}$$
- 而我們所要尋找的```在同一天生日的機率```即為


$$
\begin{align}
& 1 - \frac{365}{365} \times \frac{364}{365} \times \frac{364}{365} ... \frac{343}{365}\\
&= 1 - \bigg[ 1 \times \bigg(1-\frac{1}{365} \bigg) \times \bigg(1-\frac{2}{365} \bigg) ... \times \bigg(1-\frac{23}{365} \bigg) \bigg]
\end{align}
$$
- 因為自然常數次方的泰勒展開式為

$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ... \\
e^x \approx 1 + x \\
Suppose\ x\ is\ -\frac{a}{365},\ 1 \leq a \leq 23\\
e^{-\frac{a}{365}} \approx 1 - \frac{a}{365}$
- 因此

$p(n) \approx 1 \times e^{-\frac{1}{365}} \times e^{-\frac{2}{365}} \times e^{-\frac{3}{365}} \times ... e^{-\frac{23}{365}}\\
= e^{-\frac{(1+2+3+...+23)}{365}}\\
= e^{-\frac{276}{365}}\\
\approx 0.46946366059$

$1-0.46946366059 = 0.53053633941$
- 若是只有 22 人則為

$1 - \frac{365}{365} \times \frac{364}{365} \times \frac{364}{365} ... \frac{344}{365}\\
= 1 - \dfrac{P_{22}^{365}}{365^{22}}\\
= 1- e^{-\frac{253}{365}}\\
\approx 0.49999824781$

$1-0.49999824781 = 0.50000175219$
- 若只有 21 人

$1 - \frac{365}{365} \times \frac{364}{365} \times \frac{364}{365} ... \frac{345}{365}\\
= 1- e^{-\frac{231}{365}}\\
\approx 0.53106188922$

$1-0.53106188922 = 0.46893811078$
### Birthday problem 對資訊安全的影響在哪些層面？
- 一開始我真的想不到有什麼資訊安全跟 birthday paradox 有關係，所以我先上網查詢，最先查到的就是 [birthday attack](https://en.wikipedia.org/wiki/Birthday_attack) ，但是有些看不懂，只能大概知道他在寫跟機率有相關的部份，於是繼續查才比較了解

- Reference: [The Birthday Problem🎈](https://medium.com/i-math/the-birthday-problem-307f31a9ac6f)
#### birthday attack 介紹：
- 首先要先了解一下雜湊 (hash)
> 所謂『雜湊函數』（Hash Function），是將不定長度訊息的輸入，演算成固定長度雜湊值的輸出，且所計算出來的雜湊值必須符合兩個主要條件：
> (1) 由雜湊值是無法反推出原來的訊息
> (2) 雜湊值必須隨明文改變而改變。
> 也就是說，不同明文所計算出來的雜湊值必須是不相同的，**甚至僅改變明文中任何一個字元時，雜湊值的輸出也必須差異很大**。由此可見，期望中的雜湊值就好像是一個無法冒充的識別碼，且每一份文件都有其特殊的雜湊值，且無法被偽造，故有**數位指紋Digital Fingerprint**之稱。
>
> 一般雜湊函數必須具備下列功能：
> 1. 雜湊函數必須對任意長度的訊息輸入，產生固定長度的雜湊值輸出。
> 2. 對於任意訊息 M，雜湊函數可以輕易的計算出 H(M)，並且可經由硬體或軟體來實現。
> 3. 如果給予雜湊值 h，在計算上是無法找出原訊息 M，使其符合 h = H(M)，此特性稱之為『單向雜湊』（One-way Hash）。
> 4. 對於一個訊息 M1，在計算上是無法找出另一個訊息 M2 （≠ M1），使得 H(M1) = H(M2)。也就是說，給定一個雜湊值（H(M1)），須無法找出另一個訊息（M2），使其所產生的雜湊值相同。
> 5. 就兩訊息 M1、M2 而言，若他們的雜湊值相等，亦即 H(M1) = H(M2)，則 M1 與 M2 兩訊息也一定相等（M1 = M2）；同理，若 H(M1)≠H(M2)，則 M1≠M2。也就是說，給定一個明文與雜湊值，須保證無法找出另一個訊息來產生同樣的雜湊值。
>
> 第4項是雜湊函數最基本功能，亦即給予一段不定長度的訊息，能輕易計算出一個固定長度的雜湊值。如果反過來，給予一個固定長度的雜湊值，是無法計算出原來訊息的，也無法找出可以產生同樣雜湊值的另一段訊息，如能達到此功能，一般稱之為**弱雜湊函數 (Weak Hash Function)**。若再涵蓋第 5 項功能，則稱為**強雜湊函數（Strong Hash Function）**，其表示有了明文與雜湊值，也無法另外偽造一個明文來產生相同的雜湊值。
>
> 基本上，雜湊函數是將原來訊息打亂，得到另一個亂無章法的雜湊值，而且是越亂越好。很不幸的，我們發現**大部分的傳輸訊息都有一定的格式**，譬如:```信件一開始就有 “Dear”，結束時又出現 “Your Best Regards”```。或者資料檔案都有一定的格式，攻擊者既然知道了明文，就可以依照這些標準格式去修改內容，以達到相同的雜湊值。
>
> 我們用一個例子來說明，假設春嬌希望約志明明天見面（See you tomorrow），寫好了信件，並建立了雜湊值（也許經過加密），世雄找出 {See you yesterday}、{See you upset}、{don’t see you again} 等等，只要能符合相同的雜湊值即可，再將偽造信與春嬌簽署的簽署碼（加密的雜湊值）一起發送給志明。
> - Reference: [雜湊](http://www.tsnien.idv.tw/Security_WebBook/%E7%AC%AC%E5%9B%9B%E7%AB%A0%20%E9%9B%9C%E6%B9%8A%E8%88%87%E4%BA%82%E6%95%B8%E6%BC%94%E7%AE%97%E6%B3%95.html)
- 了解完 hash 之後，知道說如果今天想要破解 hash value 就是找出相同的 hash value ，但是以數學的觀點來看訊息經由雜湊演算法計算後，所產生的雜湊碼越長，則可能遺失的訊息就越少；如果採用較短的雜湊碼，可能遺失的訊息相對較多，不同訊息之間產生相同雜湊碼的機會也相對較大，這種觀念如同加密演算法，雜湊碼的位元數越長就越安全，因此攻擊者嘗試用不同的訊息來產生相同的 hash value ，有點像是**暴力攻擊法**，但在雜湊演算法常稱為**生日攻擊法 (birthday attack)**
- 數學上， birthday paradox 是要 n 個人同時在場，他們至少有一組人，生日在同一天的機率會超過 50％ 以上，而現在換成 hash value 問題，變成

> **hacker 要嘗試 n 個訊息，即會有 50％ 以上的機率產生至少一組相同 hash value**

#### birthday attack 數學運算機率
- 假設 hash value 的長度為 64 bits ，照該明文的格式修改其內容，譬如，保留原來空白鍵、使用較接近的文字，製造出其它偽造明文；並經過雜湊演算法計算出是否與原明文相同的雜湊值。
- 因此每次產生不同 hash value 的機率是
$$\frac{2^{64}}{2^{64}} \times \frac{2^{64}-1}{2^{64}} \times \frac{2^{64}-2}{2^{64}} ... \frac{2^{64}-n}{2^{64}}$$
- 會產生相同的機率就是用```全部的機率減掉產生不同的機率```，並且求得大於一半的 n
$$1 - \frac{2^{64} \times (2^{64}-1) \times (2^{64}-2) ... (2^{64}-n)}{2^{64 \times n}} \gt 0.5
$$
$p(n) \approx 1 \times e^{-\frac{1}{2^{64}}} \times e^{-\frac{2}{2^{64}}} \times e^{-\frac{3}{2^{64}}} \times ... e^{-\frac{n}{2^{64}}}\\
= e^{-\frac{(1+2+3+...+n)}{2^{64}}}\\
= e^{-\frac{(1+n)n/2}{2^{64}}}\\
= e^{-\frac{(1+n)n}{2^{65}}}$

$1-e^{-\frac{(1+n)n}{2^{65}}} \gt \frac{1}{2}\\
\frac{1}{2} \gt e^{-\frac{(1+n)n}{2^{65}}}\\
-ln2 \gt -\frac{(1+n)n}{2^{65}}...同取\ ln\\
2^{65} ln2 \lt (1+n)n\\
ln2 \approx 0.69314718056 \approx \frac{1}{2}\\
2^{65}\times \frac{1}{2} \lt (1+n)n\\
2^{64} < (1+n)n\\
n \approx 2^{32} \approx 4294967296$

- 而可以看到一般電腦跑 46 億次，差不多 10s~1m，所以這個有一定程度的危險

    #include <stdio.h>
    #include <time.h>

    int main() {
        long int i = 0;
        time_t start, end;

        time(&start);
        while (i < 4294967296) {
            i++;
        }
        time(&end);
        printf("time: %lf\n", difftime(end, start));
        return 0;
    }
    // output: time: 9.000000

### 像是 Random Number Generator 這樣的產生器，是否能產生「夠亂」的亂數呢？
- 基本上操作適當的話是可以作到夠亂的亂數，如 c 裡的 rand() 他的種子預設為 0 ，因此如果重複執行，每次的結果都會一樣，如以下範例：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    unsigned long int arr[10] = {0};
    for (unsigned long int i = 0; i < 100000000; i++) {
        arr[rand()%10]++;
    }

    for (int i = 0; i < 10; i++) {
        printf("%d: %lu\n", i, arr[i]);
    }
    return 0;
}

- 得出來的結果皆會是

0: 9999188
1: 10000364
2: 9996614
3: 10003534
4: 10000558
5: 9992621
6: 10002100
7: 9999641
8: 9998927
9: 10006453

- 因此多會加上利用時間來作為 rand() 的種子

srand(time(NULL));

- 因為基本上時間都會是唯一的，因此適合拿來做種子，但是若這隨機的程式攸關安全性，應該要具備不可預測性，而不是任何人都可以猜到的時間，因此有些程式或是硬體

> 為了滿足更嚴格的需求，現代的作業系統會定期蒐集硬體訊號攪拌入系統內建的位元池當中，供給應用程式作為產生亂數的依據。一些可能被使用的資訊像是：兩次鍵盤觸發的時間間隔、滑鼠移動距離、中斷觸發的時間間隔、甚至是各種硬體雜訊。這些資訊非常難以全盤掌握而且持續在更新，所以遠比純粹數學的方法安全，但也不是完全不可能破解。如果一個系統接受外部資訊的管道很少，理論上有可能被有心人士摸清內部狀態，甚至這些管道也有機會被操弄。
> Reference: [電腦的隨機數是如何做到的?](http://novus.pixnet.net/blog/post/32238099-%E9%9B%BB%E8%85%A6%E7%9A%84%E9%9A%A8%E6%A9%9F%E6%95%B8%E6%98%AF%E5%A6%82%E4%BD%95%E5%81%9A%E5%88%B0%E7%9A%84%3F)

- 但是事實上，這些亂數方式，看似是隨機，其實仍然是由一套明確的操作運算出來，如 c rand() 原始碼

    long int
    random (void)
    {
      if (rand_type == TYPE_0)
        {
          state[0] = ((state[0] * 1103515245) + 12345) & LONG_MAX;
          return state[0];
        }
      else
        {
          long int i;
          *fptr += *rptr;
          /* Chucking least random bit.  */
          i = (*fptr >> 1) & LONG_MAX;
          ++fptr;
          if (fptr >= end_ptr)
        {
          fptr = state;
          ++rptr;
        }
          else
        {
          ++rptr;
          if (rptr >= end_ptr)
            rptr = state;
        }
          return i;
        }
    }

> Reference: [gcc(github)](https://github.com/gcc-mirror/gcc/blob/master/libiberty/random.c)、[What common algorithms are used for C's rand()?](https://stackoverflow.com/questions/1026327/what-common-algorithms-are-used-for-cs-rand)
- 可以很明顯的看到這是一組可預期的數學運算，這一來其未必能稱作是真正的隨機，真正的隨機是不可預期，所以這些看似隨機卻並不是真正隨機的方式，稱具有[偽隨機性(Pseudorandomness)](https://zh.m.wikipedia.org/zh-tw/%E4%BC%AA%E9%9A%8F%E6%9C%BA%E6%80%A7)，如果直接下 ```man rand``` 看到說明第一句也程述出

    The rand() function returns a pseudo-random integer in the range 0 to
    RAND_MAX inclusive (i.e., the mathematical range [0, RAND_MAX]).

- 因此對現在一般的電腦來說是不可能運算出真正的隨機，頂多使得這個類似隨機的機制夠亂、夠不可預期，或許如老師所說，之後的量子電腦將會成功時做出真正的亂數產生器
- Reference: [你的程式夠「亂」嗎？](https://www.ithome.com.tw/voice/110007)、[man rand(3)](http://man7.org/linux/man-pages/man3/rand.3.html)、[量子電腦－曙光乍現](https://portal.stpi.narl.org.tw/index/article/10374)、[【量子密碼】亂數試金石](https://case.ntu.edu.tw/blog/?p=3131)

## Linux 風格的 linked list
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
- 首先可以先理解兩者的差別
- 最主要的差別在於 macro 會在 compile 前，行處理，把該體換的地方替換掉，因此不像 function 一樣需要傳入參數，或是呼叫時要先紀錄狀態等等，相對的執行速度上就會較快，但是其是以空間換取時間的方式進行，而且 macro 的置換有相對的問題存在，如：operators priority、condition flow 等等
- e.g.

    #define square(a) a*a
    square(5) --> 5*5 --> 25
    square(1+2) --> 1+2*1+2 --> 5 // unexpected

- 整理出來就是
- **Advantages**
* It's preprocessed.
* Not need to pass arguments like function.
* Time efficiency.
* **Disadvantages**
* Very hard to debug in large code.
* Take more memory in stack compare to function.

- 因此可以推測經常性使用的 linked list 用 macro 方式去編寫，可以提高速度

- Reference: [What is the difference between a macro and a function in C？](https://stackoverflow.com/questions/4990362/what-is-the-difference-between-a-macro-and-a-function-in-c)、[Macros vs Functions](https://www.geeksforgeeks.org/macros-vs-functions/)

### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
- linux 的 file system 即是一個 linked list 的應用

    struct file {
        ...
        struct path		f_path;
        struct inode		*f_inode;	/* cached value */
        const struct file_operations	*f_op;
        
        ...
        spinlock_t		f_lock;
        enum rw_hint		f_write_hint;
        atomic_long_t		f_count;
        unsigned int 		f_flags;
        fmode_t			f_mode;
        struct mutex		f_pos_lock;
        loff_t			f_pos;
        ...

- CPU 的排程
// TODO: complete here
- Reference: [Linux 當中的 VFS 虛擬檔案系統](http://sp1.wikidot.com/linuxvfs)、[The Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html)

### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
- typeof 是回傳這個變數的 type 的 function
- e.g. typeof(int a) 回傳 int

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

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

- 首先可以看到，在 ```linux/kernel.h``` 中也有類似的片段

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

- 根據其 macro 的說明意指 container_of 是給定資料結構的成員，回傳其資料結構的位址

    /**
    * container_of - cast a member of a structure out to the containing structure
    * @ptr:    the pointer to the member.
    * @type:   the type of the container struct this is embedded in.
    * @member: the name of the member within the struct.
    *
    */

e.g. 給定一個資料結構 container

    struct container {
      int some_other_data;
      int this_data;
    }

有一個變數 ```int *my_ptr``` 指向 ```this_data``` ，用 container_of 可以找到裝此位址的變數位址，如下

    struct container *my_container;
    my_container = container_of(my_ptr, struct container, this_data);

- 那回頭來看程式碼怎麼作到的，一開始先宣告出一個相同型態的指標，並且給定位址

    const typeof( ((type *)0)->member ) *__mptr = (ptr);

- 再來就是要計算位移偏差量

    offsetof(type,member)

- 最後將指標位置減去偏差量，就可以得到此資料結構的位址

    struct container
    +-----------------+    ^
    +   some_data     +    |  offset
    +-----------------+ <---- my_ptr 
    +   this_data     + 
    +-----------------+ 

- Reference: [Understanding container_of macro in the Linux kernel](https://stackoverflow.com/questions/15832301/understanding-container-of-macro-in-the-linux-kernel/15832614)、[Linked List in Linux Kernel](http://neokentblog.blogspot.tw/2008/01/linked-list-in-linux-kernel.html)、[Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.tw/2016/09/linuxcontainerof-offsetof.html)
### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
- 還有像 ```list_replace``` 、```list_empty``` 、 ```list_move_tail``` 這接雖然未必是必要的存在，但是如果有這些 function 可以使得工程師撰寫程式的負擔下降
- 而且光是 add 操作就有很多種 ```list_add_valid``` 、```hlist_add_behind``` 、```hlist_add_before``` 等等，可以方便性為寫出較好的程式碼，如一開始的註解說明

    /*
     * 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.
     */

### LIST_POISONING 這樣的設計有何意義？
- 參考 [ecsv/linux-like-list/list.h](https://github.com/ecsv/linux-like-list/blob/master/list.h)

    /**
     * list_del() - Remove a list node from the list
     * @node: pointer to the node
     * 
     * ...
     * ...
     * 
     * 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
    }

     /**
     * hlist_del() - Remove a hlist node from the hlist
     * @node: pointer to the node
     *
     * ...
     * ...
     * 
     * 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 an
     * hlist_del. This only works on systems which prohibit access to the predefined
     * memory addresses.
     */

- 此外 linux/list.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)

- 是希望避免在 node 被 delete 之後，其記憶體區塊還未被釋放，若此時取用其 next or prev， access 到不合法的記憶體區段
### linked list 採用環狀是基於哪些考量？
1. 它可以雙向，並且從任一點，從頭到尾，也可以從尾到頭
2. 而且到 tail 要回到 head 只需要 O(1) 的操作

### list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？
- 可以看到在說明敘述中， ```list_for_each_save``` 是安全的走訪每一個 node ，避免刪除的節點索引

    /**
     * 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)

- 可以看到兩者相比，多了第 444 行，就是避免 pos 節點被刪除，但是卻又在 for 之後 ```pos=pos->next;``` 就會是錯誤的狀況，所以先複製一個 pos 暫存於 n 再往下走訪

### for_each 風格的開發方式對程式開發者的影響為何？
- for_each 的開發方式對工程師而言，算是比較和善的，因為相較普通的 for loop 需要給定明確的邊界範圍，而 for_each 可以自動判斷，都是要對物件中的每一個元素做相同的操作，如果程式可以自行判斷範圍在哪，對工程師來說會是比較容易的，也使得程式碼較為簡潔。

### 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
- 這個非常的特別，要說到 Doxygen 工具，他是一套可以將註解自動轉換成說明文件的工具，有點類似 python 的 docstring。
- 因為在開發中若要讓人快速理解函式是在做什麼的就要那個 function 的說明，但是若編寫程式而要另外再寫一份說明文件著實有點麻煩，因此利用 Doxygen 可以將 function 上方的註解區塊轉換成 function 說明文件，因次 Doxygen 的語法中對參數的定義即是 ```@params``` ，因此才會在註解中看到許多＠。

/**
 * container_of() - Calculate address of object that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of object containing ptr
 */

- 而不只 c 有在使用，它也可以用在 C++/C#/Java
- Reference: [Doxygen parameter](https://www.stack.nl/~dimitri/doxygen/manual/commands.html#cmdparam)

### tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
- 先以 list_add.c 來做說明

#include <assert.h>
#include "list.h"

#include "common.h"

int main(void)
{
    struct list_head testlist;
    struct listitem item1;
    struct listitem item2;
    struct listitem item3;
    struct listitem item4;
    struct listitem *item = NULL;
    size_t i;

    item1.i = 1;
    item2.i = 2;
    item3.i = 3;
    item4.i = 4;

    INIT_LIST_HEAD(&testlist);
    assert(list_empty(&testlist));

    list_add(&item1.list, &testlist);
    list_add(&item3.list, &item1.list);
    list_add(&item2.list, &item1.list);
    list_add(&item4.list, &item3.list);

    i = 1;
    list_for_each_entry (item, &testlist, list) {
        assert(item->i == i);
        i++;
    }
    assert(i == 5);

    return 0;
}

- 可以看到這段程式碼，主要宣告變數、初始化，並且重點是 24～27 用了四次 ```list_add``` ，然後再去用 ```assert()``` 檢查，所作的跟變化跟預期有沒有相同，因此這個 unit test 檔就是用來測試 ```list_add``` 是否有誤，其他在 tests/ 下的檔案皆是這個概念。
- 單元測試在軟體工程來說是非常重要的一環，有了單元測試在做 refactor 時，會相對比較容易而且比較不會出錯，如果對更進階的想法來說，編寫程式同時編寫測試案例，甚至有時會先撰寫測試案例，這就比較偏向 TDD (Test-Driven-Develop)，就是因為你會先知道要測試什麼，而實做出來的功能才不會開發過度，甚至知道有什麼功能應該要捨棄。
- Reference: [【單元測試】改變了我程式設計的思維方式](http://www.codedata.com.tw/java/unit-test-the-way-changes-my-programming)、[不會寫 unit tests](http://teddy-chen-tw.blogspot.tw/2011/11/unit-tests.html)

### tests/ 目錄的 unit test 可如何持續精進和改善呢？
- 首先感覺可以把測試的單元再縮小，盡量一個檔案裡呼叫到一個就好，比如 list_add.c 中除了 ```list_add()``` ，還有第 30 行呼叫到 ```list_for_each_entry()``` 如果在測試時，出錯的卻是 ```list_for_each_entry()``` 會造成不必要的麻煩，所以應該盡量用原生的方式來做

    for (item = list_entry((&testlist)->next, __typeof__(*item), list); 
         &entry->list != (&testlist);                                     
         item = list_entry(item->list.next, __typeof__(*item), list))  {
        assert(item->i == i);
        i++;
    }

- 如果真的無法再拆開的話，被呼叫到的函數應該放在較前面的測試案例，也就是說 Makefile 裡， ```list_for_each_entry()``` ，要在 ```list_add``` 前測試

    TESTS = \
        containerof \
        list_entry \
        list_init-explicit \
        list_init-local \
        list_init-global \
        list_add \
        list_add_tail \
        list_del \
        list_del_init \
        list_first_entry \
        list_last_entry \
        list_is_singular \
        list_for_each_safe \
        list_for_each_entry_safe \
        list_for_each \
        list_for_each_entry \
        list_move \
        list_move_tail \
        list_splice \
        list_splice_tail \
        list_splice_init \
        list_splice_tail_init \
        list_cut_position

## 針對 linked list 的排序演算法