# 2024q1 Homework1 (lab0)
contributed by < [gawei1206](https://github.com/gawei1206) >
#### Reviewed by `HenryChaing`
>盡量提供 commit 連結，或是關鍵程式碼。
其餘的 review 在底下有留言
## 開發環境
```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: 39 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-7300HQ CPU @ 2.50GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 4999.90
```
## 指定的佇列操作
### `q_new`
:::danger
allocate 的翻譯是「配置」，以區格 dispatch (分發/分配) 的翻譯。
:::
一開始沒有注意到記憶體配置失敗的後續處理，後來有加上條件式去判斷，最後透過 `list.h` 中的函式 `INIT_LIST_HEAD` 來完成初始化
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### `q_free`
:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
透過 `list_for_each_entry_safe()` 來走訪每個 `entry` ，再釋放 `entry` 中 `value` 及 `list` 的空間，巨集`q_release_element` 已完成這部份實作，最後釋放 `head` 的空間
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
:::
### `q_insert_head` / `q_insert_tail`
函式 `strdup()` 會將字串複製到新的位置上，若成功會回傳位址，失敗則回傳 NULL ，最後透過 `list_add()` / `list_add_tail()` 將新的節點插入
發現在 `trace-11-malloc` 及 `trace-12-malloc` 中有出現ERROR，處理 `strdup(s)` 失敗的情況
```diff
- char *tem = strdup(s);
- node->value = tem;
+ if (!(node->value = strdup(s))) {
+ free(node);
+ return false;
+ }
```
> 如果可以請附上對應的 commit 紀錄，或是補上關鍵程式碼說明。
> [name=HenryChaing]
### `q_reverse`
走訪所有節點，並將他們插入到 `head`
使用 `list_for_each_safe()` 來走訪所有節點，並配合 `list_del()` 和 `list_add()` 將節點插入至 head ，但發現 `list_move()` 已經實作此功能，後來改正過來使程式碼更精簡
### `q_delete_mid`
透過快慢指標可以快速的找出中間的節點
透過快慢指標找出中間節點後，刪除該節點並釋放使用的空間，但應該有可以寫的更好的地方
```c
struct list_head *slow = head, *fast = head;
while (fast->next != head && fast->next->next != head) {
fast = fast->next->next;
slow = slow->next;
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
### `q_remove_head` / `q_remove_tail`
>"remove" is different from "delete"
>The space used by the list element and the string should not be freed.
>The only thing "remove" need to do is unlink it.
>Return: the pointer to element, %NULL if queue is NULL or empty.
根據題目需求，只需要找到第一個或最後一個節點，取出字串並以 `strncpy()` 複製到 `sp` 中，最後使用 `list_del()` 將節點刪除
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
:::
### `q_reverseK`
>This function should not allocate or free any list elements
>(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head)
透過 `list_cut_position` 將佇列切成兩段，兩段的 `head` 分別是 `tmp_head` 及 `start` ，將第一段的佇列經過 `q_reverse` 後再以 `list_splice_init` 接回去，
```c
struct list_head *start = head, tmp_head;
list_for_each_safe (node, safe, head) {
cnt++;
if (cnt == k) {
cnt = 0;
list_cut_position(&tmp_head, start, node);
q_reverse(&tmp_head);
list_splice_init(&tmp_head, start);
start = safe->prev;
}
}
```
### `q_swap`
`q_swap` 為 `q_reverseK` 中 `K = 2` 的特例，直接呼叫 `q_reverseK` 即可
### `q_delete_dup`
以 `list_for_each_entry_safe` 走訪每個節點，並比較當前節點與下個節點是否相等，若相等則移除，比較需要注意的地方是，當走訪到最後一個節點時並不需要再與下一個節點作比較，因為最後一個節點指向的是 `head` 如果對其取值會報錯
```c
if (node->list.next != head && strcmp(node->value, safe->value) == 0)
```
### `q_ascend` / `q_descend`
讀錯題目意思了，以 `q_ascend` 來說，題意為如果某一節點右邊存在小於他的節點，則應該刪除他自己，所以應該從最後一個節點往回做，就可以保證結果是非嚴格遞增的
> commit [caf198d](https://github.com/gawei1206/lab0-c/commit/caf198da9cb874b1a8809d6d7e43526bce997f44)
:::danger
使用你 fork 得到的 GitHub repository 超連結，亦即該以 https://github.com/gawei1206 開頭。
:::
<s>但在這題中 `remove` 的意思是需要把空間釋放掉嗎？</s>
> 已在 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) 澄清
### `q_sort`
參考 [youjiaw](https://github.com/youjiaw/lab0-c) ，先透過遞迴使串列中的節點變成單一節點，再透過自行定義的函式將已排序的子串列合併起來
> commit [a91a57f2](https://github.com/gawei1206/lab0-c/commit/a91a57f21f6cda5302bcb3d5914ac958d55f9bf8)
:::danger
你如何確保目前的測試資料已涵蓋排序演算法的最差狀況？
:::
### `q_merge`
利用 `chain` 逐一走訪各個佇列，再透過自行定義的函式將第二個到最後一個佇列一一與第一個佇列合併。
>commit [12f95f04](https://github.com/gawei1206/lab0-c/commit/12f95f048e4db2eb2516b84d38085a69f2711afd)
### `container_of`
:::danger
不懂就說不懂，沒有「不是很明白」這回事。
:::
作業中很常使用此巨集但不懂他是如何運作的，所以查看 [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)，看到 `offsetof` 部份內容時，不懂 `data` 結構中的成員 `c` 他的偏移量為什是8，後來發現 [The Lost Art of Structure Packing](http://www.catb.org/esr/structure-packing/) 中有寫到
> In general, a struct instance will have the alignment of its widest scalar member.
還有在宣告結構成員時應該注意宣告的順序，避免不需要的 alignment，以減少結構的大小
:::danger
搭配閱讀 x86-64 ABI 規格書，以得知 alignment 的作用。
:::
`offsetof` 用來得知 struct 中某一 member 的位址相對於該 struct 起始位址的距離，而 `container_of` 是只要得知某一 member 的位址，就可以利用它進一步推算出 struct 的起始位址。
> - [Linux鏈結串列struct list_head 研究 ](https://myao0730.blogspot.com/2016/12/linux.html)
> - [Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)
TODO:解決以下情況
```shell
+++ 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
```
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
## 其他閱讀
[Teach Yourself Programming in Ten Years
](https://norvig.com/21-days.html)
1. 專業技能發展需要時間：引用了多位學者和專業人士的觀點，強調成為一名專家通常需要約十年的時間或10000小時的練習，並且這個過程中沒有真正的捷徑。
2. 實踐經驗的重要性：強調了實際撰寫程式碼的經驗、與其他開發者的交流，這些都遠比單純的書本知識更為重要。
> - Program. The best kind of learning is learning by doing.
> - Talk with other programmers; read other programs. This is more important than any book or training course.
**實作**以及**交流**十分重要，不論在這篇文章中還是課堂的內容都一再強調。
> 盡量使用文章格式而非列點式描述。少用 $*$ 、 $-$ 列出想要描述的內容，用文章的方式撰寫有助於面試時完整回答問題。
> [name=HenryChaing]
TOREAD:
[每位程式開發者都該有的記憶體知識](https://sysprog21.github.io/cpumemory-zhtw/)
Sign in with Wallet
Connect another wallet