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 示意圖
  Image Not Showing Possible Reasons
  The image file may be corrupted
  The server hosting the image is unavailable
  The image path is incorrect
  The image format is not supported
  Learn More →
如果這些 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

2019q3 Homework3 (list)

macro 跟 function 差別

為何 Linux 採用 macro 來實作 linked list？

typeof 功用跟好處

了解以下代碼的功用

offsetof

pmember

功用

list.h 包含的操作跟好處

linked list 採用環狀是基於哪些考量？

linked list 的排序應用

實作 merge sort

divide

divide 改進

conquer

跑完 unitest

參考資料