contributed by < yunchieh0227 >
queue
list_head
NULL
malloc()
分配 list_head
記憶體INIT_LIST_HEAD()
初始化,確保它是空的q_free
負責 釋放 queue 所有的節點,確保沒有記憶體洩漏。head
為 NULL
,則 不做任何操作。element_t
value
head
list_for_each_entry_safe
而不是 list_for_each_entry
,因為刪除節點時,list_for_each_entry
會存取 next
,可能導致指標失效或記憶體區段錯誤 list_for_each_entry_safe
會先存好下一個節點,確保刪除當前節點後仍能安全走訪free(head);
放在最後,因為 head
代表佇列本身,必須確保所有節點都已經刪除後,才釋放它在 queue 的開頭正確插入新的節點
使用 list_add
而不是手動調整 next
,list_add
會確保 new_elem
的 prev
和 next
都正確設定
檢查點 | 錯誤處理方式 |
---|---|
head 或 s |
若失敗,返回 false |
malloc(sizeof(element_t)) |
若失敗,返回 false |
strdup |
若失敗,釋放 new_elem ,返回 false |
如果 strdup
失敗,但 new_elem
已經分配了記憶體,必須釋放 new_elem
,否則會發生記憶體洩漏。
記憶體管理與錯誤處理方法與 q_insert_head
邏輯相同,其餘差別如下:
比較項目 | q_insert_head |
q_insert_tail |
---|---|---|
插入位置 | 佇列開頭 | 佇列尾端 |
插入方式 | list_add |
list_add_tail |
q_remove_head
用來移除佇列的第一個節點,首先檢查 head
是否為 NULL
或佇列是否為空若是則直接返回 NULL
,接著使用 list_first_entry
取得佇列的第一個節點,並用 list_del
將該節點從佇列中移除,但不釋放記憶體
若 sp
不為 NULL
,則用 strncpy
將 value
複製到 sp
,確保長度不超過 bufsize - 1
,並手動加上 '\0' 以避免字串溢出。
最後,釋放 old_head->value
來避免記憶體洩漏,並釋放該節點記憶體,確保佇列的結構維持完整
取得佇列中的第一個 element_t
節點,透過 head->next
找到 element_t
結構體,member
指的是 element_t
裡的 list_head
將 entry
從佇列的鍊結串列中移除,且不會釋放 entry 的記憶體,這樣佇列結構不會被破壞,但 entry
還存在,必須手動釋放
q_remove_tail
的邏輯與 q_remove_head
相同,唯移除的節點位置不同:
q_remove_head
透過 list_first_entry
取得 第一個節點 head->next
q_remove_tail
透過 list_last_entry
取得 最後一個節點 head->prev
計算 queue 內的節點數量,但不修改 queue 的內容
NULL
,如果是,代表佇列未初始化,直接回傳 0list_for_each_entry
是一個 for
迴圈,會逐一走訪佇列的所有節點,每次 count++
list_first_entry
取得佇列第一個 element_t
節點list_next_entry
取得下一個 element_t
,直到回到 head
count
,表示佇列內的元素個數q_delete_mid
用來刪除佇列中間的節點,但不影響佇列內其他元素,並確保記憶體正確釋放
透過 q_size() 計算 queue 的長度,並用 size / 2 找到中間節點的位置
list_for_each_entry
逐一走訪佇列遍歷佇列的所有 element_t
節點,當 i
達到 mid_index
,代表找到中間節點
list_del
會讓佇列結構維持完整,但不釋放記憶體
透過 q_release_element
統一管理記憶體釋放,避免 double free
或 memory leak
刪除佇列內所有重複的元素,確保佇列中所有 所有重複的元素都被刪除value
都是唯一的
false
list_for_each_entry_safe
逐一走訪整個佇列,確保當前節點 cur
被刪除時,不影響迴圈的執行cur
和 next
的 value
是否相同:cur
是重複的節點,應該刪除list_del
把 cur
從佇列的鏈結串列中移除,再用 q_release_element
釋放該節點的記憶體,確保 cur->value
也被正確釋放true
,否則回傳 false
更改為刪除所有重複的元素,包括第一次出現的節點,確保佇列內不會保留任何重複的值
duped
變數來標記當前是否處於重複狀態cur
與 next
值相同時,刪除 cur
,並將 duped 設為 true。duped == true
代表曾經發現並刪除重複元素且 cur
不再與 next
相同時,也就是該重複元素已被刪除至最後一個時,確保第一個重複的元素也被移除duped == true
,代表佇列的尾端仍有重複元素,刪除最後一個重複元素交換佇列內的相鄰節點,且不改變節點內的 value
先將 entry (要移動的節點) 從佇列中刪除:
entry->prev->next = entry->next;
讓前一個節點跳過 entry
直接連到 entry->next
entry->next->prev = entry->prev;
讓後一個節點的 prev
直接連回 entry->prev
將 entry
加回佇列的新位置 head->next
:
entry->next = head->next;
讓 entry
的 next
指向 原來 next 的後一個,即head->next
entry->prev = head;
讓 entry
的 prev
指向 head
head->next->prev = entry;
讓 entry
的 next
,即原來 next->next
連回 entry
head->next = entry;
讓 head
的 next
變成 entry
轉佇列內所有的節點順序,且不改變節點的 value。
list_for_each_entry_safe
逐一走訪佇列cur
指向目前的節點,next
指向 cur->next
_safe
版本,確保當 cur
被移動後,不影響走訪將 cur
放到 head->next
,使每個遍歷的節點都會被依序插入到佇列開頭,達成反轉效果
list_for_each_entry_safe
的必要性不使用 list_for_each_entry
而要使用 _safe
版本
因為我們在迴圈內對 cur
進行 list_move
,這會改變 cur
的 next
和 prev
指標list_for_each_entry_safe
會在每次迴圈開始前,就先把 cur->next
儲存到 next
,確保即使 cur
被刪除或移動,仍然可以安全地訪問下一個節點
如果使用 list_for_each_entry
,當 cur
被移動到 head->next
時,原來的 cur->next
會發生變化,導致記憶體訪問邏輯錯誤
比較項目 | list_for_each_entry |
list_for_each_entry_safe |
---|---|---|
走訪方式 | 直接訪問下一個節點 | safe 儲存下一個節點,確保 pos 被刪除後仍能繼續 |
允許刪除節點? | ❌ 不允許刪除,否則 pos->next 失效 |
✅ 允許刪除,不影響走訪 |
允許移動節點? | ❌ list_move 會影響 pos->next |
✅ list_move 不影響迴圈 |
適用場景 | 只讀取、不刪除佇列 | 需要刪除或移動佇列節點 |
可能問題 | Use After Free 、無窮迴圈 、Segmentation Fault |
無此問題,走訪能正常運作 |
給定一個鏈結串列的 head
節點,請 每 k
個節點為一組 進行反轉,並返回修改後的鏈結串列
k
是一個正整數,且 k ≤ 鏈結串列的長度k
的倍數,則 最後剩餘的節點保持原樣,不進行反轉檢查基本條件
若 head 為 NULL、空鏈結串列 list_empty
,或 k < 2
,則不進行反轉
初始化變數
cur
:當前處理的 k 組的起點tail
:用來找到這組的最後一個節點next_group
:記錄下一組的開始prev_tail
:指向前一組的尾部,用於連接前後區塊檢查是否有足夠的 k 個節點
tail
移動 k-1
步,確保有足夠的節點可以反轉
反轉 k
個節點
使用 list_move
,將 cur->next
依序插入 prev_tail
之後,達成局部反轉
更新指標
前後版本的差異就在等號上,儘管對這兩種寫法輸入測資答案看起來都會是正確的,但其實,原本的寫法在兩個字串完全相等時 strcmp == 0
仍然會將第一個節點移動到第二個節點之後,破壞了排序的穩定性 stable sorting
,導致具有相同字串的元素在排序前後相對位置可能改變
修改後的寫法,當兩個節點的值相等時,不會更動順序,因此保持穩定排序的特性,修正了原先 Not stable sort
的錯誤訊息。
q_ascend
:從尾到頭q_descend
:從頭到尾q_ascend
:若前方存在更大的值則刪除當前節點。q_descend
:若後面存在更大的值則刪除當前節點。Dudect 透過「實驗測試 + 統計分析」來檢測程式是否符合 Constant-Time,而不是依賴傳統的靜態分析
定義測試輸入類別 (Classes Definition)
Dudect 採用 Fix-vs-Random 測試法:
Fixed Class
:輸入值固定不變Random Class
:每次測試時,輸入值隨機變化這種測試方式的優點:
✅ 可以觸發特殊的邊界條件,例如某些加法運算在 0000
的輸入會更快
若兩組輸入的執行時間分佈不同,則可能存在時間洩漏。
使用 CPU 時鐘來測量執行時間 (Cycle Counters)
現代 CPU 提供高精度的 時鐘週期計數器 (Cycle Counter):
✅ 這些計數器可以準確地測量程式的執行時間,避免 OS 排程造成的影響
減少環境變數影響 (Environmental Conditions)
在測試過程中,環境因素,例如: 作業系統調度、CPU 電源管理等,可能會影響測試結果,因此每次測試
Cropping (去除異常值)
由於 執行時間分佈通常會有向右偏移 (skewed distribution),某些測量值可能特別高,這可能是:
為了確保數據準確,可以去除超過某個閾值的測量值,避免極端值影響統計結果
Higher-Order Preprocessing (高階數據處理)
依據使用的統計方法,可以應用非線性轉換來增強測試能力
例如 Centered Product Method,它模擬 高階 DPA (Differential Power Analysis) 攻擊,用來捕捉更細微的變異
✅ 這些方法可以幫助檢測高階時間洩漏,使測試結果更準確
Dudect
工具中的 simulation
模式 透過實驗,而非理論分析來驗證程式的 時間複雜度 是否為常數時間 (Constant-Time, CT)
此方法的核心概念是:
Student’s t-Distribution
(t 分佈) 進行 Welch’s t-Test
來檢測執行時間是否受輸入影響。Student’s t-Distribution 是一種 連續機率分佈,適用於 小樣本統計分析,特別在母體變異數未知時。當樣本數較少時,t 分佈比標準常態分佈更能反映數據變異性
t 分佈的特性如下:
t 分佈的機率密度函數(Probability Density Function, PDF)定義如下:
其中:
t 分佈的累積分佈函數(Cumulative Distribution Function, CDF)可表示為:
其中:
這表示:
數學上:
這說明當自由度無限大時,t 分佈會變成標準常態分佈。
t 分佈主要應用於:
假設有 10 個樣本,樣本均值 ,樣本標準差 ,要求 95% 信賴區間,則:
查表得 ,代入:
計算後得到:
這表示 在 95% 的信心水準下,母體均值落在 (3.57, 6.43) 的範圍內。
在 simulation
模式中,Dudect
採用兩種統計方法來檢測時間變異性:
Welch’s t-Test (t 檢定):檢測兩組數據的均值是否有顯著差異
Kolmogorov-Smirnov (KS) Test (KS 檢定):檢測兩組數據的整體分佈是否不同
這兩種方法可以互補,t 檢定檢測均值差異,而 KS 檢定
關注整體分佈的不同,以確保測試結果的可靠性