2019q1 Homework1 (list)

contributed by < Zames-Chang >

• F02: list

實作出 merge sort

• 附上你的修改過程，也需要讓 qtest 得以支援
• 可將 dict 裡頭的測試資料拿來作效能分析的輸入
• 思考提升排序效率的方法，需要做平均和最壞狀況的分析

qtest支援

在qtest command指令中加入sort指令

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加入

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

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

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

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

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

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)
讓我比較疑惑的是，一般來說 doubly linked list不是都是

不要濫用「一般來說」這詞，你到底看了多少軟體設計和實作，才讓你得以「總結」出軟體開發的規律，才有「一般」可言呢？
另外，注意術語寫為 doubly linked list，從細節做好，快去改！

jserv

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？

後來我看到查到這篇文章

上方連結有標題，為何不清楚書寫呢？

jserv

struct student {
    char name[16];
    int id;
    struct list_head list;
};

證實了應該我的想法，所以假設我要取的 student的 name

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的進程

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的內容轉換成對應的型別
e.x.

"for example" 縮寫是 e.g.，不是 "ex"

jserv

int a;
typeof(a) b; // = int b;
typeof(&a) c; // = int* c;

after preprocess

int a;
int b;
int* c;

在linux程式碼中，它需要在 complie的時候先去確認某一些變數是不是型別是一樣的，譬如說以下 macro就是用於確認某個instance是否為某個特定型態。

/*
 * 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來得到兩個人分別的型別，並且對調

/*
 * swap - swap value of @a and @b
 */
#define swap(a, b) \
    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)

reference

解釋以下巨集的原理

#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實做細節的話，會很容易踩到坑

不要 憑感覺 書寫，應該搭配實際程式碼和自行撰寫的分析數據來探討。及早脫離「文組^TM」。特別在你撰寫過 merge sort 一類的程式後，針對 linked list 的例外處理就該有所察覺。

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做排序。

請把話說好，難道 "maintain" 是關鍵字嗎？這非得用英文寫嗎？程式寫不好，真的不可恥，但是連話都說不好，如何跟其他 (專業的) 工程人員溝通呢？

jserv

什麼情境會需要需要找到 第 k 大/小元素 呢？你打算如何實作？

譬如說你要在作業系統中找到前三大的使用cpu的程式。
我會使用 merge sort 先把 link list 排序好，再取第k個element出來，這樣所需要的時間複雜度為O(nlogn)

Show me the code!
從 Linux 核心找出實際應用的程式碼出來。

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.

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 可如何持續精進和改善呢？

暫無