# 2019q3 Homework3 (list)
contributed by < `YenHengLin` >
## macro 跟 function 差別

* macro 是透過 Preprocesser 將程式碼內有對應到 macro 定義的文字，轉換成其定義好的其他文字。由於只做文字轉換而已，所以沒辦法做型別確認。
* function 則是在程式執行到 function 時，跳轉到 function 程式所儲存的位址，其跳轉前必須要先將當前程式執行的 return address 、 local varible、 parameter 紀錄起來，以便 function 執行結束時，能知道原本的程式的狀態。其執行速度相對於 macro 慢，由於必須要做 stack 儲存的動作。
## 為何 Linux 採用 macro 來實作 linked list？
* linked list 這種指標的操作需要考驗程式設計師的專業，如果讓不了解 c 語言的人來寫可能會是個悲劇，所以我們用 macro 包裝起來，讓工程師少一點出錯的可能
* 而且我們不用像 function 特地知道指標的 type 因為 macro 只是替換文字而已
* 另外 macro 執行速度比 function 快
## typeof 功用跟好處
* typeof 為一種存取 type 跟 expression 的 type 的方式
* 使用方式為：當我想要設定變數 y 他的 type 要跟 變數 x 一樣時,我可以這樣表示 `typeof(x) y;`
* 前面我們已經提過 macro 屬於 no type checking，當我們想再 macro 裡得知傳入的參數的 type 就必須使用 typeof
* 範例 code

    #define swap((a),(b))\
        typeof(a) tmp=(a);\
        (a)=(b);\
        (b)=tmp;

如果沒有 typeof 則我們在實做這段 a b 值互換的 code 時還必須傳入 type
## 了解以下代碼的功用

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

#### offsetof
* 定義在 <linux/stddef.h> 這個檔案裡

    #define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)

* 透過強制轉型將數字 0 轉成 TYPE 型態的指標，在從 0 指向 MEMBER 這個成員。造裡來說 0 是 null pointer 由它來指向 MEMBER 會產生 segementation fault,然而我們在前面加上 **&** 代表我們只是要取出位址並不取出元素，所以就不會發生錯誤
* 因為是由 0 當作起點，所以我們也可以把得到的位址當作是， MEMBER 這個元素與(自己所在的 structure 的)起始位址的偏移 (offset)
#### pmember
* 紀錄了指向 member 型別指標的位址
#### 功用
* 利用 pmember 減去其 member 在這個 structure 的偏移，可以求出該 structure 的起始位址

## list.h 包含的操作跟好處
* 定義了初使化的操作。由於 linked list 的實做方式有很多種，為了確保使用者是使用環狀雙向鍊結的方式，我們規範了初始化的 prev 跟 next 都指向 head

    #define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

## linked list 採用環狀是基於哪些考量？
* 環狀結構為頭尾相連，所以我們可以利用 head->prev 而快速的求得 linked list 的尾巴是誰。時間複雜度為 $O(1)$
* 透過雙向環狀結構能使得資料的鍊結在遭到破壞時，多一層保障，例如某個鍊結的 next 指標壞了，我們可以透過不斷的往前追朔 prev 而能得到原本 next 指標指向的物件
## linked list 的排序應用
* 每一個 process 都對應著一個 process control block 簡稱 pcb，這些 process 的 pcb 由 linked list 串接起來放在待命佇列，等著 cpu 排班程式挑選進 cpu 執行
* pcb 示意圖

* 如果這些 pcb 彼此之間有優先順序的話，就必須要透過 linked list 排序將這些 pcb 順序調換，讓 os 選擇優先權大的先執行

