# 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 提供的程式碼帶來的效果。