# 2024q1 Homework1 (lab0)
contributed by < `syuan1017` >
## 開發環境
```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: 44 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 4800H with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU max MHz: 2900.0000
CPU min MHz: 1400.0000
BogoMIPS: 5789.61
Virtualization features:
Virtualization: AMD-V
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 4 MiB (8 instances)
L3: 8 MiB (2 instances)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
```
### 安裝必要開發套件
```shell
$ sudo apt install build-essential git-core valgrind
$ sudo apt install cppcheck clang-format aspell colordiff
```
| 套件 | 描述 |
| ------ | ----------- |
| build-essential | meta-package |
| git-core | version control system package |
| valgrind | dynamic Binary Instrumentation (DBI) framwork|
| cppcheck | static analysis tool for C/C++ code |
| clang-format | automatically formatting C, C++, Objective-C, and Objective-C++ code |
| aspell | spell Checking |
| colordiff | enhances the output of the diff tool |
## 研讀過程
:::warning
補上對應的超連結
:::
根據 [The Linux Kernel API - List Management Functionse](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)，list_del_init_careful() 與 list_empty_careful 能夠保證記憶體操作順序，但對於其中 smp_store_release() 的操作不了解
```c
static inline void list_del_init_careful(struct list_head *entry)
{
__list_del_entry(entry);
WRITE_ONCE(entry->prev, entry);
smp_store_release(&entry->next, entry);
}
```
## 指定佇列操作的實作
### `q_new`
根據 C99 規格書，malloc 函式的返回值有可能是 null pointer，因此必須先檢查返回值是否為 null pointer 在進行後續操作
* C99 [7.20.3.3-3] The malloc function returns either a null pointer or a pointer to the allocated space.
### `q_free`
在執行 make check 過程中出現以下錯誤訊息
> Segmentation fault occurred. You dereferenced a NULL or invalid pointermake: *** [Makefile:57: check] Aborted (core dumped)
嘗試開啟 SANITIZER 做進一部分析錯誤原因，並找出錯誤的程式碼位置，最後透過 gdb 觀察發現 `element_t *ele` 所指向的位置已經執行 free，因此 `cur->next` 就會存取非法記憶體位置，此處修改為取得當前節點的結構體位置後，就將指標 `cur` 指向前一個節點
> SUMMARY: AddressSanitizer: heap-use-after-free /home/alan/linux2024/lab0-c/queue.c:33 in q_free
```diff
void q_free(struct list_head *head)
{
struct list_head *cur;
if (!head)
return;
list_for_each(cur, head) {
element_t *ele;
list_del(cur);
ele = list_entry(cur, element_t, list);
+ cur = cur->prev;
free(ele->value);
free(ele);
}
free(head);
}
```
:::danger
使用 `git diff` 或 `diff -u` 命令來產生程式碼之間的變更列表，避免憑感覺填入，注意位移量。
:::
參考 `list.h` 後發現巨集 `list_for_each_safe(node, safe, head)` 透過預先紀錄下一個節點，來達成在走訪鏈結串列的過程中允許刪除當前節點，因此將程式碼進行修正
```diff
void q_free(struct list_head *head)
{
- struct list_head *cur;
+ struct list_head *cur, *next;
if (!head)
return;
- list_for_each (cur, head) {
- element_t *ele;
+ list_for_each_safe (cur, next, head) {
+ element_t *ele = list_entry(cur, element_t, list);
list_del(cur);
- ele = list_entry(cur, element_t, list);
- cur = cur->prev;
free(ele->value);
free(ele);
}
```
### `q_insert_head` \ `q_insert_tail`
在實作此兩函式是中透過 strdup 來將輸入的字串複製到節點內
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
/* Duplicate of the string s */
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
list_add(&ele->list, head);
return true;
}
```
根據 man page 的 `strdup(3)` 中說明:
> 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).
其中是透過 `malloc(3)` 來取得新的空間，因此必須先檢查返回值是否為 null pointer 在進行後續操作
### `q_remove_head` \ `q_remove_tail`
分別透過巨集 `list_first_entry` 和 `list_last_entry` 來取得欲移除的節點，根據 C99 規格書說明，若陣列 s2 長度小於 n，會以 null 字元將剩餘的長度填滿，因此此處不再額外判斷節點內所儲存的字串長度 (C99 [7.21.2.4-3])
> If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele;
ele = list_first_entry(head, element_t, list);
if (sp)
strncpy(sp, ele->value, bufsize - 1);
list_del(&ele->list);
return ele;
}
```
原本預期透過 `strncpy` 來複製字串，若`ele->value` 的長度小於 `bufsize - 1` 會自動補滿空字元，但透過 make test 發現會有錯誤，會將整個包括後面的 'x' 全部印出來，因此修正為複製完字串後再加上空字元
```diff
- if (sp)
- strncpy(sp, ele->value, bufsize - 1);
+ if (sp) {
+ size_t copy_size =
+ strlen(ele->value) > bufsize - 1 ? bufsize - 1 : strlen(ele->value);
+ strncpy(sp, ele->value, copy_size);
+ sp[copy_size] = '\0';
+ }
```
### `q_size`
觀察到 `q_size()` 會被 `do_size()`, `do_sort()`, `do_ascend()`, `do_descend()` 等函式所呼叫，而在上述函式中就會檢查該佇列是否有建立過，因此不再重複檢查，此處透過巨集 `list_for_each` 走訪整個佇列並計算節點總量。
### `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/description/) ，此處採用快慢指標來取得 middle node
> TODO: 思考是否有效率更佳的作法
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *fast = head->next;
struct list_head *slow = head->next;
while ((fast != head) && (fast->next != head)) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
element_t *ele = list_entry(slow, element_t, list);
free(ele->value);
free(ele);
return true;
}
```
### `q_delete_dup`
> [commit 6576b49](https://github.com/sysprog21/lab0-c/commit/6576b493a54f424bfef38602a5bbc67eaf31e40a)
此題對應到 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/) ，主要差別在於 LeetCode 是使用單向鏈結串列實作，而本作業是採用環狀雙向鏈結串列實作，因此不須額外紀錄前一個節點，並搭配 `list_for_each_entry_safe` 來走訪整個佇列，並透過 `list_del` 將節點從鏈結串列中移除並在釋放記憶體空間
### `q_swap`
此題對應到 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/description/) ，透過 while 迴圈逐一檢查是否有一對節點可以進行置換，並透過 `list_move` 將當前節點移除並插入到下一個節點之後
```c
void q_swap(struct list_head *head)
{
if (!head)
return;
struct list_head *cur = head->next;
while ((cur != head) && (cur->next != head)) {
list_move(cur, cur->next);
cur = cur->next;
}
}
```
### `q_reverse`
> [commit b4aa1b7](https://github.com/sysprog21/lab0-c/commit/b4aa1b73af52058da5844ee2de0259cb2f51bd36)
此題與 [LeetCode 206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/description/) 風格相似，而此處實作採用 `list_for_each_safe` 走訪除了最後一個節點外的每個節點，依序將當前節點從鏈結串列中移除，接著再新增到最後一個節點之後
### `q_reverseK`
此題對應到 [LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/description/)，此處透過兩個暫時的鏈結串列 `tmp_head` 與 `revs_head`，在走訪鏈結串列的過程中一次將 K 個節點透過 `list_cut_position` 搬移到 `revs_head` 並反轉鏈結串列，接著在透過 `list_splice_tail` 搬移到 `tmp_head`，剩餘原本鏈結串列中不足 K 個的節點則不作任何動作，最後在透過 `list_splice` 將節點全不搬移回到原本的轉鏈結串 `head` 中
>TODO:
>1. 本實作是透過 `list_for_each_safe` 來走訪鏈結串列，而巨集說明有告知當前節點是允許被移除的，但對鏈結串列的其他修改會造成不預期的行為，因此此處須再做確認
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head)
return;
LIST_HEAD(tmp_head);
LIST_HEAD(revs_head);
struct list_head *cur, *next;
size_t i = 0;
list_for_each_safe (cur, next, head) {
if (++i == k) {
list_cut_position(&revs_head, head, cur);
q_reverse(&revs_head);
list_splice_tail(&revs_head, &tmp_head);
i = 0;
}
}
list_splice(&tmp_head, head);
}
```
### `q_sort`
### `q_ascend` \ `q_descend`
> [commit ac74909](https://github.com/syuan1017/lab0-c/commit/ac7490931ade595c02a99b354d1b931e6917adf6)
此題對應到 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)，本實作在走訪鏈結串列的過程中，透過 `ele_r` 和 `ele_l` 來作走訪過程中的比較並刪除對應的節點
### `q_merge`
## 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 lab0-c 中
Sign in with Wallet
Connect another wallet