# 2023q1 Homework1 (lab0)
contributed by < `knaw0128` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.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): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping: 13
CPU MHz: 2591.998
BogoMIPS: 5183.99
Hypervisor vendor: Microsoft
Virtualization type: full
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
```
## 開發過程
:::danger
說好的進度呢？
:notes: jserv
:::
:::success
已於下方補上目前進度
:::
### q_free
:::danger
注意書寫規範：中英文間用一個半形空白區隔。
:notes: jserv
:::
目前的程式碼如下，以 `list.h` 中提及 <s>較安全的</s> 刪除佇列中的節點也不會影響走訪順序的方式一邊走訪佇列中元素並一邊 free 掉 element 及 node 中的字串
:::warning
為何「較安全」？
改進你的漢語表達。
:notes: jserv
:::
```c
if (!head) {
return;
}
struct list_head *cursor;
struct list_head *tmp;
list_for_each_safe (cursor, tmp, head) {
free(list_entry(cursor, element_t, list)->value);
free(list_entry(cursor, element_t, list));
}
free(head);
```
### q_insert_head
會一步一步檢查目前情況並 allocate 記憶體，接著利用 `memcpy` 複製字串內容，最後再透過` list_add` 的方式把 node insert 到 linkedlist 的頭。開發時沒有 free 掉 node 中的字串，經過測試後發現並修正
```c
if (!head) {
return false;
}
element_t *newNode = malloc(sizeof(element_t));
if (!newNode) {
return false;
}
newNode->value = malloc(sizeof(char) * strlen(s) + 1);
if (!(newNode->value)) {
free(newNode);
return false;
}
memcpy(newNode->value, s, sizeof(char) * strlen(s) + 1);
INIT_LIST_HEAD(&newNode->list);
list_add(&newNode->list, head);
return true;
```
### q_insert_tail
大致上和 q_insert_head 相同，只有在倒數第三行改成使用`list_add_tail`。因此也和 q_inset_head 遇到類似的問題，在本機測試時間複雜度時一樣會出現時過時不過的情形，仍在利用工具嘗試找出原因。
```c
if (!head) {
return false;
}
element_t *newNode = malloc(sizeof(element_t));
if (!newNode) {
return false;
}
newNode->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
if (!(newNode->value)) {
free(newNode);
return false;
}
memcpy(newNode->value, s, sizeof(char) * strlen(s) + 1);
INIT_LIST_HEAD(&newNode->list);
list_add_tail(&newNode->list, head);
return true;
```
### q_remove_head
先檢查 `sp` 是否為 null 再使用 memcpy 的方式搬動字串。起初是自己實作刪除 node 的方式，後來發現有 `list_del` 可以用之後就換成 linux kernel style 的寫法了。
```c
if (!head || list_empty(head)) {
return NULL;
}
element_t *now = list_entry(head->next, element_t, list);
if (sp) {
memcpy(sp, now->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(head->next);
return now;
```
### q_remove_tail
和上面 q_remove_head 類似，不同處只有把操作的 list_head pointer 換成佇列中的最後一個。且移除 node 的部分在開發時也有遇到相同問題，並且已經修正完成
```c
if (!head || list_empty(head)) {
return NULL;
}
element_t *now = list_entry(head->prev, element_t, list);
if (sp) {
memcpy(sp, now->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(head->prev);
return now;
```
### q_size
寫法和教授在文件中提及的範例相同
```c
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
```
### q_delete_mid
利用一快一慢的兩個 pointer 去走訪佇列中的每個 node，兩個 pointer 的移動速度會是 2:1。因此當快的 pointer 走到終點時，慢的 pointer 會恰好在中間的 node。
開發時不知道有 `list_del` 可以用，之後有修正掉了。
```c
if (!head || list_empty(head)) {
return false;
}
int step = 0;
struct list_head *fast = head->next;
struct list_head *slow = head->next;
while (fast != head) {
if (step) {
slow = slow->next;
}
fast = fast->next;
step = 1 - step;
}
list_del(slow);
free(list_entry(slow, element_t, list)->value);
free(list_entry(slow, element_t, list));
return true;
```
### q_delete_dup
一開始開發時以為只要把重複的 node 刪到只剩下一個就好，經過測試後才發現需要全部移除。
也因為需要全部移除，所以在刪掉最後一個 node 時需要思考一下才能優雅完成。
第一次嘗試的 code 如下，在刪除重複字串時會需要額外處理最前面的 node。此外在移動目前位置時也需要注意是否在尋找相同字串的 node 過程中就已經到達佇列的終點。
可以看出這段 code 有點冗長且不易懂，也有好幾行重複的 code ，因此應該可以有改進的地方。
```c
if (!head) {
return false;
}
struct list_head *pre = NULL;
struct list_head *safe;
struct list_head *cursor;
list_for_each_safe (cursor, safe, head) {
bool duplicated = false;
while (pre && cursor != head &&
!strcmp(list_entry(pre, element_t, list)->value,
list_entry(cursor, element_t, list)->value)) {
list_del(cursor);
free(list_entry(cursor, element_t, list)->value);
free(list_entry(cursor, element_t, list));
cursor = safe
safe = safe->next;
duplicated = true;
}
if (duplicated) {
list_del(pre);
free(list_entry(pre, element_t, list)->value);
free(list_entry(pre, element_t, list));
}
if (cursor == head) {
break;
}
pre = cursor;
}
return true;
```
之後改進實作方式成先紀錄 `cursor` 的初始位置，接著利用另個 pointer `now` 找到擁有相同字串的 node 的最後一個。最後利用 while 的條件檢查有相同字串的 node 數量是否只有一個 (`now` 和 `cursor` 相同且 `cursor` 沒有移動過)，若超過一個則會全部都從佇列中移除並 free 掉。
在 while 中的 if 便是用來判斷是否已經走到最後一個 node 的。
#### <s>最新版本</s>
```c
if (!head) {
return false;
}
struct list_head *cursor;
list_for_each(cursor, head) {
struct list_head *now = cursor->next;
struct list_head *initCursor = cursor;
char *strNow = list_entry(cursor, element_t, list)->value;
while (now != head && !strcmp(strNow, list_entry(now, element_t, list)->value)){
now = now->next;
}
now = now->prev;
while (now != cursor || cursor != initCursor) {
struct list_head *toDel = cursor;
bool end = (now == cursor);
cursor = cursor->next;
list_del(toDel);
free(list_entry(toDel, element_t, list)->value);
free(list_entry(toDel, element_t, list));
if (end) {
cursor = cursor->prev;
break;
}
}
}
return true;
```
### q_swap
因為做的事情和 `q_reverseK()` 在 k=2 時相同，所以在判斷完是 valid 的 case 後會直接呼叫 `q_reverseK()` with k = 2
```c
if (!head || q_size(head) < 2) {
return;
}
q_reverseK(head, 2);
```
### q_reverse
目前的 code 如下，要反轉一個 doubly-linked list 只需要把包含 head 的所有 node 的 `prev` 和 `next` 對調即可。
```c
struct list_head *safeNext;
struct list_head *now;
list_for_each_safe (now, safeNext, head) {
struct list_head *tmp = now->prev;
now->prev = now->next;
now->next = tmp;
}
struct list_head *tmpHead = head->prev;
head->prev = head->next;
head->next = tmpHead;
```
### q_reverseK
目前的 code 如下，會利用三個 pointer 控制需要翻轉的範圍。翻轉的方式同樣是交換 `prev` 和 `next`，但最後要設定好翻轉範圍前後的 node 的 `prev` 和 `next`。
<s>
可以發現 code 的部分非常冗長，需多細節應該可以有更好的實作方式，這會是我需要改進的部分
</s>
:::danger
避免只說「需要改進」，做法呢？
:notes: jserv
:::
```c
int listSize = q_size(head);
if (!head || listSize < 2 || k < 1) {
return;
}
else if (k >= listSize) {
q_reverse(head);
}
int idx = 0;
struct list_head *cursor;
struct list_head *front = head;
struct list_head *back = head;
while (idx < listSize) {
cursor = front->next;
for (int i = 0; i < min(k, listSize - idx); i++) {
if (i == min(k, listSize - idx) - 1) {
back = cursor->next;
}
struct list_head *tmp = cursor->prev;
cursor->prev = cursor->next;
cursor->next = tmp;
cursor = cursor->prev;
}
front->next->next = back;
back->prev->prev = front;
struct list_head *tmpFront = front->next;
front->next = back->prev;
back->prev = tmpFront;
front = back->prev;
idx += k;
}
```
### q_descend
對於每個 node 都會檢查下個 node 的字串是否比當前的大，若是的話則需要刪除並回到前一個 node 檢查是否因為移除 node 而造成遞增的排序。最開始開發時沒有注意到前面的 node 可能會因為刪除後面的 node 而需要重新檢查，在測試後才有所發現。
```c
if (!head) {
return 0;
}
struct list_head *safe;
struct list_head *cursor;
for (cursor = head->next, safe = cursor->next;
safe != head && cursor != head; cursor = safe, safe = safe->next) {
if (strcmp(list_entry(cursor, element_t, list)->value,
list_entry(safe, element_t, list)->value) < 0) {
safe = cursor->prev;
list_del(cursor);
free(list_entry(cursor, element_t, list)->value);
free(list_entry(cursor, element_t, list));
}
}
return q_size(head);
```
:::danger
開發紀錄著重於你的想法、中間遭遇到的問題，程式碼只是輔助。避免張貼完整程式碼。
改進你的漢語表達，這份筆記可能會被你日後的主管和同事看到。
:notes: jserv
:::
### q_merge
起初不太知道應該如何拿到各個佇列的 entry ，經過翻找資料後才發現各個 queue 會由 `queue_contex_t` 管理。在合併時先取出第一個 queue 的 head 作為新的 head，接著把所有佇列的 `queue_contex_t` 中的 `q` 都先指到佇列中的第一個元素，同時也把每個佇列中最後一個元素的 next 改為 NULL。
每次新增元素到合併完的佇列時都需要走過所有佇列並找出最小者，將其新增完後移動其 `queue_contex_t` 的 `q` 到下個元素，如此往復直到所有 `queue_contex_t` 中的 `size` 都變為0為止。
#### 第一次修改
在利用 valgrind 檢查時發現那些被合併的佇列的 head 沒有被 free 掉，而在 `do_merge()` 中處理這部分的方式是呼叫 `q_free()` free 掉各個 `queue_contex_t` 的 `q`
實作方式改成在將所有佇列的 `queue_contex_t` 中的 `q` 都先指到佇列中的第一個元素後，把各佇列的 head 的 prev 和 next 都指向 head，且其他 node 的 prev 和 next 不變。如此在 `q_free()` 時就只會刪除到 head 而不會刪除到已經被合併的 node，而`queue_contex_t` 中的 `q` 在合併完成後也會走回原本的 head。
### q_sort
因為需要 $O(\log N)$ 的時間複雜度，因此我選擇使用 merge sort 並以遞迴的方式實作。
此外我另外寫了兩個 function 方便我實作 merge sort。
一個 function 會負責將兩個以排序好的 queue 合併成一個，且合併完的 queue 也會是排序好的
因為規定不能 allocate 記憶體，所以需要透過修改各個 node 的 `prev` 和 `next` 來改變 queue 中元素的順序。因此對於傳入的 list_head 會需要紀錄長度方便觀察是否已經處理完成。
另一個 function 則負責將收到的佇列平均拆分成兩部分後遞迴呼叫，直到長度為 1 時會直接回傳。而收到遞迴呼叫完收到已排好的兩個佇列後會利用上面提到的 function 將兩 queue 合併起來再回傳。藉由如此方式就能達到 $O(N \log N)$ 的時間複雜度。
而 `q_sort` 只有將佇列除了 head 的部分傳入上述的 function 做排序後，再把 head 指向排序好的佇列。
實作時有許多細節會需要注意，尤其是佇列尾端的 pointer 也需要管理好，否則接回去 head 時可能會讓 pointer 指去不該指的地方。
## 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
以上的實作方式在開啟 Sanitizer 後發現存在錯誤，詳細錯誤內容如下
在 remove head/tail 時會利用 `memcpy` 複製字串內容，我在原先的作法是直接複製大小為 bufsize - 1 的記憶體給 sp 。但字串可能遠沒有這麼長，所以直接複製這麼多會將後面沒有 allocate 的部分也一併複製過去。而在印出字串時因為只會印到 `\0` 所以不會出現錯誤訊息，但 Sanitizer 會偵測到這項的錯誤。在將要複製的記憶體大小設定成 `min(bufSize, strlen(node->value))` 後就可精準複製剛剛好的大小不會觸發錯誤了
重新跑過後其他部分也沒有跳出錯誤訊息
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
執行 `make valgrind` 後跳出非常多錯誤，都是有 heap 上的記憶體仍可以被 access 到的問題，且從第一筆檢查 insert/remove head 的測資就出現錯誤。在檢查完 `queue.c` 後我想我實作的部分應該沒有甚麼問題才對，因此把目光轉向 `qtest.c`
因為是有記憶體沒有被 free 掉的錯誤，因此我從 `do_remove()` 開始檢查，可以發現真正把記憶體 free 掉的部分是交給 `q_release_element()` 來做，但檢查後也沒有發現有什麼問題。
參考了 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-lab0) 後發現問題是在於 `do_quit()` 在開頭直接回傳 true 且沒有 free 任何的記憶體
而在回傳 true 下方的程式碼有將所有的 queue 都 free 掉，因此只需要將 `do_quit()` 中第一行直接回傳 true 的部分拿掉就可以順利通過前兩筆測試案例
但修正後第三項測試案例仍然無法通過，測試的 function 有中 reverse 和 merge 是前面的測試案例沒有測過的，而只有 merge 會牽涉到會出現用不到的記憶體，也就是除第一個外的 queue 的 head。
檢查 `do_merge()` 後發現 `do_merge()` 會在執行完 `q_merge()` 後把除了第一個外的所有 queue 的 head 都 free 掉，但我在實作 `q_merge` 時在合併完成後第一個外的 queue 的 head 都會設成 NULL。也因為如此才會導致上述<s>測資</s> --- 測試案例無法通過。
修正 `q_merge()` 後就解決了
:::warning
test case 和 test data 不同，在 `lab0-c` 中，我們著重於前者，於是你該說「測試案例」。
:notes: jserv
:::
## 提供新的命令 shuffle
參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法後我決定以其 modern 的方式實作
因為需要在當前 node 之前隨機取一個作為互換位子的對象，如果每次都從佇列的開頭走過去會導致時間複雜度達到 $O(N^2)$。所以我採取使用 `malloc` 安排一段空間存放佇列中各節點的指標，以提升之後交換時存取節點的速度。而這些暫存的指標在經過 Fisher-Yates shuffle 後會再依照其在連續記憶體中的順序重新被加入佇列。
我使用 `rand()` 作為隨機抽取和當前節點交換位置的方式，當處理第 $i$ 個節點時會和位於`rand() % i` 的節點做交換
:::info
TODO : 比較亂數產生器的品質
:::
Sign in with Wallet
Connect another wallet