# 2025q1 Homework1 (lab0)
contributed by < `Yuyuan1110` >
### Reviewed by `nyraa`
> Commit message 中使用 Completed 的時機有點奇怪
在 `q_free()` 的說明段落已經寫了「記憶體洩漏問題還待解決」， commit message 中不應使用已完成的字眼。
> 中文和英文字元之間要有空白字元
書寫規範需要留意一下
### Reviewed by `NeedToDebugMyLife`
1. Commit [020b91d](https://github.com/Yuyuan1110/lab0-c/commit/020b91da334837d95a1570c4cde77c9a41c03855) 中所實作的 `q_insert_head` 和 `q_insert_tail` 未依 `<queue.h>` 中的要求進行實作。
```c
/**
* q_insert_head() - Insert an element in the head
* @head: header of queue
* @s: string would be inserted
*
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*
* Return: true for success, false for allocation failed or queue is NULL
*/
bool q_insert_head(struct list_head *head, char *s);
```
當佇列為 `NULL` 時，需要回傳 `false`，而不是建立一個佇列
2. Commit [020b91d](https://github.com/Yuyuan1110/lab0-c/commit/020b91da334837d95a1570c4cde77c9a41c03855) 中實作了多個函式，包含 `q_new`、 `q_free`、 `q_insert_head` 以及 `q_insert_tail`。這會讓commit message 的閱讀難度變高，建議將此 commit 針對函式的功能性做細部的分割。
<!-- {%hackmd NrmQUGbRQWemgwPfhzXj6g %} -->
## 開發環境
```shell!
gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-1240P
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
Stepping: 3
CPU(s) scaling MHz: 30%
CPU max MHz: 4400.0000
CPU min MHz: 400.0000
BogoMIPS: 4224.00
Virtualization: VT-x
Caches (sum of all):
L1d: 448 KiB (12 instances)
L1i: 640 KiB (12 instances)
L2: 9 MiB (6 instances)
L3: 12 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
```
## 針對佇列操作的程式碼實作
### q_new()
> Commit [596e40a](https://github.com/Yuyuan1110/lab0-c/commit/596e40ae7fc78a7aca8e048085adb88e5e054894)
在寫 malloc 的時候有想到是否有強制轉行的必要性，我想之後研讀完C99後也許會有答案，這邊先做個記錄以防忘記這個議題。
```clike!
- struct list_head *head = malloc(sizeof(*head));
+ struct list_head *head =
+ (struct list_head *) malloc(sizeof(struct list_head));
```
### q_free()
> Commit [020b91d](https://github.com/Yuyuan1110/lab0-c/commit/020b91da334837d95a1570c4cde77c9a41c03855)
我的實作在 qtest 的測試中一直有記憶體釋放不完全的問題，初步先解決了釋放空的陣列時的記憶體洩漏問題，但在釋放 list_head 的時候依然會有記憶體洩漏，目前判斷是插入的方法實作的不好，等完成所有 function 的實作後再回頭處理。
```clike
- if (!head || list_empty(head)) {
+ if (!head) {
```
### q_insert_head()
> Commit [020b91d](https://github.com/Yuyuan1110/lab0-c/commit/020b91da334837d95a1570c4cde77c9a41c03855)
在寫開發記錄的當下瞥了一眼自己的程式碼，發現在判斷記憶體分配失敗的時候沒有釋放其它的記憶體就返回了，這可能造成濳在的記憶體洩漏問題，預計在改進正常分配的狀況下釋放記憶體時會有記憶體洩漏問題時一併改進。
```clike
if (!element || !list || !element->value) {
return false;
}
```
### q_remove_head()
> Commit [020b91d](https://github.com/Yuyuan1110/lab0-c/commit/020b91da334837d95a1570c4cde77c9a41c03855)
### q_delete_mid()
> Commit [d6cafb9](https://github.com/Yuyuan1110/lab0-c/commit/d6cafb98451f60dbee54308953c981c793f05d9e)
使用快慢指標獲取中間元素，並將其釋放。
實作的當下不確定當陣列中只有一個元素時要不要移除，我的想法是當只有一個元素時就沒有所謂「中間」的概念，所以就把只有一個元素的陣列排除在外了。
```clike
if (!head || list_is_singular(head) || list_empty(head)) {
return false;
}
```
### q_delete_dup()
> Commit [2399504](https://github.com/Yuyuan1110/lab0-c/commit/2399504699e86f0e50621b363a0045df3574cd2c)
實作思想: 當當前元素與下一個元素的 value 相同時，刪除當前 head, 並且用的一個 bool 來判斷是不是已經重複過的元素。
實作當下使用 `element->value == safe->value` 時一直失敗，後來才想到 char* 是指向字串的第一位，後來改用 `strcmp` 就成功了。
```clike
list_for_each_entry_safe (element, safe, head, list) {
if (strcmp(element->value, safe->value) == 0) {
condition = true;
list_del(&(element->list));
q_release_element(element);
} else if (condition) {
condition = false;
list_del(&(element->list));
q_release_element(element);
}
if (safe->list.next == head) {
break;
}
```
### q_swap()
> Commit [d453f6b](https://github.com/Yuyuan1110/lab0-c/commit/d453f6b54ba5b01aa5a958b78189f13ec84cf19b)
將相鄰元素兩兩交換，原本的實作的想法是更改 `next` 與 `prev` 的指向來遠成目的，過幾天瞥了一眼自己劃的圖想到，相鄰元素兩兩交換其實也就是移除前一個並丟到後一個後面，所以使用 `list_del` 與 `list_add` 來實作，雖然底層邏輯一樣，但後者更為直觀。
*後來才發現 `q_insert_after()` 與 `list_add` 是一樣的實作，在後面有改成使用 list_add()*
```clike
- a = *pp;
- b = a->next;
- a->next = b->next;
- b->next = a;
- b->prev = temp;
- a->prev = b;
- *pp = b;
- temp = a;
- pp = &(a->next);
- }
- (*pp)->prev = temp;
+ anode = *pp;
+ list_del(anode);
+ q_insert_after(anode->next, anode);
+ pp = &(anode->next);
+ }
```
### q_reverse()
>Commit [de7aed1](https://github.com/Yuyuan1110/lab0-c/commit/de7aed1c303c4bd8ff4837c543b9b1e60ef57294)
有兩個想法:
- 最直觀就是改變 `next` 與 `prev` 來達成返轉目的
- 再來就是從頭尾開始交換直到在中間相遇
目前實作了方案一，因為直觀且簡單，但感覺方案二更有效率，未來會做個實驗比較兩者的效率差異，期望能擺脫「靠感覺」寫程式。
### q_sort()
>Commit [73288db](https://github.com/Yuyuan1110/lab0-c/commit/73288db5ef664407e2e3ca5b51a5301e90997eeb)
使用合併排序法來實作排序，最後判斷 `descend` 決定是否呼叫 `q_reverse()`。
### q_ascend()
>Commit [5bf9303](https://github.com/Yuyuan1110/lab0-c/commit/5bf93032367fcbd665e9f0c30fd528c564a515f2)
實作思想: 比較前兩個元素的 value 如果前者較大則移除後者，否則往後移動。
### q_merge()
>Commit [5bf9303](https://github.com/Yuyuan1110/lab0-c/commit/5bf93032367fcbd665e9f0c30fd528c564a515f2)
實作思想: 將全部的陣列合併後再調用 `q_sort()` 排序。
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案
### 題外話
一邊讀研讀 list_sort.c 的時候一邊看自己寫的程式，發現居然看不懂自己寫的程試，這才意識到我的注解與 commit log 有很大的問題，於是我就去看課程內容提到的《[為你自己學 Git](https://gitbook.tw/)》，雖然也在這次作業的預其目標中，但礎於篇幅，就另外寫一篇筆記記錄。
### 研讀 list_sort.c
#### merge()
利用 indirect pointer 的技巧將 a 或 b 插入到 tail ，如下示意:
```clike!
*tail = &a->next;
a = a->next;
```
> todo=>使用 graphviz 建立示意圖
#### merge_final()
#### list_sort()
我在實作 `q_sort` 的時候一直為分割後的 linked list 沒有 header 而苦腦，如果分割後的 list 沒有 header 的話會導致左右 list 的數量不平均，索性在每次遞歸的時候把右邊的 list 加上一個 header.
list_sort.c 中的做法是讓 merge 的過程中沒有 header 有存在，這樣就在分割或是點併的過程中就不用處理 header 了; list_sort.c 中還把本來是環狀鏈結串列變成一般的鏈結串列，這樣也是省去了 header 的判斷。
```clike
// my code
struct list_head thead;
struct list_head *head2 = &thead;
list_cut_position(head2, head, tortoise);
// list_sort.c
struct list_head *list = head->next;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
### 嘗試將 list_sort.c 引入到 lab0-c
## 比較自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
>TODO
### 嘗試改進針對鏈結串列排序實作的效能
## 在 qtest 提供新的命令 shuffle
>TODO
## 研讀論文〈Dude, is my code constant time?〉
>TODO
##### [感想](https://hackmd.io/@Yuyuan-Wang/lab0-c_thoughts)
Sign in with Wallet
Connect another wallet