Try   HackMD

2024q1 Homework1 (lab0)

contributed by < brucelee503jo3 >

留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心

開發環境

gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

架構：                   x86_64
  CPU 作業模式：         32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
供應商識別號：           GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12400
    CPU 家族：           6
    型號：               151
    每核心執行緒數：     2
    每通訊端核心數：     6
    Socket(s):           1
    製程：               5
    CPU max MHz:         4400.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4992.00

在終端機執行 export LC_ALL=C 再執行上方命令，會得到英語訊息。目前的中文訊息用語不精確。

安裝環境遇到的問題：一開始我在 windows 切割磁碟區的時候捨不得把 C 槽 SSD 分給 linux 。後來開始寫作業了之後才在想為什麼我要用 D 槽 HDD 給 linux 呢，不只開程式有點慢，連開機也覺得很慢，真的是非常的懊悔。

然後我安裝 Ubuntu 其實也不只安裝一次，至少安裝了三次有，不是忘記切 SWAP ，就是忘記關安全模式或者快速啟動，還有格式化錯誤等等，真的是要下載雙系統才有機會摸到這些東西。

目前剩下比較奇怪的地方式我預設的語言選擇了漢語，所以上面的系統資訊有中文的出現，跟其他同學的比起來看起來有那麼一點奇怪，如果後來需要的話我會再去想辦法把語言改回英語。

還有我 fork 完 lab0-c 到我的 local 端以後我依照教學影片建立在 tmp 目錄底下，正當我所有操作都摸過一輪，終於看到老師在材料上面講的，恭喜你終於看到這邊，可以開始著手撰寫 queue.c 的時候，我想說重開機一下因為電腦有點卡。 But 就在這個時候！！開機之後發現我的專案完全不見了，就在我既驚慌又難過得時候我才想到，難怪那個目錄要叫做 tmp ，不就跟我們變數取名 tmp 也就是英文 temporary 的意思嗎…所以我只好重新操作一輪以上的步驟，然後才不甘心的繼續寫作業。

  1. 不要自憐，真強者不會畏懼任何困難。
  2. 避免非必要的項目縮排 (即 * )，以清晰、明確，和通順的漢語書寫。
  3. 改進你的漢語表達，移除非必要的表情符號，不要裝可愛或裝可憐。

指定的佇列操作

q_new

struct list_head *head =
        (struct list_head *) test_malloc(sizeof(struct list_head));
if (head) {
    INIT_LIST_HEAD(head);
}

初使化的操作就比較單純，只要判斷創建佇列所配置的空間有沒有成功就好，若成功的話則使用 "init.h" 內建的巨集幫助初始化。

q_free

list_for_each_entry_safe (entry, safe, head, list) {
    list_del(&(entry->list));
    test_free(entry->value);
    test_free(entry);
}
test_free(head);

這個函式也是一樣只要使用內建的巨集遍歷 節點並把它一一釋放就好，並且要特別注意最後也要把佇列的開頭節點釋放，否則忘記了就不太好。
另外 "init.h" 提供了非常多種的 for_each 巨集，根據題目要求的釋放記憶體敘述，我選擇了較為安全的 list_for_each_entry_safe 作為使用。

不是名稱有 safe，就會「安全」，你要明確列出自己的考量因素。

q_insert_head

strncpy(ele->value, s, strlen(s) + 1);
list_add(&ele->list, head);

這題我在寫的時候遇到一點小問題

第一個問題是當時我把複製的長度填入 strlen(s) 忘了加一，導致評分的時候看到輸出比正確答案多了一些奇怪的字串，後來我就想到以前寫 C 的時候常常發生字串多印的問題，原來是因為 strlen 的返回長度不包含字串結束字元 '\0' 所以在這邊我必須要把它加上一才可以讓她複製到 '\0' 。

第二的問題是動態配置的時候不只要檢查 element * 有沒有配置成功，也要檢查 element 結構裡面的 char * 有沒有配置成功，當時我少檢查了一樣導致記憶體使用有問題，真是太不小心了。

q_insert_tail

list_add_tail(&ele->list, head);

