2024q1 Homework1 (lab0)

contributed by < gawei1206 >

Reviewed by HenryChaing

盡量提供 commit 連結，或是關鍵程式碼。
其餘的 review 在底下有留言

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  1
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4999.90

指定的佇列操作

q_new

allocate 的翻譯是「配置」，以區格 dispatch (分發/分配) 的翻譯。

一開始沒有注意到記憶體配置失敗的後續處理，後來有加上條件式去判斷，最後透過 list.h 中的函式 INIT_LIST_HEAD 來完成初始化

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() 來走訪每個 entry ，再釋放 entry 中 value 及 list 的空間，巨集q_release_element 已完成這部份實作，最後釋放 head 的空間

段落中的程式碼標注，使用 1 個 backtick，而非 3 個。

q_insert_head / q_insert_tail

函式 strdup() 會將字串複製到新的位置上，若成功會回傳位址，失敗則回傳 NULL ，最後透過 list_add() / list_add_tail() 將新的節點插入

發現在 trace-11-malloc 及 trace-12-malloc 中有出現ERROR，處理 strdup(s) 失敗的情況

- char *tem = strdup(s);
- node->value = tem;
+ if (!(node->value = strdup(s))) {
+     free(node);
+     return false;
+ }

如果可以請附上對應的 commit 紀錄，或是補上關鍵程式碼說明。
HenryChaing

q_reverse

走訪所有節點，並將他們插入到 head

使用 list_for_each_safe() 來走訪所有節點，並配合 list_del() 和 list_add() 將節點插入至 head ，但發現 list_move() 已經實作此功能，後來改正過來使程式碼更精簡

q_delete_mid

透過快慢指標可以快速的找出中間的節點

透過快慢指標找出中間節點後，刪除該節點並釋放使用的空間，但應該有可以寫的更好的地方

struct list_head *slow = head, *fast = head;

while (fast->next != head && fast->next->next != head) {
    fast = fast->next->next;
    slow = slow->next;
}

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

q_remove_head / q_remove_tail

"remove" is different from "delete"
The space used by the list element and the string should not be freed.
The only thing "remove" need to do is unlink it.
Return: the pointer to element, %NULL if queue is NULL or empty.

根據題目需求，只需要找到第一個或最後一個節點，取出字串並以 strncpy() 複製到 sp 中，最後使用 list_del() 將節點刪除

段落中的程式碼標注，使用 1 個 backtick，而非 3 個。

q_reverseK

This function should not allocate or free any list elements
(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head)

透過 list_cut_position 將佇列切成兩段，兩段的 head 分別是 tmp_head 及 start ，將第一段的佇列經過 q_reverse 後再以 list_splice_init 接回去，

struct list_head *start = head, tmp_head;

list_for_each_safe (node, safe, head) {
    cnt++;
    if (cnt == k) {
        cnt = 0;
        list_cut_position(&tmp_head, start, node);
        q_reverse(&tmp_head);
        list_splice_init(&tmp_head, start);
        start = safe->prev;
    }
}

q_swap

q_swap 為 q_reverseK 中 K = 2 的特例，直接呼叫 q_reverseK 即可

q_delete_dup

以 list_for_each_entry_safe 走訪每個節點，並比較當前節點與下個節點是否相等，若相等則移除，比較需要注意的地方是，當走訪到最後一個節點時並不需要再與下一個節點作比較，因為最後一個節點指向的是 head 如果對其取值會報錯

if (node->list.next != head && strcmp(node->value, safe->value) == 0)

q_ascend / q_descend

讀錯題目意思了，以 q_ascend 來說，題意為如果某一節點右邊存在小於他的節點，則應該刪除他自己，所以應該從最後一個節點往回做，就可以保證結果是非嚴格遞增的

commit caf198d

使用你 fork 得到的 GitHub repository 超連結，亦即該以 https://github.com/gawei1206 開頭。

但在這題中 remove 的意思是需要把空間釋放掉嗎？

已在 sysprog21/lab0-c 澄清

q_sort

參考 youjiaw ，先透過遞迴使串列中的節點變成單一節點，再透過自行定義的函式將已排序的子串列合併起來

commit a91a57f2

你如何確保目前的測試資料已涵蓋排序演算法的最差狀況？

q_merge

利用 chain 逐一走訪各個佇列，再透過自行定義的函式將第二個到最後一個佇列一一與第一個佇列合併。

commit 12f95f04

container_of

不懂就說不懂，沒有「不是很明白」這回事。

作業中很常使用此巨集但不懂他是如何運作的，所以查看 Linux 核心原始程式碼巨集: container_of，看到 offsetof 部份內容時，不懂 data 結構中的成員 c 他的偏移量為什是8，後來發現 The Lost Art of Structure Packing 中有寫到

In general, a struct instance will have the alignment of its widest scalar member.

還有在宣告結構成員時應該注意宣告的順序，避免不需要的 alignment，以減少結構的大小

搭配閱讀 x86-64 ABI 規格書，以得知 alignment 的作用。

offsetof 用來得知 struct 中某一 member 的位址相對於該 struct 起始位址的距離，而 container_of 是只要得知某一 member 的位址，就可以利用它進一步推算出 struct 的起始位址。

• Linux鏈結串列struct list_head 研究
• Linux的container_of 與 offsetof巨集

TODO:解決以下情況

+++ 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

研讀 Linux 核心原始程式碼的 lib/list_sort.c

你所不知道的 C 語言: linked list 和非連續記憶體

其他閱讀

Teach Yourself Programming in Ten Years

1. 專業技能發展需要時間：引用了多位學者和專業人士的觀點，強調成為一名專家通常需要約十年的時間或10000小時的練習，並且這個過程中沒有真正的捷徑。
2. 實踐經驗的重要性：強調了實際撰寫程式碼的經驗、與其他開發者的交流，這些都遠比單純的書本知識更為重要。

• Program. The best kind of learning is learning by doing.
• Talk with other programmers; read other programs. This is more important than any book or training course.

實作以及交流十分重要，不論在這篇文章中還是課堂的內容都一再強調。

盡量使用文章格式而非列點式描述。少用

$\ast$ 、

$-$ 列出想要描述的內容，用文章的方式撰寫有助於面試時完整回答問題。
HenryChaing

TOREAD:
每位程式開發者都該有的記憶體知識