HackMD
2025q1 Homework1 (lab0)
開發環境
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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-12500H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
Stepping: 3
CPU(s) scaling MHz: 18%
CPU max MHz: 4500.0000
CPU min MHz: 400.0000
BogoMIPS: 6220.80
Caches (sum of all):
L1d: 448 KiB (12 instances)
L1i: 640 KiB (12 instances)
L2: 9 MiB (6 instances)
L3: 18 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
針對佇列操作的程式碼實作
q_new
函式目的：建立一個空的佇列，並且回傳指標
實作方式：為了避免 malloc 配置失敗，需要在 malloc 後檢查配置是否成功，因此需要在 malloc 後做檢查，以免發生 Undefined Behavior
如果配置成功，則將 prev 及 next 指向自己並回傳
struct list_head *q_new()
{
struct list_head *node =
(struct list_head *) malloc(sizeof(struct list_head));
if (!node)
return NULL;
node->next = node;
node->prev = node;
return node;
}
q_free
目的：釋放整個佇列所佔據的記憶體
實作：先建立一個 element 接著夠過這個 element 尋訪整個 queue 在逐一進行釋放。此外，為了避免當前節點釋放後找不到下一個節點得問題，需要在額外新增一個 node 在釋放當前節點之前儲存下一個節點的位置，我們可以透過 list_for_each_safe() 這個 macro 達成
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *cur = NULL, *node = NULL;
list_for_each_entry_safe (cur, node, head, list) {
free(cur->value);
free(cur);
}
free(head);
}
q_insert_head & q_insert_tail
q_remove_head & q_remove_tail
目的：將 queue 中第一個元素移除，並放置於暫存區
實作：使用 list_entry 這個 macro 來取得第一個元素，接著透過 list_def 將其從 queue 中移除，並置於暫存區 sp
首先是 q_remove_head，根據 queue.h 中的註解，sp 是一個暫存區，裡面放的是被 remove 的元素，bufsize 是這個暫存區的大小
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
element_t *node = list_entry(head->next, element_t, list);
list_del(&node->list);
if (sp) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return node;
}
以上程式碼在 queue 為 empty 的時候會進行 remove 會導致 Segmentation fault ，因此需要在額外檢查 list_head 是否為 empty
- if (!head)
+ if (!head || list_empty(head))
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_entry(head->prev, element_t, list);
list_del(&node->list);
if (sp) {
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return node;
}
q_delete_mid
q_delete_dup
q_swap
目的：將兩元素的順序交換
實作：可以透過 list.h 中的 list_del 與 list_add，來實作
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 = head->next;
while (node && node->next != head) {
list_del(node);
list_add(node, node->next);
node = node->next;
}
}
q_reverse
目的：反轉 queue 中元素的順序
實作：與 q_swap 類似，可以透過 list_for_each_safe 以及 list_move 等 function 來達成
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head) {
list_del(node);
list_move(node, head);
}
}
q_reverseK
目的：對於整個 queue 以 k 個為一組進行反轉
實作：先將要反轉的部分從 queue 中切離，接著使用 q_reverse 進行反轉，再組合回去
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if(!head || list_empty(head))
return;
struct list_head *node = NULL, *safe = NULL, *start = head;
int count = 0;
list_for_each_safe(node, safe, head){
if (count < k - 1 ){
count++;
continue;
}
LIST_HEAD(tmp);
list_cut_position(&tmp, start, node);
q_reverse(&tmp);
list_splice(&tmp, start);
start = safe->prev;
count = 0;
}
}
q_ascend & q_descend
目的：對於每個節點，如果該節點右側有比當前節點還大 / 小的值，及刪除當前節點
實作：從 queue 的尾端往前找會比較簡單，如果條件成立就刪除，反之則繼續往前找
int q_ascend(struct list_head *head)
{
...
while (tail != head && tail->prev != head) {
struct list_head *node = tail->prev;
element_t *node_elem = list_entry(node, element_t, list);
if (strcmp(node_elem->value, tail_elem->value) > 0) {
...
}
int q_descend(struct list_head *head)
{
...
while (tail != head && tail->prev != head) {
struct list_head *node = tail->prev;
element_t *node_elem = list_entry(node, element_t, list);
if (strcmp(node_elem->value, tail_elem->value) < 0) {
...
}
q_sort
目的：針對 queue 中的元素進行排序
實作：將排序拆成三個 fucntion ，分別是 merge 、 merge_sort 以及 q_sort
q_sort 中，將整個 list 的環狀部分拆掉，接著呼叫 merge_sort 將 list 拆分成單一元素，然後透過 merge 將 list 組合回來，最後在重建 list 的環狀結構
merge_sort 實作過程中發生 Segmentation fault ，原始版本如下
struct list_head *merge_sort(struct list_head *head, bool descend)
{
if (!head || list_is_singular(head))
return head;
struct list_head *slow = head, *fast = head;
...
}
重新檢視實作的流程，當呼叫到 merge_sort 的時候，此時傳入的 head 並非 dummy node ，因此不該使用 list_is_singular 這個 function，應該判斷這個 head 後面是否還有節點存在，如果是單一節點則無須進行排序
另外，考量到傳入的 list 只有兩個節點的情況，如果 fast 的起始點設在 head，當進入 while 後，fast 會因為 fast = fast->next->next 存取到不存在的位址，造成 Segmentation fault
因此，程式碼應修成以下：
struct list_head *merge_sort(struct list_head *head, bool descend)
{
- if (!head || list_is_singular(head))
+ if (!head || !head->next)
return head;
- struct list_head *slow = head, *fast = head;
+ struct list_head *slow = head, *fast = head->next;
...
}
q_merge
目的：將所有 head 指向的 queue 合併成一個，接著進行排序
實作：建立一個新的 list_head ，接著將 head 指向的所有 queue 走過一遍，並切把節點搬到新的 list_head ，最後在進行排序
註解中有提到，這個函式有使用到 queue_contex_t 這個結構，可以先將 head->next 作為起始點，接著逐一將所有節點搬到這個 queue
