---
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,所以這個有一定程度的危險
```c=
#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 ,因此如果重複執行,每次的結果都會一樣,如以下範例:
```c=
#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;
}
```
- 得出來的結果皆會是
```c=
0: 9999188
1: 10000364
2: 9996614
3: 10003534
4: 10000558
5: 9992621
6: 10002100
7: 9999641
8: 9998927
9: 10006453
```
- 因此多會加上利用時間來作為 rand() 的種子
```c=
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() 原始碼
```c=
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.
```c
#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 的應用
```c=
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
### 解釋以下巨集的原理
```c=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
- 首先可以看到,在 ```linux/kernel.h``` 中也有類似的片段
```c=
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
```
- 根據其 macro 的說明意指 container_of 是給定資料結構的成員,回傳其資料結構的位址
```c
/**
* 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
```c=
struct container {
int some_other_data;
int this_data;
}
```
有一個變數 ```int *my_ptr``` 指向 ```this_data``` ,用 container_of 可以找到裝此位址的變數位址,如下
```c=
struct container *my_container;
my_container = container_of(my_ptr, struct container, this_data);
```
- 那回頭來看程式碼怎麼作到的,一開始先宣告出一個相同型態的指標,並且給定位址
```c
const typeof( ((type *)0)->member ) *__mptr = (ptr);
```
- 再來就是要計算位移偏差量
```c
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``` 等等,可以方便性為寫出較好的程式碼,如一開始的註解說明
```c=11
/*
* 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)
```c=
/**
* 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
}
```
```c=
/**
* 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 裡也定義
```c=18
/*
* 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 ,避免刪除的節點索引
```c=436
/**
* 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``` ,因此才會在註解中看到許多@。
```c=
/**
* 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 來做說明
```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()``` 會造成不必要的麻煩,所以應該盡量用原生的方式來做
```c=
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``` 前測試
```make=
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 的排序演算法