目的: 檢驗學員對間接指標、鏈結串列及記憶體配置的認知
1
以下程式碼運用〈你所不知道的 C 語言: linked list 和非連續記憶體〉提及的 "a pointer to a pointer" 技巧,撰寫鏈結串列的經典操作。
考慮以下程式碼:
其關鍵操作 list_insert_before
函式的語意如下:
對應的測試程式碼如下:
預期執行時期不會遇到 assert 錯誤。參考執行輸出:
list_insert_before
函式
補完程式碼,使其符合預期。
作答規範:
;
或 ,
字元延伸問題:
2
下圖展示常見的虛擬記憶體架構,其中有些資料結構的大小(如陣列)是在程式執行期間動態決定的,所以必須有個可以動態成長的區域,稱作 heap。對於每一個行程(process),作業系統核心會維護一個指標 brk 用來指向 heap 的頂部。
以下嘗試實作動態記憶體配置器,包含 malloc
, free
及 realloc
。這類配置器我們稱為顯式配置器(explicit allocator),程式必須明確呼叫 free
來釋放記憶體空間。顯式配置器必須符合以下條件:
malloc
在 32 位元系統上為 8 Byte 對齊,64 位元系統則為 16 Byte 對齊 你所不知道的 C 語言:記憶體管理、對齊及硬體特性配置器的實作必須在這些限制條件下,盡可能地在吞吐率 (throughput) 與空間利用率 (ttilization) 之間找到平衡。
單位時間內(通常為秒)可完成的配置 + 釋放請求數量。
其中:
要處理好吞吐率與空間利用率的平衡,配置器的實作必須考慮以下問題:
以往的實作中,每種類別大小(size-class)的空間都有一個 Free list,。隨著程式的執行,相同大小的空間地址可能會分散在整個記憶體的各個位置,長期下來會導致空間區域性 (spatial locality) 變差。
以下是一個 8 Bytes 的 Free list 在程式執行一段時間後的狀況:
此時,若配置(allocate)一個 8 Bytes 的鏈結串列,將會形成一個空間區域性很差的鏈結串列。
於是,我們利用分頁 (paging) 特性,確保每個分頁僅存放特定大小類別 (size-class) 的空間,藉此提升空間區域性。
下圖為一個 8 Bytes 的 mimalloc
Free list。
下方程式碼嘗試管理樹狀結構的記憶體區塊: (部分遮蔽)
請依據程式碼註解,補完程式碼以符合預期。
作答規範:
;
或 ,
字元延伸閱讀:
3
〈Optimized QuickSort — C Implementation (Non-Recursive)〉提出非遞迴 (non-recursive; iterative) 的快速排序法。此處提到的方法是以 swap 為主體,利用 L
與 R
去紀錄需交換的數量,再用 begin[]
與 end[]
作為堆疊,用來紀錄比較的範圍。
假定下方是起始的陣列內容。採取 head 作為 pivot,並且 L 會從左邊開始掃,紀錄有多少值小於 pivot,R 從右邊開始,紀錄有多少值大於 pivot。(R 一開始會定義為陣列的 length,以減法的方式紀錄)
這裡的 L 就會是 3,而 R 就會是 5
於是會把 array[4] 放到 array[0],array[3] 放到 array[4],再把 pivot 放入 array[3]
再來就是利用 begin 與 end 作為堆疊,去儲存尚未排列好的序列,由於 pivot 目前在 array[3] 的位置,所以就會有一組 begin 跟 end 為 0~2、一組為 4~5。之後會重複上述的行為,一次會以 5 為 pivot,另一次則會以 2 為 pivot,就可以得到排序好的陣列。
用變數 i
紀錄現在的 stack
在什麼位置,每次迴圈的開始都進行 pop 的操作:
依照相對於 pivot
大小整理節點的步驟沒有不同。而分類完 left
和 right
之後,本來應該各自遞迴計算的部分換成「放進堆疊中」,換言之,這份程式碼嘗試用堆疊模擬原本的遞迴呼叫。
考慮以下的鏈結串列結構體:
操作鏈結串列的圖解:
以下運用 Optimized QuickSort — C Implementation (Non-Recursive) 實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼。
其流程為
串列分割 i
之兩端,當 L R 尚未交會則進行內部排序串列分割 i+2
之內部排序(也就是先排右邊)操作鏈結串列的圖解:
接著我們使用 Linux 核心風格 List API 的簡化標頭檔 list.h 來改寫快速排序程式碼。首先是結構體:
快速排序實作的函式原型宣告:
以下是測試程式碼:
為了便於實作,我們準備以下輔助函式:
另一個輔助函式: (部分)
接著是 quick_sort
主體:
預期執行時期不會遇到 assert 錯誤。補完程式碼,使其符合預期。
作答規範:
GGGG
為有效 C 語言表示式,不含 ;
或 ,
字元HHHH
和 IIII
包含 list_entry
巨集,不含 ;
字元JJJJ
和 KKKK
為有效 C 語言表示式,不含 ;
或 ,
字元延伸問題: