# 2023q1 Homework1 (lab0)
contributed by < [tintinjian12999](https://github.com/tintinjian12999) >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ ls cpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 43 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
每核心執行緒數： 2
每通訊端核心數： 4
Socket(s): 1
NUMA 節點： 1
供應商識別號： AuthenticAMD
CPU 家族： 23
型號： 24
Model name: AMD Ryzen 7 3750H with Radeon Vega Mobile Gfx
製程： 1
Frequency boost: enabled
CPU MHz： 1700.000
CPU max MHz: 2300.0000
CPU min MHz: 1400.0000
BogoMIPS: 4591.40
虛擬： AMD-V
L1d 快取： 128 KiB
L1i 快取： 256 KiB
L2 快取： 2 MiB
L3 快取： 4 MiB
NUMA node0 CPU(s)： 0-7
```
## Reviewed by `WeiHongWi`
* 若 q_delete_mid , q_delete_dup 能夠畫圖來視覺化你的想法,會更加直觀
* 缺少利用 Valgrind 來評估程式效能
* 每個 function 的描述我認為非常詳盡,但能逐步紀錄開發和紀錄自己的想法,而不是一次寫完再解說我認為可以幫助提昇自己的思考模式
# 作業要求
詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
* q_new: 創一個空的 queue
* q_free: 釋放掉一個 queue
* q_insert_head: 在 head 插入一個 element (LIFO)
* q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
* q_remove_head: 把 head 的 element 移除
* q_size: return佇列的大小
* q_reverse: 將佇列反轉，不配置或釋放任何的 element
* q_sort: 將佇列由小排到大, sort by nature sort
# 開發過程
## q_new
:::danger
注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！
:notes: jserv
:::
安排新的記憶體空間給新的佇列(命名為 head )，且 `queue.h` 裡提到初始化 prev 與 next 兩個指標指向自身，且如果記憶體配置失敗則回傳 NULL 。
```c
struct list_head *q_new()
{ struct list_head *head = malloc(sizeof(struct list_head));
if(head == NULL)
return NULL;
head->previous = head;
head->next = head;
return head;
}
```
> 後來發現 list.h 裡有 `INIT_LIST_HEAD` 可用，程式碼調整如下:
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head == NULL)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
:::warning
1. `sizeof(struct list_head)` 可改為 `sizeof(*head)`
2. `if (head == NULL)` 可改為 `if (!head)`
:notes: jserv
:::
## q_free
清除掉所有的佇列空間，根據`queue.h`敘述，如果 header 是 NULL ，則不須做任何操作，根據[list_for_each_entry_safe](https://biscuitos.github.io/blog/LIST_list_for_each_entry_safe/)，在<s>遍歷</s> --- linked list 時，不能使用
`list_for_each_entry()`，該者會導致在刪除 node 時將指標指向 undefined state ，因此在此用 `list_for_each_entry_safe()` ，利用 safe 指標做緩存避免問題發生。
:::danger
注意 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)。
:notes: jserv
:::
在此題用 `list_for_each_entry_safe()` 走訪 linked list 並利用 `queue.h` 裡的 q_relaease_element 將 node 裡的 value 和指向該 node 的指標釋放，最後將作為 list 開頭的指標 l 釋放。
```c
void q_free(struct list_head *l)
{
if (l == NULL)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
}
```
## q_insert_head
新增一個 new_element 作為新增節點的指標，配置一個空間存放該指標，我們知道 element 裡有 value 和 list 兩個部份，接著計算讀取進來的字串長度並加 1 (要放 `'\0'`)，宣告一段長度為上述長度的空間給 element 給 value 使用，利用`strncpy`將讀取到的字串複製進 value 裡，最後用`q_insert_head`將新增的 node 加進整個 linked list 的前端。(以上配置若失敗則回傳 false 並釋放多餘的記憶體)
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *new_element = malloc(sizeof(element_t));
if (new_element == NULL)
return false;
int str_len = strlen(s);
new_element->value = malloc(sizeof(char) * (str_len + 1));
if (new_element->value == NULL) {
free(new_element);
return false;
}
strncpy(new_element->value, s, str_len);
new_element->value[str_len] = '\0';
list_add(&new_element->list, head);
return true;
}
```
:::warning
撰寫更精簡的程式碼。
:notes: jserv
:::
## q_insert_tail
基本上概念一樣，只是將新的節點利用 `list_add_tail` 加入鏈結串列的最尾端。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *new_element = malloc(sizeof(element_t));
if (new_element == NULL)
return false;
int str_len = strlen(s);
new_element->value = malloc(sizeof(char) * (str_len + 1));
if (new_element->value == NULL) {
free(new_element);
return false;
}
strncpy(new_element->value, s, str_len);
new_element->value[str_len] = '\0';
list_add_tail(&new_element->list, head);
return true;
}
```
## q_remove_head
傳進來的 header 裡的 next 指向的就是 linked list 的第一個 node，接著宣告一個 temp 指標儲存被 remove 的 node 裡的數值，利用`list_del()`移除第一個 node，將裡面的 value 複製到 sp 上且要加上`\0`才能作為新的字串，最後回傳被移除 node 的指標(也就是 temp )，當然題目提到要判斷 header 與 sp 是否為 NULL 也要考慮進去。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head))
return NULL;
element_t *temp = list_entry(head->next, element_t, list);
list_del(head->next);
if (sp != NULL && bufsize != 0) {
strncpy(sp, temp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return temp;
}
```
## q_remove_tail
與上一題十分的相似，不同的地方在最後一個 node 是 header 裡的 prev 指向的位置(因為這裡使用的是環狀 linked list )。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head))
return NULL;
element_t *temp = list_entry(head->prev, element_t, list);
list_del(head->prev);
if (sp != NULL && bufsize != 0) {
strncpy(sp, temp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return temp;
}
```
#### 目前遇到執行時間可能非常數時間的問題
## q_size
利用 `list_for_each` 走訪整個 linked list ，每經過一個 node 便將 count + 1，如此便能得到 node 的數量。
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
## q_delete_mid
參考[你所不知道的 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 (node 數為奇數)或快指標的下一個 node 為 head (node 數為偶數)時慢指標恰為整個鏈結串列的一半，之特點撰寫。
:::danger
既然給定的鏈結串列是環狀，那「盡頭」在哪？
用精準的詞彙書寫！
:notes: jserv
:::
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (head == NULL || list_empty(head))
return false;
struct list_head *fast = head->next, *slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
## q_delete_dup
用`temp`儲存指向上一個 node 的指標，從第二個 node 開始做比較，如果現在兩者的值相同則將`duplicate`計為1並移除 temp 儲存的 node ，若兩者值不同但`duplicate`為1代表 temp 儲存的 node 是剩餘沒刪到的重複 node 。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (head == NULL || list_empty(head) || list_is_singular(head))
return false;
struct list_head *li, *temp;
int duplicate = 0;
for (li = head->next->next, temp = li->prev; li != head;
li = li->next, temp = li->prev) {
if (strcmp(list_entry(li, element_t, list)->value,
list_entry(temp, element_t, list)->value) == 0) {
duplicate = 1;
list_del(temp);
q_release_element(list_entry(temp, element_t, list));
} else if (duplicate == 1) {
duplicate = 0;
list_del(temp);
q_release_element(list_entry(temp, element_t, list));
}
}
if (duplicate) {
list_del(temp);
q_release_element(list_entry(temp, element_t, list));
}
return true;
}
```
## q_swap
由於`list_add`的本質是將當前的節點 remove 並插入到所指定節點的後方，因此利用這個函式就能夠達到 swap 的目的
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if(head == NULL || list_empty(head))
return;
struct list_head *li;
for(li = head->next;li != head && li->next != head;li = li->next)
list_move(li, li->next);
}
```
## q_reverse
先將第一個節點的位址存到`first`作為判斷結束依據，接著利用`while()` 將最後一個節點插入到第一個 node 直到最後一個 node 的位址為 first (也就是說第一個 node 已經被擠到最後面)
```c
void q_reverse(struct list_head *head)
{
if (head == NULL || list_empty(head))
return;
struct list_head *li = head->next;
while (li != head) {
li = li->next;
list_move(li->prev, head);
}
}
```
:::warning
撰寫更精簡的程式碼。
:notes: jserv
:::
## q_reverseK
當 count 等於 K 時，則利用`list_move()`將 temp 到 li 之間的所有 node 做翻轉。
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
struct list_head *li = head->next, *lj, *temp = head, *next;
int count = 0;
while(li != head){
count++;
next = li->next;
if (count == k) {
lj = temp->next->next;
while(lj != next->next){
list_move(lj->prev, temp);
lj = lj->next;
}
temp = next->prev;
count = 0;
}
li = next;
}
}
```
## q_sort
一開始使用簡單的bubble sort做撰寫。
```c
void q_sort(struct list_head *head)
{
if (head == NULL || list_empty(head))
return;
struct list_head *current, *tail;
tail = head;
element_t *current_node, *next_node;
while (tail != head->next) {
current = head->next;
while (current->next != tail) {
current_node = list_entry(current, element_t, list);
next_node = list_entry(current->next, element_t, list);
if (strcmp(current_node->value, next_node->value) > 0)
list_move(current, current->next);
else
current = current->next;
}
tail = current;
}
}
```
後來參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)，和 [Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort)，與[seasonwang0905](https://hackmd.io/@seasonwang/B1B0lVqpo#q_sort)的作法改寫成 merge sort 的形式。
```c
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2) {
struct list_head *head = NULL, **indirect = &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;
*indirect = *node;
indirect = &(*indirect)->next;
}
*indirect = (struct list_head *)((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
```c
struct list_head *merge_sort(struct list_head *head)
{
if (head == NULL || head->next == NULL)
return head;
struct list_head *fast = head, *slow = head, *mid;
struct list_head *left,*right;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
mid = slow;
slow->prev->next = NULL;
left = merge_sort(head);
right = merge_sort(mid);
return mergeTwoLists(left, right);
}
```
上述的 `mergeTwoLists` 適用於以 NULL 為結尾的非環狀 Linked list ，因此在使用時要先將最後一個 node 裡指向下個 node 的指標設為 NULL。
在執行完 `mergeTwoLists` 後需要透過迴圈將 linked list 重新設為環狀。
~~排列要將<s>打斷</s> ??? 的 linked list 重新接回。~~
:::warning
避免用「打斷」這樣不精準的詞彙，在作業系統中，可能會對應到 preempt 或 interrupt 等詞彙，顯然非你本來的意思。
:notes: jserv
:::
```c
void q_sort(struct list_head *head)
{
if (head == NULL || list_empty(head))
return;
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head *cur = head, *next = head->next;
while (next != NULL) {
next->prev = cur;
cur = next;
next = next->next;
}
cur->next = head;
head->prev = cur;
}
```
## q_descend
比較 temp 與前一個節點的值，若前一個節點較小則將其全部 remove ，若前一個節點較大則將比較的基準移至前一個節點。
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (head == NULL || list_empty(head) || list_is_singular(head))
return 0;
struct list_head *li, *temp = head->prev, *safe;
for (li = head->prev->prev, safe = li->prev; li != head;
li = safe, safe = li->prev) {
if (strcmp(list_entry(temp, element_t, list)->value,
list_entry(li, element_t, list)->value) > 0) {
list_del(li);
q_release_element(list_entry(li, element_t, list));
} else
temp = li;
}
return q_size(head);
}
```
:::danger
注意作業書寫規範：中英文間用一個半形空白字元區隔。
程式碼縮排亦有相關規範，請依循！
:notes: jserv
:::
## q_merge
參考 [SPFishcool](https://hackmd.io/@SPFishcool/r1r4u_26j) 整理的結構圖與 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#2023q1-Homework1-lab0) 的實作
Sign in with Wallet
Connect another wallet