---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < `YSRossi` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping: 10
CPU MHz: 2600.000
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
:::warning
`lscpu` 套件提供的中文翻譯品質不佳，請先執行 `export LC_ALL=C` 再執行 `lscpu`，隨後更新上述硬體描述。
:notes: jserv
> 已更新
:::
## 開發過程
### `q_new`
動態配置 head 所需的記憶體並使用 `INIT_LIST_HEAD` 對其進行初始化。
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
:::warning
將 `malloc(sizeof(struct list_head))` 改為 `malloc(sizeof(*head))` 以簡化程式碼。
:notes: jserv
> 已更新
:::
### `q_free`
一開始檢查 `l` 是否為空，如果為空就將 `l` 釋放。
為了刪掉目前的元素後還能夠走訪下個節點，所以選擇 `list_for_each_entry_safe` 來逐一走訪每個節點並將其所佔用空間釋放。
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
if (!l || list_empty(l)) {
free(l);
return;
}
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, l, list) {
list_del(&entry->list);
q_release_element(entry);
}
free(l);
}
```
### `q_insert_head`
配置一個 `s` 字串長度加一 (`'\0'`)的空間給 `entry->value`，並將 `s` 複製到 `entry->value`， 最後使用 `list_add` 將 `entry` 加入 list 的開頭。
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *entry = malloc(sizeof(element_t));
if (!entry)
return false;
size_t len = strlen(s) + 1;
entry->value = malloc(len * sizeof(char));
if (!entry->value) {
free(entry);
return false;
}
memcpy(entry->value, s, len);
INIT_LIST_HEAD(&entry->list);
list_add(&entry->list, head);
return true;
}
```
:::warning
可以將`INIT_LIST_HEAD`移除，因為在下一行的list_add就會將entry->list的prev以及next配置
:notes: WilsonKuo
:::
### `q_insert_tail`
與 `q_insert_head` 作法相似，差在最後使用 `list_add_tail` 將 `entry` 加入 list 的尾端。
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *entry = malloc(sizeof(element_t));
if(!entry)
return false;
size_t len = strlen(s) + 1;
entry->value = malloc(len * sizeof(char));
if(!entry->value) {
free(entry);
return false;
}
memcpy(entry->value, s, len);
INIT_LIST_HEAD(&entry->list);
list_add_tail(&entry->list, head);
return true;
}
```
### `q_remove_head`
使用 `list_first_entry` 找到第一個元素，並使用 `list_del_init` 將該元素從串列中移走，最後使用 strncpy 將先前移走的元素的 `value` 複製到 `sp` 中。
```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 *entry = list_first_entry(head, element_t, list);
list_del_init(&entry->list);
if (sp) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return entry;
}
```
### `q_remove_tail`
與 `q_remove_head` 作法相似，差異是使用 `list_last_entry` 找到串列中最後一個 entry。
```c
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || list_empty(head))
return NULL;
element_t *entry = list_last_entry(head, element_t, list);
list_del_init(&entry->list);
if (sp) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return entry;
}
```
### `q_size`
使用 `list_for_each` 走訪整個佇列，使用 `size` 變數來紀錄總共的 elements 數量。
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
if (!head)
return -1;
int size = 0;
struct list_head *node = NULL;
list_for_each (node, head)
size++;
return size;
}
```
### `q_delete_mid`
正向 ： 往 `next` 的方向。
反向 ： 往 `prev` 的方向。
從 `head->next` 與 `head->prev` 分別往正向與反向走訪，直到雙方目前走訪的節點相同或是相鄰，即找到中間節點，將該點刪除並釋放。
```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;
}
list_del_init(forward);
element_t *entry = list_entry(forward, element_t, list);
q_release_element(entry);
return true;
}
```
### `q_delete_dup`
想法是目前節點是否與上個節點的 `value` 相同來決定要不要刪除上個節點，所以一串擁有相同 `value` 的節點當中的最後一個節點不會被刪除，因此使用 `del` 紀錄目前節點走訪到下個節點時是否也要刪除。
```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 || list_empty(head))
return false;
element_t *entry = NULL, *safe = NULL, *dentry = NULL;
char *val = "";
bool del = false;
list_for_each_entry_safe (entry, safe, head, list) {
if (!strcmp(entry->value, val)) {
if (list_last_entry(head, element_t, list) == entry) {
list_del(&entry->list);
q_release_element(entry);
}
list_del(&dentry->list);
q_release_element(dentry);
del = true;
} else {
if (del) {
list_del(&dentry->list);
q_release_element(dentry);
}
val = entry->value;
del = false;
}
dentry = entry;
}
return true;
}
```
### `q_swap`
因為 `list_move` 為 `list_del` 與 `list_add` 的組合，因為 `list_move` 會將目標串列的開頭做一次 `next`，即 `list_move(node, node->next)` 相當於將 `node` 接到 `node->next-next` 的前面，所以與 `list_for_each` 一起使用剛好可以使串列兩兩交換。
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *node = NULL;
list_for_each (node, head) {
if (node->next == head)
break;
list_move(node, node->next);
}
}
```
### `q_reverse`
將串列每個節點的 `next` 與 `prev` 交換。
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head) {
struct list_head *tmp = node->next;
node->next = node->prev;
node->prev = tmp;
}
struct list_head *tmp = head->next;
node->next = head->prev;
node->prev = tmp;
}
```
### q_reverseK
每走訪 K 個節點，將這 K 個走訪過的節點使用 `list_cut_position` 移到 `tmp` 做 `q_reverse` 後，使用 `list_splice_init` 插入原本的串列。
```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))
return;
int cnt = 0;
struct list_head *node = NULL, *safe = NULL, *from = head;
LIST_HEAD(tmp);
list_for_each_safe (node, safe, head) {
cnt++;
if (cnt == k) {
list_cut_position(&tmp, from, node);
q_reverse(&tmp);
list_splice_init(&tmp, from);
from = safe->prev;
cnt = 0;
}
}
}
```
### q_sort
原本思考如何利用與 `q_delete_mid` 一樣分別從頭與尾往中間走訪找中間節點的方式，搭配[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)中介紹的遞迴版本 merge sort 來實作，考量到過程會常常切割串列，為了能快速找到 `tail` ，還需維護 `prev` ，因此最後選擇用快慢指標尋找中間節點，排序完成後再將串列變回雙向環狀鏈結串列。
```c
static struct list_head *merge_two_lists(struct list_head *L1,
struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
element_t *node1 = list_entry(L1, element_t, list);
element_t *node2 = list_entry(L2, element_t, list);
node = (strcmp(node1->value, node2->value) <= 0) ? &L1 : &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
static struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast, *slow = head;
for (fast = head->next; fast && fast->next; fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *left = merge_sort(head), *right = merge_sort(mid);
return merge_two_lists(left, right);
}
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head *ptr;
for (ptr = head; ptr->next; ptr = ptr->next)
ptr->next->prev = ptr;
ptr->next = head;
head->prev = ptr;
}
```
### q_descend
從串列尾端 `head->prev` 往 `prev` 方向走訪每個節點，過程中紀錄到目前為止走過的節點的最大值 `max` ，並刪除比 `max` 小的節點。
```c
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
int total = 0, rm = 0;
char *max = list_last_entry(head, element_t, list)->value;
element_t *entry = NULL, *safe = NULL;
for (entry = list_entry((head)->prev, element_t, list),
safe = list_entry(entry->list.prev, element_t, list);
&entry->list != (head);
entry = safe, safe = list_entry(safe->list.prev, element_t, list)) {
total++;
if (strcmp(entry->value, max) < 0) {
list_del(&entry->list);
q_release_element(entry);
rm++;
} else
max = entry->value;
}
return total - rm;
}
```
### q_merge
剛開始的思考方向是如何找到其他佇列的 `head` ，後來在 `queue.h` 找到了管理佇列的 `queue_contex_t`，如此一來就可以使用目前已知的 `head` 搭配 `list_for_each_entry` 走訪每個佇列，將每個已排序的佇列接在一起並排序。
```c
/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head)
return 0;
LIST_HEAD(tmp);
queue_contex_t *qchain;
list_for_each_entry (qchain, head, chain)
list_splice_init(qchain->q, &tmp);
int size = q_size(&tmp);
q_sort(&tmp);
list_splice(&tmp, list_first_entry(head, queue_contex_t, chain)->q);
return size;
}
```
Sign in with Wallet
Connect another wallet