# 2025q1 Homework1 (lab0)
contributed by <`miaoshahaha`>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$lscpu
rchitecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-14500
CPU family: 6
Model: 191
Thread(s) per core: 2
Core(s) per socket: 14
Socket(s): 1
Stepping: 2
CPU(s) scaling MHz: 19%
CPU max MHz: 5000.0000
CPU min MHz: 800.0000
BogoMIPS: 5222.40
```
## 開發指定的佇列操作
### 開發準備
在實作 lab0-c 之前，要先詳閱 `queue.h` 以及 `list.h`，其中雙向鏈結串列的設計如下：
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
並且將 list_head 嵌入至結構體 element_t，可藉由 `container_of` 巨集推算出 list 節點的記憶體位址。
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
`container_of` 巨集可以在給定成員的型態及名稱，傳回成員的位址減去結構體的起始位址。
```c
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) - offsetof(type, member)))
```
### `q_new`
建立新的空佇列
```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;
}
```
先宣告一個 `list_head` 結構體 `head`，並且分配記憶體空間，如果分配空間失敗，則回傳 `NULL` ，這邊用到了 `INIT_LIST_HEAD`，可以將 `head` 的 `next` 跟 `prev` 指標指向自己。
這邊最一開始就要注意，當我們呼叫 `malloc` 的時候，並不保證每一次都會成功的分配記憶體空間，所以在呼叫 `malloc` 之後，必須確認是否成功分配記憶體空間，以防止 Segmentation Fault：
**C99 (7.20.3)**
> If the space cannot be allocated, a null pointer is returned.
### `q_free`
釋放佇列所佔用的記憶體空間
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *entry, *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
q_release_element(entry);
}
free(head);
}
```
當我們要釋放記憶體空間的時候，除了要釋放雙向環狀鏈結佇列之外，還必須
連帶將 `element_t` 結構體中的元素釋放，釋放的方法是遍歷佇列中每個節點，透過 `list_for_each_entry` 可以拜訪每個節點，而其程式碼為：
```c
#define list_for_each_entry(entry, head, member) \
for (entry = list_entry((head)->next, typeof(*entry), member); \
&entry->member != (head); \
entry = list_entry(entry->member.next, typeof(*entry), member))
```
裡面的 `list_entry` 就是藉由 `container_of` 來得知其中元素所在的記憶體位址為何。
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
### `q_insert_head`
在佇列開頭插入給定的新節點
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_ele = malloc(sizeof(element_t));
if (!new_ele)
return false;
new_ele->value = strdup(s);
if (!new_ele->value) {
free(new_ele);
return false;
}
list_add(&new_ele->list, head);
return true;
}
```
做插入的時候先分配記憶體空間給結構體 `element_t` ，並且用 `strdup` 函式複製字串，它可以將副本的起始位址的指標回傳，最後我們透過 `list_add` 來新增節點至佇列開頭的下一個位置。
### `q_insert_tail`
在佇列尾端插入給定的新節點
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_ele = malloc(sizeof(element_t));
if (!new_ele)
return false;
new_ele->value = strdup(s);
if (!new_ele->value) {
free(new_ele);
return false;
}
list_add_tail(&new_ele->list, head);
return true;
}
```
這裡的做法跟插入節點到開頭唯一的差別就是用到了 `list_add_tail`，
我們可以透過 `list_add` 以及 `list_add_tail` 來決定要將節點新增到頭部或尾端。
### `q_remove_head`
在佇列開頭移去給定的節點
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_first_entry(head, element_t, list);
if (sp) {
memcpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&ele->list);
return ele;
}
```
這裡的做法是要移去給定的節點，這裡有個要留意的地方是，在 `queue.h` 的標頭檔有說明 'remove' 和 'delete' 是不同的，我們只需要移除節點即可，而不需要釋放記憶體空間。
移去給定節點方法是，如果 `*sp` 不是 `NULL` 則將元素移除，並且將移除元素字串複製 `bufsize - 1` 的大小到 `*sp` ，然後在最後加上 NULL terminator。這裡找出字串位址的方法是透過 `list_first_entry` 這個巨集先找出元素的位址，再間接的找出元素中 `*value` 的位址。
再來有個困難的地方是如何將字串複製到 `*sp` ，直覺的想法是直接用 `strcpy` 或者是 `strncpy`，但我們需要的是 `bufsize - 1` 的大小，所以必須要給定一個複製的範圍，因此不能用 `strcpy`，所以想法是用 `strncpy` 來複製字串到 `*sp` 當中，不過這邊有個考量是，在 C 語言規格書中所規範的 `strncpy` 是：
**C99 (7.21.2.4)**
>If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.
如果複製字串小於我們所給定的大小，`strncpy` 會將超過原本字串的部分全部補 '0' ，因為是不必要的操作所以會導致效率不佳。其他的複製字串的方式就是使用 `memcpy`，它的差別是給定多少的大小，它就複製多少的空間，這個方法符合 `q_release_head` 的需求，所以我們只需要按照它的需求，複製 `bufsize - 1` 大小，並且在最後自行補上 NULL terminator 就可以。
### `q_remove_tail`
在佇列尾端移去給定的節點
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_last_entry(head, element_t, list);
if (sp) {
memcpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&ele->list);
return ele;
}
```
這裡的方法大致上跟 `q_remove_head` 相同，不一樣的地方在我們要移除的是尾端的節點，因此就用 `list_last_entry` 來得到尾端元素的記憶體位址，就可以做移除了。
### `q_size`
計算目前佇列的總節點量
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
struct list_head *next;
int cnt = 0;
list_for_each (next, head) {
cnt++;
}
return cnt;
}
```
這裡只要遍歷每個節點即可，用一個計數器來計算節點數量。
### `q_delete_mid`
移走佇列中間的節點
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *slow = head->next, *fast = head->next->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
element_t *del_ele = list_entry(slow, element_t, list);
list_del(&del_ele->list);
q_release_element(del_ele);
return true;
}
```
要找出中間節點的方法只要透過快慢指標就可以快速找到，當找到中間節點之後，再透過 `list_entry` 得到元素的記憶體位址，接著移除節點，並釋放元素佔據的記憶體空間即可，這裡透過 `queue.h` 中的靜態變數 `q_release_element` 來釋放元素記憶體空間。
### `q_swap`
```c
void q_swap(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *safe;
for (node = (head)->next, safe = node->next;
node != (head) && safe != (head);
node = node->next, safe = node->next) {
list_move(node, safe);
}
}
```
這邊要針對佇列中兩兩節點做交換，接著用 `list_move` 來交換節點。
### `q_reverse`
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *node;
struct list_head *safe;
list_for_each_safe (node, safe, head) {
list_move(node, head);
}
}
```
以反向順序重新排列鏈結串列，並且不配置額外的記憶體空間來操作，這個做法可以透過遍歷每個節點，並且將正在拜訪的節點移到頭部，如此即可將鏈結串列反向排列。
### `q_reverseK`
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head)
return;
struct list_head *tmp = head;
LIST_HEAD(tmp_head);
struct list_head *node, *safe;
int cnt = 0;
list_for_each_safe (node, safe, head) {
cnt++;
if (cnt == k) {
list_cut_position(&tmp_head, tmp, node);
q_reverse(&tmp_head);
list_splice_init(&tmp_head, tmp);
}
cnt = 0;
tmp = node->next;
}
}
```
透過 `q_release` 來進行反向順序的操作，並且使用計數器計算遍歷過的節點，當遍歷的節點等於 `k` ，便將該段串列進行反向排列。
## 在 qtest 提供新的命令 shuffle
在 `qtest.c` 中會呼叫 `console_init()` 命令，我們可以在 `console_init()` 中新增 `shuffle` 命令，觀察新增命令使用了 `ADD_COMMAND` 巨集如下：
```c
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
所以要建立新的命令，只要在 `qtest.c` 檔案中先提供 `do_*` 函式，並且在 `console_init()` 中新增即可，假設要新增 `shuffle` 命令：
```c
bool do_shuffle(int argc, char *argv[])
{
/* my_shuffle_function*/
return (bool) printf("Hello, World\n");
}
```
Sign in with Wallet
Connect another wallet