HackMD
2025q1 Homework2 (quiz1+2)
contributed by < JeffBla >
Q1 間接指標、鏈結串列與記憶體配置
測驗 1
解釋程式碼運作的原理
/**
* Inserts a new item into the list before a specified item.
*
* This function traverses the list to locate the position immediately before
* the item pointed to by @before and inserts @item in that position.
* The time complexity is O(n), where n is the number of steps needed to
* reach @before from the head of the list.
*
* Parameters:
* @l : Pointer to the list.
* @before : Pointer to the item before which the new item should be inserted.
* - If @before is the head of the list, the new item is inserted
* at the front.
* - If @before is NULL, the new item is appended to the end of
* the list.
* - In all other cases, behavior is undefined if @before does not
* belong to @l.
* @item : The new list item to be inserted.
*/
static inline void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item){
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
;
*p = item;
DDDD = before;
}
AAAA = &l->head
BBBB = before
CCCC = &(*p)->next
DDDD = item->next
此函式是將節點 item 插入到 before 之前，在插入之前，需要知道指向 before 的節點，以修改節點順序，因此 for 的流程：
- 初始化： 鏈結串列開頭。
- 條件判斷： 當 pointer to pointer 所指向的
next或head指向before則代表所操控的指標為before的前一個節點的next，即我們希望插入的位置，當到達此情況，則停止迴圈。 - 移動至下一個：當離開迴圈條件不滿足，代表此 pointer to pointer 的數值並非所求，檢查下一個節點。
最後，因為找到目標指標所以將此指標指向欲新增的節點，並維護後續節點。其函式流程圖如下：
假設一開始的鏈結串列如下
初始化，將 pointer to pointer 指向 &list->head ，利用 pointer to pointer 控制指標以去除特例。
當找到目標，則另用 pointer to pointer 控制 next 或 head 指標，插入新節點。
最後將新節點指向 before 完整插入。
解釋測試程式碼運作原理
主要測試函式為 test_list ，主要測試三個項目
- 頭部插入
- 尾部插入
- 尾部插入（無數值檢查）
每項目由
- 重設鏈結串列與待插入數值
- 確認鏈結串列長度為零
- 插入
N項 - 確認插入後鏈結串列長度為
N - 檢查插入數值是否符合預期
在現有的程式碼基礎上，撰寫合併排序操作
實作 buttom-up mergesort
想法：使用 list_insert_before 進行將鏈結串列 2 依據遞增插入到 鏈結串列 1 的合併演算法。
list_item_t *merge(list_item_t *left, list_item_t *right) {
list_t result = {NULL};
list_item_t *next;
// Merge the two lists
while (left && right) {
if (left->value <= right->value) {
next = left->next;
list_insert_before(&result, NULL, left); // Insert at end
left = next;
} else {
next = right->next;
list_insert_before(&result, NULL, right); // Insert at end
right = next;
}
}
// Handle remaining elements
while (left != NULL) {
next = left->next;
list_insert_before(&result, NULL, left);
left = next;
}
while (right != NULL) {
next = right->next;
list_insert_before(&result, NULL, right);
right = next;
}
return result.head;
}
void merge_sort(list_t *l) {
if (!l || !l->head || !l->head->next)
return;
int len = 0;
for (list_item_t *curr = l->head; curr; curr = curr->next)
len++;
for (int size = 1; size < len; size *= 2) {
list_item_t dummy;
dummy.next = NULL;
list_item_t *tail = &dummy;
list_item_t *curr = l->head, *left, *right;
while (curr) {
left = curr;
right = split(left, size);
curr = split(right, size);
tail->next = merge(left, right);
while (tail->next) {
tail = tail->next;
}
}
l->head = dummy.next;
}
}
測驗 2
EEEE = (*pred_ptr)->r
FFFF = &(*pred_ptr)->r
解釋程式碼運作的原理
find_free_tree從root找到target並回傳指向target的指標的指標，也就是指標的指標指向l或r。find_predecessor_free_tree找到能夠替換的target的節點。
此函式刪除二元搜尋樹中的特定節點。首先找到指向 target 的指標的指標。判斷欲刪除節點之子嗣的存在與否，如果沒有則直接刪除，若存在其一且唯一，則將後代上提，替換目標節點。若左右兩邊都存在節點且將替換的節點為 target 的兒子，則直接替換，因為其替換的演算法為找尋左子樹中最大值，如果將替換節點為其後代，則代表欲替換節點左子樹不須處理且能夠直接承接 target 之右子樹。若左右兩邊都存在節點但將替換節點不為 target 的兒子，則紀錄 target 左右子樹，遞迴修剪欲替換的節點，待欲替換的節點整理完成，執行替換。
第一種：欲刪除節點沒有子嗣
第二種：存在左或右子代其一
第三種：存在左與右子代
紀錄欲移除節點的左右子樹，以利後續維護。
pred_ptr 找到將替換節點後，利用遞迴，將欲替換節點當作欲移除節點，確保替換後，二元搜索樹結構仍正確。因為替換節點需要做移除並插入的動作，所以利用遞迴將此種操作傳遞到子代，一直到末端。下面是進入迴圈，處理子代的操作：
當子代處理完成，回到 target 的處理。
嘗試補完程式碼
測試程式碼移除的三種情況。實作找到指向 target 的指標、初始化並插入建二元搜索樹。
block_t **find_free_tree(block_t **root, block_t *target) {
if (!*root) {
return root;
}
while ((*root)->size != target->size) {
if ((*root)->size < target->size) {
root = &(*root)->r;
} else {
root = &(*root)->l;
}
}
return root;
}
void insert_free_tree(block_t **root, size_t sz) {
if (!*root)
return;
while (*root) {
if ((*root)->size < sz) {
root = &(*root)->r;
} else {
root = &(*root)->l;
}
}
*root = malloc(sizeof(block_t));
(*root)->l = NULL;
(*root)->r = NULL;
(*root)->size = sz;
}
static void tree_reset(void) {
root.l = NULL;
root.r = NULL;
for (size_t i = 0; i < N; i++) {
temp[i] = i + 1;
}
size_t index = 0;
fill_balanced(0, N - 1, &index);
}
以 N 為 1000 節點測試，建造 complete BST ，並依序刪除
- First quarter: N / 4
- Middle: N / 2
- Third quarter: 3 * N / 4
- First item: 0
- Last item: N -
之後測試隨機刪除直到節點全被移除。
效能評比
測驗 3
解釋程式碼運作原理
GGGG = head->prev=prev
HHHH = list_entry(pivot,node_t,list)->value
IIII = list_entry(n,node_t,list)->value
JJJJ = pivot
KKKK = right
此程式碼和運用 Optimized QuickSort — C Implementation (Non-Recursive) 實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼原理相同。
利用 begein 與 end (在此實作利用 list_tail 取代) 代替分割所需要的遞迴空間及紀錄數值。採用和 list_sort.h 類似風格實作，首先，將環狀改成非環狀並在後續復原 prev 指標，復原環狀與雙向指標的特性。利用 L 代表串列最左， R 代表串列最右進行範圍內的運算，其中 pivot 為最左邊的節點，並將此節點獨立，利用 p 指標遍歷L 到 R 中的節點，將大於 pivot 內數值的節點歸到 right 其他歸到 left 。 最後將 right 、 pivot 、 left 開頭記錄到 begin ，其中 right 所記錄的位置最後面， 其次是 pivot 和 left ，由於 begin 採用堆疊的概念，在排序時，也是 right 完成後才是 pivot 與 left 。 當排序完成， L 與 R 指向相同節點，將此節點記錄到 result ，並使用 begin 執行前面一項鏈結串列排序。
Q2 鏈結串列、雜湊表，及位元操作
測驗 1
AAAA = list_first_entry
BBBB = list_del
CCCC = list_move_tail
DDDD = list_add
EEEE = list_splice
FFFF = list_splice_tail
解釋上方程式碼運作原理
改進 random_shuffle_array
利用 ASLR 實作隨機，在 unbiased_random 中乘法可有效地將隨機分佈擴展到目標範圍，透過採用高位而不是使用模數，避免偏差。
#include <stdlib.h>
#include <time.h>
#include <stdint.h>
static uint16_t get_unsigned16(void) {
// Get addresses of different functions that will be randomized by ASLR
void* func_ptr1 = (void*)&malloc;
void* func_ptr2 = (void*)&free;
// Create some stack variables to get their addresses
int stack_var1;
int stack_var2;
// Mix function and stack addresses together
uintptr_t addr_mix = (uintptr_t)func_ptr1 ^
(uintptr_t)func_ptr2 ^
(uintptr_t)&stack_var1 ^
(uintptr_t)&stack_var2;
// Mix in some dynamic memory address
void* heap_ptr = malloc(sizeof(int));
addr_mix ^= (uintptr_t)heap_ptr;
free(heap_ptr);
// Add time component for additional entropy
addr_mix ^= (uintptr_t)time(NULL);
// Extract 16 bits with better mixing
uint16_t random_value = (uint16_t)((addr_mix >> 4) ^ (addr_mix >> 8) ^ addr_mix);
return random_value;
}
static uint16_t unbiased_random(uint16_t max_exclusive) {
// For small ranges relative to UINT16_MAX, this approximation works well
uint32_t random = get_unsigned16();
uint32_t scaled = (random * (uint32_t)max_exclusive) >> 16;
return (uint16_t)scaled;
}
static inline void random_shuffle_array(uint16_t *operations, uint16_t len) {
for (uint16_t i = 0; i < len; i++) {
// Will generate a number between 0 and i inclusive
uint16_t j = unbiased_random(i + 1);
uint16_t temp = operations[i];
operations[i] = operations[j];
operations[j] = temp;
}
}
若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
list_for_each_entry_safe 是由前到後遍歷， list_move_tail 將每次遍歷的數值加入到特定鏈結串列的末端，形成類似佇列的排列，先插入的節點會在前面，而後插入的在後面，確保了 stable 的性質。若換成 list_move 將每次遍歷的數值加入到特定鏈結串列的前端，則形成如堆疊的排列，先插入的節點在後面，後插入的在前面。
測驗 2
GGGG = 14
HHHH = 2
IIII = 0
JJJJ = 3
KKKK = 2
LLLL = 1
MMMM = ~1
NNNN =
PPPP =
