# 2016q1 Homework2 (B) unit-test
作業要求 (B)
* 學習GDB (GNU Debugger)，透過GDB進行unit testing
* 在 GitHub 上 fork [unit-tests](https://github.com/embedded2016/unit-tests)，並依據 [第三週](https://embedded2016.hackpad.com/ep/pad/static/kpfgwU6YgOF) 課堂 code review 的認知，指出給定程式不足之處
* 補強給定程式的 swap() 和 bubble_sort() 函式，並且研究如何用 GDB 進行自動測試
* 實做 Merge sort，可參見 [競技程式設計課程的解說](http://wiki.csie.ncku.edu.tw/acm/course/Review1)，需要提供以下檔案:
* merge.c: merge_sort() 函式的實做
* test-merge.sh: 測試 merge_sort() 函式的 GDB script
* data-merge.in: 用來測試的輸入資料，原則上與 data-bubble.in 相仿
* 將你學習 GDB 的過程、指出原本程式不足之處 (程式碼寫出來就是給你改進的，可不是給你背誦用！)、如何修正和強化程式，以及在實做 merge sort 的各項啟發，紀錄於 「[作業區](https://embedded2016.hackpad.com/2016q1-Homework-2-v37rXPJjRlW)」，記得標注「開發紀錄(B)」
## GDB學習
先來測試跟學一些指令，編譯程式需要加上 -g，執行加上 gdb
```
gcc -g -o swap swap.c
gdb ./swap
```
指定breakpoint，因爲只是測試先，所以我在程式裏加上了main
```
(gdb) b main
Breakpoint 1 at 0x400733: file swap.c, line 99.
```
開始執行
```javascript=
(gdb) r
Starting program: /home/tempo/Desktop/hw2/unit-tests/swap
Breakpoint 1, main () at swap.c:99
99 return 0;
(gdb) p $head //建立一個head，p = print
$1 = void
(gdb) source scripts/create_list.gdb //讀入gdb script
(gdb) source scripts/print_list.gdb
(gdb) source scripts/free_list.gdb
(gdb) create_list $head 4 //利用剛剛的head建立一個4個node的list
(gdb) printf_list $head //輸出list,結果是0，1,2,3
$28 = (List *) 0x602010
$29 = 0
$30 = (struct List_node *) 0x602030
$31 = 1
$32 = (struct List_node *) 0x602050
$33 = 2
$34 = (struct List_node *) 0x602070
$35 = 3
$36 = (struct List_node *) 0x0
/* 測試程式的swap，結果應該要爲2,1,0,3 */
(gdb) p $head = swap($head ,$head , $head->next->next)
$37 = (List *) 0x602050
(gdb) printf_list $head
$38 = (List *) 0x602050
$39 = 2
$40 = (struct List_node *) 0x602030
$41 = 1
$42 = (struct List_node *) 0x602010
$43 = 0
$44 = (struct List_node *) 0x602070
$45 = 3
$46 = (struct List_node *) 0x0
```
## Swap.c 程式碼分析
1. 剛開始的 If 應該要用 || 而不是 &&
```clike=
if (!head ||
(node_1 == NULL) || (node_2 == NULL) ||
(node_1 == node_2))
return head;
```
尋找node的迴圈應該設定一個break condition已節省時間，然後判斷是不是head的部分也可以先做，如果有其中一個是head，那就只需尋找另一個node就好了。因此就在尋找node的迴圈裏加入多一個condition。另外還有判斷circular linked list，也防止無限迴圈。
好奇circular linked list的定義，如果尾巴跟中間的節點相連這也算嗎？
```clike=
if (head == node_1) {
pre_node_1 = NULL;
num_pre_node_1_and_node_2 = num_pre_node_1_and_node_2 + 1;
}
if (head == node_2) {
pre_node_2 = NULL;
num_pre_node_1_and_node_2 = num_pre_node_1_and_node_2 + 1;
}
/* 這裏加多一個判斷num_pre_node_1_and_node_2 是不是小於2 */
while ( (head && head->next) || num_pre_node_1_and_node_2 < 2 ) {
if (head->next == node_1) {
pre_node_1 = head;
num_pre_node_1_and_node_2 = num_pre_node_1_and_node_2 + 1;
/* 判斷circular，不過也只能判斷出尾跟頭相連罷了 */
if(node_1->next == _head)
is_circular = true;
}
else if (head->next == node_2) {
pre_node_2 = head;
num_pre_node_1_and_node_2 = num_pre_node_1_and_node_2 + 1;
if(node_2->next == _head)
is_circular = true;
}
head = head->next;
}
```
3.修改一些地方跟加上做circular的部分
```clike=
if (pre_node_1 == NULL) {
pre_node_2->next = node_1;
tmp_node = node_1->next;
/* circular linked list */
if(is_circular)
node_1->next = node_2;
else
node_1->next = node_2->next;
node_2->next = tmp_node;
return node_2;
}
```
最後檢查輸出有沒有問題（一部分）：
```javascript=
$28 = "old_list"
$29 = (List *) 0x602010
$30 = 0
$31 = (struct List_node *) 0x602030
$32 = 1
$33 = (struct List_node *) 0x602050
$34 = 2
$35 = (struct List_node *) 0x602070
$36 = 3
$37 = (struct List_node *) 0x0
$38 = (List *) 0x602010
$48 = "change 1 3" //換掉第一個跟第三個node
$49 = "new_list"
$50 = (List *) 0x602050
$51 = 2
$52 = (struct List_node *) 0x602030
$53 = 1
$54 = (struct List_node *) 0x602010
$55 = 0
$56 = (struct List_node *) 0x602070
$57 = 3
$58 = (struct List_node *) 0x0
$59 = (List *) 0x602050
```
## Bubble.c 程式碼分析
1\. 首先是刪除一些不必要的code，第一個迴圈計算list的長度，裏面還有做了一點sort，在這裏的這個sort是不必要的，所以就把它刪了。還有加上circular的判斷，也避免無限迴圈：
```clike=
while (sub_head && sub_head->next) {
num_list = num_list + 1;
/* Circular list */
if(sub_head->next == *head)
break;
sub_head = sub_head->next;
}
```
2.再來是以下這行有點奇怪，首先一開始就有判斷head是不是空的，也可以利用剛剛計算的 num_list來確認list到底是不是空的，所以這個有點不必要
` for (*head && (*head)->next; i < sub_for_times; i++) `
* 因此我把它改成利用num_list來做最後的sorting部分，也把sub_for_times和sub_for_Max變數給刪了
```clike=
for (i = num_list; i > 0; i--) {
sub_head = *head;
pre_sub_head = head;
for (sub_i = 0; sub_i < i; sub_i++) {
/* 這裏我把大的號碼排去後面 */
if (sub_head->value > sub_head->next->value) {
sub_head = swap(sub_head,sub_head,sub_head->next);
*pre_sub_head = sub_head;
}
pre_sub_head = &((*pre_sub_head)->next);
sub_head = sub_head->next;
}
}
```
都修改好後就執行看看結果，發現它沒有讀到測資中第一行的3，反而讀到下一行的12，也導致後面的結果亂掉了。看了一下test-bubble.sh檔後，發現第一個while會讀到一個var，導致下一次讀的時候是12。因此便在data-bubble.in中加多一個空行就行了。
```clike=
while (read var)
do
read var
list_length=$var
```
最後在查看結果（一部分）：
```javascript=
$27 = "test begin"
$28 = "old_list"
$29 = (List *) 0x602030
$30 = 12
$31 = (struct List_node *) 0x602050
$32 = 4
$33 = (struct List_node *) 0x602070
$34 = 5
$35 = (struct List_node *) 0x0
$37 = "new_list" //已排序好的list
$38 = (List *) 0x602050
$39 = 4
$40 = (struct List_node *) 0x602070
$41 = 5
$42 = (struct List_node *) 0x602030
$43 = 12
$44 = (struct List_node *) 0x0
```
## Merge sort 實作
利用很普通的演算法來實作，先計算list的長度，在進入遞回跟merge進行sorting：
```clike=
void merge_sort(List **head) {
if (head == NULL || (*head==NULL))
return;
int n = 0;
List *_head;
_head = *head;
while (_head && _head->next) {
n++;
/* Circular linked list */
if (_head->next == *head)
break;
_head = _head->next;
}
Sort(head, 0, n);
}
void Sort(List **list, int low, int high) {
if(high > low) {
Sort(list, low, (low+high)/2);
Sort(list, ((low+high)/2)+1, high);
Merge(list, low, high);
}
}
```
再來是其它function的詳細實作就不po在這邊了，最後產生自己的測資，考慮到執行時間的關係，只產生100個，每筆測資也只有50個亂數：
```clike=
for(i=0; i<100; i++) {
n = rand() % 50 + 1;
fprintf(fp,"%d\n",n);
for(j=0; j<n; j++) {
int value = rand() % 1000 + 1;
fprintf(fp,"%d ",value);
}
}
```
最後查看結果（一部分）：
```javascript=
$51 = "test begin"
$52 = "old_list"
$53 = (List *) 0x602030
$54 = 949
$55 = (struct List_node *) 0x602050
$56 = 814
$57 = (struct List_node *) 0x602070
$58 = 461
$59 = (struct List_node *) 0x602090
$60 = 583
$61 = (struct List_node *) 0x6020b0
$62 = 954
$63 = (struct List_node *) 0x6020d0
$64 = 346
$65 = (struct List_node *) 0x0
$67 = "new_list" //Sorted
$68 = (List *) 0x602030
$69 = 346
$70 = (struct List_node *) 0x602050
$71 = 461
$72 = (struct List_node *) 0x602070
$73 = 583
$74 = (struct List_node *) 0x602090
$75 = 814
$76 = (struct List_node *) 0x6020b0
$77 = 949
$78 = (struct List_node *) 0x6020d0
$79 = 954
$80 = (struct List_node *) 0x0
```
Sign in with Wallet
Connect another wallet