# 2023q1 Homework1 (lab0)
contributed by < [`Shiritai`](https://github.com/Shiritai) >
### Reviewed by `Urbaner`
* 考慮重新整理，理出一條主要的開發線，善用開關標籤以免迷失在過長的筆記。
:::info
以一個主要個開發線或者主題來敘述開發是很好的想法，未來我將嘗試這樣做。
不過 Hackmd 本身提供快速移動到某標題的功能 (table of content)，以快速閱覽任意長度且設置正常標題的筆記，故似乎沒有必要使用開關標籤。
我認為開關標籤的使用是省略可選的內容，比如本筆記內隱藏針對 VSCode 中使用註解格式的議題，這是因為此部分僅與使用 VSCode 的使用者有關，且並不直接與開發的邏輯有關。
> [name=Eroiko]
:::
* 有提到不需貼出整段程式碼，僅需數行即可。考慮精簡頁面，突顯重點。
:::info
ok
> [name=Eroiko]
:::
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
```
## queue 開發過程
### q_new
$O(1)$
建立新鏈結串列節點，僅在成功配置記憶體時初始化回傳值 `ret` 為首位節點，並回傳。若配置失敗，`ret == NULL`，正好符合函式要求。
```c=
struct list_head *q_new()
{
struct list_head *ret = malloc(sizeof(struct list_head));
if (ret) // if not null
INIT_LIST_HEAD(ret);
return ret;
}
```
### q_free
$O(n)$
:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)，變更下方用語。
:notes: jserv
> ok，本以為真的走訪全部可稱遍歷。
今後會多加注意名詞的使用。 [name=Eroiko]
:::
透過 `list_for_each_entry_safe` 巨集走訪所有元素節點，分別先釋放 `value` 成員再釋放元素節點本身。使用 `_safe` 版巨集走訪是因為一路上的節點會被釋放。最後不忘要釋放首位元素節點。
```c=
void q_free(struct list_head *l)
{
if (!l) // guard invalid condition
return;
element_t *cur, *nxt; // iterators
// this macro works with DS that contains
// a member of type "list_head"
list_for_each_entry_safe (cur, nxt, l, list) {
// cur->value must have value except queue head
// which won't be iterated
q_release_element(cur);
}
free(l); // free head
}
```
### q_element_alloc 輔助函式
$O(1 + \tt{memcpy(sizeof(element\_t)) + strdup(s)})$
:::info
Allocate 翻為配置。
> [name=Eroiko]
:::
由於 `q_insert_head` 和 `q_insert_tail` 的邏輯相似，皆需「配置新元素節點並複製給定字串值」，故將此邏輯獨立為本函式。我定義回傳值為指標，非 `NULL` 表成功，否則表 `element_t` 或 `element_t::value` 配置失敗。
```c=
/**
* Allocate and construct a new element
* @param s value to save as element
* @return non-null if success, null if any bad thing happens
*/
static element_t *q_element_alloc(const char *s)
{
// allocate a new element node
element_t *n_ele = malloc(sizeof(element_t));
if (!n_ele) // guard invalid condition
return NULL;
// copy value of s to element member
n_ele->value = strdup(s);
if (!n_ele->value) {
// allocation failed
free(n_ele);
return NULL;
}
return n_ele;
}
```
注意以下四點：
* 若 `n_ele` 配置成功但 `n_ele->value` 失敗，則回傳 `NULL` 前不忘歸還 `n_ele`。
* 宣告為 `static` 是為了縮小可見度 (<s>封閉性</s> ?)，~~原本名稱前面兩底線更進一步表達此函式的私有性~~。
:::success
已修改
> [name=Eroiko]
:::
* 要複製的字串參數實際上應該被限縮為常數，因為我們不需要修改之。
* 使用 [doxyden](https://zh.wikipedia.org/zh-tw/Doxygen) 文本註解格式，這是由於在 VSCode 中比起 [Linux Kernel-doc](https://docs.kernel.org/doc-guide/kernel-doc.html) 能辨識並給予清楚的提示。實際上，doxygen 也是當前大多數程式語言都使用的註解格式。
:::warning
`static` 是為了 [visibility](https://gcc.gnu.org/wiki/Visibility)，而非「封閉性」，後者是數學用語。
:notes: jserv
> 確實... [name=Eroiko]
:::
:::spoiler 舉例而言...
* 辛辛苦苦使用 Linux Kernel-doc 的註解不能即時得到回饋。
:::info
如果讀者您知道哪些 VSCode 擴充套件可以解析 Linux Kernel-doc 的，請務必告訴我。
:::
* 使用 doxygen 可以得到關鍵字的辨識與參數提示。
:::
### q_insert_head 和 q_insert_tail 的實作與重構
一開始使用最普通的實作。由於都有「配置新元素節點並複製給定字串值」，故將該邏輯獨立為 `q_element_alloc`。最後使用 `list_add_tail` 巨集幫助完成 push front/back 的邏輯。
```c=
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) // NULL queue
return false;
// allocate a new element node
element_t *n_ele = q_element_alloc(s);
if (!n_ele)
return false;
// insert to queue head
// i.e. head->next become &n_ele->list
list_add(&n_ele->list, head);
return true;
}
```
```c=
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) // NULL queue
return false;
// allocate a new element node
element_t *n_ele = q_element_alloc(s);
if (!n_ele)
return false;
// insert to queue tail
// i.e. head->prev become &n_ele->list
list_add_tail(&n_ele->list, head);
return true;
}
```
會發現這倆函式行為極其相似，僅差在函式名稱以及插入位置的不同。不妨使用前處理器的技巧，讓程式更好維護，如下。
:::success
注意到前處理的換行不能被 "//" 屏蔽，故使用 C 風格的註解。
> [name=Eroiko]
:::
```c=
#define gen_q_insert(fn_suffix, list_macro) \
bool q_insert_##fn_suffix(struct list_head *head, char *s) \
{ \
if (!head) /* NULL queue */ \
return false; \
/* allocate a new element node */ \
element_t *n_ele = q_element_alloc(s); \
if (!n_ele) \
return false; \
/* insert into queue */ \
list_macro(&n_ele->list, head); \
return true; \
}
```
如此，兩函式的實作變為簡單兩行。
```c=
/* Insert an element at head of queue */
gen_q_insert(head, list_add);
/* Insert an element at tail of queue */
gen_q_insert(tail, list_add_tail);
```
### q_remove_head 和 q_remove_tail 的實作與重構
首先處理邊界情況，接著取得串列的首位準備移除，當 `sp` 合法時複製欲移除節點之值，最後回傳。
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) // guard
return NULL;
// fetch last element
element_t *ret = list_first_entry(head, element_t, list);
list_del(&ret->list);
if (sp) {
// sp is valid
memcpy(sp, ret->value, bufsize);
sp[bufsize - 1] = '\0';
}
return ret;
}
```
```c=
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) // guard
return NULL;
// fetch last element
element_t *ret = list_last_entry(head, element_t, list);
list_del(&ret->list);
if (sp) {
// sp is valid
memcpy(sp, ret->value, bufsize);
sp[bufsize - 1] = '\0';
}
return ret;
}
```
與插入的情況相同，可以發現這倆函式行為極其相似，僅差在函式名稱以及插入位置的不同。不仿再次使用前處理器的技巧，讓程式更好維護，如下。
```c=
#define gen_q_remove(fn_suffix, list_macro) \
element_t *q_remove_##fn_suffix(struct list_head *head, char *sp, \
size_t bufsize) \
{ \
if (!head || list_empty(head)) /* guard */ \
return NULL; \
/* fetch first element */ \
element_t *ret = list_macro(head, element_t, list); \
list_del(&ret->list); \
if (sp) { \
/* sp is valid */ \
memcpy(sp, ret->value, bufsize); \
sp[bufsize - 1] = '\0'; \
} \
return ret; \
}
```
注意字串的複製我使用 `memcpy` 來加快效率，並在最後補上 `\0`。
於是兩刪除節點函式的實作變成:
```c=
/* Remove an element from head of queue */
gen_q_remove(head, list_first_entry);
/* Remove an element from tail of queue */
gen_q_remove(tail, list_last_entry);
```
減少多餘的程式碼與人工同步的成本。
:::warning
注意用語！在電腦科學和工程中，[冗餘](https://zh.wikipedia.org/wiki/%E5%86%97%E9%A4%98) (英語: redundancy) 是指系統為了提昇其可靠度，刻意組態重複的零件或是機能。顯然這裡不是 redundancy 的寓意，應該避免該詞彙的使用。
:notes: jserv
> ok [name=Eroiko]
:::
### q_size
$O(n)$
如 Spec 給我們的提示，遍歷整個鏈結串列得所求大小。
```c=
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_find_mid 輔助函式
$O(n)$
有鑒於「尋找中點」需求不僅應用於一處，我將此邏輯獨立為本靜態函式。注意第二個參數 `offset` 可用來儲存「中點」實際上自 `head` 往 `next` 方向之距離，不浪費用來存取非連續記憶體的辛勞；若`offset == NULL` 則忽視此參數。相似的，文件註解採 doxygen 格式。
```graphviz
digraph find_mid {
label = <<b>Initial state</b>>;
bgcolor="transparent";
node[shape=record];
graph[rankdir=TD];
head[label="<p> prev | head\n(back) | <n> next"];
front[label="<p> prev | front | <n> next"];
next_dotting[label="... (front direction)", shape=plaintext];
prev_dotting[label="... (back direction)", shape=plaintext];
head:n -> front;
front -> next_dotting
head:p -> prev_dotting
}
```
算法是利用雙向鏈結串列的特性，以兩個指標分別向 `next` 和 `prev` 方向等速移動，透過 `front` 向 `next`、`back` 向 `prev` 遍歷，目標是讓 `front` 最終指向目標。由於每次各走一步，總位移量為 $2$，故有兩種相遇的可能：
1. `back` 和 `front` 最接近時差一，表有偶數個節點，此情況必有一次迴圈中 `back->prev == front`。
2. `back` 和 `front` 會相遇，表有奇數個節點。
```graphviz
digraph find_mid {
label = <<b>Terminate state</b>>;
bgcolor="transparent";
node[shape=record];
graph[rankdir=TD];
subgraph find_mid_odd {
head[label="<p> prev | head | <nxt> next"];
next_dotting1[label="... (front direction)", shape=plaintext];
next_dotting2[label="... (front direction)", shape=plaintext];
prev_dotting[label="... (back direction)", shape=plaintext];
front[label="<p> prev | <m> front\n(odd middle) | <nxt> next"];
back[label="<p> prev | <m> back | <nxt> next"];
head:nxt -> next_dotting1;
head:p -> prev_dotting;
next_dotting1 -> next_dotting2;
next_dotting2:s -> front:m:ne;
prev_dotting -> back:m;
back:p:s -> front:m:nw;
// front:nxt:n -> back:m:s;
// front:p:n -> next_dotting2:s;
}
subgraph find_mid_even {
head_ev[label="<p> prev | head | <nxt> next"];
next_dotting1_ev[label="... (front direction)", shape=plaintext];
next_dotting2_ev[label="... (front direction)", shape=plaintext];
prev_dotting_ev[label="... (back direction)", shape=plaintext];
front_ev[label="<p> prev | <m> front | <nxt> next"];
mid[label="<p> prev | <m> even middle | <nxt> next"];
back_ev[label="<p> prev | <m> back | <nxt> next"];
head_ev:nxt -> next_dotting1_ev;
head_ev:p -> prev_dotting_ev;
next_dotting1_ev -> next_dotting2_ev;
next_dotting2_ev -> front_ev:m;
prev_dotting_ev -> back_ev:m;
front_ev:nxt -> mid:me;
back_ev:p -> mid:mw;
// mid:p -> front_ev;
// mid:nxt -> back_ev:m:s;
}
}
```
用以上兩情況決定迴圈的持續條件。
```c=
/**
* Find the middle point in given list
*
* @param offset pointer to obtain position count of mid point.
* Can pass NULL of you don't need this result.
*/
static struct list_head *q_find_mid(struct list_head *head, int *offset)
{
if (!head || list_empty(head))
return NULL; // nothing to find
// traverse in different direction
struct list_head *front = head->next, *back = head;
int _o = 1;
// two possible cases for "two step in each loop"
// in both cases, "front" will be what we want to delete
// 1. back == front, then there are even nodes
// 2. back->prev == front, then are odd nodes
while (back != front && back->prev != front) {
front = front->next;
back = back->prev;
++_o;
}
if (offset)
*offset = _o;
return front;
}
```
### q_delete_mid
利用 `q_find_mid`，根據以上找到欲刪除節點後，便是正常的刪除操作。
```c=
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
struct list_head *mid = q_find_mid(head, NULL);
if (!mid)
return false;
list_del(mid); // unlink mid node
element_t *to_del = list_entry(mid, element_t, list);
q_release_element(to_del);
return true;
}
```
### q_delete_dup
要刪除重複的節點，首先列表至少要有兩元素，故邊界條件額外考慮僅單節點的情況，可使用 `list_is_singlar` 巨集來判斷。
接下來的演算法為：透過比較鄰近兩元素 (`cur`, `nxt`) 的字串決定行為。
若字串相同，則
1. 刪除 `cur`
2. 以 `mark_del` 標記 `nxt` 為「待刪除元素」
若不同且標記不為空，則
1. 刪除標記下的元素，即上個迴圈的 `nxt`
2. 重設標記為空，避免重複釋放記憶體
節點的走訪可搭配運用 `list_for_each_entry_safe` 巨集。
```c=
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head) || list_is_singular(head))
return false; // nothing to be deleted
// delete cur when cur->value == nxt->value
element_t *cur, *nxt, *mark_del;
// if deletion happens, set mark_del as nxt
// else, delete held node and reset to NULL
mark_del = NULL;
list_for_each_entry_safe (cur, nxt, head, list) {
// notice that nxt == head means the last case,
// just try to go to "else"
if (&nxt->list != head && !strcmp(cur->value, nxt->value)) {
mark_del = nxt;
list_del(&cur->list);
q_release_element(cur);
} else if (mark_del) {
list_del(&mark_del->list);
q_release_element(mark_del);
mark_del = NULL;
}
}
return true;
}
```
### q_swap
$O(n)$
由於後面會實作 `q_reverseK` 函式，而 `q_swap` 實際上就是 `q_reverseK` 的特例，故直接複用即可，這使程式更加易於維護。
```c=
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
// reuse special case of implemented algorithm
q_reverseK(head, 2);
}
```
### q_reverse
$O(n)$
利用巨集，可透過遍歷所有節點，並將節點的 `list_head::next` 和 `list_head::prev` 交換，即表示反轉串列，故以下為第一種實作。
```c=
void q_reverse(struct list_head *head)
{
if (!head)
return; // nothing to be reversed
struct list_head *cur, *nxt;
list_for_each_safe (cur, nxt, head) {
cur->next = cur->prev;
cur->prev = nxt;
}
// in the end, we should also swap the links of head
struct list_head *tmp = head->next;
head->next = head->prev;
head->prev = tmp;
}
```
特例是要另外反轉 `head` 的兩個指標。若要消除此例外，可以使用 `do-while` 迴圈取代，便是第二種實作如下。
```c=
void q_reverse(struct list_head *head)
{
if (!head)
return false; // nothing to be reversed
struct list_head *cur = head, *nxt = head->next;
do {
// swap links
cur->next = cur->prev;
cur->prev = nxt;
// iterate
cur = nxt;
nxt = nxt->next;
} while (cur != head);
}
```
考慮邊界條件，只要 `head` 存在，整套算法即可正常運行。
### q_reverseK
$O(n)$
本函式乍一看與 `q_reverse` 的運作邏輯相似，就是複雜了一點。每 k 個元素一群，要滿 k 個元素才可以進行反轉，故不能邊遍歷邊反轉，得先確認眼下真有 k 個元素。復用 `q_reverse` 得到的演算法可以是:
* 以迴圈不斷...
* 走訪 $k$ 個元素，確認是不是真有 $k$ 個。
* 將一鏈結串列的一定範圍截斷。
* 利用巨集 `list_cut_position`，其根據給定之 `head` 和右界
* 為此我們需一指標 `lead` 向前遍歷 k 位後確認要截斷的位置。
* 注意 `lead` 的起點不可為 `head`，因為 `list_cut_position` 的截斷是「包含」給定之右界: $(head, lead\big]$，範圍是左開右閉。
* 為了不失去領頭做標記的 `lead`，將其初始化為 `head->next`，截斷之右界也順應變成 `lead->prev`。
* 接入暫存串列 `rev_head`。
* 利用已經實作好的 `q_reverse` 反轉暫存串列。
* 接入最終串列 `new_head`。
* 最後不忘將結果接回 `head` 串列。
```c=
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head)
return;
struct list_head *lead = head->next;
LIST_HEAD(new_head);
do {
// move k steps
int i; // counter
for (i = 0; i < k && lead != head; ++i)
lead = lead->next;
if (i == k) { // there are k elements: [from, lead)
// cut k nodes from head, reverse them, and paste to new_head
LIST_HEAD(rev_head);
list_cut_position(&rev_head, head, lead->prev);
q_reverse(&rev_head);
list_splice_tail_init(&rev_head, &new_head);
}
} while (lead != head);
list_splice_init(&new_head, head);
}
```
與 `q_reverse` 相似，考慮邊界條件，只要 `head` 存在，整套算法即可正常運行。
### in_order 輔助函式
由於 [Merge request #133](https://github.com/sysprog21/lab0-c/commit/16fbb731fa3d06e1492967e3c02ddd594940900b) 加入對升序、降序的支援，我決定將「是否正確的排序」的邏輯從原本呼叫 `strcmp` 後比對回傳值的操作獨立成 `in_order` 函式，以便多處重複利用。
實作的部分即儲存 `strcmp` 的結果，對三種可能進行確認，詳見函式內註解。
另由於本函式小巧玲瓏，故加入 `inline` 修飾，期待編譯器將呼叫處改為程式碼展開。
```c=
/**
* Return whether a and b with order: [... , a, b, ...] is in correct ordering,
* where a and b are strings for comparison.
* @param descend whether we're using descending order
*/
static inline bool in_order(const char *a, const char *b, bool descend)
{
int _cmp = strcmp(a, b);
/**
* strcmp(a, b) == 0: always in order
* strcmp(a, b) < 0: inorder if using ascending order
* strcmp(a, b) > 0: inorder if using descending order
*/
return !_cmp || (_cmp < 0 && !descend) || (_cmp > 0 && descend);
}
```
### merge_two_lists 輔助函式
本輔助函式的意義在將 `sub` 串列併入 `major` 串列中，假設兩者都排完序。不同於上課介紹過的「先找一暫存串列，將兩目標串列的節點併入暫存串列後轉移回原串列」的做法，本函式假設一定併入 `major`，故可以省略與 `major` 長度相等之「併入」操作，降低執行時的負擔。
原本的實作為以下:
```c=
/**
* Helper function to merge two sorted lists.
* @param major major list of merging, all nodes will
* move to this linked list, must not be empty!
* @param sub list to be merged.
*/
static void merge_two_lists(struct list_head *major, struct list_head *sub)
{
if (list_empty(major)) {
list_splice_init(sub, major);
return;
} else if (!sub || list_empty(sub)) {
return;
}
struct list_head *m = major->next;
element_t *m_ele = list_entry(m, element_t, list);
element_t *s_ele = list_first_entry(sub, element_t, list);
do {
if (strcmp(m_ele->value, s_ele->value) > 0) {
list_move_tail(sub->next, m);
s_ele = list_first_entry(sub, element_t, list);
} else if (m->next != major) {
m = m->next;
m_ele = list_entry(m, element_t, list);
} else {
list_splice_tail_init(sub, major);
return;
}
} while (!list_empty(sub));
}
```
除了 edge case 有點雜亂外， `do-while` 迴圈內也不怎麼「美觀」，函式的其中一個返回的可能甚至在 `else` 條件下，實在說不上有品味...
經重構後為以下，邏輯相等不過好看多了。
```c=
/**
* Helper function to merge two sorted lists.
* @param major major list of merging, all nodes will
* move to this linked list
* @param sub list to be merged.
*/
static void merge_two_lists(struct list_head *major, struct list_head *sub)
{
if (!sub)
return;
struct list_head *m = major->next;
element_t *m_ele = list_entry(m, element_t, list);
element_t *s_ele = list_first_entry(sub, element_t, list);
while (!list_empty(sub) && m != major) {
if (strcmp(m_ele->value, s_ele->value) > 0) {
list_move_tail(sub->next, m);
s_ele = list_first_entry(sub, element_t, list);
} else {
m = m->next;
m_ele = list_entry(m, element_t, list);
}
}
list_splice_tail_init(sub, major);
}
```
新的 `merge_two_lists` 應該提供升/降序的合併，故將比較部分從
```c=
strcmp(m_ele->value, s_ele->value) > 0
```
改為
```c=
!in_order(m_ele->value, s_ele->value, descend)
```
注意新的函式簽名額外加入 `descend` 參數。
### q_i_sort (insertion sort) 輔助函式
考慮到後面我們要實作穩定的排序，不一定要使用 merge sort，insertion sort 也是某些情境下的好選擇。
在資料結構中我們學到，在欲排序元素較少的情況下，尤其趨近排序完成的情況下，`insertion sort` 擁有優異的效能表現，無論是時間抑或空間複雜度上。
時間上可使用迴圈完成，無需 function call 的額外負擔。具體而言可能有參數的預備、calling stack 的操作 push/pop，code memory 中的跳導致的 cache miss 等。
空間上 insertion sort 可以就地排序，且僅需 $O(1)$ 的額外空間，比起 merge sort 使用 calling stack、quick sort 使用 calling stack 或普通 stack 還好。
注意到我的演算法參數有二，標示著欲排序的範圍。不直接如 `q_sort` 傳入 `head` 是為了擴展性，是為了讓本函式可以進行局部排序。
```c=
/**
* Sort list of closed range [from, to] using insertion sort.
* Assume from != NULL and to != NULL !!!
* @param from starting node of sorting (include), must NOT be NULL
* @param to ending node of sorting (include), must NOT be NULL
*/
static void q_i_sort(struct list_head *from, const struct list_head *to)
{
const struct list_head *l_bd = from->prev,
*r_bd = to->next; // boundary never change!
struct list_head *cur = from->next;
while (cur != r_bd) { // loop if haven't reach end of sorting range
struct list_head *nxt = cur->next, *prv = cur;
element_t *c_ele = list_entry(cur, element_t, list), *p_ele;
// traverse (back) to correct position
// cur should finally be placed at prv->next;
do {
prv = prv->prev;
p_ele = list_entry(prv, element_t, list);
} while (prv != l_bd && strcmp(p_ele->value, c_ele->value) > 0);
list_move(cur, prv);
cur = nxt; // iterator increment
};
}
```
順帶一提，一開始實作時由於不是先以 `l_bd` (left bound) 和 `r_bd` (right bound) 兩恆定指標將我們感興趣的邊界記下，而是動態去與 `from`、`to` 的鄰居比較，未考量 `from`、`to` 本身也是會被移動的對象，所以除錯搞了很久...
重構時為邊界加上 `const` 修飾。
新的 `q_i_sort` 應該提供升/降序的合併，故將比較部分從
```c=
strcmp(m_ele->value, s_ele->value) > 0
```
改為
```c=
!in_order(m_ele->value, s_ele->value, descend)
```
注意新的函式簽名額外加入 `descend` 參數。
### q_sort
本函式為 merge sort + insertion sort 的混合穩定排序。當欲排序數量大於 `THRESHOLD` 時使用 merge sort 的 partition，反之使用前面實作好的 insertion sort `q_i_sort` 直接排序。最後透過同樣實作好的 `merge_two_lists` 完成合併。
程式碼可分為三塊解釋。
1. 邊界條件與變數初始化
`THRESHOLD` 的大小我認為與 insertion sort 的甜蜜點和 cache 的大小有關。
:::info
另外注意到之所以我不將單節點串列納入邊界情況，是因為我的實作確保以下兩點：
1. 每次必定切成近乎等長的兩串列呼叫遞迴
2. 使用 insertion sort 針對長度較小的情況排序
如此，遇到長度很低的串列自然會使用 insertion sort 排序完成，省略了大量函式呼叫。
:::
```c=
if (!head)
return;
// Use merge sort + insertion sort
// threshold to use insertion sort optimization
static const int THRESHOLD = 32;
// for merge sort, we first divide then conquer
// initialize stack two heads
LIST_HEAD(other);
```
2. 切分與遞迴
中點的尋找我採用前面實作過的 `q_find_mid` 來同時取得分割點與此點兩邊串列大致的長度，後續將以此決定切分後的邏輯。
```c=
// find pivot
/**
* Offset of left side (mid point), which is
* approximately the same as right side
*/
int offset;
struct list_head *pivot = q_find_mid(head, &offset);
// divide into two lists: head and other
list_cut_position(&other, head, pivot);
if (offset > THRESHOLD) {
q_sort(head);
q_sort(&other);
} else {
q_i_sort(head->next, head->prev);
q_i_sort(other.next, other.prev);
}
```
3. 合併
以 `head` 為標的合併。
```c=
// merge then complete
merge_two_lists(head, &other);
```
新的 `q_sort` 函式簽名加入 `descend` 參數，連帶調整呼叫 `q_sort`, `q_i_sort` 和 `merge_two_lists`。
### q_descend 和 q_ascend 的實作與重構
$O(n)$
解決 `q_descend` 的演算法為將題意換句話說，就是維護從右往左看的單調上升序列。
```c=
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head) || list_is_singular(head))
return 0;
int cnt = 0;
struct list_head *lead = head->prev, *test = lead->prev;
// not necessarily change in each loop, declare outside
element_t *l_ele = list_entry(lead, element_t, list);
do {
// must change in each loop
element_t *t_ele = list_entry(test, element_t, list);
struct list_head *tmp = test->prev;
if (strcmp(t_ele->value, l_ele->value) > 0)
l_ele = t_ele; // save in new list
else {
list_del(test); // remove from doubly linked list
q_release_element(t_ele); // delete element node
++cnt;
}
test = tmp; // move test
} while (test != head);
return cnt;
}
```
由於新版 `lab0-c` 改成要實作 `q_ascend` 和 `q_descend` 兩個維護單調序列的函式，此兩函式實際上唯一的區別在[輔助函式 `in_order`](#in_order-%E8%BC%94%E5%8A%A9%E5%87%BD%E5%BC%8F) 的回傳值。如同 [q_insert_head 和 q_insert_tail 的實作與重構](#q_insert_head-%E5%92%8C-q_insert_tail-%E7%9A%84%E5%AF%A6%E4%BD%9C%E8%88%87%E9%87%8D%E6%A7%8B)，我以 `gen_q_monotonic` 巨集實現兩函式，透過巨集參數決定演算法維護的是單調升序抑或降序的序列。
與舊版的 `q_descend` 相比，調換 `if-else` 的內容，使「升序」(`descend` 替換為 `false`) 為預設的序列，這符合程式的直觀行為。
```c=
#define gen_q_monotonic(fn_suffix, descend) \
int q_##fn_suffix(struct list_head *head) \
{ \
/* https://leetcode.com/problems/remove-nodes-from-linked-list/ */ \
if (!head || list_empty(head) || list_is_singular(head)) \
return 0; \
int cnt = 0; \
struct list_head *lead = head->prev, *test = lead->prev; \
\
/* not necessarily change in each loop, declare outside */ \
element_t *l_ele = list_entry(lead, element_t, list); \
\
do { \
/* t_ele must change in each loop */ \
element_t *t_ele = list_entry(test, element_t, list); \
struct list_head *tmp = test->prev; \
\
if (!in_order(t_ele->value, l_ele->value, descend)) { \
list_del(test); /* remove from linked list */ \
q_release_element(t_ele); /* delete element node */ \
++cnt; \
} else { \
l_ele = t_ele; /* save in new list */ \
} \
\
test = tmp; /* move test */ \
} while (test != head); \
return cnt; \
}
```
如此一來，`q_ascend` 和 `q_descend` 的實作變成簡單兩行。
```c=
/* Remove every node which has a node with a strictly less value anywhere to
* the right side of it */
gen_q_monotonic(ascend, false);
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
gen_q_monotonic(descend, true);
```
### q_merge
$O(n)$
當中 $n$ 為總元素數。
要將所有 queue 的內容併為一個，相當於不斷套用前面實作好的「將一串列併入某串列」的邏輯。要使 `merge_two_lists` 正常運作的條件為 `major` 參數需非 `NULL`，故將等價意義的 `!head || list_empty(head)` 設為邊界條件。
過程為先將首個 queue 元素 `first` 自原串列分離，遍歷所有剩下的串列並將當中的 queue 一個個併入 `first->q`，最後把 `first` 接回元素串列。
```c=
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
// unlink first queue
list_del(&first->chain);
// iterate through remaining queues and merge into "first->q"
queue_contex_t *cur = NULL;
list_for_each_entry (cur, head, chain) {
merge_two_lists(first->q, cur->q);
first->size += cur->size;
}
// relink first queue
list_add(&first->chain, head); // restore the first queue
return first->size;
}
```
新的 `q_merge` 應該提供升/降序的合併，故將比較部分從
```c=
strcmp(m_ele->value, s_ele->value) > 0
```
改為
```c=
!in_order(m_ele->value, s_ele->value, descend)
```
注意新的函式簽名額外加入 `descend` 參數。
## Valgrind 的使用與記憶體分析
為了更好的閱讀 Valgrind 的輸出報告，可以使用命令列的重新導向功能，比如
```bash
(make valgrind) > make_valgrind_output.log 2 > make_valgrind_err.log
```
若要將 `stdout` 和 `stderr` 重新導向至同一檔案，可改成以下
```bash
(make valgrind) > make_valgrind.log 2>&1
```
如此一來我們便能仔細端詳 `stdout` 和 `stderr`。
### memcpy 記憶體讀取問題
在 `q_remove_head` 和 `q_remove_tail` 中，我原本認為使用 `memcpy` 理當較 `strncpy` 高效，故使用前者。不過開啟 Valgrind 後發現 `memcpy` 會讀取到非法位置。
```text
scripts/driver.py -p /tmp/qtest.YkLqZX --valgrind
# Test of insert_head and remove_head
==320616== Invalid read of size 8
==320616== at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==320616== by 0x10FD60: memcpy (string_fortified.h:29)
==320616== by 0x10FD60: q_remove_head (queue.c:102)
==320616== by 0x10CA60: queue_remove (qtest.c:354)
==320616== by 0x10CC08: do_rh (qtest.c:411)
==320616== by 0x10E356: interpret_cmda (console.c:181)
==320616== by 0x10E90B: interpret_cmd (console.c:201)
==320616== by 0x10ED0C: cmd_select (console.c:610)
==320616== by 0x10F5F8: run_console (console.c:729)
==320616== by 0x10D748: main (qtest.c:1338)
==320616== Address 0x4b80128 is 8 bytes before a block of size 2,049 alloc'd
==320616== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==320616== by 0x10C7FF: queue_remove (qtest.c:319)
==320616== by 0x10CC08: do_rh (qtest.c:411)
==320616== by 0x10E356: interpret_cmda (console.c:181)
==320616== by 0x10E90B: interpret_cmd (console.c:201)
==320616== by 0x10ED0C: cmd_select (console.c:610)
==320616== by 0x10F5F8: run_console (console.c:729)
==320616== by 0x10D748: main (qtest.c:1338)
==320616==
==320616== Invalid read of size 8
```
## list_sort.c 排序比較
:::info
TODO
:::
> 以下為小筆記
Linux 核心 list_sort.c 引用關係表，省略所有名為 `linux` 的路徑。
```mermaid
graph TD;
LIST_SORT_C["list_sort.c"] --> LIST_SORT_H["list_sort.h"] --> TYPES_H["type.h"];
LIST_SORT_C --> CONTAINER_OF_H["container_of.h"];
LIST_SORT_C --> LIST_H["list.h"];
LIST_H --> CONTAINER_OF_H;
LIST_H --> TYPES_H["type.h"];
TYPES_H --> UAPI_TYPES_H["uapi/type.h"];
UAPI_TYPES_H --> ASM_TYPES_H["asm/type.h"];
```
## Web server 調整
:::info
TODO
:::
> 以下為小筆記
* `select` 資訊
以下資訊來自 [Linux Manual Page](https://man7.org/linux/man-pages/man2/select.2.html)。
`select` 函式功能
> select() allows a program to monitor ***multiple file descriptors***, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is ***considered ready if it is possible to perform a corresponding I/O operation*** (e.g., read(2), or a sufficiently small write(2)) ***without blocking***.
關於 File descriptor sets
> The principal arguments of select() are three "sets" of file descriptors (declared with the type fd_set), which ***allow the caller to wait for three classes of events on the specified set of file descriptors***. Each of the fd_set arguments may be specified as NULL if no file descriptors are to be watched for the corresponding class of events.
注意官方提到若使用於迴圈內，也就是 `fd_set` 可能在迴圈內被修改，則我們應該 (用 `FD_ZERO`) 重新初始化 `fd_set`。
以下四個巨集協助修改 file descriptor set。
* `FD_ZERO`: 初始化 `fd_set`。
* `FD_SET`: 加入某 `fd` 至 `fd_set`。
* `FD_CLR`: 將某 `fd` 自 `fd_set` 移除。
* `FD_ISSET`: 確認某 `fd` 是否在 `fd_set` 中，存在則非零，不存在則為零。
另一函式 `pselect` 與 `select` 有些許不同。
* 加入 `select`
於 `linenoice:line_edit` 中加入 Spec 建議的程式碼後，須引入以下標頭檔。
```c=
#include <netinet/in.h> /* sockaddr_in */
#include <sys/select.h> /* fd_set */
```
並修改 `listenfd` 為 web 輸入的檔案描述子 `l.ifd`、將 `SA` 縮寫改為 `struct sockaddr_in`。
## 其他紀錄
### :penguin: [作業完成度](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-f)
* [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* [x] 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
* [x] 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* [x] 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
* [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
* [ ] 確保 `qtest` 提供的 `web` 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 `linenoise` 套件就無法使用，請提出改善機制
* [ ] 提示: 使用 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫
* [ ] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」
* [ ] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10` 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 `qtest` 切換不同的 PRNG 的實作 (可選定 [Xorshift](https://en.wikipedia.org/wiki/Xorshift))，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質
* [ ] 參見: [由大數法則理解訊息熵 (entropy) 的數學意義](https://hackmd.io/@8dSak6oVTweMeAe9fXWCPA/ryoegPgw_)
* [ ] 參見: [The Linux Pseudorandom Number Generator Revisited](https://eprint.iacr.org/2012/251.pdf)
* [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。
* [ ] 注意：現有實作存在若干致命缺陷，請討論並提出解決方案
* [ ] 在 [oreparaz/dudect](https://github.com/oreparaz/dudect) 的程式碼具備 percentile 的處理，但在 [lab0-c](https://github.com/sysprog21/lab0-c) 則無。
* [ ] 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
* [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2023-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* [ ] 詳閱第 1 週所有教材及作業描述 [(一)](/@sysprog/linux2023-lab0-a), [(二)](/@sysprog/linux2023-lab0-b), [(三)](/@sysprog/linux2023-lab0-c), [(四)](/@sysprog/linux2023-lab0-d), [(五)](/@sysprog/linux2023-lab0-e)，記錄你的啟發和疑惑
* [ ] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
### Quick Note
* 以規定之標準格式化程式碼檔案
```bash
clang-format -i *.[ch]
```
* `if-else` 採 K&R 風格
```c=
if (condition1) {
} else if (condition2) {
} else {
}
```
* GDB 重要命令與用法紀錄
* 帶參數除錯
```bash
gdb --args EXECUTABLE ARG1 ARG2 ...
```
* 使用重新導向除錯
```bash
gdb EXECUTABLE
...
(gdb) run < FILE_TO_REDIRECT_AS_INPUT
```
* 常用命令
| Command | Alias | Argument | Usage |
|:-----------:|:-----:|:------------------:|:----------------------------------------------------------------------------:|
| `help` | `h` | `ALL_GDB_COMMAND` | 啥都不知道時先 `help` 一下就對了 |
| `print` | `p` | `SOMETHING` | 印出 `SOMETHING`，可以是參數、<br>指標，甚至呼叫函式的節果 |
| `break` | `b` | `FILE:LINE_NUMBER` | 在 `FILE` 的第 `LINE_NUMBER`<br>設定中斷點，比如 `b queue.c:123` |
| `step` | - | - | 單步執行 |
| `continue` | `c` | - | 從當前中斷點繼續執行<br>(至下個中斷點或執行結束 or 報錯) |
| `info` | `i` | `SOME_GDB_COMMAND` | 印出 `SOME_GDB_COMMAND` 的相關訊息，可使用 `help info` 查看哪些命令可供查看 |
| `backtrace` | `bt` | - | 印出 function stack |
| `frame` | `f` | `FRAME_NUMBER` | 移動至 function stack 中編號 `FRAME_NUMBER` 的 frame，目前有哪些 frame 可用 `bt` 查詢 |
| `up` | - | - | 切換到上層 frame |
| `down` | - | - | 切換到下層 frame |
:::warning
查閱教育部辭典「[幀](https://dict.revised.moe.edu.tw/dictView.jsp?ID=7954)」的釋義: 量詞。計算照片、字畫等的單位。但這樣的量詞跟 GDB 原本的 stack frame 不相符，後者更在意可切換 stack context 的範疇。因應漢語的侷限，這裡不該翻譯。
:notes: jserv
> ok
:::
* Valgrind
* 透過維護一組暫存器和主記憶體的副本，安全監視程式的運行。寫好的 Machine Code 先被轉譯為虛擬指令集 VEX (中間表示法 IR)，再以 JIT 的方式重新翻譯為目標架構的 Machine Code。
* 自動測試程式
* 透過 function hooking 搭配雙向鏈結串列，儲存記憶體使用的
* 測試時將 `malloc`, `calloc` 透過巨集與 `test_malloc`, `test_calloc` 掛鉤。
### Sync fork 紀錄
由於我 fork 的 repository 與源 repository 有不少落差，今希望將源 repository (i.e. `upstream`) 的修改也加入我 fork 的 repository。
* Git 為遠端加入 `upstream`
* 查看當前遠端 repository
```bash
> git remote -v
origin https://github.com/Shiritai/lab0-c.git (fetch)
origin https://github.com/Shiritai/lab0-c.git (push)
```
* 新增 `upstream`
```bash
> git remote add upstream https://github.com/sysprog21/lab0-c.git
```
* 確認
```bash
> git remote -v
origin https://github.com/Shiritai/lab0-c.git (fetch)
origin https://github.com/Shiritai/lab0-c.git (push)
upstream https://github.com/sysprog21/lab0-c.git (fetch)
upstream https://github.com/sysprog21/lab0-c.git (push)
```
* Sync fork
* 載入 `upstream`
```bash
> git fetch upstream
remote: Enumerating objects: 94, done.
remote: Counting objects: 100% (58/58), done.
remote: Compressing objects: 100% (10/10), done.
remote: Total 94 (delta 48), reused 54 (delta 48), pack-reused 36
Unpacking objects: 100% (94/94), 32.80 KiB | 645.00 KiB/s, done.
From https://github.com/sysprog21/lab0-c
* [new branch] master -> upstream/master
```
* 保險起見將本地主分支備份為 `backup`
```bash
> git checkout -b backup
Switched to a new branch 'backup'
> git checkout master
Switched to branch 'master'
> git branch
backup
* master
(END)
```
* 嘗試與 `upstream` 合併
```bash
> git merge upstream/master
Auto-merging .github/workflows/main.yml
CONFLICT (content): Merge conflict in .github/workflows/main.yml
Auto-merging linenoise.c
Auto-merging qtest.c
Auto-merging queue.c
CONFLICT (content): Merge conflict in queue.c
Auto-merging report.c
CONFLICT (content): Merge conflict in report.c
Automatic merge failed; fix conflicts and then commit the result.
```
使用 git 自動合併的話，可以看到數個檔案出現衝突，這符合預期，接下來便是針對衝突逐一解決。
* merge 紀錄
* 使用 VSCode 內 Merge editer 的 accept combination 會自動嘗試合併兩方的修改。
* `q_sort` 的部分，由於改成支援升序與降序兩種方式，`q_sort` 的簽名進行了調整，需合併衝突：採用新簽名。
* 新增 `q_ascend` 函式，直接併入即可。
### 遇到問題
* SSH 設定與 `ssh-private-key` 問題
* 這可能是由於自己已經有一 ssh key，卻又不小心生成另一個，因為自以為舊的可能不會派上用場。
* 目前透過修改 `main.yml` 使 github action 可運行測試。
* 當然這顯然不是個好方法，僅權宜
```yml
# TODO uncomment this
# - uses: webfactory/ssh-agent@v0.7.0
# with:
# ssh-private-key: ${{ secrets.SSH_PRIVATE_KEY }}
```
* ~~具體等完成 lab 的其他部分後再來研究...~~
* 透過 sync fork，將 `upstream` 上同學的 [merge request](https://github.com/sysprog21/lab0-c/pull/112) 併入後得到解決。
* 目前實作之分數為 $100/100$，不知為何突然最後一項常數時間的測試場景通過了...
* Cppcheck 警告
* 警告位置: `repost.c:report_event`
```bash
static char *msg_name_text[N_MSG] = {
"WARNING",
"ERROR",
"FATAL ERROR",
};
```
* 原本透過加上 `const` 解決。
* `upstream` 的 [commit 0180045](https://github.com/sysprog21/lab0-c/commit/0180045dba46fd4571f48ff10faed7d1872a8ad8) 將 `pre-commit.hook` 修改，我將其 sync 回我 fork 的 repository 而解決。
### Typos or patch?!
* 要先 fork + 打開 Github Action 後，照 Spec 的「小試身手」操作才會正確運行
* git commit 後會自動進行測試、報告結果，並寄送至郵件
* Valgrind + 自動測試程式
* Signal 處理與應用
* `queue_init` 不存在，應為 `q_init`
* `sigsegvhandler` 不存在，應為 `sigsegv_handler`
* `sigalrmhandler` 不存在，應為 `sigalrm_handler`
:::warning
請修改 HackMD 頁面。
:notes: jserv
> 好的，修改完畢。
:::
* `web`
* `linenoiseEdit` 可改為 `linenoice.c:line_edit` 方能立刻找到
* 程式碼的諸多函式名稱有誤，需舉燭
* 部分操作難以理解，似乎因為是針對以前的程式碼說明？！
* Linux 核心排序實作的演進
* 數學推導過程沒採用 LaTeX 風格於 Markdown 的置中語法，有點不習慣。即:
```md
$$
\rm{example statement}
$$
```
* 整個 Hackmd 都有的排版建議
* 程式碼區於列表下 (i.e. `*` 無序列表或 `1. ` 有序列表) 幾乎都沒有縮排，也許是為了控制單行字數能保持一致，不過有點違和。
Sign in with Wallet
Connect another wallet