--- tags: lab0-c, linux2023 --- # 2023q1 Homework1 (quiz1) contributed by < `EdwardCKC` > ## [測驗 `1`](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-1) 問題: `struct list_head head` and `struct list_head *head` 之間分別是? 我的理解:一個是 struct 一個是 pointer 延伸問題:但為什麼要用在這裡，它的在優缺點又是什麼? ``` struct list_head list_less, list_greater; INIT_LIST_HEAD(&list_less); INIT_LIST_HEAD(&list_greater); ``` * 解釋上述程式碼運作原理 * 針對 Quick sort 提出上述程式碼的改進方案並實作 * 引入上述的 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響 * BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻 ### 運作原理 `list_first_entry (ptr, type, member)` 從 [Arguments](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.list_first_entry) 得知 AAA 是要放 struct 的 type，而 BBB 是要放 list_head 的名稱 ``` cpp struct item *pivot = list_first_entry(head, AAA, BBB); list_del(&pivot->list); ``` 因為`pivot` 是 `struct item` 所以 AAA 是 ```struct item``` ```cpp! struct item { uint16_t i; struct list_head list; }; ``` 根據 `struct item` BBB 是 `list` ```cpp CCC (itm, is, head, list) { if (cmpint(&itm->i, &pivot->i) < 0) DDD (&itm->list, &list_less); else EEE (&itm->list, &list_greater); }; ``` 因為要走訪list，所以一定是 list_for_each_entry ，還有因為有4個參數，所以 `CCC` 是 `list_for_each_entry_safe` cmpint 後就是根據條件式分別移動到 `list_less` / `list_greater` 所以 DDD 和 EEE 可能是 `list_move` / `list_move_tail` 之後問了ChatGPT哪個會比較好 問: I guest DDD and EEE are list_move or list_move_tail, but I don't know which is better 答: It depends on the specific use case and requirements of the program. If preserving the order of the original list is not important, then **list_move_tail may be a better choice as it adds elements to the end of the new list, which can improve performance in some cases.** On the other hand, if the order of the original list needs to be preserved, then list_move may be a better choice. Ultimately, the choice between these functions should be based on the specific needs of the program and the performance characteristics of the data structures being used. 這裡因為後面會做 `list_sort` 所以 DDD 和 `EEE` 會選 `list_move_tail` 最後 `FFF` 是 `list_splice_tail` 因為是正序排序，所以是串接 `list_less` 的尾端，整合成完整的 sorted list ## [測驗 `2`](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-2) ## [測驗 `3`](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-3) `XOR_COMP` function 是將2個 pointer 做 XOR 運算 所以 `LLLL` 是 `(uintptr_t) a ^ (uintptr_t) b`