contributed by < Grace258
>
HenryChaing
可以再詳閱課程教材補充背景知識,指標觀念可以再補強。
其餘的 review 在底下有留言
在終端機執行 export LC_ALL=C
並執行上述命令,可得到英語的輸出訊息,原本中文訊息用語不精準。
請附上 commit 紀錄,以及 github repository 連結, 你的 github。
HenryChaing
q_new
建立一個的 struct list_head *
,如果沒有足夠空間配置的話,回傳 NULL
。
如果有成功配置空間,將其初始化成符合環狀雙向鏈結串列的 head
指標。
我們要請求配置
struct list_head
的記憶體空間,成功的話指標會指向剛才配置成功的空間。
HenryChaing
q_free
因為要刪除 current
所在的節點,所以使用定義在 list.h
的 list_for_each_safe
走訪所有的節點,讓 next_node
記住 current
要移動到的下一個位置,最後再刪除剩下的 head
指標。
head
指標並沒有被刪除,我們做的是釋放head
所指向的記憶體空間,參閱: 課程教材。
HenryChaing
q_insert_head
將要插入到 head
的字串 s
用 element_t
將其存取,因為 element_t
才是鏈結串列節點的資料型態,因為 s
和 new_element->value
都是指標,因此要用 strncpy
來複製,因為對指標使用 =
是指向的意思。
指標也是紀錄資料,但是紀錄的是記憶體位置,因此 依舊是賦予數值的作用 。
HenryChaing
改進你的漢語表達。
q_insert_tail
操作原理和 q_insert_head
相似,差別在於使用 list_add_tail
將節點插到最後面。
將節點插入串列尾端。
HenryChaing
q_remove_head
避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景。
建立一個指標 first
指向鏈結串列中的第一個節點,建立一個 element_t
來取得要移除的節點的字串,將字串內容複製到 sp
中,並且要注意字串的最後是 \0
因此長度是字母數量 +1
。
字串長度+1較恰當,電腦科學用語中字元才是單位量詞。
HenryChaing
q_remove_tail
操作原理和 q_remove_head
相似,差別在於指標一開始是指向鏈結串列的最後一個節點。
q_size
使用 list_for_each
走訪每一個節點,用 count
來計算走過得節點數量。
q_delete_mid
使用 list_for_each
和快慢指標走訪, fast
一次走兩個節點, slow
一此走一個節點,當 fast
走完整個 list
後,就代表 slow
已經走到中間的節點,此時將其刪除,刪除不同於移除,需要釋放記憶體空間。
q_delete_dup
要刪除所有重複的節點(包含當前的節點),因此會用到一個 bool
的 flag
last_check
可以用來檢查當前節點是否是要刪除的最後一個節點,因為是 delete
所以會用到 q_release_element
來釋放記憶體空間。
q_swap
相鄰的兩個節點互換其實就是以 2
為單位反轉節點,因此可以直接使用 q_reverseK
。
這裡的想法是走訪每一個節點,並將當前節點移至 list
的最前面。
先初始化一個指標 start
用來標示 group K
的第一個節點,在反轉之後將其接到 group K
的下一個節點的前面。
對 list
做 merge sort
,因為我寫的 merge sort
是上升排序,所以如果descend
為真,要對整個 list
做反轉。
用兩個迴圈走訪節點,當內圈迴圈走訪到的節點小於外圈迴圈所在的節點時,表示此時的 list
不是上升排序,因此要刪除外圈迴圈的當前節點。
撰寫出更精簡的程式碼。
q_descend
操作和 q_ascend
相似,差別在於刪除節點的時機是當內圈迴圈走訪到的節點大於外圈迴圈所在的節點時。
q_merge
將所有的 queue
接在一起,使用的資料型態是 queue_contex_t
用來表示多個 list
。
文字訊息避免用圖片來表示,否則不好搜尋和分類。
這個錯誤訊息表示在程式結束時仍有一些動態分配的記憶體(使用malloc分配的)沒有被釋放,導致這些記憶體被視為 reachable
,也就是說,程式結束時仍然可以訪問到這些記憶體。
詳閱 資訊科技詞彙翻譯。
==7733==
: 是 Valgrind
的process ID
at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
: 表示記憶體分配操作發生的位置
by 0x10DB6C: malloc_or_fail (report.c:215)
: 表示程式執行中的呼叫堆疊,以及記憶體操作是被 malloc_or_fail
這個 function
使用的,並且這個 function
位於 report.c
的第215
行。
cycle counter
來實現。(例如 x86
系列的 TSC register
或 ARM
架構中的systick 外設 )post-processing
: 在進行系統分析之前,可以對每個單獨的測量套用一些 post-preocessing
(包含 cropping) 或套用更高階的 preprocessing
(例如 centered product
)模仿高階 DPA
攻擊。 simulatioin
是基於實際執行時間的測量和統計分析,以及使用統計測試來驗證兩個不同資料型態輸入的執行式間是否有顯著差異,因此 simulatioin
是通過實驗來驗證程式碼的時間複雜度,而不是依賴理論推導。現有程式碼和論文描述哪裡不同?
GNU General Public License v2.0
GNU General Public License
可以縮寫成 GNU GPL
或 GPL
,這一行的意思是指其使用 GPL
的 2.0
版本,大多數軟體的許可證用意是剝奪使用者分享和修改的自由,相較之下, GPL
的用意是保證所有使用者分享和更改軟體的自由。
告知編譯器第二、三、四個傳遞的參數不可為 NULL
,可以幫助開發者避免由傳遞 NULL
指標引起的意外行為或崩潰,提高程式碼的可維護性和可靠性。
merge
根據註解:
可以得知 merge
沒有維護到 prev
指標
可以發現傳遞的參數有一個自定義的函式 list_cmp_func_t
,可以在 list_sort.h
中找到。
這裡定義了一個函式指標 list_cmp_func_t
,它會接收三個參數,它們的資料型態分別是 void*
和兩個 const struct list_head*
,最後會返回一個整數,而 __attribute__((nonnull(2,3)))
表示編譯器會檢查該函式指標的使用,確保第二個和第三個參數不為 NULL
。
根據 list_sort.c
的註解:
可以得知:
a > b
那麼回傳 > 0
a < b
那麼回傳 <= 0
(表示 a
應該在 b
之前或維持原本的排序)list_sort
是一個穩定排序,因此不需要考慮 a <= b
的情況所以當 cmp
回傳的值 <= 0
時,要將 a
放到已排序的鏈結串列的尾端,因為 a
要比 b
先被排序。
merge_final
根據註解:
可以得知 merge_final
會將鏈結串列恢復成雙向的。
這裡的註解提到當 merge
非常不平衡時,舉例來說,儘管輸入都是已排序的節點,但是迴圈可能還是會跑很多次,這時可以定期調用 cond_resched()
解決此問題。
此處使用的函式 unlikely()
可以在 /include/linux/compiler.h
中找到。
__builtin_expect() 是 gcc
內建函式,作用是將執行頻率高的分支標示為 likely
,執行頻率低的分枝則標示為 unlikely
,所以 merge_final()
中的 unlikely
是用來檢查是否已經對鏈結串列 b
中的節點進行多次迭代,如果是的話,則調用 cmp
函式來觸發回調。
使用 !!(x)
兩個 !
的原因是將表達是轉換成布林值的 0
或 1
。
list_sort