# 2024q1 Homework1 (lab0)
contributed by < [Lowen0909](https://github.com/Lowen0909) >
## 開發環境
```
$gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 10
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
```
## 實作指定的佇列操作
### 測試結果
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
83/100,其中trace 6,17沒有通過
待解決的問題
* 多數function中list API使用的比例很低，可能導致維護或協作不易
* trace 17中說insert兩個function可能都不是常數時間或是實作錯誤
並且remove_head發生Segmentation fault
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
### q_free
原本是自己使用pointer和for loop去釋放所有節點
但會出現ERROR: Attempted to free unallocated block.
```diff
-struct list_head *tmp = head->next;
- while (tmp != head) {
- list_del_init(tmp);
- free(tmp);
- tmp = head->next;
- }
+element_t *del, *safe;
+ list_for_each_entry_safe (del, safe, head, list) {
+ list_del(&del->list);
+ free(del->value);
+ free(del);
+ }
+ free(head);
```
後來寫insert_head時想起應該要free的是包含list_head的整個結構體element_t,同時在insert時也會配置記憶體用來儲存複製的字串,也需要釋放。
並且在測試時發現上方寫法在trace 17會跑得非常慢，參考[vestata](https://github.com/vestata/lab0-c)的開發紀錄,改為使用API中的list_for_each_entry_safe就比較快速。
### q_insert_head,q_insert_tail
:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement
「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
原本<s>實做</s>時以為新加入的節點的字串是直接使用傳入function中字串，後來參考[vestata](https://github.com/vestata/lab0-c)才發現需要複製那段字串而不是直接使用所以使用strncpy。
```c
element_t *ele = malloc(sizeof(element_t));
char *s1 = malloc(strlen(s) + 1);
if (!s1 || !ele) {
free(s1);
free(ele);
return false;
}
strncpy(s1, s, strlen(s) + 1);
ele->value = s1;
struct list_head *new = &ele->list;
list_add_tail(new, head);
```
### q_remove_tail,q_remove_head
這邊也需要將移除的字串進行複製，但同時也需要檢查buffer空間是否足夠。
```c
size_t len = strlen(node->value);
int i = 0;
while (bufsize && len) {
*(sp + i) = *(node->value + i);
i++;
bufsize--;
len--;
}
if (bufsize == 0)
i--;
*(sp + i) = '\0';
```
### q_del_mid
改寫自[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List)
trace 2出現以下錯誤，猜測是沒有將insert時動態配置給字串的記憶體釋放
```
ERROR: Freed queue, but 2 blocks are still allocated
```
所以加入 `free(del->value)`。
```diff
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;
struct list_head** indir=&head->next;
for(struct list_head *fast=head->next; fast!=head && fast->next!=head;fast=fast->next->next)
indir=&(*indir)->next;
struct list_head*tmp=*indir;
list_del(tmp);
element_t *del=list_entry(tmp,element_t,list);
+ free(del->value);
free(del);
return true;
}
```
### q_delete_dup:
演算法是使用兩個指標，slow和fast，剛開始slow會指向list的第一個node,fast則是指向slow的下一個節點,接著會開始比較slow和fast指向的節點中的字串是否相等,如果相等,移除並釋放fast指向的節點,fast往下移動一個節點,並且slow不動，直到fast移動到一個和slow字串內容不相等的節點,再釋放slow指向的節點,並將slow指向和fast一樣的節點。不斷重複以上步驟就可以刪除所有重複的節點。
程式碼部份片段：
```c
if (cmp == 0) {
struct list_head *del;
while (fast != head &&
!strcmp(list_entry(fast, element_t, list)->value,
list_entry(slow, element_t, list)->value)) {
del = fast;
fast = fast->next;
list_del(del);
q_release_element(list_entry(del, element_t, list));
}
del = slow;
slow = slow->next;
list_del(del);
q_release_element(list_entry(del, element_t, list));
if (fast == head)
break;
}
```
:::warning
TODO: 研讀 List API，撰寫出更精簡的程式碼。
:::
### q_reverse
演算法是類似左右手交換彼此的內容,也就是交換每個list_head中的prev和next的內容
```c
struct list_head *tmp = head;
struct list_head *change = NULL;
do {
change = tmp->prev;
tmp->prev = tmp->next;
tmp->next = change;
tmp = tmp->prev;
} while (tmp != head);
```
### q_sort
參考作業要求中提供的連結[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
先把環狀鏈結串列的都變成一般的鏈結串列，再進行原始版本的merge sort。
有額外製作兩個helper function:mergesort(),mergeList()
### q_ascend,q_descend
參考LeetCode中的Hint,從串列尾端往回比較相鄰兩個節點的值,以降序為例,如果現在的節點比他的下一個節點的值還要小，就移除現在的節點，反之則保留。因為我們從尾端開始進行,所以每次比較只需要比較現在的節點和他的下一個節點的值，因為下一個節點以後的所有節點都已經降序排列。我是使用recursive的方法，從最後一個節點往前比較，有額外實做一個removeHelper()協助遞迴。但後來想到因為我們使用的串列是雙向鍊結，所以迭代法應該也是很容易可以實作出來。
### q_merge
參考 [jujuegg](https://github.com/jujuegg/lab0-c), [25077667](https://github.com/25077667/lab0-c/blob/dev/queue.c#L178), [YangYeh-PD](https://github.com/YangYeh-PD/lab0-c)，我了解到需要使用queue_contex_t這個結構以及它裡面的member代表的意義，不過在queue.h檔案中也有紀錄：
```c
typedef struct {
struct list_head *q;//指向queue串列中的其中一個queue
struct list_head chain;//把多個queue串起來的串列
int size;
int id;
} queue_contex_t;
```
程式碼片段，這邊和q_sort相同先把queue底層的串列從環狀改成一般的串列,接著呼叫mergesort中已經實作的mergeList函式。
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
```c
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
struct list_head *q1 = first->q;
q1->prev->next = NULL;
struct list_head *m1 = q1->next;
for (struct list_head *ptr = (first->chain).next; ptr != head;ptr = ptr->next) {
struct list_head *q2 = list_entry(ptr, queue_contex_t, chain)->q;
q2->prev->next = NULL;
m1 = mergeList(m1, q2->next, descend);
q2->next = q2;
q2->prev = q2;
}
```
Sign in with Wallet
Connect another wallet