HackMD
2025q1 Homework1 (lab0)
contributed by <wx200010>
開發環境
$ 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
q_new 需要對新配置的 head 進行初始化，正好 linux kernel API 提供了 INIT_LIST_HEAD 來初始化 head 的 next 和 prev 指標，因此我用了該巨集來簡化程式碼：
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
q_free的目的是釋放整條 queue 所佔用的記憶體，因此我使用了list_for_each_entry_safe 來走訪整條 queue 並釋放記憶體。
不過在一開始的版本中，我額外使用了 list_del 巨集來確保每個節點從串列中被移除，如下：
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處理後就被釋放記憶體了，不能再被訪問，因此最後的版本便拔掉了多餘的程式碼：
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
q_size 的目的是回傳整條串列的節點總數，這步驟可以依靠list_for_each巨集來走訪整條串列：
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 （最新）
Commit 143dc94
Commit 06b615d
Commit c29bb5a
Commit 3d17f18 （最舊）
這兩者都需要配置一個新節點並插入到queue中，只差在新節點會被插在 head 或是 tail，因此我額外撰寫了一段inline函數 q_insert 來簡化程式碼，其中參數 insert_func 會決定插入時是使用 list_add 或 list_add_tail，程式碼如下：
/*
* 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。
設計q_insert來簡化程式碼的部份，參考了25077667的code
q_remove_head 與 q_remove_tail
這兩者函式的差別與上面的 insert 一樣，只差在刪除的節點是在開頭或結尾，因此我也是額外設計了一份 inline 函式 q_remove 來簡化程式碼，參數node即是需要被刪除的節點，程式碼如下：
/*
* 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
q_delete_mid
該函式的難點在於如何定位 middle node，這部份我參考了你所不知道的 C 語言: linked list 和非連續記憶體與快慢指標。在得到 middle node 後便可使用 linux kernel API 提供的 list_entry 和 list_del 巨集來處理移除節點並釋放記憶體的部份。
相關程式碼如下：
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
q_swap需要將兩兩相鄰的節點進行互換，因此我使用了兩個指標L與R來處理兩兩互換的部份，程式碼如下：
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
q_reverse
該函式需要將整條串列進行反轉，我的想法是走訪整條串列並逐一把每個節點的prev與next指標值進行交換，走訪的部份則靠list_for_each_safe來實現：
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
在你所不知道的 C 語言: linked list 和非連續記憶體中，有提到如何合併兩條已排序的串列，因此我設計了merge_two_lists函式來完成兩兩合併的功能。
/* 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
而q_merge需要將多條串列進行合併，同樣在你所不知道的 C 語言: linked list 和非連續記憶體中也有提到關於合併效率的問題，若是每次都拿第一條串列來合併剩下的串列，會導致合併速度越來越慢，因此我選擇了開頭跟結尾兩兩合併的實現方式，程式碼如下：
/* 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，只差在我將其改變成頭尾兩兩合併的實現方式。
q_sort
q_sort的目的是要將 queue 裡的 elements 進行排序。由於queue是雙向環狀鏈結串列，因此我的作法是先將queue轉換成非環狀鏈結串列(把head->prev->next設為NULL)後，再使用先前學到的mergesort_list函數來實現非環狀串列的合併排序。
可以注意到的是，mergesort_list函數也需要尋找到 middle node，因此也會使用到快慢指標的方法，以下是相關程式碼：
/* 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;
}
