# 2019q1 Homework1 (list)
contributed by < `Zames-Chang` >
* [F02: list](https://hackmd.io/s/S12jCWKHN)
## 實作出 merge sort
* 附上你的修改過程，也需要讓 qtest 得以支援
* 可將 dict 裡頭的測試資料拿來作效能分析的輸入
* 思考提升排序效率的方法，需要做平均和最壞狀況的分析
## qtest支援
在qtest command指令中加入sort指令
```c=
static void console_init(){
...
add_cmd("sort", do_sort, " | Merge sort queue contents");
...
}
bool do_sort(int argc, char *argv[]){
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
my_merge_sort(q); // implement merge sort in this function
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
### 自動化單元測試
新增trace-16-mysort.cmd
因為qtest中的queue的元素為string，為了測試排序的功能，我假設輸入都是一個char，並根據他們的ascII code做排序。
```
new
ih a
ih c
ih b
ih e
ih d
ih h
ih h
sort
show
```
並在driver.py加入
```python
traceDict = {
...
16 : "trace-16-mysort"
}
traceProbs = {
...
16 : "Trace-16"
}
```
#### result
```
+++ TESTING trace trace-16-mysort:
q = [a b c d e h h]
```
### Merge Sort
```c=
/**
* merge_sort - using merge sort to sort queue
* @head: pointer to queue first element
*
* queue element must be a single char
* @Return :pointer to sorted link list head;
*/
list_ele_t* merge_sort(list_ele_t* head){
if(head && head->next){
list_ele_t* mid = spice_half(head);
head = merge_sort(head);
mid = merge_sort(mid);
list_ele_t* result = sort_merge(head,mid);
return result;
}
else{
return head;
}
}
```
### spice_half
```c=
/**
* spice_half - cut link list into half
* @head: pointer to queue first element
*
* @Return: half of remaining link list
* e.g. a->b->c->d splice into a->b,c->d and return pointer to c
*/
list_ele_t* spice_half(list_ele_t* head){
if(head){
list_ele_t *mid = get_mid(head);
list_ele_t *next_start = mid->next;
mid->next = NULL;
return next_start;
}
else
return head;
}
```
### get_mid
```c=
/**
* get_mid - get mid element of link list
* @head: pointer to queue first element
*
* @Return: pointer to mid of link list
*/
list_ele_t* get_mid(list_ele_t* head){
int i = 0;
list_ele_t* des = head;
while(head){
head = head->next;
i++;
}
for(int j=0;j<i/2 - 1;j++)
des = des->next;
return des;
}
```
### sort_merge
```c=
/**
* insert_tail - insert node_2 in tail of node_1
* @node_1: pointer element
* @node_1: pointer element
*
*/
void insert_tail(list_ele_t *node_1,list_ele_t* node_2){
if(node_1 && node_2){
list_ele_t* temp = node_1->next;
node_1->next = node_2;
node_2->next = temp;
}
}
/**
* sort_merge - merge two sorted link list
* @head1: pointer to first sorted link list
* @head2: pointer to second sorted link list
*
* @Return: pointer to merged link list head
*/
list_ele_t* sort_merge(list_ele_t* head1,list_ele_t* head2){
if(head1 && head2){
if(*(head1->value) > *(head2->value)){
list_ele_t* tmp = head2;
head2 = head1;
head1 = tmp;
}
}
else{
return head1 ? head1 : head2;
}
list_ele_t* org_head = head1;
while(head2){
if(head1){
if(head1->next == NULL){
head1->next = head2;
break;
}
else if(*(head1->value) < *(head2->value) && *(head1->next->value) > *(head2->value)){
list_ele_t* item = head2;
head2 = head2->next;
insert_tail(head1,item);
}
else{
head1 = head1->next;
}
}
}
return org_head;
}
```
## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
macro 在編譯前會被 preprocesser 把對應的程式碼貼到macro的地方，而不是一個 function call 的形式。
一個 function call 很麻煩，要把當前暫存器的東西備份一份到暫存器或記憶體，分配空間給 local 變數， Stack 要長上去，中間牽涉到許多記憶體的變化。耗時又費工。
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
`linux/list.h`中的double link list
```c=
struct list_head {
struct list_head *next, *prev;
};
struct My_DATA {
int Data_A;
int Data_B;
int Data_C;
struct list_head list;
};
```
大概結構會像這樣
(參考來自：https://myao0730.blogspot.com/2016/12/linux.html)
讓我比較疑惑的是，<s>一般來說</s> doubly linked list不是都是
:::danger
不要濫用「一般來說」這詞，你到底看了多少軟體設計和實作，才讓你得以「總結」出軟體開發的規律，才有「一般」可言呢？
另外，注意術語寫為 **doubly** linked list，從細節做好，快去改！
:notes: jserv
:::
```clike
struct Node {
struct Node *next, *prev;
int val;
};
```
為何它要特別定義一個 list_head裝下兩個 pointer，更重要的是就算我指到 next的 node我也拿不到資料阿？因為指到下一個 list_head中也沒有 Data_A,Data_B,Data_C阿？這邊我猜測應該跟 strcut記憶體是連續的有關吧？也許它可以透過相對位子取得 Data_A,Data_B,Data_C？
後來我看到查到[這篇文章](http://adrianhuang.blogspot.com/2007/10/linux-kernel-listhead.html)
:::danger
上方連結有標題，為何不清楚書寫呢？
:notes: jserv
:::
```clike
struct student {
char name[16];
int id;
struct list_head list;
};
```
證實了應該我的想法，所以假設我要取的 student的 name
```c=
struct list_head list next = head->next;
char *temp;
temp = (char*) (((void*) &next )- 20);
```
在 linux中process的資訊是由 task_struct管理，譬如說
`struct list_head children`，就是這個 process中的有沒有子 process，如果有會以 link list串接在這裡。
`struct list_head sibling`，則是存跟當前這個 process同樣 parent的進程
```c=
struct task_struct {
...
struct task_struct __rcu *real_parent;
struct task_struct __rcu *parent;
struct list_head children;
struct list_head sibling;
...
}
```
### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
typeof的功能是去回傳一個跟帶入的 instance同樣型別的type， ，它會在你編譯前的預處理時去幫你把 typeof的內容轉換成對應的型別
<s>e.x.</s>
:::danger
"for example" 縮寫是 [e.g.](https://www.merriam-webster.com/dictionary/e.g.)，不是 "ex"
:notes: jserv
:::
```clike
int a;
typeof(a) b; // = int b;
typeof(&a) c; // = int* c;
```
after preprocess
```clike
int a;
int b;
int* c;
```
在linux程式碼中，它需要在 complie的時候先去確認某一些變數是不是型別是一樣的，譬如說以下 macro就是用於確認某個instance是否為某個特定型態。
```clike
/*
* Check at compile time that something is of a particular type.
* Always evaluates to 1 so you may use it easily in comparisons.
*/
#define typecheck(type,x) \
({ type __dummy; \
typeof(x) __dummy2; \
(void)(&__dummy == &__dummy2); \
1; \
})
```
另一個例子是當你希望把兩個 instance的型別作對調的時候，你不太可能在一開使用的時候就知道兩個變數分別的型別，這時候就可以利用typeof來得到兩個人分別的型別，並且對調
```clike
/*
* swap - swap value of @a and @b
*/
#define swap(a, b) \
do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
```
[reference](http://deltamaster.is-programmer.com/posts/37253.html)
### 解釋以下巨集的原理
```clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
`const __typeof__(((type *) 0)->member) *__pmember = (ptr)`
這段是在製造一個 member的指針，並指向 ptr的位址，我這邊比較不理解的地方是為啥不用`const __typeof__(member) __pmember = (ptr)`要大費周章的先用轉成比較上層的struct在去存取下面的member
`(type *) ((char *) __pmember - offsetof(type, member))`
這行則是透過減掉 member在此 struct中的偏移量，進而得到這個struct的起始位址。
### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
讓使用者可以用更高level的角度來操作 link list，不然的話像原始碼中它如何判斷 link list是到底了呢？一般來講我們自己寫程式的話會判斷它最後一個元素有沒有指到 null，但是linux不是這樣實做，它實做的方式是去比較`tail->next == head`，因此不了解 linux link list實做細節的話，會很容易踩到坑
:::danger
不要 ==憑感覺== 書寫，應該搭配實際程式碼和自行撰寫的分析數據來探討。及早脫離「文組^TM^」。特別在你撰寫過 merge sort 一類的程式後，針對 linked list 的例外處理就該有所察覺。
:notes: jserv
:::
### linked list 採用環狀是基於哪些考量？
比較彈性，在 init時候它會把 tail跟 head都指向 head，因為假設他不是環狀的話你要insert tail就必須要走到最後一個元素才能insert也就需要`O(n)`的時間複雜度，然而如果是環狀的話只要`head->pre`就是tail了，這樣只要`O(1)`。而且假設搜尋link list的某個元素，而且你知道從尾巴往前找比從頭往後找要快的話，環狀的結構就可以滿足這個需求，在linux中這個macro叫做`list_for_each_entry_reverse`
### 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
例如說`$ htop`，由於程式會隨著時間加入或刪除，你不太可能用一個 array去 maintain，但是你又常常需要根據 cpu的使用時間去做排序，因此這個時候我們就必須要要對 link list做排序。
:::danger
請把話說好，難道 "maintain" 是關鍵字嗎？這非得用英文寫嗎？程式寫不好，真的不可恥，但是連話都說不好，如何跟其他 (專業的) 工程人員溝通呢？
:notes: jserv
:::
### 什麼情境會需要需要找到 第 k 大/小元素 呢？你打算如何實作？
譬如說你要在作業系統中找到前三大的使用cpu的程式。
我會使用 merge sort 先把 link list 排序好，再取第k個element出來，這樣所需要的時間複雜度為`O(nlogn)`
:::danger
Show me the code!
從 Linux 核心找出實際應用的程式碼出來。
:notes: jserv
:::
### list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？
list_for_each 假設你在執行的過程中不會有節點被刪掉，但是safe的版本會幫你檢查這件事情有沒有被發生
### for_each 風格的開發方式對程式開發者的影響為何？提示：對照其他程式語言，如 Perl 和 Python
for_each 這種開發風格可以讓程式發開者不需要事先知道list的長度，也不會因為改動for loop中的i造成confuse的問題。
e.x.
```c=
for(int i=0;i<5;i++){
array[i] = 0;
i--;
}
```
### 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？提示: 對照看 Doxygen
因為有多 doc 是由程式像是 Doxygen 生成的，透過在原始碼中加入＠的註解，可以被這些自動生成 doc 的程式解析，並輸出doc。
### tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
測試程式的 robust 程度，甚至測試 worst case, edge case，看要跑多久，對於軟體工程來說，測試非常重要，如果沒有測試你不知道你的程式在怎樣的情況下能夠 handle ，比如說，台灣股票市場曾經因為大力光股票價格太高，導致計算過程中 overflow 造成結果計算錯誤，這就是系統沒有經過單元測試的結果。
### tests/ 目錄的 unit test 可如何持續精進和改善呢？
暫無
Sign in with Wallet
Connect another wallet