# 2024q1 Homework1 (lab0)
contributed by < [`poabob`](https://github.com/POABOB/lab0-c) >
## 開發環境
> Mackbook Pro M1 with lima.
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: 0x00
Model: 0
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 0x0
BogoMIPS: 48.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp a
simdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 asimddp
sha512 asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpo
dp flagm2 frint
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
```
## 實作指定的佇列操作
### `q_new`
> commit: [cc603ed](https://github.com/POABOB/lab0-c/commit/cc603ed7f2afa0f5fa3f962c47a597626d04fd89)
:::danger
allocate 的翻譯是「配置」，以區格 dispatch (分發/分配) 的翻譯
:::
先<s>分配</s> 記 `list_head` 憶體空間，如果分配不到記憶體直接返回 `NULL`；反之，就可以使用 [`void INIT_LIST_HEAD(struct list_head *list)`](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.INIT_LIST_HEAD) 來初始化一個空的鏈結串列。
```c
struct list_head *q = malloc(sizeof(struct list_head));
/* If q didn't allocate space */
if (!q) return NULL;
/* Initialize a list_head structure */
INIT_LIST_HEAD(q);
```
在 [list.h](https://github.com/torvalds/linux/blob/805d849d7c3cc1f38efefd48b2480d62b7b5dcb7/include/linux/list.h#L35) 中，可以發現 `INIT_LIST_HEAD()` <s>函數</s> 函式是使用 `WRITE_ONCE()` 對來將 `next` 和 `prev` 指定為自己。
:::danger
對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 [time](https://man7.org/linux/man-pages/man2/time.2.html) 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。另外，對於更一般的描述，function 會指「功能」一類的意涵，應合適挑選譯詞。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
```c
static inline void INIT_LIST_HEAD(struct list_head *list)
{
WRITE_ONCE(list->next, list);
WRITE_ONCE(list->prev, list);
}
```
在 [linux/tools/include/linux/compiler.h](https://github.com/torvalds/linux/blob/805d849d7c3cc1f38efefd48b2480d62b7b5dcb7/tools/include/linux/compiler.h#L200C1-L206C3) 中，是使用 `marco`，而不是單純的 `list->next = list`，在 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC) <s>有非常詳細的說明</s>。
:::danger
不用特別提「有非常詳細的說明」，本該如此，你該闡述自己的洞見。
:::
```c
#define WRITE_ONCE(x, val) \
({ \
union { typeof(x) __val; char __c[1]; } __u = \
{ .__val = (val) }; \
__write_once_size(&(x), __u.__c, sizeof(x)); \
__u.__val; \
})
```
簡單來說，看到 `volatile` 關鍵字，主要是告訴編譯器：
1. 這筆操作不能進行 `編譯器優化`，避免 `執行順序` 可能發生變換。
1. 確保 CPU `不會從暫存器讀值`，而是 `從記憶體重新讀`。
:::danger
查閱 C 語言規格書，並予以解讀。
:::
### `q_size`
> commit: [cc603ed](https://github.com/POABOB/lab0-c/commit/cc603ed7f2afa0f5fa3f962c47a597626d04fd89)
使用 `list_for_each` 來計算整個鏈結串列有幾個節點。
```c
int q_size(struct list_head *head)
{
if (!head) return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head) len++;
return len;
}
```
> `list_for_each` 只能使用 `不刪除節點` 的時候使用，若是 `需要刪除節點` 就需要使用 [`list_for_eac_safe`](https://hackmd.io/@sysprog/c-linked-list#list_for_each_safe--list_for_each_entry_safe)，這個巨集會幫你記錄 next 節點，避免當前節點被刪除找不到下一個節點在哪。
### `q_free`
> commit: [cc603ed](https://github.com/POABOB/lab0-c/commit/cc603ed7f2afa0f5fa3f962c47a597626d04fd89)
在 [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof#container_of-%E5%B7%A8%E9%9B%86%E4%BD%9C%E7%82%BA%E8%B3%87%E6%96%99%E5%B0%81%E8%A3%9D%E7%9A%84%E5%9F%BA%E7%A4%8E) 中有提到，`container_of` 則在 `offsetof` 的基礎上，擴充為「給定成員的位址、struct 的型態，及成員的名稱，**傳回該結構體的位址**」。
使用 while 來逐一找尋元素的地址，再透過 `q_release_element` 將該節點釋放。
```c
void q_free(struct list_head *head)
{
if (!head) return;
struct list_head *current = head->next;
while (head != current) {
element_t *e = container_of(current, element_t, list);
current = current->next;
q_release_element(e);
}
free(container_of(head, element_t, list));
}
```
:::danger
\# Delete queue. Goes back to a NULL queue.
ERROR: Attempted to free unallocated block. Address = 0xaaaae2c479d8
ERROR: Attempted to free unallocated or corrupted block. Address = 0xaaaae2c479d8
ERROR: Corruption detected in block with address 0xaaaae2c479d8 when attempting to free it
Segmentation fault occurred. You dereferenced a NULL or invalid pointermake: *** [Makefile:57: check] Aborted (core dumped)
:::
這邊遇到 `Segmentation fault occurred` 原因是因為 `head` 本身就沒有 `element_t`，我卻使用 `container_of` 去找元素的位址，理所當然回傳一個 NULL。
> commit: [d803afa](https://github.com/POABOB/lab0-c/commit/d803afa2670e3baaca42e0c4f4b39621aa6c7de0)
```diff
- free(container_of(head, element_t, list));
+ free(head);
```
### `q_insert_head`
> commit: [cc603ed](https://github.com/POABOB/lab0-c/commit/cc603ed7f2afa0f5fa3f962c47a597626d04fd89)
在新增一個元素時，先申請 `element_t` 記憶體空間，然後原本想使用 `strcpy`，但是看到別人使用 `strdup` 後，才知道 `strdup` 會順便申請該字串的記憶體空間，並返回該指標。
:::danger
assign 不該偷懶地翻譯為「賦值」，明明 assign 是個常見詞彙，你何時在英語課程聽到「賦值」的解釋？本例來說，可寫作「將指標的內含值指派給某變數」。
改進你的漢語表達。
:::
再來將 `c` 的指標<s>賦值</s> 給 `el->value` ，使用 [Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.list_add) 的 `list_add` 將其與 `head` 串起來。
```c
element_t *el = malloc(sizeof(element_t));
if (!el) return false;
char *c = strdup(s);
if (!c) {
free(el);
return false;
}
el->value = c;
list_add(&el->list, head);
```
### `q_insert_tail`
> commit: [cc603ed](https://github.com/POABOB/lab0-c/commit/cc603ed7f2afa0f5fa3f962c47a597626d04fd89)
這個函數與 [`q_insert_head`](https://hackmd.io/cHKtZ0waRkyPaVDzWZHb2w?both#q_insert_head) 邏輯一樣，只不過最後使用 `list_add_tail()`。
### `q_remove_head`
> commit: [cc603ed](https://github.com/POABOB/lab0-c/commit/cc603ed7f2afa0f5fa3f962c47a597626d04fd89)
先判斷 head 為 `NULL` 還是 `empty`，避免後續操作失敗。
再使用 `list_first_entry()` 獲取第一個元素，也就是要刪除並返回的。
透過 `strncpy` 將該元素的值複製到 `sp`，並在最後用 `\0` 來結尾。
> 這邊使用 `strncpy` 而不是 `strcpy` 是避免 `sp` 的空間如果不夠，就會產生 `buffer overflow`，`strncpy` 可以控制複製長度。
最後，把該元素從鏈結串列中刪除，返回該元素。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) return NULL;
element_t *target = list_entry(head, element_t, list);
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(head->next);
return target;
}
```
### `q_remove_tail`
> commit: [cc603ed](https://github.com/POABOB/lab0-c/commit/cc603ed7f2afa0f5fa3f962c47a597626d04fd89)
這個<s>函數</s> 與 [`q_remove_head`](https://hackmd.io/cHKtZ0waRkyPaVDzWZHb2w?both#q_remove_head) 邏輯一樣，只不過最後使用 `list_last_entry()`。
### `q_delete_mid`
> commit: [cc603ed](https://github.com/POABOB/lab0-c/commit/cc603ed7f2afa0f5fa3f962c47a597626d04fd89)
這個函數可以定義兩個指標，分別叫做 `slow` 和 `fast`。
- `slow` 每次迭代的時候會走訪一個節點。
- `fast` 每次迭代的時候會走訪兩個節點。
這樣當 `fast` 走訪結束之後，`slow` 就會是中間節點，就可以把它刪除。
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || empty(head)) return false;
struct list_head *fast = head->next, *slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
### q_delete_dup
> commit: [bfa16e4](https://github.com/POABOB/lab0-c/commit/bfa16e46a2306ddc6e163af6d9667a88cd41de25)
假定一個鏈結串列已經經過排序了，那麼可以使用 `list_for_each_safe` 來判斷 `左 (i)` `右 (i+1)` 兩個節點中的元素是否相同。
如果相同就把 `左節點 (i)` 給刪除，並往下走訪接續的節點。
最後要注意如果當 `右節點 (i+1)` 與我們的 `head` 相同，就代表該鏈結串列已走訪完畢。
```c
struct list_head *left, *right;
list_for_each_safe (left, right, head) {
element_t *l_el = list_entry(left, element_t, list),
*r_el = list_entry(right, element_t, list);
if (left->next != head && strcmp(l_el->value, r_el->value) == 0) {
list_del(left);
q_release_element(l_el);
}
}
```
### q_reverse
> commit: [3cdf0f8](https://github.com/POABOB/lab0-c/commit/3cdf0f84ccba62ec7bea03e29c4360e1c3194579)
這個函數也是可以用 `list_for_each_safe` 來執行，把 `left->next` 指向 `left->prev`，再把 `left->prev` 指向 `right`，這樣就可以逐一將每個節點進行反轉。
```c
struct list_head *left, *right;
list_for_each_safe (left, right, head) {
left->next = left->prev;
left->prev = right;
}
```
### q_swap
> commit: [085613b](https://github.com/POABOB/lab0-c/commit/085613b890cbbe1f246d0137019e9856453caad3)
```c
struct list_head *left, *right;
list_for_each_safe(left, right, head) {
if (!count) {
struct list_head *temp = left;
left->next = right->next;
left->prev->next = right;
left->prev = right;
right->next = left;
right->prev = temp->prev;
count = 1;
} else if (count) {
count = 0;
right->prev = left->next;
}
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
Sign in with Wallet
Connect another wallet