# 2024q1 Homework1 (lab0)
contributed by < `Leo5307` >
### Reviewed by `lintin528`
這次實作中有很多需要去走訪每個節點的情況，都可以適當的選用 "list.h" 中定義好的巨集來使用，這樣可以避免在 `while` 迴圈中若發生一些問題，如 `next` 的指標設定有誤、 `current` 與 `tmp` 導致稍微難以整理的時候，程式碼會難以維護。
在 `q_reverse` 中，我沒想過可以將每個節點的 `next` 與 `prev` 反轉來完成整個佇列的反轉，我的作法是從 `head` 處走訪每個節點後使用 `list_move` 移至佇列的頭部來完成反轉，相比起 `list_move` 需要進行 `list_del` 再 `list_add` ，你的做法可以省去很多不必要的步驟。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 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): 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) i5-8265U CPU @ 1.60GHz
Stepping: 11
CPU MHz: 1800.000
CPU max MHz: 3900.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
:::danger
說好的進度呢？
:::
## 針對佇列操作的程式碼實作
### q_free
一開始的實作如下：
```c
void q_free(struct list_head *head)
{
element_t *entry;
element_t *safe;
if (head) {
list_for_each_entry_safe (entry, safe, head, list) {
list_del(&(entry->list));
free(entry);
}
free(head);
}
}
```
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)；
:::
在初步完成 `q_insert_head` 及 `q_insert_tail` 後 發現以下錯誤：
``` shell
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 13 blocks are still allocated
--- trace-11-malloc 0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
ERROR: Freed queue, but 25 blocks are still allocated
--- trace-12-malloc 0/6
```
發現是由於沒有釋放到 ```entry->value``` 的空間才導致錯誤，因此進行修改：
```c
void q_free(struct list_head *head)
if (head) {
list_for_each_entry_safe (entry, safe, head, list) {
list_del(&(entry->list));
+ free(entry->value);
free(entry);
}
free(head);
+
}
}
```
:::danger
使用 `git diff` 或 `diff -u` 命令來產生程式碼之間的變異列表，不要憑感覺填入，注意位移量。
:::
:::warning
在這邊釋放的時候可以透過 "queue.h" 內定義的 `q_release_element` ，在這之內定義的 `test_free` 有更完整的記憶體處理，且也不需要分別將 element_t 內的各項元素拆開處理。
:notes: lintin528
:::
### q_size
參考[牛刀小試](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a#%E7%89%9B%E5%88%80%E5%B0%8F%E8%A9%A6)，利用``` list_for_each ```走訪所有節點，以此計算佇列長度
```c
int q_size(struct list_head *head)
{
if (!head) return 0;
int len = 0;
struct list_head *cursor;
list_for_each (cursor, head)
len++;
return len;
```
### q_delete_mid
一開始參考[快慢指標]()
```c
while (fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
```
但發現一直跳出
``` shell
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
```
發現是由於使用了**雙向環狀鏈結串列**作爲基底，用上述程式碼會導致無限迴圈，因此改用較直覺的做法：
:::warning
我的做法是將終止條件改為 `fast != head && fast->next != head` ，這樣可以因應環狀鏈結串列最後一個元素的 `next` 不為 `NULL` 的狀況。
:notes: lintin528
:::
```c
if (!head) {
return false;
}
int size = q_size(head);
int mid = 0;
if (size % 2 == 0) {
mid = size / 2 - 1;
} else {
mid = size / 2;
}
struct list_head *cursor;
int len = 0;
list_for_each (cursor, head) {
if (len == mid) {
break;
} else {
len++;
}
}
element_t *del_node = container_of(cursor, element_t, list);
list_del(cursor);
free(del_node->value);
free(del_node);
return true;
```
:::warning
使用 List API 改進上述程式碼。
:::
### q_swap
由於這題需要兩兩互換，因此考慮兩種情況：
<s>
- A,B關係互換
- 
- Ｃ,D,E,F關係互換
- 
</s>
:::danger
使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記。
:::
```c
prev_list = first_list->prev;
next_list = second_list->next;
// in the box
first_list->prev = second_list;
second_list->next = first_list;
// outside the box
first_list->next = next_list;
second_list->prev = prev_list;
next_list->prev = first_list;
prev_list->next = second_list;
```
:::warning
使用 List API 改進上述程式碼。
:::
### q_sort
> [commit 850a705](https://github.com/Leo5307/lab0-c/commit/850a70547aa54947b6268894a394c41863319d40)
參考自[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)與[examples/quick-sort.c](https://github.com/sysprog21/linux-list/blob/master/examples/quick-sort.c)中關於 Quick Sort 的實作。
:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
隨後發現Quick Sort無法達成所要求的時間復雜度，因此改成隨機選擇 pivot
``` cpp
{
struct list_head list_less, list_greater;
element_t *item = NULL, *is = NULL;
-
+ int count = 0;
+ srand(time(0));
if (list_empty(head) || list_is_singular(head))
return;
// int size = q_size(head);
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
- element_t *pivot = list_last_entry(head, element_t, list);
+ int random = rand() % q_size(head);
+ element_t *pivot = list_first_entry(head, element_t, list);
+ list_for_each_entry(item,head,list){
+ if(count == random){
+ pivot = item;
+ break;
+ }
+ }
```
但還是不能通過測試，因此轉用 merge sort
``` cpp
void merge(struct list_head *l1, struct list_head *l2,struct list_head *head){
// printf("zero");
while (!list_empty(l1) && !list_empty(l2)){
element_t *l1_node = container_of(l1->next,element_t,list);
element_t *l2_node = container_of(l2->next,element_t,list);
if(strcmp(l1_node->value,l2_node->value) <= 0){
list_move_tail(l1->next,head);
}
else{
list_move_tail(l2->next,head);
}
}
if(!list_empty(l1)){
list_splice_tail_init(l1,head);
}
if(!list_empty(l2)){
list_splice_tail_init(l2,head);
}
}
void mergeSortList(struct list_head *head){
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *slow = head->next;
struct list_head *fast = head->next->next;
while (fast != head && fast->next != head){
slow = slow->next;
fast = slow->next->next;
}
LIST_HEAD(l_head);
LIST_HEAD(r_head);
list_splice_tail_init(head,&r_head);
list_cut_position(&l_head,&r_head,slow);
mergeSortList(&l_head);
mergeSortList(&r_head);
merge(&l_head,&r_head,head);
}
void q_sort(struct list_head *head, bool descend){
mergeSortList(head);
if(descend){
q_reverse(head);
}
}
```
其中我發現將上述程式碼中的
``` cpp
struct list_head *slow = head->next;
struct list_head *fast = head->next->next;
while (fast != head && fast->next != head){
slow = slow->next;
fast = slow->next->next;
}
```
改成
``` cpp
struct list_head *slow = head, *fast = head;
do {
fast = fast->next->next;
slow = slow->next;
} while (fast != head && fast->next != head);
```
時才能通過 trace-14,但是據我的理解這兩者是邏輯等價的，因此猜測可能兩者在執行時的時間復雜度有所不同。
### q_reverse
透過 ```curr``` 來記錄當前指標，走訪每個節點
```c
void q_reverse(struct list_head *head) {
if (head && !(list_is_singular(head))) {
struct list_head *curr = head;
struct list_head * tmp;
do {
tmp = curr->next;
curr->next = curr->prev;
curr->prev = tmp;
curr = tmp;
}while((curr != head));//terminate
}
}
```
### q_merge
透過將所有的佇列合併到第一個佇列後再使用ｑ_sort 即可實現。
### 檢查
目前雖把函數都寫完了卻還沒有達到100發現trace-06，08，17 都沒成功
其中
``` shell
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-08-robust 0/6
```
發現是由於```q_remove_head```和```q_remove_tail```沒有處理到空佇列而導致，因此加入後就解決了問題。
```
if (!head || list_empty(head)) {
return NULL;
}
```
trace-06
則是由於原先``` reverseK```的邏輯會在有多組時將後面組別放在更前面的位置，因此修改成：
``` cpp
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
- if (list_empty(head) || k <= 1 || list_is_singular(head)) {
+ if (!head || list_empty(head) || k <= 1 || list_is_singular(head)) {
return;
}
struct list_head *cursor;
struct list_head *safe;
struct list_head new_queue;
+ struct list_head tmp_queue;
struct list_head *new_queue_head = &new_queue;
+ struct list_head *tmp_queue_head = &tmp_queue;
struct list_head **start_node = &head;
// struct list_head tmp_queue, *tmp_head = head, *safe, *node;
INIT_LIST_HEAD(new_queue_head);
+ INIT_LIST_HEAD(tmp_queue_head);
int count = 1;
list_for_each_safe (cursor, safe, head) {
if (count == k) {
- list_cut_position(new_queue_head, *start_node, cursor);
- q_reverse(new_queue_head);
- list_splice_init(new_queue_head, head);
+ list_cut_position(tmp_queue_head, *start_node, cursor);
+ q_reverse(tmp_queue_head);
+ list_splice_tail_init(tmp_queue_head, new_queue_head);
start_node = &(safe->prev);
count = 0;
}
count++;
}
+ if(!list_empty(head)){
+ list_splice_tail_init(head,new_queue_head);
+ }
+ list_cut_position(head,new_queue_head,new_queue_head->prev);
+
}
```
但上述程式碼稍顯冗長，還有改進的空間
目前分數爲95分，問題出在 trace-17
參考論文[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)和[vax-r](https://github.com/vax-r/lab0-c/blob/master/queue.c)同學的做法，成功通過```q_insert_head```和```q_insert_tail```的測試。
### 再次檢查
發現```q_remove_tail```和```q_remove_head```之所以不成功是因爲在使用```strnpy```時都直接給```bufsize - 1```的大小，導致空間不足，因此做了以下修改：
``` cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
return NULL;
}
element_t *remove_node = list_first_entry(head, element_t, list);
+ list_del(&(remove_node->list));
if (sp && remove_node) {
- strncpy(sp, remove_node->value, bufsize - 1);
- sp[bufsize - 1] = '\0';
- list_del(&remove_node->list);
- // printf("%s", sp);
+ size_t size;
+ if (strlen(remove_node->value) < (bufsize - 1)) {
+ size = strlen(remove_node->value);
+ } else {
+ size = bufsize - 1;
+ }
+ strncpy(sp, remove_node->value, size);
+ sp[size] = '\0';
}
```
其中也發現了將```list_del(&(remove_node->list))```放在原先的位置（```strnpy```下）會導致在 trace-17 時出現```Segmentation fault occurred. You dereferenced a NULL or invalid pointer``` 但在其他的測試，還有運用```./qtest```時都不會有問題，因此還不知道爲什麼會這樣
Sign in with Wallet
Connect another wallet