# 2025q1 Homework1 (lab0)
contributed by <`wx200010`>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ hostnamectl
Operating System: Ubuntu 24.04.2 LTS
Kernel: Linux 6.11.0-17-generic
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.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): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 14
Socket(s): 1
Stepping: 3
CPU(s) scaling MHz: 39%
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 5376.00
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 544 KiB (14 instances)
L1i: 704 KiB (14 instances)
L2: 11.5 MiB (8 instances)
L3: 24 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-19
```
## 開發指定的佇列操作
### `q_new`
> [Commit 95096ed](https://github.com/wx200010/lab0-c/commit/95096edd077febeb7070b5b820f227f9b8e6d633)
`q_new` 需要對新配置的 head 進行初始化，正好 linux kernel API 提供了 `INIT_LIST_HEAD` 來初始化 head 的 `next` 和 `prev` 指標，因此我用了該巨集來簡化程式碼：
```c
struct list_head *q_new()
{
return NULL;
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### `q_free`
> [Commit 95096ed](https://github.com/wx200010/lab0-c/commit/95096edd077febeb7070b5b820f227f9b8e6d633)
`q_free`的目的是釋放整條 queue 所佔用的記憶體，因此我使用了`list_for_each_entry_safe` 來走訪整條 queue 並釋放記憶體。
不過在一開始的版本中，我額外使用了 `list_del` 巨集來確保每個節點從串列中被移除，如下：
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *curr = NULL, *next = NULL;
list_for_each_entry_safe (curr, next, head, list) {
list_del(&curr->list);
free(curr->value);
free(curr);
}
free(head);
}
```
然而這步是多餘的，因為整條串列在經過`q_free`處理後就被釋放記憶體了，不能再被訪問，因此最後的版本便拔掉了多餘的程式碼：
```diff
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *curr = NULL, *next = NULL;
list_for_each_entry_safe (curr, next, head, list) {
- list_del(&curr->list);
free(curr->value);
free(curr);
}
free(head);
}
```
### `q_size`
> [Commit 7ec6f4e](https://github.com/wx200010/lab0-c/commit/7ec6f4ee3ed5698a801e703cf1df4b83a407bea1)
`q_size` 的目的是回傳整條串列的節點總數，這步驟可以依靠`list_for_each`巨集來走訪整條串列：
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *it;
list_for_each (it, head)
len++;
return len;
}
```
### `q_insert_head` 與 `q_insert_tail`
> [Commit 9dccf54 （最新）](https://github.com/wx200010/lab0-c/commit/9dccf548e760c1145043896c12bf7cecba39dea4)
> [Commit 143dc94](https://github.com/wx200010/lab0-c/commit/143dc94cded5bb64d245a05d6a0e32bd46dbaab4)
> [Commit 06b615d](https://github.com/wx200010/lab0-c/commit/06b615defd202e5a1b7b265b8cf6c558310dc973)
> [Commit c29bb5a](https://github.com/wx200010/lab0-c/commit/c29bb5ae13c8b239fb05ff5c41a058e0b68376a2)
> [Commit 3d17f18 （最舊）](https://github.com/wx200010/lab0-c/commit/3d17f1822f6313ac6af96a4069ca39be80c232d3)
這兩者都需要配置一個新節點並插入到queue中，只差在新節點會被插在 head 或是 tail，因此我額外撰寫了一段inline函數 `q_insert` 來簡化程式碼，其中參數 `insert_func` 會決定插入時是使用 `list_add` 或 `list_add_tail`，程式碼如下：
```c
/*
* Insert an element at the head or tail of the queue, depending on the caller.
* This function simplifies the implementation of q_insert_head and
* q_insert_tail.
*/
static inline bool q_insert(struct list_head *head,
char *s,
void (*insert_func)(struct list_head *,
struct list_head *))
{
if (!head)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
new->value = strdup(s);
if (!new->value) {
free(new);
return false;
}
insert_func(&new->list, head);
return true;
}
bool q_insert_head(struct list_head *head, char *s)
{
return q_insert(head, s, list_add);
}
bool q_insert_tail(struct list_head *head, char *s)
{
return q_insert(head, s, list_add_tail);
}
```
注意到`q_insert`在複製參數`s`字串值到新配置的節點時，可以使用`strdup`函數來完成。
之前我使用`strlen(s) + 1`來計算出完整字串長度，再使用`strncpy`來複製字串。然而僅使用`strdup`便能達到相同效果，又能節省程式碼。
> `strdup`的部份參考了[allen741的code](https://github.com/allen741/lab0-c/blob/master/queue.c#L73)。
> 設計 `q_insert` 來簡化程式碼的部份，參考了[25077667的code](https://github.com/25077667/lab0-c/blob/dev/queue.c#L261)
### `q_remove_head` 與 `q_remove_tail`
> [Commit 8b56ec1（最新）](https://github.com/wx200010/lab0-c/commit/8b56ec1661dcc6fe8d1f17cf00575fb265d0ac2a)
> [Commit 06b615d](https://github.com/wx200010/lab0-c/commit/06b615defd202e5a1b7b265b8cf6c558310dc973)
> [Commit 5804494（最舊）](https://github.com/wx200010/lab0-c/commit/5804494c768eabb0b36270576c8f2f30670e8176)
這兩者函式的差別與上面的 insert 一樣，只差在刪除的節點是在開頭或結尾，因此我也是額外設計了一份 inline 函式 `q_remove` 來簡化程式碼，參數`node`即是需要被刪除的節點，程式碼如下：
```c
/*
* Remove an element from the head or tail of the queue, depending on the
* caller. This function simplifies the implementation of q_remove_head and
* q_remove_tail.
*/
static inline element_t *q_remove(struct list_head *head,
struct list_head *node,
char *sp,
size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *entry = list_entry(node, element_t, list);
list_del(&entry->list);
if (sp) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return entry;
}
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
return q_remove(head, head->next, sp, bufsize);
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
return q_remove(head, head->prev, sp, bufsize);
}
```
注意到在刪除節點的部份，可以使用 `list_del` 巨集來實現。
> 設計 `q_remove` 來簡化程式碼的部份，參考了[25077667的code](https://github.com/25077667/lab0-c/blob/dev/queue.c#L271)
### `q_delete_mid`
> [Commit 0c17e9d](https://github.com/wx200010/lab0-c/commit/0c17e9d6a63a1cc8d69dcfc355a10eab50861744)
該函式的難點在於如何定位 middle node，這部份我參考了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List)與[快慢指標](https://hackmd.io/@sysprog/ry8NwAMvT)。在得到 middle node 後便可使用 linux kernel API 提供的 `list_entry` 和 `list_del` 巨集來處理移除節點並釋放記憶體的部份。
相關程式碼如下：
```c
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;
/* Find the middle node in queue */
struct list_head *del_node = head->next;
for (const struct list_head *ptr = head->next;
ptr != head && ptr->next != head; ptr = ptr->next->next) {
del_node = del_node->next;
}
/* Delete the middle node */
element_t *del = list_entry(del_node, element_t, list);
list_del(del_node);
free(del->value);
free(del);
return true;
}
```
### `q_swap`
> [Commit a52438d](https://github.com/wx200010/lab0-c/commit/a52438d0d9b6dae2047f3763a68dd8ccb5ae1cef)
q_swap需要將兩兩相鄰的節點進行互換，因此我使用了兩個指標`L`與`R`來處理兩兩互換的部份，程式碼如下：
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *L = head->next, *R = L->next;
while (L != head && R != head) {
/* swap L and R node */
L->prev->next = R;
R->next->prev = L;
R->prev = L->prev;
L->next = R->next;
L->prev = R;
R->next = L;
L = L->next;
R = L->next;
}
return;
}
```
> 實際上可以改用`list_move`完成，程式碼相當精簡，請見[LIAO-JIAN-PENG的code](https://github.com/LIAO-JIAN-PENG/lab0-c/blob/master/queue.c#L215)
### `q_reverse`
> [Commit d816356](https://github.com/wx200010/lab0-c/commit/d816356261fdd4f2ab42205a3ec8d7a92f07bb39)
該函式需要將整條串列進行反轉，我的想法是走訪整條串列並逐一把每個節點的`prev`與`next`指標值進行交換，走訪的部份則靠`list_for_each_safe`來實現：
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node, *safe = NULL;
list_for_each_safe (node, safe, head) {
node->next = node->prev;
node->prev = safe;
}
safe = head->next;
head->next = head->prev;
head->prev = safe;
}
```
### `q_merge`
> [Commit a9d3750](https://github.com/wx200010/lab0-c/commit/a9d3750306fa26324c89a0f0049b9f062c01bc87)
在[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)中，有提到如何合併兩條已排序的串列，因此我設計了`merge_two_lists`函式來完成兩兩合併的功能。
```c
/* Merge two list from the first element*/
struct list_head *merge_two_lists(struct list_head *L1,
struct list_head *L2,
bool descend)
{
/* Indirect pointer method */
struct list_head *head = NULL, **ptr = &head, **node;
for (node = &L1; L1 && L2; *node = (*node)->next) {
node = ((strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) <= 0) ^
descend)
? &L1
: &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
> 注意到`merge_two_lists`是基於單向非環狀鏈結串列上設計使用的，因此在本次作業的雙向環狀鏈結串列上，會需要做額外處理（詳情請見下方q_merge的程式碼）
> 該想法參考了[millaker的code](https://github.com/millaker/lab0-c/blob/master/queue.c#L375)
而`q_merge`需要將多條串列進行合併，同樣在[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)中也有提到關於合併效率的問題，若是每次都拿第一條串列來合併剩下的串列，會導致合併速度越來越慢，因此我選擇了開頭跟結尾兩兩合併的實現方式，程式碼如下：
```c
/* Merge all the queues into one sorted queue, which is in ascending/descending
* order */
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
int chain_size = q_size(head);
// Convert each queue to a non-circular linked list.
for (struct list_head *p = head->next; p != head; p = p->next) {
list_entry(p, queue_contex_t, chain)->q->prev->next = NULL;
}
// Merge all the queues into one sorted queue
struct list_head *L, *R = head->prev;
while (chain_size > 1) {
L = head->next;
while (L != R) {
queue_contex_t *contex_L = list_entry(L, queue_contex_t, chain);
queue_contex_t *contex_R = list_entry(R, queue_contex_t, chain);
contex_L->q->next =
merge_two_lists(contex_L->q->next, contex_R->q->next, descend);
contex_L->size += contex_R->size;
contex_R->q->prev = contex_R->q->next = contex_R->q;
R = R->prev;
if (L == R)
break;
L = L->next;
}
chain_size = (chain_size + 1) >> 1;
}
/* Restore the first queue to circular doubly Linked List */
struct list_head *q_head = list_entry(head->next, queue_contex_t, chain)->q;
L = q_head;
while (L->next != NULL) {
L->next->prev = L;
L = L->next;
}
L->next = q_head;
q_head->prev = L;
return list_first_entry(head, queue_contex_t, chain)->size;
}
```
該程式碼會先將每條queue各自轉換成非環狀鏈結串列，就能使用`merge_two_lists`函式來實現合併，最後只剩一條queue時再重新維護`prev`指標與環狀結構就完成了。
> 同樣，該想法參考了[millaker的code](https://github.com/millaker/lab0-c/blob/master/queue.c#L375)，只差在我將其改變成頭尾兩兩合併的實現方式。
### `q_sort`
> [Commit af24429](https://github.com/wx200010/lab0-c/commit/af24429d3049f73f4f751cd65a50a14a882980e9)
q_sort的目的是要將 queue 裡的 elements 進行排序。由於queue是雙向環狀鏈結串列，因此我的作法是先將queue轉換成非環狀鏈結串列(把`head->prev->next`設為NULL)後，再使用先前學到的`mergesort_list`函數來實現非環狀串列的合併排序。
> 這部分參考了[你所不知道的 C 語言: linked list 和非連續記憶體 - Merge Sort 的實作](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)
可以注意到的是，`mergesort_list`函數也需要尋找到 middle node，因此也會使用到快慢指標的方法，以下是相關程式碼：
```c
/* Perform merge sort on the list. */
struct list_head *mergesort_list(struct list_head *head, bool descend)
{
if (!head || !head->next)
return head;
struct list_head *slow = head, *mid, *left, *right;
for (const struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
mid = slow->next;
slow->next = NULL;
left = mergesort_list(head, descend);
right = mergesort_list(mid, descend);
return merge_two_lists(left, right, descend);
}
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return;
head->prev->next = NULL;
head->next = mergesort_list(head->next, descend);
/* Fix the prev pointer */
struct list_head *p = head;
while (p->next != NULL) {
p->next->prev = p;
p = p->next;
}
p->next = head;
head->prev = p;
}
```
### `q_delete_dup`
> [Commit b3d23af](https://github.com/wx200010/lab0-c/commit/b3d23af0e575aa7b4b2a295c1b53df44b75fb2ba)
### `q_reverseK`
> [Commit c355a99](https://github.com/wx200010/lab0-c/commit/c355a99ccce111a0b7dff0b7d9992403136a1bce)
### `q_ascend`
> [Commit 103efdd](https://github.com/wx200010/lab0-c/commit/103efdd3bc286d0aeb8bfb4ecda7418111b57424)
### `q_descend`
> [Commit 103efdd](https://github.com/wx200010/lab0-c/commit/103efdd3bc286d0aeb8bfb4ecda7418111b57424)
Sign in with Wallet
Connect another wallet