---
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 的名稱

struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);

因為`pivot` 是 `struct item` 所以 AAA 是 ```struct item```

struct item {                         
    uint16_t i;
    struct list_head list;
};

根據 `struct item` BBB 是 `list`

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`