# 2024q1 Homework1 (lab0)
### 1. 第 1 週所有教材及作業描述，啟發和疑惑
:::warning
教材內容皆以引用符號表示，如下
> 引用內容
:::
#### 一、 [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#%E8%A7%A3%E8%AE%80%E8%A8%88%E7%AE%97%E6%A9%9F%E7%B7%A8%E7%A2%BC)
**模除和溢位**
> 無論在圓環上繞幾圈，最終的落點仍會在圓環上，每繞一圈就會發生最高位的溢位，並從 00000000 開始，這就是模除的本質。對於乘法，這個圓環依然使用，兩個數相乘，只要有一個數是正數，那麼就可用上述的圓弧不斷拼接來得到答案，比如 3 * 2 就是用 2 個 3 這個圓弧拼接兩次，-2 * 4 就是拿 4 個 -2 這個圓弧拼接四次，對於兩個負數相乘，比如 (-a) * (-b)，可拆成 (a * b) * (-1) * (-1)，於是只要計算 (-1) * (-1) 即可，也就是 11111111 * 11111111，最終的結果是 [xxx]00000001，高位全部溢位，結果就是正數 1。
`(-a) * (-b)，可拆成 (a * b) * (-1) * (-1)，於是只要計算 (-1) * (-1) 即可`，-1若用8位元表示即為11111111，因此a或b無論多小經過此算式皆會被進位置超出範圍被捨棄，因此只要計算(-1) * (-1) 即可，也就是 11111111 * 11111111，最終的結果是 [xxx]00000001，高位全部溢位，結果就是正數 1。也示範了負負何以得正。
**阿貝爾群及對稱性**
>伽羅瓦的思想大致是：每個多項式都對應於一個與它的根的對稱性有關的置換群，後人稱之為「伽羅瓦群」。下圖是個簡單置換群 $S_3$ 的例子。一個方程有沒有根式解，取決於它的伽羅瓦群是否為可解群。
> 
> 在上圖的置換群 S3 中，給定 3 個字母 ABC，它們能被排列成如上圖右邊的 6 種不同的順序。也就是說，從 ABC 產生 6 種置換構成的元素。這 6 個元素按照生成它們的置換規律而分別記成 (1), (12), (23) … 括號內的數字表示置換的方式，比如 (1) 表示不變，(12) 的意思就是第 1 個字母和第 2 個字母交換等等。
(12) 乘以 (123) 得到 (13) (原始為 ABC，先經過後者123之操作變為 BCA，再經過前者12之操作變為 CBA，即等同13) ，而當把它們交換變成 (123) 乘以 (12) 時，卻得到不同的結果 (23) (原始為 ABC，先經過後者12之操作變為 BAC，再經過前者123之操作變為 ACB，即等同23) ，因此， $S_3$ 是種不可交換的群，或稱之為「非阿貝爾群」。 $S_3$ 不是循環群，也不是 (非循環) 交換群但[為可解群(詳見 P.2-4)](http://chowkafat.net/Math/Galois24.pdf)。
**`x` 和 `-x` 在時鐘上的表示**
:warning: 問題:
> 
和阿貝爾群對稱不同，0000 的一補數對稱是 1111，而非是本身，因此它的對稱軸線與阿貝爾群對稱軸線有偏差：
此圖藍色是一補數的對稱軸，紅色是二補數的對稱軸
敘述中:「對稱軸線與阿貝爾群對稱軸線有偏差」，應該是藍色實線與紅色實線之偏差，那藍色虛線為何?
**常數時間實作**
如何移除 branch (即 "branchless") 呢？
$$
abs(x) =
\begin{cases}
x & \text{if } x \geq 0 \newline
-x & \text{if } x < 0
\end{cases}
$$
By **2's complement**
$$
abs(x) =
\begin{cases}
x & \text{if } x \geq 0 \newline
(\sim x) + 1 & \text{if } x < 0
\end{cases}
$$
再透過Bitwise XOR (`^`)
| bit a | bit b | bitwise `^` |
| ----- | ----- | ----------- |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
最後兩行可看出無論a為正或負，可給定b而得到異號a (以此達成反轉) ，利用此特性得到以下branchless程式碼
```C
int32_t abs(int32_t x) {
int32_t mask = (x >> 31);
return (x + mask) ^ mask;
// or return x ^ mask - mask; // 因反轉異號
}
```
首先，令 `mask` 為 `x` 算術右移31位，此時若 `x` 為正，`mask` 為 `0x00000000` ， `x` 為負則為 `0xFFFFFFFF` ，最後就可利用上述數學式轉換。
**反轉** : 若 `x` 為負， `mask` 為 `0xFFFFFFFF` ，以此可達成反轉，若 `x` 為正， `mask` 為 `0x00000000` ，可以避免不必要的反轉。
**減1** : 2's complement 重要之處，`0xFFFFFFFF` 即為 `-1` ， `0x00000000` 即為 `0` ， 因此 `+ mask` 即使 `x` 為正，也因為`mask` 為 `0` 而不影響。
最後達成branchless，無須因為應付不同狀況去產生branch，同時使用bitwise的操作達成高效。
不過，當 `x` 為 $-2^{31}$ 時 (`10000000000000000000000000000000`) ，其所轉換的 $2^{31}$ 再2補數中是不存在的，因此會變為 `01111111111111111111111111111111` 再加上 1 超出正值上限進而變回 $-2^{31}$，因此使用此 `abs` 須保證傳遞參數之有效範圍。
#### 二、 [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84C%E8%AA%9E%E8%A8%80%EF%BC%9A%E6%8C%87%E6%A8%99%E7%AF%87)
**沒有「雙指標」只有「指標的指標」**
> ```c
> void func(int *p) { p = &B; }
> ```
在這裡因為單純修改指標的值，也就是複製一份 `ptrA` 並指向 `B` 之位址，並不是從根本去修改 `ptrA` ，因此 `ptrA` 不會有任何改變。
> ```graphviz
> digraph structs {
> node[shape=record]
> {rank=same; structa,structb,structc}
> structp [label="p|<p>&B"]
> structptr [label="<name_ptr> ptrA|<ptr> &A"];
> structb [label="<B> B|2"];
> structa [label="<A> A|1"];
> structc [label="<C> C|3"];
>
> structptr:ptr -> structa:A:nw
> structp:p -> structb:B:nw
> }
> ```
若要從根本去修改，便應該從指標 `ptrA` 之位址下手，如下
> ```c
> void func(int **p) { *p = &B; }
> ```
函式 `func` 複製一份指向 `ptrA` 之位置，並更改指向 `ptrA` 指向的位置之值。
> ```graphviz
> digraph structs {
> node[shape=record]
> {rank=same; structa,structb,structc}
> structp [label="p(in func)|<p> &ptrA"]
> structadptr [label="&ptrA(temp)|<adptr> &ptrA"]
> structptr [label="<name_ptr> ptrA|<ptr> &B"];
> structb [label="<B> B|2"];
> structa [label="<A> A|1"];
> structc [label="<C> C|3"];
>
> structptr:ptr -> structb:B:nw
> structadptr:adptr -> structptr:name_ptr:nw
> structp:p -> structptr:name_ptr:nw
> }
> ```
**Pointers vs. Arrays**
> - array vs. pointer
> - in declaration
> - extern, 如 `extern char x[];` $\to$ 不能變更為 pointer 的形式
> - definition/statement, 如 `char x[10]` $\to$ 不能變更為 pointer 的形式
> - parameter of function, 如 `func(char x[])` $\to$ 可變更為 pointer 的形式 $\to$ `func(char *x)`
> - in expression
> - array 與 pointer 可互換
> `x[i]` 總是被編譯器改寫為 `*(x + i)` $\leftarrow$ in expression
> ```c
> int main() {
> int x[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
> printf("%d %d %d %d\n", x[4], *(x + 4), *(4 + x), 4[x]);
> }
> ```
>
> - array subscripting 在**編譯時期**只確認以下兩件事:
> - 得知 size
> - 取得陣列第 0 個 (即最初的一項) 元素的指標
> - 前兩者以外的操作，都透過 pointer
> - array subscripting => syntax sugar
**Function Pointer**
```C
int main() { return (********puts)("Hello"); }
```
> - function designator - 基本上就是 function name
無論函式名稱 (此為 `puts` ) 加上多少個 `*` ，他仍是一個 `function designator` ，最後被轉為 `pointer to function returning type` ，所以 `*` 的數目不會影響結果。
**Address and indirection operators**
> * `[]` or `*` 的操作結果：跟這兩個作用時，基本上就是相消
> - `*` - operand 本身
> - `[]` - `&` 會消失，而 `[]` 會被轉換成只剩 `+` (註：原本 `[]` 會是 `+` 搭配 `*`)
> + 例如: `&(a[5]) == a + 5`
>
> ```c
> char str[123];
> ```
> 為何 str == &str 呢？
> * 實際上左右兩邊的型態是不一樣的，只是值相同。
> * 左邊的是 pointer to char：`char *`
> - 規格書中表示：除非遇到 sizeof 或是 & 之外，array of type (在這就是指 str) 都會被直接解讀成 pointer to type (在這就是 pointer to char)，而這個 type 是根據 array 的第一個元素來決定的。
> * 右邊的則是 pointer to an array： `char (*)[123]`
> - 上面提到：遇到 & 時，str 不會被解讀為 pointer to type，而是做為原本的 object，在這就是 array object，而 address of array object 也就是這個 array object 的起始位址，當然也就會跟第一個元素的位址相同。
**重新探討「字串」**
> - 由於 C 語言提供了一些 syntax sugar 來初始化陣列，這使得 `char *p = "hello world"` 和 `char p[] = "hello world"` 寫法相似，但底層的行為卻大相逕庭
> - 背景知識: [你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/s/SJ6hRj-zg) 關於 stack 的描述
> - 以指標的寫法 `char *p` 來說，意思是 `p` 將會是指向 static storage 的一個指標。如此的寫法有潛在問題，因為當開發者嘗試修改 string literals 的內容，將會造成未定義行為，而編譯器並不會對存取 p 的元素提出警告
> - 值得注意的是，陣列的寫法依據 C99 規範，string literals 是必須放在 "static storage" 中，而 `char p[]` 的語意則表示要把資料分配在 stack 內，所以這會造成編譯器 (gcc) 隱性地 (implicitly) 產生額外的程式碼，使得 C 程式在執行時期可把 string literals 從 static storage 複製到 stack 中。雖然字串本身並非存放於 stack 內，但 `char p[]` 卻是分配在 stack 內，這也造成 `return p` 是未定義行為
如果是用 char p[]的方法，直接印出p是可以的，但如果是要return就會出錯，因為一離開函式該空間便會被清除。
> [使用函式回傳字串](https://ithelp.ithome.com.tw/questions/10204274)
> 在C語言，要回傳字串還是只能用全域變數或靜態修飾宣告，強制將記憶體位置放置不會被free掉的地方。否則在離開函式copystr()的時候就，宣告char *a會free掉, 回傳的位址指向的東西將是一串無意義的東西。
若使用char *p = "hello world"話，只要不改他就不會出現這個問題，但他的問題是literals不能改值。因此建議改用const char * p = "hello world" ，如此一來便無法改動 p 指向位址之值。
**C 語言 offsetof 巨集的定義**
> `<stddef.h>` 定義了 [offsetof 巨集](https://en.wikipedia.org/wiki/Offsetof)，取得 struct 特定成員 (member) 的位移量。傳統的實作方式如下:
> ```cpp
> #define offsetof(st, m) ((size_t)&(((st *)0)->m))
> ```
>
> 這對許多 C 編譯器 (像是早期的 gcc) 可正確運作，但依據 C99 規格，這是 undefined behavior。後來的編譯器就不再透過巨集來實作，而改用 builtin functions，像是 gcc:
> ```cpp
> #define offsetof(st, m) __builtin_offsetof(st, m)
> ```
>
> 這對於 C++ 非常重要，否則原本的巨集連編譯都會失敗。
>
> 延伸閱讀: [C99 的 offsetof macro](http://blog.linux.org.tw/~jserv/archives/001399.html)
>
> Linux 核心延伸 offsetof，提供 container_of 巨集，作為反向的操作，也就是給予成員位址和型態，反過來找 struct 開頭位址：
> ```cpp
> #define container_of(ptr, type, member) ({ \
> const typeof(((type *) 0)->member) *__mptr = (ptr); \
> (type *) ((char *)__mptr - offsetof(type,member) );})
> ```
因此，可透過此程式碼找出組合的 `struct` 之位置，如下
[此次lab0作業](https://github.com/sysprog21/lab0-c/tree/master)
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
`struct element_t` 中的成員 `list` 為 `struct list_head` ，其成員 `*prev` 及 `*next` 皆為指向 `struct list_head` 之指標，也就是無法只向下一個 `struct element_t` ，此時若利用 `container_of` ，可串接這兩個 `struct` ，並利用指向的 `struct list_head` (相當於 `struct element_t` 中的成員 `list` 之位置) ，反向尋找出 `struct element_t` 之位置。
#### 三、 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
**從 Linux 核心的藝術談起**
> ```c
> void remove_list_node(List *list, Node *target)
> {
> Node *prev = NULL;
> Node *current = list->head;
> // Walk the list
> while (current != target) {
> prev = current;
> current = current->next;
> }
> // Remove the target by updating the head or the previous node.
> if (!prev)
> list->head = target->next;
> else
> prev->next = target->next;
> }
> ```
> 直觀的寫法會有特例，也就是第一筆資料與中間的資料的移去操作不同。
> 若要移去的是第一筆資料，那就需要把指標指向第一個節點；而若是要移除中間的資料，則須要把指標指向目標的前一個節點。
> ```c
> void remove_list_node(List *list, Node *target)
> {
> // The "indirect" pointer points to the *address*
> // of the thing we'll update.
> Node **indirect = &list->head;
> // Walk the list, looking for the thing that
> // points to the node we want to remove.
> while (*indirect != target)
> indirect = &(*indirect)->next;
> *indirect = target->next;
> }
> ```
> Linus Torvalds 換個角度來思考，通過指標的指標 (或稱「間接指標」，即 indirect pointer) 來操作，如此一來，上面的特例就不存在。
第一個方法為檢測指向的值是否正確，因此需要一個額外的指標去保留，當要移除時需判別是否為第一個再去決定將什麼指標重接。
第二個方法是利用指標之指標，這樣實際上之指標會為在上一個指標所指向的 `node` ，即上一個 `node` ，因此無須因為是否為 `head` 而去使用不同方法。
> ```c
> void append(int value, list_entry_t **head)
> {
> list_entry_t *direct = *head;
> list_entry_t *prev = NULL;
>
> list_entry_t *new = malloc(1 * sizeof(list_entry_t));
> new->value = value, new->next = NULL;
>
> while (direct) {
> prev = direct;
> direct = direct->next;
> }
>
> if (prev)
> prev->next = new;
> else
> *head = new;
> }
> ```
>
> 函式的參數列表中，之所以用 `list_entry_t **head`，而非 `list_entry_t *head`，是因為原本傳入的 `head` 可能會被變更，但 C 語言在參數傳遞時永遠都是傳遞數值 (副本)，於是若接受 `list_entry_t *head` 做為參數，那就要提供 `append` 函式的傳回值，也就是說，該函式原型宣告變為:
> ```c
> list_entry_t *append(int value, list_entry_t *head);
> ```
> 或運用 indirect pointer 的技巧:
> ```c
> void append_indirect(int value, list_entry_t **head)
> {
> list_entry_t **indirect = head;
>
> list_entry_t *new = malloc(1 * sizeof(list_entry_t));
> new->value = value, new->next = NULL;
>
> while (*indirect)
> indirect = &((*indirect)->next);
>
> *indirect = new;
> }
> ```
如果在函數內部修改 head 指標的值，即讓它指向新的 `linked list` 頭部，這個修改僅在函數內部有效，不會影響外部。為了在函數內部修改外部傳入的指針，需要使用 `list_entry_t **head` 作為參數。
將函式名稱前加上指標變為 `pointer to function returning type` ，將使回傳類型為指標，而指標的副本仍指向同一個位置，因此可回傳修改後的原始 `linked list` 。
**案例探討: LeetCode 21. Merge Two Sorted Lists**
> 使用 indirect pointer
> ```c
> struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
> struct ListNode *head = NULL, **ptr = &head, **node;
>
> for (node = NULL; L1 && L2; *node = (*node)->next) {
> node = (L1->val < L2->val) ? &L1: &L2;
> *ptr = *node;
> ptr = &(*ptr)->next;
> }
> *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
> return head;
> }
> ```
> 但如何取值做合併也是非常重要
1. naive
> ```c
> struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
> if (listsSize == 0) return NULL;
> for (int i = 1; i < listsSize; i++)
> lists[0] = mergeTwoLists(lists[0], lists[i]);
> return lists[0];
> }
> ```
缺點 : 以不斷增長的第一條串列去添加剩餘的串列，造成合併速度減緩。
2. 頭跟尾兩兩合併
> ```c
> struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
> if (listsSize == 0) return NULL;
>
> while (listsSize > 1) {
> for (int i = 0, j = listsSize - 1; i < j; i++, j--)
> lists[i] = mergeTwoLists(lists[i], lists[j]);
> listsSize = (listsSize + 1) / 2;
> }
>
> return lists[0];
> }
> ```
多條串列頭尾兩兩合併，類似等差級數求和之梯形公式，多數情況下長度較平均，合併較快。
3. 分段合併
> ```c
> struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
> if (listsSize == 0) return NULL;
>
> for (int interval = 1; interval < listsSize; interval *= 2)
> for (int i = 0; i + interval < listsSize; i += interval * 2) {
> lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
> }
>
> return lists[0];
> }
> ```
其方法類似 [count leading zero](https://en.wikipedia.org/wiki/Find_first_set)
以下為 unsign_int 32 實作
```c
uint16_t count_leading_zeros(uint32_t x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
/* count ones (population count) */
x -= ((x >> 1) & 0x55555555);
x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
x = ((x >> 4) + x) & 0x0f0f0f0f;
x += (x >> 8);
x += (x >> 16);
return (32 - (x & 0x7f));
}
```
大致上概念為將最高位1右側bit全補為1，並以以下視覺化圖片實作計算右側 1 總數。
> ```graphviz
> digraph G {
> {
> node[shape=none,label="interval = 1"]; i1
> node[shape=none,label="interval = 2"]; i2
> node[shape=none,label="interval = 4"]; i4
> node[shape=none,label="interval = 8"]; i8
> }
>
> interval1[label="<f0>L0|<f1>L1|<f2>L2|<f3>L3|<f4>L4|<f5>L5|<f6>L6|<f7>L7", shape=record, fixedsize=false,width=6]
> interval2[label="<f0>L01|<f1>|<f2>L23|<f3>|<f4>L45|<f5>|<f6>L67|<f7>", shape=record, fixedsize=false,width=6]
> interval4[label="<f0>L0123|<f1>|<f2>|<f3>|<f4>L4567|<f5>|<f6>|<f7>", shape=record, fixedsize=false,width=6]
> interval8[label="<f0>result|<f1>|<f2>|<f3>|<f4>|<f5>|<f6>|<f7>", shape=record, fixedsize=false,width=6]
>
> i1->i2[style=invis]
> i2->i4[style=invis]
> i4->i8[style=invis]
>
>
> interval1:f0 -> interval2:f0
> interval1:f1 -> interval2:f0
> interval1:f2 -> interval2:f2
> interval1:f3 -> interval2:f2
> interval1:f4 -> interval2:f4
> interval1:f5 -> interval2:f4
> interval1:f6 -> interval2:f6
> interval1:f7 -> interval2:f6
> interval1:f7 -> interval2:f7[style=invis]
>
> interval2:f0 -> interval4:f0
> interval2:f2 -> interval4:f0
> interval2:f4 -> interval4:f4
> interval2:f6 -> interval4:f4
> interval2:f7 -> interval4:f7[style=invis]
>
> interval4:f0 -> interval8:f0
> interval4:f4 -> interval8:f0
> interval4:f7 -> interval8:f7[style=invis]
> }
> ```
4. Divide and Conquer
> ```c
> struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
> if (!listsSize)
> return NULL;
> if (listsSize <= 1)
> return *lists;
>
> int m = listsSize >> 1;
> struct ListNode *left = mergeKLists(lists, m);
> struct ListNode *right = mergeKLists(lists + m, listsSize - m);
>
> return mergeTwoLists(left, right);
> }
> ```
不斷分左右邊直到 `listSize <= 1`，並會先做 `mergeTwoLists` 再回傳，因此最後也是經排序過之資料。
>
**案例探討: Leetcode 2095. Delete the Middle Node of a Linked List**
快慢指標
> ```c
> struct ListNode *deleteMiddle(struct ListNode *head) {
> if (!head->next) return NULL;
>
> struct ListNode **indir = &head, *prev = NULL;
> for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
> prev = *indir;
> indir = &(*indir)->next;
> }
> prev->next = (*indir)->next;
> free(*indir);
> return head;
> }
> ```
> 這裡考慮給定的鏈結串列為 [1, 3, 4, 7, 1, 2, 6]，上述的程式碼在迴圈結束後，*indir 會指向內容為 7 的節點 (以下記做 node7)，prev 緊隨其後指向內容為 4 的節點 (以下記做 node4)，換言之，prev->next 就是 *indir。
>
> 找出 indir 跟 prev 所指向的節點與關係後，可知 prev->next = (*indir)->next; 相當於 (*indir) = (*indir)->next;，而 **`**indir` 為指標的指標，因此他會指向指向 `prev->next` 的 `node` ， 即 `prev`** ，因此 `*indir` 會從 node4 指向 node1。
>
> 在 `free(*indir)` 時， `node1` 會被 free 掉，而被偵測到 heap-use-after-free。
> 因此改用 `*next` 來儲存 `(*indir)->next`
> ```c
> struct ListNode *deleteMiddle(struct ListNode *head) {
> if (!head->next) return NULL;
>
> struct ListNode **indir = &head, *prev = NULL;
> for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
> prev = *indir;
> indir = &(*indir)->next;
> }
> struct ListNode *next = (*indir)->next;
> free(*indir);
> prev->next = next; // *indir = next
> return head;
> }
> ```
> 或無須 prev 指標：
> ```c
> struct ListNode *deleteMiddle(struct ListNode *head) {
> struct ListNode **indir = &head;
> for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next)
> indir = &(*indir)->next;
> struct ListNode *del = *indir;
> *indir = (*indir)->next;
> free(del);
> return head;
> }
> ```
須留意指標的指標的應用以避免指向錯誤之處。
快慢指標的應用，這邊我的第一想法會是第一次遍歷一次 `linked list` 並記錄數量，然後再一次遍歷，直到數到中間那一個。若以快慢指標， `fast` 一次動兩格，而 `indir` 一次動一格，那 `fast` 抵達終點時 `indir` 剛好位於中間，因此可以一次遍歷並無須花費額外記憶體儲存，
**案例探討: LeetCode 86. Partition List**
> 目的為：給定一個鏈結串列跟整數 x，將串列分割成兩組，比 x 小的節點置前，大於或等於 x 的節點置後，應維持分割前的順序。
> ```c
> struct ListNode *partition(struct ListNode *head, int x)
> {
> struct ListNode *l2 = NULL;
> struct ListNode **p1 = &head, **p2 = &l2;
>
> for (struct ListNode *node = head; node; node = node->next) {
> if (node->val < x) {
> *p1 = node;
> p1 = &(*p1)->next;
> } else {
> *p2 = node;
> p2 = &(*p2)->next;
> }
> }
>
> *p1 = l2;
> *p2 = NULL;
> return head;
> }
> ```
> 利用「指標的指標的指標」來簡化程式碼
> ```c
> struct ListNode *partition(struct ListNode *head, int x)
> {
> struct ListNode *l2 = NULL;
> struct ListNode **p1 = &head, **p2 = &l2;
>
> for (struct ListNode *node = head; node; node = node->next) {
> struct ListNode ***indir = node->val < x ? (&p1): (&p2);
> **indir = node;
> *indir = &(**indir)->next;
> }
>
> *p1 = l2;
> *p2 = NULL;
> return head;
> }
> ```
先利用 `***indir` 來決定要接在哪一個指標的指標，才開始接。
**circular linked list**
[Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection)
> Let μ be the smallest index such that the value xμ reappears infinitely often within the sequence of values xi, and let λ (the loop length) be the smallest positive integer such that xμ = xλ + μ. The cycle detection problem is the task of finding λ and μ.
這邊不貼教材原始碼，只解釋教材裡面沒解釋到的變數。
**Linux 核心原始程式碼**
`WRITE_ONCE`
>
> 藉由 WRITE_ONCE 和 READ_ONCE 的使用，可以避免編譯器合併、切割、甚至重排特定的記憶體讀寫操作。下面是 WRITE_ONCE 的定義:
> ```c
> #define WRITE_ONCE(x, val) \
> ({ \
> union { typeof(x) __val; char __c[1]; } __u = \
> { .__val = (val) }; \
> __write_once_size(&(x), __u.__c, sizeof(x)); \
> __u.__val; \
> })
> ```
> 我們可以再次看到 statement expression 技巧的應用。此外，可以看到 WRITE_ONCE 把 val 寫入 union 結構中，使其與一個 char __c[1] 共享空間。藉由以 union 為基礎的 type-punning 技巧，可避免違反 strict aliasing 規則，使得 __c 能作為這個 union 的指標來使用，從而允許編譯器最佳化。
何謂 aliasing
>其所指為同一個位置可被多個 symbol 存取時，這種情形會造成編譯器最佳化的限制。根據 Options That Control Optimization， -fstrict-aliasing 參數會讓編譯器假設程式撰寫者不會將相似類型 (例如 int 和 unsigned int) 以外的指標予以指向同一塊記憶體空間，以允許做更激進的最佳化。
**Linux 核心的 `list_sort` 實作**
> 方法會保持兩個要被 merge 的 list 至少是 2 : 1 的狀態 (較大的 list 至多是較小者的 2 倍)，這可有效的降低比較的次數。list_sort 與一般的 fully-eager bottom-up mergesort 方法不同，後者只要出現兩個 $2^k$ 大小的 list，就會立刻被合併。而前者的方法是在出現兩個 $2^k$ 大小的 list 的時候，不立即合併，反之，一直等到下一個 $2^k$ 的 list 被蒐集起來時，前者的這兩個 linked list 才會被合併起來。只要這 2 : 1 的 list 可以完全被放到 cache 裡，就可避免 cache thrashing。
>
> 方法中會透過一個 `count` 來紀錄 pending 的節點數量。當目前的 count + 1 後，會設置第 $k$ 個 bit 為 1，$k-1$ 至 0 bit 為 0 時(除了 `count` 為 $2^k - 1$ 的情境)，我們就把兩個 $2^k$ 長度的 list 做合併。
>
> * $2^0$ $\to$ count = 1 = $1_{2}$ $\to$ $2^0$ + $2^0$ (no merge)
> * $2^0$ + $2^0$ $\to$ count = 2 = $10_{2}$ $\to$ $2^1$ + $2^0$ (將 $10_{2}$ 加 1 的話 set bit 0，merge to 2^1)
> * $2^1$ + $2^0$ count = 3 = $11_{2}$ -> $2^1$ + $2^0$ + $2^0$ (no merge)
> * $2^1$ + $2^0$ + $2^0$ $\to$ count = 4 = $100_{2}$ $\to$ $2^1$ + $2^1$ + $2^0$ (將 $100_{2}$ 加 1 的話 set bit 0 $\to$ merge to $2^1$)
>
> * $2^1$ + $2^1$ + $2^0$ $\to$ count = 5 = $101_{2}$ $\to$ $2^2$ + $2^0$ + $2^0$ (將 $101_{2}$ 加 1 的話 set bit 1 $\to$ merge to $2^2$)
>
> * $2^2$ + $2^0$ + $2^0$ $\to$ count = 6 = $110_{2}$ $\to$ $2^2$ + $2^1$ + $2^0$ (將 $110_{2}$ 加 1 的話 set bit 0 $\to$ merge to $2^1$)
當 `count == 5` 再加 1 後，會設置第 $k$ 個 bit 為 1 ，而這裡 $k$ = 1 ( 因從 `兩個`$2^k$`大小的 list` 這句話看出 $k$ 指的是存在兩個相同大小 `list` 的指數，因此 $k$ 便是 `1` )，而 $k-1$ 至 0 bit 為 0 時 ，就把兩個 $2^k$ 長度的 list 做合併。而範例給的是 count = 5 = $101_{2}$ ，再加 1 ，變為 $110_{2}$ ，同時設置第 1 個 bit 為 1 ，因 $k-1$ (0) 至 0 bit 為 0 ，因此合併。
#### 四、[Linux 核心設計: 作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts)
Sign in with Wallet
Connect another wallet