# 2024q1 Homework1 (lab0)
contributed by < [`bclegend`](https://github.com/bclegend) >
### Reviewed by `brian049`
- 要注意撰寫中文時要避免使用到英文鍵盤的逗號，且句子尾端加上句號才會形成完整的句子。
>感謝建議，已改進。
- 在解釋 `q_free` 和 `q_remove_head / q_remove_tail` 函式時可以藉由 `-` 或是 `*` 等等列點式來讓整段文字易讀。
- `q_sort` 函式缺少解釋。
- [commit 1282572](https://github.com/bclegend/lab0-c/commit/1282572617e6eeb243ccf097149ad63c83ba31a0) 和 [commit 54dab51](https://github.com/bclegend/lab0-c/commit/54dab51b796fcbf69c5fbfcdba260913972aa88c) 分別是 `Add q_size` 以及 `Modify q_size`，可以在後者的 commit message 當中補述為什麼要那樣改程式碼。
> 感謝建議，已依照建議更新 [commit 2766e40](https://github.com/bclegend/lab0-c/commit/2766e40daed3b268d6a0ad2674ca84c443c7402f) 。
- `q_reverseK` 函式解釋當中有添加圖示使整體解釋更明瞭。
:::danger
注意細節，上方的空白。
:::
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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.
$ 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): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
```
## 遭遇到的問題
### 如何解讀這段程式碼
```c
/**
* container_of() - Calculate address of structure that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of structure containing ptr
*/
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#else
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif
```
> 閱讀指定的教材了嗎？若是，列出過程中遇到的問題。
### 測試時間過久
在測試程式碼時在 `TESTING trace trace-17-complexity` 卡住，而無法結束測試。
```
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Testing insert_tail...(0/10)
meas: 0.00 M, not enough measurements (9120 still to go).
```
## 佇列操作的程式碼實作
:::danger
command 是「命令」，而非「指令」(instruction)
:::
編寫完程式後需要使用以下命令<s>指令</s> ，使程式碼排版符合規範。
```shell
$ clang-format -i queue.c
```
#### 測試範例
```shell
$ ./qtest -v 3 -f traces/trace-eg.cmd
```
### q_new
宣告一個新的佇列。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
宣告一個新的佇列並將 `list_head` 大小的空間分配給新的佇列，並判斷該佇列是否成功分配。
將佇列結構中指向下一個以及前一個節點的指標 `prev` 和 `next` 宣告在該新佇列之中。
> [commit 784e4f9](https://github.com/bclegend/lab0-c/commit/784e4f9231355bfe11c0c941799330f9f5400469)
問題
* 為什麼要加入判斷式 `if(!q_empty)` ？
If the space cannot be allocated, a null pointer is returned. ( C99 規格書：7.20.3)
* ==什麼情況可能導致空間無法配置？==
:::warning
參閱作業系統教科書關於 slab 的描述
:::
### q_free
釋放在佇列中的節點，並釋放佇列。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
首先需要確認佇列是否存在。
宣告指標 `entry` 用於指向目前的節點和指標 `safe` 用於指向下一節點。
利用 `list_for_each_entry_safe` 來經過佇列中的每個節點，運用 `list_del` 來刪除節點於佇列中的連結，並使用 `free` 來釋放該節點的記憶體。
在刪除完佇列中的節點後，釋放節點 `head` 的記憶體。
```diff
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
list_del(&entry->list);
- free(entry);
+ q_release_element(entry);
}
free(head);
}
```
> [commit 37f921b](https://github.com/bclegend/lab0-c/commit/37f921b3618f91c0a91ea18e57738bb7faf2b624)
問題
* `return;` 是否合理?會有什麼表現？
A return statement with an expression shall not appear in a function whose return type is void. A return statement without an expression shall only appear in a function whose return type is void. ( C99 規格書：6.8.6.4)
* 為什麼用 `free(entry)` 會讓佇列無法釋放節點？
```
cmd> new
l = []
cmd> ih hihi 20
l = [hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi]
cmd> free
l = NULL
ERROR: There is no queue, but 20 blocks are still allocated
```
:::warning
提供 GDB 實驗步驟和分析
:::
### q_insert_head / q_insert_tail
將新的節點插入佇列的頭部/尾端。
函式 `q_insert_head` 運用 `list_add` 將目標節點加入佇列頭部，而函式 `q_insert_tail` 運用 `list_add_tail` 將目標節點加入佇列尾端。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
首先需要確認佇列是否存在。
宣告一個新的 `element` 並將 `element_t` 大小的空間分配給新的 `element` ，並確認 `element` 是否配置成功。
將目標字元指標 `s` 指配到新的 `element->value` 中，並確認是否成功指配。
利用 `list_add` 或是 `list_add_tail` 將 `element` 加入到佇列之中，並回傳 `true` 回報 `element` 已經加入佇列之中。
:::danger
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
:::
> [commit b215d6e](https://github.com/bclegend/lab0-c/commit/b215d6e504866a2e0677021e5cddb1609f77ab8d)
> [commit 489b0e4](https://github.com/bclegend/lab0-c/commit/489b0e43f294d379707d796f70adede21494fb17)
問題
* 什麼是 [`strdup`](https://en.cppreference.com/w/c/experimental/dynamic/strdup)?
:::warning
查閱 Linux man page，避免看 cppreference.com 網站，因為後者是舊的副本。
:::
```shell
$ man strdup
```
> 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
將佇列頭部/尾部的節點從佇列中移除。
函式 `q_remove_head` 運用 `head` 中的 `next` 成員指定目標節點而函式 `q_remove_tail` 運用 `head` 的 `prev` 成員指定目標節點 。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
首先需要確認佇列是否存在以及佇列是否為空的佇列。
宣告一個新的指標 `node` 將 `head->next` 或是 `head->prev` 指派到 `node`
宣告一個 `element_t` 的指標 `element` ，並將 `node` 的進入點指派到。`element` 中，
將該節點中的字串依照設定的長度 `bufsize` 複製到字元指標 `sp` 中，並在字元最後加入 `\0` 。
使用函式 `list_del` 刪除該節點在佇列中的連結。
> [commit 93c580d](https://github.com/bclegend/lab0-c/commit/93c580d4884c3f51761947a1a1ef2a63f9cf5a72)
> [commit 7b1e6fe](https://github.com/bclegend/lab0-c/commit/7b1e6fee876aaee22cb2ae638aaf0eee678ed606)
問題
* 什麼是 [`strncpy`]()?
```shell
$ man strdup
```
> The strndup() function is similar (with `strdup`) , but copies at most n bytes. If s is longer than n, only n bytes are copied, and a terminating null byte ('\0') is added.
參考 [`Risheng1128`](https://github.com/Risheng1128) 提供的範例中以下程式碼作用為何？
測試：
1.以下實際作用為何？
2.若 `strncpy` 已經在末端加入 ('\0') 那 `sp[bufsize - 1] = 0;` 的目的為何？
```c
if (sp) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = 0;
}
```
:::warning
有疑慮就該去做實驗並分析。
:::
### q_size
計算在佇列中有幾個節點 。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
首先需要確認佇列是否存在。
指派 `0` 到新宣告的整數 `count` 中。
使用函式 `list_for_each` 訪問每一個節點，每存取<s>訪問</s> 一個節點就將 `count` 加 `1` ，計算出在佇列中的節點數量。
:::danger
access 的翻譯是「存取」，而非「訪問」(visit)
:::
> [commit 1282572](https://github.com/bclegend/lab0-c/commit/1282572617e6eeb243ccf097149ad63c83ba31a0)
### q_delete_mid
刪除在佇列中間的節點。
設計流程 : 從 `head` 由前往後和由後往前出發，當這兩個指向同一個位置時這個位置會在佇列的中間，因此我們只需要刪除這個節點，就能達成我們所期望的效果。
首先需要確認佇列是否存在。
並同時宣告兩個指標 `move_head` 以及 `move_tail` ，並分別指派 `head` 到指標之中。
在迴圈中同時移動 `move_head` 到 `next` 的位置以及移動 `move_tail` 到 `prev` 的位置，並在 `move_head->next` 與 `move_tail->prev` 指向同一個位置時或是 `move_head->next` 指向 `move_tail` 時離開迴圈。
將 `move_head` 移動到下一個節點，並刪除且釋放該節點。
> [commit cebcb6e](https://github.com/bclegend/lab0-c/commit/cebcb6e9c032d98164002fd71b1d3f60692117b7)
### q_delete_dup
:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement
「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
根據 [wanghanchi](https://hackmd.io/@wanghanchi/linux2023-lab0#q_merge) 的筆記中提到的，`q_delete_dup` 是針對已經排序過後的佇列進行刪除有重複字串的節點，因此在實作<s>實做</s> 時我們需要比較下一個節點上的字串即進行刪除。
用函式 `list_for_each_entry_safe`(Iterate over list entries and allow deletes) 組成巢狀迴圈比對每個節點中的數值是否一致，若一致則刪除該節點。
> [commit de1e8bb](https://github.com/bclegend/lab0-c/commit/de1e8bbd25772f8dac2249da8b70f5b36b2c29e9)
問題
* 在程式碼中若缺少條件 `entry->list.next != head &&` 會造成錯誤 `Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)` 的原因為何？
* 在 `lab0-c/list.h` 中 `list_for_each_safe` 和 `list_for_each_entry_safe` 的描述如下
```c
list_for_each_safe - Iterate over list nodes and allow deletions
list_for_each_entry_safe - Iterate over list entries and allow deletes
```
deletes 和 deletions 有什麼差別？
### q_swap
將佇列中的節點從頭到尾進行兩兩交換。
依序經過佇列中的每個節點與下一個節點進行交換。
首先需要確認佇列是否存在。
宣告一個新的指標 `node` 並利用函式 `list_for_each` 讓該指標經過佇列中的每個節點。
在經過節點時將節點與節點所指向的下一節點進行交換。
```diff
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *node;
list_for_each (node, head) {
+ if (node->next == head)
+ break;
list_move(node, node->next);
}
}
```
若缺少以下判斷式，原程式碼會將佇列頭部以及尾端進行交換，而這不是我們所希望的效果。
```diff
+ if (node->next == head)
+ break;
```
在 `q_reverseK` 完成的情況下，使用以下程式可以達成與 `q_swap` 一致的結果。
```c
void q_swap(struct list_head *head)
{
q_reverseK(head,2);
}
```
### q_reverse
將佇列中所有的節點反向。
在使用函式 `list_for_each_safe` 時，會將指標 `safe` 指向 `node->next` 並且由於函式 `list_for_each_safe` 支持在迭代中移除節點的操作，因此選用此函式對用在該實作中。
首先需要確認佇列是否存在。
接著宣告兩個指標 `node` 以及 `safe` 並在引用函式 `list_for_each_safe` 時將 `node` 指向 `head->next` 並將 `safe` 指向 `node->next`。
接著在每次的迭代中會先將指標 `safe` 指向 `node->next` 的位置，並對調 `node` 中指向前後節點的位置。
最後由於迭代結束後節點 `head` 沒有被改動到，因此另外將節點 `head` 指向前後節點的指標 所指向的位置進行對調。
> [commit bd64e32](https://github.com/bclegend/lab0-c/commit/bd64e32cd5ffe113b30320e5d37497e4dfcfc793)
### q_reverseK
將在佇列中的節點以 `k` 為一組進行反轉，直到剩餘的佇列不足 `k` 個節點
首先需要確認佇列是否存在。
接下來宣告 `nhead` 並初始為 `LIST_HEAD` ，另外計算 `times` 為該佇列需要反轉段落有幾段。
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head -> struct0
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
nhead
}
{
rank="same";
nhead
}
}
```
再來宣告 `temp1` 以及 `temp2` 並初始為 `LIST_HEAD` ，作用分別為在每一次的迭代中將 `head` 所指向的佇列中首個節點放到 `temp1` 所指向的佇列中，接著將 `temp1` 中的節點插入到 `temp2` 所指向的佇列中的前方，重複直到執行 `k` 次。
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
temp1 [fontcolor="blue"]
temp2 [fontcolor="blue"]
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
temp1->struct0
nhead
}
{
rank="same";
nhead
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
temp1 [fontcolor="blue"]
temp2 [fontcolor="blue"]
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
temp2->struct0
nhead
}
{
rank="same";
nhead
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
temp1 [fontcolor="blue"]
temp2 [fontcolor="blue"]
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head -> struct2
struct2 -> struct3
struct3 -> struct4
temp1->struct1
temp2->struct0
nhead
}
{
rank="same";
nhead
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
temp1 [fontcolor="blue"]
temp2 [fontcolor="blue"]
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head -> struct2
struct2 -> struct3
struct3 -> struct4
temp1
temp2->struct1
struct1->struct0
nhead
}
{
rank="same";
nhead
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
temp1 [fontcolor="blue"]
temp2 [fontcolor="blue"]
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head -> struct3
struct3 -> struct4
temp1->struct2
temp2->struct1
struct1->struct0
nhead
}
{
rank="same";
nhead
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
temp1 [fontcolor="blue"]
temp2 [fontcolor="blue"]
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head -> struct3
struct3 -> struct4
temp1
temp2->struct2
struct2->struct1
struct1->struct0
nhead
}
{
rank="same";
nhead
}
}
```
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
temp1 [fontcolor="blue"]
temp2 [fontcolor="blue"]
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head -> struct3
struct3 -> struct4
temp1
nhead->struct2
struct2->struct1
struct1->struct0
nhead
}
{
rank="same";
nhead
}
}
```
並將 `temp2` 指向的佇列插入 `head` 指向的佇列尾端，並將 `temp2` 所指向的佇列插入 `nhead` 所指向的佇列 `times` 次後，將 `head` 所指向佇列 `head` 剩餘的節點插入 `nhead` 所指向的佇列的尾端。
```graphviz
digraph structs {
node[shape=plaintext];
"k=3" [fontcolor ="blue"]
head [fontcolor="red"];
nhead [fontcolor="red"];
node[shape=box];
struct0 [label= "1"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "4"];
{
rank="same";
head
struct3 -> struct4
nhead->struct2
struct2->struct1
struct1->struct0
struct0->struct3
nhead
}
{
rank="same";
nhead
}
}
```
:::danger
以清晰、明確，且流暢的漢語書寫。
:::
> [commit 2d33134](https://github.com/bclegend/lab0-c/commit/2d33134f3b8a6282b43e966ee4726dc0334b5882)
### q_descend / q_ascend
將佇列中的元素沿著下降/上升方向排列，若有為反規則的元素存在，則刪除該節點。
參考 [Leetcode](https://leetcode.com/problems/remove-nodes-from-linked-list/solutions/4152665/beats-99-using-iterative-approach/) 中的解法，但由於此實做使用的是雙向鏈結串列，而原題中使用的是線性單向鏈結串列，因此在函數的開頭需要先反轉鏈結串列。
:::danger
以清晰、明確，且流暢的漢語書寫。
:::
> [commit 0fcf63e](https://github.com/bclegend/lab0-c/commit/0fcf63ea96e2623da9d551d759bc65c56670e9ef)
> [commit 6520d3f](https://github.com/bclegend/lab0-c/commit/6520d3f93da89da89f7b9b8d0e2349dfb3102e3e)
### q_merge
:::danger
以清晰、明確，且流暢的漢語書寫。
:::
此函數的作用是將所有連結在一起的環狀鏈結串列合併到第一個節點中，同時將其餘的鏈結頭重新初始化以確保它們是空的。
> [commit 22103fa](https://github.com/bclegend/lab0-c/commit/22103faa7e9503de0a7506b8a5e0944ac701c0ce)
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
## 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並完成 q_sort
`list_sort.c` 為 linux 核心中實作的 merge sort 檔案
在執行 `list_sort` 函式時，在開始排序前會先將環狀雙向鏈結串列轉換為 `null-terminated` 的單向鏈結串列，並最後使用函式 `merge_final` 在最後一次的 merge 後轉換回原本的環狀雙向鏈結串列。
```c
__attribute__((nonnull(2,3,4)))
```
根據 [A GNU Manual](https://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Function-Attributes.html) 在函式定義時，檢查在位置 `(2,3,4)` 輸入的參數為 `non-null` 的指標。
```c
__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)
```
### q_sort
基於 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中的架構，將該架構修改符合 `queue.c` 的架構。
## 閱讀論文 〈[ Dude, is my code constant time? ](https://eprint.iacr.org/2016/1123.pdf)〉
## 利用 valgrind 分析記憶體使用情況
Sign in with Wallet
Connect another wallet