2024q1 Homework1 (lab0)

contributed by < bclegend >

Reviewed by brian049

• 要注意撰寫中文時要避免使用到英文鍵盤的逗號，且句子尾端加上句號才會形成完整的句子。

  感謝建議，已改進。

• 在解釋 q_free 和 q_remove_head / q_remove_tail 函式時可以藉由 - 或是 * 等等列點式來讓整段文字易讀。
• q_sort 函式缺少解釋。
• commit 1282572 和 commit 54dab51 分別是 Add q_size 以及 Modify q_size，可以在後者的 commit message 當中補述為什麼要那樣改程式碼。

  感謝建議，已依照建議更新 commit 2766e40 。

• q_reverseK 函式解釋當中有添加圖示使整體解釋更明瞭。

注意細節，上方的空白。

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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.

$ 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

遭遇到的問題

如何解讀這段程式碼

/**
 * container_of() - Calculate address of structure that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of structure containing ptr
 */
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#else
#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif

閱讀指定的教材了嗎？若是，列出過程中遇到的問題。

測試時間過久

在測試程式碼時在 TESTING trace trace-17-complexity 卡住，而無法結束測試。

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Testing insert_tail...(0/10)
meas:    0.00 M, not enough measurements (9120 still to go).

佇列操作的程式碼實作

command 是「命令」，而非「指令」(instruction)

編寫完程式後需要使用以下命令指令 ，使程式碼排版符合規範。

$ clang-format -i queue.c

測試範例

$ ./qtest -v 3 -f traces/trace-eg.cmd

q_new

宣告一個新的佇列。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

宣告一個新的佇列並將 list_head 大小的空間分配給新的佇列，並判斷該佇列是否成功分配。
將佇列結構中指向下一個以及前一個節點的指標 prev 和 next 宣告在該新佇列之中。

commit 784e4f9

問題

• 為什麼要加入判斷式 if(!q_empty) ？
  If the space cannot be allocated, a null pointer is returned. ( C99 規格書：7.20.3)
• 什麼情況可能導致空間無法配置？

參閱作業系統教科書關於 slab 的描述

q_free

釋放在佇列中的節點，並釋放佇列。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

首先需要確認佇列是否存在。
宣告指標 entry 用於指向目前的節點和指標 safe 用於指向下一節點。
利用 list_for_each_entry_safe 來經過佇列中的每個節點，運用 list_del 來刪除節點於佇列中的連結，並使用 free 來釋放該節點的記憶體。
在刪除完佇列中的節點後，釋放節點 head 的記憶體。

/* Free all storage used by queue */
void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        list_del(&entry->list);
-        free(entry);
+        q_release_element(entry);
    }
    free(head);
}

commit 37f921b

問題

• return; 是否合理?會有什麼表現？
  A return statement with an expression shall not appear in a function whose return type is void. A return statement without an expression shall only appear in a function whose return type is void. ( C99 規格書：6.8.6.4)
• 為什麼用 free(entry) 會讓佇列無法釋放節點？
  ​​​​cmd> new
  ​​​​l = []
  ​​​​cmd> ih hihi 20
  ​​​​l = [hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi hihi]
  ​​​​cmd> free
  ​​​​l = NULL
  ​​​​ERROR: There is no queue, but 20 blocks are still allocated
  

提供 GDB 實驗步驟和分析

q_insert_head / q_insert_tail

將新的節點插入佇列的頭部/尾端。

函式 q_insert_head 運用 list_add 將目標節點加入佇列頭部，而函式 q_insert_tail 運用 list_add_tail 將目標節點加入佇列尾端。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

首先需要確認佇列是否存在。
宣告一個新的 element 並將 element_t 大小的空間分配給新的 element ，並確認 element 是否配置成功。
將目標字元指標 s 指配到新的 element->value 中，並確認是否成功指配。
利用 list_add 或是 list_add_tail 將 element 加入到佇列之中，並回傳 true 回報 element 已經加入佇列之中。

