# 2025q1 Homework1 (lab0)
contributed by < [Hlunlun](https://github.com/Hlunlun) >
## Reviewed by `yy214123`
### `q_free`
在 `queue.h` 中有實作：
```c
static inline void q_release_element(element_t *e)
{
test_free(e->value);
test_free(e);
}
```
可以如下改善：
```diff
void q_free(struct list_head *head)
{
element_t *entry = NULL, *safe;
list_for_each_entry_safe(entry, safe, head, list) {
- free(entry->value);
- free(entry);
+ q_release_element(entry);
}
free(head);
return;
}
```
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```bash
lun@lun-OMEN:~/linux2025/hw1/lab0-c$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## 開發步驟與工具
1. 前置作業
- 安裝雙系統：[安裝雙系統在有兩個 SSD 的 hp 筆電上](https://hackmd.io/@clh/linux-00)
- 安裝套件
```
sudo apt install build-essential git-core valgrind
sudo apt install cppcheck clang-format aspell colordiff
```
2. 取得程式碼與測試
```cpp
git clone https://github.com/sysprog21/lab0-c
```
3. 每次開發完一個函數就 commit ，紀錄開發過程
```bash
clang-format -i <file>
git add <file>
git commit -a
git push
```
## 實做佇列
### `q_new`
- C99 [7.20.3.3] ***The malloc function***
>The malloc function returns either a null pointer or a pointer to the allocated space
`malloc` 如果沒有成功配置到記憶體是有可能回傳 NULL 的，所以要檢查 `malloc` 要求的記憶體是否有成功
- 問題：但後來在 `make test` 後發現第 13 個 trace 無法通過
>猜測這個函式可能是一定要配置到記憶體位置才是正確的，因此使用迴圈檢查記憶體配值直到成功為止，經過 [Commit 4417ea0](https://github.com/Hlunlun/lab0-c/commit/4417ea0f755e43d724a9bb1d31f957d29ffbe98b) 竟然就通過測資了，但是這樣可能會造成記憶體一直不夠一直再回圈中檢查，造成整個系統異常，要在想原因是什麼
>2025/03/09 不要平感覺寫程式
```diff
struct list_head *q = malloc(sizeof(struct list_head));
- if (q == NULL)
- return NULL;
+ while (q == NULL)
+ q = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(q);
return q;
```
### `q_free`
先將 `list` 移除，在釋放整個節點
### `q_insert_head` 、`q_insert_tail`
- 重點：需要更注意 字串 的記憶體配置
- 問題：原本我直接把 `element->value` 指向 `s`，如果有在其他地方有人對 `s` 做任何變更或是釋放記憶體，`element->value` 就會也跟著改變，所以應該是要用 `strdup` 配置新的空間給 `element->value`
- 在 [你不知道的C語言：指標篇](https://youtu.be/Owxols1RTAg?t=6715) 中也有說到字串的生命週期有可能快結束，所以才使用 `strdup`
```diff
- element->value = s;
+ element->value = strdup(s);
if (!element->value) {
free(element);
return false;
```
- 那為何要判斷 `element->value` 是否為 `NULL` 呢？
可以運用 linux 的說明文件 [man page](https://zh.wikipedia.org/zh-tw/%E6%89%8B%E5%86%8C%E9%A1%B5)，在 terminal 打上 `man strdup`，這時候就會看到因為在使用 `strdup` 時會用到 `malloc`，而在規格書 C99 [7.20.3.3] 中有提到 `malloc` 有可能因為記憶體不夠用而造成記憶體配置失敗從而回傳 `NULL`，所以才要檢查 `element->value`
>The strdup() function returns a pointer to a new
string which is a duplicate of the string s. Memory
for the new string is obtained with malloc(3), and
can be freed with free(3).
### `q_remove_head` 、`q_remove_tail`
- 重點：只要 unlinlk 就好，不用釋放記憶體，找到第一個 `list_head` 節點，然後 unlink
- 問題 ：**copying of string in remove_head overflowed destination buffer.**
原本我是直接用 `bufsize` 有多大就複製多大的 `entry->value` 到 `sp` ，但如果 `entry->value` 的長度比 `bufsize` 小，會有 **buffer overflow detected** 的錯誤
- 這裡就會好奇所以 [strncpy 是否會自動補上 \0](https://hackmd.io/@unknowntpo/strncpy) ，從 man page 看到 `strncpy` 的實做原理，可以看到這個函式會用到 `strpncpy` 並且在其中會檢查 `dsize` 和 `src` 的長度，但是並沒有和 `dst` 比較，而這裡的 `q_remove_*` 會有 `bufsize` 的限制，所以要而外檢查 `element->value` 的大小，經過 [commit 27965a2](https://github.com/Hlunlun/lab0-c/commit/27965a21dfdc383d6505efa1a4b6b247003c69ac) 即可解決這個問題
```cppchar *
stpncpy(char *restrict dst, const char *restrict src, size_t dsize)
{
size_t dlen;
dlen = strnlen(src, dsize);
return memset(mempcpy(dst, src, dlen), 0, dsize - dlen);
}
```
- 關於可以複製多大的字串到 `sp` ，在 `man strncpy` 中，看到了 `strncpy` 的實做使用到 `strnlen(src, dsize)` ，這個函式會回傳 `min(strlen(src), dsize)` ，可以讓程式碼更精簡，因此做了 [commit d03a3d8](https://github.com/Hlunlun/lab0-c/commit/d03a3d832eb103215ba787fe65aaad4d41250d1c) 的修改
```diff
if (sp) {
- size_t size = strlen(entry->value) < (bufsize - 1)
- ? strlen(entry->value)
- : (bufsize - 1);
- strncpy(sp, entry->value, size);
- sp[size] = '\0';
+ size_t dlen = strnlen(entry->value, bufsize - 1);
+ mempcpy(sp, entry->value, dlen);
+ *(sp + dlen) = 0;
}
```
### `q_delete_mid`
運用 [指標的指標](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHyBPr9WGl#%E6%B2%92%E6%9C%89%E3%80%8C%E9%9B%99%E6%8C%87%E6%A8%99%E3%80%8D%E5%8F%AA%E6%9C%89%E3%80%8C%E6%8C%87%E6%A8%99%E7%9A%84%E6%8C%87%E6%A8%99%E3%80%8D) 技巧，找到指向 `middle node` 的 指標 ，然後將它移除，只是這裡的迴圈判斷條件是 `fast` 和 `fast->next` 還沒到迭代到 `head` 之前，如 [commit a351491](https://github.com/Hlunlun/lab0-c/commit/a351491f34dfd7727990bdbbc21e463110885728)
### `q_delete_dup`
使用 `list_for_each_entry_safe` 才可以在迭代過程中移除節點，因為只要出現多於 1 次就要全部移除，所以需要一個標誌來確認目前此次刪除是否進行完，如 [commit 49224d8](https://github.com/Hlunlun/lab0-c/commit/49224d844bc6d2ba3b1e25123ee7e69a3ef45383)
```cpp
list_for_each_entry_safe(node, safe, head, list) {
if (&safe->list != head && !strcmp(node->value, safe->value)) {
//delete node
dup = true;
} else if (dup) {
//delete node
dup = false;
}
}
```
### `q_swap`
先看 `list_for_each_safe`，所以使用這個巨集時，要 swap 的就是 `node` 和 `safe`
```cpp
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
因為是每兩個節點交換位置，所以每次迭代 `safe` 和 `node` 需要移動兩個位置，且要檢查 `safe` 和 `node` 都不是 `head`，但 `node` 會在 `list_for_each_safe` 中被檢查是否是 `head`，所以只要檢查 `safe` 就行，如 [commit 6a80e4b](https://github.com/Hlunlun/lab0-c/commit/6a80e4bf019cd38da71aab3b22d870cab8589ef4)
```cpp
list_for_each_safe(node, safe, head) {
if (safe == head)
return;
struct list_head *next = safe->next;
struct list_head *prev = node->prev;
//... node 和 safe 兩個節點交換位置
safe = node->next;
}
```
### `q_reverse`
- 重點：利用雙向鍊結串列的特性，改變每個節點的 `prev` 和 `next`，如 [commit 7203bbd](https://github.com/Hlunlun/lab0-c/commit/7203bbdff068c448bf05fd73234552efc708e56c)
### `q_reverseK`
為了可以直接使用到 [`q_reverse`](#q_reverse)，可以透過 `list_cut_position` 將雙向鍊結串列中的片段切割出來使用 `q_reverse` 去倒轉，將到轉完的雙向鍊結串列先存放在暫時的 `new_head` 中，繼續迭代 `head` 找出 k-group 的片段，最後在將 `new_head` 用 `list_splice` 全部拼接到 `head`，如 [commit b4dc453](https://github.com/Hlunlun/lab0-c/commit/b4dc4535f6da96b0cbee26336d548828f0ae93b9)
### `q_sort`
透過 [研讀 Linux 核心原始程式碼的 lib/list_sort.c](#研讀-Linux-核心原始程式碼的-liblist_sortc) 了解排序運作原理後，實做在此函數，如 [commit 4ebd88e](https://github.com/Hlunlun/lab0-c/commit/4ebd88ec6d154fcfcdb74e9e0221062a58ae34cf)
**C99 [7.21.4.2] The strcmp function**
應該使用 `strcmp` 函數來比較兩個字串，因為此函數是比較指標指向的記憶體位置中存放的值
>The strcmp function compares the string pointed to by s1 to the string pointed to by s2.
**C99 [6.5.8] Relational operators**
如果直接使用 關係運算子 (Relational operator) 對兩個指標( `list_entry(a, element_t, list)` 的屬性 `value` 變數類型是指標) 進行比較，則是比較指標指向的記憶體位置，而非記憶體中存放的數值
>When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object or incomplete types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript
```diff
bool cmp(const struct list_head *a, const struct list_head *b, bool descend)
{
+ element_t *e1 = list_entry(a, element_t, list);
+ element_t *e2 = list_entry(b, element_t, list);
+
if (descend)
- return list_entry(a, element_t, list)->value >=
- list_entry(b, element_t, list)->value;
+ return strcmp(e1->value, e2->value) >= 0;
- return list_entry(a, element_t, list)->value <=
- list_entry(b, element_t, list)->value;
+ return strcmp(e1->value, e2->value) <= 0;
```
### `q_ascend`、`q_descend`
兩個函數都只要將最右邊當作基準點去由右而左迭代，只要遇到 `left` 比 `right` 指向的節點還要 小( `q_descend` ) 或大( `q_ascend` )就刪除，並且一直往左走直到 `left` 走到 `head` ，如 [commit ed4547b](https://github.com/Hlunlun/lab0-c/commit/ed4547b0fa4cf1b5b7a5f6f66536413e83aca659)
### `q_merge`
此函數主要功能就是將在不同 `q_context_t` 中的雙向鍊結串列 `q` 全部合併到第一個 `q_context_t` 中的 `q` ，不同的 `q_context_t` 則是藉由 `chain` 來連接(下圖藍色線條)，且在合併之前的每個 `q` 都保證已經排序過，因為是字串，所以 "10" 小於 "23"
```graphviz
digraph ll{
node[shape=record];
head[label="<next>next|<ref>head|<prev>prev"];
subgraph cluster1
{
label="first q_context_t";
q1[label="<prev>prev|<ref>q|<next>netx"];
c1[label="<prev>prev|<ref>chain|<next>next"];
n11[label="<prev>prev|<ref>\"10\"|<next>next"]
n12[label="<prev>prev|<ref>\"23\"|<next>next"]
n13[label="<prev>prev|<ref>\"7\"|<next>next"]
q1:next -> n11:ref;
n11:prev -> q1:ref;
n11:next -> n12:ref;
n12:prev -> n11:ref;
n12:next -> n13:ref;
n13:prev -> n12:ref;
n13:next -> q1:ref;
q1:prev -> n13:ref;
}
subgraph cluster2
{
label="second q_context_t";
q2[label="<prev>prev|<ref>q|<next>next"];
c2[label="<prev>prev|<ref>chain|<next>next"];
n21[label="<prev>prev|<ref>\"12\"|<next>next"]
n22[label="<prev>prev|<ref>\"17\"|<next>next"]
n23[label="<prev>prev|<ref>\"2\"|<next>next"]
q2:next -> n21:ref;
n21:prev -> q2:ref;
n21:next -> n22:ref;
n22:prev -> n21:ref;
n22:next -> n23:ref;
n23:prev -> n22:ref;
n23:next -> q2:ref;
q2:prev -> n23:ref;
}
subgraph cluster3
{
label="third q_context_t";
q3[label="<prev>prev|<ref>q|<next>next"];
c3[label="<prev>prev|<ref>chain|<next>next"];
n31[label="<prev>prev|<ref>\"19\"|<next>next"]
n32[label="<prev>prev|<ref>\"5\"|<next>next"]
n33[label="<prev>prev|<ref>\"6\"|<next>next"]
q3:next -> n31:ref;
n31:prev -> q3:ref;
n31:next -> n32:ref;
n32:prev -> n31:ref;
n32:next -> n33:ref;
n33:prev -> n32:ref;
n33:next -> q3:ref;
q3:prev -> n33:ref;
}
head:next -> c1:ref[color="blue"];
c1:prev -> head:ref[color="blue"];
c1:next -> c2:ref[color="blue"];
c2:prev -> c1:ref[color="blue"];
c2:next -> c3:ref[color="blue"];
c3:prev -> c2:ref[color="blue"];
c3:next -> head:ref[color="blue"];
head:prev -> c3:ref[color="blue"];
}
```
合併後應該要是長這樣，除了第一個 `q_context_t` 中的 `q`，其餘 `q_context_t` 中的 `q` 都會變空的雙向鍊結串列
```graphviz
digraph ll{
node[shape=record];
head[label="<next>next|<ref>head|<prev>prev"];
subgraph cluster1
{
label="first q_context_t";
q1[label="<prev>prev|<ref>q|<next>netx"];
c1[label="<prev>prev|<ref>chain|<next>next"];
n11[label="<prev>prev|<ref>\"10\"|<next>next"]
n12[label="<prev>prev|<ref>\"12\"|<next>next"]
n13[label="<prev>prev|<ref>\"17\"|<next>next"]
n14[label="<prev>prev|<ref>\"19\"|<next>next"]
n15[label="<prev>prev|<ref>\"2\"|<next>next"]
n16[label="<prev>prev|<ref>\"23\"|<next>next"]
n17[label="<prev>prev|<ref>\"5\"|<next>next"]
n18[label="<prev>prev|<ref>\"6\"|<next>next"]
n19[label="<prev>prev|<ref>\"7\"|<next>next"]
q1:next -> n11:ref;
n11:prev -> q1:ref;
n11:next -> n12:ref;
n12:prev -> n11:ref;
n12:next -> n13:ref;
n13:prev -> n12:ref;
n13:next -> n14:ref;
n14:prev -> n13:ref;
n14:next -> n15:ref;
n15:prev -> n14:ref;
n15:next -> n16:ref;
n16:pre -> n15:ref;
n16:next -> n17:ref;
n17:prev -> n16:ref;
n17:next -> n18:ref;
n18:prev -> n17:ref;
n18:next -> n19:ref;
n19:prev -> q1:ref;
q1:prev -> n19:ref;
}
subgraph cluster2
{
label="second q_context_t";
q2[label="<prev>prev|<ref>q|<next>next"];
c2[label="<prev>prev|<ref>chain|<next>next"];
q2:prev -> q2:ref;
q2:next -> q2:ref;
}
subgraph cluster3
{
label="third q_context_t";
q3[label="<prev>prev|<ref>q|<next>next"];
c3[label="<prev>prev|<ref>chain|<next>next"];
q3:prev -> q3:ref;
q3:next -> q3:ref;
}
head:next -> c1:ref[color="blue"];
c1:prev -> head:ref[color="blue"];
c1:next -> c2:ref[color="blue"];
c2:prev -> c1:ref[color="blue"];
c2:next -> c3:ref[color="blue"];
c3:prev -> c2:ref[color="blue"];
c3:next -> head:ref[color="blue"];
head:prev -> c3:ref[color="blue"];
}
```
這裡我直接把其他 `queue_context_t` 中的雙向鍊結串列拼接到第一個 `queue_context_t` 中，在用 [`q_sort`](#q_sort) 進行排列即完成，commit
至此，即佇列各種函數的實做，成功就會出現[星之卡比的圖片](https://hackmd.io/_uploads/H1TP7k-CJg.png)
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
參考：[坤諦江](https://hackmd.io/@chiangkd/BJBB9rnzq) 、[The Linux Kernel](https://docs.kernel.org/index.html#the-linux-kernel-documentation)、[Risheng](https://hackmd.io/@Risheng/list_sort)
### `__attribute__`
>參考 [GNU 6.35.1 Common Function Attributes](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html)
其中這段有提到 [`nonnull` function attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-nonnull-function-attribute) 可能會用在至少有一個指標參數的函數，告訴編譯器哪幾個指標參數必為非空指標
>The nonnull attribute may be applied to a function that takes at least one argument of a pointer type. It indicates that the referenced arguments must be non-null pointers. For instance, the declaration...informs the compiler that, in calls to my_memcpy, arguments dest and src must be non-null.
[lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 使用的 函數屬性 使其第 2、3、4 個參數 `cmp` 、`a` 、 `b` 必須為非空的指標，所以從程式碼可以間接知道 `cmp` 是指標，因為 `__attribute__((nonnull))` 只用於限制指標參數(可以透過閱讀 [`nonnull` function attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-nonnull-function-attribute) 範例得出結論 )
```cpp
__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
```
仔細閱讀 函數屬性 在函數被觸發以及在編譯階段定義時會有不同的效果，在函數被觸發時如果在標記為 `nonnull` 的位置傳入 `null` 會觸發緊告，所以其實程式還是可以通過編譯，但是會有警告
>If the compiler determines that a null pointer is passed in an argument slot marked as non-null, and the [`-Wnonnull`](https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html) option is enabled, a warning is issued.
在課堂上老師也不斷提及 linux kernel 是牽一髮而動全身的，所以開發者必須更謹慎小心，而 `__attribute__` 就是一種警告機制，把控傳參數這樣的細節
### `list_cmp_func_t cmp`
解釋 [函數屬性](#__attribute__) 時提及 `cmp` 是一個指標，其型態定義於 [linux/list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) ，將 整數 定義為一個 指標函數 (pointer to function) ，或者可以解釋為這是一個會回傳整數的指標函數
```cpp
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
const struct list_head *, const struct list_head *);
```
>為何不直接使用它原本的整數型態，還特別定義為 指標函數 呢？
透過程式中的註解解釋 `cmp`，此函數用於比較當前節點的數值，
```
The comparison function @cmp must return > 0 if @a should sort after
@b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
sort before @b *or* their original order should be preserved. It is
always called with the element that came first in the input in @a,
and list_sort is a stable sort, so it is not necessary to distinguish
the @a < @b and @a == @b cases.
```
### [`merge`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L13)
運用到 [指標的指標](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHyBPr9WGl#%E6%B2%92%E6%9C%89%E3%80%8C%E9%9B%99%E6%8C%87%E6%A8%99%E3%80%8D%E5%8F%AA%E6%9C%89%E3%80%8C%E6%8C%87%E6%A8%99%E7%9A%84%E6%8C%87%E6%A8%99%E3%80%8D) 技巧，進行兩個雙向鍊結串列的合併，並沒有去修改 `prev` 指標指向的節點，舉例以下 `a` 和 `b` 可能的樣貌，且最後一個節點都會是 `NULL` ，原因可以看到 [`merge_final` 的解釋內容](#merge_final)
```graphviz
digraph linked_list0 {
rankdir=LR;
node [shape=record];
// Improve edge routing
splines=true;
overlap=false;
// Position and style nodes
HEAD [label="<val>HEAD|{<prev> prev| <next>next}", shape=record];
tail [label="tail", style=filled, fillcolor="#D8E8D8"];
head [label="head", style=filled, fillcolor="#F8CACA"];
node1 [label="<val>1|{<prev>prev |<next> next }", shape=record];
node2 [label="<val>2 | {<prev> prev | <next> next }", shape=record];
node3 [label="<val>3|{<prev> prev| <next> next }", shape=record];
null [label="NULL", shape=none];
// Basic connections
tail -> head;
head -> node1:val;
// Explicitly define ALL edges with careful ordering
HEAD:next ->node1:val;
node1:next -> node2:val[arrowhead=vee];
node2:next -> node3:val[arrowhead=vee];
node3:next -> null[arrowhead=vee];
node1:prev -> HEAD:val[arrowhead=vee];
node2:prev -> node1:val[arrowhead=vee];
node3:prev -> node2:val[arrowhead=vee];
}
```
```graphviz
digraph linked_list {
rankdir=LR;
node [shape=record];
// Improve edge routing
splines=true;
overlap=false;
// Position and style nodes
HEAD [label="<val>HEAD|{<prev> prev| <next>next}", shape=record];
node1 [label="<val>2|{<prev>prev |<next> next }", shape=record];
node2 [label="<val>5 | {<prev> prev | <next> next }", shape=record];
node3 [label="<val>6|{<prev> prev| <next> next }", shape=record];
null [label="NULL", shape=none];
// Explicitly define ALL edges with careful ordering
HEAD:next -> node1:val;
node1:next -> node2:val[arrowhead=vee];
node2:next -> node3:val[arrowhead=vee];
node3:next -> null[arrowhead=vee];
node1:prev -> HEAD:val;
node2:prev -> node1:val[arrowhead=vee];
node3:prev -> node2:val[arrowhead=vee];
}
```
經過 `merge` 函數後，會呈現以下，也就是說只有將 `next` 指標指向對的節點，`prev` 指標依舊，也就是說按照 `next` 指標走，排列的順序是正確的
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
splines=true;
overlap=false;
tail [label="tail", shape=none, fontcolor="green"];
head [label="head", shape=none, fontcolor="red"];
node1 [label="<val>1|{<prev>prev |<next> next }", shape=record];
node2 [label="<val>2|{<prev>prev |<next> next }", shape=record];
node3 [label="<val>2|{<prev>prev |<next> next }", shape=record];
node4 [label="<val>3|{<prev>prev |<next> next }", shape=record];
node5 [label="<val>5|{<prev>prev |<next> next }", shape=record];
node6 [label="<val>6|{<prev>prev |<next> next }", shape=record];
null [label="NULL", shape=none];
head -> node1:val;
node1:next -> node2:val[arrowhead=vee];
node2:next -> node3:val[arrowhead=vee];
node3:next -> node4:val[arrowhead=vee];
node4:next -> node5:val[arrowhead=vee];
node5:next -> node6:val[arrowhead=vee];
node6:next -> null[arrowhead=vee];
tail -> null[arrowhead=vee];
node2:prev -> node1:val[arrowhead=vee];
node4:prev -> node3:val[arrowhead=vee];
node5:prev -> node4:val[arrowhead=vee];
}
```
### [`merge_final`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L49)
首先看到函數定義可知，參數中 `cmp` 、`head` 、`a` 、`b` 必不為空指標
```cpp
__attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b)
```
`head` 在 [`list_sort`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L189) 中作為呼叫 `merge_final` 的引數，可以知道 `head` 是一個雙向鍊結串列的第一個節點，而在 `merge_final` 中 `a` 和 `b` 會有序的排列在 `head` 之後。
此處也可解釋為何在 `merge` 在過程中 `a` 和 `b` 明明是雙向鍊結串列的型態 `list_head` 結構中卻有 `NULL` ，因為以下程式碼第 11 行將 `head->prev` 這個節點的 `next` 指標指向 `NULL` ，也就是原本指向 `head` 的 `head->prev->next` 指標，現在指向 `NULL` ( 這跟直接將 `head` 設置為 `NULL` 還是差別的！所以 `head` 依然存在並未變成 `NULL` )，所以才可以用跟合併單向鍊結串列一樣的判斷條件是迭代直至 `NULL`
```cpp=
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
...
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
}
```
看完[第 55 到](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L55) 到 [第 74 行](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L74) 的程式碼可以知道 [`merge_final`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L49) 和 [`merge`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L13) 作法大致相同，也就是會比較 `a` 和 `b` 這兩個雙向鍊結串列並且做合併，但是 `merge_final` 有調整每個節點的 `prev` 指標
```cpp
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
```
若是兩個鍊結串列不是平衡的，代表只有將其中一個鍊結串列走完並排列到 `head` 後面，需要繼續處理另一個鍊結串列，以下程式碼即是處理此情況
```cpp
/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
```
### `unlikely` 、 `likely`
>參考 [`likely() and unlikely()`](https://kernelnewbies.org/FAQ/LikelyUnlikely)
定義於 [linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) ，使用到 GCC 內建函式 [`__builtin_expect (long exp, long c)`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect) 如下
```cpp
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
關於 [`__builtin_expect(long exp, long c)` ](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect)的描述如下，此內建函數會提供編譯器分支預測的資訊，此處 [分支 branch](https://en.wikipedia.org/wiki/Branch_(computer_science)) 指程式中的能夠改變執行指令順序的如 `if-else` 和 `switch` 的條件表達式，這種功能可以避免指令跳轉從而優化程式執行過程
>You may use `__builtin_expect` to provide the compiler with branch prediction information...
其運作方式如字面上 `expect` 的含意，編譯器會預期 `exp` 的數值結果是 `c`，回傳值會是 `exp` 的運算結果
>The return value is the value of `exp`, which should be an integral expression. The semantics of the built-in are that it is expected that `exp == c`.
嘗試以下程式碼印出 `__builtin_expect` 的值，就是 `exp` 本身，此函數並不會影響 `exp` 本身，
```cpp
#include<stdio.h>
int main(){
int a = 10;
printf("%ld\n", __builtin_expect(a, 1)); // 10
printf("%ld\n", __builtin_expect(a==10, 0)); // 1
}
```
所以，`__builtin_expect(!!(x), 1)` 代表預期布林值 `!!(x)` 是對的，即希望執行 `likely` 這個分支；反之 `__builtin_expect(!!(x), 0)` 則代表預期布林值 `!!(x)` 是錯的，即不希望執行 `unlikely` 這個分支。透過預期 `exp` 發生的機率高低讓編譯器可以提早預測是否按照順序執行程式碼或是需要執行會降低效能的跳轉指令。
### `list_sort`
此處一樣有限制第 2 和 3 個參數須不為空的指標
```c
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
```
其參數定義如下，`head` 即 `list_sort` 要進行排序的雙向鍊結串列， `cmp` 則為的用於比較的函數
>@priv: private data, opaque to list_sort(), passed to @cmp
>@head: the list to sort
>@cmp: the elements comparison function
參考 [RinHizakura](https://hackmd.io/@RinHizakura/HkEuhNwGO#list_sort) 中解釋 [[RESEND PATCH v2 5/5] lib/list_sort: Optimize number of calls to comparison function](https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1957556.html)
開頭解釋由於 [`CONFIG_RETPOLINE`](https://www.kernelconfig.io/CONFIG_RETPOLINE?q=CONFIG_RETPOLINE&kernelversion=6.13.7&arch=x86) 降低了 呼叫間接函數 的表現，所以應該要減少使用間接函數如用來比較的 `cmp()` 函數，這也就是為什麼 `list_sort` 的合併排列中兩個序列長度需要以 2:1 的比例進行，因為此方式可以減少比較的次數，也就減少了調用 `cmp()` 而降低了系統的性能情況發生。
>CONFIG_RETPOLINE has severely degraded indirect function call performance, so it's worth putting some effort into reducing the number of times cmp() is called.
這段程式碼改變了以前是用 Bottom-up mergesort 的方式(以下為前版本描述)，可以參考 patch 中提供的文獻：[Bottom-up mergesort -- A detailed analysis](https://www.researchgate.net/publication/225952172_Bottom-up_mergesort_-_A_detailed_analysis)，比較特別的是這篇論文是一個經濟系和數學系的專家寫的，他們推導出可以表達 bottom-up mergesort 過程中做比較次數的表示式，並與 top-down 進行分析，並且得出結論雖然 top-down mergesort 的複雜度可能更低，但是它伴隨著需要先知道排列個數的限制，我想這也是為什麼以前是用 bottom-up 現在優化也不選擇 top-down 的原因
```
- * This function implements a bottom-up merge sort, which has O(nlog(n))
- * complexity. We use depth-first order to take advantage of cacheing.
- * (E.g. when we get to the fourth element, we immediately merge the
- * first two 2-element lists.)
```
且合併排列的比例盡可能要是 2:1
- 兩個鍊結串列都是 $2^k$ ，所以合併後就是 $2^{k+1}$
- 後續至少還有 $2^k$ 個元素
- 所以，合併過程中要同時處理的元素總數就是
$$2^{k+1} + 2^k = 2 \cdot 2^k + 2^k = 3\cdot2^k $$
```
+ * This mergesort is as eager as possible while always performing at least
+ * 2:1 balanced merges. Given two pending sublists of size 2^k, they are
+ * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
```
>[cache thrashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science)) 快取抖動：重複存取不在快取中的資料，導致快取不斷被替換，造成性能下降。
這邊有解釋到，因為這樣可以防止 cache thrashing，由於 CPU 的 [cache 快取](https://hackmd.io/@sysprog/it-vocabulary#%E8%A9%9E%E5%BD%99%E9%87%8B%E7%BE%A9) 存取速度由快到慢分別為 L1, L2, L3，所以如果 CPU 要存取資料會最先到 L1，這 $3\cdot2^k$ 個資料剛好可以都在 L1 就不會造成 cache thrashing
> :bulb: 可以透過 `lscpu` 知道自己電腦的 L1 大小
```
+ * Thus, it will avoid cache thrashing as long as 3*2^k elements can
+ * fit into the cache. Not quite as good as a fully-eager bottom-up
+ * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
+ * the common case that everything fits into L1.
```
我們需要計算兩個鍊結串列的長度並且檢查是否為 2 的次方，而用來計算的 `count` 就是控制是否合併的因素，當兩個鍊結串列長度為 $2^k$ 就合併，也就是計算 `pending` 的長度，以下所說的："在 `k` 個位置設為1後`k` 以前的位置就都變成0" 就是指 `count` 變成 $2^k$ 的時候二進位的呈現
```
+ * The merging is controlled by "count", the number of elements in the
+ * pending lists. This is beautiully simple code, but rather subtle.
+ *
+ * Each time we increment "count", we set one bit (bit k) and clear
+ * bits k-1 .. 0. Each time this happens (except the very first time
+ * for each bit, when count increments to 2^k), we merge two lists of
+ * size 2^k into one list of size 2^(k+1).
```
以下是計算方式的說明，說明有幾個 $2^k$ 長度的鍊結串列並且何時合併
這邊用實際數字來模擬這個過程，為了方便表示這裡先用單向鍊結串列：
:::spoiler
1. 初始狀態 $\to$ `count` = 0: `000`
2. 插入第 1 個元素 $\to$ `count` = 1: `001`
有一個長度為 1 的鍊結串列
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n1 [label="{<val>12 |<ref>}"]
none[label="", shape=none]
n1:ref:c -> none[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
}
```
3. 插入第 2 個元素 $\to$ `count` = 2: `010`
- 有兩個長度為 1 的鍊結串列
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n1[label="{<val>12 |<ref>}"]
n2[label="{<val>5|<ref>}"]
none1[label="", shape=none]
none2[label="", shape=none]
n1:ref:c -> none1[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n2:ref:c -> none2[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
}
```
4. 插入第 3 個元素 $\to$ `count` = 3: `011`
合併這兩個長度為 1 的鍊結串列為一個長度為 2 的鍊結串列、有一個長度為 1 的鍊結串列
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n1[label="{<val>12 |<ref>}"]
n2[label="{<val>5|<ref>}"]
n3[label="{<val>7|<ref>}"]
none1[label="", shape=none]
none2[label="",shape=none]
n1:ref:c -> none1[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n2:ref:c -> n1[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n3:ref:c -> none2[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
}
```
5. 插入第 4 個元素 $\to$ `count` = 4: `100`
- 兩個長度為 1 的鍊結串列、一個長度為 2 的鍊結串列
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n1[label="{<val>12 |<ref>}"]
n2[label="{<val>5|<ref>}"]
n3[label="{<val>7|<ref>}"]
n4[label="{<val>13|<ref>}"]
none1[label="", shape=none]
none2[label="",shape=none]
none3[label="", shape=none]
n1:ref:c -> none1[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n2:ref:c -> n1[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n3:ref:c -> none2[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n4:ref:c -> none3[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
}
```
- 兩個長度為 1 的鍊結串列合併成一個長度為 2 的鍊結串列、一個長度為 2 的鍊結串列
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n1[label="{<val>12 |<ref>}"]
n2[label="{<val>5|<ref>}"]
n3[label="{<val>7|<ref>}"]
n4[label="{<val>13|<ref>}"]
none1[label="", shape=none]
none2[label="",shape=none]
n1:ref:c -> none1[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n2:ref:c -> n1[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n3:ref:c -> n4[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n4:ref:c -> none2[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
}
```
- 合併兩個長度為 2 的鍊結串列為一個長度為 4 的鍊結串列
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
n1[label="{<val>12 |<ref>}"]
n2[label="{<val>5|<ref>}"]
n3[label="{<val>7|<ref>}"]
n4[label="{<val>13|<ref>}"]
none[label="", shape=none]
n1:ref:c -> n4[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n2:ref:c -> n3[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n3:ref:c -> n1[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
n4:ref:c -> none[arrowtail=dot, dir=both, tailclip=false, arrowsize=1];
}
```
6. 重複 2. ～ 5. 流程
:::
```
+ * The number of pending lists of size 2^k is determined by the
+ * state of bit k of "count" plus two extra pieces of information:
+ * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
+ * - Whether the higher-order bits are zero or non-zero (i.e.
+ * is count >= 2^(k+1)).
+ * There are six states we distinguish. "x" represents some arbitrary
+ * bits, and "y" represents some arbitrary non-zero bits:
+ * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
+ * 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
+ * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
+ * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
+ * (merge and loop back to state 2)
```
而這個過程合併用的函數就是定義在上面的 [`merge`](#merge)，完成所有節點的排序後，最後在使用 [`merge_final`](#merge_final) 調整雙向鍊結串列的 `prev` 指標，至此，就是 [`list_sort`](#list_sort) 的註解解釋
### list_sort 排序過程
- 先將雙向鍊結串列頭尾斷開，即連接到 `head` 的 `prev` 指標指向的節點的 `next` 指標指向 `NULL` ，所以 `head` 的 `prev` 並未斷開
- 創建待排序的指標 `pending` ，初始化這個指標指向 `NULL`
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""];
pending -> null2;
head:next -> n4:val;
n4:prev -> head:val;
n4:next -> n1:val;
n1:prev -> n4:val;
n1:next -> n5:val;
n5:prev -> n1:val;
n5:next -> n2:val;
n2:prev -> n5:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> null1[color="red"];
head:prev -> n3:val;
list -> n4:val;
}
```
以下就是作者那一大串註解所說明的排序過程，
```c
do {
..
} while (list);
```
- `tail` 在這裡的作用是在找 待排序的鍊結串列 `pending` 上的最後一個節點，`pending` 一開始是空的，所以 `tail` 指向 `pending`
```cpp
size_t bits;
struct list_head **tail = &pending;
```
```graphviz
digraph pointer2poitner{
rankdir=LR;
node[shape=none]
tail->pending;
pending->NULL;
}
```
- `count` 初始化是 0 ，所以一開始不會執行這個迴圈
```cpp
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
- 此處使用到的 [`likely`](#unlikely-、-likely)，即有很大可能 `bits` 是大於 0 的數字，但是如果有經過上面的迴圈 `bits` 還大於 0 的可能有以下兩種
- `bits` 本身就是 $2^k$
2 (0010) 、4 (0100) 、8 (1000) ... 等數都不會經過上面迴圈
- `bits` 是 $(2^k, 2^{k+1}-1)$ 區間的整數
5 (0101) 、6 (0110) 、9 (1001) 、10 (1010) 、11 (1011) 、12 (1100) 、13 (1101) 、14 (1110) ... 等數中，偶數不會經過上面迴圈，奇數則是經過上面迴圈後依然大於 0
```cpp
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
```
- `count` = 0 $\to$ `count` = 1
將雙向鍊結串列上的節點移至 `pending` 上
```cpp
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
第一次執行這段程式碼如以下，此時 `pending` 上就會有一個節點 `12` ，且其 `prev` 和 `next` 都會被斷開，如同從此雙向鍊結上移至另一個等待的鍊結串列上，此時也因應 `pending` 上增加一個節點，`count` = 1
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""];
tail->pending;
pending -> n4:val;
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> n4:val;
n1:next -> n5:val;
n5:prev -> n1:val;
n5:next -> n2:val;
n2:prev -> n5:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> null1
head:prev -> n3:val;
list -> n1:val;
}
```
- `count` = 1 $\to$ `count` = 2：不 merge
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""];
tail->n4:prev[color=red];
pending -> n1:val[color=red];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> n4:val;
n1:next -> null4;
n5:prev -> n1:val;
n5:next -> n2:val;
n2:prev -> n5:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> null1
head:prev -> n3:val;
list -> n5:val[color=red];
}
```
- `count` = 2 $\to$ `count` = 3 : 合併
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""];
tail->pending[color=red];
pending -> n1:val;
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> n4:val;
n1:next -> null4;
n5:prev -> n1:val;
n5:next -> n2:val;
n2:prev -> n5:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> null1
head:prev -> n3:val;
list -> n5:val;
}
```
進入 `if likely(bits)` 的區塊準備進行合併，這裡使用的是只會調整每個節點的 `next` 指標的 [`merge` 函數](#merge)
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
list[label="list", shape=none];
a[label="a", shape=none];
b[label="b", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
a -> n1:val[color=red style="dashed"];
b -> n4:val[color=red style="dashed"];
tail->pending[color=red];
pending -> n1:val;
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> n4:val;
n1:next -> null4;
n5:prev -> n1:val;
n5:next -> n2:val;
n2:prev -> n5:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> null1
head:prev -> n3:val;
list -> n5:val;
}
```
此時節點 `2` 的 `next` 指標就會指向節點 `12` (此處假設是升冪排序)，且節點 `2` 的 `prev` 也會被清空指向 `NULL`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
list[label="list", shape=none];
a[label="a", shape=none];
b[label="b", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n1 -> n4 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
a -> n1:val[color=red];
b -> n4:val[color=red];
tail->pending;
pending -> n1:val;
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val[color=red];
n5:prev -> n1:val;
n5:next -> n2:val;
n2:prev -> n5:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> null1
head:prev -> n3:val;
list -> n5:val;
}
```
最後將下一個的節點增加至 `pending`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
tail->pending;
pending -> n5:val[color="red"];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5[color="red"];
n2:prev -> n5:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> null1
head:prev -> n3:val;
list -> n2:val[color="red"];
}
```
- `count` = 3 $\to$ `count` = 4 : 不合併
找目前在 `pending` 上的最後一個節點，並將 `tail` 指向該指標，因為 `next` 指標是有順序的指向下一個節點，如果要找到最後一個節點就是要用 `prev` 去找 `tail`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
tail->n1:prev[color="red"];
pending -> n5:val;
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n5:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> null1
head:prev -> n3:val;
list -> n2:val;
}
```
將下一個節點新增至 `pending`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
null6[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
tail->n1:prev;
pending -> n2:val[color="red"];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n5:val;
n2:next -> null6[color="red"];
n3:prev -> n2:val;
n3:next -> null1;
head:prev -> n3:val;
list -> n3:val[color="red"];
}
```
- `count` = 4 $\to$ `count` = 5: 合併
將 `pending` 上的節點進行合併
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
null6[label="NULL", shape=none];
list[label="list", shape=none];
a[label="a", shape=none];
b[label="b", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
a -> n2:val[color="red", style="dashed"];
b -> n5:val[color="red", style="dashed"];
tail->pending[color="red"];
pending -> n2:val;
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n5:val;
n2:next -> null6;
n3:prev -> n2:val;
n3:next -> null1;
head:prev -> n3:val;
list -> n3:val;
}
```
經過合併後，節點 `5` 的 `next` 指標會指向節點 `13`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
// null6[label="NULL", shape=none];
list[label="list", shape=none];
a[label="a", shape=none];
b[label="b", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
a -> n2:val[color="red"];
b -> n5:val[color="red"];
tail->pending;
pending -> n2:val;
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n1:val[color="red"];
n2:next -> n5:val[color="red"];
n3:prev -> n2:val;
n3:next -> null1;
head:prev -> n3:val;
list -> n3:val;
}
```
將下一個節點移至 `pending`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
tail[label="tail", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
// null6[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
tail->pending;
pending -> n3:val[color="red"];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n1:val;
n2:next -> n5:val;
n3:prev -> n2:val;
n3:next -> null1;
head:prev -> n3:val;
list -> null1[color="red"];
}
```
至此，由於 `list` 指向 `NULL` ，所以跳出迴圈
由上圖可知，雙向鍊結串列尚未排序完成，只有每格兩個節點用 `next` 去看順序是正確的，`prev` 目前也尚未完成，以下程式碼就是
```clike
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
- 將在 `pending` 的節點進行排序，
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
// null6[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
pending -> n2:val[color="red"];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n1:val;
n2:next -> n5:val;
n3:prev -> n2:val;
n3:next -> null1;
head:prev -> n3:val;
list -> n3:val[color="red", style="dashed"];
}
```
- 進入 `for` 迴圈進行排序
先將下一個節點存放至 `next`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
null1[label="NULL", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
// null6[label="NULL", shape=none];
list[label="list", shape=none];
next[label="next", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
next -> n1:val[color="red"];
pending -> n2:val[color="red", style="dashed"];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n1:val;
n2:next -> n5:val;
n3:prev -> n2:val;
n3:next -> null1;
head:prev -> n3:val;
list -> n3:val[color="red", style="dashed"];
}
```
經過 [`merge`](#merge)，完成所有節點的 `next` 指標排序： `5` $\to$ `7` $\to$ `13`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
// null1[label="NULL", shape=none];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
// null6[label="NULL", shape=none];
list[label="list", shape=none];
next[label="next", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
next -> n1:val;
pending -> n1:val[color="red"];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n1:val;
n2:next -> n3:val[color="red"];
n3:prev -> n2:val;
n3:next -> n5:val[color="red"];
head:prev -> n3:val;
list -> n2:val[color="red"];
}
```
先將下一個節點存放至 `next`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
pending[shape=none];
null2[label="NULL", shape=none];
null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
// null6[label="NULL", shape=none];
list[label="list", shape=none];
next[label="next", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n4 -> n1 -> n5 -> n2 -> n3;
// Visible connections
edge [style=""]
next -> null4[color="red"];
pending -> n1:val[color="red", style="dashed"];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> null3;
n1:prev -> null4;
n1:next -> n4:val;
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n1:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> n5:val;
head:prev -> n3:val;
list -> n2:val[color="red", style="dashed"];
}
```
經過 [`merge`](#merge)，完成所有節點的 `next` 指標排序： `2` $\to$ `5` $\to$ `7` $\to$ `12` $\to$ `13`
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
pending[shape=none];
null2[label="NULL", shape=none];
// null3[label="NULL", shape=none];
null4[label="NULL", shape=none];
null5[label="NULL", shape=none];
// null6[label="NULL", shape=none];
list[label="list", shape=none];
next[label="next", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n1 -> n2 -> n3 -> n4 -> n5;
// Visible connections
edge [style=""]
next -> null4;
pending -> null4[color="red"];
head:next -> n4:val;
n4:prev -> null2;
n4:next -> n5:val[color="red"];
n1:prev -> null4;
n1:next -> n2:val[color="red"];
n5:prev -> n1:val;
n5:next -> null5;
n2:prev -> n1:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> n4:val[color="red"];
head:prev -> n3:val;
list -> n1:val[color="red"];
}
```
最後使用 [`merge_final` 函數](#merge_final)，將 `prev` 指標更新完成
```cpp
merge_final(priv, cmp, head, pending, list);
```
```graphviz
digraph ll{
rankdir=LR;
node[shape=record];
head[label="<val>head|{<prev>prev|<next>next}"];
n4[label="<val>12|{<prev>prev|<next>next}"];
n1[label="<val>2|{<prev>prev|<next>next}"];
n5[label="<val>13|{<prev>prev|<next>next}"];
n2[label="<val>5|{<prev>prev|<next>next}"];
n3[label="<val>7|{<prev>prev|<next>next}"];
pending[shape=none];
null5[label="NULL", shape=none];
null4[label="NULL", shape=none];
list[label="list", shape=none];
// Establish node order with invisible edges
edge [style=invis];
head -> n1 -> n2 -> n3 -> n4 -> n5;
// Visible connections
edge [style=""]
pending -> null4;
head:next -> n1:val[color="red"];
n4:prev -> n3:val[color="red"];
n4:next -> n5:val;
n1:prev -> head:val[color="red"];
n1:next -> n2:val;
n5:prev -> n4:val[color="red"];
n5:next -> null5;
n2:prev -> n1:val;
n2:next -> n3:val;
n3:prev -> n2:val;
n3:next -> n4:val;
head:prev -> n5:val[color="red"];
list -> n1:val;
}
```
## 實作 shuffle 命令
### Fisher–Yates shuffle
此演算法是一個時間複雜度為 O(n) 和空間複雜度為 O(1) 的洗牌演算法，步驟如下：
假設有一個 `n` 長度的陣列 `array`
1. 迭代 0 到 n 之間，迭代過程的變數 `i`
2. 第 `i` 次迭代中
- 在 $[0,i]$ 之間隨機找一個索引 `j`
- 將 `array[i]` 和 `array[j]` 交換位置
```python
for i from 0 to n − 1 do
j ← random integer such that 0 ≤ j ≤ i
a[i] ← source[i]
a[i] ← a[j]
a[j] ← source[i]
```
### `q_shuffle`
實做 Fisher-Yates Shuffle 在雙向鍊結串列中
## 閱讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
### Abstract
開發了一個可以檢測差不多 300 行的 C 語言程式的執行時間是否為常數時間的工具: `dudect`
### Introduction
- 動機
為了抵抗 Timing attack 的相關資安攻擊，雖然聽起來是很瑣碎的事情，但是如果發生 timing leaks 就會造成很嚴重的結果
>Assessing whether an implementation runs in constant time is not a trivial task. Even implementations that were supposed to be constant-time turned out not to be so [GBY16 ], [ Cry16]— reinforcing the argument that timing leaks may not be easy to detect, but can have serious consequences.
- 貢獻
即使以前也有可以評估記憶體資源或時間的工具，但是這些工具都需要去模擬硬體，這其實是滿困難的，而這篇論文的作者開發的 `dudect` 並不需要，只要跑在他們的平台上即可評估時間複雜度，而且不是靜態的分析?是用統計分析程式執行時間?
>Our tool does not rely on static analysis but on statistical analysis of execution timing measurements on the target platform. In this way, we circumvent the problem of modeling the underlying hardware.
### Approach
1. 第一步: 測執行時間
- fix-vs-random 測試
測兩組不同資料類別的執行時間來做洩漏檢測，一組是固定輸入，然後另一組是隨機輸入，這樣就可以抓到比較多潛在的時序洩漏
- 週期計數器
用硬體的計數器去測執行時間
- 可以減少環境的影響
因為是隨機的輸入類別，而且還是在測量前就選好資料類別的輸入，進入測量後就不會受到環境影響
2. 第二步: 後處理
- 剪裁
把無關類別和不是百分位數的測量值丟掉，只處理常態分布的時序，減少異常質對測量的影響
- 高階處理
可用內積模仿 DPA 攻擊
3. 第三步： 統計測試
- 排除 null hyprothesis:
- t-test: 因為 cropping 是非線性的轉換，可以使用 Welch's t-test 來測試 first-order timing information leakage
- non-parametric test: fewer assumptions
### Result
- 將由 300 行 C 程式碼開發的工具 `deduct` 開放在 [github](https://eprint.iacr.org/2016/1123.pdf) 上
- 採用 Welch's t 檢驗，結合 Welford 方差計算方法可以提高數值穩定性
- `dudect` 在 MacBook、Intel Xeon 和 ARM7TDMI 上都有效，具有其通用性
## 開發過程遇到的問題
1. commit message 遇到的問題: 說我用到 非英文單字，後來我檢查，因為我在 body 中寫到 "Use INIT_LIST_HEAD" macro 的名字導致無法儲存，改掉就好，
- 不通過的詞：deallocation
```bash
Read https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md#git-commit-style carefully.
Proceed with commit? [e/n/?] e
Implement q_new with circular list structure [line 1]
- Avoid using non-American English words
```
2. **Failed to retrieve upstream commit hash from GitHub.**
解決：重開機 或是 等一陣子在試，[3/9直播](https://www.youtube.com/watch?v=b7AkUgz_xvg) 有說道不要急著做 `make test` ，先思考在執行
```bash
lun@lun-OMEN:~/linux2025/hw1/lab0-c$ make test
Progress: [####################--------------------] 50%
[!] Failed to retrieve upstream commit hash from GitHub.
make: *** [Makefile:60: test] Error 1
```
## 閱讀資料
### [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHyBPr9WGl)
1. 釐清 pointer
引用 [C語言: 超好懂的指標，初學者請進～](https://kopu.chat/c%E8%AA%9E%E8%A8%80-%E8%B6%85%E5%A5%BD%E6%87%82%E7%9A%84%E6%8C%87%E6%A8%99%EF%BC%8C%E5%88%9D%E5%AD%B8%E8%80%85%E8%AB%8B%E9%80%B2%EF%BD%9E/) 中的描述可以很好理解
>指標 (Pointer) 就是某變數的位址。而這邊的指標變數 (Pointer Variable)，則是用來存放指標的變數。
2. array subscripting 在編譯時期只確認以下兩件事:
- 得知 size
- 取得陣列第 0 個 (即最初的一項) 元素的指標
前兩者以外的操作，都透過 pointer
array subscripting => syntax sugar
C has no real "array"!
3. 關於為什麼 `&b[0]` 是 pointer to struct? `&` 不是 address of 用來取位置的嗎？那為什麼不是一個數值？
因為我們前面有了解過指標變數中存的值就是記憶體位置，在這裡我的理解是：把 `b[0]` 看成一個變數，`&b[0]` 這個數值就是記憶體位置，那什麼變數會存放記憶體位置呢？就是指標變數了，所以才會是 pointer to struct
```cpp
(gdb) whatis &b[0]
type = struct {...} *
```
4. 遇到 `gdb` 無法存取記憶體
```bash
(gdb) p &b
$1 = (struct {...} (*)[17]) 0x4620 <b>
(gdb) x/4 b
0x4620 <b>: 0 0 0 0
(gdb) p (&b[0])->v = {1, 2, 3}
Cannot access memory at address 0x4620
```
後來找到原因，因為我沒有把程式跑起來，但是跑起來後，因為 `main()` 中沒有程式碼，整個程式會直接結束，還來不急跟變數做互動它就結束的概念，所以要在 `main()` 這個地方做一個 break point，讓它停在那裡我們就可以對 `b[0]` 做修改記憶體了
```bash
(gdb) break main
Breakpoint 1 at 0x555555555136: file s.c, line 5.
(gdb) run
Starting program: /home/lun/linux2025/hw1/s
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Breakpoint 1, main () at s.c:5
5 int main(){}
(gdb) p (&b[0])->v = {1, 2, 3}
$1 = {1, 2, 3}
```
5. 關於 [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHyBPr9WGl#Pointers-vs-Arrays) 的這個部份，我和影片中實做的結果不一樣
```bash
(gdb) p &b
$31 = (struct {...} (*)[17]) 0x555555558060 <b>
(gdb) p &b+1
$32 = (struct {...} (*)[17]) 0x555555558280 <calendar>
(gdb) p &a[0]
$33 = (int *) 0x555555558040 <a>
(gdb) p &a[3]
$34 = (int *) 0x55555555804c
```
其中 `&b+1` 不是 `a[0]` 或是 `a[3]` 的位置，而是 `calendar` 的位置
```bash
(gdb) p &b[16]
$42 = (struct {...} *) 0x555555558260 <b+512>
(gdb) p &calendar
$43 = (int (*)[12][31]) 0x555555558280 <calendar>
```
在查看 calendar 位置的實做過程中，發現 `memcpy` 不能直接使用，要先強至轉型才能看到值
```bash
$3 = (double *) 0x555555558280 <calendar>
(gdb) p memcpy(calendar, b, sizeof b[0])
'memcpy' has unknown return type; cast the call to its declared return type
(gdb) p (double*)memcpy(calendar, b, sizeof b[0])
$3 = (double *) 0x555555558280 <calendar>
```
### [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-prog/%2Fs%2FSkE33UTHf)
1. pointer to pointer 的實做理解
用 [leetcode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/) 來實做，並用 graphviz 畫每個步驟
- 每一個節點都是一個 `ListNode` 物件
- 最一開始 `indirect` 指向 `head`，`head` 指向第一個節點的位置，`cur` 指向 `indirect` 指向的 `head` 指向的位置（指標的指標）
```graphviz
digraph linked_list {
rankdir=LR;
node [shape=record];
head [label="head", style=filled, fillcolor="#F8CACA"];
indirect [label="indirect", style=filled, fillcolor="#D8E8D8"];
cur [label="cur", style=filled, fillcolor="#D8E8FF"];
node1 [label="{1 |<next> next }", shape=record];
node2 [label="{2 | <next> next }", shape=record];
node3a [label="{3| <next> next }", shape=record];
node3b [label="{3| <next> next }", shape=record];
node4 [label="{4 | <next> next }", shape=record];
node5 [label="{5 | <next> next }", shape=record];
null_node [label="NULL", shape=plaintext];
head -> node1;
indirect -> head;
cur -> node1;
node1:next -> node2;
node2:next -> node3a;
node3a:next -> node3b;
node3b:next -> node4;
node4:next -> node5;
node5:next -> null_node;
}
```
- 如果 `cur` 的值與下一個節點值不相同
- 改變 `indirect` 中儲存的記憶體位置，改到 指向位置的指標的 `next`(也是一個指標)的位置
```graphviz
digraph LinkedList {
rankdir=LR;
// Node styling
node [shape=record, height=.1, fontname="Arial"];
edge [fontname="Arial"];
// Define nodes with their data and next pointer port
head [shape=box, fillcolor="#FFCACA", style=filled, label="head"];
indirect [shape=box, fillcolor="#CAFFCA", style=filled, label="indirect"];
cur [shape=box, label="cur"];
// Define the linked list nodes
node1 [label="<n>1 | <next>next"];
node2 [label="<n>2 | <next>next "];
node3a [label="<n>3 | <next>next "];
node3b [label="<n>3 | <next>next "];
node4a [label="<n>4 | <next>next "];
node4b [label="<n>4 | <next>next "];
node5 [label="<n>5 |<next> next"];
null [shape=plaintext, label="NULL"];
indirect_next [ label="\(*indirect\)\-\>next", fontcolor=purple];
indirect_next_loc [label="\&\(*indirect\)\-\>next", fontcolor=purple];
// Create the main linked list connection
head -> node1:n;
node1:next -> node2:n;
node2:next -> node3a:n;
node3a:next -> node3b:n;
node3b:next -> node4a:n;
node4a:next -> node4b:n;
node4b:next -> node5:n;
node5:next -> null:n;
// Connect cur pointer to node1
cur -> node1:n;
// Connect indirect to node1 with red label
indirect -> node1:n [color=red, label="*indirect", fontcolor=red];
indirect -> head [style=dashed];
indirect_next -> node2:n[style=dashed, color=purple];
indirect_next_loc -> node1:next[style=dashed, color=purple];
}
```
- 所以，`indirect` 不是直接指向 `2` !! 而是指向指向 `2` 的 `1->next` 指標
```graphviz
digraph LinkedList {
// 基本設置
rankdir=LR;
node [shape=record, height=.1, fontname="Arial"];
edge [fontname="Arial"];
// 定義頭指針和其他指針
head [shape=box, fillcolor="#FFCACA", style=filled, label="head"];
cur [shape=box, fillcolor="#E0E0FF", style=filled, label="cur"];
indirect [shape=box, fillcolor="#E0FFEA", style=filled, label="indirect"];
// 定義鏈表節點
node1 [label="<f0> 1 | <f1> next"];
node2 [label="<f0> 2 | <f1> next"];
node3a [label="<f0> 3 | <f1> next"];
node3b [label="<f0> 3 | <f1> next"];
node4a [label="<f0> 4 | <f1> next"];
node4b [label="<f0> 4 | <f1> next"];
node5 [label="<f0> 5 | <f1> next"];
null [shape=plaintext, label="NULL"];
// 連接鏈表
head -> node1:f0;
node1:f1 -> node2:f0;
node2:f1 -> node3a:f0;
node3a:f1 -> node3b:f0;
node3b:f1 -> node4a:f0;
node4a:f1 -> node4b:f0;
node4b:f1 -> node5:f0;
node5:f1 -> null;
// 連接 cur 指針到第一個節點
cur -> node1:f0;
// indirect 指向 next 指針
indirect -> node1:f1;
// 調整節點位置
{rank=same; head}
{rank=same; cur}
{rank=same; indirect}
}
```
- 如果 `cur`的值與下一個節點值相同
- 迭代 `cur` 一直到不相同
```graphviz
digraph LinkedList {
// 基本設置
rankdir=LR;
node [shape=record, height=.1, fontname="Arial"];
edge [fontname="Arial"];
// 定義頭指針和其他指針
head [shape=box, fillcolor="#FFCACA", style=filled, label="head"];
cur1 [shape=box, style="filled,dashed", fillcolor="#E0E0FF", label="cur"];
cur2 [shape=box, style="filled,dashed", fillcolor="#E0E0FF", label="cur"];
cur3 [shape=box, style="filled", fillcolor="#E0E0FF", label="cur"];
indirect [shape=box, fillcolor="#E0FFEA", style=filled, label="indirect"];
// 定義鏈表節點
node1 [label="<f0> 1 | <f1> next"];
node2 [label="<f0> 2 | <f1> next"];
node3a [label="<f0> 3 | <f1> next"];
node3b [label="<f0> 3 | <f1> next"];
node4a [label="<f0> 4 | <f1> next"];
node4b [label="<f0> 4 | <f1> next"];
node5 [label="<f0> 5 | <f1> next"];
null [shape=plaintext, label="NULL"];
// 連接鏈表
head -> node1:f0;
node1:f1 -> node2:f0;
node2:f1 -> node3a:f0;
node3a:f1 -> node3b:f0;
node3b:f1 -> node4a:f0;
node4a:f1 -> node4b:f0;
node4b:f1 -> node5:f0;
node5:f1 -> null;
// 連接 cur 指針到不同節點
cur1 -> node3a:f0;
cur2 -> node3b:f0;
cur3 -> node4a:f0;
// indirect 指向 node2 的 next 指針
indirect -> node2:f1;
// 調整節點位置
{rank=same; head}
{rank=same; cur1, cur2, cur3}
{rank=same; indirect}
}
```
- 然後把 `indirect` 指到的 `next` 指標，指向 `cur` 指向的節點 4
```graphviz
digraph LinkedList {
// 基本設置
rankdir=LR;
node [shape=record, height=.1, fontname="Arial"];
edge [fontname="Arial"];
// 定義頭指針和其他指針
head [shape=box, fillcolor="#FFCACA", style=filled, label="head"];
cur [shape=box, style="filled", fillcolor="#E0E0FF", label="cur"];
indirect [shape=box, fillcolor="#E0FFEA", style=filled, label="indirect"];
// 定義鏈表節點
node1 [label="<f0> 1 | <f1> next"];
node2 [label="<f0> 2 | <f1> next"];
node3a [label="<f0> 3 | <f1> next"];
node3b [label="<f0> 3 | <f1> next"];
node4a [label="<f0> 4 | <f1> next"];
node4b [label="<f0> 4 | <f1> next"];
node5 [label="<f0> 5 | <f1> next"];
null [shape=plaintext, label="NULL"];
// 連接鏈表
head -> node1:f0;
node1:f1 -> node2:f0;
node3a:f1 -> node3b:f0;
node3b:f1 -> node4a:f0;
node4a:f1 -> node4b:f0;
node4b:f1 -> node5:f0;
node5:f1 -> null;
// 連接 cur 指針到第一個值為4的節點
cur -> node4a:f0;
// indirect 指向 node2 的 next 指針
indirect -> node2:f1;
// 顯示 *indirect=cur 的關係
node2:f1 -> node4a:f0[color=red, style=bold, label="*indirect=cur", fontcolor=red];
// 調整節點位置
{rank=same; head}
{rank=same; cur}
{rank=same; indirect}
}
```
- [重複以上步驟](https://hackmd.io/_uploads/rJPn4iZj1e.png)，直到 `indirect` 指向的指標指向的物件為 `NULL`
2. *-safe 就是不管任何條件 `*`，這個函式都可以執行
Sign in with Wallet
Connect another wallet