## 實作 merge sort
### divide
* merge sort 是先將資料從中間作切割，分成左半邊跟右半邊，直到無法再分割為止
* 一開始我原本在想是否需要將 list 長度計算出來，才能回推中間的資料是哪個，後來我想到了當我用兩個指針， next 跟 prev 分別從 head 往後跟往前每次走一格，next 指針經歷的資料接在 list_left 後頭，而 prev 指針經歷的資料接在 list_right 後頭，則我們能剛好將資料分成兩個部分
* 當 `next->next == prev` 代表我們將所有的資料都走訪過了，這時我們將 visitall 設為 true 表示不用再將最後一個 prev 放在 list_left 尾端
* code

    INIT_LIST_HEAD(&list_left);
    INIT_LIST_HEAD(&list_right);
    /* split half*/
    struct list_head *next = head->next;
    struct list_head *prev = head->prev;
    bool visit_all = false;
    for (; next != prev; next = next->next, prev = prev->prev) {
        list_move_tail(next, &list_left);
        list_move_tail(prev, &list_right);
        if (next->next == prev) {
            visit_all = true;
        }
    }
    if (!visit_all)
        list_move_tail(prev, &list_right);
    list_mergesort(&list_left);
    list_mergesort(&list_right);

### divide 改進
* 使用 list_move_tail 會導致錯誤因為當我 list_del 完後 next 釋放掉了，就無法在 next 指向 next，prev 也同理，所以我就去參考 quick-sort.c 的寫法
* quick-sort.c 使用了 list_for_each_safe，使用了 safe 指針去指向 `node->next`，這樣就能確保在釋放掉時還能知道下一個物件位址在哪
* code

    for (safen = next->next, safep = prev->prev; next != prev;
         next = safen, prev = safep, safen = safen->next, safep = safep->prev) {
        list_move_tail(next, &list_left);
        list_move_tail(prev, &list_right);
        if (next->next == prev) {
            visit_all = true;
        }
    }

### conquer
* conquer 就是將 list_left 跟 list_right 的元素一一取出，使用 list_entry 取出 listhead 現在位於哪個 listitem 底下，將左值跟右值作比較 `iteml->i <= itemr->i`，將比較小的值插入 head 的尾端，為了避免使用 list_move_tail 後造成指針消失，使用了 safel 跟 safer 記錄下一個指向的位址
* 由於有可能還有剩餘的物件沒有被加進 head ，所以在最後加上 `list_splice_tail`
* code

    /* merge*/
    struct list_head *left_next, *right_next;
    struct list_head *safel = NULL, *safer = NULL;
    left_next = list_left.next;
    right_next = list_right.next;
    safel = left_next->next;
    safer = right_next->next;
    while (left_next != &list_left && right_next != &list_right) {
        iteml = list_entry(left_next, struct listitem, list);
        itemr = list_entry(right_next, struct listitem, list);
        if (iteml->i <= itemr->i) {
            list_move_tail(&iteml->list, head);
            left_next = safel;
            safel = safel->next;
        } else {
            list_move_tail(&itemr->list, head);
            right_next = safer;
            safer = safer->next;
        }
    }
    list_splice_tail(&list_left, head);
    list_splice_tail(&list_right, head);

### 跑完 unitest
* 發現有 segmentation fault
## 參考資料
* [wiki macro](https://zh.wikipedia.org/wiki/%E5%B7%A8%E9%9B%86)
* [stack overflow:Macro vs Function in C](https://stackoverflow.com/questions/9104568/macro-vs-function-in-c/9104584)
* [你所不知道的C語言：函式呼叫篇](https://hackmd.io/@sysprog/SJ6hRj-zg?type=view)
* [GNU: The C Preprocessor 導讀](http://wen00072.github.io/blog/2013/10/13/talk-about-c-macros/)
* [GCC typeof在kernel中的使用——C语言的“编译时多态”](http://deltamaster.is-programmer.com/posts/37253.html)
* [Linux Kernel: 強大又好用的list_head結構 ](https://adrianhuang.blogspot.com/2007/10/linux-kernel-listhead.html)
* [Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)
* 作業系統基本概念 第二板
* [Process Control Block in Operating System (OS)](https://prepinsta.com/operating-systems/process-control-block/)