在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","

commit b215d6e
commit 489b0e4

問題

• 什麼是 strdup?

查閱 Linux man page，避免看 cppreference.com 網站，因為後者是舊的副本。

$ man strdup

The strdup() function returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc(3), and can be freed with free(3).

q_remove_head / q_remove_tail

將佇列頭部/尾部的節點從佇列中移除。

函式 q_remove_head 運用 head 中的 next 成員指定目標節點而函式 q_remove_tail 運用 head 的 prev 成員指定目標節點 。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

首先需要確認佇列是否存在以及佇列是否為空的佇列。
宣告一個新的指標 node 將 head->next 或是 head->prev 指派到 node
宣告一個 element_t 的指標 element ，並將 node 的進入點指派到。element 中，
將該節點中的字串依照設定的長度 bufsize 複製到字元指標 sp 中，並在字元最後加入 \0 。
使用函式 list_del 刪除該節點在佇列中的連結。

commit 93c580d
commit 7b1e6fe

問題

• 什麼是 strncpy?

$ man strdup

The strndup() function is similar (with strdup) , but copies at most n bytes. If s is longer than n, only n bytes are copied, and a terminating null byte ('\0') is added.

參考 Risheng1128 提供的範例中以下程式碼作用為何？
測試：
1.以下實際作用為何？
2.若 strncpy 已經在末端加入 ('\0') 那 sp[bufsize - 1] = 0; 的目的為何？

if (sp) {
    strncpy(sp, element->value, bufsize - 1);
    sp[bufsize - 1] = 0;
}

有疑慮就該去做實驗並分析。

q_size

計算在佇列中有幾個節點 。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

首先需要確認佇列是否存在。
指派 0 到新宣告的整數 count 中。
使用函式 list_for_each 訪問每一個節點，每存取訪問 一個節點就將 count 加 1 ，計算出在佇列中的節點數量。

access 的翻譯是「存取」，而非「訪問」(visit)

commit 1282572

q_delete_mid

刪除在佇列中間的節點。
設計流程 : 從 head 由前往後和由後往前出發，當這兩個指向同一個位置時這個位置會在佇列的中間，因此我們只需要刪除這個節點，就能達成我們所期望的效果。
首先需要確認佇列是否存在。
並同時宣告兩個指標 move_head 以及 move_tail ，並分別指派 head 到指標之中。
在迴圈中同時移動 move_head 到 next 的位置以及移動 move_tail 到 prev 的位置，並在 move_head->next 與 move_tail->prev 指向同一個位置時或是 move_head->next 指向 move_tail 時離開迴圈。
將 move_head 移動到下一個節點，並刪除且釋放該節點。

commit cebcb6e

q_delete_dup

對照 Dictionary.com 對 implement 一詞的解釋:

• to fulfill; perform; carry out:
• to put into effect according to or by means of a definite plan or procedure.
• Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
• to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ 資訊科技詞彙翻譯

根據 wanghanchi 的筆記中提到的，q_delete_dup 是針對已經排序過後的佇列進行刪除有重複字串的節點，因此在實作實做 時我們需要比較下一個節點上的字串即進行刪除。
用函式 list_for_each_entry_safe(Iterate over list entries and allow deletes) 組成巢狀迴圈比對每個節點中的數值是否一致，若一致則刪除該節點。

commit de1e8bb

問題

• 在程式碼中若缺少條件 entry->list.next != head && 會造成錯誤 Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped) 的原因為何？

• 在 lab0-c/list.h 中 list_for_each_safe 和 list_for_each_entry_safe 的描述如下

  ​​​​list_for_each_safe - Iterate over list nodes and allow deletions
  ​​​​list_for_each_entry_safe - Iterate over list entries and allow deletes
  

  deletes 和 deletions 有什麼差別？

q_swap

