# 2022q1 Homework1 (lab0)
contributed by < [november295536](https://github.com/november295536) >
> [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
## 學習紀錄
[2022 Linux 核心設計/實做學習紀錄](/v4QcQooCSLOD3yuahQCfXw)
## 作業環境
```shell
$ uname -a
Linux november-PC 5.11.0-27-generic #29~20.04.1-Ubuntu SMP Wed Aug 11 15:58:17 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
$ 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: 43 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 23
Model: 24
Model name: AMD Ryzen 5 3400G with Radeon Vega Graphics
Stepping: 1
Frequency boost: enabled
CPU MHz: 1400.000
CPU max MHz: 3700.0000
CPU min MHz: 1400.0000
BogoMIPS: 7386.31
Virtualization: AMD-V
L1d cache: 128 KiB
L1i cache: 256 KiB
L2 cache: 2 MiB
L3 cache: 4 MiB
NUMA node0 CPU(s): 0-7
```
## 作業要求
- [x] 修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，滿足 `$ make test` 自動評分系統得所有項目
- [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 `qtest` 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- [ ] 修正 `qtest` 中的記憶體錯誤
- [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點
- [ ] 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理
- [ ] 討論目前的 "simulation" 模式現存的致命缺陷及提出解決方案。
- [ ] 指出現有程式的缺陷或可改進之處
## 實現 queue.c
### q_new
> 2/28 0600-0743
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
一開始的實做方式是透過 `if(head != NULL)` 來進行判斷，在看到 jserv 對其他人的 [review 訊息](https://github.com/laneser/lab0-c/commit/136701ea195180ec2f8a24a18d7a2b5ac30a1d51)之後調整為更精簡的表達方式 `if(head)` 。
原本使用 cppcheck v2.7 並想要 commit 針對 q_new 的更動時跳出了以下訊息：
```shell
$ git commit -a
Following files need to be cleaned up:
queue.c
qtest.c:507:33: error: Uninitialized variable: item->value [uninitvar]
slen = strlen(item->value) + 1;
^
qtest.c:504:17: note: Assuming condition is false
if (!tmp)
^
qtest.c:507:33: note: Uninitialized variable: item->value
slen = strlen(item->value) + 1;
^
Fail to pass static analysis.
```
由於我只打算讓本次提交中包含 q_new 相關的實現，也並不打算在現在處理這個問題，因此透過把 cppcheck 版本降至 v2.3 來通過靜態分析。
### q_free
原本使用 `list_for_each_entry` 配合已經寫好的 `q_release_element` 實做，但這樣寫其實是對於 `list_for_each_entry` 的誤用，因為無法透過被 `q_release_element` 操作過的節點找到下一個節點的位置。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *pos;
list_for_each_entry (pos, l, list)
q_release_element(pos);
free(l);
}
```
經修正後改為以下版本：
```c
void q_free(struct list_head *l)
{
if (!l)
return;
while (!list_empty(l)) {
element_t *node = list_first_entry(l, element_t, list);
list_del(&node->list);
q_release_element(node);
}
free(l);
}
```
### q_insert_head & q_insert_tail
針對這兩個插入操作，由於都需要新增節點，因此我寫了一個工具函式來避免寫出重複的代碼。邏輯是只要節點或字串任一分配空間失敗，就釋放已經分配好的空間並返回 `NULL`，不然就返回指向新建立節點的指標。
:::spoiler 第一版實做
```c
/*
* Attempt to create a new element_t.
* Argument s points to the string to be stored.
* Return pointer to new element_t if successful.
* Return null if failed.
*/
static inline element_t *element_create(char *s)
{
element_t *node = malloc(sizeof(element_t));
char *copy = strdup(s);
if (!node || !copy) {
free(node);
free(copy);
return NULL;
}
node->value = copy;
return node;
}
```
:::
第二版實做: 如果失敗的話提早進行返回以減少非必要的字串複製動作。
```c
static inline element_t *element_create(char *s)
{
element_t *node = malloc(sizeof(element_t));
if (!node)
return NULL;
char *copy = strdup(s);
if (!copy) {
free(node);
return NULL;
}
node->value = copy;
return node;
}
```
`q_insert_head` 跟 `q_insert_tail` 的差別僅在於兩者調用不同的插入函式，前者使用 `list_add` 後者使用 `list_add_tail`。
```c
/*
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = element_create(s);
if (!node)
return false;
list_add(&node->list, head);
return true;
}
/*
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = element_create(s);
if (!node)
return false;
list_add_tail(&node->list, head);
return true;
}
```
### q_remove_head & q_remove_tail
這兩個函式也幾乎一樣，差別只在於從 `lish.h` 中調用不同 macro 去取得不同方向的第一個節點。為了復用相同兩者相同的地方，也另外寫了解決複製被刪除的字串的工具函式 `cpynstr`。
`cpynstr` 的邏輯很簡單，如果傳近來的 `des` 不是 NULL 就會往裡面複製最多 `bufsize` 個字符，而且最後一個字符必定為 `\0`。
```c
static inline void cpynstr(char *des, const char *source, size_t bufsize)
{
if (des) {
strncpy(des, source, bufsize - 1);
des[bufsize - 1] = 0;
}
}
```
`q_remove_head` 和 `q_remove_tail` 執行步驟如下:
1. `list_first_entry` 和 `list_last_entry` 來獲得需要被從鏈接串列中移除的節點(並非刪除)。
2. 取得須被移除的節點之後調用 `list.h` 中的 `list_del` 從鏈接串列中移除節點。
3. 使用工具函式 `cpynstr` 嘗試把被刪除節點鎖保存的字串複製到指定位置。
```c
/*
* Attempt to remove element from head of queue.
* Return target element.
* Return NULL if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
*
* NOTE: "remove" is different from "delete"
* The space used by the list element and the string should not be freed.
* The only thing "remove" need to do is unlink it.
*
* REF:
* https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
*/
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_first_entry(head, element_t, list);
list_del(&node->list);
cpynstr(sp, node->value, bufsize);
return node;
}
/*
* Attempt to remove element from tail of queue.
* Other attribute is as same as q_remove_head.
*/
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_last_entry(head, element_t, list);
list_del(&node->list);
cpynstr(sp, node->value, bufsize);
return node;
}
```
### q_size
`q_size` 的實做主要依靠巨集 `list_for_each` 去實現走訪所有節點的功能。該巨集的第一個參數是一個指向節點的指標，第二個參數是整個鏈接串列的頭。
```c
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int len = 0;
struct list_head *p;
list_for_each (p, head)
len++;
return len;
}
```
### q_delete_mid
程式的邏輯分成三個步驟:
1. 找到鏈接串列中間的節點。
2. 從鏈接串列中移除該節點。
3. 釋放這個節點的資源。
為了和其他函式共用`找到鏈接串列中間的節點`這個邏輯，抽出了一個工具函式 `find_mid`，其實現邏輯是透過一快一慢的兩個指標，快的指標每往後移動兩步，慢的指標只移動一步，這樣當快的指標走完整個鏈接串列的時候，慢的指標就會停在中間的節點。
`find_mid` 曾經透過 `lish.h` 中定義的 `list_for_each` 來實做，不過因為後面在處理排序問題的時候會把 doubly linked list 轉換成沒有 head 節點的 singly linked list，`list_for_each` 沒辦法很好的應付這種情況，因此使用處理方式相似但判斷邏輯略有不同的 for 迴圈來走訪整個鏈接串列。
```c
static inline struct list_head *find_mid(struct list_head *head)
{
struct list_head *mid = head, *p;
int i = 1;
for (p = head->next; p && p != head; p = p->next) {
if (i % 2) {
mid = mid->next;
}
i++;
}
return mid;
}
```
實現出上面的 `find_mid` 把找出中間節點的邏輯封裝起來之後 `q_delete_mid` 的程式就長得很精簡，閱讀起來跟閱讀上面提到的三個步驟幾乎一樣。
```c
/*
* Delete the middle node in list.
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six element, the third member should be return.
* Return true if successful.
* Return false if list is NULL or empty.
*/
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *mid = find_mid(head);
list_del(mid);
q_release_element(list_entry(mid, element_t, list));
return true;
}
```
#### q_delete_dup
這個函式應該要刪除有重複字串的節點，如果有兩個節點保存的字串相同，兩個節點都應該被刪除，但我一開始誤會了，以為只要刪除其他重複的並保留其中一個即可，因此第一版的程式無法通自動評分測試。
第一版本中有兩個 for 迴圈，外部的 for 迴圈透過巨集 `list_for_eqch_entry` 訪問鏈接串列中的每個節點並取得包含 `list_head` 結構的 `element_t` 本身，內部的 for 迴圈則檢查是否有跟當前走訪到的節點保存相同字串的節點並予以刪除。這個版本除了誤解題意之外，透過 `next = list_entry(pos->list.next, element_t, list)` 去取得下一個節點內部的字串時也會因為遇到整個鏈接串列的 head 而發生錯誤。
:::spoiler 第一版實作
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
element_t *pos, *next;
list_for_each_entry (pos, head, list) {
if (pos->list.next == head)
break;
for (next = list_entry(pos->list.next, element_t, list);
strcmp(pos->value, next->value) == 0;
next = list_entry(pos->list.next, element_t, list)) {
list_del(&next->list);
q_release_element(next);
}
}
return true;
}
```
:::
第二個版本則多引入一個標誌 `delete_cur` 用來表示需要刪除當前的節點，在內部的 for 迴圈檢測到出現重複的字串後，就會將 `delete_cur` 設為 `true` 並在結束後進行刪除的動作。
這個版本也多出兩個 if 判斷式去判斷下個節點是不是整個鏈接串列的頭，這是為了避免對不是 `element_t` 結構體的表頭進行 `list_entry` 的操作。
```c
/*
* Delete all nodes that have duplicate string,
* leaving only distinct strings from the original list.
* Return true if successful.
* Return false if list is NULL.
*
* Note: this function always be called after sorting, in other words,
* list is guaranteed to be sorted in ascending order.
*/
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
element_t *pos, *tmp;
list_for_each_entry (pos, head, list) {
if (pos->list.next == head)
break;
bool delete_cur = false;
for (tmp = list_entry(pos->list.next, element_t, list);
strcmp(pos->value, tmp->value) == 0;
tmp = list_entry(pos->list.next, element_t, list)) {
list_del(&tmp->list);
q_release_element(tmp);
delete_cur = true;
// cppcheck-suppress knownConditionTrueFalse
if (pos->list.next == head)
break;
}
if (delete_cur) {
tmp = list_entry(pos->list.prev, element_t, list);
list_del(&pos->list);
q_release_element(pos);
pos = tmp;
}
}
return true;
}
```
### q_swap
題目要求交換兩兩相鄰的節點，為了程式的可讀性與並讓未來能繼續復用現有程式碼，我新增了一個工具函式 `list_swap` 去交換兩個鏈接串列的節點。
`list_swap` 的邏輯是先判斷兩個需要被交換的點是否相鄰，若是相鄰則把後一個節點從鏈接串列中移除，並重新添加到前一個節點的前方。若是兩節點不相鄰，則紀錄兩節點在鏈接串列中的相對位置，並將兩個節點從鏈接串列中移除，最後根據紀錄的相對位置重新插入。
```c
/*
* Swap two list_head.
*/
static inline void list_swap(struct list_head *head1, struct list_head *head2)
{
if (head1->next == head2) {
list_del(head2);
list_add(head2, head1->prev);
} else if (head2->next == head1) {
list_del(head1);
list_add(head1, head2->prev);
} else {
struct list_head *head1_prev = head1->prev, *head2_prev = head2->prev;
list_del(head1);
list_del(head2);
list_add(head2, head1_prev);
list_add(head1, head2_prev);
}
}
```
有了 `list_swap` 函式之後，想要實做 `q_swap` 就變得很簡單，只需要透過巨集 `list_for_each` 去走訪整個鏈接串列，每走訪兩個節點就進行一次交換即可。
```c
/*
* Attempt to swap every two adjacent nodes.
*/
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
int i = 0;
struct list_head *cur;
list_for_each (cur, head) {
if (i % 2) {
list_swap(cur->prev, cur);
cur = cur->next;
}
i++;
}
}
```
### q_reverse
為了要反轉整個鏈接串列的順序，這邊使用 front 及 back 兩個指標從正向以及反向分別走訪整個鏈接串列，每走一步就透過前面提過得工具函式 `list_swap` 交換指標指向的兩個節點在鏈接串列中的位置。while 循環的中止條件有兩個:
1. 當總節點個數為奇數時，兩個指標會同時指向正中間的節點，代表鏈接串列經完成反轉
2. 當總節點個數為偶數時，反轉完之後兩指標所指向的節點若相鄰，也代表完成鏈接串列反轉
要特別注意在使用 `list_swap` 交換完兩節點的位置之後，為了讓兩個指標能正確的繼續從正向及反向走訪整個鏈接串列，也需要交換兩指標的內容。
```c
/*
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
*/
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *front = head, *back = head, *tmp;
while (true) {
front = front->next;
back = back->prev;
if (front == back)
break;
list_swap(front, back);
tmp = front;
front = back;
back = tmp;
if (front->next == back)
break;
}
}
```
### q_sort
#### quick sort 版本
一開始使用 quick sort 的方式實現:
1. 第一個節點設定成 `pivot`，並另外新增兩個鏈接串列的頭 `head1` 及 `head2` 去分別存儲應該在 `pivot` 左邊及右邊的節點。
2. 第二步則是透過一個 while 循環走訪整個鏈接串列，並使用 `strcmp` 比較兩節點存儲的字串，透過其返回值決定需要將當前節點轉移到 `head1` 還是 `head2` 中。
3. 第三步則是透過遞迴呼叫去排序 `head1` 及 `head2` 兩個鏈接串列。
4. 最後將排序好的 `head1` 及 `head2` 分別插入原本傳入的鏈接串列的頭及尾。
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *pivot = head->next;
element_t *pivot_entry = list_entry(pivot, element_t, list);
LIST_HEAD(head1);
LIST_HEAD(head2);
while (pivot->next != head) {
struct list_head *cur = pivot->next, *target;
element_t *cur_entry = list_entry(cur, element_t, list);
target =
strcmp(pivot_entry->value, cur_entry->value) > 0 ? &head1 : &head2;
list_move(cur, target);
}
q_sort(&head1);
q_sort(&head2);
list_splice(&head1, head);
list_splice_tail(&head2, head);
}
```
使用 quick sort 無法通過性能 `trace-14-perf.cmd` 及 `trace-15-perf.cmd` 這兩個效能測試，在看了隔壁 [laneser](https://hackmd.io/@laneser/linux2022_lab0#q_sort) 及 [Risheng1128 ](https://hackmd.io/@Risheng/linux2022-lab0#q_sort) 同學的心得之後，發現原來是我對 quick sort 的理解不足，其不僅不是一個 stable 的排序方式，在最壞情況下的時間複雜度則會來到 $O(n^2)$，所以改成使用 merge sort 來進行實做。
#### merge sort 版本
原本在實做的時候，我想保有雙向鏈接串列的環狀特性，並使用 linux 風格的界面去進行鏈接串列的操作，但在實作的過程中為了判斷鏈接串列是否已經是空的，需要加上大量非必要的程式碼，最後我決定在實作 merge sort 的時候先把雙向鏈接串列拆分成單向鏈接串列。
##### q_sort
這個函式主要做了三件事情:
1. 把傳進來的環狀鏈接串列變成非環狀的鏈接串列
```c
head->prev->next = NULL;
```
2. 呼叫 `merge_sort` 函式取得排序好的鏈接串列，排序好的鏈接串列為單向並且沒有形成環狀結構。
3. 把結果復原成環狀環狀雙向鏈接串列
```c
// 把串列的頭指向排序好的單向鏈接串列
head->next = sorted_list;
// 走訪整個鏈接串列並把 prev 接上使其成為雙向鏈接串列
struct list_head *cur = head;
while (cur->next) {
cur->next->prev = cur;
cur = cur->next;
}
// 把最後一個節點接上鏈接串列的頭，復原成環狀雙向鏈接串列
cur->next = head;
head->prev = cur;
```
程式如下:
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *first_node = head->next;
head->prev->next = NULL;
struct list_head *sorted_list = merge_sort(first_node);
head->next = sorted_list;
struct list_head *cur = head;
while (cur->next) {
cur->next->prev = cur;
cur = cur->next;
}
cur->next = head;
head->prev = cur;
}
```
> 在實現的過程中我因為少打了 `cur=cur->next;` 這一行程式碼導致結果有錯([修復的 commit](https://github.com/november295536/lab0-c/commit/003571b99c6e9d052845aed8514ca427af173644))，然而當我想使用 `gdb` 進行除錯，設定好中斷點、執行程式、正要進行單步跟蹤的時候卻總是沒有成功的進入到下一步，而是進入 `harness.c` 的267行:
> ```c
> 0x000055555555aae5 in exception_setup (limit_time=true) at harness.c:267
> 267 if (sigsetjmp(env, 1)) {
>```
> 這一步卡了我非常久，為此我花了數個小時在沒有 gdb 的情況下想辦法除錯，其中包含了使用肉眼去推算程式中哪裡出了問題，到最後我都找出問題了也不知道為什麼 gdb 無法順利進入下一行。
> 一直到一段時間之後我才發現在 `harness.c` 中有設定了 `time_limit`，只要調整這個變數的值即可按照預期的方式使用 gdb。
再來看會用到的兩個工具函式 `merge_two_lists` 及 `merge_sort`。
##### merge_sort
1. `merge_sort` 首先會找到傳入的鏈接串列的中間節點並將其斷開形成兩個新的鏈接串列
2. 將兩個鏈接串列分別使用遞迴呼叫去進行排序
3. 將排序好的兩個鏈接串列使用 `merge_two_lists` 進行合併
在這邊使用到了前面所提到的 `find_mid`，當初 `find_mid` 之所以沒有使用 `list_for_each` 就是為了相容這邊單向鏈接串列結構。
```c
static struct list_head *merge_sort(struct list_head *head)
{
if (!head->next)
return head;
struct list_head *mid = find_mid(head);
mid->prev->next = NULL;
head = merge_sort(head);
mid = merge_sort(mid);
return merge_two_lists(head, mid);
}
```
##### merge_two_list
`merge_two_list` 接受兩個指向單向鏈接串列中的第一個元素的指標當作參數，並返回指向合併後的鏈接串列的第一個元素的指標。
其合併兩個串列的時候則使用了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)中鎖提到的操作指標的指標的技巧。
```c
static struct list_head *merge_two_lists(struct list_head *head1,
struct list_head *head2)
{
struct list_head *head = NULL, **node, **ptr = &head;
for (node = NULL; head1 && head2; *node = (*node)->next) {
element_t *e1 = list_entry(head1, element_t, list);
element_t *e2 = list_entry(head2, element_t, list);
node = (strcmp(e1->value, e2->value) < 0) ? &head1 : &head2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((u_int64_t) head1 | (u_int64_t) head2);
return head;
}
```
## 在 qtest 中新增 shuffle 命令
:::warning
因為不能更動 `queue.h` 所以只好把相關函式直接新增在 `qtest.c` 之中。
:::
這個要求可以拆分成兩個任務:
1. 新增 `q_shuffle` 函式進行 shuffle 的動作
2. 在 `qtest.c` 中新增 shuffle 命令
### q_shuffle 的設計
該函式的功能是對傳進來佇列使用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 進行洗牌的動作。由於 queue 的底層使用 linked list 進行實作，特性是各節點的位置在記憶體上並非連續的，為了訪問特定位置的節點需要一邊記數一邊走訪整個鏈接串列，操作效率較低，因此這邊先使用一個大小和節點數量相當的陣列去存儲指向各節點的指標，接下來再對陣列中指標的順序進行洗牌操作，最後再將各節點根據洗牌後的順序重新插入 queue 之中來完成洗牌。
首先是透過 `q_size` 去取得陣列的大小，並把指向各個節點的指標依序存放在陣列之中:
```c
int size = q_size(head);
struct list_head *queue[size];
// Put every node into an array
for (int i = 0; i < size; i++) {
struct list_head *first = head->next;
queue[i] = first;
list_del(first);
}
```
:::warning
C99 標準才允許 variable-length array
:::
再來是對陣列中的元素進行洗牌，洗牌之前先使用 `srand` 指定亂數種子:
```c
// Do Fisher–Yates shuffle on array "queue"
// ref: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
srand(time(NULL));
for (int i = size - 1; i > 0; i--) {
int rand_pos = rand() % (i + 1);
struct list_head *tmp = queue[rand_pos];
queue[rand_pos] = queue[i];
queue[i] = tmp;
}
```
最後再把節點按照新的順序加回佇列中:
```c
// Add nodes back to head in new order
for (int i = 0; i < size; i++) {
list_add_tail(queue[i], head);
}
```
:::spoiler q_shuffle 完整程式碼:
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int size = q_size(head);
struct list_head *queue[size];
// Put every node into an array
for (int i = 0; i < size; i++) {
struct list_head *first = head->next;
queue[i] = first;
list_del(first);
}
// Do Fisher–Yates shuffle on array "queue"
// ref: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
srand(time(NULL));
for (int i = size - 1; i > 0; i--) {
int rand_pos = rand() % (i + 1);
struct list_head *tmp = queue[rand_pos];
queue[rand_pos] = queue[i];
queue[i] = tmp;
}
// Add nodes back to head in new order
for (int i = 0; i < size; i++) {
list_add_tail(queue[i], head);
}
}
```
:::
### 新增 shuffle 命令
追蹤 `qtest.c` 中的程式碼後可以發現透過 `ADD_COMMAND` 巨集接收兩個參數，第一個是命令的名稱，第二個參數是命令的說明。命令使用的名稱則會去呼叫名為 `do_{名稱}` 函式進行處理，因此只需要在 `console_init` 之中新增下面這行程式碼，即可在 `qtest` 中新增 shuffle 命令:
```c
ADD_COMMAND(shuffle, " | Shuffle nodes in queue");
```
由於 shuffle 命令還需要 `do_shuffle` 函式去進行處理，因此還需要在 `qtest.c` 中新增 `do_shuffle` 函式，該函式參考 swap 命令所調用的 `do_swap` 函式:
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takse no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Try to access null queue");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
## TODO
- [ ] 完成所有函式後使用 cppcheck v2.7 重新檢查
- [ ] 使用圖片更清楚的表示對節點的各項操作
Sign in with Wallet
Connect another wallet