# 2025q1 Homework1 (lab0)
contributed by < `eastWillow` >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ uname -a
Linux jens 6.8.0-52-generic #53~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Wed Jan 15 19:18:46 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

$ 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:          48 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 7800X3D 8-Core Processor
    CPU family:           25
    Model:                97
    Thread(s) per core:   2
    Core(s) per socket:   8
    Socket(s):            1
    Stepping:             2
    CPU max MHz:          5050.0000
    CPU min MHz:          545.0000
    BogoMIPS:             8399.99

## 閱讀 driver.py 了解成績標準

針對執行順序與檢查的項目來寫作業，要把時間花在刀口上，卡超過2 天就參考同學的寫法
單獨執行檢查分數的指令`scripts/driver.py -c`

## trace-01-ops.cmd
### q_new
> commit [1acccae](https://github.com/eastWillow/lab0-c/commit/1acccae7ac89fb753e764ffec1da813e2e139d38)

參考第一周作業

### q_insert_head
> commit [c01a625](https://github.com/eastWillow/lab0-c/commit/c01a62591e079ea581720af9273f4154a0448072)

發現 string.h 當中原來有 strdup 可以直接使用
練習都使用 `$ man strdup` 當記憶體無法成功配置的時候會回傳 NULL
根據前面的作業練習，要考慮這些fail 的情境
因為還有發現malloc 失敗的比例是可以設定的，代表這件事情很重要，先放在心上

### q_remove_head
> commit [96d8835](https://github.com/eastWillow/lab0-c/commit/96d8835b9206c13538e8c16d03782db81fb2cea7)

想了一陣子發現一個關鍵第一個節點當作head ，必須是第二個節點以後才能使用`list_entry`

附上Debug 用的表達式
`(element_t*)((char*)head->next - (sizeof(element_t) - sizeof(struct list_head)))`

### q_free

隱藏關卡，這一題沒有寫qtest 會跳錯誤
ERROR: Freed queue, but 1 blocks are still allocated

### q_insert_tail (do_it)

參考 q_insert_head

### q_size
## trace-02-ops.cmd
### q_remove_tail (do_rt)

參考 q_remove_head, 因為是circular linkage list, 直接使用 head->prev

### q_delete_mid (do_dm)

[n / 2]th node from the start using 0-based indexing

驗算一下公式

$$
\begin{split}
i_middle &= \frac{n_{size}}{2} \\
[0, 1] ,\ n_{size} = 2,\ i &= 1, \text{result is} [1] \\
[0, 1, 2, 3, 4],\ n_{size} = 5,\ i &= 2, \text{result is} [2] \\
[0, 1, 2, 3],\ n_{size} = 4,\ i &= 2, \text{result is} [2] \\
\end{split}
$$

## trace-03-ops.cmd
### q_sort (do_sort)
`$ man strcmp`
> strcmp, strncmp - compare two strings
> `int strcmp(const char *s1, const char *s2);`
> • 0, if the s1 and s2 are equal;
> • a negative value if s1 is less than s2;
> • a positive value if s1 is greater than s2.

descending order is : 5, 4, 3, 2, 1

排列演算法先直接使用第一周作業
[2025 年春季「Linux 核心設計」第 1 週測驗題](/wOuZnVe6Q9ejvhXWGDfJ0Q)
附上當時寫隨堂測驗的心得 [第一週: 誠實面對自己](/Qf67pg3IRUKWPX5QQWKEGg)

### q_merge (do_merge)
這裡傳入的`list_head *head` 是 `&chain.head`，所以看物件的角度要換成chain
`(queue_contex_t*)((char*)head->next - (sizeof(queue_contex_t) - sizeof(struct queue_chain_t)))`

queue_contex_t *node = list_entry(head->next, queue_contex_t, chain);
拿到第一個queue

list_is_singular(&node->chain) 才是代表第一個queue 的head_list *head

> 參考 [2025 年 Linux 核心設計課程作業 —— lab0 (E)](/age56DtJQ_uwupRMOt1c5Q)
> [你所不知道的 C 語言: linked list 和非連續記憶體](/YA7RMqd6RE2UL8OmmjU9PQ#案例探討-LeetCode-21-Merge-Two-Sorted-Lists)
> 參考 Linux 核心原始程式碼的 lib/list_sort.c 當中的Merge
需要注意 sort stability [排序的穩定與不穩定](/qnzUlNwOS-uf4MFWIAkYLQ)

因為卡住超過三天，研究一下其他同學的寫法

> https://hackmd.io/@Charlie1123/linux2025-homework1 merge 的寫法最接近教材

取得第一個 a list
`(element_t*)((char*)a->next - (sizeof(element_t) - sizeof(struct list_head)))`

取得第二個 b list
`(element_t*)((char*)b->next - (sizeof(element_t) - sizeof(struct list_head)))`

#### (gdb) lanuch trace-03-ops.cmd

如果有人想要使用vscode + gdb 可以參考以下這一部的設定，剩下使用vscode 的預設就可以了

"program": "${workspaceFolder}/qtest",
"args": [
    "-v",
    "3",
    "-f",
    "traces/trace-03-ops.cmd"
],
"cwd": "${workspaceFolder}",

### q_reverse (do_reverse)
## trace-04-ops.cmd
### q_swap
## trace-05-ops.cmd
## trace-06-ops.cmd
### q_delete_dup
### q_descend
### q_reverseK
## 代辦
### Malloc failure probability percent

### 重購

改用 list_is_singular

### sort stability

### 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)

### 研讀論文〈Dude, is my code constant time?〉

### 指出lab0的缺陷或者可改進之處

### 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

### 運用 Valgrind 排除 qtest 實作的記憶體錯誤

### 研讀 [2025 年 Linux 核心設計課程作業 —— lab0 (E)](/age56DtJQ_uwupRMOt1c5Q)