contributed by < bevmmf
>
1
singly linked list struct
在 list_reset
中,l.head 被設為 NULL => linked list 結構無dummy node
這份程式是一 singly linked list 的測試程式。主要用來測試 list_insert_before
。程式使用 macro 來進行斷言(assertion)和測試執行,並驗證 singly linked list 在不同插入情境下的行為。
巨集(macro)是由前處理器(preprocessor)處理的一種機制,它會在編譯之前將程式碼中的巨集名稱替換為你定義的內容。這種替換是純粹的文字替換,不涉及函式呼叫的開銷
my_assert
:如果條件 test
不成立,返回錯誤訊息 message
,否則繼續執行。
while(0)
條件永遠為假,因此loop只執行一次my_run_test
:用來執行測試函數,並追蹤測試次數。如果測試失敗,會輸出錯誤訊息。
items[N]
: 一個包含 N(1000) 個 list_item_t
結構的陣列,用於測試中插入的項目。l
: 一個 list_t
結構的實例,表示鏈結串列。tests_run
: 追蹤測試次數,初始為 0。list_reset
: 重置 items
陣列和鏈結串列 l
,確保每次測試從乾淨的狀態開始。
test_list
: 核心測試函數,測試 list_insert_before
在不同情況下的行為。
l
開頭插入 (每次插入都在 l
開頭(prepend),導致最後插入的元素(items[999]
)成為頭部)
list_insert_before(&l, l.head, &items[i])
1000 次:
l.head
為 NULL,假設 list_insert_before
將 items[0]
設為新頭。items[1]
在 l.head
(即 items[0]
)之前,更新頭為 items[1]
,items[1].next = items[0]
。l
結尾插入 (每次插入都在串列結尾(append))
list_insert_before(&l, NULL, &items[i])
1000 次:
position == NULL
表示插入到結尾。items[0]
成為頭。items[1]
在結尾,items[0].next = items[1]
。test_suite
: 使用 my_run_test
執行 test_list
,執行所有測試案例。若無錯誤,返回 NULL。
main
:
test_suite
,儲存結果。result
非空,輸出錯誤訊息;否則輸出成功訊息。首先必須知道函式 list_insert_before
每個parameter的定義
@l
: 指向欲操作list的pointer
@before
:
Pointer to the item before which the new item should be inserted
以上句子which指the item,因此before指向插入之new item之後的item位置
@item
: 要插入的new item
再來是函式運作邏輯 :
以 before
= C 為例:
for loop會遍歷 l
,直到找到 before
item
*p = item;
將before
前一個item的 next
指向 new item,完成插入
item->next = before;
讓 new item 指向 before
所指向,確保 l
完整性
再來是解題部分 :
AAAA : &l->head
,因為是從頭開始遍歷,所以為指向head
。又因p為指向指向item的pointer,因此除了取 l
的 head
之外還要取 &
。
BBBB : before
,根據此函式signature comment可知欲插入的new item在before
之前,因此遍歷的停止點應設在 p
指向 before
指向的item即跳出
CCCC : &(*p)->next
,此好品味地函式使用指向指標的指標,目的是能夠不用判斷是否head條件。此寫法的核心即是讓指標的指標持續指向 next
。
DDDD : item->next
,根據此函式定義,將new item下一個指向before即完成
2
延伸問題 1
解釋上方程式碼運作的原理,並嘗試補完程式碼,使其可獨立執行,應提供相關的測試程式碼
此題背景為 dyynamic memory allocator 的實現,特別是顯式配置器(explicit allocator)。allocator 必須滿足多個條件,包括處理任意請求序列、立即滿足需求、僅使用heap空間、確保地址對齊(例如 32 位系統為 8 位元組對齊,64 位系統為 16 位元組對齊),並且不得修改已配置的區塊。目標是在吞吐率(單位時間內完成的配置和釋放請求數量)和空間利用率( ,其中 是過去請求的有效荷載總和, 是目前heap大小)之間找到平衡。為了提升空間區域性(spatial locality),allocator利用分頁(paging)特性,確保每個分頁僅存放特定大小類別(size-class)的空間,避免自由區塊地址分散導致效能下降。
為什麼選擇 BST 架構實作allocator?
此題程式碼實現了一個基於二元搜尋樹(BST)的記憶體區塊管理系統
記憶體區塊 block_t
結構定義如下:
以下為未完成函式 :
以下為函式 remove_free_tree
:
目的是從 BST 中移除 target 節點,以下是函式signature
block_t **root
:指向樹根的指標的指標,允許函數修改樹的根。block_t *target
:要移除的目標節點。返回指向 target
的指標,若 target
不存在,則undefined behavior(程式碼未處理此情況)
處理有兩個子節點的情況
特別處理的原因是 :
在 BST 中,移除有兩個子節點的節點需要找到一個替換節點,以維持 BST 的性質(左子樹所有 節點小於根,右子樹所有節點大於root)
替換節點通常是中序前驅(左子樹的最大節點)或中序後繼(右子樹的最小節點) tree學習
(*pred_ptr)->r
, 因為它會走訪 target 節點的 左子樹,找到其中的最右節點。&(*pred_ptr)->r
, 因為它代表如何向右子樹移動,即應該指向 pred_ptr 的 右子節點,直到找到最右節點。find_predecessor_free_tree
獲取中序前驅,並與 pred_ptr
指向的節點比較assert
進行調試,確保找到的中序前驅正確處理有一個子節點或無子節點的情況
有一個子節點:
if-else
*node_ptr = child
)無子節點
清除被移除節點的指標
fin
find_free_tree
根據比較 target
與 root
subtree大小往下找,直到size相同、address也同
find_predecessor_free_tree
在 node
的left subtree 持續往右下找到底
測試程式為插入節點 3, 5, 7, 10, 15,形成如下結構
假設 target
為10
移除 size = 10 的節點(root 有兩個子節點)。remove_free_tree
會用中序前驅(7)替換 10,結果如下:
延伸問題 2
參閱 memory-allocators,針對你補完 (及後續改進) 的記憶體配置器,進行效能評比,並解讀其效能表現
3
延伸問題1
解釋上述程式碼運作原理
這題要求補全一個非遞迴的快速排序演算法實現,該實現基於鏈結串列,並使用堆疊模擬遞迴過程。
首先是所需的變數
pivot
: 基準點L
))
left
: 左邊子串列right
: 右邊子串列L
: 當前子串列的開頭L
從堆疊(begin[]
)裡取出,然後被設為 pivot。L
告訴我們「從哪開始排序」R
: 當前子串列的結尾begin[]
: stack(記錄子串列開頭)end[]
: stack(記錄子串列結尾)參數:node_t **list
是一個指向鏈結串列頭部指針的指針
變數 :
n
:串列的節點數量,通過 list_length(list) 計算。
value
:用來儲存基準點(pivot)的值。
i
:堆疊的索引,指的是當前正在處理的子串列位置。
max_level
:堆疊的最大容量,設為 2 * n。這個值確保堆疊有足夠空間處理最壞情況下的分割。
begin[]
和 end[]
:兩個陣列模擬堆疊,分別儲存每個待排序子串列的開頭和結尾節點。
result
:最終排序完成的串列頭部,初始為 NULL。
left
和 right
:用來暫存分割後的子串列,分別存放小於和不大於 pivot 的節點
stack初始化
主循環
i >= 0
時,表示stack中還有待處理的子串列。L
和 R
:從堆疊中取出當前子串列的開頭(begin[i]
)和結尾(end[i]
)。如果 L != R
,子串列有多於一個節點,需要進行分割。
left = right = NULL
,為下一次分割準備。i += 2
,跳到 right 子串列的位置,下一次循環會先處理它。每組子串列會佔用 begin[]
的三個位置
如果 L == R
,子串列只有一個節點(或為空),直接處理並加入結果。
L != NULL
,表示這個子串列只有一個節點,將其加入 result。L == NULL
,則跳過(空子串列)。i--
,返回堆疊中上一個待處理的子串列。將排序後的串列頭部 result
令 list
指向
list_construct
創建一個新的節點並將其插入到指定的鏈結串列中
list_free
釋放lsit中的所有節點記憶體
list_is_ordered
檢查list是否ascend
shuffle
將整數陣列的元素隨機打亂
i + rand() / (RAND_MAX / (n - i) + 1)
確保隨機選擇是均勻的main
初始化 list
準備100000筆測試數據放入 test_arr
將 test_arr
中測試數據放入插入 list
quick_sort(list)
排序
assert(list_is_ordered(list)
驗證升序結果
釋放 list
、 test_arr
中的所有節點。
list_tail
返回鏈結串列的尾部節點
list_length
計算鏈結串列的長度
rebuild_list_link
重建之前被斷開之雙向鏈結串列,重接回成circular雙向鏈結串列
int n = list_length(list)
:計算鏈結串列長度。int max_level = 2 * n
:設置堆疊最大層級為 2 * n,以應對最壞情況(完全不平衡的分割)。struct list_head *begin[max_level]
:堆疊數組,儲存待處理的子串列開頭。result, left, right
:分別用於儲存最終結果和分割後的左右子串列,初始化為 NULL。begin[0] = list->next
:將整個鏈結串列的開頭放入堆疊。list->prev->next = NULL
:斷開循環鏈結串列,轉為單向鏈結串列,便於後續操作。while (i >= 0)
,表示堆疊中仍有待處理的子串列。L = begin[i]
:當前子串列的開頭。R = list_tail(begin[i])
:當前子串列的結尾。
L != R
,執行分割過程。
pivot
L == R
,執行合併過程。
L->next = result; result = L
:將單節點加入 result(頭插法)。i--
:回退到堆疊中的上一個子串列。1
延伸問題1:
解釋上方程式碼運作原理,改進random_shuffle_array
也探討list_for_each_entry_safe
建構的迴圈中,若將list_move_tail
換為list_move
,為何會無法滿足 stable sorting
通常傳統的quick sort為unstable(相同元素的相對順序可能改變)。此題目的為用linux 核心風格linked list做出stable的quick sort
list struct
比較用的函式 cmpint
ARRAY_SIZE
macro
計算陣列 x 的元素個數
getnum
函式
生成一個偽隨機的 8 位元無符號整數(uint8_t),範圍在 0 到 255 之間
首先要先了解什麼是 線性同餘生成器(LCG)
線性同餘生成器(Linear Congruential Generator, LCG)是一種簡單的偽隨機數生成演算法
它的核心是使用一個遞迴公式來生成隨機數序列,公式如下:
再回來看函式即為
使用三個靜態變數 s1、s2、s3 作為隨機數種子,初始值分別為 2、1、1
每次調用時,根據線性同餘生成器(LCG)的變形更新種子:
s1 = (s1 * 171) % 30269
s2 = (s2 * 172) % 30307
s3 = (s3 * 170) % 30323
將更新後的 s1、s2、s3 進行xor(^)運算,返回結果作為隨機數。
get_unsigned16
生成一個 16 位元無符號整數(uint16_t)的偽隨機數,範圍在 0 到 65535 之間
random_shuffle_array
將給定陣列 operations(長度為 len)的元素順序隨機打亂
我認為此src有誤,應為swap,因此不應該為 operations[j] = i;
list_quicksort
主體檢查edge condition
初始化臨時串列 list_less
、list_greater
選取並移除pivot
pivot 通常從串列頭部獲取第一個節點
分割串列
list_move_tail
src def
因為 stable sorting 定義為兩相等值在排序後相對順序不會改變。若出現兩個與pivot相等的node使用list_move
,相對順序會被顛倒。
遞迴呼叫自己 排序子串列
將被移光的list開始合併所有子串列(先接pivot,再左子list,最後右子list)
2
clz32
以 0x0001F000
為例:
clz64
sqrti
返回值y : x的整數平方根,即
m
: mask,用於測試當前位元的貢獻
y
:累積的平方根結果,初始值為 0
shift
:用於計算初始遮罩 m 的位移量
total_bits - 1 - clz64(x)
:取得 x 最高有效位的索引
& ~1
:將數值的最右邊一位 (最低位) 清零,確保結果為偶數
m = 1ULL << shift
:初始化變數 m
為一個 4 的次方數
1ULL
:代表 1,並確保它是 uint64_t
類型 (unsigned long long)shift
:是一個偶數,確保 m
是 (平方數)1ULL << shift
:將 1 左移 shift
位,等於 逐位逼近計算平方根
m
為 ,從最高位開始測試。b = y + m
,嘗試將 m
加到 y
中。y >>= 1
,將 y 右移一位,準備更新平方根的估計值。x >= b
,說明 b*b
不超過 x
,則:
x -= b
,更新剩餘數值。y += m
,將 m
加到 y
中,表示這一位是有效的平方根部分。m >>= 2
,每次 m
右移 2
位,因為平方數每次變化是 。節錄自 liangchingyun
範例分析
最後 y = 6
,即 sqrt(36) = 6
。
3
LeetCode 的 Two Sum 問題要求在給定陣列 nums 和目標值 target 中,找到兩個元素的索引,使得它們的和等於 target。題目保證有且僅有一個解,且索引順序無關緊要。使用暴力法時間複雜度為 ,顯然效率不高,因此我們採用 hash table 來優化至 O(n)
ht
是包含多個 hlist_head 的陣列。每個 hlist_head.first 是對應 bucket 的開頭,指向該 bucket 的第一個 hlist_node
bits
: 存儲 hash table 的位元數,用來計算 bucket 的總數。例如,若 bits 為 4,則 bucket 數量為 hash_key
代表 hash table 中的一個鍵值對節點(bucket 內linked list中的一個節點)map_init
: 創建並初始化 hash table輸入是key(val)輸出是索引
find_key
: 查找特定 key 的節點在 hash table 中查找特定鍵 key,返回對應的 hash_key 結構指針,若未找到則返回 NULL
map_add
: 插入新 key 值對並維護 mapmap_add 將一個新的鍵值對 (key, data) 加入 hash table。
map_deinit
: 釋放所有記憶體
map_deinit 釋放 hash table 及其所有節點的記憶體。
map->ht
的每個 bucket(總數為 MAP_HASH_SIZE(map->bits)
)。twoSum
twoSum 解決 Two Sum 問題,找到陣列 nums 中和為 target 的兩個元素的索引,返回包含這兩個索引的陣列。
bail
釋放 map。