# 2023q1 Homework1 (lab0)
contributed by < [`bonianlee`](https://github.com/bonianlee) >
## 開發環境
```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
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 6
On-line CPU(s) list: 0-5
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
Stepping: 10
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 6000.00
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 9 MiB
NUMA node0 CPU(s): 0-5
```
## 開發過程
:::info
作業要求
- [x] q_new: 建立新的「空」佇列
- [x] q_free: 釋放佇列所佔用的記憶體
- [x] q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
- [x] q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
- [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
- [x] q_remove_tail: 在佇列尾端 (tail) 移去 (remove) 給定的節點
- [x] q_size: 計算目前佇列的節點總量
- [x] q_delete_mid: 移走佇列中間的節點並釋放之
- [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點並釋放它們
- [x] q_swap: 交換佇列中鄰近的節點
- [x] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- [x] q_reverseK: 以K個節點為小組 (K-group) 進行分組，並以反向順序重新排列小組內的鏈結串列
- [x] q_sort: 以遞增順序來排序鏈結串列的節點
- [x] q_descend: 若佇列中任意節點的右端存在嚴格大於 (strictly greater) 的值 (value) ，則將該節點移去 (remove)
- [x] q_merge: 將所有佇列合併 (merge) 成一個以遞增順序排列好的鏈結串列
:::
### 三個重要的結構體
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
```c
/* Linked list element */
typedef struct {
char *value;
struct list_head list;
} element_t;
```
```c
/* The context managing a chain of queues */
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
### q_new
建立新的「空」佇列，將其 linked list 的 ` next ` 與 ` prev ` 指向本身
- 實作流程
1. 使用 `malloc` 分配記憶體空間，並以 `head` 指向它
2. 如果空間分配失敗， `malloc` 會回傳 `NULL` 並被 `head` 指向，此時讓 `q_new` 回傳 `NULL`
3. 如果空間分配成功， `if (head)` 判斷式會執行，參考 `list.h` 中的函式 `INIT_LIST_HEAD` ，將其 linked list 的 ` next ` 與 ` prev ` 指向本身，做初始化的動作
- `list.h` 參考函式 `INIT_LIST_HEAD`
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
- 實作程式碼
```c
truct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head) {
INIT_LIST_HEAD(head);
return head;
}
return NULL;
}
```
### q_free
釋放所有由佇列佔用的記憶體空間
- 實作流程
1. 如果 `list_head *l` 不存在 (`NULL`) ，則不執行記憶體釋放
2. 如果 `list_head *l` 存在，參考 `list.h` 中的函式 `list_empty` ，判斷 linked list 開頭 (head) 有沒有接著其他的 node ，若有則使用 `q_remove_head` 與 `q_release_element` 來連續清除記憶體空間，最後再將「空」佇列 `l` 佔用的記憶體空間清除
- 實作程式碼
```c
void q_free(struct list_head *l)
{
if (l) {
while (!list_empty(l))
q_release_element(q_remove_head(l, NULL, 0));
free(l);
}
return;
}
```
:::danger
列出對應的 GitHub commit 超連結即可。
:notes: jserv
:::
<s>
:::spoiler `q_remove_head` 與 `q_release_element` 程式碼
- `q_remove_head`
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *element = list_first_entry(head, element_t, list);
if (bufsize && sp) {
strncpy(sp, element->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del_init(&element->list);
return element;
}
```
- `q_release_element`
```c
static inline void q_release_element(element_t *e)
{
test_free(e->value);
test_free(e);
}
```
:::
</s>
### q_insert_head
在佇列開頭 (head) 插入 (insert) 給定的新節點
- 實作流程
1. 使用 `malloc` 配置 `element_t` 的記憶體空間，若空間分配失敗，則回傳 `false`
2. 使用 `strlen` 計算引數 `s` 的字串長度 (包含空格) ，作為分配記憶體空間給 `element->value` 的依據，**如果 `value` 的記憶體配置失敗，記得要先將 `element` 的空間釋放掉，才可以回傳 `false`**
3. 使用 `strncpy` 將 `s` 複製給 `element->value` ，再參考 `list.h` 中的 `list_add` 將 `element` 插入 (insert) 到佇列開頭 (head)
- `list.h` 參考函式 `list_add`
```c
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
- 實作程式碼
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
int len = strlen(s);
element->value = malloc((len + 1) * sizeof(char));
if (!element->value) {
free(element);
return false;
}
strncpy(element->value, s, len);
*(element->value + len) = '\0';
list_add(&element->list, head);
return true;
}
```
### q_insert_tail
在佇列尾端 (tail) 插入 (insert) 給定的新節點
- 實作流程
重複 `q_insert_head` 實作流程的 1 , 2 步驟，惟步驟 3 改成使用 `list_add_tail` 將新的 `element` 插入 (insert) 到在佇列尾端 (tail)
- `list.h` 參考函式 `list_add_tail`
```c
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
- 實作程式碼
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
int len = strlen(s);
element->value = malloc((len + 1) * sizeof(char));
if (!element->value) {
free(element);
return false;
}
strncpy(element->value, s, len);
*(element->value + len) = '\0';
list_add_tail(&element->list, head);
return true;
}
```
### q_remove_head
在佇列開頭 (head) 移去 (remove) 給定的節點
- 實作流程
1. 如果 `head` 不存在，或者為「空」佇列，則回傳 `NULL`
2. 使用 `list_first_entry` 取得開頭的 element ，並使用 `strncpy` 將 `element->value` 複製給 `sp`
3. 使用 `list_del_init` 將開頭 (head) 的 element 移去 (remove)
- 實作程式碼
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *element = list_first_entry(head, element_t, list);
if (bufsize && sp) {
strncpy(sp, element->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del_init(&element->list);
return element;
}
```
:::spoiler `list_first_entry` 與 `list_del_init` 程式碼
- `lsit_first_entry`
```c
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
- `list_del_init`
```c
static inline void list_del_init(struct list_head *node)
{
list_del(node);
INIT_LIST_HEAD(node);
}
```
:::
### q_remove_tail
在佇列尾端 (tail) 移去 (remove) 給定的節點
- 實作流程
重複 `q_remove_head` 實作流程的步驟，惟步驟 2 的 `list_first_entry` 改成使用 `list_last_entry` ，取得尾端 (tail) 的 element
- `list.h` 中的 `list_last_entry`
```c
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
```
- 實作程式碼
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *element = list_last_entry(head, element_t, list);
if (bufsize && sp) {
strncpy(sp, element->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del_init(&element->list);
return element;
}
```
### q_size
計算目前佇列的節點總量
- 實作流程
1. 若 `head` 不存在，則傳回 0
2. 使用 `list.h` 中的巨集 `list_for_each` 逐一走訪鏈結串列，每存取到 `temp` 則遞增 `count`，最後回傳 `count`
:::warning
踩雷紀錄：迭代所使用的指標 `temp` 不要指向另外 `malloc` 的記憶體空間，因為若沒有 `free` 掉 `temp` 所佔用的記憶體空間，當 `$ make test` 執行重複呼叫 `q_size` 的 Trace 測試檔時，會導致 `q_free` 後仍有記憶體空間被佔用而沒被釋放掉，將 `temp` 改成指向 `NULL` ，則不會佔用到記憶體空間
:::
- 實作程式碼
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int count = 0;
struct list_head *temp = NULL;
list_for_each (temp, head)
count++;
return count;
}
```
### q_delete_mid
移走佇列中間的節點並釋放之
參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
- 思考方向
1. 龜兔賽跑 (Tortoise and Hare Algorithm):
使用兩個指標 `fast` 和 `slow` 指向 `head->next` ，其中 `fast` 的前進速度較快，一次走兩格節點，而 `slow` 的速度較慢，一次走一格節點，如此一來，只要當 `if (fast == head || fast->next == head)` 判斷式成立，指標 `slow` 所指向的節點即為佇列中間的節點，將之移走 (remove) 並且釋放掉 (release) 佔用的記憶體空間即可
2. 頭尾逼近
因為 `struct list_head` 是雙向的 linked list ，所以除了使用龜兔賽跑那樣同向的指標移動之外，還可以從頭跟尾互相接近的方式來找出佇列中間的節點位置，這種策略能夠減少指標移動的次數
- 實作流程 (採用頭尾逼近)
1. `head` 至少要接一個節點，才可以執行 delete mid 的動作，因此當 `if(!head || list_empty(head))` 判斷式滿足，則傳回 `false`
2. 建立兩個指標 `forward` 與 `backward` ， `forward` 指向 `head->next` ，而 `backward` 指向 `head->prev` ，我使用 `while` 迴圈來不斷移動指標，若滿足判斷式 `forward != backward && forward != backward->prev` ，則使 `forward = forward->next` 和 `backward = backward->prev` ，即互相靠近，並且每次只前進一個節點
3. 當發生以下兩種情形之一，代表已經找出佇列中間的節點了
- `forward == backward`
若佇列除了 `head` 外，連接了**奇數**個節點，則這種情形就會發生，此時 `forward` 和 `backward` 指向的節點即為佇列中間的節點
- `forward == backward->prev`
若佇列除了 `head` 外，連接了**偶數**個節點，則這種情形就會發生，此時 `backward` 指向的節點即為佇列中間的節點
4. 將步驟 3 的兩種情形用 `if` 判斷式做區別，即可找出佇列中間的節點，並做移去 (remove) 與釋放 (release) 記憶體的動作，這邊我使用 `list.h` 中的 `list_del` 與 `list_first_entry` ，再搭配 `q_release_element` 來完成
:::warning
踩雷紀錄： `list.h` 內的 `list_del` 做的事情只有將節點從 linked list 中孤立出來，並沒有做記憶體釋放的動作，因此我使用 `list.h` 中的 `list_first_entry` 找出佇列中間 element 的**前一個** element 的地址，再用 `q_release_element` 釋放掉佇列中間 element 佔用的記憶體空間
:::
- 實作程式碼
```diff
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *forward = head->next;
struct list_head *backward = head->prev;
if (!forward)
return false;
if (!backward)
return false;
while (forward != backward && forward != backward->prev) {
forward = forward->next;
backward = backward->prev;
}
if (forward == backward) {
+ element_t *element = list_first_entry(forward->prev, element_t, list);
list_del(forward);
+ q_release_element(element);
return true;
}
if (forward == backward->prev) {
+ element_t *element = list_first_entry(forward, element_t, list);
list_del(backward);
+ q_release_element(element);
return true;
}
return true;
}
```
### q_delete_dup
在已經排序的狀況，移走佇列中具備重複內容的節點並釋放它們
:::danger
注意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:notes: jserv
:::
:::success
遍歷：著重在「完全」走訪每個節點
本項 `q_delete_dup` 的實作目的是要找出特定內容的節點並釋放之，使用「遍歷」可能會令焦點模糊不清，已修正不當的詞彙描述，謝謝教授！
:cat2: ccasdqwe
:::
- 實作流程
1. 除了 `head` 指向的「空」節點外，至少還要連接兩個以上的節點才有可能發生重複內容的狀況，因此先做例外排除 `if (!head || list_empty(head) || list_is_singular(head))` ，若滿足判斷式就傳回 `false`
2. 宣告兩個新指標 `curr` 和 `safe` ，用來作為 `list_for_each_safe` 的引數，另外還宣告了布林變數 `diff` ，用來在之後的迭代過程判斷是否要繼續執行刪除的動作，將它初始化為 `false`
3. 使用 `list.h` 中的巨集 `list_for_each_safe` 來做 `curr` 與 `safe` 的<s>遍歷</s> --->逐一走訪，另外宣告一個指向 `curr->next` 的指標 `next` ，並宣告 `curr_entry` 與 `next_entry` 分別指向它們所屬的 element
4. 判斷式中 `!strcmp(curr_entry->value, next_entry->value)` 用來比較 `curr_entry` 與 `next_entry` 的 `value` 是否相同，若相同 `strcmp()` 會回傳 0 ，加入邏輯運算子 `!` 就會得到 `true` 的結果，如此一來，當 if 判斷式滿足，即代表兩個相鄰 element 的 `value` 重複出現，此時將 `curr` 移去 (remove) 並且釋放掉 (release) 它占用的記憶體空間，最後令 `diff = true` ，代表下一個 element 也是待釋放的目標
5. 當 `if ((next != head) && (!strcmp(curr_entry->value, next_entry->value)))` 不再滿足，且 `diff` 仍為 `true` ，代表 `curr` 所指向的 element 為連續重複內容的最末端 element ，將它釋放掉後，令 `diff = false` 代表已刪除完其中一組重複內容的 element
- 實作程式碼
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return false;
bool diff = false;
struct list_head *curr, *safe;
list_for_each_safe (curr, safe, head) {
struct list_head *next = curr->next;
element_t *curr_entry = list_entry(curr, element_t, list);
element_t *next_entry = list_entry(next, element_t, list);
if ((next != head) && (!strcmp(curr_entry->value, next_entry->value))) {
list_del(curr);
q_release_element(curr_entry);
diff = true;
} else if (diff) {
list_del(curr);
q_release_element(curr_entry);
diff = false;
}
}
return true;
}
```
### q_swap
交換佇列中鄰近的節點
- 實作流程
1. 例外處理
`q_swap` 是在進行節點兩兩對調的動作，因此佇列除了 `head` 指向的節點外，若沒有額外連接兩個以上的節點，就無法執行對調的動作，故先使用 `if` 判斷式做例外處理
2. 宣告指標
我宣告了兩個指標 `left` 與 `right` ，分別指向 `head->next` 跟 `head->next->next` ，方便之後進行節點對調的動作
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
rankdir=LR
e->1->2->3->4->5
5->4->3->2->1->e
5->e
e->5
h[shape=plaintext, label="head"];
l[shape=plaintext, label="left"];
r[shape=plaintext, label="right"];
h->e
l->1
r->2
}
```
3. `next` 與 `prev` 的重新指向
將 `head` 指向的節點改成與 2 號節點相鄰， 1 號節點接在 2 號節點的後面， 3 號節點再去與 1 號節點做 `next` 與 `prev` 的重新指向，最後成功對調 1 號與 2 號節點，此時 `right` 指向 2 號節點，而 `left` 則指向 1 號節點
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
rankdir=LR
e->2->1->3->4->5
5->4->3->1->2->e
5->e
e->5
h[shape=plaintext, label="head"];
l[shape=plaintext, label="left"];
r[shape=plaintext, label="right"];
h->e
l->1
r->2
}
```
4. 移動指標並重複步驟 3
使用判斷式判斷 `left->next` 跟 `left->next->next` 是否為 `head` 所指向的節點，若滿足其中一個，則跳出 `while` 迴圈，代表剩餘的節點數已經不足 2 個，無法進行對調的動作
如果 `left->next` 跟 `left->next->next` 都不是 `head` 所指向的節點，代表佇列尚未完全地完成兩兩對調，故移動指標並繼續進行步驟 3 的對調動作，直到跳出 `while` 迴圈的條件被滿足為止，最終結果如下圖
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
rankdir=LR
e->2->1->4->3->5
5->3->4->1->2->e
5->e
e->5
h[shape=plaintext, label="head"];
l[shape=plaintext, label="left"];
r[shape=plaintext, label="right"];
h->e
l->3
r->4
}
```
- 實作程式碼
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *left = head->next;
struct list_head *right = head->next->next;
head->next = right;
right->next->prev = left;
left->next = right->next;
right->next = left;
right->prev = head;
left->prev = right;
while (left->next != head) {
if (left->next->next != head) {
right = left->next->next;
right->prev->next = right->next;
right->next->prev = right->prev;
right->next = right->prev;
right->prev->prev = right;
right->prev = left;
left->next = right;
left = right->next;
} else
break;
}
return;
}
```
### q_reverse
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- 實作流程
1. 例外處理
`q_reverse` 的目的是要將佇列以反向順序重新排列 (除了 `head` 所指向的節點之外) ，因此至少要額外連接 2 個以上的節點，才可以執行此動作，故先排除掉可能發生的例外
2. 排列節點
`q_reverse` 可以使用 `list.h` 中的 `list_for_each_safe` 與 `list_move` 很簡單的達成，方法是透過 `list_for_each_safe` <s>遍歷</s> --->逐一走訪佇列，過程中用 `list_move` 不斷把節點移至開頭 (head) ，過程如下圖所示
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
rankdir=LR
e->1->2->3->4->5
5->4->3->2->1->e
5->e
e->5
h[shape=plaintext, label="head"];
h->e
{
rank=same
dummy[ shape = point, width = 0 ];
1
}
2:n->dummy:n[label="move to"]
}
```
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
rankdir=LR
e->2->1->3->4->5
5->4->3->1->2->e
5->e
e->5
h[shape=plaintext, label="head"];
h->e
{
rank=same
dummy[ shape = point, width = 0 ];
2
}
3:n->dummy:n[label="move to"]
}
```
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
rankdir=LR
e->3->2->1->4->5
5->4->1->2->3->e
5->e
e->5
h[shape=plaintext, label="head"];
h->e
{
rank=same
dummy[ shape = point, width = 0 ];
3
}
4:n->dummy:n[label="move to"]
}
```
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
rankdir=LR
e->4->3->2->1->5
5->1->2->3->4->e
5->e
e->5
h[shape=plaintext, label="head"];
h->e
{
rank=same
dummy[ shape = point, width = 0 ];
4
}
5:n->dummy:n[label="move to"]
}
```
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
rankdir=LR
e->5->4->3->2->1
1->2->3->4->5->e
1->e
e->1
h[shape=plaintext, label="head"];
h->e
}
```
- 實作程式碼
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node = NULL;
struct list_head *safe = NULL;
list_for_each_safe (node, safe, head)
list_move(node, head);
return;
}
```
### q_reverseK
以 k 個節點為小組 (k-group) 進行分組，並以反向順序重新排列小組內的鏈結串列
- 實作流程
1. 例外處理
`q_reverseK` 會進行反向順序的重新排列，因此除了 `head` 所指向的節點外，至少還要連接兩個以上的節點，才能執行排列的動作，故先做例外排除
同理， `k < 2` 無法執行排列的動作，因此也要做例外排除
2. `k == 2` 與 `k > 2` 的情形
`k == 2` 時 `q_reverseK` 的功能與 `q_swap` 相同，是在進行節點兩兩對調的動作，因此直接呼叫 `q_swap` 即可
若 `k > 2` ，我的作法是先數好總共要做幾次的反向順序重排，再由 `for` 迴圈執行相同的反向順序重排流程，其中變數 `count` 代表 `head` 以外的節點總數， `repeat_times` 則為反向順序重排流程所要執行的次數
3. k 個節點為小組進行反向順序重新排列
宣告指標 `sub_head` 與 `cut_pos` ，分別都指向 `head` ，它們之後會作為引數提供給 `list_cut_position` 跟 `list_splice_init` 使用
:::info
為了圖形美觀，環狀佇列頭尾相連的鏈結省略不畫
:::
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
d [label="Empty"]
rankdir=LR
e->1->2->3->4->5
5->4->3->2->1->e
h[shape=plaintext, label="head"];
s[shape=plaintext, label="sub_head"];
c[shape=plaintext, label="cut_pos"];
t[shape=plaintext, label="head_temp"];
h->e
s->e
c->e
t->d
}
```
假設 k = 3 ，則移動指標 `cut_pos` 至節點 3 的位置，並以 `list_cut_position` 將節點們移至另一個佇列
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
d [label="Empty"]
rankdir=LR
e->4->5
5->4->e
d->1->2->3
3->2->1->d
h[shape=plaintext, label="head"];
s[shape=plaintext, label="sub_head"];
c[shape=plaintext, label="cut_pos"];
t[shape=plaintext, label="head_temp"];
h->e
s->e
c->3
t->d
}
```
使用 `q_reverse` 將 `head_temp` 為頭端 (head) 的鏈結串列進行反向順序重新排列
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
d [label="Empty"]
rankdir=LR
e->4->5
5->4->e
d->3->2->1
1->2->3->d
h[shape=plaintext, label="head"];
s[shape=plaintext, label="sub_head"];
c[shape=plaintext, label="cut_pos"];
t[shape=plaintext, label="head_temp"];
h->e
s->e
c->3
t->d
}
```
使用 `list_splice_init` ，將 `head_temp` 為頭端 (head) 的鏈結串列除了 `head_temp` 指向的節點以外，其他的節點移回原佇列
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
d [label="Empty"]
rankdir=LR
e->3->2->1->4->5
5->4->1->2->3->e
h[shape=plaintext, label="head"];
s[shape=plaintext, label="sub_head"];
c[shape=plaintext, label="cut_pos"];
t[shape=plaintext, label="head_temp"];
h->e
s->e
c->3
t->d
}
```
最後移動指標 `sub_head` 與 `cut_pos` ，若 `( count / k ) > 1` ，則重複上述的流程
```graphviz
digraph{
node[shape=box];
e [label="Empty"]
d [label="Empty"]
rankdir=LR
e->3->2->1->4->5
5->4->1->2->3->e
h[shape=plaintext, label="head"];
s[shape=plaintext, label="sub_head"];
c[shape=plaintext, label="cut_pos"];
t[shape=plaintext, label="head_temp"];
h->e
s->1
c->1
t->d
}
```
- 實作程式碼
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
if (k < 2)
return;
else if (k == 2)
q_swap(head);
else {
int count = 0;
struct list_head *node = NULL;
list_for_each (node, head)
count++;
if (count < k)
return;
else {
int repeat_times = count / k;
LIST_HEAD(dummy);
struct list_head *head_temp = &dummy;
struct list_head *sub_head = head;
struct list_head *cut_pos = head;
for (int i = 0; i < repeat_times; i++) {
for (int j = 0; j < k; j++)
cut_pos = cut_pos->next;
list_cut_position(head_temp, sub_head, cut_pos);
q_reverse(head_temp);
list_splice_init(head_temp, sub_head);
for (int j = 0; j < k; j++)
sub_head = sub_head->next;
cut_pos = sub_head;
}
}
}
return;
}
```
### q_sort
以遞增順序來排序鏈結串列的節點
參考 < [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) > 與 < [Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort#Merge-Sort-%E8%88%87%E5%AE%83%E7%9A%84%E8%AE%8A%E5%8C%96) >
- 實作流程
1. 例外處理
除了 `head` 所指向的節點外，至少要連接 2 個以上的節點才能夠進行排序，因此做例外處理
2. Merge sort
參考 < [Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort#Merge-Sort-%E8%88%87%E5%AE%83%E7%9A%84%E8%AE%8A%E5%8C%96) > ，先將鏈結串列尾端 (tail) 的 `next` 指向 `NULL` ，即斷開 `next` 方向的環狀結構，再使用撰寫好的 `merge_sort` 進行遞增順序的排序
3. 重新連接環狀串列
將 `merge_sort` 過程中切斷的 linked list 指標重新指向
- 實作程式碼
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head *curr = head, *next = curr->next;
while (next) {
next->prev = curr;
curr = next;
next = next->next;
}
curr->next = head;
head->prev = curr;
}
```
### q_descend
若佇列中任意節點的右端存在嚴格大於 (strictly greater) 的值 (value) ，則將該節點移去 (remove)
參考 < [KHLee529](https://hackmd.io/@KHLee529/linux2023-lab0#q_descend) > 的實作
- 實作流程
1. 參考 < [KHLee529](https://hackmd.io/@KHLee529/linux2023-lab0#q_descend) > 同學的實作流程，他的作法是從佇列尾端 (tail) 往回比較 `element->value` 的大小，過程中不斷更新 (或者說紀錄) 擁有最大值的字串，並由 `max` 指向它，當碰到比 `max` 大小還要小的 `value` ，則將之移除 (remove and release)
2. 在迭代過程中使用整數變數 `total` 與 `n_del` 分別紀錄 element 總數和移除的 element 總數，最後傳回兩者之差，即為剩下的 element 總數
- 實作程式碼
```c
int q_descend(struct list_head *head)
{
char *max = NULL;
element_t *entry = NULL, *safe = NULL;
int total = 0, n_del = 0;
for (entry = list_entry(head->prev, element_t, list),
safe = list_entry(entry->list.prev, element_t, list);
&entry->list != head;
entry = safe, safe = list_entry(safe->list.prev, element_t, list)) {
total += 1;
if (!max || strcmp(entry->value, max) > 0) {
max = entry->value;
} else {
list_del(&entry->list);
q_release_element(entry);
n_del += 1;
}
}
return total - n_del;
}
```
### q_merge
將所有佇列合併 (merge) 成一個以遞增順序排列好的鏈結串列
參考 < [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_merge) > 的實作
- 實作流程
1. 使用 `list_for_each_entry_safe` 逐一走訪完每個節點，每當存取到 `c_cont` 就斷開部分連結，並以 `mergeTwoLists` 將 `sorted` 與 `c_cont->q->next` 合併
2. 迭代完成後須復原環狀 doubly linked list 結構，因為過程中各個 linked list 的 `prev` 被 `mergeTwoLists` 打亂了，只有 `next` 的指向是正確的
3. 使用 `list_splice` 將處理完的鏈結串列交還給 `head` 所屬的 element
- 實作程式碼
```c
int q_merge(struct list_head *head)
{
// reference to @chiangkd
if (!head)
return 0;
queue_contex_t *c_cont;
queue_contex_t *n_cont;
struct list_head *sorted = NULL;
list_for_each_entry_safe (c_cont, n_cont, head, chain) { // iterate context
c_cont->q->prev->next = NULL;
c_cont->q->prev = NULL;
sorted = mergeTwoLists(sorted, c_cont->q->next);
INIT_LIST_HEAD(c_cont->q); // reconnect the lists which are moved and
// merged to "sorted" list;
}
LIST_HEAD(tmp);
struct list_head *t = &tmp;
t->next = sorted;
struct list_head *c = t;
while (sorted) {
sorted->prev = c;
c = sorted;
sorted = sorted->next;
}
c->next = t;
t->prev = c;
int size = q_size(t); // store size before splice to main queue
list_splice(t, list_first_entry(head, queue_contex_t, chain)->q);
return size;
}
```
### 額外撰寫的函式
#### merge_sort
將佇列從中間切斷，產生的兩個子佇列再個別切斷中間的鏈結，以此種方式迭代，直到切成單個節點為止，再以 `mergeTwoLists` 進行遞增順序的合併
```c
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next) {
slow = slow->next;
}
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *left = merge_sort(head), *right = merge_sort(mid);
return mergeTwoLists(left, right);
}
```
#### mergeTwoLists
將兩個串列以遞增的順序合併在一起
```c
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node = NULL;
while (L1 && L2) {
element_t *L1_entry = list_entry(L1, element_t, list);
element_t *L2_entry = list_entry(L2, element_t, list);
node = strcmp(L1_entry->value, L2_entry->value) < 0 ? &L1 : &L2;
*ptr = *node;
ptr = &(*ptr)->next;
*node = (*node)->next;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
---
### 研讀 Linux 核心原始程式碼 < [`list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) >
:::info
作業要求
- [x] 研讀 Linux 核心原始程式碼的 lib/list_sort.c
- [x] 嘗試引入 Linux 核心原始程式碼到 lab0-c 專案
- [ ] 比較自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
:::
#### 研讀 Linux 核心原始程式碼的 lib/list_sort.c
參考 < [Risheng1128](https://hackmd.io/@Risheng/linux2022-lab0#%E7%A0%94%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC-list_sortc) > 的 < [研讀 Linux 核心原始程式碼 list_sort.c](https://hackmd.io/@Risheng/list_sort#%E7%A0%94%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC-list_sortc) >
研讀原始程式碼 `list_sort.c` 發現主要是由三個函式 `merge()` 、 `merge_final()` 及 `list_sort()` 組成，接著要個別分析它們的作用
在分析之前，先探討函式屬性 `__attribute__((nonnull()))` 的作用，因為三個函式在宣告函式原型時都擁有這個屬性，參考 < [` __attribute__((nonnull)) ` function attribute](https://developer.arm.com/documentation/dui0375/g/Compiler-specific-Features/--attribute----nonnull---function-attribute) > 可以得知 `nonnull` 的作用是當特定函式的引數為 `NULL` 時，編譯器會發出警告訊息
>This function attribute specifies function parameters that are not supposed to be null pointers. This enables the compiler to generate a warning on encountering such a parameter.
##### `merge()`
:::spoiler `merge()` 原始碼
```lua=
__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)
{
struct list_head *head, **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
:::
- 引數 `cmp` 分析
資料型態為 `list_cmp_func_t` ，根據 < [ linux/include/linux/list_sort.h ](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) > ，得知 `cmp` 是一個函式指標
```c
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,const struct list_head *, const struct list_head *);
```
`cmp` 指向回傳型態為 `int` 的函式，該函式的引數為 `void *` 和 2 個 `const struct list_head *`
- 宣告指標 ( line 5 )
宣告兩個指標，一個是指向 `struct list_head` 資料型態的指標 `head` ，另一個則是指向指標的指標 `tail` ，並且將它初始化指向 `head` 的地址
- for 迴圈 ( line 7 )
沒有設定判斷式，為無限迭代的迴圈，使用 `cmp` 來判斷下一個節點是要從 `a` 或者 `b` 來取得，假如 linked list `a` 已經沒有節點時，則接上 linked list `b` ，反之，假如 linked list `b` 已經沒有節點時，則接上 linked list `a`
##### `merge_final()`
將所有節點的 `prev` 接回前一個節點
```c
/* 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;
```
##### `list_sort()`
首先閱讀此函式的註解
```c
* 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.
*
* 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.
```
由此可知，此 merge sort 總是等到 linked list 的長度比例為 2 : 1 時才會開始進行合併的動作，舉例來說，有兩個大小為 $2^k$ 的 linked list 時， merge sort 不會直接進行合併，而是會等到有第三個 $2^k$ 時，才開始合併，並且是以 $2^k+1$ 和 $2^k$ 兩個 linked list 進行合併，滿足前述的 2 : 1
若以這種方式進行 merge sort ，假如被合併的 linked list 都可以被放進 cache 裡，則可以避免 [Cache thrashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science)) 的問題
#### 引入 Linux 核心原始程式碼到 lab0-c 專案
參考 < [komark06](https://hackmd.io/@komark06/SyCUIEYpj#%E5%BC%95%E5%85%A5-liblist_sortc) > 的方法引入原始程式碼，並且加入新的 `qtest` 命令 `list_sort`
:::info
實作流程
1. 將檔案 lib/list_sort.c 加進 lab0-c
2. 將位於其他檔案的巨集函式加進 `list_sort.h`
3. 在 `qtest.c` 新增函式 `cmp()`
4. 修改 `qtest.c` 的 `do_sort()` 函式
:::
首先要在 lab0-c 專案裡面建立 `lsit_sort.c` 及 `lsit_sort.h` ，前者包含 Linux 核心原始程式碼，而後者則是包含 lab0-c 所缺少的必要定義
以下為 `lsit_sort.h` 的內容
```c
#ifndef _LIST_SORT_H
#define _LIST_SORT_H
#include <stdint.h>
#include "list.h"
#define USE_LINUX_SORT 1
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif /* End of _LIST_SORT_H_ */
```
接著在 Makefile 中的 `OBJS` 新增 `list_sort.o`
```c
OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o\
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
linenoise.o web.o
```
在 `qtest.c` 上建立函式 `cmp()`
```c
__attribute__((nonnull(2,3)))
int cmp(void *priv, const struct list_head *list1, const struct list_head *list2)
{
element_t *list1_entry = list_entry(list1, element_t, list);
element_t *list2_entry = list_entry(list2, element_t, list);
return strcmp(list1_entry->value, list2_entry->value) < 0 ? 0 : 1;
}
```
---
## 運用 Valgrind 排除 qtest 實作時的記憶體錯誤
:::info
作業要求
- [x] 運用 Valgrind 排除 qtest 實作時的記憶體錯誤，並且使用 Massif 進行視覺化記憶體使用情況的分析
:::
當 `queue.c` 的實作基本上完成後，執行 `$ make valgrind` 進行動態分析，發現 `trace-13-malloc.cmd` 沒有通過測試，因此針對這個檔案進行分析，使用命令 `valgrind -q --leak-check=full ./qtest -f traces/trace-13-malloc.cmd` 對檔案 `trace-13-malloc.cmd` 進行測試
:::spoiler 測試結果
```c
# Test of malloc failure on new
WARNING: Malloc returning NULL
l = NULL
l = []
WARNING: Malloc returning NULL
l = NULL
l = []
l = []
l = []
==76976== 32 bytes in 1 blocks are still reachable in loss record 1 of 3
==76976== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76976== by 0x10CBCE: do_new (qtest.c:145)
==76976== by 0x10DDFA: interpret_cmda (console.c:181)
==76976== by 0x10E3AF: interpret_cmd (console.c:201)
==76976== by 0x10E7B0: cmd_select (console.c:610)
==76976== by 0x10F09C: run_console (console.c:705)
==76976== by 0x10D1EC: main (qtest.c:1223)
==76976==
==76976== 160 bytes in 5 blocks are possibly lost in loss record 2 of 3
==76976== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76976== by 0x10CBCE: do_new (qtest.c:145)
==76976== by 0x10DDFA: interpret_cmda (console.c:181)
==76976== by 0x10E3AF: interpret_cmd (console.c:201)
==76976== by 0x10E7B0: cmd_select (console.c:610)
==76976== by 0x10F09C: run_console (console.c:705)
==76976== by 0x10D1EC: main (qtest.c:1223)
==76976==
==76976== 224 bytes in 4 blocks are still reachable in loss record 3 of 3
==76976== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76976== by 0x10F110: test_malloc (harness.c:133)
==76976== by 0x10F515: q_new (queue.c:23)
==76976== by 0x10CC07: do_new (qtest.c:149)
==76976== by 0x10DDFA: interpret_cmda (console.c:181)
==76976== by 0x10E3AF: interpret_cmd (console.c:201)
==76976== by 0x10E7B0: cmd_select (console.c:610)
==76976== by 0x10F09C: run_console (console.c:705)
==76976== by 0x10D1EC: main (qtest.c:1223)
==76976==
```
:::
從錯誤訊息中發現有 still reachable 類型的記憶體遺失情形發生，且不是在 `queue.c` 實作中造成的，因此根據錯誤訊息的追隨路徑，開始檢查 `qtest.c` 中有無不合理的操作，但找了許久還是沒有頭緒，參考了 [KHLee529](https://hackmd.io/@KHLee529/linux2023-lab0#Valgrind) 同學的筆記後，才發現 `qtest.c` 中的 `q_quit` 敘述第一行為 `return true;` ，也就是說這個函式第一行以後的敘述毫無作用，很明顯語意上有誤
> still reachable: 程式結束時有尚未釋放的記憶體，且還被指標所指向，通常會發生在全域變數
:::spoiler `q_quit`
```diff
static bool q_quit(int argc, char *argv[])
{
- return true;
report(3, "Freeing queue");
if (current && current->size > BIG_LIST_SIZE)
set_cautious_mode(false);
if (exception_setup(true)) {
struct list_head *cur = chain.head.next;
while (chain.size > 0) {
queue_contex_t *qctx, *tmp;
tmp = qctx = list_entry(cur, queue_contex_t, chain);
cur = cur->next;
q_free(qctx->q);
free(tmp);
chain.size--;
}
}
exception_cancel();
set_cautious_mode(true);
size_t bcnt = allocation_check();
if (bcnt > 0) {
report(1, "ERROR: Freed queue, but %lu blocks are still allocated",
bcnt);
return false;
}
return true;
}
```
:::
當我將錯誤的語意清除後重新執行 `valgrind -q --leak-check=full ./qtest -f traces/trace-13-malloc.cmd` ，先前 still reachable 類型的記憶體遺失情形也隨之解決了
:::spoiler 測試結果
```c
# Test of malloc failure on new
l = []
l = []
WARNING: Malloc returning NULL
l = NULL
WARNING: Malloc returning NULL
l = NULL
WARNING: Malloc returning NULL
l = NULL
l = []
Freeing queue
```
:::
使用圖形化工具 < [Massif](https://valgrind.org/docs/manual/ms-manual.html) > 來查看執行 `trace-13-malloc.cmd` 時記憶體的分配狀況，輸入命令 `valgrind -v --tool=massif ./qtest -f traces/trace-13-malloc.cmd` ，產生了檔案 `massif.out.85066` ，接著使用 massif-visualizer 打開檔案，輸入命令 `massif-visualizer ./massif.out.85066` ，最終結果為下圖
從動態記憶體配置的圖形發現，佔用的記憶體最終都<s>歸零</s> --->歸還了，可見 `qtest` 在 `trace-13-malloc.cmd` 執行結束後，過程中佔用的記憶體都已成功被釋放
:::warning
注意用語，請查詢辭典，理解「歸零」的意涵是否可對應到本例 malloc/free 操作。
:notes: jserv
:::
:::success
歸零：將儀表或計量裝置的指示值調至零點或起點
本例的操作是對記憶體進行分配與釋放 (歸還) ，記憶體總量沒有減少，因此不適合用「歸零」來描述，已修正錯誤的詞彙使用，謝謝教授！
:cat2: ccasdqwe
:::
---
Sign in with Wallet
Connect another wallet