2019q1 Homework1 (list)

contributed by < Laurora>

• F02: list

自我檢查事項

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

• macro表示方式為#define MACRONAME 指令或常數
• 用 #define 定義一段指令或常數，當 preprocessor 掃描到程式中 macroname 表示時，便會使該 macro 表示的指令或常數替換。

看起來和 function call 很像，為什麼不用 function call 就好了？

• 在呼叫 function call 時需要 stack 的 push 和 pop 來存取傳入變數和 function 位置，時間成本增加，當 function call 大量使用時便會浪費掉許多時間。
• 使用 macro 時則是直接將程式碼替換，須增加指令空間，若指令複雜相對指令空間就必須分配較多，且維護不易，因此 macro 適合替換簡單且大量重複的指令。

設計實驗來驗證上述說法，搭配反組譯結果的解讀

jserv

---

Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

---

GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？

• typeof 是 gcc 對 C 語言中的一個 extension

• 主要功能是回傳參數的 type

• 傳入 typeof 的參數可以有兩種形式： expression 或是 type

• expression

typeof (x[0](1))

這邊假設陣列 x 存取指向 function 的 pointer， typeof 便可以得到 function 回傳的 type

• type

typeof (int *)

也可以直接輸入 type ， typeof 得到的就是 int *

#define max(a,b) \
  ({ typeof (a) _a = (a); \
      typeof (b) _b = (b); \
    _a > _b ? _a : _b; })

當使用 macro 定義 type 時，因不確定傳入的變數的 type ，因此需要 typeof 找到該變數的 type 避免執行錯誤。

---

解釋以下巨集的原理

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

• ((type *) 0)->member ： 0 的 type 是 pointer to type 並指向 master

• __typeof__(((type *) 0)->member) ： 用 typeof 取得 master 的 type

• __typeof__(((type *) 0)->member) *__pmember ：宣告 *__pmember ， type 為 master 的 type

• __typeof__(((type *) 0)->member) *__pmember = (ptr); ： *__pmember 的位址為 (ptr)

• offsetof 的用途是計算 structure member 的 offset ，以 byte 為單位 return structure memeber的 offset

• __extension__ ： 告訴 gcc 不要提出警告

• (char *) __pmember - offsetof(type, member); ： 則以 __pmember 減去 member 在 type 這個 structure 的 offset，可以得到這個 type 的起始位址

• (type *) ((char *) __pmember - offsetof(type, member)); ：宣告此起始位址為 pointer to type

---

除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？

更完善 list.h 的功能，考量不同情況的呼叫，避免發生程式嚴重錯誤。

不要用字面意思解讀，善用案例解釋 (及早脫離「文組^TM」)
show me the code!

jserv

---

LIST_POISONING 這樣的設計有何意義？

---

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

---

什麼情境會需要對 linked list 做排序呢？

排序可以使資料搜尋變得更快，現實生活中的應用如：

• 排序好以後可以快速尋找整個 list 最小和最大的元素
• Heap Sort 是圖論中實現 priority queue 的一種方式，可應用在 Dijkstra's algrithm （尋找最短路徑）、 Huffman 編碼（資料壓縮）

在 Linux kernel 中的應用如：

• file system management
• garbage collection

參考：Basic Data Structures and Algorithms in the Linux Kernel

用實際程式碼解說，附上分析和實驗

jserv

---

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

---

list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？

• list_for_each_safe：會額外將 node 的下一個記錄在 save ，可避免刪除 node 後會找不到下一個 node。

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

• list_for_each ：不紀錄 node->next ，因此在刪除 node 時可能產生 dangling pointer

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

---

for_each 風格的開發方式對程式開發者的影響為何？

for_each 是 c++ 提供的 funtion templete ，可直接呼叫該函式回傳開發者要的結果。

本處是探討 Linux linked list macro，而不是 C++ 語言特徵

jserv

• Linux linked list macro 在單向鍊結和雙向鍊結分別 define 了 FOREACH 和 FOREACH_SAFE 幫助迭代整個 list ，若需要從 list 中刪除元素則需要用到 FOREACH_SAFE
  下面是 linux 中 定義單向鍊結的 FOREACH 和 FOREACH_SAFE

#define LL_FOREACH(head,el)
    for(el=head;el;el=el->next) 

#define LL_FOREACH_SAFE(head,el,tmp)
    for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)

對開發者而言， for_each 提供了一個比較通用的函式幫助迭代，只要呼叫函式，將需要處理的變數傳入函式即可，而不需要自己從 for/while 迴圈開始寫，不只可讓程式可讀性變得更高，開發者所遇到的錯誤會更少。
而在編譯器的處理上，編譯器對於這種已經包裝好的函式——不同於 for/while 必須對迴圈內的程式有 break, continue 的可能——不須多做預測與處理，讓編譯器可對整個程式效能做更好的改進。

若要將 array 中的所有 element 相加，不使用 for_each 實做可能會長這樣：

int main() {
    int a[] = { 1, 2, 3, 4 };
    int i;
    int sum=0;
    for (i=0;i<4;i++)
        sum += a[i]; 
    
}

在 Python 中可以直接用三行程式碼就達到上面程式碼的效果

a = [ 1, 2, 3, 4 ]
for i in a:
    sum += a[i]

在函式導入或是物件呼叫變得複雜，開發者所遇到的困難或是錯誤可能會更多，此時 for_each 風格的使用能更簡化程式的呈現。

---

程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？

Doxygen 能自動從程式中生成註解， @ 符號的功能是讓開發者呼叫特定的註解。

---

tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？

---

tests/ 目錄的 unit test 可如何持續精進和改善呢？