HackMD
2025q1 Homework1 (lab0)
contributed by < duckcone >
開發環境
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ uname -a
Linux oslab 6.8.0-54-generic #56-Ubuntu SMP PREEMPT_DYNAMIC Sat Feb 8 00:37:57 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 7800X3D 8-Core Processor
CPU family: 25
Model: 97
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 2
指定的佇列操作
q_new()
建立一個空佇列。利用 malloc() 配置一塊記憶體，並且利用函式 INIT_LIST_HEAD(); 對佇列進行初始化。
在測試中發現原先程式碼並未考慮 malloc 失敗的問題，因此加入了判斷 malloc 是否成功的程式碼。
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
+ if (!head)
+ return NULL;
INIT_LIST_HEAD(head);
return head;
q_free()
釋放佇列的空間。利用 list_for_each_entry_safe() 走訪每個包含 list_head 結構體的每個節點，並且利用 qrelease_element() 釋放節點。
q_insert_head()
新增一個節點在佇列的起始位置。透過呼叫 create_new_element() 函式來新增新的 element_t，最後透過 list_add() 函式將節點新增在佇列的開頭位置。
create_new_element() 的實作細節
- 在進行
element_t *new_element = malloc(sizeof(element_t))之後須判斷是否成功，若malloc()失敗則釋放其記憶體並傳NULL。 - 透過
strdup()將參數sduplicate 一份，並且將節點的value指向其位址。
如果 *s 是 NULL pointer 呢？
參考 2024 年系統軟體系列課程討論區 社團中的這篇貼文所提到的問題，發現自己的程式碼無法確認使用者在新增節點時所輸入的字串為何，因此在 q_insert_head() 以及 q_insert_tail() 中新增了判斷字串的程式碼，透過 if(!s || !*s) 來確保指標 s 所指向的位址非 NULL或字串非 NULL 。
bool q_insert_head(struct list_head *head, char *s)
{
- if (!head)
+ if (!head || !s || !*s)
return false;
element_t *new_element = create_new_element(s);
if (!new_element)
return false;
list_add(&new_element->list, head);
return true;
}
q_insert_tail()
與 q_insert_head() 的實作方式相同，透過呼叫 element_new() 函式來新增新的節點，並透過 list_add_tail() 將節點新增在佇列的尾端。
q_remove_head()
原先的想法是先取得佇列開頭的節點位址，並且調整 prev 以及 next 所指向的位址。但是在進行 $ make test 後，發現在進行 Test of insert_head and remove_head 測試時會有以下錯誤訊息：
ERROR: Attempted to free unallocated block. Address = 0x558a5a52e278
ERROR: Attempted to free unallocated or corrupted block. Address = 0x558a5a52e278
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
在閱讀 queue.h 檔案時不夠仔細，忽略了以下針對 q_remove_head() 的說明：
If sp is non-NULL and an element is removed, copy the removed string to
*sp(up to a maximum of bufsize-1 characters, plus a null terminator.)
因此針對此函式進行修正。
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
- if (!head)
+ if (!head || list_empty(head))
+ return NULL;
+
+ element_t *head_element = list_first_entry(head, element_t, list);
+ if (!head_element)
return NULL;
- element_t *head_element = container_of(head, element_t, list);
- head->next->prev = head->prev;
- head->prev->next = head->next;
+ if (!sp)
+ return head_element;
+ memset(sp, '\0', bufsize);
+ strncpy(sp, head_element->value, bufsize);
+ list_del(&head_element->list);
return head_element;
}
q_remove_tail()
與 q_remove_head() 的實作方式相同，唯一的差別在於利用 list_last_entry() 尋找佇列的最後一個節點。
q_size()
利用 list_for_each() 逐一走訪每個節點來計算佇列中的節點數量。
q_delete_dup()
實作上分為兩個步驟
- 尋找重複的節點
- 刪除重複的節點
尋找重複的節點
- 利用
list_for_each(current, next, head)來逐一走訪每個節點，並且同時擁有當前節點current以及下個節點next的位址。 - 只要
next != head就判斷current節點的字串是否與next節點的字串相同，若是相同就將next = next->next。 - 一旦
next == head或者current節點的字串與next節點的字串不同，便會跳出尋找重複節點的迴圈。這時從current到next->prev節點的字串內容都是相同的。
刪除重複的節點
- 設定
dup_head = current表示所有重複節點的起始節點。 - 設定
dup_head->prev->next = next; next->prev = dup_head->prev來將重複的節點斷開連接。 - 利用
temp節點作為dup_head的下一個節點。並在刪除dup_head所指向的節點之後將dup_head = temp。反覆執行此操作直到dup_head == next即可將所有重複的節點刪除。 list_for_each_safe()會在每一次迭代將current = next。
q_swap()
參考自 2025-02-25 問答簡記 HerryChaing 的實作方式。
初始化 current 為 head->next 。當 current 以及 current->next 都不等於 head 節點時，利用 list_move 將 current 與 current->next 的節點互換，並且繼續走訪佇列。
查看 list_move() 的實作可以發現該函式呼叫 list_add(node, head) ，在 list_add() 中之所以是將 node 加入至 head->next->prev 是因為在佇列的 head 本身只有提供尋找佇列開頭的功能，並且並無嵌入在 element_t 的結構中，因此需要透過 head->next 才是佇列中的第一個節點。
透過 list_move(node, head) 的特性，正好可以將，node 與 head 的位置互換。
q_reverse()
利用 list_for_each_safe() 逐一走訪每一個節點，並且將 current 節點的 next 與 prev 所指向的位址互換。由於 list_for_each_safe() 的中止條件為 node == head ，因此迴圈結束後需要再將 head 節點的 next 以及 prev 所指向的位址互換。
q_reverseK()
當以下四種情況時不須進行節點反轉
head為NULL時head所指向的佇列為空佇列時head所指向的佇列只有一個節點時- 反轉的節點數量
k為 0 時
首先利用 list_for_each_safe(current, safe, head) 逐一走訪每個節點，並且利用計數器 counter 來計算走訪的節點數量，當 counter >= k 時便進行反轉：
- 利用
list_move_tail(current->prev, safe)將current的前一個節點移動至safe節點之前 - 將
counter值減 1 - k 個元素只需要做 k - 1 次的交換即可完成反轉，因此完成反轉時
counter的值為 1 - 將
counter歸 0
q_delete_mid()
透過兩個指標 head_ptr 以及 tail_ptr 對 head 的 prev 以及 next 方向逐一走訪，當兩個指標相等(節點數量為奇數)，或是 head_ptr->next 等於 tail_ptr (節點數量為偶數) 時，即中間節點的位置。