這題最精彩的地方就在於，這份作業第一個開始決的 linux 的雙向環狀鏈結串列美妙的地方，原本一般作法應該要用迴圈跑到鏈結串列的尾端再進行操作，但由於環狀雙向的特性，我們只要常數時間就可以完成這個操作，真的是太美妙了 linux 的開發者們！

q_remove_head

struct list_head *node_tmp = head->next;
element_t *ele_tmp = container_of(node_tmp, element_t, list);
strncpy(sp, ele_tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';

list_del(node_tmp);
return ele_tmp;

這題我覺得老師設計得很有意思，基本上是在考英文解讀能力，老師在作業說明裡面有特別強調 remove 以及 delete 的差異性，所以我一開始就有朝著斷開鏈結並不釋放記憶體的方向去做，所以還算順利。

另外這題對我來說很美妙的地方是，這是我第一次覺得 container_of 這個巨集竟然如此的美如此的強大，以前我在寫作業系統課程的作業的時候為了要包裝 ucontext 這個資料結構以及一些我自己需要紀錄的資料，所以自己建造了一個結構體，但當時要控管這些所有行程的資料時操作變得很麻煩，當時我要是知道 container_of 這個巨集的話我一定會非常開心

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

q_remove_tail

struct list_head *node_tmp = head->prev;
element_t *ele_tmp = container_of(node_tmp, element_t, list);
strncpy(sp, ele_tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';

list_del(node_tmp);
return ele_tmp;

這題的話就跟上面基本一樣了，由於雙向環狀的特性讓我們的操作變得非常簡單，可以更加方便的透過內建的函式統一操作。

q_size

list_for_each (li, head)
    len++;
return len;

計算 list 的 size 的話非常的簡單，只要用一般的遍歷的方式去計算就好，所以老師在作業要求的範例裡面就用這題讓我們去熟悉 git 操作練練手，不然像我這種對 git 還不是特別熟練的人來說找不到地方試試看如何 commit/push/pull 。

q_delete_mid

struct list_head *forward = head->next, *backward = head->prev;
while (forward != backward && forward->next != backward) {
    forward = forward->next;
    backward = backward->prev;
}

這題我卡了蠻多時間的，當時我用最常見的快慢指標的方式來寫這個函式，很快就寫完了，但使用測試功能的時候一直跳出有可能是我的寫法太沒有效率的提示訊息，想了老半天沒頭緒我又去看了 leetcode 上面找到鏈結串列中間點的大神們的解法，但看來看去也跟我一樣。

明確指出你參考的 GitHub 帳號名稱。

後來我實在想太久了就去參考幾位同學 的作法，其中 hungyuhang 同學的作法讓我醍醐灌頂，才喵一眼我知道我又忘了雙向環狀的優點，可以一前一後的走訪 ；但其實一開始我還是看不太出來 到底哪裡有比較快，想了一陣子之後才發現 worst case 的話一前一後的找尋時間是 n/3 的時間，而快慢指標則需要花費 n/2 的時間，只能說雙向環狀的這個特性真的有很多好處。

工程人員說話要精準，不要說「看不太出來」

留意資訊科技詞彙翻譯

q_delete_dup

list_for_each_entry_safe (iter, safe, head, list) {
    if (&safe->list != head && strcmp(iter->value, safe->value) == 0) {
        dup = true;
        list_del(&iter->list);
        q_release_element(iter);
    } else if (dup) {
        list_del(&iter->list);
        q_release_element(iter);
        dup = false;
}

這題一樣可以用巨集 list_for_each_entry_safe 拿來作尋訪以及刪除，並搭配 dup 這個 flag 來標示當前的值是否已經重複出現過，若出現過的話就可以對她進行刪除，以及釋放位於 heap 的記憶體空間。

q_swap

while (prev != head && curr != head) {
    prev->prev->next = curr;
    curr->next->prev = prev;

    curr->prev = prev->prev;
    prev->prev = curr;

    prev->next = curr->next;
    curr->next = prev;

    prev = prev->next;
    curr = prev->next;
}

當我在構思這個函式的時候馬上就想起了之前在 leetcode 上寫過這題的經驗，差別在於由於現在是使用 Linux 核心風格的環狀雙向鏈結串列，所以由後往前分別需要維護八個指標所指向的記憶體位置，是一個非常好練習指標的機會。另外在想這題的指標要怎指的時候我有一瞬間想要畫圖，但當時想到老師曾在上課說過一個好的工程人員不需要靠繪圖也可以把自己的想法表達清楚且間單好懂，因此我就刻意的不靠繪圖輔助，單純只靠想像來將指標指向，還好結果測試的時候一次就成功，算是又進步了一點。

q_reverse

tmp = head->next;
head->next = head->prev;
head->prev = tmp;
list_for_each (node, head) {
    tmp = node->next;
    node->next = node->prev;
    node->prev = tmp;
}

反轉佇列的話就只要用順向以及反向兩個指標的方式把 next, prev 兩個指標交換就好，但值得一提的是 initial case 以及 final case 沒有辦法同時避免（也有可能只是我沒想到），所以寫起來的話就比較沒有那麼 good-taste (Linux Torvards 曾對撰寫不夠優雅的的程式碼說 not good taste )。

改進你的漢語表達。

q_reverseK

list_for_each_safe (itr, safe, head) {
    if (itr != k_last)
        list_move(itr, k_last);
    else {
        k_last = k_lastr;
        for (int i = 0; i < k; ++i) {
            k_last = k_last->next;
            if (head == k_last)
                return;
        }
        safe = k_lastr = k_lastr->next;
    }
}

題目敘述是每 K 個節點把她作順序反轉，這題一樣搭配巨集 list_for_each_safe 以及 list_move 就可以達成題目目的，稍微需要注意的是因為是環狀雙向鏈結串列，所以不只前後倒置，中間的節點也都需要把 prev 以及 next 作變更。

q_ascend

while (node->prev != head) {
    prev = container_of(node->prev, element_t, list);
    if (strcmp(prev->value, min) > 0) {
        list_del(node->prev);
        q_release_element(prev);
    } else {
        min = prev->value;
        count++;
        node = node->prev;
    }
}

這個函式的精隨就在於詳閱 interface 上面的敘述，使用界面說明上提到了如果一個節點的右側有比她更小的節點，則刪除該節點。這表示我們可以從環狀鏈結串列的反方向依照動態規劃演算法來幫我們決定刪除哪些節點，因此寫出來的函式非常淺顯易懂。

q_descend

while (node->prev != head) {
    prev = container_of(node->prev, element_t, list);
    if (strcmp(prev->value, max) < 0) {
        list_del(node->prev);
        q_release_element(prev);
    } else {
        max = prev->value;
        count++;
        node = node->prev;
    }
}

這題的作法就跟上一題的升序完全一樣，差別就在於，前一題是如果右側有比她小的節點就刪除當前節點；而這題則是如果右側有比她大的節點就刪除當前節點，所以寫起來非常類似，我們一樣也可以使用動態規劃的方式來完成這一題。

開發雜記

我遇到一個問題是在我想要使用 git commit -a 去產生 commit message 的時候， cppcheck 一直偵測存放在我 fork 的目錄底下 User/history 路徑裡有我之前 make 之後不符合格式的檔案，詢問過了兩三個同學以後他們也都沒有遇過這種狀況，他們的目錄夾 ?? 裡從來沒有這些複製的檔案，而且是只要我 make 之後不符合一次格式就會存一份備份到該目錄底下，也因為如此在這之後 cppcheck 檢查到這些檔案所以讓我一直無法 commit 成功，即便我真正在撰寫程式的檔案 queue.c 已經完全符合格式也沒有辦法讓我 commit ，因為她還是一直跑去檢查 User/history 底下那些檔案，後來我重新 fork 到其他的目錄底下也還是沒有解決這個問題，正當我查了一堆資料都沒有人分享這種狀況之際，我又重新 fork 一次才解決這個問題，如果老師或同學知道我的狀況是發生什麼事的話非常歡迎編輯這份 hackMD 提點我，謝謝。

以 rebase 更新到最新的 master 分支。

Last changed by 
 
李展瑋
0
251
Published on HackMD