# 2024q1 Homework1 (lab0)
contributed by <` jerry7961` >
### Reviewed by `jychen0611`
* git commit message 的標題重複且無特別意義，以祈使句為標題
* git commit message 無內文，以`what? why? how?` 描述每次更改的內容
* 單次 commit 修改過多函式，如 [commit 1aa9030](https://github.com/sysprog21/lab0-c/commit/1aa9030b50a48b366a6cf7b678c6b6b0ce4513cc)
* 可斟酌參考我寫的 commit :monkey: [commit a064820](https://github.com/sysprog21/lab0-c/commit/a06482096e43108f6c8c7fdb1c10854d802bc0dc) 和〈[如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)〉
* 開發紀錄不用存放完整程式碼，善用 diff 功能標出重點
* 佇列功能實作尚未完整
:::danger
直接列出 git commits 的超連結並討論，不要只談「心法」，跟同學說你認為要改成什麼，細節！
不用說「建議」，什麼沒做好，就去改什麼。假裝有禮貌無助於工程品質的提升。
:notes: jserv
:::
### Reviewed by `jimmy01240397`
1. 善用巨集展開以減少重複的程式碼，例如：
```c
#define q_remove_base(head, sp, bufsize, from) \
if (head && !list_empty(head)) { \
element_t *to_remove = list_##from##_entry(head, element_t, list); \
list_del(&to_remove->list); \
if (sp) { \
strncpy(sp, to_remove->value, bufsize - 1); \
} \
return to_remove; \
} \
return NULL; \
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
q_remove_base(head, sp, bufsize, first);
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
q_remove_base(head, sp, bufsize, last);
}
```
- `q_insert_head`
- `q_insert_tail`
- `q_remove_head`
- `q_remove_tail`
:::danger
提供說明用的程式碼，不要只談「心法」。
:notes: jserv
:::
### Reviewed by `jujuegg`
- 可以只列出重點程式碼討論
- 建議將內文中提及程式碼的部份加上``，如 `strcpy`。
# 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-1235U
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 4
BogoMIPS: 4992.00
```
## 指定的佇列操作
### `q_new`
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head != NULL) {
INIT_LIST_HEAD(head);
}
return head;
}
```
### `q_free`
先檢查佇列是否為空，若為空則 `return` 。
用 `list_for_each_entry_safe` 巨集走訪所有節點，並釋放節點。
最後釋放開頭節點。
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *cur, *next;
list_for_each_entry_safe (cur, next, head, list) {
q_release_element(cur);
}
free(head);
}
```
### `q_insert_head`
一開始誤用 `strcpy` (如下) 。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *new_element=malloc(sizeof(element_t));
if(!new_element)
return false;
strcpy(new_element->value,s);
if(!new_element->value){
free(new_element);
return false;
}
list_add(&new_element->list,head);
return true;
}
```
`strcpy(s1,s2)` 的功能是複製字串 `s2` 到字串 `s1` ，不會為 `s1` 分配内存， `s1` 的長度必須大於 `s2` 的長度。
因此在沒有為 `new_element->value` 分配內存的情況下直接用 `strcpy(new_element->value,s)` 會造成錯誤。
事先為 `new_element->value` 分配內存再用 `strcpy` 複製字串即可修正錯誤。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *new_element=malloc(sizeof(element_t));
if(!new_element)
return false;
new_element->value=malloc(strlen(s) + 1);
if(!new_element->value){
free(new_element);
return false;
}
strcpy(new_element->value,s);
list_add(&new_element->list,head);
return true;
}
```
另一種做法是使用 `strdup` 來代替 `strcpy` ，`strdup` 會為字串分配內存空間，並返回新分配空間的指標。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *new_element=malloc(sizeof(element_t));
if(!new_element)
return false;
new_element->value=strdup(s);
if(!new_element->value){
free(new_element);
return false;
}
list_add(&new_element->list,head);
return true;
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
### `q_insert_tail`
與 `q_insert_head` 的做法類似，差別是改用 `list_add_tail`。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_element = malloc(sizeof(element_t));
if (!new_element)
return false;
new_element->value = strdup(s);
if (!new_element->value) {
free(new_element);
return false;
}
list_add_tail(&new_element->list, head);
return true;
}
```
### `q_remove_head`
:::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)
:::
`q_remove_head` 的作用是從鏈結串列的開頭移除一個元素。
首先檢查 `head` 是否為空指標，以及鏈結串列中是否至少有一個節點，確保鏈結串列存在且不為空。接著用 `list_first_entry` 取得鏈結串列第一個元素的指標，並透過 `list_del` 將這個元素從鏈結串列中移除。
如果 `sp` 不為 `NULL` ，使用 `strncpy` 函式將被移除元素的字串 `(to_delete->value)` 複製到 `sp` 指向的位址中。複製的字元數量最多為 `bufsize - 1` ，這是為了在字串結尾預留一個位置，用來存放 `\0` 。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head && !list_empty(head)) {
element_t *to_remove = list_first_entry(head, element_t, list);
list_del(&to_remove->list);
if (sp) {
strncpy(sp, to_remove->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return to_remove;
}
return NULL;
}
```
### `q_remove_tail`
與 `q_remove_head` 類似，差別在使用 `list_last_entry` 來取得要移除的元素。
### `q_size`
使用 `list_for_each` 來走訪所有節點，每走訪一個節點 `count` 值就加一。
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int count = 0;
struct list_head *temp;
list_for_each (temp, head)
count++;
return count;
}
```
:::danger
說好的進度呢？
:::
### `q_delete_mid`
使用快慢指標，快指標每次前進兩步，慢指標每次前進一步。
* 當鏈結串列包含奇數個節點時，快指標會停在最後一個節點上，此時慢指標正好指向鏈結串列的中間節點。
* 當鏈結串列包含偶數個節點時，快指標會回到鏈結串列的 `head` ，此時慢指標將指向中間兩個節點中的第二個。為了使 `q_delete_mid` 能夠刪除中間兩個節點中的第一個，需要增加一個 `if` 語句來調整慢指標的位置。
:::danger
改進你的漢語表達。
:::
```c
if (fast == head) {
slow = slow->prev;
}
```
:::danger
使用作業規範的程式碼縮排風格
:::
### `q_delete_dup`
`q_delete_dup` 是要在鏈結串列已經排序好的狀況下，移走其中具有重複內容的節點。
* 使用 `list_for_each_safe` 來走訪鏈結串列中的每個節點。
* `mark_del` 用來標記是否遇到重複節點。
* 在走訪過程中，根據當前節點與前後節點的關係，需要處理以下幾種情況：
1. 當前節點已經是最後一個節點，此時用 `mark_del` 來判斷當前節點是否與前一個節點重複，如果重複則刪除它。
2. 當前節點與下一個節點內容相同，此時刪除當前節點，並將 `mark_del` 設為 `true` ，表示已遇到重複節點。
3. 當前節點與下一個節點內容不同，但 `mark_del` 為 `true`，這表示當前節點與上一個節點內容相同，因此刪除當前節點，並將 `mark_del` 設為 `false`。
4. 非前三種情況，代表當前節點與下一個節點內容不同，與上一個節點也不同，無需執行任何操作。
### `q_swap`
`q_swap` 的作用是交換鏈結串列中鄰近的節點。
* 如果鏈結串列中的節點數量小於等於 1 ，無需執行任何操作。
* 如果鏈結串列中的節點數量大於 1 ，則 `q_swap` 從頭部節點的下一個節點開始走訪鏈結串列。對於每對相鄰節點，`q_swap` 會先將它們從鏈結串列中移除，然後以交換後的順序將它們重新插入到鏈結串列中。這個過程會一直重複，直到走訪完鏈結串列的所有節點。
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node = head->next;
while (node != head && node->next != head) {
struct list_head *nextNode = node->next;
list_del(node);
list_del(nextNode);
list_add(nextNode, node->prev);
list_add(node, nextNode);
node = node->next;
}
}
```
### `q_reverse`
從頭部節點開始走訪鏈結串列，交換每個節點的 `next` 和 `prev` 指標以反轉鏈結串列方向，直到走訪完整個鏈結串列。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
struct list_head *current = head;
struct list_head *temp = NULL;
do {
temp = current->next;
current->next = current->prev;
current->prev = temp;
current = current->prev;
} while (current != head);
}
```
### `q_sort`
一開始使用 Insertion Sort ，無法通過測資，後來參考同學寫法，改用 Merge Sort 。
```c
void merge(struct list_head *l_head,
struct list_head *r_head,
struct list_head *head)
{
struct list_head temp_list;
INIT_LIST_HEAD(&temp_list);
while (!list_empty(l_head) || !list_empty(r_head)) {
struct list_head *chosen;
if (list_empty(l_head)) {
chosen = r_head;
} else if (list_empty(r_head)) {
chosen = l_head;
} else {
element_t *l_entry = list_entry(l_head->next, element_t, list);
element_t *r_entry = list_entry(r_head->next, element_t, list);
chosen =
(strcmp(l_entry->value, r_entry->value) <= 0) ? l_head : r_head;
}
list_move_tail(chosen->next, &temp_list);
}
list_splice_tail_init(&temp_list, head);
}
void merge_sort_recursive(struct list_head *head, int length)
{
if (length <= 1)
return;
int mid = length / 2;
struct list_head left, right;
INIT_LIST_HEAD(&left);
INIT_LIST_HEAD(&right);
struct list_head *current = head->next;
for (int i = 0; i < mid; i++) {
struct list_head *next = current->next;
list_move_tail(current, &left);
current = next;
}
list_splice_tail_init(head, &right);
merge_sort_recursive(&left, mid);
merge_sort_recursive(&right, length - mid);
INIT_LIST_HEAD(head);
merge(&left, &right, head);
}
void merge_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int length = 0;
struct list_head *pos;
list_for_each (pos, head) {
length++;
}
merge_sort_recursive(head, length);
}
void q_sort(struct list_head *head, bool descend)
{
merge_sort(head);
if (descend) {
q_reverse(head);
}
}
```
### `q_merge`
使用 `list_for_each_entry_safe` 走訪整個鏈結串列。從第二個鏈結串列開始，透過 `list_splice_init` 將每個鏈結串列中的節點合併到第一個鏈結串列中。完成合併後，利用 `q_sort` 對合併後的鏈結串列進行排序。
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head)) {
return 0;
}
if (list_is_singular(head)) {
return 1;
}
int total_elements = 0;
queue_contex_t *context, *tmp;
struct list_head *first_queue = NULL;
list_for_each_entry_safe (context, tmp, head, chain) {
if (!first_queue) {
first_queue = context->q;
total_elements += context->size;
} else {
list_splice_init(context->q, first_queue);
context->q = NULL;
total_elements += context->size;
}
}
q_sort(first_queue, false);
return total_elements;
}
```
## 記憶體洩漏
在 trace-03-ops 出現以上錯誤，經過排查，問題出在 `q_merge` 函式。原始版本的 `q_merge` 創建了一個新的 `first_queue` 指標，它用來指向第一個遇到的非空鏈結串列，這個鏈結串列將作為所有鏈結串列合併的目標，所有其他鏈結串列的元素都會被合併到這個 `first_queue` 中，其他鏈結串列在合併到 `first_queue` 後 `q` 指標會被設為 `NULL`，但相關內存沒有被釋放，導致錯誤。修改 `q_merge` 函式後， trace-03-ops 可順利通過。
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head)) {
return 0;
}
queue_contex_t *base_queue = list_first_entry(head, queue_contex_t, chain);
if (list_is_singular(head)) {
return base_queue->size;
}
queue_contex_t *queue_to_merge;
struct list_head *current, *next;
list_for_each_safe (current, next, head) {
if (current == &base_queue->chain) {
continue;
}
queue_to_merge = list_entry(current, queue_contex_t, chain);
list_splice_tail_init(queue_to_merge->q, base_queue->q);
base_queue->size += queue_to_merge->size;
}
q_sort(base_queue->q, descend);
return base_queue->size;
}
```
## 透過 Massif 分析記憶體使用量
- 參考 [alanjiang85](https://hackmd.io/@alanjian85/lab0-2023#%E9%80%8F%E9%81%8E-Massif-%E5%88%86%E6%9E%90%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%BF%E7%94%A8%E9%87%8F) 的說明，用 `trace-eg.cmd` 進行分析
- 透過 Valgrind 產生 massif 檔案
```
$ valgrind --tool=massif ./qtest -f traces/trace-eg.cmd
```
- 產生記憶體使用情形的時間分佈圖
```
$ massif-visualizer ./massif.out.59554
```
Sign in with Wallet
Connect another wallet