# 2022q1 Homework1 (lab0)
contributed by < `cy023` >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ uname -a
Linux cy023-e14 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
$ 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): 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: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz
Stepping: 12
CPU MHz: 2300.000
CPU max MHz: 4900.0000
CPU min MHz: 400.0000
BogoMIPS: 4599.93
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
```
## 作業要求
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
- [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
- [x] 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
- [x] 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
* 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2022-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- [ ] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
- [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
- [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
* 截止日期：
* Mar 1, 2022 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review 並持續改進者，評分越高
- `queue.c` 實作
:::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_release_element`: 釋放特定節點的記憶體空間;
- [x] `q_size`: 計算目前佇列的節點總量;
- [x] `q_delete_mid`: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
- [x] `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
- [x] `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
- [x] `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- [x] `q_sort`: 以==遞增順序==來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
:::
## 開發紀錄
### q_new
建立一個佇列起點 (`struct list_head` 型態)。
佇列內不含其他資料，並將起點的 `prev`, `next` 指向自己。
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
一開始配置 `element_t` 型態大小的空間給 `queue head`, 並將 `element_t` 的 `value` 元素指向 `NULL`。
```c
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
struct list_head *q_new()
{
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return NULL;
ele->value = NULL;
INIT_LIST_HEAD(&ele->list);
return &ele->list;
}
```
但後來發現完全不必要額外浪費不使用的空間(一個字元指標大小)，`queue head` 設定為 `struct list_head` 即可。
(若在其他應用場景可以將`queue head` 型態改為包含 `stuct list_head` 與其他佇列額外資訊的結構型態，在使用 `container_of` 取得需要的資訊)
並使用 `list.h` 中 Linux Kernel 風格 API `INIT_LIST_HEAD()` 初始化 `queue head`。
:::spoiler INIT_LIST_HEAD
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
:::
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
:::warning
除了張貼程式碼，你應該解釋其作用，並探討後續的改進空間。
:notes: jserv
:::
### q_free
釋放所有佇列使用到的空間。
`q_free` 函式傳入參數為 `struct list_head *` 型態，但佇列中用來儲存資料的節點型態是 `element_t`，需要注意所有佇列中的字串都要被釋放，以防 `memory leak`。
```c
typedef struct {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct list_head list;
} element_t;
```
需要實作利用結構成員實際位址，找出該結構物件的起始位址的操作。
參考 `list.h` 中，`container_of`。
:::spoiler container_of
```c
/**
* container_of() - Calculate address of object 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 object 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
```
:::
使用標準 API `list_empty()` 檢查佇列是否為空，如果佇列內還有資料，使用 `list_first_entry()` 取出第一筆資料 (`element_t` 型態)， `list_del()` 將第一筆資料移出 `queue`，然後釋放掉該節點使用的空間，最後釋放 `queue head`。
:::spoiler list_empty()
```c
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
:::
:::spoiler list_first_entry()
```c
#define list_entry(node, type, member) container_of(node, type, member)
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
:::
:::spoiler list_del()
```c
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
:::
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
if (!l)
return;
while (!list_empty(l)) {
element_t *tmp = list_first_entry(l, element_t, list);
list_del(l->next);
free(tmp->value);
free(tmp);
}
free(l);
}
```
將 [~~疊代~~](https://terms.naer.edu.tw/detail/17514220/) [迭代](https://www.facebook.com/groups/system.software2022/permalink/1981539525360781/)方式改為標準 API，list_for_each_entry_safe()。
:::spoiler list_for_each_entry_safe()
```c
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
```
:::
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *li, *safe;
list_for_each_entry_safe (li, safe, l, list) {
list_del(&li->list);
free(li->value);
free(li);
}
free(l);
}
```
### q_insrt_head
配置 `element_t` 型態空間當作新節點，另外配置傳入字串長度的空間用來存放節點的字串資料。
複製字串時考慮 [buffer overflow 議題](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)，使用 `strncpy()` 函式。
設定好新節點後，用標準 API `list_add` 將節點插入佇列。
:::spoiler 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
/*
* 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;
size_t slen = strlen(s);
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
INIT_LIST_HEAD(&ele->list);
ele->value = malloc(slen + 1);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, slen + 1);
list_add(&ele->list, head);
return true;
}
```
### q_insert_tail
與 `q_insert_head` 類似，將新增節點利用 `list_add_tail()` 插入佇列尾端。
:::spoiler 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
/*
* 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;
size_t slen = strlen(s);
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
INIT_LIST_HEAD(&ele->list);
ele->value = malloc(slen + 1);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, slen + 1);
list_add_tail(&ele->list, head);
return true;
}
```
### q_remove_head
利用前述提到的 `list_first_entry()` 取出佇列中的第一個節點，並使用 `list_del()` 從佇列中移除 (remove)。
在將被移除節點字串內容複製出來時，使用 `strncpy()` 函式，根據 `man strncpy`
> The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. Beware of buffer overruns! (See BUGS.)
>
> The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.
需要注意，當被移除節點字串長度大於 buffer 長度時，`strncpy()` 並不會在 buffer 最後一位補上 `'\0'` 結尾，需要幫忙加上。
```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 *q = list_first_entry(head, element_t, list);
if (!q)
return NULL;
list_del(head->next);
if (sp) {
strncpy(sp, q->value, bufsize);
sp[bufsize - 1] = '\0';
}
return q;
}
```
### q_remove_tail
與 `q_remove_head` 類似，以 `list_last_entry()` 取出佇列中的最後一個節點，並使用 `list_del()` 從佇列中移除 (remove)。
:::spoiler list_last_entry()
```c
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
```
:::
```c
/*
* 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 *q = list_last_entry(head, element_t, list);
if (!q)
return NULL;
list_del(head->prev);
if (sp) {
strncpy(sp, q->value, bufsize);
sp[bufsize - 1] = '\0';
}
return q;
}
```
### q_size
`list_for_each()` 走訪所有節點，並計算長度。
:::spoiler list_for_each()
```c
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
:::
```c
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(struct list_head *head)
{
if (!head)
return 0;
size_t len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_delete_mid
[LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
藉由 [Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection) 演算法的機制，找出 `queue` 的中間節點，並將其 `delete` (不只是 `remove`)。
如果節點數量為奇數，移除第 `⌊n / 2⌋` 個節點。
```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 NULL if list is NULL or empty.
*/
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return NULL;
struct list_head *slow = head->next;
struct list_head *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_del(slow);
element_t *mid = list_entry(slow, element_t, list);
free(mid->value);
free(mid);
return true;
}
```
### q_delete_dup
[LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
TODO: 探討與 `quiz1` 遞迴版本的差異
```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)
{
if (!head || list_empty(head))
return NULL;
struct list_head *tmp = head->next;
struct list_head *end;
while (tmp != head) {
end = tmp->next;
element_t *q1 = list_entry(tmp, element_t, list);
element_t *q2 = list_entry(end, element_t, list);
while (end != head && !strcmp(q1->value, q2->value)) {
struct list_head *next = end->next;
list_del(end);
free(q2->value);
free(q2);
end = next;
q2 = list_entry(end, element_t, list);
}
tmp = end;
}
return true;
}
```
在看 quiz1 的時候，突然發現這裡寫錯了...
重複的節點需要全部移除，但以上的實作，重複的節點會有一個被保留下來。
回頭看 `./qtest` 的 `do_dedup()` 只有檢查是否存在重複節點，若留一個重複節點下來，`./qtest` 並不會發現。
改成
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
struct list_head *tmp = head->next;
struct list_head *end;
while (tmp != head) {
end = tmp->next;
bool isdup = 0;
element_t *q1 = list_entry(tmp, element_t, list);
element_t *q2 = list_entry(end, element_t, list);
while (end != head && !strcmp(q1->value, q2->value)) {
end = end->next;
list_del(end->prev);
free(q2->value);
free(q2);
q2 = list_entry(end, element_t, list);
isdup = 1;
}
if (isdup) {
tmp = tmp->next;
list_del(tmp->prev);
free(q1->value);
free(q1);
}
tmp = end;
}
return true;
}
```
### q_swap
[LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
~~一次跨兩步~~ 剛開始將 `node` 指向 `head`，先檢查是否存在下下個節點 (`node->next` 不等於 `head` 且 `node->next->next` 不等於 `head`)。
若下下個節點存在，使用 `list_move()` 將當下節點 (`node`) 與下一個節點 (`node->next`) 交換，再將 `node` 指向下下個節點。
按照這個順序走訪並交換，直到下次執行會回到 `head` 或超前 `head`。
:::spoiler list_move()
```c
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
```
:::
- 當節點有奇數個，代表迴圈會因為 `node->next` 等於 `head` 而停下，此時最後一個落單的節點不會被交換。
- 當節點有偶數個，代表迴圈會因為 `node->next->next` 等於 `head` 而停下，在停下前，迴圈會交換每對的節點。
```c
/*
* Attempt to swap every two adjacent nodes.
*/
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node = head;
while (node->next != head && node->next->next != head) {
struct list_head *tmp = node->next->next;
list_move(tmp, node);
node = node->next->next;
}
}
```
### q_reverse
[LeetCode 206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
```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 *node = head;
struct list_head *tmp;
do {
tmp = node->next;
node->next = node->prev;
node->prev = tmp;
node = node->next;
} while (node != head);
}
```
### q_sort
#### bubble sort
效能分數當然拿不到 XD，留個紀錄。
```c
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
size_t len = q_size(head);
for (int i = 0; i < len; i++) {
struct list_head *li = head->next;
for (; li->next != head && li != head; li = li->next) {
element_t *q1 = list_entry(li, element_t, list);
element_t *q2 = list_entry(li->next, element_t, list);
if (strcmp(q1->value, q2->value) > 0) {
list_del(li);
list_add(li, li->next);
}
}
}
}
```
#### merge sort
```c
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
head->prev->next = NULL;
head->next = list_merge_sort(head->next);
struct list_head *prev = head;
struct list_head *tmp = prev->next;
while (tmp) {
tmp->prev = prev;
tmp = tmp->next;
prev = prev->next;
}
prev->next = head;
head->prev = prev;
}
// Doubly-linked list (not circular)
struct list_head *list_merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast = head->next;
struct list_head *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
struct list_head *l1 = list_merge_sort(head);
struct list_head *l2 = list_merge_sort(fast);
return merge(l1, l2);
}
```
參考 [案例探討: LeetCode 21. Merge Two Sorted Listssw34](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
struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
struct list_head *head = NULL;
struct list_head **ptr = &head;
struct list_head **node;
for (node = NULL; l1 && l2; *node = (*node)->next) {
element_t *q1 = list_entry(l1, element_t, list);
element_t *q2 = list_entry(l2, element_t, list);
node = strcmp(q1->value, q2->value) < 0 ? &l1 : &l2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
return head;
}
```
### 新增命令 `shuffle`
在 `qtest.c` 內新增函式 `do_shuffle()`，
```c
static bool do_shuffle(int argc, char *argv[]);
```
並在 `static void console_init()` 函式內新增 `shuffle` 命令。
```c
ADD_COMMAND(shuffle, " | Shuffle nodes in queue");
```
修改後就能使用 `help` 查詢到 `shuffle` 命令了：）
```diff
$ ./qtest
cmd> help
Commands:
# ... | Display comment
dedup | Delete all nodes that have duplicate string
dm | Delete middle node in queue
free | Delete queue
help | Show documentation
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
log file | Copy output to file
new | Create new queue
option [name val] | Display or set options
quit | Exit program
reverse | Reverse queue
rh [str] | Remove from head of queue. Optionally compare to expected value str
rhq | Remove from head of queue without reporting value.
rt [str] | Remove from tail of queue. Optionally compare to expected value str
show | Show queue contents
+ shuffle | Shuffle nodes in queue
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source file | Read commands from source file
swap | Swap every two adjacent nodes in queue
time cmd arg ... | Time command execution
web | Web server...
Options:
echo 1 Do/don't echo commands
error 5 Number of errors until exit
fail 30 Number of times allow queue operations to return false
length 1024 Maximum length of displayed string
malloc 0 Malloc failure probability percent
simulation 0 Start/Stop simulation mode
verbose 4 Verbosity level
```
實作 `shuffle` 演算法，一開始想要擺在 `queue.c`，但 `queue.h` 不能改，結果最後直接放在 `qtest.c` 的 `do_shuffle()` 內。
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
srand(time(NULL));
size_t len = q_size(head);
struct list_head *trace = head->prev;
while (--len) {
int index = rand() % (len + 1);
struct list_head *target = trace->prev;
while (index--)
target = target->prev;
list_del(trace);
list_add_tail(trace, target);
trace = trace->prev;
}
}
```
```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");
error_check();
set_noallocate_mode(true);
if (exception_setup(true)) {
if (l_meta.l && !list_empty(l_meta.l)) {
srand(time(NULL));
size_t len = q_size(l_meta.l);
struct list_head *trace = l_meta.l->prev;
while (--len) {
int index = rand() % (len + 1);
struct list_head *target = trace->prev;
while (index--)
target = target->prev;
list_move(trace, target);
trace = trace->prev;
}
}
}
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
### 整合 `tiny-web-server`
### 參考資料
[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
>:)
> cat scripts/pikachu.raw
Sign in with Wallet
Connect another wallet