# 2023q1 Homework1 (lab0)
contributed by < `Jacobchen142` >
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 36 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz
CPU family: 6
Model: 42
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 7
CPU max MHz: 3400.0000
CPU min MHz: 1600.0000
BogoMIPS: 6185.67
Virtualization: VT-x
Caches :
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
```
## 實作queue.c 開發紀錄
:::danger
說好的進度呢？
:notes: jserv
> 老師抱歉，因為我發現我有太多基礎需要補上，所以一直沒開始做作業
:::
### 結構
`list_head` 為 doubly-linked list 的 head 或是 node
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
```graphviz
digraph list_ele {
rankdir=LR;
node[shape=record];
head [label="{<left>prev|<right>next}", style=bold];
}
```
`element_t` 為 doubly-linked list 的 element
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
node [shape=record];
value [label="{value}"];
head [label="{<prev>prev|<next>next}"];
style=bold;
label=element_t
}
}
```
- 參考 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c)
- 參考[你所不知道的 C 語言：linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
### 問題紀錄
1. 我遇到的第一個大問題就是對於整體結構沒有概念，一知半解。透過詳讀[你所不知道的 C 語言：linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)，就可以對於 doubly-linked list 的結構有所掌握。
指向串列開頭的指標，是單一個`list_head`結構。
而在串列的元素中，`list_head`結構則是嵌入在自定義的結構中，本次作業中即為`element_t`
### q_new
1. 串列的開頭是一個指向`list_head`的指標，透過`malloc()`建立該指標
2. 利用`list.c`所提供的`INIT_LIST_HEAD()`進行初始化
:::spoiler 實際程式碼
```c
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
if (!new)
return NULL;
INIT_LIST_HEAD(new);
return new;
}
```
:::
### q_free
- 想法：走訪整個串列，每經過一個節點，就 remove 該節點，並釋放該節點的記憶體空間。重複動作，直到剩下指向開頭的指標。最後釋放指向開頭的指標之記憶體空間。
- 實作流程：
1. 若傳入的`l`(指向開頭的指標) 為`NULL`則直接`return`
2. 若除了`l`之外還有其他`list_head`的節點，利用`list_del()`移除節點的連結，再透過`list_entry()`找到串列節點的位置，用`q_release_element（）`釋放記憶體
3. 重複步驟 2 直到整個串列只剩下`l`
4. 用`free()`釋放`l`
:::spoiler 程式碼
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *node = l->next;
while (node != l) {
struct list_head *del = node;
node = node->next;
list_del(del);
q_release_element(list_entry(del, element_t, list));
}
free(l);
}
```
:::
### q_insert_head
* 實作流程：
1. 排除`head`或`s`為`NULL`的情況
2. 用`malloc()`取得節點所需的記憶體空間，要注意`malloc()`失敗的情況
3. 設置節點的內容並用`list_add()`加入串列中
* 提醒：複製字串的函式不要用`strcpy()`
:::spoiler 程式碼
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
int str_space = (strlen(s) + 1) * sizeof(char);
new->value = malloc(str_space);
if (!new->value) {
free(new);
return false;
}
strncpy(new->value, s, str_space);
*(new->value + str_space) = '\0';
list_add(&new->list, head);
return true;
}
```
:::
### q_insert_tail
* 想法 1：比照`q_insert_head()`的方法
* 想法 2：直接利用`q_insert_head()`來實作
* 參考[alanjian85](https://hackmd.io/@alanjian85/lab0-2023#q_insert_head--q_insert_tail)
:::spoiler 程式碼
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head || !s)
return false;
return q_insert_head(head->prev, s);
}
```
:::
### q_remove_head
* 實作流程：
1. 排除`head`為`NULL`或是串列為空的情況
2. 用`list_first_entry()`取得第一個節點的記憶體位置，並用`list_del()`從串列中移除該節點
3. 將節點中的字串內容複製到`sp`
:::spoiler 程式碼
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_first_entry(head, element_t, list);
list_del(&node->list);
if (bufsize) {
strncpy(sp, node->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return node;
}
```
:::
### q_remove_tail
* 實作流程：
1. 排除`head`為`NULL`或是串列為空的情況
2. 用`list_last_entry()`取得第一個節點的記憶體位置，並用`list_del()`從串列中移除該節點
3. 將節點中的字串內容複製到`sp`
:::spoiler 程式碼
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
return q_remove_head(head->prev->prev, sp, bufsize);
}
```
:::
### q_delete_mid
* 想法 1: 利用快慢指標。慢的指標每次走訪一個節點；快的指標每次走訪兩個節點。當快的指標到達串列最後一個節點時，慢的指標剛好在串列的中心點。
* 想法 2: 本次的串列是 circular doubly-linked list ，可以利用雙向環狀的特性，用兩個指標分別以不同方向（`prev`和`next`)走訪串列。當兩個指標相遇或是即將交錯位置，即可判斷中心節點。
:::spoiler 程式碼
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *front = head->next, *back = head->prev;
while (front != back && front->next != back) {
front = front->next;
back = back->prev;
}
list_del(back);
q_release_element(list_entry(back, element_t, list));
return true;
}
```
:::
### q_delete_dup
* 想法：在已經排序好的串列中，`value`相同之節點一定是相鄰的。順著串列的`next`方向走訪，若相鄰的兩個節點內容一樣，則刪除當前節點。
* 實作方法：
1. 排除例外狀況
2. 利用`list_for_each_entry_safe()`走訪串列，並定義兩個布林變數紀錄狀態：`equal`，表示相鄰兩節點之字串內容是否相同；`flag`，表示前一次的`equal`
3. 只要`equal`或`flag`為其一`true`，表示當前的節點為與下一個或前一個相同，刪除該節點
4. 走到最後一個節點（`head->prev`)時，`equal`必為`false`(`equal`中有定義當前節點的`next`不能是`head`的條件)，所以要另外單獨用`flag`判斷
:::spoiler 程式碼
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head) || list_is_singular(head))
return true;
element_t *cur_node, *next_node;
bool flag = false;
list_for_each_entry_safe (cur_node, next_node, head, list) {
bool equal = &next_node->list != head &&
!strcmp(cur_node->value, next_node->value);
if (flag || equal) {
list_del(&cur_node->list);
q_release_element(cur_node);
flag = equal;
}
}
if (flag) {
list_del(&cur_node->list);
q_release_element(cur_node);
}
return true;
}
```
:::
### q_swap
:::spoiler 程式碼
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *first = head->next, *second = first->next;
while (first != head && second != head) {
list_del_init(first);
list_add(first, second);
first = first->next;
second = first->next;
}
}
```
:::
### q_reverse
* 想法：從`head`的`next`方向開始走訪，每經過一個節點便將該節點加到`head->next`
- 參考[25077667](https://hackmd.io/@25077667/lab0-2023#q_reverseK)
:::spoiler 程式碼
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *cur = head->next, *next = cur->next;
while (cur != head) {
list_del_init(cur);
list_add(cur, head);
cur = next;
next = cur->next;
}
}
```
:::
### q_reverseK
* 想法：每次取K個節點來進行`q_reverse()`
* 注意：`q_reverse()`的參數是串列的開頭，所以呼叫`q_reverse()`之後，下次若要再次呼叫該函式，要傳入的引數是尚未做`q_reverse()`節點的前一個(第14行)
:::spoiler 程式碼
```c=
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (q_size(head) <= 1)
return;
struct list_head *curr, *next, *tmp_head_from = head, tmp_head_to;
int i = 1;
INIT_LIST_HEAD(&tmp_head_to);
list_for_each_safe (curr, next, head) {
if (i == k) {
list_cut_position(&tmp_head_to, tmp_head_from, curr);
q_reverse(&tmp_head_to);
list_splice_init(&tmp_head_to, tmp_head_from);
tmp_head_from = next->prev;
i = 0;
}
i++;
}
}
```
:::
### q_sort
* 想法：使用 merge sort
* 步驟：
1. 先把環狀鏈結串列改成非環狀
2. 從串列的中心點分割程兩個串列
3. 若串列中只剩一個節點則開始合併，否則繼續步驟2
4. 合併兩個串列
5. 將串列復原成環狀鏈結串列
### q_merge
## Valgrind 檢查記憶體錯誤
執行命令`make valgrind`會發現以下訊息
```shell
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==12489== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==12489== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12489== by 0x10CBCE: do_new (qtest.c:145)
==12489== by 0x10DDFA: interpret_cmda (console.c:181)
==12489== by 0x10E3AF: interpret_cmd (console.c:201)
==12489== by 0x10E7B0: cmd_select (console.c:610)
==12489== by 0x10F09C: run_console (console.c:705)
==12489== by 0x10D1EC: main (qtest.c:1223)
==12489==
==12489== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==12489== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12489== by 0x10F110: test_malloc (harness.c:133)
==12489== by 0x10F605: q_new (queue.c:18)
==12489== by 0x10CC07: do_new (qtest.c:149)
==12489== by 0x10DDFA: interpret_cmda (console.c:181)
==12489== by 0x10E3AF: interpret_cmd (console.c:201)
==12489== by 0x10E7B0: cmd_select (console.c:610)
==12489== by 0x10F09C: run_console (console.c:705)
==12489== by 0x10D1EC: main (qtest.c:1223)
==12489==
--- trace-01-ops 5/5
```
關鍵字`still reachable`，根據[Valgrind FAQ](https://valgrind.org/docs/manual/faq.html#faq.reports)可得知，當`still reachable`發生時，程式可以正常執行但是仍有指標指向未釋放的記憶體。再參考[yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#Valgrind-%E8%88%87-Address-Sanitizer-%E8%A8%98%E6%86%B6%E9%AB%94%E6%AA%A2%E6%9F%A5)的筆記，發現是`qtest.c`中的`q_quit()`第一行就直接`return true`，移除該行程式即可
```c
static bool q_quit(int argc, char *argv[])
{
return true;
report(3, "Freeing queue");
```
### 學習機率與統計
Sign in with Wallet
Connect another wallet