---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `YiChianLin` >
> [作業說明](https://hackmd.io/@sysprog/linux2022-lab0)
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.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): 16
On-line CPU(s) list: 0-15
Thread(s) per socket: 2
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
model: 158
Model name: Intel(R) Core(TM) i9-9900KF CPU @ 3.60GHz
Stepping: 12
CPU MHz: 3600.000
CPU max MHz: 5000.0000
CPU min MHz: 800.0000
BogoMIPS: 7200.00
L1d cache: 256 KiB
L1i cache: 256 KiB
L2 cache: 2 MiB
L3 cache: 16 MiB
NUMA node0 CPU(s): 0-15
```
## 作業要求
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供界面([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
* `q_new` : 建立新的「空」佇列;
* `q_free` : 釋放佇列所佔用的記憶體;
* `q_insert_head` : 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* `q_insert_tail` : 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* `q_remove_head` : 在佇列開頭 (head) 移去 (remove) 給定的節點;
* `q_release_element` : 釋放特定節點的記憶體空間;
* `q_size` : 計算目前佇列的節點總量;
* `q_delete_mid` : 移走佇列中間的節點;
* `q_delete_dup` : 在已經排序的狀況，移走佇列中具備重複內容的節點;
* `q_swap` : 交換佇列中鄰近的節點;
* `q_reverse` : 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
* `q_sort` : 以遞增順序來排序鏈結串列的節點;
## 開發過程
### q_new
* 函式功能:
* 建立新的「空」佇列
* 程式運作
1.重新建立新的節點，使用 `malloc` 新配置記憶體空間
2.使用 [lish.c](https://github.com/torvalds/linux/blob/master/include/linux/list.h) API 中的 `INIT_LIST_HEAD` 將新建立的 `list_head` 連結成環狀的結構
```c
struct list_head *q_new()
{
struct list_head *new_head = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(new_head);
return new_head;
}
```
* INIT_LIST_HEAD 函式
將未形成 `circlar doubly-linked list` 的 `head` 節點串接再一起
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
* 但是發現並沒有考慮到 `malloc` 會失敗的問題，在 `trace-12-malloc.cmd` 會產生 [Segmentation fault](https://zh.wikipedia.org/wiki/%E8%A8%98%E6%86%B6%E9%AB%94%E5%8D%80%E6%AE%B5%E9%8C%AF%E8%AA%A4) 的問題產生，所以必須考慮到 `malloc` 失敗的情形，將程式進行修改
* `trace-12-malloc.cmd` 文件內容 `option malloc 50` 敘述會將 `malloc` 的失敗機率提升至 50%
```
# Test of malloc failure on new
option fail 10
option malloc 50
new
new
new
new
new
new
```
* 原程式的報錯內容
```shell
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
* 程式修改
1.確認欲新增的 `head` 是否 `malloc` 成功
2.若成功建立新的 `head` 節點並回傳，若失敗則釋放配置失敗的空間並為傳 `NULL`
```c
struct list_head *q_new()
{
struct list_head *new_head = malloc(sizeof(struct list_head));
if (new_head) {
INIT_LIST_HEAD(new_head);
return new_head;
}
free(new_head);
return NULL;
}
```
### q_free
* 函式功能:
* 釋放佇列所佔用的記憶體
* 思考方式:
* 先判斷 queue 的 `head` 是否為 `NULL` (注意: `empty` 不等於 `NULL` )
* 參考:[作業說明](https://hackmd.io/@sysprog/linux2022-lab0), 內文提到:
* `NULL` 佇列 : 是指標值為 `NULL`;
* 「空」(empty) 的佇列是指向有效結構，但開頭 ( `head` ) 的值為 `NULL`;
* 使用暫時的指標走訪每個節點
* 使用 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的 `list_entry` 可找出每個 linked list 資料的起始位址
* 使用指標 `ptr (element_t *ptr)` 取得節點資料的位址
* 使用 `queue.c` 的 `q_release_element()` 將結構 `element_t` 的節點裡的 `*value` 與 linked list 的指標釋放，參考以下的 `q_release_element()` 程式碼
* 所有 `node` 釋放後，再將 linked list 的 `head` 釋放
* 程式運作:
1.先判斷 linked list 的 `head` (也就是引數中的 `list_head *l`) 是否為 `NULL`（注意 : 若是 `empty` 則判斷式不成立)
2.使用 `tmp` 指標走訪每個節點
3.建立 `ptr (element_t *ptr)` 取得節點資料的位址
4.`tmp` 指標走訪至下一個點
5.`ptr` 取得節點資料後再使用 `q_release_element()` 釋放記憶體空間
6.直到每個 `node` 釋放結束最後將 `l` (注意 : `l` 為沒有 value 的指標) 釋放
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *tmp = l->next;
while (tmp != l) {
element_t *ptr = list_entry(tmp, element_t, list);
tmp = tmp->next;
q_release_element(ptr);
}
free(l);
}
```
* 程式可改進之處
* 多使用 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中的 `API` 進行實作
將 `container_of` 更換成 `list_entry` ， 雖然兩個函式功能相同，但是在協作上的考量上要能有統一的規範!
:::danger
除了列出程式碼，你應該說明程式運作和後續可改進之處。
:notes: jserv
:::
q_release_element()
* 函式說明:
將 `element_t` 的資料釋放，分別有 `element_t` 內部的 `char` 與 `element_t` 本身的指標
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### q_insert_head
* 函式功能:
* 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
* 思考方式:
* 重新建立新的 `node` ，將資料新增且配置記憶體
* 透過 `list_add` 函式進行新增 `node`
* 程式運作方式
1.先判斷傳入的 `head` 是否為 `NULL` (如果是 `empty` 情況也可以執行)
2.配置 `element_t *new` 的記憶體，並也配置資料的記憶體 `char* new->value` 長度為 `strlen(s)`
3.使用 `strncpy()` 將 `s` 複製到 `new->value` 中(***注意***: 不能使用 `strcpy()` 這個函式是[不安全的函式](https://stackoverflow.com/questions/26558197/unsafe-c-functions-and-the-replacement)不可使用)
4.最後使用 `list_add()` 將新 `node` 加入 `list` 中
:::success
> [ISO/IEC 9899:1999](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
> 7.21.2.4 The strncpy function
> `char *strncpy(char * restrict s1, const char * restrict s2, size_t n);`
>
> Description : The strncpy function copies not more than n characters (characters that followanull character are not copied) from the array pointed to by s2 to the array pointed to by s1.
> If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.
> 可以得知函式的使用方式為，將 `s2` 字符複製 `n` 個數量到 `s1` 中
:::
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
} else {
element_t *new = malloc(sizeof(element_t));
new->value = malloc(strlen(s) * sizeof(char));
strncpy(new->value, s, strlen(s));
list_add(&new->list, head);
}
return true;
}
```
* `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;
}
```
* 程式運作:
1. `*next = head->next;` ，將 `next` 指向 `head->next` 也就是 `A`
```graphviz
digraph graphname{
node[shape=box]
next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=new_node]
}
next->A
A->B->head->A
A->head->B->A
D->D
}
```
2. `next->prev = node;` ，將 `A->prev` 指向 `new_node`
```graphviz
digraph graphname{
node[shape=box]
next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=new_node]
}
next->A
A->B->head->A
A->D
head->B->A
D->D
}
```
3. `node->next = next;` ，將 `new_node->next` 指向 `A`
```graphviz
digraph graphname{
node[shape=box]
next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=new_node]
}
next->A
A->B->head->A
A->D->A
head->B->A
D->D
}
```
4. `node->prev = head;` ，將 `new_node->->prev` 指向 `head` 也就是指回 `A` 的前一個
```graphviz
digraph graphname{
node[shape=box]
next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=new_node]
}
next->A
A->B->head->A
A->D->A
head->B->A
D->head
}
```
5. `head->next = node;` ，將 `head->next` 指回 `new_node` 完成 `circular doubly-linked list` 新加入一個 `node` 的操作
```graphviz
digraph graphname{
node[shape=box]
next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=new_node]
}
next->A
A->B->head
A->D->A
head->D
D->head->B->A
}
```
* 發現程式碼的問題:
* 尚未確認 `s` 是否為 `NULL`
* `new->value` 在配置記憶體的時候要多一個空間給結尾符號 `\0`
* 需要釋放 `malloc` 失敗的 `node` 指標
在測試 `trace-12-malloc.cmd` 時，發現上述程式碼會有問題，使用 `malloc` 失敗的指標佔用記憶體，需要將未配置成功的指標釋放，且將輸入的字串加入結尾符號 `\0`，因此經過調整
:::danger
注意共筆書寫規範：中英文間用一個半形空白字元區隔
:notes: jserv
:::
> 好的，學生會再多注意共筆書寫規範![name=YiChianLin]
* 根據發現的問題進行修改:
* `if (new && s)` 判斷 `new` 是否能不能 `malloc` 成功，以及判斷 `s` 資料是否為 `NULL`
* 需要在複製的資料加上結尾符號，所以配置記憶體更改為 `new->value = malloc((strlen(s) + 1) * sizeof(char))`
* `*(new->value + strlen(s)) = '\0';`
* 最後要透過 `free(new)` 將有可能配置失敗的記憶體釋放
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new = malloc(sizeof(element_t));
if (new && s) {
new->value = malloc((strlen(s) + 1) * sizeof(char));
if (new->value) {
strncpy(new->value, s, strlen(s));
*(new->value + strlen(s)) = '\0';
list_add(&new->list, head);
return true;
}
}
free(new);
return false;
}
```
### q_insert_tail
* 函式功能:
* 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
* 程式運作的方式與 `q_insert_tail()` 相似
* 使用 `list_add_tail()` 函數
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
} else {
element_t *new = malloc(sizeof(element_t));
new->value = malloc(strlen(s) * sizeof(char));
strncpy(new->value, s, strlen(s));
list_add_tail(&new->list, head);
}
return true;
}
```
* `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;
}
```
* 程式運作方式與 `list_add` 相似，差別在於對 `head->prev` 操作
* 加入前
```graphviz
digraph graphname{
node[shape=box]
prev[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=new_node]
}
prev->B
A->B->head->A
A->head->B->A
D->D
}
```
* 完成操作後
```graphviz
digraph graphname{
node[shape=box]
prev[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=new_node]
A[label=A]
B[label=B]
D[label=head]
}
prev->B
A->B->head
A->D->A
head->D
D->head->B->A
}
```
同理在 `q_insert_tail()` 發現與 `q_inset_head()` 一樣的問題，並加以修改
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new = malloc(sizeof(element_t));
if (new &&s) {
new->value = malloc((strlen(s) + 1) * sizeof(char));
if (new->value) {
strncpy(new->value, s, strlen(s));
*(new->value + strlen(s)) = '\0';
list_add_tail(&new->list, head);
return true;
}
}
free(new);
return false;
}
```
### q_removed_head
* 函式功能:
* 在佇列開頭 (head) 移去 (remove) 給定的節點;
* 思考方式:
* 透過 `list_entry` 函式進行找出節點 `element_t` 的資料
* 移除 `head->next` (注意:移除 `remove` 不等於刪除 `delete` )
* 確認 `bufsize` 與欲將移除的資料比較長度
* 將資料複製給 `sp`
* 程式運作方式:
1. 先判斷傳入的 `linked list` 是否為 `NULL` 或是 `empty` (只剩下單一的 `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 *rm_ele = list_entry(head->next, element_t, list);
list_del(head->next);
int char_len = strlen(rm_ele->value) < (bufsize - 1) ? strlen(rm_ele->value)
: (bufsize - 1);
if (sp)
{
strncpy(sp, rm_ele->value, char_len);
*(sp + char_len) = '\0';
return rm_ele;
}
return rm_ele;
}
```
* 實作後發現誤解題目意思，原先認為在複製字串長度需要考慮到 `bufsize` 與 `rm_ele->value` 之長度，應修正為將 `bufsize - 1` 字串長度複製給 `sp` 並且在字串的尾端加入結尾符 `\0`，所以將其改寫
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *rm_ele = list_entry(head->next, element_t, list);
list_del(head->next);
if (sp) {
strncpy(sp, rm_ele->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return rm_ele;
}
```
* 程式運作前
```graphviz
digraph graphname{
node[shape=box]
head_next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=remove_head]
}
head_next->D
A->B->head
A->D->A
head->D
D->head->B->A
}
```
* 程式運作後
```graphviz
digraph graphname{
node[shape=box]
head_next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=remove_head]
}
head_next->D
D->D
A->B->head
head->A
head->B->A->head
}
```
### q_removed_tail
* 函式功能:
* 在佇列尾端 (tail) 移去 (remove) 給定的節點;
* 思考方式:
* 與 `q_removed_head` 相似，相異之處在於移除目標改為 `head->prev`
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *rm_ele = container_of(head->prev, element_t, list);
list_del(head->prev);
int char_len = strlen(rm_ele->value) < (bufsize - 1) ? strlen(rm_ele->value)
: (bufsize - 1);
if (sp)
{
strncpy(sp, rm_ele->value, char_len);
*(sp + char_len) = '\0';
return rm_ele;
}
return rm_ele;
}
```
* 與 `q_removed_head` 遇到的問題相同，將程式加以修正
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *rm_ele = list_entry(head->prev, element_t, list);
list_del(head->prev);
if (sp) {
strncpy(sp, rm_ele->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return rm_ele;
}
```
* 程式運作前
```graphviz
digraph graphname{
node[shape=box]
head_prev[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=B]
B[label=A]
D[label=remove_tail]
}
head_prev->D
A->B->head
A->D->A
head->D
D->head->B->A
}
```
* 程式運作後
```graphviz
digraph graphname{
node[shape=box]
head_prev[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=B]
B[label=A]
D[label=remove_tail]
}
head_prev->D
D->D
A->B->head
head->A
head->B->A->head
}
```
### q_size
* 程式功能:
* 計算目前佇列的節點總量;
* 使用 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中的 `list_for_each` 可走訪 `linked list` 的每一個點進行長度的計算
```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;
}
```
* `list_for_each` 函式
在 `for` 迴圈透過 `node` 指標指向 `head->next` 也就是第一個元素，所以在迭代的次數為"linked list 的元素個數"，並不包含空資料的 `head`
```c
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
### q_delete_mid
* 參考 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
* 程式功能:
* 移走佇列中間的節點;
* 思考方式:
* 先找出移動到中間點的次數
* `head` 走訪到該次數的節點(中間點)
* 移除中間節點
* 釋放掉中間節點的資料
* 程式運作
1. 判斷 `linked list` 是否存在或是為單一的 `head`，若是其中一條件符合則會回傳 `false`
2. 利用 `q_size` 函式先得出，中間元素的位置，且要判斷偶數或是奇數
3. `for` 迴圈走放置中間點
4. 使用 `list_del` 將中間點移除( `remove` )
5. 使用 `list_entry` 取得 `element_t` 的指標
6. 最後使用 `q_release_element` ，先將 `element_t->value` (內部資料)釋放，再將 `element_t` 本身的指標也釋放
* 程式運作前:
```graphviz
digraph graphname{
node[shape=box]
head_next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
head_next
}
```
* 走訪至中間點，走訪到 `C` 節點
```graphviz
digraph graphname{
node[shape=box]
head_next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
head_next->C
}
```
* 移除中間點 `C`
```graphviz
digraph graphname{
node[shape=box]
head_next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=C]
D[label=D]
}
head->A->B->D->head
head_next->C->C
}
```
* 釋放 `C` 的資料
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=D]
}
head->A->B->D->head
}
```
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
int mid_pos =
q_size(head) % 2 == 0 ? q_size(head) / 2 : q_size(head) / 2 + 1;
for (int i = 0; i < mid_pos; i++)
head = head->next;
list_del(head);
element_t *mid_ele = list_entry(head, element_t, list);
q_release_element(mid_ele);
return true;
}
```
* 程式改進之處:
* 不使用 `q_size` 函式，而是利用兩個不同速率的指標找到中間點，可增加程式的效率
:::success
找尋中間的節點方式好比龜兔賽跑的形式，當兔子到終點的時候，烏龜只跑了一半
:::
* 將程式改寫
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *first = head->next;
struct list_head *second = head->next;
while (first != head && first->next != head) {
first = first->next->next;
second = second->next;
}
list_del(second);
element_t *mid_ele = list_entry(second, element_t, list);
q_release_element(mid_ele);
return true;
}
```
* 程式運作先將 `first` 、 `second` 指標指向 `head->next`
```c
struct list_head *first = head->next;
struct list_head *second = head->next;
```
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
second[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
first->A
second->A
}
```
* `first != head && first->next != head` 直到 `first` 跑完整個 `linked list` ， 所以 `second` 就會落在中間點的位置
* `while` 迴圈中 `first` 每次都移動兩個節點， `second` 每次移動一個節點
```c
first = first->next->next;
second = second->next;
```
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
second[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
first->C
second->B
}
```
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
second[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
first->head
second->C
}
```
* 移除中間點 `C`
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
second[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=C]
D[label=D]
}
head->A->B->D->head
first->head
second->C->C
}
```
* 釋放 `C` 的資料
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=D]
}
head->A->B->D->head
first->head
}
```
### q_delete_dup
* 參考 [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* 程式功能
* 在已經排序的狀況，移走佇列中具備重複內容的節點;
* 思考方式
* 走訪每一個節點確認當前節點的下一個節點是否是重複的
* 若有重複，則記錄重複點的起始位置，將下一個節點先移除( `remove` )再刪除( `delete` )，直到下一個點不是重複，將起始位置的節點刪除
* 若沒有重複，就會不斷的走訪下一個點，直到回到 `head`
* 程式運作
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_is_singular(head))
return false;
struct list_head *tmp = head->next;
struct list_head *if_dup = NULL;
while (tmp != head) {
element_t *ele_dup = list_entry(tmp, element_t, list);
element_t *ele_dup_next = list_entry(tmp->next, element_t, list);
while (!strcmp(ele_dup->value, ele_dup_next->value)) {
if_dup = tmp;
list_del(tmp->next);
q_release_element(ele_dup_next);
ele_dup_next = list_entry(tmp->next, element_t, list);
if (tmp->next == head)
break;
}
tmp = tmp->next;
if (if_dup) {
element_t *ele_dup_a = list_entry(if_dup, element_t, list);
list_del(if_dup);
q_release_element(ele_dup_a);
if_dup = NULL;
}
if (tmp->next == head)
break;
}
return true;
}
```
用以下簡單的範例解釋:
1. `tmp` 指標指到第一個 `node` ， `tmp->next` 指標指到第二個 `node` ，利用判斷是否有重複元素的指標 `if_dup` 指向 `NULL`
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext,fontcolor=red]
tmp_next[shape=plaintext,fontcolor=red]
if_dup[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=B]
D[label=D]
}
head->A->B->C->D->head
tmp->A tmp_next->B
if_dup->NULL
}
```
2. `tmp` 指標指到 `A` ， `tmp->next` 指標指到 `B` 所以兩個元素的值不同，因此兩個指標走放置下一個節點，由於 `tmp` 與 `tmp->next` 的元素相同，使 `if_dup` 記住 `tmp` 的位置
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext,fontcolor=red]
tmp_next[shape=plaintext,fontcolor=red]
if_dup[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=B]
D[label=D]
}
head->A->B->C->D->head
tmp->B tmp_next->C
if_dup->B
}
```
3. 將 `tmp->next` 也就是重複的元素 `remove` 與 `delete`
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext,fontcolor=red]
tmp_next[shape=plaintext,fontcolor=red]
if_dup[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
D[label=D]
}
head->A->B->D->head
tmp->B tmp_next->D
if_dup->B
}
```
4. `tmp` 走訪至下一個節點，將有重複點的起始位置 `if_dup` 節點刪除，重複進行上述動作直到把具有重複的節點都刪除
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext,fontcolor=red]
tmp_next[shape=plaintext,fontcolor=red]
if_dup[shape=plaintext,fontcolor=blue]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
D[label=D]
}
head->A->D->head
tmp->D tmp_next->head
if_dup->NULL
}
```
### q_swap
* [Leetcode swap node](https://leetcode.com/problems/swap-nodes-in-pairs/)
* 程式功能:
* 交換佇列中鄰近的節點;
* 思考方式:
* 不直接改變 `linked list` 的連接串列，而是對 `element_t` 內部的 `element_t->value` 進行交換
* 走訪的次數為 `linked list` 長度的一半次數
```c
void q_swap(struct list_head *head)
{
if (!head || list_is_singular(head) || list_empty(head))
return;
struct list_head *forward = head->next;
struct list_head *forward_next = forward->next;
char *tmp;
int size = q_size(head) / 2;
for (int i = 0; i < size; i++) {
element_t *ele_first = list_entry(forward, element_t, list);
element_t *ele_second = list_entry(forward_next, element_t, list);
tmp = ele_first->value;
ele_first->value = ele_second->value;
ele_second->value = tmp;
forward = forward_next->next;
forward_next = forward->next;
}
```
* 程式運作:
1. 由 `forward` 與 `forward->next` 每次指向鄰近的兩個節點
```graphviz
digraph graphname{
node[shape=box]
forward[shape=plaintext,fontcolor=red]
forward_next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A]
B[label=B]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
forward->A forward_next->B
}
```
2. 使用 `list_entry` 取得 `element_t` 內部 `value` 值，再透過暫存的 `char *tmp` ，將資料進行交換
```graphviz
digraph graphname{
node[shape=box]
forward[shape=plaintext,fontcolor=black]
forward_next[shape=plaintext,fontcolor=black]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=B,fontcolor=red]
B[label=A,fontcolor=red]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
forward->A forward_next->B
}
```
3. 交換後 `forward` 與 `forward->next` 兩個指標前進到下兩個元素進行交換直到走訪全部的 `linked list`
```graphviz
digraph graphname{
node[shape=box]
forward[shape=plaintext,fontcolor=red]
forward_next[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=B,fontcolor=black]
B[label=A,fontcolor=black]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
forward->C forward_next->D
}
```
:::danger
與 [StevenChou43](https://hackmd.io/@StevenChou43) 和 [Risheng1128](https://hackmd.io/@Risheng) 同學討論後，發現這樣資料的交換方式對記憶體的處理會造成負擔，需要多配置暫存的記憶體空間，造成效率不彰的問題
:::
* 改善方法:
* 用兩個指標指向前兩個節點
* 移除前面的節點再加入至後面的節點
* 程式運作:
主要透過 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中的 `list_del` 與 `list_add` 進行操作
```c
void q_swap(struct list_head *head)
{
for (struct list_head *first = head->next,struct list_head *second = first->next;; !(first == head || second == head);
second = first->next->next, first = first->next) {
list_del(first);
list_add(first, second);
}
}
```
1. 一開始由 `first` 與 `second` 指標指到前兩個元素
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
second[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A,fontcolor=black]
B[label=B,fontcolor=black]
C[label=C]
D[label=D]
}
head->A->B->C->D->head
first->A second->B
}
```
2. 移除 `first` 指標的元素 `A`
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
second[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A,fontcolor=black]
B[label=B,fontcolor=black]
C[label=C]
D[label=D]
}
head->B->C->D->head
first->A second->B
}
```
3. `first` 指標移除後，再從 `second` 指標的位置使用 `list_add` 加入 `A`
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
second[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A,fontcolor=black]
B[label=B,fontcolor=black]
C[label=C]
D[label=D]
}
head->B->A->C->D->head
first->A second->B
}
```
4. `second = first->next` `second` 指到 `C` ， `first = first->next->next` `first` 移動兩個節點到 `second` 前面一個節點，持續上述的流程直到所有的節點交換完成
```graphviz
digraph graphname{
node[shape=box]
first[shape=plaintext,fontcolor=red]
second[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
head[label=head]
A[label=A,fontcolor=black]
B[label=B,fontcolor=black]
C[label=C]
D[label=D]
}
head->B->A->C->D->head
first->A second->B
}
```
### q_reverse
* 程式功能:
* 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
* 舉例: `head -> 1 -> 2 -> 3 -> 4 -> head` 經反轉後， `head -> 4 -> 3 -> 2 -> 1 -> head`
* 思考方式:
* 使用三個指標進行操作，分別為 `prev` 、 `cur` 、 `next`
* 由 `cur` 指標走訪至每個節點改變其 `cur->next` 、 `cur->prev` 指向的位置，分別指向 `prev` 與 `next` 指標的位置
* 最後三個節點一起移動直到走訪完整個 `linked list`
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *prev = head->prev;
struct list_head *cur = head;
struct list_head *next = cur->next;
do {
cur->next = prev;
cur->prev = next;
prev = cur;
cur = next;
next = next->next;
} while (cur != head);
}
```
* 程式運作
1. 初始狀態:
```graphviz
digraph graphname{
prev[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=red]
node[shape=record];
rankdir=LR
{
rankdir = LR
head[label="<f0> prev|<f1> head|<f2> next"]
A[label="<f0> prev|<f1> A|<f2> next"]
B[label="<f0> prev|<f1> B|<f2> next"]
C[label="<f0> prev|<f1> C|<f2> next"]
}
cur->head:f1 prev->C:f1 next->A:f1
head:f2->A:f1 A:f2->B:f1 B:f2->C:f1 C:f2->head:f1
head:f0->C:f1 A:f0->head:f1 B:f0->A:f1 C:f0->B:f1
}
```
2. 更改 `cur->next` 從 `A` 改指到 `C` ， `cur->prev` ，從 `C` 改指到 `A`
```graphviz
digraph graphname{
prev[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=red]
node[shape=record];
rankdir=LR
{
rankdir = LR
head[label="<f0> prev|<f1> head|<f2> next"]
A[label="<f0> prev|<f1> A|<f2> next"]
B[label="<f0> prev|<f1> B|<f2> next"]
C[label="<f0> prev|<f1> C|<f2> next"]
}
cur->head:f1 prev->C:f1 next->A:f1
head:f2->C:f1 A:f2->B:f1 B:f2->C:f1 C:f2->head:f1
head:f0->A:f1 A:f0->head:f1 B:f0->A:f1 C:f0->B:f1
}
```
3. 更改後三個指標皆向前走訪， `pre` 走訪至 `cur` 的位置，`cur` 走訪至 `next` 的位置， `next` 走訪至 `next->next` 位置，完成一次的循環動作，直到將所有節點的反轉完成
```graphviz
digraph graphname{
prev[shape=plaintext,fontcolor=red]
cur[shape=plaintext,fontcolor=red]
next[shape=plaintext,fontcolor=red]
node[shape=record];
rankdir=LR
{
rankdir = LR
head[label="<f0> prev|<f1> head|<f2> next"]
A[label="<f0> prev|<f1> A|<f2> next"]
B[label="<f0> prev|<f1> B|<f2> next"]
C[label="<f0> prev|<f1> C|<f2> next"]
}
cur->A:f1 prev->head:f1 next->B:f1
head:f2->C:f1 A:f2->B:f1 B:f2->C:f1 C:f2->head:f1
head:f0->A:f1 A:f0->head:f1 B:f0->A:f1 C:f0->B:f1
}
```
### q_sort
* 程式功能:
* 以遞增順序來排序鏈結串列的節點
* 思考方式:
* 使用 [merge sort 演算法](https://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)，使用參考連結的圖片解說運作模式
* 將整串資料進行兩兩分割
* 直到全部的資料為單一資料後，再進行比較、排序
* 所得到的[時間複雜度](https://en.wikipedia.org/wiki/Time_complexity)為 ( `NlogN` )
* 分割兩串 `linked list` 自定義函式 `sep_list`
* 程式運作
* 找尋的方式參考至 [SteveChou同學](https://hackmd.io/@StevenChou43/linux2022_lab0) 開發紀錄找尋中間點的方式
1. 首先，由以下程式碼 6 ~ 11 行中，將兩指標 `fast` 與 `mid` 從 `linked list` 的頭尾兩端進行走訪，直到兩個指標相遇或是中間隔一個節點的時候，方可找到中間節點的位置
2. 以 `head` 與 `mid` 中間點分別為兩串資料的起使節點，設定為`left` 與 `right`
3. 在程式碼 17 ~ 25 行中，將 `linked list` 分割成兩段，分割方式使用圖解的方式說明:
* 初始狀態
```graphviz
digraph graphname{
node_tmp[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=red]
right[shape=plaintext,fontcolor=red]
node[shape=record];
rankdir=LR
{
rankdir = LR
head[label="<f0> prev|<f1> head|<f2> next"]
A[label="<f0> prev|<f1> A|<f2> next"]
B[label="<f0> prev|<f1> B|<f2> next"]
C[label="<f0> prev|<f1> C|<f2> next"]
}
left->head:f1 node_tmp->C:f1 right->B:f1
head:f2->A:f1 A:f2->B:f1 B:f2->C:f1 C:f2->head:f1
head:f0->C:f1 A:f0->head:f1 B:f0->A:f1 C:f0->B:f1
}
```
* `left->prev = right->prev;` ， `left->prev` 指向 `A` ， `left->prev->next = left;` 也就是 `A->next` 指回 `head`
```graphviz
digraph graphname{
node_tmp[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=red]
right[shape=plaintext,fontcolor=red]
node[shape=record];
rankdir=LR
{
rankdir = LR
head[label="<f0> prev|<f1> head|<f2> next"]
A[label="<f0> prev|<f1> A|<f2> next"]
B[label="<f0> prev|<f1> B|<f2> next"]
C[label="<f0> prev|<f1> C|<f2> next"]
}
left->head:f1 node_tmp->C:f1 right->B:f1
head:f2->A:f1 A:f2->head:f1 B:f2->C:f1 C:f2->head:f1
head:f0->A:f1 A:f0->head:f1 B:f0->A:f1 C:f0->B:f1
}
```
* `node->next = right;` ，,也就是 `C->next` 指向 `B` ，最後 `right->prev = node;` 也就是 `B` 指回 `C` ，最後得到分割後的兩段 `linked list`
```graphviz
digraph graphname{
node_tmp[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=red]
right[shape=plaintext,fontcolor=red]
node[shape=record];
rankdir=LR
{
rankdir = LR
head[label="<f0> prev|<f1> head|<f2> next"]
A[label="<f0> prev|<f1> A|<f2> next"]
B[label="<f0> prev|<f1> B|<f2> next"]
C[label="<f0> prev|<f1> C|<f2> next"]
}
left->head:f1 node_tmp->C:f1 right->B:f1
head:f2->A:f1 A:f2->head:f1 B:f2->C:f1 C:f2->B:f1
head:f0->A:f1 A:f0->head:f1 B:f0->C:f1 C:f0->B:f1
}
```
4. 而遞迴至剩兩個元素時，則使用 `list_del_init` 函數自成一個指向自己的節點，最後進入 `merge_list` 函式中將資料進行合併
```c=
struct list_head *sep_list(struct list_head *head)
{
if (head == head->next)
return head;
struct list_head *fast = head;
struct list_head *mid = head->prev;
while (fast != mid && fast->next != mid) {
fast = fast->next;
mid = mid->prev;
}
struct list_head *left = head;
struct list_head *right = mid;
struct list_head *node = left->prev;
if (list_is_singular(left)) {
list_del_init(left);
list_del_init(right);
} else {
left->prev = right->prev;
left->prev->next = left;
node->next = right;
right->prev = node;
}
return merge_list(sep_list(left), sep_list(right));
}
```
* `merge_list` 函式說明
* 作法參考至 [2020q1 第 1 週隨堂測驗解題思路](https://hackmd.io/@Ryspon/HJVH8B0XU#2020q1-%E7%AC%AC-1-%E9%80%B1%E9%9A%A8%E5%A0%82%E6%B8%AC%E9%A9%97%E8%A7%A3%E9%A1%8C%E6%80%9D%E8%B7%AF) 共筆文章
* 將從 `sep_list` 函式中得到兩半部分的 `linked list`
* 程式運作說明:
1. 在 6 、 7 行中，先將兩段資料的尾端接到 `NULL` 作法類比至單向 `linked list` 的方式，為判斷式的依據
2. 建立 `head` 與 `tmp` 指標作為合併資料用的暫存點
3. 分為兩種情況:
2.1 `head` (合併後的資料的起始位置)未建立，使用 `strcmp` 判斷左右邊的第一個資料，若 `return < 0` 則使 `left` 的第一個資料當作是 `merge` 後資料的 `head` ，若 `return > 0` 則反之
2.2 `head` (合併後的資料的起始位置)已建立，則使用 `list_add_tail` 把判斷出較小的資料加入 `linked list` 中
4. 最後回傳整個 `merge` 後的結果
:::success
[ISO/IEC 9899:1999](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
> 7.21.4.2 The strcmp function
> Description : The strcmp function compares the string pointed to by s1 to the string pointed to by s2.
> Returns : The strcmp function returns an integer greater than, equal to, or less than zero, pointed to by s2.
> 可用來比較字串間的大小，若 `s1` 較小會 `return < 0` 的數值，而 `s1` 較大則會 `return > 0` 的數值
:::
```c=
struct list_head *merge_list(struct list_head *left, struct list_head *right)
{
struct list_head *head = NULL;
struct list_head *tmp = NULL;
left->prev->next = NULL;
right->prev->next = NULL;
while (left || right) {
if (!right ||
(left && strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) < 0)) {
if (!tmp) {
head = tmp = left;
left = left->next;
if (left)
left->prev = tmp->prev;
INIT_LIST_HEAD(tmp);
} else {
tmp = left;
left = left->next;
if (left)
left->prev = tmp->prev;
list_add_tail(tmp, head);
}
} else {
if (!tmp) {
head = tmp = right;
right = right->next;
if (right)
right->prev = tmp->prev;
INIT_LIST_HEAD(tmp);
} else {
tmp = right;
right = right->next;
if (right)
right->prev = tmp->prev;
list_add_tail(tmp, head);
}
}
}
return head;
}
```
* `q_sort` 函式說明
1. 將整個 `linked list` 未含有資料的 `head` 節點分離出
2. 再將整個 `linked list` 經過 `sep_list` 中透過 `merge sort` 方式，先將資料分段在兩兩合併
3. 排序好的 `linked list` 再將 `head` 加入
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *new_head = head->next;
list_del(head);
new_head = sep_list(new_head);
list_add_tail(head, new_head);
}
```
## 在 qtest 中加入 shuffle 指令
* 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [`Fisher–Yates shuffle 演算法`](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，對佇列中所有節點進行洗牌 (`shuffle`) 操作
* 在 `qtest.c` 檔案中加入 `do_shuffle` 與 `q_shuffle` 函式
* 思考方式:
* 每一輪的操作為將最後一個元素與前面的隨機一個元素進行交換
* 之後固定好當前輪次最後一個元素直到最後兩個元素進行交換
* 舉例來說:依順序為[1, 2, 3, 4, 5]
1. 5 與 1~4其中一個交換，得到[1, 5, 3, 4, 2]
2. 此時2就不再移動，下一輪要交換的元素為 4 和 1 5 3 其中一個元素
3. 直到剩下最後兩個元素進行交換
* 程式運作
1. 先判斷傳入的 `linked list` 是否為 `NULL` 、 `empty` 、 `singular`
2. 設定兩個迴圈次數的變數，分別為 `length` 為總函式的操作次數(交換幾輪)，再來是 `count` 每次的交換後最後一個元素的位置，每經過一輪即遞減透過， `rand() % (count - 1) + 1` 獲取每一輪的隨機亂數位置
3. 將 3 個指標初始位置都指向 `head` ， `tmp` 指標指到隨機位置的前一個位置，主要用來獲得要加入交換來的位置， `tail` 指標則指到每一輪要交換的為最後一個元素， `rand_ptr` 為隨機位置的元素指標
4. 每一輪三個指標確定後先將 `rand_ptr` 隨機的元素移除後再加入在 `tail` 後方
5. 再來，移除 `tail` 元素加入至 `rand_ptr` 被交換前的位置，也就是 `tmp` 指標元素的下一個
6. 交換後將三個指標再回到 `head` 準備進行下一輪的交換
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
srand(time(NULL));
int length = q_size(head) - 1;
int count = length + 1;
struct list_head *tail = head, *tmp = head, *rand_ptr = head;
for (int i = 0; i < length; i++) {
int rand_num;
rand_num = rand() % (count - 1) + 1;
for (int j = 0; j < count; j++) {
if (j < rand_num)
rand_ptr = tmp = tmp->next;
tail = tail->next;
}
tmp = rand_ptr->prev;
list_del(rand_ptr);
list_add(rand_ptr, tail);
list_del(tail);
list_add(tail, tmp);
rand_ptr = tail = tmp = head;
count--;
}
}
```
* 在 `qtest.c` 中新增 `shuffle` 命令，觀察其他的宣告命令方式可以得知函式的兩個引數，分別為 `argc` 與 `argv` 分別為輸入 `command` 的引數數量與引數內輸入字元
* 舉例來說 : 增加 5 個元素為 `dophin`
```
cmd>>ih dophin 5
```
* 此時 `argc = 3` ， `argv[0] = ih` 、 `argv[1] = dophin` 、 `argv[2] = 5`
* 因此建立一個 `shuffle` 命令，變數為 `argc = 1` ， `argv[0] = shuffle` ，進入 `do_shuffle` 會先判斷命令的輸入是否為一個引數，若命令錯誤會顯示 `shuffle takes no arguments` 的錯誤訊息
* `l_meta.l` 在 `qtest.c` 中可觀察為整個 `linked list` 所以判斷 `l_meta.l` 是否存在
* 兩者判斷式確認後就可即執行 `q_shuffle` 的函式中進行打亂元素的功能
* 最後透過 `show_queue` 函式將 `shuffle` 後的結果顯示
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l) {
report(3, "Warning: Try to access null queue");
return false;
}
q_shuffle(l_meta.l);
return show_queue(0);
}
```
* 測試運行成果，從 `./qtest` 進入命令模式，輸入以下指令測試
* 使用 `RAND` 指令填入隨機 6 個元素，測試命令的運作情況
```shell
cmd> new
l = []
cmd> ih RAND 6
l = [bshbasnli ewfdfyov anepx gqaokyijm xttlxhrjq fjpxj]
cmd> shuffle
l = [xttlxhrjq gqaokyijm fjpxj bshbasnli anepx ewfdfyov]
cmd> shuffle
l = [bshbasnli fjpxj xttlxhrjq ewfdfyov gqaokyijm anepx]
cmd> free
l = NULL
```
* 若輸入的引數不正確會跳出錯誤訊息
```shell
cmd> new
l = []
cmd> ih RAND 5
l = [lxgjf lqfnd djzywlcf tmbhkpywi ikfrzcsg]
cmd> shuffle 3
shuffle takes no arguments
```
## 引入 linux 的程式碼進行 sort 比較
[參考 linux list.c 共筆文章](https://hackmd.io/@DokiDokiPB/SJfES914O)
* 在 `merge_final` 函式中，處理了不平衡的兩個串列，為了減少過多不必要的迭代次數，以下是原文的附註
```
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.
```
* `list_sort.c` 中，主要處理了非 2 倍數的串列，會進行 padding 的動作，引述自原文，在 mergesort 中會希望最差能有 2 : 1 的資料比例進行，主要能避免 [cache thrashing](https://ithelp.ithome.com.tw/articles/10208889) 的情況產生，可避免 CPU 的效率急速下降
```
* 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.
```
* 將 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 引入到 [lab0-c](https://hackmd.io/@sysprog/linux2022-lab0) 專案中
* 為了將程式碼引用將一些程式的宣告加入
* 可以看到在 2 、 3 行中，參考至此篇文章 [likely and unlikely](https://coctec.com/docs/linux/show-post-184401.html) 的解說，[`__builtin_expect`](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html) 為 gcc 引入，目的提高 cpu 的效率，讓 cpu 可以預先取出下一條指令，減少 cpu 的等待時間，在參數中 `!!(x)` 將 `(x)` 轉換成 bool 值，可以得到 `true/false` 所以在執行上 `likely(x)` 會用 if 的敘述的機會變大
* 可以看到在原始碼中有 `list_cmp_func_t` 的宣告，加入了 4 、 5 行的敘述，參考至 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h)對 `list_cmp_func_t` 的宣告
* [`__attribute__((nonnull(2,3)))`](keil.com/support/man/docs/armcc/armcc_chr1359124976631.htm)確保在 2 3 位的引數中不為空指標
> The nonnull attribute specifies that some function parameters should be non-null pointers
> [文件](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Function-Attributes.html)
```c=
typedef unsigned char u8;
#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 *);
```
這裡參考了 [lanser同學的筆記](https://hackmd.io/@laneser/linux2022_lab0) 加入了對引數的資料的比較方式，利用 `strcmp` 比較 `merge list` 中的兩元素的值(使用 `list_entry` 取出)
* `list_sort.c` 內部的函式說明:
```
* 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.
```
```c
int sort_comp(void *p, const struct list_head *a, const struct list_head *b)
{
return strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value);
}
```
補完上述的一些宣告就可以使用 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的函式做使用
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
list_sort(NULL, head, sort_comp);
}
```
### 比較 q_sort 與 list_sort 效率
* 在 `trace` 目錄下新增兩個測試的的檔案分別為 `trace-18-sort.cmd` 與 `trace-19-sort.cmd`
* `trace-18-sort.cmd` 內容如下，主要測試以 `RAND` 指令給定下的隨機資料進行比較，分別進行 100000 、 500000 、 1000000 筆資料的比較
* 使用 time 指令可以得到 sort 的時間
```shell
# Test performance of sort with RAND
option fail 0
option malloc 0
new
ih RAND 100000
time
sort
time
```
* 測試的方式使用 `perf` 工具，參考至 [`perf 的使用說明`](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
```shell
perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-18-sort.cmd
```
* 測試運行時間 (second):
| Data Number | 100000 | 500000 | 1000000 |
| -------- | -------- | -------- | -------- |
| list_sort | 0.029 | 0.318 | 0.721 |
| q_sort | 0.034 | 0.345 | 0.807 |
| time improved | 17.24% | 8.5% | 11.92% |
* 以取 100000 筆資料的效能結果 (list_sort)
```shell
Performance counter stats for './qtest -f traces/trace-18-sort.cmd' (5 runs):
1,641,816 cache-misses # 12.925 % of all cache refs ( +- 1.74% )
12,702,519 cache-references ( +- 0.39% )
280,380,864 instructions # 0.98 insn per cycle ( +- 0.00% )
284,740,366 cycles ( +- 0.42% )
```
* 以取 100000 筆資料的效能結果 (q_sort)
```shell
Performance counter stats for './qtest -f traces/trace-18-sort.cmd' (5 runs):
1,823,005 cache-misses # 13.040 % of all cache refs ( +- 7.01% )
13,980,297 cache-references ( +- 0.24% )
297,605,881 instructions # 0.99 insn per cycle ( +- 0.03% )
301,111,612 cycles ( +- 0.79% )
```
* 總合上述的結果進行一點分析比較:
* 在時間的表現上使用 `list_sort` 的方法在亂數資料的排序下，比自己寫的 `q_sort` 都有約 10% 的速度提升
* 可以看到在效能上 `cache-misses` 與 `instructions` 上也 `list_sort` 的資源使用上也少了一些，整體是比較有效率的
* `trace-19-sort.cmd` 內容如下，主要測試以給定固定的兩種重複性資料(分別為 gerbil 與 dolphin)，分別進行 100000 、 500000 、 1000000 筆資料的測試
```shell
# Test performance of sort with duplication
option fail 0
option malloc 0
new
ih gerbil 50000
ih dolphin 50000
time
sort
time
```
* 測試運行時間 (second):
| Data Number | 100000 | 500000 | 1000000 |
| -------- | -------- | -------- | -------- |
| list_sort | 0.010 | 0.085 | 0.172 |
| q_sort | 0.014 | 0.131 | 0.282 |
| time improved | 40% | 54.11% | 63.95% |
* 以取 100000 筆資料的效能結果 (list_sort)
```shell
Performance counter stats for './qtest -f traces/trace-18-sort.cmd' (5 runs):
1,177,740 cache-misses # 16.648 % of all cache refs ( +- 6.72% )
7,074,268 cache-references ( +- 0.41% )
182,706,651 instructions # 1.32 insn per cycle ( +- 0.01% )
138,478,460 cycles ( +- 1.18% )
```
* 以取 100000 筆資料的效能結果 (q_sort)
```shell
Performance counter stats for './qtest -f traces/trace-18-sort.cmd' (5 runs):
1,383,044 cache-misses # 13.986 % of all cache refs ( +- 8.55% )
9,888,627 cache-references ( +- 0.63% )
209,100,672 instructions # 1.19 insn per cycle ( +- 0.01% )
175,059,692 cycles ( +- 0.64% )
```
* 測試的結果分析
* 可以看到在重複的資料進行排序的時候， `list_sort` 很明顯的就比 `q_sort` 所花的時間還要短，而且在越多筆資料的表現上，時間上的差距會越來越明顯(40% -> 54.11% -> 63.95%)，可見在 `list_sort` 對於重複性或預排好的資料處理的速度快了許多
* 而在效能上 `cache-misses` 與 `instructions` 上 `list_sort` 的資源使用上也相對使用的較少
## 參考資料
* [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
* [ISO/IEC 9899:1999](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
Sign in with Wallet
Connect another wallet