將佇列中的節點從頭到尾進行兩兩交換。
依序經過佇列中的每個節點與下一個節點進行交換。
首先需要確認佇列是否存在。
宣告一個新的指標 node 並利用函式 list_for_each 讓該指標經過佇列中的每個節點。
在經過節點時將節點與節點所指向的下一節點進行交換。

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;
    list_for_each (node, head) {
+        if (node->next == head)
+            break;
        list_move(node, node->next);
    }
}

若缺少以下判斷式，原程式碼會將佇列頭部以及尾端進行交換，而這不是我們所希望的效果。

+        if (node->next == head)
+            break;

在 q_reverseK 完成的情況下，使用以下程式可以達成與 q_swap 一致的結果。

void q_swap(struct list_head *head)
{
    q_reverseK(head,2);
}    

q_reverse

將佇列中所有的節點反向。
在使用函式 list_for_each_safe 時，會將指標 safe 指向 node->next 並且由於函式 list_for_each_safe 支持在迭代中移除節點的操作，因此選用此函式對用在該實作中。
首先需要確認佇列是否存在。
接著宣告兩個指標 node 以及 safe 並在引用函式 list_for_each_safe 時將 node 指向 head->next 並將 safe 指向 node->next。
接著在每次的迭代中會先將指標 safe 指向 node->next 的位置，並對調 node 中指向前後節點的位置。
最後由於迭代結束後節點 head 沒有被改動到，因此另外將節點 head 指向前後節點的指標 所指向的位置進行對調。

commit bd64e32

q_reverseK

將在佇列中的節點以 k 為一組進行反轉，直到剩餘的佇列不足 k 個節點
首先需要確認佇列是否存在。
接下來宣告 nhead 並初始為 LIST_HEAD ，另外計算 times 為該佇列需要反轉段落有幾段。

再來宣告 temp1 以及 temp2 並初始為 LIST_HEAD ，作用分別為在每一次的迭代中將 head 所指向的佇列中首個節點放到 temp1 所指向的佇列中，接著將 temp1 中的節點插入到 temp2 所指向的佇列中的前方，重複直到執行 k 次。

並將 temp2 指向的佇列插入 head 指向的佇列尾端，並將 temp2 所指向的佇列插入 nhead 所指向的佇列 times 次後，將 head 所指向佇列 head 剩餘的節點插入 nhead 所指向的佇列的尾端。

以清晰、明確，且流暢的漢語書寫。

commit 2d33134

q_descend / q_ascend

將佇列中的元素沿著下降/上升方向排列，若有為反規則的元素存在，則刪除該節點。
參考 Leetcode 中的解法，但由於此實做使用的是雙向鏈結串列，而原題中使用的是線性單向鏈結串列，因此在函數的開頭需要先反轉鏈結串列。

以清晰、明確，且流暢的漢語書寫。

commit 0fcf63e
commit 6520d3f

q_merge

以清晰、明確，且流暢的漢語書寫。

此函數的作用是將所有連結在一起的環狀鏈結串列合併到第一個節點中，同時將其餘的鏈結頭重新初始化以確保它們是空的。

commit 22103fa

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

研讀 lib/list_sort.c 並完成 q_sort

list_sort.c 為 linux 核心中實作的 merge sort 檔案
在執行 list_sort 函式時，在開始排序前會先將環狀雙向鏈結串列轉換為 null-terminated 的單向鏈結串列，並最後使用函式 merge_final 在最後一次的 merge 後轉換回原本的環狀雙向鏈結串列。

__attribute__((nonnull(2,3,4)))

根據 A GNU Manual 在函式定義時，檢查在位置 (2,3,4) 輸入的參數為 non-null 的指標。

__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
				struct list_head *a, struct list_head *b) 

q_sort

基於 lib/list_sort.c 中的架構，將該架構修改符合 queue.c 的架構。

閱讀論文 〈 Dude, is my code constant time? 〉

利用 valgrind 分析記憶體使用情況