---
# System prepended metadata

title: 2016q1 Homework2 (B) unit-test

---

# 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
```
