HackMD
2025q1 Homework2 (quiz1+2)
contributed by < charliechiou >
第一週測驗題
測驗 1
延伸問題 1
解釋上方程式碼運作原理
"a pointer to a pointer" 使用 pointer 指向想要操作的指標，避免了類似一次一次把 current point 指向下一個節點的這種操作。先定義所用到的結構
#include <stddef.h>
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
其中 list_t 為整個鍊結串列，而 list_item 則為每個鍊結串列中的節點。示意圖如下
而該題則是實作 list_insert_before 的函式
void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
其中 l 指向整個鍊結串列，而目標為將 *item 插入 *before 之前。
首先定義一個 pointer to pointer 並使用迴圈將其指向目標位置 (before 前一個節點)
接著便將 p 所指向位置的指標設為指向欲插入的節點 item
最後再將 item 的 next 指向 before，並完成插入節點的目的。
接著使用測試程式來測試結果，首先先建立 N 個測試用的節點，並使用 list_rest 初始化
static list_t *list_reset(void)
{
for (size_t i = 0; i < N; i++) {
items[i].value = i;
items[i].next = NULL;
}
l.head = NULL;
return &l;
}
根據規格書中 7.17
size_t
which is the unsigned integer type of the result of the sizeof operator
size_t 為無符號整數型別，因此可用於 i 避免出現負數。接著便進行測試，分別測試將 item 插入在鍊結串列的頭,尾，並測試是否如預期的將其插入在對應的位置。
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
但這邊疑惑的是作業提供的程式碼有兩段所檢查的是相同的內容，差別僅在於第一項測試中有額外測試是否每個插入值皆正確，而第二段測試沒有。
/* Test inserting at the end */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
k = 0;
cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k++;
cur = cur->next;
}
/* Reset the list and insert elements in order (i.e. at the end) */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "list size should be N");
了解完測試的方式接著查看如何使用 Marco 來將整個測試包裝，首先定義 my_run_test 作為測試的入口，接著在 test_suite 中傳入要進行的測試。
#define my_run_test(test) \
do { \
char *message = test(); \
tests_run++; \
if (message) \
return message; \
} while (0)
static char *test_suite(void)
{
my_run_test(test_list);
return NULL;
}
以上述為例，test_list 傳入預先定義好的 my_run_test 後會被展開如下，透過這樣的方式便可以自由的更換我們所要測試的內容，而測試過程中若有錯誤則會回傳 message 並由result 儲存錯誤訊息，最後印出。
do { \
char *message = test_list(); \
tests_run++; \
if (message) \
return message; \
} while (0)
延伸問題 2
在現有的程式碼基礎上，撰寫合併排序操作
測驗 2
延伸問題 1
解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
首先先定義每個節點所儲存的資料，分別表示該節點所記憶的空閒大小、樹的左右兩個節點。
typedef struct block
{
size_t size;
struct block *l, *r;
} block_t;
接著使用二元樹的方式做搜尋，使用到的函式分別為 find_free_tree, remove_free_tree, insert_free_tree 。
find_free_tree 用於尋找 free tree 中可以使用的空間，當需要分配記憶體時便會用到該函式來確認是否有足夠的空間可以分配記憶體。
假設目前 free tree 結構如下，其中 size 表示剩餘的空間大小。
先將 curr = root 指向根節點及 best_fit 指向 NULL，並開始搜尋。
以分配 target = 350 為例，當 curr 所指向的大小大於 target 時，由於 curr 已經足夠分配大小了，因此更新 best_fit 指向 curr的位置，並持續朝節點的左邊更新 curr 試圖尋找更小且足夠分配的空間。
best_fit = curr;
curr = &((*curr)->l);
當目前節點小於 target 時，由於空間不夠分配給使用者因此不改動 best_fit 的位置，繼續更新 curr 至節點的右邊尋找。
當 curr 已經指向 NULL 時候便回傳最後所紀錄到的 best_fit。 若過程中直接找到 target 則直接會傳 curr。
remove_free_tree 用於將特定節點從 free tree 中移除，並調整好樹的結構使其維持結構。
首先先使用前述提到過的函式來找到目標的位置
block_t **node_ptr = find_free_tree(root, target);
此時會有三種可能性
- 沒有子節點
- 存在一個子節點
- 存在兩個子節點
沒有子節點以刪除 size = 300 的節點為例， node_ptr 指向欲刪除的節點
由於沒有子節點，因此直接將 node_ptr 改為指向 NULL 以移除節點，且不需要做調整。
存在一個子節點以刪除 size=600 的節點為例， node_ptr 指向欲刪除的節點。
先判斷節點在 node_ptr 的左邊或右邊，再直接將 node_ptr 指向該節點以完成取代。
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
存在兩個子節點以刪除 size=200 為例， node_ptr 指向欲刪除的節點。
使用左子樹的最大值 predecessor 來取代 node_ptr 位置，由於 predecessor 大於左子樹中所有值且小於右子樹所有值，因此取代後仍然滿足下列兩點二元樹的要求。
- 根節點大於左子樹所有節點
- 根節點小於右子樹
透過尋找左子樹最右邊的節點來確認 predecessor 的位置
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &((*pred_ptr)->r);
若 predecessor 即為 node_ptr 左邊節點，直接替換
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /* Replace target with its left child. */
(*node_ptr)->r = old_right; /* Attach the original right subtree. */
若 predecessor 在左子樹更深的位置，則先儲存 node_ptr 左右兩個節點位置
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
並迭代呼叫 remove_free_tree 再使用移除的 predecessor 來取代 node_ptr 的位置
/* The predecessor is deeper in the left subtree. */
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* Remove the predecessor from its original location. */
remove_free_tree(&old_left, *pred_ptr);
/* Replace the target node with the predecessor. */
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
insert_free_tree 用於在樹中插入新節點
以插入 size=250 為例，先將 curr 指向根節點
若目標小於 curr 則向左尋找可插入的位置，反之則向右尋找。
尋找到可插入的位置後便把該位置替換為 node，並將左右節點初始化為 0 。
*curr = node;
node->l = node->r = NULL;
接著便進行 allocator 的實作
首先先使用 init_allocator 初始化記憶體空間，使用 malloc 來分配所需要的大小並將空間存入 free tree。
由於會需要使用 block_t 的記憶體來紀錄 free tree 相關資訊，因此存入的空間大小需要預先扣除 sizeof(block_t) 才會是使用者真正可以分配的空間。
free_tree_root->size = total_size - sizeof(block_t);
接著使用 allocate 及 deallocate 兩個函式來分配及釋放記憶體空間。
allocate 首先先使用 find_free_tree 來找到可以用來分配的 block_t ，接著計算分配後的 block_t 記憶體位置並使用 insert_free_tree 增加至 free tree 中。
block_t *new_block = (block_t *)((char *)found + sizeof(block_t) + size);
新的記憶體位置為原始找到的地址加上 block_t 結構大小及分配的空間大小。
最後再將原先 tree 上的 node 移除
remove_free_tree(&free_tree_root, found);
deallocate 則直接先找回需要釋放的記憶體位置
block_t *block = (block_t *)ptr - 1;
接著把多出來的空間再重新紀錄於 free_tree 上。
insert_free_tree(&free_tree_root, block);
最後使用測試程式來測試分配結果
int main()
{
printf("Initializing memory allocator...\n");
init_allocator(1024);
print_tree(free_tree_root, 0);
printf("\nAllocating 200 bytes...\n");
void *ptr1 = allocate(200);
print_tree(free_tree_root, 0);
printf("\nAllocating 300 bytes...\n");
void *ptr2 = allocate(300);
print_tree(free_tree_root, 0);
printf("\nFreeing first block...\n");
deallocate(ptr1);
print_tree(free_tree_root, 0);
printf("\nFreeing second block...\n");
deallocate(ptr2);
print_tree(free_tree_root, 0);
return 0;
}
輸出結果如下
Initializing memory allocator...
[1000]
Allocating 200 bytes...
[776]
Allocating 300 bytes...
[452]
Freeing first block...
[452]
[200]
Freeing second block...
[452]
[300]
[200]
延伸問題 2
參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
測驗 3
延伸問題 1
解釋上述程式碼運作原理
〈Optimized QuickSort — C Implementation (Non-Recursive)〉中提出非遞迴 (non-recursive; iterative) 的快速排序法。以 swap 為主體，使用 L 與 R 紀錄需交換的數量，再用 begin[] 與 end[] 作為堆疊，用來紀錄所需比較的範圍。
題目中程式碼使用了 Linux 風格的 List API 來建立鍊結串列，並使用 value 來紀錄數值。
typedef struct __node
{
long value;
struct list_head list;
} node_t;
由於每次分割都會產生兩個子列表需要做排序，最壞情況下為每次分割其中一邊只有一個元素，會導致需要分割 n 次，產生
int max_level = 2 * n;
struct list_head *begin[max_level];
begin[0] = list->next;
list->prev->next = NULL;
接著便開始進行排序的動作，
排序的過程中首先先將 L 及 R 兩指標指向頭及尾。
若 L 及 R 兩者不同，則將 piviot 指向 L 所指的節點，並將 piviot 的數值存於 value。
並使用 p 指向 piviot 的下一個節點，並斷開 piviot。
使用 p 遍歷節點，將小於 value 的置於 left 中，大於 value 則置於 right 中。
if (n_value > value)
{
n->next = right;
right = n;
}
else
{
n->next = left;
left = n;
}
接著將 begin[] 指向對應的位置。
begin[i]= begin[0] = left;
begin[i + 1]= begin[1] = pivot;
begin[i + 2]= begin[2] = right;
left = right = NULL;
在下一輪中同樣將 L 指向 begin[i] 即為 begin[2] (從較大子序列開始),而 R 則指向 begin[2] 的尾端。
此時按照先前的步驟將 piviot 設置在 L 並將 p 指向 piviot 下一個節點
同樣遍歷節點，將小於 value 的置於 left 中，大於 value 則置於 right 中，並將 begin[] 指向對應的位置。
begin[i]= begin[2] = left;
begin[i + 1]= begin[3] = pivot;
begin[i + 2]= begin[4] = right;
left = right = NULL;
此時將 L 指向 begin[4], R 指向 begin[4] 的尾端，兩者皆指向 NULL，且 L 為 NULL 因此 i= i-1 = 3 。又 3 也同樣為單一一個節點，因此 i 會不斷扣一並在過程中逐步將元素加到 result 中，直到 i = 0 。
此時再依照先前的方法同樣為 2 及 1 兩個節點設置 begin[]。
最後再使用 result 收回
接著再使用 rebuild_list_link 設置回原本的雙向鍊結串列。
延伸問題 2
研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
第二週測驗題
測驗 1
延伸問題 1
解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
首先先確認所使用的結構體，分別儲存鍊結串列的 list_head 及 uint16 數值。
struct listitem {
uint16_t i;
struct list_head list;
};
接著查看排序的演算法
首先先宣告兩個空的 list_head 分別為 list_less 及 list_greater，將 piviot 設定在整個 list 的開頭並移出 list。
接著使用 list_for_each_entry_safe 遍歷每個節點，將小於 piviot 的放置在 list_less 中，反之則放入 list_greater 中。
接著用同樣的方式整理 list_less 及 list_greater，再將 piviot 加回 HEAD 中。
接著再把 list_greater 及 list_less 分別加到鍊結串列的尾端及前端。
探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
若有兩相同值的元素如下圖，分別為第一個 4 及第二個 4。
當使用 list_move 時候，由於我們是從前面遍歷至後面，因此第二個 4 會被置於第一個之前
此時重複呼叫 quick_sort 並不會將 list_great 中的 4 重新排序，因此會造成兩個的位置互換，非 stable sort。
改進 random_shuffle_array
延伸問題 2
將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋
測驗 2
延伸問題 1
解釋上述程式碼，並探討擴充為
(向上取整數) 實作，該如何調整並保持只用整數加減及位元操作
先確認 counting leading zero 的方法，
#define clz32(x) clz2(x, 0)
static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};
unsigned clz2(uint32_t x, int c)
{
if (!x && !c)
return 32;
uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));
if (c == 3)
return upper ? magic[upper] : 2 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}
8、9行首先先確認輸入，若輸入為 0 則表示 32 位元中全部皆是 0 ，因此回傳 32 。
接著將輸入的 x 分割成前半部及後半部
前半部直接將 x 右移完成。以 0b0001 0010 0101 0011 取前半部為例，由於這邊僅剩下 16 位數因此可以推得 c = 1，需要位移 8 位。透過將 16 >> c (即除以 c 次 2)來設定需要右移的數量，便可以取得 upper = 0b0001 0010。
後半部則使用 0xFFFF >> mask 來設定對應的遮罩，不同 c 所需要的遮罩分別如下
| c | mask |
|---|---|
| 0 | 0b 1111 1111 1111 1111 |
| 1 | 0b 0000 0000 1111 1111 |
| 2 | 0b 0000 0000 0000 1111 |
| 3 | 0b 0000 0000 0000 0011 |
因此設定的遮罩為 mask[] = {0, 8, 12, 14};。透過遮罩便可以把對應的，同樣以 0b0001 0010 0101 0011 取後半部為例，與 0b0000 0000 1111 1111 取 AND 後便為後半部0b0000 0000 0101 0011。
若 c = 3 則表示目前僅剩下兩位數，因此直接使用查表的方式來確認 clz。
| bits | Clz |
|---|---|
| 00 | 2 |
| 01 | 1 |
| 10 | 0 |
| 11 | 0 |
接著便迭代呼叫 clz2，若前半位大於 0 則僅須計算前半的 leading zero 即為整個 x 的 leading zero。若前半為皆為 0 則計算後半部的 leading zero 並加上前半位 0 的數量。
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
若要計算 64 位元，則確認前半位是否全為 0 ，若全為 0 則直接計算後半部的部份再加上 32 即可，若為非則直接計算前半部即可。
static inline int clz64(uint64_t x)
{
return (x >> 32) ? clz32((uint32_t)(x >> 32)) : clz32((uint32_t)x) + 32;
}
演算法使用逐步逼近的方式來計算平方根，首先先計算 m 的起始值，其中最困惑的便是 m 起始值的部份。
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
其中 total_bits - 1 - clz64(x) 表示最高位 1 的位置，接著再透過與 ~1 做 AND 運算來清除最低位以確保位移值是偶數，接著將 m 設置在最高位作為估計的起始。
在逐步檢視程式碼如何逼近平方根前，先參考從 √2 的存在談開平方根的快速運算理解其數學推導。
實際以
接著從高位開始計算
因此在計算的過程中會先計算高位的平方,再逐次加入
而二進制可以將一般化的平方和表示為
其中
因此我們可以利用最高位 1 來有個初始值，再藉由不斷加上新的低位元數值來逼近結果 。
回頭檢視程式碼,
我們從最高位的 1 開始計算並使用 b 來紀錄目前要測試的數值，藉由測試 y + m 是否會超過 x 來判斷能不能更逼近平方根。若 x >= b 則表示測試的 b 為可行的解，因此更新 x 及 y。但此處仍在理解為何需要將 y 及 m 位移。
延伸問題 2
參照計算機結構測驗題 C 及其注釋，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格。對照 sqrtf, rsqrt, reciprocal implementations in Arm assembly
延伸問題 3
參照從 √2 的存在談開平方根的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能
測驗 3
延伸問題 1
解釋上述程式碼運作原理，應提供測試程式碼
使用 Hash table 的方式解決紀錄缺少的程式碼，參考測驗題中的範例
nums =
[2, 11, 7, 15]target = 9
步驟如下:
nums[0] = 2，且 2 沒有對應的 HT[2]，因此建立 HT[9-2] = 0。nums[1] = 11且 11 沒有對應的 HT[11]，因此建立 HT[9-11] = 1。nums[2] = 7對應的 HT[7] = 0 存在表示 7 和 nums[0] 相加為 9 ，因此回傳[2, HT[7]] = [2, 0]。
查看測驗題中的實作，首先先定義結構體。透過 hlist_head 定義 hash table 的頭並使用 hlist_node 來串接每個 hash_key。
struct hlist_head
{
struct hlist_node *first;
};
struct hlist_node
{
struct hlist_node *next, **pprev;
};
typedef struct
{
int bits;
struct hlist_head *ht;
} map_t;
struct hash_key
{
int key;
void *data;
struct hlist_node node;
};
接著程式中先用 map_init 初始化 hash table ，其中 bits 儲存需要分配的大小，並使用 marco 將 bits 轉換為對應的數值。以 bits = 10 為例，傳入後轉換為 1024 因此將 hash table 上限為 1024 個值。
#define MAP_HASH_SIZE(bits) (1U << (bits))
傳換後再由 malloc 分配對應的空間至 ht 內
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
接著遍歷 nums 並使用 map_get 來確認 map 中是否有對應的 key ，若存在則回傳結果，若不存在則使用 map_add 加入至 hash table 中。
for (int i = 0; i < numsSize; i++)
{
int *p = map_get(map, target - nums[i]);
if (p)
{ /* found */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
先查看雜湊函數的部份
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
TBD
使用 map_get 取得對應的 key ，其中用到 find_key 來找到對應的 key 位置。
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
find_key 先使用 hash 來找到對應鍊結串列的頭
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
接著再遍歷鍊結串列來找到對應的位址
for (struct hlist_node *p = head->first; p; p = p->next)
{
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
當查找不到對應的 key 時，便需要使用 map_add 將目前的值插入到 hash table 中
首先先確認 key 是否在 hash table 中，若已存在則返回。
struct hash_key *kn = find_key(map, key);
if (kn)
return;
接著設定新的節點並取得要插入的鍊結串列的頭節點
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)];
再將設定好的新節點插入到鍊結串列的前端
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
延伸問題 2
進行《The Art of Computer Programming》(vol 3) 一書section 6.4 的 exercise 8，也就是證明 Theorem S
延伸問題 3
探討 Linux 核心中使用 hash table 的應用案例，至少二項，應當列出原始程式碼並分析，斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素
