# linux2023: [shhung](https://github.com/shhung) Homework 1

---
###### tags: `Linux`
---

## 測驗 $\alpha-1$
### `st_remove`
根據註解說明，可以知道 `st_remove` 的ㄒ行為有以下幾種情況
- 當被刪除的節點 `del` 有右節點時，便找到右子樹中的最左節點 `least` 來取代被刪除的節點，取代後對 `least` 進行 `update`
- 同樣的，當被刪除的節點 `del` 有左節點時，便找到左子樹中的最右節點 `most` 來取代被刪除的節點，取代後對 `most` 進行 `update`
- 當被刪除的節點 `del` 沒有子節點時，便直接刪除，並對 `del` 的親代做 `update`

透過原本已寫好的 `st_replace_right` 、 `st_replace_left` 、 `st_replace_update` ，及幾個 `st_` 相關 `macro` ，便能完成上述的操作。

### `__treeint_dump`
而 `__treeint_dump` 則是透過遞迴來完成 `In-Order traversal`，透過 `st_left` 、 `st_left` 即可以完成，詳細說明不多贅述，可參閱資料 [binary-tree-traversal](http://alrightchiu.github.io/SecondRound/binary-tree-traversalxun-fang.html)。

## 測驗 $\beta-1$
`align_up` 針對 `alignment` 為 `2` 的冪時透過 bitwise 操作加速運算，其中透過 `(alignment & mask) == 0` 來判斷是否為 `2` 的冪，
$2^n$ = `1 << n`
透過上式可以觀察到`2` 的冪僅有一位為 `1` ，便可以透過 `(alignment & mask) == 0` 來判斷，其中 `mask = alignment - 1`。

## 測驗 $\gamma-1$
關鍵函式為 `qsort_mt` 和 `qsort_thread`，
- `qsort_mt` 為 multi-thread 版本 qsort 的呼叫函式，判斷是否有足夠資源或者排序的陣列是否大於閾值，符合條件則進行 multi-thread qsort ，否則就用一般的 qsort
- qsort_thread 則是子線程實際進行排序的函式，對陣列進行實際的排序

`qsort_mt` 引入 POSIX Thread 來實現 multi-thread，包含以下幾個關鍵函式
- pthread_mutex_lock()
- pthread_mutex_unlock()
- pthread_cond_wait()
- pthread_cond_signal()