Try   HackMD

2023q1 Homework1 (quiz1)

contributed by < EdwardCKC >

測驗 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 得知 AAA 是要放 struct 的 type,而 BBB 是要放 list_head 的名稱

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

因為pivotstruct 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個參數,所以 CCClist_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

最後 FFFlist_splice_tail 因為是正序排序,所以是串接 list_less 的尾端,整合成完整的 sorted list

測驗 2

測驗 3

XOR_COMP function 是將2個 pointer 做 XOR 運算 所以 LLLL(uintptr_t) a ^ (uintptr_t) b