# 2022q1 Homework1 (lab0)
contributed by < [Nomad1230](https://github.com/Nomad1230) >
## 實驗環境
```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
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
Vendor ID： GenuineIntel
Model name: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
CPU family： 6
Model： 158
Thread(s) per core： 1
Core(s) per socket： 1
Socket(s): 1
Stepping： 10
BogoMIPS: 4608.00
```
## 作業要求
> [lab0](https://hackmd.io/@sysprog/linux2022-lab0)
[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: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
* q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* q_swap: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
* q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
* q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
## 開發過程
### q_new
>Free ALL storage used by queue.
>No effect if q is NULL
:::spoiler **程式碼**
```c
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
// check if malloc success
if (!new)
return NULL;
else {
INIT_LIST_HEAD(new);
return new;
}
}
```
:::
呼叫 `malloc` 函式以配置記憶體給 `struct list head`，注意 `q_new` 函式的返回型態為 `struct list_head *`，而非 `element_t *`，因為該函式的目的是建立新的鏈結串列，但不實際儲存任何資料，`struct list head` 的次個節點，才開始儲存資料。
:::danger
請用通順的漢語書寫，並使用已明確規範的翻譯用語。考慮到日後在科技公司面試，現在你所撰寫的開發紀錄，其中可能會有一部分在面試場合出現。現在就練習用專業、精準，和有效率的方式來表達。
:notes: jserv
:::
程式碼中使用了 `list.h` 中的函式 `INIT_LIST_HEAD` ，功能為將節點的指標都指向自己。
```c
static inline void INIT_LIST_HEAD(struct list_head *head) {
head->next = head;
head->prev = head;
}
```
另外 `malloc` 在分配記憶體失敗時會回傳 NULL ，須使用條件判斷避免程式出錯。
---
### q_free
>Free ALL storage used by queue.
>No effect if q is NULL
:::spoiler **程式碼**
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, l) {
list_del_init(node);
q_release_element(list_entry(node, element_t, list));
}
free(l);
}
```
:::
程式碼中使用到巨集 `list_for_each_safe` ，此巨集的功能為走訪所有節點，並使用 `safe` 變數來暫存下一個節點，如此一來即可對當前節點進行任何操作且不使 linked list 的結構被破壞。
```c
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
另外使用到巨集 `list_entry`
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
`list_entry` 實際上另一個巨集 `container_of` 的包裝，功能為利用 struct 中的 member 去反向查詢整個 struct 的起始位置，以存取 struct 內的其他成員，詳細實作參考〈[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)〉。
```c
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
釋放記憶體則使用到 `queue.c` 中的函式`q_release_element` ，可以釋放 的記憶體。
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
---
### q_insert_head
>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.
:::spoiler **程式碼**
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
else {
new->value = strdup(s);
if (!new->value) {
free(new);
return false;
} else {
list_add(&new->list, head);
return true;
}
}
}
```
:::
程式碼使用到 `list.h` 中定義的 `list_add` ，注意到這邊的參數是使用 `&new->list` ，因為 `element_t` 結構中的 `list_head list` 並非指標型態，故用 & operator 取址。
```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;
}
```
---
### q_insert_tail
>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.
:::spoiler **程式碼**
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
else {
new->value = strdup(s);
if (!new->value) {
free(new);
return false;
} else {
list_add_tail(&new->list, head);
return true;
}
}
}
```
:::
跟 `q_insert_head` 的實作方式幾乎相同，只把 `list_add` 更改成 `list_add_tail` ，由於使用的 linked list 是 circular doubly-linked list，故 `list_add_tail` 跟 `list_add` 都一樣是 O(1) 的效率。
```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;
}
```
---
### q_remove_head
> 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.)
:::spoiler **程式碼**
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
else {
struct list_head *del = head->next;
list_del(head->next);
element_t *del_ele = list_entry(del, element_t, list);
if (sp) {
strncpy(sp, del_ele->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return del_ele;
}
}
```
:::
注意 remove 只有將節點移出 linked list ，並未釋放其記憶體。
程式碼使用到 `list.h` 中定義的函式 `list_del` ，會將欲刪除節點的前後兩個節點串接起來，並將自身的指標移除。
最後用 `list_entry` 取得被刪除的 entry 位置並將其回傳。
要注意在使用 `strncpy` 時並不會為複製好的字串加上 ``'\0'`` ，必須自行補上，以免出錯。
```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
}
```
---
### q_remove_tail
>Attempt to remove element from tail of queue.
Other attribute is as same as q_remove_head.
:::spoiler **程式碼**
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
else {
struct list_head *del = head->prev;
list_del(head->prev);
element_t *del_ele = list_entry(del, element_t, list);
if (sp) {
strncpy(sp, del_ele->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return del_ele;
}
}
```
:::
實作方式和 `q_remove_head` 雷同，只有把 `list_del` 的參數換成 `head->prev` 也就是最後一個節點。
---
### q_size
>Return number of elements in queue.
Return 0 if q is NULL or empty.
:::spoiler **程式碼**
```c
int q_size(struct list_head *head)
{
if (!head || head->next == head)
return 0;
int count = 0;
struct list_head *node;
list_for_each (node, head) {
count++;
}
return count;
}
```
:::
此函式用來計算 linked list 中的節點數目，使用巨集 `list_for_each` 走訪並使用變數 `count` 計次即可。
---
### q_delete_mid
>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 lm is NULL or empty.
:::spoiler **程式碼**
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || head->next == head)
return false;
element_t *del;
struct list_head **indir = &head;
struct list_head *temp = head->prev;
temp->next = NULL;
for (struct list_head *fast = head; fast && fast->next;
fast = fast->next->next)
indir = &(*indir)->next;
temp->next = head;
del = list_entry(*indir, element_t, list);
list_del_init(*indir);
q_release_element(del);
return true;
}
```
:::
由於要求為 delete ，所以除了將節點移除出 linked list 之外，還要釋放其記憶體。
實作方式參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94)中快慢指標的技巧來找到中間的節點並將其刪除，注意一開始將 `head->prev->next` 設為 NULL ，此舉目的是先將 linked list 環狀結構拆掉，以方便在走訪的過程中找到終止點，最後再回復即可。
---
### q_delete_dup
>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.
:::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 *node, *safe;
list_for_each_entry_safe (node, safe, head, list) {
// if &safe->list == head, safe->value will dereference a null pointer
if (&safe->list != head) {
if (node->value && safe->value) {
if (!strcmp(node->value, safe->value)) {
list_del(&node->list);
q_release_element(node);
}
}
}
}
return true;
}
```
:::
使用到巨集 `list_for_each_entry_safe` 走訪 linked list ，走訪的過程可以存取整個 entry ，並且使用 `safe` 變數來儲存下一個 entry ，因此可以對當前的 entry 進行操作。
```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))
```
由於此巨集可以在一次迴圈中存取兩個 entry ，且 `q_delete_dup` 實作的前提是 linked list 已經排序完畢，因此在走訪的過程中使用 `strcmp` 比較兩個 entry 中的元素，若資料相同則把當前的 entry 刪除，即可達成目的。
另外要注意由於 `safe` 走的比較快，所以在走訪到最後一個節點時 `safe` 已經回到 `head` 了，此時若執行 `strcmp` 時去存取 `safe` 中的資料會造成 deference NULL pointer ，因此加上 `if (&safe->list != head)` 來避免出錯。
---
### q_swap
> Attempt to swap every two adjacent nodes.
Ref: https://leetcode.com/problems/swap-nodes-in-pairs/
:::spoiler **程式碼**
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || head->next == head || head->next->next == head)
return;
for (struct list_head *node1 = head->next, *node2 = head->next->next;
node1 != head && node2 != head;
node1 = node1->next, node2 = node1->next) {
node1->prev->next = node2;
node2->prev = node1->prev;
node1->prev = node2;
node1->next = node2->next;
node2->next->prev = node1;
node2->next = node1;
}
}
```
:::
一開始實作的時候我的想法是將相鄰的兩個節點中的資料取出並交換，過程中使用 `strdup` 來複製字串，後來發現頻頻跳出錯誤訊息 "Calls to malloc disallowed" 。
檢查後發現原因出自於此專案的 function hooking ，在 `harness.h` 中會把 `strdup` 對應到 `test_strdup` 。
```c
/* Use undef to avoid strdup redefined error */
#undef strdup
#define strdup test_strdup
```
`harness.c` 中對 `test_strdup` 的定義如下:
```c
char *test_strdup(const char *s)
{
size_t len = strlen(s) + 1;
void *new = test_malloc(len);
if (!new)
return NULL;
return (char *) memcpy(new, s, len);
}
```
可以發現使用到另一個 hook function `test_malloc` ，檢查後發現偵錯的程式碼如下:
```c
void *test_malloc(size_t size)
{
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to malloc disallowed");
return NULL;
}
...
}
```
使用 noallocate_mode 關鍵字去搜尋專案中的程式碼，發現在 `qtest.c` 中的函式 `do_swap` 有以下操作:
```c
static bool do_swap(int argc, char *argv[])
{
...
set_noallocate_mode(true);
if (exception_setup(true))
q_swap(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
...
}
```
發現在此專案中 `queue.c` 大多的函式在執行前都會先被鎖定住，不可以再分配多餘記憶體。
於是只好尋求第二方案，在不多耗費記憶體的前提下來實作此函式。
最後採用的方式如下:
如圖所示，若要將 node0 及 node1 作交換，則將與這兩個節點所接觸到的6條指標進行重新排序。
排序完成後則可做到交換的效果。
用迴圈對每兩個節點都實施同樣的操作，即可完成此函式。
---
### q_reverse
>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.
:::spoiler **程式碼**
```c
void q_reverse(struct list_head *head)
{
if (!head || head->next == head)
return;
struct list_head *node = head, *temp;
head->prev->next = NULL;
head->prev = NULL;
while (1) {
temp = node->next;
node->next = node->prev;
node->prev = temp;
if (!node->prev)
break;
else
node = node->prev;
}
node->prev = head;
head->next = node;
}
```
:::
將每一個節點的 `prev` 跟 `next` 指標互相交換，當每一個節點的都交換完成，即可完成整個 linked list 反轉。
迴圈前會先把 linked list 中首尾相接的兩條指標設成 `NULL` ，讓 `while` 迴圈操作時可以順利終止並避免出錯，當完成之後再把頭尾的指標重新連結上。
交換前:
交換後:
(真的不知道要怎麼把 graphviz 的圖弄好看一點...)
---
### q_sort
>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.
這個函式我實作了兩次，兩次都是使用 merge sort ，第一次實作是參考<[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94)>中非遞迴的方式實作，會使用非遞迴的方式是因為考量到效能較佳。
實作時會先創建一個 `stack[10000]` 及 `lists[100000]` ，將一開始走訪的節點設為 `left` 並使用快慢指標的方式存取中間的節點設為 `right` ，後將 `left` 跟 `right` 存入 `stack` 中，當所有節點都存入 `stack` 後將 `stack` 中的元素全部 pop 到 `lists` 中，此時 `lists` 會是存放 `q_size` 個 linked list 的陣列，其中每一個 linked list 都只有一個節點。
最後使用 `MergeTwoList` 函式來比較並兩兩合併這些 linked list ，即可完成 merge sort 。
:::spoiler **第一次實作之程式碼**
```c
void q_sort(struct list_head *head)
{
if (!head || head->next == head || head->next->next == head)
return;
int top = 0;
int listsSize = 0;
struct list_head *stack[10000] = {NULL};
struct list_head *lists[100000] = {NULL};
stack[top] = head->next;
head->prev->next = NULL;
INIT_LIST_HEAD(head);
// divide to single node
while (top >= 0) {
struct list_head *left = stack[top--];
if (left) {
struct list_head *slow = left;
struct list_head *fast;
for (fast = left->next; fast && fast->next; fast = fast->next->next)
slow = slow->next;
struct list_head *right = slow->next;
slow->next = NULL;
stack[++top] = left;
stack[++top] = right;
} else {
stack[top]->prev = stack[top];
stack[top]->next = NULL;
lists[listsSize++] = stack[top--];
}
}
// merge K sorted lists
while (listsSize > 1) {
for (int i = 0, j = listsSize - 1; i < j; i++, j--)
lists[i] = mergeTwoLists(lists[i], lists[j]);
listsSize = (listsSize + 1) / 2;
}
struct list_head *node = lists[0];
while (node->next) {
node->next->prev = node;
node = node->next;
}
node->next = head;
head->next = lists[0];
lists[0]->prev = head;
head->prev = node;
}
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
node = (strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) < 0) ? &L1: &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
if (!L1) {
*ptr = L2;
return head;
}
if (!L2) {
*ptr = L1;
return head;
}
return head;
}
```
:::
但這樣的方式雖然能通過 make test 大部分的測試，唯獨 `trace-14-perf.cmd` 怎樣調整都測試不過，於是我檢查了其測資:
```
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih dolphin 1000000
cmd> it gerbil 1000000
cmd> reverse
cmd> sort
```
可以發現其輸入大筆數目的測資，造成了 stack overflow ，因此只好進行程式碼的改良。
最後修正的方案是使用 recursive function 來實作分割，用單純迭代的方式雖然較快較直觀，但缺點就是在記憶體的分配上相當不便。
原本也有考量用動態陣列的方式來改良，但遇到龐大資料的時候就很難處理，因為動態陣列需要連續的記憶體，且不容易根據測資數目來調整。
只好將其改回 recursion 的形式，最後也成功地通過 make test 的測試。
:::spoiler **最終程式碼**
```c
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
node = (strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) < 0)
? &L1
: &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((u_int64_t) L1 | (u_int64_t) L2);
return head;
}
static struct list_head *mergesort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head, *fast = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
slow->prev->next = NULL;
struct list_head *left = mergesort(head);
struct list_head *right = mergesort(slow);
return mergeTwoLists(left, right);
}
void q_sort(struct list_head *head)
{
if (!head || head->next == head || head->next->next == head)
return;
head->prev->next = NULL;
head->next = mergesort(head->next);
struct list_head *node = head->next;
node->prev = head;
while (node->next) {
node->next->prev = node;
node = node->next;
}
node->next = head;
head->prev = node;
}
```
:::
## 比較自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
### 運作原理
首先在實作核心程式碼之前，先嘗試理解其運作原理，詳細運作流程我是參考< [freshLiver](https://hackmd.io/@freshLiver/2022q1-hw1) >同學的筆記來理解，但也不算理解的相當透徹，故以下只記錄自己理解的部分。
[Linux 核心程式碼](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)針對硬體層面的考量進行了優化，一般在實作 merge sort 的時候會採用 fully-eager 的方式來合併，fully-eager 的方式會把相同數目的 list 立即進行合併，比如說現在有節點數分別為 [1,1,2,4] 的 list ，那麼它會被合併成 [2,2,4]->[4,4]->[8] 。
但 Linux 核心所實作的 `list_sort` 採用了 not-fully-eager 的方式來合併 list ，當資料數目達到2:1時才進行合併，也就是說當目前有2個數目為 2^k 的 pending list 時，會在繼續等待到有 2^k 筆資料進入才進行合併，比如說目前有 [2,4] 的 list ，其合併的過程會是: [2,4]->[1,2,4]->[1,1,2,4]->[1,2,2,4]->[1,1,2,2,4]->[1,2,2,2,4]->[1,2,4,4]
### cache thrashing
會有以上實作的原因可以參考核心程式碼中的註解:
```
* 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.
```
由註解中可以理解到這樣 2:1 merge 的方式可以減少 cache thrashing 的情形，那麼何謂 cache thrashing 呢?參考示意圖:
記憶體中會有多個區塊共用一部分 cache 的情形，以圖中為例， m1 及 m5 就共用了 c1 這部分的 cache ，當程式先使用到 m1 時 m1 的資料就會被搬進 c1 ，這時如果程式又需要 m5 的資料， 這時就會把 m5 的資料搬進 c1 並將原本的資料覆蓋，這樣的機制就稱為 cache thrashing 。
::: warning
TODO 理解為何 2:1 merge 會減少 cache thrashing
:::
### likely 、 unlikely
另外 likely 及 unlikely 機制也跟硬體方面的優化有關，例如 source code 中有以下程式碼:
```c
...
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
...
if (unlikely(!++count))
cmp(priv, b, b);
```
這兩個巨集的定義詳見<[likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/)>。
這個機制也跟 cache 有關，當我們要從記憶體的特定位置存取資料時，這個位置附近的資料也極有可能一同被存取，此特性稱為 spatial locality 。
因此如果把使用機率高的資料擺在一起的話，就有很高的機率被一同被存取到 cache 中，因而減少 cache miss 的機率。
### 將 list_sort.c 實作加入專案
首先修改 `qtest.c` ，在 `do_dm` 中加入命令:
```c
ADD_COMMAND(
linuxsort,
" | Use Linux kernel built-in function to sort list");
```
加入 `do_linuxsort` :
```c
bool do_linuxsort(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Calling sort on null queue");
error_check();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling sort on single node");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_linuxsort(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
bool ok = true;
if (l_meta.size) {
for (struct list_head *cur_l = l_meta.l->next;
cur_l != l_meta.l && --cnt; cur_l = cur_l->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
element_t *item, *next_item;
item = list_entry(cur_l, element_t, list);
next_item = list_entry(cur_l->next, element_t, list);
if (strcasecmp(item->value, next_item->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
show_queue(3);
return ok && !error_check();
}
```
然後將 `list_sort.c` 的程式碼直接複製貼到 `queue.c` ，進行一些微調就可以使用了。
記得新增定義:
```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 *);
```
### 效能比較
自己手動輸入測資
```
cmd> option fail 0
cmd> option malloc 0
cmd> new
cmd> ih dolphin 1000000
cmd> it gerbil 1000000
cmd> reverse
cmd> time sort
Delta time = 0.995
cmd> reverse
cmd> time linuxsort
Delta time = 0.651
```
```
cmd> option fail 0
cmd> option malloc 0
cmd> new
cmd> ih a 200000
cmd> it b 200000
cmd> it c 200000
cmd> it d 200000
cmd> it e 200000
cmd> it f 200000
cmd> it g 200000
cmd> it h 200000
cmd> it i 200000
cmd> it j 200000
cmd> reverse
cmd> time sort
Delta time = 0.967
cmd> reverse
cmd> time linuxsort
Delta time = 0.635
```
可以看到效率約差距30%，相當之多。
## 加入 shuffle 功能
在 `qtest.c` 中加入命令:
```c
ADD_COMMAND(
shuffle,
" | Use Fisher and Yates algorithm to shuffle list");
```
加入 `do_shuffle` :
```c
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: Calling shuffle on null queue");
error_check();
int cnt = q_size(l_meta.l);
if (cnt < 2)
report(3, "Warning: Calling shuffle on single node");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
bool ok = true;
show_queue(3);
return ok && !error_check();
}
```
在 `queue.c` 新增函式 `q_shuffle` :
```c
void q_shuffle(struct list_head *head)
{
struct list_head *select = head;
for (int size = q_size(head), rnd; size > 0; size--) {
rnd = rand() % size + 1;
do {
select = select->next;
rnd--;
} while (rnd > 0);
list_del_init(select);
list_add_tail(select, head);
select = head;
}
}
```
演算法參考<[Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)>。
假設 linked list 中一共有 n 個節點，第一次迴圈取範圍 1~n 的亂數 k ，將第 k 個節點移出 linked list 並將其插入到最尾端，第二次迴圈取 1~n-1 的亂數以此類推，直到所有的節點都被選取即完成 shuffle 。
## 加入 web 功能
Sign in with Wallet
Connect another wallet