# 2023q1 Homework1 (lab0)
contributed by < `Lomomo` >
## 前言
:::spoiler
寫這段主要是來提醒和勉勵自己。
大學畢業到現在已經工作兩年，雖然拿到看似還過得去的薪水，但是因為自己的專業不足，對於每天自己產出爛程式碼的生活感到反感，於是來參加課程。
第一周的上課老師說很多所謂的得過且過、能動就好的那種半吊子工程師根本就是在說我，在 Maslow’s pyramid of code review 中，我的確連邊都摸不到。
**誠實面對自己，面對自己的不足**。
> [name=Vic Luo][time=Feb 17, 2023]
:::
<!-- ## 教材閱讀 -->
<!-- [GNU Make Manual Note](https://hackmd.io/@Lomomo/GNU_Make_Manual_Note) -->
<!-- ### 你所不知道的 C 語言: 開發工具和規格標準 -->
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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: 43 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 3700X 8-Core Processor
CPU family: 23
Model: 113
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 0
Frequency boost: disabled
CPU max MHz: 5040.9170
CPU min MHz: 2200.0000
BogoMIPS: 8200.08
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: 32 MiB (2 instances)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
```
## 開發過程
### 開發環境設定
`cppcheck` install from gitgub.
```shell
git clone https://github.com/danmar/cppcheck
sudo apt install libpcre3-dev
make install -j24 MATCHCOMPILER=yes FILESDIR=/usr/share/cppcheck HAVE_RULES=yes CXXFLAGS="-O2 -DNDEBUG -Wall -Wno-sign-compare -Wno-unused-function"
$ cppcheck --version
Cppcheck 2.11 dev
```
### q_insert_head
`head` 若為 `Null` 回傳 `false`.
要為 `element_t` 和 `element_t->value` 配置記憶體.
`strlen()` 回傳字串長度不包含 `\0`.
`strncpy()` 不會幫字串加入結尾字元, 必須另外處裡.
### q_remove_head
若 `head->next` 指向自己,表示 queue 為空.
`list_del` 在 `list.h` 中說明
> the node has to be handled like an uninitialized node.
使用 `list_del_init` 移除並初始化節點, 確保移除後節點內指標是安全的.
:question: 做到這邊發現我不知道怎麼取得 `element_t->value`.到 `qtest.c` 中觀察到 `q_show()` 有使用到 `list_entry` ,在這裡面還有 `container_of` 在教材中有搜尋到回去詳讀.
```c
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
```
參考 [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof "title")
`offsetof` 會回傳成員的位址減去 struct 的起始位址
> `offsetof` 會處理 struct 記憶體對齊的部份
:::spoiler `offsetof` example code
```c
#include <stddef.h>
#include <stdio.h>
struct data {
short a;
char b;
double c;
};
int main() {
struct data x = {.a = 25, .b = 'A', .c = 12.45};
char *p = (char *) &x;
printf("a=%d\n", *((short *) p));
p += sizeof(short);
printf("b=%c\n", *((char *) p));
p = (char *) &x + offsetof(struct data, c);
// p += sizeof(char);
printf("c=%lf\n", *((double *) p));
printf("p=%p, &x.c=%p\n", p, &(x.c));
printf("offsetof(struct data, c): %ld\n", offsetof(struct data, c));
}
```
```bash
$ ./main
a=25
b=A
c=12.450000
p=0x7ffe438c9c88, &x.c=0x7ffe438c9c88
offsetof(struct data, c): 8
```
下面是結果是直接對 struct member type 計算偏移的結果, 會有 padding 導致 c 得出的結果有誤.
```bash
./main
a=25
b=A
c=190346578428946467411813376969926036231236201599375216348857262157744255007426608362121915988857235308148337053537869186724122510073570901116281414778212356702476212757602596560790618112.000000
p=0x7ffc47e4ae73, &x.c=0x7ffc47e4ae78
```
:::
:bulb: 了解 `offsetof` 後, 回到作業中觀察, 就可以知道麼去獲取 `element_t` 的位置了.
展開 Macro 後如下
```c
// #define container_of(ptr, type, member)
container_of(head->next, element_t, list);
((element_t *) ((char *) (head->next) - offsetof(element_t, list)))
```
* `(char *) (head->next)` 在 element_t 中 list_head 的位址
* `offsetof(element_t, list)` element_t->list 的位址減去 struct 的起始位址
* 上述兩個位址相減就得到最外層 element_t 的位址
* 最後 `(element_t *)` 回傳
### q_reverse
利用 `list_for_each_safe` 的特性就可以順利的走訪 queue 及 `node->next` 和 `node->prev` 交換操作.
最後 `node` 會指回 `head` 即可完成 `head->next` 和 `head->prev` 交換的操作.
### q_delete_mid
剛開始就很直觀的直接去實做出來, 先計算 queue size 的一半的是多少, 然後走訪 queue 得到 middle 的位置.
在教材中有看到可以利用快慢指標的方式去取得之後再來改寫.
另外在 `qtest` 測試 `dm` 的過程中，有發現計算 queue 大小的變數 `current->size` 除了程式報錯的情況都會去執行 `current->size--` 的運算, 導致有負數的出現. 已經提交 Pull request 等待 code reivew.
下面為 gdb 除錯的紀錄
```
0x0000555555557dd8 in do_dm (argc=<optimized out>, argv=<optimized out>) at qtest.c:689
689 current->size--;
(gdb) c
Continuing.
Hardware access (read/write) watchpoint 1: current->size
Old value = 0
New value = -1
Hardware access (read/write) watchpoint 1: current->size
Value = -1
do_dm (argc=<optimized out>, argv=<optimized out>) at qtest.c:690
690 q_show(3);
```
使用快慢指針改進原本用計數取得中間節點的時間複雜度, 少了計算 queue 的大小, 使得時間複雜度從 $O(n^2)$ 變成 $O(n)$.
### q_swap()
初步思考如下圖，A 節點透過 `list_del`移出後, B 節點對於 C 節點後面的 list 即為 head node. 在透過 `list_add(A, B)` 把 A 節點加到 C list 的開頭, 這樣對於 A, B 兩節點即完成交換的動作. `list_del` 和 `list_add` 也已經在 list.h 封裝成 `list_move`.
在 `list_for_each` node 在 swap 完成後, 也就剛好指向下一對節點.
最後走訪所有節點, 執行上述步驟即完成 q_swap().
### q_sort()
嘗試去實做時, 因為 merge sort 需要取得中間節點, 就使用快慢指針回去改寫 get_middle_node 的方法.
閱讀教材的過程, 真的覺得自己理解指標變數的速度很慢, 特別要去理解間接指標的時候更覺得有挫折感, 下面是大概描述我看到這段程式腦海理解他的聲音，雖然感覺描述這段很沒有意義，但是就是有個結在卡在那的感覺，如果有更好的理解在麻煩多指教，不過追根究底我覺得還是指標的使用太少了，還得多多練習.
```c
// head 是指向結構體的變數, 存有結構體的位址
struct ListNode *head = malloc(stuct ListNode);
// ptr 是 pointer to pointer to struct ListNode 知道他是這樣但是感覺有點迷糊
struct ListNode **ptr = &head;
// ptr equal &head
// *ptr equal head
// **ptr equal *head equal struct Listnode
ptr = &(*ptr)->next
// ptr = &(head)->next
// ptr = &(*head).next
```
Sign in with Wallet
Connect another wallet