# 2023q1 Homework1 (lab0)
contributed by < [`kingkazma1109`](https://github.com/kingkazma1109) >
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
CPU family: 6
Model: 126
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 5
CPU max MHz: 3600.0000
CPU min MHz: 400.0000
BogoMIPS: 2380.80
Virtualization features:
Virtualization: VT-x
L1d: 192 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 2 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA node0 CPU(s): 0-7
```
## 開發過程
### q_new
依據 [malloc(3)](https://man7.org/linux/man-pages/man3/malloc.3.html#top_of_page) 的描述:
> On error, these functions return NULL.
可以得知當 malloc() 無法成功配置記憶體時，會回傳 `NULL` ，所以需要額外判斷使 `INIT_LIST_HEAD` 巨集能夠正常運作，同時，若在配置記憶體失敗時也能正常回傳 `NULL` 給呼叫端
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *newQueue = malloc(sizeof(struct list_head));
if (newQueue)
INIT_LIST_HEAD(newQueue);
return newQueue;
}
```
### q_free
首先排除 `NULL` 的情況後，接下來研讀 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)，我們得知 `list_for_each_entry_safe` 巨集可使我們安全的移除每一個經過的節點
> `list_for_each_entry_safe` - Iterate over list entries and allow deletes
使用 `list_del` 巨集從佇列移除節點並配合 `queue.h` 的 `q_release_element` 巨集釋放存放資料的空間
>`q_release_element()` - Release the element
即可逐一走訪佇列並安全的移除節點，最後再釋放指向佇列開頭的指標即可完全釋放所有為此佇列配置的所有記憶體
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *cur, *safe;
list_for_each_entry_safe (cur, safe, l, list) {
list_del(&cur->list);
q_release_element(cur);
}
free(l);
}
```
### q_insert_head
首先處理佇列為 `NULL` 的情況，再來為即將插入的節點配置空間，同前面 [q_new](https://hackmd.io/UnzxLIxFQ-eDGzwGhvji_w?both#q_new) 所提到的，若 `malloc` 配置記憶體失敗時會回傳 `NULL` ，所以要檢查配置是否成功，若成功則可以使用 [strdup(3) — Linux manual page
](https://man7.org/linux/man-pages/man3/strdup.3.html)來指派給新節點的 `value` 一個指向 `s` 的複製值的指標
> The `strdup()` function returns a pointer to a new string which is a duplicate of the string s.
同時我們也需要處理配置失敗的狀況，並透過 `q_release_element` 巨集來做釋放
> On success, the `strdup()` function returns a pointer to the duplicated string. It returns NULL if insufficient memory was available, with errno set to indicate the error.
排除所有例外狀況後，即可使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 的 `list_add` 巨集來將新的 `node` 放到佇列的開頭
>`list_add()` - Add a list node to the beginning of the list
最後再回傳 `true` 結束函式
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
node->value = strdup(s);
if (!node->value) {
q_release_element(node);
return false;
}
list_add(&node->list, head);
return true;
}
```
### q_insert_tail
作法和 [q_insert_head]() 一樣，最後使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 的 `list_add_tail` 巨集即可將新的節點放到佇列的尾端
> `list_add_tail()` - Add a list node to the end of the list
最後回傳 `true` 即可結束函式
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
node->value = strdup(s);
if (!node->value) {
q_release_element(node);
return false;
}
list_add_tail(&node->list, head);
return true;
}
```
### q_remove_head
首先處理 `head` 為 `NULL` 的情況以及利用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 的 `list_empty` 巨集來判斷佇列是否存在任何節點
>`list_empty()` - Check if list head has no nodes attached
接著使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 的 `list_first_entry` 巨集來取得佇列的第一個節點的資料位址
>`list_first_entry()` - Get first entry of the list
再來檢查傳入的字元陣列指標是否為 `NULL` ，檢查後即可使用 [strncpy](https://archive.kernel.org/oldlinux/htmldocs/kernel-api/API-strncpy.html) 來複製第一個節點的值到字元陣列
>`strncpy` — Copy a length-limited, C-string
但配置時預留最後一個空間放空字符來避免非預期的錯誤發生，最後從佇列移除節點，並回傳節點
```c
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&node->list);
return node;
}
```
### q_remove_tail
同 [q_remove_head](https://hackmd.io/UnzxLIxFQ-eDGzwGhvji_w?both#q_remove_head) 但使用 `list_last_entry` 巨集來取得最後一個節點
>`list_last_entry()` - Get last entry of the list
```c
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&node->list);
return node;
}
```
:::warning
TODO: 思考進一步縮減以上程式碼的方法，善用前置處理器。
:notes: jserv
:::
### q_size
先處理 `NULL` 的狀況，剩下的即可透過 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 的 `list_for_each` 巨集來計算迴圈次數得到結果
>`list_for_each` - Iterate over list nodes
最後回傳 `count` 結束函式
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
if (!head)
return 0;
int count = 0;
struct list_head *li;
list_for_each (li, head)
count++;
return count;
}
```
### q_delete_mid
除了上課提到的 [Floyd's tortoise and hare](https://en.wikipedia.org/wiki/Cycle_detection#:~:text=Floyd's%20cycle%2Dfinding%20algorithm%20is,The%20Tortoise%20and%20the%20Hare.) (快慢指標)的演算法外，老師也提示了可以從兩端往中間走會更有效率的解決找尋中點的問題。
做法一樣先判斷例外狀況，然後分別宣告一個從開頭往結尾走的指標，和一個結尾往開頭的指標，直到迴圈進行到兩者重疊或相鄰的狀況，即可透過 `list_entry` 巨集取得節點的資料地址，接著將節點從佇列中移除，最後再釋放存放的資料
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *forward = head->next, *backward = head->prev;
while (forward != backward && forward->next != backward) {
forward = forward->next;
backward = backward->prev;
}
element_t *middle = list_entry(forward, element_t, list);
list_del(&middle->list);
q_release_element(middle);
return true;
}
```
### q_delete_dup
一開始不確定題目回傳的布林值是代表 `true` 已經無重複節點或是 `true` 有刪除重複節點，以及誤會題目意思做成了刪除重複的節點成一個，導致花了大量時間修改測試，後來參考了 [paul90317](https://hackmd.io/@paul90317/linux2023-spring-lab0#q_delete_dup) 的筆記且精簡部份程式碼後得到以下的版本
用 `list_for_each_entry_safe` 巨集逐一走訪佇列並檢查當前節點與下一個是否重複，若是，則需要往後遞迴直到不相同的節點，最後再將重複節點的兩端接上
```c
/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
element_t *curr, *next, *temp;
list_for_each_entry_safe (curr, next, head, list) {
if (&next->list != head && !strcmp(curr->value, next->value)) {
do {
temp = next;
next = list_entry(next->list.next, element_t, list);
q_release_element(temp);
} while (&next->list != head && !strcmp(curr->value, next->value));
curr->list.prev->next = &next->list;
next->list.prev = curr->list.prev;
q_release_element(curr);
}
}
return true;
}
```
### q_swap
排除例外後，我們即可走訪佇列並透過一次移動兩步的方式，將佇列分成兩個為一組，值得一提的是，因為是先交換才移動指針，所以就等於移動兩步，接著每次都利用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 的 `list_del_init` 巨集移除當前節點並初始化，這裡沒有使用 `list_del` 巨集的原因是因為我們移除後會放回，所以初始化可以增加錯誤放回的難度，最後再透過 `list_add` 巨集將節點放到 `next` 節點的後面即可
>`list_del_init()` - Remove a list node from the list and reinitialize it
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *curr;
for (curr = head->next; curr != head && curr->next != head; curr = curr->next) {
struct list_head *next = curr->next;
list_del_init(curr);
list_add(curr, next);
}
}
```
### q_reverse
先處理 `NULL` 和無節點的情況，接著逐一走訪佇列，並且交換 `prev` 和 `next`，直到 `next` 再次指向 `head`
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *prev = head->prev, *curr = head, *next = NULL;
while (next != head) {
next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
}
```
### q_reverseK
先處理例外狀況後，利用 `list_for_each_safe` 巨集逐一走訪佇列，並且使用 `count` 來計算當前節點數量，當 `k` 個的時候，我們把當前指向的節點，也就是 `cur` 做為新片段的開頭，並宣告 `backward` 為指向 `cur` 前一個節點的指標，接著重複把 `backward` 的值指派給 `tmp` 並將 `tmp` 從佇列移除並且利用 `list_add` 巨集將其加到佇列的 `head` 參數的下一個位置，而這裡的 `head` 就是 `cur` 所以會不斷的更新到片段的結尾，最後迴圈結束前讓 `cur` 往前走一個節點， `backward` 往後走一個節點
```c
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head) || k <= 1)
return;
int count = 0;
struct list_head *cur, *next;
list_for_each_safe (cur, next, head) {
count++;
if (!count % k) {
count -= 1;
struct list_head *tmp = cur->prev;
while (count--) {
list_del(tmp);
list_add(tmp, cur);
cur = cur->next;
tmp = tmp->prev;
}
}
}
}
```
### q_sort
```c
```
### q_descend
```c
```
### q_merge
```c
```
Sign in with Wallet
Connect another wallet