2023q1 Homework1 (lab0)

contributed by < ShamrockLee >

queue.c 函式實作

實作細節

Linux 核心的 list API 使用帶有起始節點（ list head ）的環狀雙向鍊結串列。 節點以結構 struct list_head 表示，該結構有兩個成員 prev 、 next ，分別存放指向串列中前一個與後一個節點的指標。

每個節點所攜帶的資料，以巨集 list_entry 存取。 list_entry 即 container_of ，可用來存取帶有該節點變數（非指標）的結構的位址，藉以存取該結構中帶有的資料。 前述結構在 queue.h 當中有 element_t 及 queue_contex_t

list.h 當中大部分函式輸入參數被設計來傳入起始節點指標（能看到以 head 命名的輸入參數多次出現）。 然而，那些函式也能用在串列中其他節點上，以插入、讀取或移除該節點兩側的節點。 善用這種操作能在更多地方重用 list.h 所定義的函式，減少手動賦值 prev 、 next 帶來的的維護負擔。

以下是個別函式實作值得注意的部份：

• q_free

  • 在釋放記憶體空間時，由於節點是 element_t 的成員，會跟著 element_t 一起釋放；若再以 free 釋放節點，就會出錯。

• q_delete_mid

  • 由於 q_sort 的合併排序實作也會需要知道中間節點的位址，故將計算中間節點位址的部份另外獨立為函式 q_get_mid 。
  • q_get_mid 以起始節點的後方節點為起點，透過快慢指標求得中間節點的位置。

• q_delete_dup

  • 這個函數仍保留較多的手動賦值操作，且程式碼較為冗長，或許還能簡化。

• q_reverse

  • 這個函數以交換 prev 與 next 實作。
  • 會被 q_reverseK 和 q_swap 呼叫。

• q_reverseK

  • 函式中，宣告了兩個 struct list_head 變數 temp_head_reverser 與 temp_head_result 作為兩個「暫時串列」的起始節點；前者用以傳入 q_reverse ，後者儲存反轉後的節點。

• q_swap

  • 以 k = 2 的 q_reverseK 實現
  • 不確定會不會比直接賦值 prev 、 next 效能差。

• q_merge

  • 排序部份獨立為函數 q_merge2 ，以便 q_sort 合併排序時重用。
  • 直接操作 q_contex_t 的 size 以減少時間複雜度。

• q_sort

  • 實作為合併排序。
  • 宣告struct list_head temp_head 使用 q_get_mid 尋找中間節點，並以 list_cut_position 把前半部切給 &temp_head 。
  • 兩個鍊結串列分別傳入 q_sort 排序，再使用 q_merge2 合併。

過程概要

實作初期，只看到了 list API 所使用的串列結構，並從註解發現大部分函式都是對起始節點的操作，未能理解 list_move 、 list_splice 、 list_cut_position 適用的情境，因此實作 q_swap 、 q_reverseK 、 q_sort 時幾乎都是手動指定 prev 、 next 。 這造成程式碼愈來愈冗長、難以除錯，以至於花費許多時間而缺乏成效，最後卡在合併串列（merge）的部份。又因為怕被發現進度落後，遲遲未上傳程式碼並接受檢核。

在一對一對談後，以「儘可能重用 List API 提供的函式」與「儘可能重用已定義的函式」為目標最佳化。 仔細閱讀 list.h 的函式，花了三小時內實作、重構了所有函式，五小時除錯，達到記憶體使用以外的行為符合期待的結果。 這顯示及早接受檢核的重要性與重用 API 提供的程式碼帶來的效果。