HackMD
2025q1 Homework2 (quiz1+2)
contributed by < otischung >
Quiz 1
測驗 1-1
補完之程式碼如下所示
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
/**
* 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 stepsneeded to reach @before fromthe head of the list.
*
* Parameters:
* @l : Pointer to the list.
* @ before : Pointer to the item before which the new item should be inseted.
* - 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 = &l->head; *p != before; p = &(*p)->next) // AAAA, BBBB, CCCC
;
*p = item;
item->next = before; // DDDD
}
由於 l->head 與 list_item_t *before 都是 struct list_item *，因此我們只需要紀錄這些指標的位址，透過 dereference 即可操作該記憶體內容。
因此，我們的操作步驟如下：
- 從頭開始，鏈結串列是由
l->head所紀錄，其型態是list_item_t *，故其位址為&l->head，其型態是list_item_t **。 - 搜尋
*p是否等於目標before，若相同則下一步，若不同則將*p的下一個(*p)->next的位址紀錄起來&(*p)->next。 - 將
*p所指之處放入item，並將item->next記成before。
我們分析以下三種情況
- 插入在鏈結串列之頭
這種情況的話，p = &l->head，因此，執行插入的時候，*p = l->head = item，再把item->next紀錄成before，也就是之前的頭。 - 插入在鏈結串列之中間部份
- 插入在鏈結串列之尾
這種情況的話，before = NULL，所以最後*p = NULL，**p指向最後一個元素的位址，因此將最後一個元素的next，也就是*p，指向item，並將item的下一個指向NULL，而此時before = NULL，因此不違反原先的設定。
由此證明，以上程式碼具有一般性，不須做其他額外處理。
測驗 1-2
補完之程式碼如下所示
void remove_free_tree(block_t **root, block_t *target)
{
/* Locate the pointer to the target node in the tree. */
block_t **node_ptr = find_free_tree(root, target);
/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
/* 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) // EEEE
pred_ptr = &(*pred_ptr)->r; // FFFF
...
}
...
}
要找到最右邊的 node，就從左邊一路掃到右邊就可以了。
測驗 1-3
補完之程式碼如下所示
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
}
void quick_sort(struct list_head *head)
{
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;
while (i >= 0) {
struct list_head *L = begin[i], *R = list_tail(begin[i]);
if (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;
} else {
if (L) {
L->next = result;
result = L;
}
i--;
}
}
list->next = result;
rebuild_list_link(list);
}
首先，rebuild_list_link() 只在 quick_sort() 最後一行執行，而觀察 quick_sort() 只有處理 next，並未處理 prev，因此判定此 rebuild_list_link() 是為了補上 prev。
因此，我們定義 prev 為第一個元素，node 為第二個元素，透過雙向環狀 linked-list 依序處理，即可推斷 GGGG 為何。
HHHH 與 IIII 皆是利用 container_of macro 取得 node_t 的位址，再取得該 node 的值。
JJJJ 與 KKKK 皆為圖例所示，依序為 left, pivot, 與 right。
Quiz 2
測驗 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 = list_first_entry(head, struct listitem, list); // AAAA
list_del(&pivot->list); // BBBB
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater); // CCCC
}
list_quicksort(&list_less);
list_quicksort(&list_greater);
list_add(&pivot->list, head); // DDDD
list_splice(&list_less, head); // EEEE
list_splice_tail(&list_greater, head); // FFFF
}
其實對於 AAAA 來說，選擇 pivot 可以是任意的，不過在選項中，可以使用 container_of 得出「一個」 node 的 macro，只有 list_first_entry，那麼他就是唯一解。
與測驗 1-3 不同的是，這裡使用遞迴的方式實作，額外準備兩個 list 做遞迴。
取出 pivot 後，將 pivot 移出 list，之後將每個 node 與 pivot 作比較，分別移入兩個 lists。
至此，原本的 head 已經沒有東西了。
遞迴解完之後，先把 pivot 放回 head，再把左邊 list 插入頭段，最後把右側 list 插入尾段。
測驗 2-2
補完之程式碼如下所示
static const int mask[] = {0, 8, 12, 14}; // {0, 8, 12, GGGG}
static const int magic[] = {2, 1, 0, 0}; // {HHHH, 1, 0, IIII}
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) // JJJJ
return upper ? magic[upper] : 2 + magic[lower]; // KKKK
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1); // LLLL
}
#define clz32(x) clz2(x, 0)
這個實作是使用遞迴呼叫求解 counting leading zero，直到剩下 2 bits 為止。
每次都將目前的位元平分成 upper 與 lower
| c | upper/lower 位元數 |
|---|---|
| 0 | 16 |
| 1 | 8 |
| 2 | 4 |
| 3 | 2 |
- 當 upper 非 0，則繼續尋找 upper，忽略 lower。
- 當 upper 為 0，則繼續尋找 lower，將目前 upper 的位元數加進來。
當 c == 3 時，則 upper 與 lower 只剩下 0b00, 0b01, 0b10, 0b11 三種可能，而這些數字的開頭分別有 {2, 1, 0, 0} 個 0，因此，當 c == 3 時，
- 當 upper 非 0，則返回 upper 有幾個 0。
- 當 upper 為 0，則返回 lower 有幾個 0，加上 upper 的部分，有 2 個 0。
接下來，我們補完開平方根的程式碼
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
/* clz64(x) returns the count of leading zeros in x.
* (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
* Rounding that index down to an even number ensures our starting m is a
* power of 4.
*/
int shift = (total_bits - 1 - clz64(x)) & ~1; // MMMM
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1; // NNNN
if (x >= b) {
x -= b;
y += m;
}
m >>= 2; // PPPP
}
return y;
}
我們的目標是要找到一個最大的數字
我們知道對於所有正整數與 0 可以以二進位表示，即
對於所有
因此，對於所有
由於我們總是從 shift 必定是偶數，而又因為我們的起始項不超過 & ~1。
接下來，我們看一下 0xAA，因此 shift == 6，此時我們有
由於
接下來，我們搜尋
我們將等式做展開
