HackMD
2025q1 Homework1 (lab0)
contributed by <Boomer0211>
開發與實驗環境
$ 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: 43 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 24
On-line CPU(s) list: 0-23
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 9 3900X 12-Core Processor
CPU family: 23
Model: 113
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
Stepping: 0
Frequency boost: enabled
CPU(s) scaling MHz: 49%
CPU max MHz: 4672.0698
CPU min MHz: 2200.0000
BogoMIPS: 7586.04
針對佇列操作的程式碼實作
q_new
根據 malloc(3) 回傳值說明：
The malloc(), calloc(), realloc(), and reallocarray() functions return a pointer to the allocated memory, which is suitably aligned for any type that fits into the requested size or less.
On error, these functions return NULL and set errno.
當配置記憶體失敗時，malloc 會回傳 NULL 。故必須先檢查 head 非 NULL 才可呼叫 INIT_LIST_HEAD，否則可能造成 Null pointer dereference 。
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
q_free
使用 list.h 中的 list_for_each_entry_safe 走訪每一個節點並逐一刪除並釋放記憶體，最終釋放 head 指標所指向的記憶體空間。
因在 list_for_each_entry 更改佇列的內容將造成未定義行為，所以這裡必須使用 list_for_each_entry_safe。
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *e, *safe = NULL;
list_for_each_entry_safe(e, safe, head, list) {
q_release_element(e);
}
free(head);
}
q_insert_head 和 q_insert_tail
在 element_t 結構體中，因 value 為 char * 型態，僅配置 element_t 所需記憶體僅能夠配置指標所需的記憶體。為了能夠將字串複製給節點，必須配置一記憶體空間供 value 指標指向。
strdup(3) 會複製字串至一透過 malloc 新配置的記憶體空間並回傳指向該記憶體的指標，並且這空間在刪除節點時也必須另外透過 free 釋放。
bool q_insert_head(struct list_head *head, char *s)
{
element_t *e = (element_t *) malloc(sizeof(element_t));
if (!head || !e)
return false;
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add(&e->list, head);
return true;
}
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *p = (element_t *) malloc(sizeof(element_t));
if (!head || !p)
return false;
p->value = strdup(s);
if (!p->value) {
free(p);
return false;
}
list_add_tail(&p->list, head);
return true;
}
q_remove_head 和 q_remove_tail
先利用 list.h 提供的函式 list_first_entry 或 list_last_entry 取得欲移除元素，再使用 list_del 將元素移除。
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if ((!head) || list_empty(head))
return NULL;
element_t *e = list_first_entry(head, element_t, list);
list_del(&e->list);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if ((!head) || list_empty(head))
return NULL;
element_t *e = list_last_entry(head, element_t, list);
list_del(&e->list);
if (sp) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
q_size
利用 list_for_each 走訪各個節點，並記錄走訪的節點數量，即可得到佇列的元素個數。
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each(li, head)
len++;
return len;
}
q_delete_mid
使用快慢指標來取得佇列中點，並使用 list_del 自佇列移除與 q_release_element 釋放元素佔用的記憶體空間。
bool q_delete_mid(struct list_head *head)
{
if ((!head) || list_empty(head))
return false;
struct list_head *fast, *slow;
for (fast = head->next->next, slow = head->next;
fast != head && fast != head->prev;
fast = fast->next->next, slow = slow->next) {
}
element_t *e = list_entry(slow, element_t, list);
list_del(&e->list);
q_release_element(e);
return true;
}
q_delete_dup
從測資中觀察到在執行 q_delete_dup 前都會先執行 q_sort ，意味著若有重複的元素，則在佇列中會是連續的。
我的做法為在每走訪一個節點時先複製該字串到暫存的變數，並於後續的走訪判斷是否為相同的字串，若字串相同則刪除前一節點。
原先做法在迴圈內使用 strdup 來保存用來辨別重複的字串，已知 strdup 是由呼叫 malloc 來配置記憶體空間，每次呼叫 malloc 或 free 時，可能會觸發系統呼叫（如 sbrk 或 mmap），這些系統呼叫需要從使用者層級切換到核心層級，這是一個相對昂貴的操作。
後續改用固定緩衝區，在程式啟動時一次性分配，不需要頻繁的系統呼叫，因此避免了這些開銷。
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
+ char s[MAX_STR_LEN];
struct list_head *li = head->next;
while (li != head && li->next != head) {
element_t *e = list_entry(li, element_t, list);
const element_t *e_next = list_entry(li->next, element_t, list);
if (strcmp(e->value, e_next->value) == 0) {
- struct list_head *prev = li->prev;
- char *s = strdup(e->value);
+ strncpy(s, e->value, MAX_STR_LEN - 1);
+ s[MAX_STR_LEN - 1] = '\0';
while (strcmp(e->value, s) == 0) {
li = li->next;
+ list_del(&e->list);
q_release_element(e);
if (li == head)
break;
e = list_entry(li, element_t, list);
}
- free(s);
- prev->next = li;
- li->prev = prev;
} else
li = li->next;
}
q_swap
以兩個節點為單位，每走訪一節點，使用 list_move 將此節點移動到其下一節點的 next 指標指向的位置即完成交換。
後續迴圈的指標也只需往前一元素即代表移動到新的另一兩節點。
void q_swap(struct list_head *head)
{
if (!head)
return;
struct list_head *li = head->next;
while (li != head && li->next != head) {
list_move(li, li->next);
li = li->next;
}
}
q_reverse
首先創建一暫存變數 tmp ，使用 list_splice_init() 將 head 後續的所有元素移動到 tmp 並將 head 初始化，後續再將原先存於 tmp 元素逐一移動到 head->next ，即可達到佇列反轉。
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
LIST_HEAD(tmp);
list_splice_init(head, &tmp);
while (!list_empty(&tmp)) {
struct list_head *li = tmp.next;
list_move(li, head);
}
}
q_reverseK
先以佇列的元素個數除以 K 求得預計反轉的次數 n ，並自 head 將 K 個節點轉移到暫存佇列 tmp ，反轉 tmp 的節點後再加到原先佇列的尾部，重複 n 次。
最終再將剩餘不需反轉的節點移動到尾部即完成。
void q_reverseK(struct list_head *head, int k)
{
int n = q_size(head) / k, r = q_size(head) % k;
LIST_HEAD(tmp);
for (int i = 0; i < n; i++) {
struct list_head *li = head;
for (int j = 0; j < k; j++)
li = li->next;
list_cut_position(&tmp, head, li);
q_reverse(&tmp);
list_splice_tail_init(&tmp, head);
}
for (int i = 0; i < r; i++)
list_move_tail(head->next, head);
}
merge
此函式為 q_sort 的輔助函式，用來將兩個開頭為 left 及 right 的子串列排序並合併到另一個開頭為 head 的子串列，而這裡的 head 為原先兩個子串列拆分前的開頭。
void merge(struct list_head *head,
struct list_head *left,
struct list_head *right)
{
while (!list_empty(left) && !list_empty(right)) {
element_t *l = list_first_entry(left, element_t, list);
element_t *r = list_first_entry(right, element_t, list);
if (strcmp(l->value, r->value) <= 0)
list_move_tail(&l->list, head);
else
list_move_tail(&r->list, head);
}
if (list_empty(left))
list_splice_tail(right, head);
else
list_splice_tail(left, head);
}
merge_sort
此函式是 q_sort 的輔助函式，用來將一個串列以中點為界拆分成左右兩個子串列，並將原先的開頭 head 初始化作爲後來儲存排序後串列的開頭。
void merge_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *fast = head->next, *slow = head->next;
while (fast->next != head && fast->next->next != head) {
slow = slow->next;
fast = fast->next->next;
}
LIST_HEAD(left);
LIST_HEAD(right);
list_cut_position(&left, head, slow);
list_splice_tail_init(head, &right);
merge_sort(&left);
merge_sort(&right);
merge(head, &left, &right);
}
q_sort
實作採用遞迴 Merge Sort ，先以中點為界將佇列分成左右兩部分直到出現單一元素的子佇列後，再將佇列逐一排序後合併，最終即可完成排序。
void q_sort(struct list_head *head, bool descend)
{
merge_sort(head);
if (descend)
q_reverse(head);
}
q_ascend 和 q_descend
q_ascend 必須使佇列中的每個節點不大於其右邊的節點，否則必須刪除這個節點。需注意的是這函式刪除的對象為左邊節點，若是直接從左邊開始走訪的話，則必須每走訪一個節點就記錄起來並跟後續節點比較是否有發現嚴格小於它的值直到回到 head ，直觀的做法時間複雜度為 O(
然而若是先反轉佇列，則變成刪除的對象為右方，且只要往前走訪時確保右方節點的值 head 即完成刪除，最終再次反轉回到原始的順序即可完成題目要求。
因 strcmp(a, b) 比較方式是由 a 的值減去 b 的值，並依據結果的正負值判斷大小。原先的作法是以右邊節點值減去左邊節點值，想法上較不直觀，因為比較方式是由左自右，應由左邊節點減去右邊節點才較能看出變化的趨勢，進而得知函式結果是遞增或遞減。
/* Remove every node which has a node with a strictly less value anywhere to
* the right side of it */
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
q_reverse(head);
const char *min = NULL;
struct list_head *li, *tmp;
list_for_each_safe(li, tmp, head) {
element_t *e = list_entry(li, element_t, list);
- if (!min || strcmp(e->value, min) < 0)
+ if (!min || strcmp(min, e->value) >= 0)
min = e->value;
q_merge
根據 queue.h 對於此函式的說明，將第二個及之後的佇列合併到第一個佇列。
我的作法為先將第二及之後的佇列與第一個佇列依序合併，並且記錄佇列大小的變化。當所有佇列合併成後再呼叫 q_sort ，並根據 descend 的值排序成升序或降序。
int q_merge(struct list_head *head, bool descend)
{
queue_contex_t *fqc = list_first_entry(head, queue_contex_t, chain);
queue_contex_t *iqc;
list_for_each_entry(iqc, head, chain) {
if (iqc == fqc)
continue;
list_splice_init(iqc->q, fqc->q);
fqc->size += iqc->size;
iqc->size = 0;
}
q_sort(fqc->q, descend);
return fqc->size;
}
