# 2024q1 Homework1 (lab0)
contributed by < [YiChiChao](https://github.com/YiChiChao) >
### Reviewed by `yu-hsiennn`
多利用 `graphviz` 來製圖
## 開發環境
```shell
$ 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-8265U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 12
CPU max MHz: 3900.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
```
## 名詞中英定義
>過去整理筆記很習慣中英夾雜，透過這學期的學習希望能改變這樣的行為。
* linked list ： 鏈結串列
* traverse ： 走訪
* memory hierarchy ： 記憶體階層架構
* generic programming ： 泛用性 （？）
## 資料閱讀筆記
### 你所不知道的 C 語言: linked list 和非連續記憶體
* （待解答）如何偵測鏈結串列是否存在環狀結構？
* （待解答）如何對鏈結串列排序並確保**空間複雜度**為 $O(1)$呢？
* （待解答）什麼是 Locality of reference
* 有品味的寫法（以`remove_list_node`為例）：
* 直覺：用指標指向第一個元素資料，此種方法需要考慮到此筆資料是否為第一筆資料，如果是，則`list->head` 和 `prev->next`都需要更新。
* 有品味：用「指標的指標」指向 `＆list->head`，以「要更新的位址」為思考點來操作，而後指標的指標皆為指向 `&node->next`。刪除的操作，實質上是去更新特定指標的位址中的內容，而不是單就個別的node 去判別。
* 針對移走節點的間接指標版本
```c
typedef struct list_entry {
int value;
struct list_entry *next;
} list_entry_t;
// Given that there is a remove function in stdio.h, I have renamed it to
// remove_element to avoid potential conflicts. The for loop needs to account
// for scenarios both with and without the target value. The indirect variable
// cannot be included in the for loop because its new value needs to be assigned
// at the end.
void remove_element(list_entry_t **head, int value) {
list_entry_t **indirect = head;
for (; (*indirect)->value != value || (*indirect)->next == NULL;
indirect = &((*indirect)->next)) {
}
*indirect = (*indirect)->next;
}
```
:::danger
使用作業規範的程式碼縮排風格。
:::
## 指定的佇列操作
### `q_new`
透過 `malloc` 配置記憶體，並且透過 `list.h` 中的 `INIT_LIST_HEAD` 初始結構體。
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
`list.h` 中有 `LIST_HEAD(head)` 和 `INIT_LIST_HEAD(struct list_head *head)` 兩個功能很類似的函式/巨集。`LIST_HEAD` 是直接宣告一個區域變數並且完成初始化的巨集，`INIT_LIST_HEAD` 只負責初始化傳入的 `list_head` 指標。
:::danger
allocate 翻譯為「配置」，以區隔 dispatch (分發/分配) 的翻譯，二者在作業系統領域都是常見詞彙。
> 了解，已修正。[name=YiChi Chao]
:::
之所以不能直接用 `LIST_HEAD(head)` 而要動態配置記憶體，再用 `INIT_LIST_HEAD` 初始化指標，是因為在函式中宣告的區域變數會被配置到 stack 中，當函式返回時會自動將此區域回收，此時即使回傳此結構體的指標，指標的內容也可能為未定義之內容。透過 `malloc` 配置的記憶體在 heap 中，此區的記憶體需要透過 `free` 來釋放。所以 `malloc` 配置的記憶體的結構體指標回傳後，其內容並不會因為函式結束而被回收。
```c
struct list_head *q_new()
{ // instead of using LIST_HEAD creating local variable
// use INIT_LIST_HEAD and malloc for both declaration and initialization
struct list_head *new_queue = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(new_queue);
return new_queue;
}
```
### `q_free`
```c
void q_free(struct list_head *l)
{
free(l);
}
```
### `q_insert_head`
:::danger
string 是「字串」。
:::
`strdup` 是用來動態複製一個以 `'\0'` 結尾的字串，並回傳字串指標。
>strdup(3) — Linux manual page,"The strdup() function returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc(3), and can be freed with free(3)."
Delete 的時候在處理記憶體問題時，除了結構體本身，要記得處理字串本身記憶體的回收。
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
// false for queue is NULL
return false;
}
element_t *nownode = malloc(sizeof(element_t));
assert(nownode);
if (!nownode) {
return false;
}
nownode->value = strdup(s);
if (!nownode->value) {
free(nownode);
return false;
}
list_add(&(nownode->list), head);
return true;
}
```
在 commit 時遇到 error
```c
git commit
Following files need to be cleaned up:
queue.c
queue.c:69:5: error: Memory leak: nownode [memleak]
return true;
^
Fail to pass static analysis.
```
最後的解決方式是將 `&(nownode->next)` 改成 `&nownode->next` 。
### `q_insert_tail`
從 [terry23304](https://hackmd.io/@normal/SyAQbn26j#q_insert_headtail) 看到可重用 `q_insert_head` 的建議，將插入 `Head` 的尾看作插入 `Head->prev` 的頭。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
return q_insert_head(head->prev, s);
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
> 了解，先刪除此部份
:::
### `container_of`
```c
#define container_of(ptr, type, member) \
({ \
void *__mptr = (void *) (ptr); \
static_assert(__same_type(*(ptr), ((type *) 0)->member) || \
__same_type(*(ptr), void), \
"pointer type mismatch in container_of()"); \
((type *) (__mptr - offsetof(type, member))); \
})
```
由已知結構體中的 **某個成員起始位址** 去獲得此成員所在之 **結構體的起始位址**。
利用成員起始位址`ptr`扣掉成員在結構體中相對位址。
:::danger
避免非必要的項目列表 (即 `* `)，以清晰且明確的漢語書寫。
:::
## `q_delete_dup`
此函式的目的是要消除佇列中重複的字串節點。在條件判斷會有三種情況：
1. 目前的節點字串和前一個節點字串相同
2. 目前的節點字串和前一個節點字串不同，但和下一個節點字串相同
3. 目前的節點字串和前一個節點字串不同，且和下一個節點字串不同
前兩者皆為字串重複，第二種除了消除目前節點外，還需要更新紀錄重複字串之變數（ `prob` )
原本更新 `prob` 的寫法為直接透過 `strdup` 重新動態配置字串空間，紀錄最新重複字串。
```c
if (prob == NULL || strcmp(prob, cur->value)) {
// Check if the current node has the same string
// as the next node
if (next == NULL || strcmp(cur->value, next->value)) {
continue;
} else {
// Update the prob if cur and next have the same string
prob = strdup(cur->value);
}
}
//printf("Free: %s\n", cur->value);
list_del(&cur->list);
free(cur->value);
free(cur);
```
當透過 `make check` 搭配 `trace-06-ops.cmd` 測試時，會發現有兩個配置的位置沒有被釋放
```c
make check
CC queue.o
LD qtest
./qtest -v 3 -f traces/trace-06-ops.cmd
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
l = []
l = [tvzaist vfktis prljcykrc jxiswnclm]
l = [tvzaist vfktis prljcykrc jxiswnclm gerbil gerbil gerbil]
l = [tvzaist vfktis prljcykrc jxiswnclm gerbil gerbil gerbil lion lion]
l = [tvzaist vfktis prljcykrc jxiswnclm gerbil gerbil gerbil lion lion zebra zebra]
l = [gerbil gerbil gerbil jxiswnclm lion lion prljcykrc tvzaist vfktis zebra zebra]
l = [jxiswnclm prljcykrc tvzaist vfktis]
l = NULL
ERROR: There is no queue, but 2 blocks are still allocated
```
更仔細地印出目前釋放位置的字串內容才發覺，當透過 `strdup` 來更新 `prob` 的字串時，未釋放前一個 `prob` 字串的位置。
```c
l = [gerbil gerbil gerbil jxiswnclm lion lion prljcykrc tvzaist vfktis zebra zebra]
Free: gerbil
Free: gerbil
Free: gerbil
Free: lion
Free: lion
Free: zebra
Free: zebra
Free Prob: zebra
...
ERROR: There is no queue, but 2 blocks are still allocated
```
在更新 `prob` 前，先釋放目前字串之位置，將 `prob` 設為 NULL ，再進行更新。
```c
if (prob) {
free(prob);
prob = NULL;
}
prob = strdup(cur->value);
```
:::warning
改為以下:
```c
free(prob);
prob = strdup(cur->val);
```
注意看 [free(3)](https://man7.org/linux/man-pages/man1/free.1.html)。
:::
Sign in with Wallet
Connect another wallet