HackMD
2025q1 Homework2 (quiz1+2)
contributed by < ibat10clw >
2025q1 第 1 週測驗題
測驗 1
測驗要求補齊程式碼，使其執行時不會遇到 assert 錯誤。
除了題目明確說明的 list_insert_before 需要實作外，還得實作 list_size 使程式可以完整運行。
#define list_for_each(node, l) \
for (node = (l)->head; node != NULL; node = node->next)
size_t list_size(list_t *l) {
size_t sz = 0;
list_item_t *cur;
list_for_each(cur, l)
sz++;
return sz;
}
在 list_size 的函式實作中，引入 linux 核心中的巨集 list_for_each，並將其改為適用於題目定義的結構體 list_t 以及 list_item_t 的版本。
list_insert_before 的實作採取了指標的指標的方式，可以消除要更新 head 的特例。
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;
(*p)->next = before;
}
這個迴圈的目的是為了找到要插入的位置，也就是找到參數 before 的節點在串列中的位置。
我們將指標 p 指向 struct list_item * 的指標，所以將 p 初始化為 &l->head，這時候對 p 解引用就會獲得開頭節點。
比照同樣的方式，當 *p 沒有指向目標 before 時，就將 p 向前移動，透過解引用 p 可以存取當前節點的 next 指標，透過 next 移動至下一個節點後，再把 p 指向新的 next。
以下為插入在開頭節點前，以及插入在結尾節點前的兩個特例
- list_insert_before(&l, l.head, &items[i]);
- 迴圈不會執行，因為初始化完成後
*p == before成立，item將成為新的開頭節點
- 迴圈不會執行，因為初始化完成後
- list_insert_before(&l, NULL, &items[i]);
- 此處串列為單向鍊結串列，最後一節點的
next指向NULL，因此迴圈結束後*p為串列最後一個節點，將item分配給*p，相當於在串列結尾加入節點
- 此處串列為單向鍊結串列，最後一節點的
測驗 1 - 合併排序
測驗 2
測驗 2 以二元搜索樹實作一記憶體分配器(memort allocator)，題目第一部份的需求為程式碼填空。
根據函式名稱帶有 remove，以及各處註解的提示，不難看出此函式為刪除二元搜索樹中的節點。
當要被刪除的節點的左子樹以及右子樹都存在時，可以透過下列兩個方式維持二元搜索樹的結構
- 找出左子樹中最大的節點，以其取代欲刪除之節點
- 找出右子樹中最小的節點，以其取代欲刪除之節點
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
根據註解我們可以得知此處想找出左子樹中最大的節點，當 pred_ptr 左子樹的樹根後，接著不斷向右移動直到抵達葉節點，這時便能找出目標。
此處依然透過指標的指標進行操作，解引用 pred_ptr 後便可存取樹狀結構中的節點，透過判斷此節點是否存在右子樹來決定是否能夠向右邊進行移動。
針對此案例有一處實作上的細節為對找到的節點 p 的後續處理
/* If the predecessor is the immediate left child. */
if (*pred_ptr == (*node_ptr)->l) {
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. */
} else {
/* 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;
}
在上方程式碼 if 的案例中，若 p 為 n 的左孩子，則將 p 取代 n 的時候，需要保留 r 的記憶體位址，並將其作為 p 的右子樹。
n
/ \
p r
/
...
關於 else 的案例，由於 p 節點並未與 n 相連，因此沒辦法像之前一樣單純交換指標來完成取代的動作。
在程式的實作中，使用遞迴呼叫的方式，將 nn 視為一顆樹，並且把 p 從 nn 這一棵樹裡面移除後，再將 p 擺放到原先 n 的位置。
n
/ \
nn r
\
p
/
...
剩下的案例則較為單純，若欲刪除節點無任何子樹，直接移除即可，
*node_ptr = NULL;
若右子樹與左子樹只存在其一，將整串子樹移動至欲刪除節點之處(node_ptr)即可。
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
- 由於此處使用指標的指標實作，因此不必區分要串接的左子樹或者右子樹，
node_ptr所指向的指標(屬於某個節點的l或者是r)就是要串接的位置
接著是 find_free_tree 的實作，從註解中可以得知
/* Locate the pointer to the target node in the tree. */
此函式的目的應當為找出 target 節點所在之處，也就是實作二元搜索樹的搜尋功能。
block_t **find_free_tree(block_t **root, block_t *target) {
block_t *cur = *root;
while (cur && cur != target) {
if (cur->size < target->size) {
cur = cur->r;
} else {
cur = cur->l;
}
}
return cur ? &cur : NULL;
}
從樹根開始依序比較當前節點的數值是否與 target 相等，若不相等則根據大小關係決定往左子樹或右子樹移動，直到找到目標節點，或者當前節點變為空指標的時候，即可回傳結果。
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
if (root == NULL || *root == NULL)
return NULL;
block_t *pred1 = find_predecessor_free_tree(&(*root)->l, node);
if (pred1 != NULL)
return pred1;
// peak next element in inorder travesal
if ((*root)->r != NULL && (*root)->r->size == node->size)
return *root;
block_t *pred2 = find_predecessor_free_tree(&(*root)->r, node);
if (pred2 != NULL)
return pred2;
return NULL;
}
尋找前驅節點的函式實作，由經典的遞迴式 inorder travesal 改寫而來，核心思路為偷看下一個節點是否與 node 相等，如果是的話，則當前所在的節點就是前驅節點。
偷看下一個節點的方式僅需要存取 (*root)->r 即可，因為這個節點本來就是 inorder 中下一個要拜訪的節點。
測驗 3
題目實作一個非遞迴版本的快速排序在 linux 核心風格的串列上。
首先查看 quicksort 函式中宣告以及初始化的資料
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
struct list_head *begin[max_level];
struct list_head *result = NULL, *left = NULL, *right = NULL;
begin[0] = list->next;
list->prev->next = NULL;
在非遞迴版本的實作中，使用 begin 這個堆疊紀錄當前要處理的串列的範圍，並且初始化為串列的第一個元素 list->next，並且破壞串列的環狀結構。
接下來有一個 while 迴圈，依序取出 begin 內紀錄的資料，開始對 struct list_head *L = begin[i], *R = list_tail(begin[i]); 這個範圍中的元素進行 partition。
接下來分為兩個狀況，若 L != R 代表這個範圍有不只一個元素需要處理
struct list_head *pivot = L;
value = list_entry(pivot, node_t, list)->value;/* HHHH */;
struct list_head *p = pivot->next;
pivot->next = NULL; /* break the list */
while (p) {
struct list_head *n = p;
p = p->next;
int n_value = list_entry(n, node_t, list)->value;/* IIII */;
if (n_value > value) {
n->next = right;
right = n;
} else {
n->next = left;
left = n;
}
}
begin[i] = left;
begin[i + 1] = pivot/* JJJJ */;
begin[i + 2] = right/* KKKK */;
left = right = NULL;
i += 2;
此處以第一個元素作為 pivot，接著透過指標 p 走過串列，若節點 n 的值大於 pivot，就將 n 掛到 right 上，反之掛到 left 上，此處 left 和 right 皆初始化為空串列，並且用 n->next 指向兩者其一，可以達到將串列 partition 成兩個子串列的效果。
當完成一輪的 partition 後，將已處理的串列開頭紀錄到堆疊中。
另外一個狀況則是將已排序的子串列掛到 result 上
if (L) {
L->next = result;
result = L;
}
i--;
當所有元素處理完成後重新建立串列的雙向鍊結，以及恢復環狀結構。
list->next = result;
rebuild_list_link(list);
static void rebuild_list_link(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *prev;
prev = head;
node = head->next;
while (node) {
node->prev = prev;
prev = node;
node = node->next;
}
prev->next = head;
head->prev = prev/* GGGG */;
}
2025q1 第 2 週測驗題
測驗 1
題目要求補齊快速排序的程式碼
static void list_quicksort(struct list_head *head)
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = /*AAAA*/list_first_entry(head, struct listitem, list);
/*BBBB*/list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
/*CCCC*/list_move_tail(&item->list, &list_greater);
}
list_quicksort(&list_less);
list_quicksort(&list_greater);
/*DDDD*/list_add(&pivot->list, head);
/*EEEE*/list_splice(&list_less, head);
/*FFFF*/list_splice_tail(&list_greater, head);
}
這邊實作的是遞迴版本，首先在 AAAA 的地方，依據變數名稱可得知需要取一個元素作為 pivot，此處取首個元素，因此填寫 list_first_entry(取最後一個元素也可以)。
接著將 pivot 節點從串列中移除，避免後續的迴圈會重複處理，此處填寫 list_del。
再來是比較的部份，這邊將比 pivot 小的元素移動至 list_less 上，因此反過來將比較大的元素移動到 list_greater 上，所以此處一樣是 list_move_tail。
當遞迴處理結束後，需要將串列合併在一起，並且以 pivot 為中點進行劃分。
首先將 pivot 加入 head，此時 head 應該會是空串列，使用 list_add 將 pivot 加入並且成為 head 的唯一一個元素。接著以此為分界將 list_less 以及 list_greater 分別加入至串列開頭以及結尾兩處，各使用 list_splice 及 list_splice_tail，便完成排序。
使用 list_move_tail 保持 stable sorting 的原因
list_move() - Move a list node to the beginning of the list
假設原先串列元素如下
3 => 1 => 1' => 2 => 5
當 list_for_each_entry_safe 在逐個確認串列節點時，會先看到 1 再看到 1'，如果使用 list_move 的話，那麼當 item 的值為 1' 時，這時候把 1' 加入到 list_less 的開頭，1' 與 1 的順序就被會改變。
測驗 2
題目透過位元運算的方式實作開根號計算。
首先是輔助用的函式 clz2，作用是計算 leading zero 的數量。
static const int mask[] = {0, 8, 12, /*GGGG*/14};
static const int magic[] = {/*HHHH*/2, 1, 0, /*IIII*/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 == /*JJJJ*/3)
return upper ? magic[upper] : /*KKKK*/2 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + /*LLLL*/1);
}
#define clz32(x) clz2(x, 0)
clz2 的實作透過遞迴的方式，每次將數字切為 upper 和 lower，若 upper 不為 0 則需要繼續檢查 upper 的部份，否則計算 lower 的 leading zero 並 upper 的位數作為答案(upper 為 0 代表他們全都是 leading zero 的一部分)。
將焦點先放在位元的切分上，觀察以 mask 陣列的三個數字 0, 8, 12 對 0xFFFF 做右移運算時產生的結果: 0xFFFF, 0xFF, 0xF，這三個結果分別可以取出某個數字的 0~15, 0~7, 0~3 bits，因此還缺少一個取出 0~1 bits 的 mask，所以此處要的填入的是 14，可將 0xFFFF 化為 0x3 以取出最低的兩個位元。
JJJJ 的部份，可以由遞迴中止的條件思考而來，當 c == 3 的時候代表已經比較到最低兩位元了，此時必可得出結果，不必再繼續遞迴操作。
再來思考 magic 的作用，從 return 的敘述可以得知 magic 能夠作為 upper 不為 0 時的答案，當 upper 剩下 2 bits 時候只可能為 10 或者 01，所以對應 magic[0b01] 必須是 1，magic[0b10] 為 0。
接著繼續考慮 upper 為 0 的狀況，此時保底能夠有 2 個 bits 的 0，所以 KKKK 為 2。
然後此處有所不同的是 lower 可能有 4 種情況, 0b00, 0b01, 0b10, 0b11，必須對應到的 magic 為 2, 1, 0, 0。
最後是遞迴呼叫的部份，從最一開始的 32 bits 整數切為 16 bits + 16 bits 開始，下一次要對 16 bits 作判斷時會希望將其切為 8 bits + 8 bits，此時要靠的就是 mask 中的數字，並且搭配 c 這個 index 來達成將數字逐漸縮小的效果，所以不論 upper 有沒有值，遞迴呼叫時都需要把 c 給往上加 1。
進入根號計算的函式前，先說明數學的核心思想。
假設要計算
透過這個方式可不斷地去逼近
實務上會將數字每兩位數分成一組，並且由右邊開始(左邊不夠就補一個 0)，原因可參見 the-square-root-algorithm 中的說明，直觀地說是平方的兩位數會對應於平方根的一位數(0 ~ 9 的數字拿去平方都會是兩位數)。
然後起始的 x 可以由估計最左邊的那個群組中的數字而來，一樣是找一個平方後最接近且不大於的數字，例如：
(12)(34)(56) => 3, (05)(67) => 2，依此類推。
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & /*MMMM*/~1;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= /*NNNN*/1;
if (x >= b) {
x -= b;
y += m;
}
m >>= /*PPPP*/2;
}
return y;
}
開根號函式的本體，m 的初始值必須要為 4 的冪，對應演算法中兩數字一組的分組方式。當 1ULL << shift, shift is even 時，就可以將 m 變成 4 的冪。所以 MMMM 應該要具備將 bit 0 歸零的效果，以 ~1LL 來獲得一個除了 bit 0 為 0，其餘 bits 皆為 1 的 mask。
while 迴圈在找的是前述的 if 去判斷 y + m 是不是會超過 x 來決定要不要把 m 加到最後的結果 y 。
NNNN 和 PPPP 分別要填寫的為 2 和 1，原因是將 m 逐次減少 4 位數，並且程式中直接將 m 加到了最後結果 y 上，但是每一輪測試僅會多產生 1 位數的結果，因此也在每個回合將 y 多算的部份透過右移給去除。
測驗 3
題目以 linux 核心風格的 hash table 解 Leetcode 的 two sum。
用到的結構體定義如下
struct hlist_node {
struct hlist_node *next, **pprev;
};
struct hlist_head {
struct hlist_node *first;
};
typedef struct {
int bits;
struct hlist_head *ht;
} map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
hlist_node, hlist_head 這兩個與串列相關的結構分別代表 bucket 的開頭以及屬於這個 bucket 上的串列節點。
hash table 則是由 map_t 這個結構體表示，根據後續的實作共有
hash_key 用來表示 map_t 中儲存的資料，在 map_t 中 key 必須是唯一的，在操作 map_t 時得先確認 key 是否已經存在，再決定後續行為。
初始化 map_t 的程式碼關鍵片段如下
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
透過 malloc 動態分配 map->ht 的大小，並且將所有 bucket 初始成 NULL，以利後續判斷 bucket 是否為空的狀態。
再來是加入資料的操作 map_add
void map_add(map_t *map, int key, void *data)
{
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, /*BBBB*/map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
/*CCCC*/first->pprev = &n->next;
h->first = n;
/*DDDD*/n->pprev = &h->first;
}
首先檢查 key 是否已經存在給定的 map 中，如果是的話則不進行後續處理。
接著分配一個 hash_key 的記憶體空間，並且使用傳入的參數初始化 kn。再來根據 key 以及 map_t 的大小決定要將資料存在哪一個 bucket，此處的 BBBB 填入 map->bits。
為了有效加入元素到串列上，這邊統一把新資料 kn 透過他的 node n 加到 bucket 的開頭，於是便有了判斷 bucket 是否為空的 if(first)，當 bucket 上已經有資料時，必須把舊的開頭節點的 pprev 指向新節點 n->next 指標，CCCC 處填寫 first->pprev。
處理完舊節點 first 後，就把 h->first 更新成新節點 n，之後再將 n->pprev 指向該 bucket 的開頭節點 h->first 以完成 map_t 上資料的新增。
資料搜尋函式以 key 作為參數尋找對應的 map 上是不是已經存在。
static struct hash_key *find_key(map_t *map, int key)
{
struct hlist_head *head = &(map->ht)[hash(key, /*AAAA*/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;
}
return NULL;
}
這裡一樣先找出 hash value，所以 AAAA 填寫 map->bits，確定要在哪個 bucket 搜尋目標後，就拜訪此條串列並依序比較節點上的 kn->key 與傳入的參數 key 是否相等，若有批配的目標就將記憶體地址回傳，否則回傳 NULL。
最後是釋放 map_t 的函式 de_init
{
...
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = /*EEEE*/ n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
...
}
這邊有兩個 for 迴圈，外層的迴圈負責檢索每個 bucket 開頭，內層迴圈則是跟著開頭節點依序存取串列上所有節點，先將節點從串列上移除，再釋放記憶體空間。
n 為要被從串列上移除的節點，為了將與 n 相鄰的節點都取出，此處 EEEE 填寫 n->pprev，接著 *pprev = next 可以讓 n 前方的節點跳過 n 自己，串到下一個位置，與之對應若 n 之後不為空，還存在節點的話就 next->pprev = pprev 把自己跳過，讓他指向更之前的位置。
不過考慮這個函式為 de_init 後續不會再需要使用到 hash table 上的資料，應該可以省去移除節點的操作，將回收 bucket 的行為視為一般釋放鍊結串列的形式即可，類似於以下的虛擬碼。
head = bucket[i]
while head:
next = head.next
free head
next = head
測試程式
int main () {
int *ret;
int sz = -1;
int input_size = 10000;
int nums[input_size];
const int min = -1e9;
const int max = 1e9;
const int range = max - min + 1;
srand(time(NULL));
for (int i = 0; i < 10000; ++i) {
nums[i] = min + (int)(((double)rand() / (RAND_MAX + 1.0)) * range);
}
int indices[2] = {0};
do {
indices[0] = rand() % input_size;
indices[1] = rand() % input_size;
} while (indices[0] == indices[1]);
int target = rand() % 2 ? nums[indices[0]] + nums[indices[1]] : rand();
ret = twoSum(nums, input_size, target, &sz);
if (sz == 2)
printf("%d %d\n", ret[0], ret[1]);
else
printf("not found\n");
return 0;
}
由於 two sum 的求解函式會一同分配 return 資料所需的記憶體空間，因此宣告指標接收回傳值。
測試資料的部份則隨機產生，測資大小固定為 leetcode 上此題目最大測資大小
target 的部份則隨機生成一個數，或者是隨機從 nums 內挑兩個數字出來相加。
