# 2025q1 Homework1 (lab0)
**contributed by <`Today-Asked`>**
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ uname -a
Linux today-asked-MS-7E14 6.11.0-19-generic #19~24.04.1-Ubuntu SMP PREEMPT_DYNAMIC Mon Feb 17 11:51:52 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-12400
CPU family: 6
Model: 151
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 5
CPU(s) scaling MHz: 24%
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
```
## 實作 queue.[ch]
### `q_new`
> commit [f7abe63](https://github.com/Today-Asked/lab0-c/commit/f7abe636a054763018d98e2401adb1bf37f59623) （commit message 錯誤，待修改）
使用 `malloc` 分配一個 `list_head` 的空間給變數 `head`，使用巨集 `INIT_LIST_HEAD` 把 `prev` 與 `next` 都指向自身，然後回傳 `head`。
僅閱讀函式說明時，誤解為必須為 `queue_context_t` 分配空間，但在閱讀 `qtest.c` 以及 [Dennis40816](https://hackmd.io/@dennis40816/linux2025-homework1#q_new) 的紀錄後，才發現相關的實作細節已出現在 `qtest.c` 的 `do_new` 函式中：
```c
if (exception_setup(true)) {
queue_contex_t *qctx = malloc(sizeof(queue_contex_t));
list_add_tail(&qctx->chain, &chain.head);
qctx->size = 0;
qctx->q = q_new();
qctx->id = chain.size++;
current = qctx;
}
```
### `q_free`
>commit [82aceb3](https://github.com/Today-Asked/lab0-c/commit/82aceb397724ef78a926bdf91ad667fa5be8eab6)
也是在閱讀 `qtest.c` 後得知只需釋放單一佇列所佔的空間，因此我宣告一個指標 `li` 指向 `head->next`，使用 `list_entry()` 找到內嵌 `li` 的結構體 `element_t`，並且釋放該空間。
然而在初步編譯並執行 `make check` 後，執行 `free` 命令後出現了錯誤：
```
ERROR: Attempted to free unallocated block. Address = 0x56106b2170d8
ERROR: Attempted to free unallocated or corrupted block. Address = 0x56106b2170d8
Segmentation fault occurred. You dereferenced a NULL or invalid pointer.
```
我很納悶為何此處並非出現 AddressSanitizer 形式的錯誤訊息 **(待完成)**
總之在 copilot 的協助下，我才知道是因為原先未加上 `li != head` 的限制，導致迴圈存取到已經被釋放的記憶體。
修改上述不安全處，並且釋放並改用 `list_for_each_entry_safe` 巨集讓程式更簡短易讀後，最終程式如下：
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *e, *next_e;
list_for_each_entry_safe(e, next_e, head, list){
free(e->value);
free(e);
}
free(head);
}
```
### `q_insert_head` & `q_insert_tail`
>comment [1e4385b](https://github.com/Today-Asked/lab0-c/commit/1e4385bcd0492b9c0fe5780683de1a75192deea8)
先檢查 `head` 是否為 NULL，若是則回傳 `false`。
分配一塊空間予 `element_t` 結構體，並明確分配一塊空間予其 `value` 成員。
實施的記憶體安全措施包含：
1. 若 `malloc(sizeof(element_t))` 未成功，回傳 `false`
2. 使用 `strdup()` 指定一塊記憶體空間，複製傳入的字元指標，避免傳入指標處的記憶體被刪除而出現 dangling pointer 的問題。
### `q_remove_head` & `q_remove_tail`
>commit [6ffe018](https://github.com/Today-Asked/lab0-c/commit/6ffe018b5618f35ce12e92273e7d16009cfd7a5d)
此處不必釋放 `element_t` 的空間，因此只需對 `head->next` 進行
`list_del_init` 即可。
使用 `strncpy` 函式，避免緩衝區溢位。
### `q_size`
> commit [82aceb3](https://github.com/Today-Asked/lab0-c/commit/82aceb397724ef78a926bdf91ad667fa5be8eab6)
使用最原始的方法，遍歷過整個鏈結串列，回到頭時結束迴圈。
可能的改進方式: 使用快慢指標
### `q_delete_mid`
> commit
最直覺的方法是使用 `q_size()` 得到串列的長度並算出中間值，使用一個變數計算何時會到達該節點，並刪除之。
但我後來參閱 leetcode 上的解法後改為使用兩個指標，一個往前一個往後，當兩者相遇時刪除該節點，如此可以將時間縮短為一半。
### `q_delete_dup`
> commit
我花了很多時間才理解題意，一開始以為是對於一個隨機排列的串列刪除複製的節點，因此我原想使用雜湊表來完成。
後來看了很多同學（）的解法，才發現在呼叫之前佇列的值便已排列，因此只須注意前一個與本身的值是否相同。
另外使用一個 `del_last` 變數，判斷是否為最後一個被刪除的複製元素，若是則將其刪除。
### `q_swap`
> commit
利用 `list_del` 並未將對於每兩個節點，
### `q_reverse`
### `q_reverseK`
### `q_ascend` & `q_decend`
由於一開始沒有想法，我是參考這篇 [leetcode solution](https://leetcode.com/problems/remove-nodes-from-linked-list/solutions/6467872/0ms-100-runtime-c-easiest-approach-reverse-traversal-of-linekd-list/) 的作法，由後往前走過整個鏈結串列，（以 ascend 為例，）比較目前節點 `li` 和前一個節點 `prev` 的外嵌結構體（`e` 及 `prev_e`）值，當前一個節點的值大於自身時刪除前者，否則將目前節點移至前一個，繼續走訪串列直到回到 `head`。
在撰寫的過程中遇到了 Segmentation fault 的情況，後發現是因未處理兩個結構體的值相等的情況，導致程式陷入無限迴圈而記憶體傾印。
## 疑問
為何 `list_del` 只是將節點從鏈結串列中移除，並未釋放記憶體，函式名稱卻是 delete 而非 remove？
查看 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中與 `list_del` 相關的程式碼：
```c
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
WRITE_ONCE(prev->next, next);
}
/*
* Delete a list entry and clear the 'prev' pointer.
*
* This is a special-purpose list clearing method used in the networking code
* for lists allocated as per-cpu, where we don't want to incur the extra
* WRITE_ONCE() overhead of a regular list_del_init(). The code that uses this
* needs to check the node 'prev' pointer instead of calling list_empty().
*/
static inline void __list_del_clearprev(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->prev = NULL;
}
static inline void __list_del_entry(struct list_head *entry)
{
if (!__list_del_entry_valid(entry))
return;
__list_del(entry->prev, entry->next);
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
```
發現 `list_del` 的說明的確就是 "deletes entry from list."
查看 `git blame`，發現這段程式是由 Linus Torvalds 在 2005 年上傳（我想這應該是），此後未再修改，然而 [Linus Torvalds 的演講](https://www.ted.com/talks/linus_torvalds_the_mind_behind_linux) 中作為範例的函式 `remove_list_entry`，執行的也是將一個節點從鏈結串列中移除，這代表他在 2013 年也認同 [remove 的定義](https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove)，那麼為何函式名稱並非後綴 `remove`，是沿用習慣，還是當時並未清楚定義兩者差別？
Sign in with Wallet
Connect another wallet