# 2025q1 Homework1 (lab0)
contributed by < [`blue76815`](https://github.com/blue76815/lab0-c) >
## Reviewed by `tyj513`
1. 作業書寫規範有提及
> HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
2.q_descend的圖片無法閱覽
3.
[作業內容](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a)
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ uname -a
Linux blue76815-tuf-gaming-fx504ge-fx80ge 6.8.0-45-generic #45-Ubuntu SMP PREEMPT_DYNAMIC Fri Aug 30 12:02:04 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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
架構： x86_64
CPU 作業模式： 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
供應商識別號： GenuineIntel
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
CPU 家族： 6
型號： 158
每核心執行緒數： 2
每通訊端核心數： 6
Socket(s): 1
製程： 10
CPU(s) scaling MHz: 34%
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
Virtualization features:
虛擬： VT-x
Caches (sum of all):
L1d: 192 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 1.5 MiB (6 instances)
L3: 9 MiB (1 instance)
NUMA:
NUMA 節點： 1
NUMA node0 CPU(s)： 0-11
Vulnerabilities:
Gather data sampling: Mitigation; Microcode
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Mitigation; PTE Inversion; VMX conditional cache flush
es, SMT vulnerable
Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Meltdown: Mitigation; PTI
Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Reg file data sampling: Not affected
Retbleed: Mitigation; IBRS
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prct
l
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointe
r sanitization
Spectre v2: Mitigation; IBRS; IBPB conditional; STIBP conditional;
RSB filling; PBRSB-eIBRS Not affected; BHI Not affect
ed
Srbds: Mitigation; Microcode
Tsx async abort: Not affected
```
## `queue.c` 實作
- `q_new`: 建立新的「空」佇列;
- `q_free`: 釋放佇列所佔用的記憶體;
- `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
- `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
- `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
- `q_remove_tail`: 在佇列尾端 (tail) 移去 (remove) 給定的節點;
- `q_size`: 計算目前佇列的節點總量;
- `q_delete_mid`: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
- `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
- `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
- `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- `q_reverseK`: 類似 `q_reverse`，但指定每 k 個節點為一組，進行反向順序排列，詳見 [LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/)
- `q_sort`: 以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
- `q_ascend` 及 `q_descend`: 參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)，注意節點間的順序
- `q_merge`: 合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
### q_new
此操作為建立新的「空」佇列，因此是建立 `struct list_head head` 頭端，而不是新建一個 element_t 節點
1. 配置一個新 head
2. 若配置失敗則回傳 NULL
3. 調用 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) `INIT_LIST_HEAD()`初始化head
> Commit [`71ffce9`](https://github.com/blue76815/lab0-c/commit/71ffce98a2664dc36e15ae5313f808f075eef430#diff-3f6f16518a74b523b2cad7ede4d4a9c11605317dfed2905cdaf12e242ee05923)
```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;
}
```
### q_free
1. 調用 `list_for_each_entry_safe` 尋訪 `struct list_head` 環狀佇列
2. `list_del()` 只是將 `node` 從其原本的 linked list 連接移除
3. 還得用 `q_release_element(node)` 才能將節點記憶體釋放
> Commit [`71ffce9`](https://github.com/blue76815/lab0-c/commit/71ffce98a2664dc36e15ae5313f808f075eef430#diff-3f6f16518a74b523b2cad7ede4d4a9c11605317dfed2905cdaf12e242ee05923)
```c
void q_free(struct list_head *l)
{
if (l == NULL)
return;
element_t *node = NULL, *tmp_node = NULL;
list_for_each_entry_safe (node, tmp_node, l, list) {
list_del(&node->list);
q_release_element(node);
}
free(l);
}
```
### q_insert_head
1. `malloc `配置新節點
2. 將字串資料複製到 `node->value`
3. `list_add()` 將指定的 node 插入到 linked list `struct list_head head` 的開頭
> Commit [`71ffce9`](https://github.com/blue76815/lab0-c/commit/71ffce98a2664dc36e15ae5313f808f075eef430#diff-3f6f16518a74b523b2cad7ede4d4a9c11605317dfed2905cdaf12e242ee05923)
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (s == NULL || head == NULL)
return false;
element_t *node = malloc(sizeof(element_t));
if (node == NULL)
return false;
node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
if (node->value == NULL) {
q_release_element(node);
return false;
}
memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
memcpy(node->value, s, sizeof(char) * strlen(s));
list_add(&node->list, head);
return true;
}
```
#### 注意事項
1. 節點插入`data` 資料時，得用 `element_t` 才能配置
```c
typedef struct {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct list_head list;
} element_t;
```
圖片來源：[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list?type=view#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)
2. 要訪問 linked list 各別節點內的資料，可調用
```
list_entry(node, type, member)
list_first_entry(head, type, member)
list_last_entry(head, type, member)
```
3. 配置 `strlen(s) + 1` 是因為
[Linux Programming Interface 查詢 strlen](https://man7.org/linux/man-pages/man3/strlen.3.html) 有提到
> ### DESCRIPTION
> The strlen() function calculates the length of the string pointed to by s, <span class="red">**excluding the terminating null byte ('\0').**</span>
>
> ### RETURN VALUE
> The strlen() function returns the number of bytes in the string pointed to by s.
`strlen()` 計算字元個數到 **null byte ('\0')** 就停止，因此字數不包含 **null byte ('\0')**。
多加一格，是為了**在字串結尾多填一格 NULL 值**，
**避免 `strlen(const char str)` 計算字串長度時，把字尾相鄰的記憶體殘值也列入字元個數**
### q_insert_tail
1. `malloc `配置新節點
2. 將字串資料複製到 `node->value`
3. 差別只在插入 link-list 時，得用 `list_add_tail(&node->list, head);` 插入到尾端
> Commit [`71ffce9`](https://github.com/blue76815/lab0-c/commit/71ffce98a2664dc36e15ae5313f808f075eef430#diff-3f6f16518a74b523b2cad7ede4d4a9c11605317dfed2905cdaf12e242ee05923)
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL || s == NULL)
return false;
element_t *node = malloc(sizeof(element_t));
if (node == NULL)
return false;
node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
if (node->value == NULL) {
q_release_element(node);
return false;
}
memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
memcpy(node->value, s, sizeof(char) * strlen(s));
list_add_tail(&node->list, head);
return true;
}
```
### q_remove_head
* 調用 `list_first_entry()` ，取得 linked list 的開頭
> Commit [`7dc94e1`](https://github.com/blue76815/lab0-c/commit/7dc94e119bf2eb8e50f9a9aa0dd959eca253bbc6)
```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 *node = list_first_entry(head, element_t, list);
list_del_init(&(node->list));
if (sp) {
size_t length = strlen(node->value) + 1;
length = length > bufsize ? bufsize : length;
memset(sp, '\0', length);
memcpy(sp, node->value, length - 1);
}
return node;
}
```
### q_remove_tail
* 調用 `list_last_entry()` ，取得 linked list 的結尾
> Commit [`1c58006`](https://github.com/blue76815/lab0-c/commit/1c580065612322823fad6fb05d4cc5f0c5ce4887)
```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 *node = list_last_entry(head, element_t, list);
list_del_init(&(node->list));
if (sp) {
size_t length = strlen(node->value) + 1;
length = length > bufsize ? bufsize : length;
memset(sp, '\0', length);
memcpy(sp, node->value, length - 1);
}
return node;
}
```
### q_size
1. 調用 `list_for_each_entry_safe`
2. 尋訪 `struct list_head` 環狀佇列計次
> Commit [`71ffce9`](https://github.com/blue76815/lab0-c/commit/71ffce98a2664dc36e15ae5313f808f075eef430#diff-3f6f16518a74b523b2cad7ede4d4a9c11605317dfed2905cdaf12e242ee05923)
```c
int q_size(struct list_head *head)
{
if (head == NULL || list_empty(head))
return 0;
int size = 0;
struct list_head *node = NULL;
list_for_each (node, head) {
size++;
}
return size;
}
```
### q_delete_mid
參考[金刀的算法小册子 0876-链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/jin-dao-ji-shu-fa-kuai-man-zhi-zhen-yyds-9fgd/)
改成快慢兩種指標做 Floyd’s Cycle detection
Commit [`53c2ae4`](https://github.com/blue76815/lab0-c/commit/53c2ae472257a9fd1d34c8fcfa803edf46fbbdf5)
```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;
struct list_head *slow = head->next;
while (fast!=head && fast->next !=head) {
slow = slow->next;
fast = fast->next->next;
}
element_t *ele_node = list_entry(slow, element_t, list);
list_del(slow);
free(ele_node->value);
free(ele_node);
return true;
}
```
### q_delete_dup
參考 [SmallHanley](https://hackmd.io/@SmallHanley/linux2022-lab0#q_delete_dup) 同學的方法
1. 檢查 `head` 是否為 `NULL`，是則回傳 `false`。
1. 用一個 bool 值 `last_same_node` 判斷相鄰重複的節點，是否已經刪除到最後一個。
1. 呼叫 `list_for_each_safe (node, tmp, head)` 走訪每個節點
1. 走訪節點時，此`node`內是儲存**某 element_t 節點的記憶體位址**，得用 `list_entry(node, element_t, list)` 和 `list_entry(node, element_t, list)` 才能解析出 element_t 節點內的 value 成員
1. 判斷此 element_t 節點和下一個 element_t 節點的 `value` 是否相同，是則將 `last_same_node` 設為 `true`，然後從串列中移除此節點並釋放相關空間。
1. 若 `value` 不同，而 `last_same_node` 依然是 `true`，代表此節點是相鄰重複的節點中的最後一個，將 `last_same_node` 設回 `false` 並釋放相關空間。
例如 link-list 1==>1==>1==>2==>3
當刪除到剩 1==>2==>3 時，此 1 節點就是**相鄰重複節點中的最後一個**
[list_entry 介紹](https://biscuitos.github.io/blog/LIST_list_entry/)
[内核双链表遍历：带 safe 和不带 safe 的区别](https://biscuitos.github.io/blog/LIST_ADV_safe/)
> ```
> #define list_for_each(pos, head) \
> for (pos = (head)->next; pos != (head); pos = pos->next)
>
>
> #define list_for_each_safe(pos, n, head) \
> for (pos = (head)->next, n = pos->next; pos != (head); \
> pos = n, n = pos->next)
> ```
> 从两个接口的定义差别只看出，**list_for_each_safe() 的定义多了一个参数 n，这个参数 n 用于缓存下一个节点**，其余并没有什么逻辑上的差异。
>
所以寫 `list_for_each_safe (node, tmp, head) `
相當於用 `node` 節點 跑 `for` 迴圈
Commit [`829bd87`](https://github.com/blue76815/lab0-c/commit/829bd8755f78a35e586e28627e79b5f1a45066cc)
```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))
return false;
struct list_head *node, *tmp;
bool last_same_node = false;
list_for_each_safe (node, tmp, head) {
element_t *curr_element_t = list_entry(node, element_t, list);
element_t *next_element_t = list_entry(node->next, element_t, list);
if (node->next != head &&
strcmp(curr_element_t->value, next_element_t->value) == 0) {
last_same_node = true;
list_del(node);
free(curr_element_t->value);
free(curr_element_t);
} else if (last_same_node == true) {
last_same_node = false;
list_del(node);
free(curr_element_t->value);
free(curr_element_t);
}
}
return true;
}
```
### q_swap
在[官方 linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中，發現有 `list_swap()` 可調用
```c
/**
* list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
* @entry1: the location to place entry2
* @entry2: the location to place entry1
*/
static inline void list_swap(struct list_head *entry1,
struct list_head *entry2)
{
struct list_head *pos = entry2->prev;
list_del(entry2);
list_replace(entry1, entry2);
if (pos == entry1)
pos = entry2;
list_add(entry1, pos);
}
```
調用 `list_swap()` 編譯時出現
```
$ make
CC queue.o
queue.c: In function ‘q_swap’:
queue.c:267:9: error: implicit declaration of function ‘list_swap’ [-Werror=implicit-function-declaration]
267 | list_swap(node,node->next);
| ^~~~~~~~~
cc1: all warnings being treated as errors
make: *** [Makefile:50：queue.o] 錯誤 1
```
發現我們 `lab0` 專案內的 `list.h` 中
沒有加入[官方 linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的 `list_swap()` 程式碼
於是我自己將官方 `list_swap()` 程式碼加在 `lab0` 專案內的 `queue.c` 中
再次編譯
```
$ make
CC qtest.o
In file included from qtest.c:16:
list.h: In function ‘list_swap’:
list.h:348:2: error: implicit declaration of function ‘list_replace’; did you mean ‘list_splice’? [-Werror=implicit-function-declaration]
348 | list_replace(entry1, entry2);
| ^~~~~~~~~~~~
| list_splice
cc1: all warnings being treated as errors
make: *** [Makefile:50：qtest.o] 錯誤 1
```
`queue.c` 中還要再補上 [官方 linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) `list_replace()`
```c
/**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
```
編譯成功
Commit [`f1efcf0`](https://github.com/blue76815/lab0-c/commit/f1efcf002655e8bedb1cae36823f91410eedc3c7)
```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 *node = head->next, *tmp_node;
while (node != head && node->next != head) {
tmp_node = node->next->next;//相鄰兩節點交換前，先備份第3個節點位址到 tmp_node 變數中
list_swap(node, node->next);//相鄰兩節點交換
node = tmp_node;//載入新的節點
}
}
```
### q_reverse
將 `prev` 與 `next` 兩個指標的內容交換(可藉由 `tmp_node` 暫存)
1. `struct list_head` 為環狀佇列，當節點走訪一圈後就會回到 `head` 位址，利用此特點判斷 `while(node!=head)` 是否走訪一圈回到`head`
圖片來源：[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list?type=view#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)
2. 先做 `next_node=node->next` ，備份好下個節點
3. 每個節點逐一將 `prev` 與 `next` 兩個指標內儲存的地址交換(藉由 `tmp_node` 變數，暫存節點地址)
4. 離開前，記得 `head` 節點的 `prev` 與 `next` 也要交換
> Commit [`e8449fe`](https://github.com/blue76815/lab0-c/commit/e8449fec6aa6a7ee7cd459a00973e23a7141688b)
```c
void q_reverse(struct list_head *head) {
if ( head==NULL || list_empty(head)) {
return;
}
struct list_head *node=head->next,*next_node,*tmp_node;
while(node!=head)//判斷是否走訪一圈回到 head
{
/* prev 與 next 交換前，先備份好下個節點*/
next_node=node->next;
/*將 prev 與 next 兩個指標內儲存的地址交換*/
tmp_node=node->next;
node->next=node->prev;
node->prev = tmp_node;
/* 更新下一個節點*/
node=next_node;
}
/*離開前 記得 head 節點的 prev 與 next 也要交換*/
tmp_node = head->next;
head->next = head->prev;
head->prev = tmp_node;
}
```
### q_reverseK
1. 執行完 `list_cut_position(&new_cut_list, origin_list, cut_node)`，會形成兩個佇列。
* `new_cut_list`： 收留要被剪切的節點的新鍊錶
* `origin_list`： 要被剪切的舊鍊錶
* `cut_node`：剪切入口
2. 透過 q_reverse 反轉。
`q_reverse(&new_cut_list);`
3. 最後，透過 `list_splice_init(&new_cut_list, origin_list)` 將兩個佇列連結成一個佇列，並更新 `origin_list` 。
`origin_list` 作用類似假的 head，紀錄下一次切分佇列和連結佇列的位置。
```c
void q_reverseK(struct list_head *head, int k)
{
if ( head==NULL || list_empty(head) || k <= 1) {
return;
}
struct list_head *cur, *safe, *origin_list = head;
LIST_HEAD(new_cut_list);
int count = 0;
list_for_each_safe (cur, safe, head) {
count++;
if (count == k) {
/* step1.
執行完 list_cut_position(&new_cut_list, origin_list, cut_node)
，會形成兩個佇列。*/
list_cut_position(&new_cut_list, origin_list, cur);
/*step2.透過 q_reverse 反轉。 */
q_reverse(&new_cut_list);
/*
step3.最後，透過 list_splice_init(&new_cut_list, origin_list)
將兩個佇列連結成一個佇列，
*/
list_splice_init(&new_cut_list, origin_list);
count = 0;
/* 並更新 origin_list 。 */
origin_list = safe->prev;
}
}
}
```
### q_descend
根據 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)
函式功能:若**左邊節點數值 < 右邊節點數值**，則**刪除左邊節點**
* `list_del()` 只是將 node 從其原本的 linked list 連接移除
還得用 `q_release_element(node)` 才能將節點記憶體釋放
* 使用 `list_del()` 和 `q_release_element(node)` 的好處，在於**移除 link-list 節點時，不用煩惱如何將節點指向的 prev , next 位址做修正**
* `q_descend` 改從 `linked list` 尾端往回找，直到往回比較到 head 時，才停止
* 因為若從 head 端開始比較 **左邊節點數值 < 右邊節點數值**，會頻繁的將 head 節點刪除替換掉（步驟變多，時間複雜度變高）
* 所幸我們的 linked list 結構為 prev，next 雙向鍊結方向
* 因此我們改成從 linked list 尾端往回比較節點，直到往回比較到 head 時，才停止
* **這樣的優點是最多只移除1次 head 節點**，不用重複多次步驟移除 head 節點
走訪整個 linked list 時，有考慮選用
```c
list_for_each(node, head)
list_for_each_entry(entry, head, member)
```
但是根據 [你所不知道的 C 語言: linked list 和非連續記憶體-Linked list 在 Linux 核心原始程式碼](https://hackmd.io/@sysprog/c-linked-list#%E7%B0%A1%E5%8C%96%E7%9A%84%E5%AF%A6%E4%BD%9C)
> #### `list_for_each`
> ```cpp
> #define list_for_each(node, head) \
> for (node = (head)->next; node != (head); node = node->next)
> ```
>
> 走訪整個 linked list。注意: **`node` 和 `head` 不能在迴圈中被更改 (可能在多工環境中出現)，否則行為不可預期。**
>
> #### `list_for_each_entry`
> ```cpp
> #ifdef __LIST_HAVE_TYPEOF
> #define list_for_each_entry(entry, head, member) \
> for (entry = list_entry((head)->next, __typeof__(*entry), member); \
> &entry->member != (head); \
> entry = list_entry(entry->member.next, __typeof__(*entry), member))
> #endif
> ```
>
> 走訪包含 `struct list_head` 的另外一個結構之 entry。**`node` 和 `head` 不能在迴圈中被更改，否則行為不可預期。**
使用上面這兩種 API **`node` 和 `head` 不能在迴圈中被更改 (可能在多工環境中出現)，否則行為不可預期。**
考慮到我們 `q_descend` 在走訪整個 linked list 時，會有 list head 移除的情況
因此改用
> #### `list_for_each_safe` / `list_for_each_entry_safe`
> ```cpp
> #define list_for_each_safe(node, safe, head) \
> for (node = (head)->next, safe = node->next; node != (head); \
> node = safe, safe = node->next)
>
> #define list_for_each_entry_safe(entry, safe, head, member) \
> for (entry = list_entry((head)->next, __typeof__(*entry), member), \
> safe = list_entry(entry->member.next, __typeof__(*entry), member); \
> &entry->member != (head); entry = safe, \
> safe = list_entry(safe->member.next, __typeof__(*entry), member))
> ```
>
> 透過額外的 `safe` 紀錄每個迭代 (iteration) 所操作的節點的下一個節點，**因此目前的節點可允許被移走**，其他操作則同為不可預期行為。
但是若從 `head` 端開始比較 左邊節點數值 < 右邊節點數值，
**會頻繁的將 head 刪除替換掉（處理步驟變多，時間複雜度變高）**
所幸我們的 `linked list` 結構為 `prev`，`next` 雙向鍊結方向，
因此我們**改成從 `linked list` 尾端往回比較節點，**
直到往回比較到 `head` 節點時，才停止，
這樣的**優點是最多只移除1次 `head` 節點**
**不用重複多次步驟移除 `head` 節點**
> Commit [`ab7975a`](https://github.com/blue76815/lab0-c/commit/ab7975a069955e0c1c3753091745ee3eb056c68d)
```c
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
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 *curr = head->prev, *next = curr->prev 從 linked list 尾端往回找，直到往回比較到head時，才停止
// 因為若從 head 端開始比較 左邊節點數值 < 右邊節點數值，會頻繁的將 head 刪除替換掉（步驟變多，時間複雜度變高）
// 所幸我們的 linked list 結構為 prev，next 雙向鍊結方向，
// 因此我們改成從 linked list 尾端往回比較節點，直到往回比較到head時，才停止，
// 這樣的優點是最多只移除1次head節點
// 不用重複多次步驟移除 head 節點
struct list_head *curr = head->prev;
struct list_head *next = curr->prev;
while(next != head)
{
element_t *curr_entry = list_entry(curr, element_t, list);//取得節點資料
element_t *next_entry = list_entry(next, element_t, list);
if (strcmp(curr_entry->value, next_entry->value) > 0) {
list_del(next);// list_del() 只是將 node 從其原本的 linked list 連接移除
q_release_element(next_entry);//還得用 q_release_element(node) 才能將節點記憶體釋放
} else{
curr = next;
}
next = curr->prev; //從 linked list 尾端往回比較節點
}
return q_size(head);
}
```
#### 驗證函式功能
leetcode 考題**輸入的資料型態是 `int val` 數字變數**
但是我們的 q_descend()，**輸入的是 ASCII 字元或字串**
因此輸入 `cmd> it 13` 時不是常數 13
而是2個ASCII 字元的字串`1(0x31)` 和 `3(0x33)`
因此將 `cmd> it 13` **改成單一字元的資料**，
例如 ASCII 字元 9，就能符合 leetcode 考題結果
```
cmd> new
l = []
cmd> ih 5
l = [5]
cmd> it 2
l = [5 2]
cmd> it 9
l = [5 2 9]
cmd> it 3
l = [5 2 9 3]
cmd> it 8
l = [5 2 9 3 8]
cmd> descend
l = [9 8]
cmd>
```
### q_ascend
釐清 `q_ascend` 定義
從 `./qtest help`指令中，能查到
```
$ ./qtest
cmd> help
Commands:
...
ascend | Remove every node which has a node with a strictly less value anywhere to the right side of it
descend | Remove every node which has a node with a strictly greater value anywhere to the right side of it
```
ascend：刪除每個節點，只要該節點右側任意位置有一個值嚴格**小於**該值的節點
descend：刪除每個節點，只要該節點右側任意位置有一個嚴格**大於**該值的節點
回顧 `q_descend`
> descend：刪除每個節點，只要該節點右側任意位置有一個嚴格**大於**該值的節點
>
> 參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)
>
> > Remove every node which has a node with a **greater** value anywhere to the right side of it.
>
> ```c
> /* Remove every node which has a node with a strictly greater value anywhere to
> * the right side of it */
> 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 *curr = head->prev;
> struct list_head *next = curr->prev;
> while(next != head)
> {
> element_t *curr_entry = list_entry(curr, element_t, list);//取得節點資料
> element_t *next_entry = list_entry(next, element_t, list);
>
> if (strcmp(curr_entry->value, next_entry->value) > 0) {
> list_del(next);//list_del() 只是將 node 從其原本的 linked list 連接移除
> q_release_element(next_entry);//還得用 q_release_element(node) 才能將節點記憶體釋放
> } else{
> curr = next;
> }
>
> next = curr->prev; //從 linked list 尾端往回比較節點
> }
> return q_size(head);
> }
> ```
> descend：刪除每個節點，只要該節點右側任意位置有一個嚴格**大於**該值的節點
> 是根據
> `if (strcmp(curr_entry->value, next_entry->value) > 0)`
因此
ascend：刪除每個節點，只要該節點右側任意位置有一個值嚴格**小於**該值的節點
改成
`if (strcmp(curr_entry->value, next_entry->value) < 0)`
即可
> Commit [`d0eff68`](https://github.com/blue76815/lab0-c/commit/d0eff68008b4046e1d93be095349f94839fcbab1)
```c
/* Remove every node which has a node with a strictly less value anywhere to
* the right side of it */
int q_ascend(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 *curr = head->prev;
struct list_head *next = curr->prev;
while (next != head) {
element_t *curr_entry =
list_entry(curr, element_t, list); // 取得節點資料
element_t *next_entry = list_entry(next, element_t, list);
if (strcmp(curr_entry->value, next_entry->value) < 0) {
list_del(next); // list_del() 只是將 node 從其原本的 linked list
// 連接移除
q_release_element(next_entry); // 還得用 q_release_element(node)
// 才能將節點記憶體釋放
} else {
curr = next;
}
next = curr->prev; // 從 linked list 尾端往回比較節點
}
return q_size(head);
}
```
#### 驗證 ascend 功能
```shell
$ ./qtest
cmd> new
l = []
cmd> ih 5
l = [5]
cmd> it 2
l = [5 2]
cmd> it 9
l = [5 2 9]
cmd> it 3
l = [5 2 9 3]
cmd> it 8
l = [5 2 9 3 8]
cmd> ascend
l = [2 3 8]
cmd>
```
比較
```shell
cmd> new
l = []
cmd> ih 5
l = [5]
cmd> it 2
l = [5 2]
cmd> it 9
l = [5 2 9]
cmd> it 3
l = [5 2 9 3]
cmd> it 8
l = [5 2 9 3 8]
cmd> descend
l = [9 8]
cmd>
```
### q_sort（遞迴版）
參閱
* [你所不知道的 C 語言: linked list 和非連續記憶體 Merge Sort 的實作](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) 遞迴作法
* [freshLiver](https://hackmd.io/@freshLiver/2022q1-hw1#%E5%AF%A6%E4%BD%9C-queue-%E7%9B%B8%E9%97%9C%E5%87%BD%E5%BC%8F) 同學
* [kevinshieh0225](https://hackmd.io/@Masamaloka/2022q1-hw1) 同學
* 2025年作業版本-新增 `bool descend` 選項
> Commit [`4bf80c7`](https://github.com/blue76815/lab0-c/commit/4bf80c7b81a3914858da6052ece4a0ea1b94ab3a)
```c
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (head == NULL || list_empty(head)) {
return;
}
head->prev->next = NULL;
head->next = mergesort_list(head->next,descend);
struct list_head *ptr = head;
while (ptr->next != NULL) {
ptr->next->prev = ptr;
ptr = ptr->next;
}
ptr->next = head;
head->prev = ptr;
}
```
`mergesort_list()` 的詳細實做如下
```c
//2025 年 新增 bool descend 項
// 用來判斷
// * @descend: whether or not to sort in descending order
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2 , bool descend)
{
struct list_head *head = NULL;
struct list_head **ptr = &head;
for (; L1 && L2; ptr = &(*ptr)->next) {
element_t *L1_element_t = list_entry(L1, element_t, list);
element_t *L2_element_t = list_entry(L2, element_t, list);
if ((strcmp(L1_element_t->value, L2_element_t->value) <= 0)!= descend) {
*ptr = L1;
L1 = L1->next;
} else {
*ptr = L2;
L2 = L2->next;
}
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
static struct list_head *mergesort_list(struct list_head *head, bool descend)
{
if (!head || !head->next || list_is_singular(head))
return head;
struct list_head *slow = head;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *left = mergesort_list(head, descend), *right = mergesort_list(mid, descend);
return mergeTwoLists(left, right, descend);
}
```
其中
`if ((strcmp(L1_element_t->value, L2_element_t->value) <= 0)!= descend)`
是參照 實做 `ascend（）`和 `descend（）`時的設計原理
```c
// 遞增排序用
if (strcmp(curr_entry->value, next_entry->value) < 0)
來比較
/* Remove every node which has a node with a strictly less value anywhere to
* the right side of it */
int q_ascend(struct list_head *head)
{
if (strcmp(curr_entry->value, next_entry->value) < 0) {
list_del(next); // list_del() 只是將 node 從其原本的 linked list
// 連接移除
q_release_element(next_entry); // 還得用 q_release_element(node)
// 才能將節點記憶體釋放
} else {
curr = next;
}
}
// 遞減排序用
if (strcmp(curr_entry->value, next_entry->value) > 0)
來比較
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
if (strcmp(curr_entry->value, next_entry->value) > 0) {
list_del(next); // list_del() 只是將 node 從其原本的 linked list
// 連接移除
q_release_element(next_entry); // 還得用 q_release_element(node)
// 才能將節點記憶體釋放
} else {
}
}
```
```c
// 遞增排序用
if (strcmp(curr_entry->value, next_entry->value) < 0)
//來比較
// 遞減排序用
if (strcmp(curr_entry->value, next_entry->value) > 0)
//來比較
//所以加入 `bool descend` 判斷式時，就能合併表示成
if ((strcmp(L1_element_t->value, L2_element_t->value) <= 0)!= descend)
//用來切換 mode
```
### q_merge
研讀 [你所不知道的 C 語言: linked list 和非連續記憶體-Merge Sort 的實作](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)
> Commit [109b430](https://github.com/blue76815/lab0-c/commit/109b430ddd83afef094306b9b50b9d16bfbbeb2d)
```c
/* Merge all the queues into one sorted queue, which is in ascending/descending
* order */
int q_merge(struct list_head *head, bool descend)
{
// 1. 檢查 head 是否有效
if (!head || list_empty(head))
return 0;
if (list_is_singular(head)){
// 只有一個元素就直接回傳該 queue 的大小
queue_contex_t *single_node=list_entry(head->next, queue_contex_t, chain);
return single_node->size;
}
// 2. 建立一個「暫存 list」及變數
struct list_head tmp;
INIT_LIST_HEAD(&tmp);
int total_size = 0;
queue_contex_t *entry;
/*
* 3. 逐一把 head 裏的所有 queue context 的佇列
* 都 splice 到 tmp 這個暫存 list 中
*/
list_for_each_entry (entry, head, chain) {
// 將 entry->q 所有元素併到 tmp，並把 entry->q 清空
list_splice_tail_init(entry->q, &tmp);
total_size += entry->size;
entry->size = 0;
}
// 4. 對暫存 list 進行排序（升冪或降冪由 descend 決定）
q_sort(&tmp, descend);
// 5. 將排序好的 list 塞回其中一個 queue (例如第一個 queue 做目標)
queue_contex_t *target = list_entry(head->next, queue_contex_t, chain);
list_splice_tail_init(&tmp, target->q);
target->size = total_size;
// 6. 回傳合併後的總大小
return total_size;
}
```
### 驗證效能
目前在測試項
* trace-13-malloc
* trace-14-perf
* trace-16-perf
* trace-17-complexity
顯示以下異常，分析問題中
```shell
$ make test
....
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_reverse', and 'q_sort'
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 1000000.
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of 'q_sort' with random and descending orders: 'q_new', 'q_free', 'q_insert_head', 'q_sort', and 'q_reverse'
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', and 'q_reverse'
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of 'q_insert_tail', 'q_insert_head', 'q_remove_tail', and 'q_remove_head' is constant
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
Probably constant time
ERROR: Probably not constant time or wrong implementation
--- trace-17-complexity 0/5
--- TOTAL 95/100
make: *** [Makefile:61：test] 錯誤 1
```
## 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
```
$ make SANITIZER=1
$ make test
```
目前沒輸出有關 Address Sanitizer 異常的訊息
## 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
將 `/traces` 資料夾內的各測試項，各別做 Valgrind 測試
```
$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-02-ops.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-03-ops.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-04-ops.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-05-ops.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-06-ops.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-07-string.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-08-robust.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-09-robust.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-10-robust.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-11-malloc.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-12-malloc.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-13-malloc.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-14-perf.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-15-perf.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-16-perf.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-17-complexity.cmd
$ valgrind -q --leak-check=full ./qtest -f traces/trace-eg.cmd
```
```shell
$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd
==70264==ASan runtime does not come first in initial library list; you should either link runtime to your application or manually preload it with LD_PRELOAD.
```
請教 [chatgpt](https://chatgpt.com/share/67d4063a-fbc0-8006-a4e7-a62d169ebb98)
Valgrind 顯示，
> **Address Sanitizer 與 Valgrind 同時插樁，造成載入順序不正確**，以致出現「ASan runtime does not come first」的警告。最簡單的解法是：要測記憶體洩漏就單純用 Valgrind、要用 ASan 就單獨用 ASan，就不會遇到這個錯誤了。
先將 Address Sanitizer 關閉，再做 Valgrind 測試
```shell
$ make clean
$ make SANITIZER=0
$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd
```
### `$ valgrind -q --leak-check=full ./qtest -f traces/trace-14-perf.cmd` 測出異常
- [ ] 待分析原因
```shell
$ valgrind -q --leak-check=full ./qtest -f traces/trace-14-perf.cmd
cmd> # Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_reverse', and 'q_sort'
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih dolphin 1000000
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
cmd> it gerbil 1000000
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
l = [dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
Warning: Skip checking the stability of the sort because the number of elements 514174 is too large, exceeds the limit 100000.
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
Freeing queue
ERROR: Freed queue, but 2 blocks are still allocated
==75940== 47 bytes in 1 blocks are still reachable in loss record 1 of 3
==75940== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==75940== by 0x10F959: alloc (harness.c:146)
==75940== by 0x10FAAC: test_malloc (harness.c:176)
==75940== by 0x10FFB8: q_insert_tail (queue.c:64)
==75940== by 0x10CF88: queue_insert (qtest.c:233)
==75940== by 0x10D0A0: do_it (qtest.c:288)
==75940== by 0x10E9AA: interpret_cmda (console.c:214)
==75940== by 0x10ED54: interpret_cmd (console.c:234)
==75940== by 0x10EFEC: cmd_select (console.c:604)
==75940== by 0x10F8CD: run_console (console.c:684)
==75940== by 0x10DB4C: main (qtest.c:1444)
==75940==
==75940== 64 bytes in 1 blocks are still reachable in loss record 2 of 3
==75940== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==75940== by 0x10F959: alloc (harness.c:146)
==75940== by 0x10FAAC: test_malloc (harness.c:176)
==75940== by 0x10FF9C: q_insert_tail (queue.c:58)
==75940== by 0x10CF88: queue_insert (qtest.c:233)
==75940== by 0x10D0A0: do_it (qtest.c:288)
==75940== by 0x10E9AA: interpret_cmda (console.c:214)
==75940== by 0x10ED54: interpret_cmd (console.c:234)
==75940== by 0x10EFEC: cmd_select (console.c:604)
==75940== by 0x10F8CD: run_console (console.c:684)
==75940== by 0x10DB4C: main (qtest.c:1444)
==75940==
==75940== 64 bytes in 1 blocks are definitely lost in loss record 3 of 3
==75940== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==75940== by 0x10F959: alloc (harness.c:146)
==75940== by 0x10FAAC: test_malloc (harness.c:176)
==75940== by 0x10FEBB: q_insert_head (queue.c:37)
==75940== by 0x10CEEB: queue_insert (qtest.c:234)
==75940== by 0x10D0BC: do_ih (qtest.c:282)
==75940== by 0x10E9AA: interpret_cmda (console.c:214)
==75940== by 0x10ED54: interpret_cmd (console.c:234)
==75940== by 0x10EFEC: cmd_select (console.c:604)
==75940== by 0x10F8CD: run_console (console.c:684)
==75940== by 0x10DB4C: main (qtest.c:1444)
==75940==
```
根據
```
==75940== by 0x10FFB8: q_insert_tail (queue.c:64)
==75940== by 0x10FF9C: q_insert_tail (queue.c:58)
```
```c=52
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL || s == NULL)
return false;
element_t *node = malloc(sizeof(element_t));
if (node == NULL)
return false;
node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
if (node->value == NULL) {
q_release_element(node);
return false;
}
memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
memcpy(node->value, s, sizeof(char) * strlen(s));
list_add_tail(&node->list, head);
return true;
}
```
### `$ valgrind -q --leak-check=full ./qtest -f traces/trace-16-perf.cmd` 測出異常
- [ ] 待分析原因
```shell
$ valgrind -q --leak-check=full ./qtest -f traces/trace-16-perf.cmd
cmd> # Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', and 'q_reverse'
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih dolphin 1000000
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
l = [dolphin ... ]
cmd> it gerbil 1000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> it jaguar 1000
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
Freeing queue
ERROR: Freed queue, but 2 blocks are still allocated
==76718== 48 bytes in 1 blocks are still reachable in loss record 1 of 2
==76718== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76718== by 0x10F959: alloc (harness.c:146)
==76718== by 0x10FAAC: test_malloc (harness.c:176)
==76718== by 0x10FED7: q_insert_head (queue.c:41)
==76718== by 0x10CEEB: queue_insert (qtest.c:234)
==76718== by 0x10D0BC: do_ih (qtest.c:282)
==76718== by 0x10E9AA: interpret_cmda (console.c:214)
==76718== by 0x10ED54: interpret_cmd (console.c:234)
==76718== by 0x10EFEC: cmd_select (console.c:604)
==76718== by 0x10F8CD: run_console (console.c:684)
==76718== by 0x10DB4C: main (qtest.c:1444)
==76718==
==76718== 64 bytes in 1 blocks are still reachable in loss record 2 of 2
==76718== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==76718== by 0x10F959: alloc (harness.c:146)
==76718== by 0x10FAAC: test_malloc (harness.c:176)
==76718== by 0x10FEBB: q_insert_head (queue.c:37)
==76718== by 0x10CEEB: queue_insert (qtest.c:234)
==76718== by 0x10D0BC: do_ih (qtest.c:282)
==76718== by 0x10E9AA: interpret_cmda (console.c:214)
==76718== by 0x10ED54: interpret_cmd (console.c:234)
==76718== by 0x10EFEC: cmd_select (console.c:604)
==76718== by 0x10F8CD: run_console (console.c:684)
==76718== by 0x10DB4C: main (qtest.c:1444)
==76718==
```
根據
```
==76718== by 0x10FED7: q_insert_head (queue.c:41)
==76718== by 0x10FEBB: q_insert_head (queue.c:37)
```
```c=32
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (s == NULL || head == NULL)
return false;
element_t *node = malloc(sizeof(element_t));
if (node == NULL)
return false;
node->value = (char *) malloc(sizeof(char) * strlen(s) + 1);
if (node->value == NULL) {
q_release_element(node);
return false;
}
memset(node->value, '\0', sizeof(char) * strlen(s) + 1);
memcpy(node->value, s, sizeof(char) * strlen(s));
list_add(&node->list, head);
return true;
}
```
Sign in with Wallet
Connect another wallet