Try   HackMD

2025q1 Homework2 (quiz1+2)

contributed by < TonyLinX >

2025q1 第 1 週測驗題

測驗 1

這段程式碼定義單向 linklist 的 node 以及串列整個 linklist 的 list_t :

#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_insert_before
這個函式的功能是在指定的 before 節點前插入新的 node，並且會遍歷 linklist 來找到 before 節點的位置。

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

先來討論另個想法，實際上如果只是要遍歷整個 linklist 不需要 **p，只需要 *p，因為只要創建一個指向 list_item_t 的指標並讓它指向 l->head，並一路透過 next 即可往後遍歷。

void list_traverse(list_t *l) {
    list_item_t *p = l->head;  
    while (p != NULL) {       
        printf("%d\n", p->value);  
        p = p->next;           
    }
}

那為什麼我們需要雙重指標 (**p)，因為我們要修改結構，如果說是單指標就會在 p = item 的地方出問題。因為 p 本身是局部變數，p = item 只是讓 p 去指向另個位址，但是整個 linklist 結構並不會改變，所以說我們需要 **p。

這裡其實可以想像成，如果傳送過去的指標是要被改變去指向另一個位址，那就必須要用雙重指標，因為你需要去改變這個指標的值，但是如果你只是要透過指標操作它所指向的內容，而不需要改變它本身的值（指向位址），那只需要單指標就夠了。

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;
}

假設鏈結串列是：head -> A -> B -> C -> NULL，而 before 是 B，你想在 B 前插入 item，目標是讓鏈結串列變成：head -> A -> item -> B -> C -> NULL。
list_insert_before 的流程會先透過 for loop 尋找到 before 前面的節點，所以先初始化 p 為 l->head 的地址，然後比對 (*p) 是否為 before，如果不是 before 就往下一個節點移動， p = &(*p)->next 中的 *p 代表的是指向某一個 node 的指標，所以我們可以用他的成員 next 進行移動。 當遇到 before 時，p為 A->next 的地址，所以 *p 就是 A->next，那我們就可以透過 *p = item 插入 item，最後再讓 item 的 next 指向 before 就可完成這個 linklist。

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;
}
詳細步驟
  • 初始化: p = l->head，所以 p 指向 A（地址 0x1000）。
  • 迴圈執行：
    • 第一次：*p != before（0x1000 != 0x2000），p = &((*p)->next)：
      • *p 是 A（0x1000），(*p)->next 是 A->next，也就是 B（0x2000）。
      • &((*p)->next) 是 A->next 的地址（假設是 0x1004，因為 next 是 A 結構中的成員）。
      • 所以 p 更新為 &A->next（0x1004）。
    • 第二次：*p == before（0x2000 == 0x2000），條件不成立，離開迴圈。
    • 結果：迴圈結束時，p 指向 A->next 的地址（0x1004）。
    • *p = item：
      • p 是 &A->next（0x1004），*p 是 A->next 的值（原本是 0x2000，指向 B）。
      • *p = item 把 A->next 修改成 item 的地址（0x4000）。
      • 現在：l->head -> A -> item，鏈結串列結構改變了！
    • item->next = before：
      • item->next 被設為 B（0x2000）。
      • 結果：l->head -> A -> item -> B -> C，插入成功！

撰寫合併排序操作 : Commit 2b418c3

首先，設計 merge sort 的 test case，這邊的設計方式透過 list_insert_before 創建一個 999 -> 998 -> ... -> 0 的 linklist，期望再透過 merge sort 之後可以變成 0 -> 1 -> ... -> 999。而 merge sort 的方式採用 top-down 的方式實現，也就是遞迴的方式。

測驗 2

這段 code 主要是在做，當某個 free block 被 malloc() 拿去用了，要將 BST 上的 free block 移除。

// 先從 BST 上找到 target node.
block_t **node_ptr = find_free_tree(root, target);

由於要維護 BST 的順序，在刪除上會有三種 case，每一種 case 要做的事情都不同，分成以以下三種：

  • 有左右子樹 if ((*node_ptr)->l && (*node_ptr)->r) =>
    • 找目標節點的左子樹中最大的值 
      ​​​​​​​​block_t **pred_ptr = &(*node_ptr)->l;
​​​​​​​​while (EEEE) pred_ptr = FFFF;

      所以說 EEEE 為 (*pred_ptr)->r ， FFFF 為 &(*pred_ptr)->r

    • 找目標節點的右子樹中最小的值
  • 只有左子樹或右子樹 else if ((*node_ptr)->l || (*node_ptr)->r) {} => 直接把左子樹或右子樹補上去
  • 沒有任何子樹 => 直接設定成 NULL

下面這段 code 主要的設計是考慮到 pred_ptr 的位置，如果說 pred_ptr 是目標節點左子樹的根，那可以直接替換上去，但如果是在非常深處的 leaf ，由於沒辦法得知 pred_ptr 的父節點，所以只能透過遞迴的方式把它找出來並且移除，然後再把它拿去替換。

/* 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. */
    assert(*node_ptr != (*node_ptr)->l);
    assert(*node_ptr != (*node_ptr)->r);
} 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;
    assert(*node_ptr != (*node_ptr)->l);
    assert(*node_ptr != (*node_ptr)->r);
}

測驗 3

這個題目主要是在做 QuickSort，常見的 QuickSort 是會透過 swap 以及 recursive 的方式實現排序。在這裡不會使用以往 recursive 的方法，而是改成 stack 來模擬原本的遞迴呼叫。

  • begin[i], end[i] 分別用來存放單一排序分割的起始點和終點，i 為分割編號
  • left 用來存放小於等於 pivot 的節點
  • right 用來存放大於 pivot 的節點
  • result 用來存放排序完的分割

具體來說，他會先找一個 pivot，並取比較剩下的 node_t 的 value，如果比 pivot 還小就接在left的尾部，如果比較大就分給 right 的尾部，所以當處理完所有的 node_t，你就會得到三組分割 left,pivot, right。接下來，這三組分別對應 i,i+1,i+2，各自將自己的第一個 node_t 加入到 begin[i], begin[i+1], begin[i+2]，並也將自己的最後一個 node_t 加入到 end[i], end[i+1], end[i+2]。 最後，就從最後面的部分開始排序。

這段 code 主要是當不只一個 node_t，必須根據 pivot 將所有的 node_t 分成 left 以及 right，

  • value 代表的是 pivot 的值，由於 pivot 是 list_head，所以要先用 list_entry 找到 node_t，才可以得到 value，所以 HHHH = list_entry(pivot,node_t,list)->value。
  • n_value代表的是 n 的值，所以 IIII = list_entry(n,node_t,list)->value
  • begin[i],begin[i + 1],begin[i + 2]，對應到的是三組分割 left,pivot,right，所以 JJJJ = pivot, KKKK = right。
if (L != R) {
    struct list_head *pivot = L;
    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 = /* IIII */;
        if (n_value > value) {
            n->next = right;
            right = n;
        } else {
            n->next = left;
            left = n;
        }
    }

    begin[i] = left;
    begin[i + 1] = /* JJJJ */;
    begin[i + 2] = /* KKKK */;
    left = right = NULL;
    i += 2;
}

這段 code 主要是維護環狀的 double-linklsit。

GGGG = head->prev=prev

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;
    /* GGGG */;
}

2025q2 第 2 週測驗題

測驗 1

這段 code 主要是在對 values 進行賦值以及打亂。j 代表是 index

#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))

static uint16_t values[256];

static inline uint8_t getnum(void)
{
    static uint16_t s1 = UINT16_C(2);
    static uint16_t s2 = UINT16_C(1);
    static uint16_t s3 = UINT16_C(1);

    s1 *= UINT16_C(171);
    s1 %= UINT16_C(30269);

    s2 *= UINT16_C(172);
    s2 %= UINT16_C(30307);

    s3 *= UINT16_C(170);
    s3 %= UINT16_C(30323);

    return s1 ^ s2 ^ s3;
}

static uint16_t get_unsigned16(void)
{
    uint16_t x = 0;
    size_t i;

    for (i = 0; i < sizeof(x); i++) {
        x <<= 8;
        x |= getnum();
    }

    return x;
}

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        /* WARNING biased shuffling */
        uint16_t j = get_unsigned16() % (i + 1);
        operations[i] = operations[j];
        operations[j] = i;
    }
}

這個部分是實作 quicksort，這裡的 code 跟第一周測驗三有點雷同，因為都會切成三塊，這裡的 less, pivot, greater 對應到那第一周測驗三的 left, pivot, right，整體流程為:

  • 先提取 pivot 的 listietm，並將 pivot 分割出來。
  • 根據 pivot 將小於的點接在 list_less 後面，而大於的點接在 list_greater 後面。
  • 各自將 list_less 以及 list_greater 進行遞迴排序。
  • 最後，再將這三塊接回 head。
  • 用第一個 listitem 做為pivot，所以 AAAA = list_first_entry 。
  • 將 pivot 分割出來，所以 BBBB = list_del。
  • 將大於的 pivot 的 listitem 接在 list_greater 後面，所以 CCCC = list_move_tail。
  • 由於 pivot 是一個點，所以一定是 list_add，所以 DDDD = list_add (但我覺得 list_add_tail 也可以)。
  • 由於 list_less 是比 pivot 還小的值，且可能為多個點，所以 EEEE = list_splice。
  • 由於 list_greater 是比 pivot 還大的值，且可能為多個點，所以 FFFF = list_splice_tail。
{
    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(head, struct listitem, list);
    BBBB(&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(&item->list, &list_greater);
    }

    list_quicksort(&list_less);
    list_quicksort(&list_greater);

    DDDD(&pivot->list, head);
    EEEE(&list_less, head);
    FFFF(&list_greater, head);
}

待完成

延伸問題

測驗 2

clz2() 這支函式用遞迴的方式計算 32 bit 無號整數 x 的前導零個數：它把輸入逐層一分為二，c = 0 代表先把 32 bit 切成高 16 bit (upper) 與低 16 bit (lower)，若 upper 全為 0，就可以直接把 16 累加到答案並改遞迴處理 lower；反之，若 upper 非 0，表示那 16 bit 內尚未遇到 1，就只遞迴 upper 繼續細分成 8/4/2 bit 區段。這個過程隨 c 增大而重複，區段長度依序是 16, 8, 4, 2 bit（所以 c 最大值為 3）；到最底層 (c == 3) 時，upper 只剩 2 bit，可能是 00, 01, 10, 11，對應要加的前導零個數可透過 magic[] 查表一次取得，同時若 upper 為 0 則還需把 magic[lower] 加進去。mask[] 是遮罩，是為了從 x 取出正確長度的 lower；magic[] 是當 lower 只剩下 2 bit 用來查表，由於只會是 00, 01, 10, 11，剛好可以對應為 {2, 1, 0, 0}。如果最一開始 x == 0 且 c == 0，代表 32 bit 全零，直接回傳 32。

  • 由於 lower 最後只需要 2 bit，所以 GGGG = 14。
  • 00, 01, 10, 11 對應 {2, 1, 0, 0}，所以HHHH = 2， IIII = 0。
  • 因為是 32 bit，區段長度依序是 16, 8, 4, 2 bit，所以 JJJJ = 3。
  • 當 upper 以及 lower 為 2 bit 的時候，在 upper == 0 ，才會觸發 KKKK + magic[lower];，所以 KKKK = 2。
  • 當 c != 3，不管 upper 是不是 0，c 都要加 1，繼續計算 clz，所以 LLLL = 1。
static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {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 == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}

這支 sqrti() 函式透過「二進位長除法」計算 64 bit 整數平方根。流程如下：先用 clz64(x) 找出最高的 1 所在位元索引 h = 63 - clz64(x)，再把 LSB 清 0（shift = h & ~1ULL），確保起始位階是偶數，因為開平方一次處理的是 2 bit ，所以起始位置一定要是偶數。
在迴圈中，每回合先計算出除數 b = y + m，接著把 y 右移 1（從 2 r 還原為 r）；若 x ≥ b 就說明這個 bit 應設 1 ，把 x -= b 並將 y += m；無論成敗，移到下一組 2 bit，繼續判斷。當 m 減到 0，y 即為 ⌊√x⌋。

  • 由於起始位置要是偶數，所以要將 LSB 清成 0 ，所以 MMMM = ~1
  • 由於這裡 y 代表的是 2r，要變成 r ，所以 NNNN = 1。
  • 每次做完移到下組 2 bit，所以 PPPP = 2。
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)) & MMMM;
    m = 1ULL << shift;

    while (m) {
        uint64_t b = y + m;
        y >>= NNNN;
        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= PPPP;
    }
    return y;
}

待完成

延伸問題

測驗 3

測驗 3 是要用 hash table 的方式完成 Two sum 這個題目。
這段 code 是在建立一個 hash table，假設 bits =

10，代表這個表會有
210 =
1024 個 buckets。每一個 bucket 對應一個 struct hlist_head，它的結構中包含一個 struct hlist_node *first，這是該 bucket 所屬 double linklist 的開頭指標，用來儲存碰撞時的多個 key-value 節點。我們透過 malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(bits)) 一次配置出整塊 bucket 陣列的空間。雖然 map->ht 是一個指標，但它實際上指向的是一段連續的記憶體空間，因此可以使用陣列方式操作（例如 map->ht[i]）。接下來透過迴圈逐一初始化每個 bucket 的 first 成員為 NULL，表示目前所有 buckets 都是空的、尚未儲存任何資料。

map_t *map_init(int bits)
{
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    if (map->ht) {
        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}

map_deinit() 是用來釋放整個雜湊表 map_t 所使用的記憶體資源，其核心流程如下：

  • 每個 bucket 是一個 struct hlist_head，其中的 first 成員指向該 bucket 的鏈結串列起點。
  • 使用 MAP_HASH_SIZE(bits) 計算出雜湊表大小（實際上是
    2bits     個 buckets）。
  • 若 bucket 為空（first == NULL），代表此 bucket 沒有資料，會被自動略過。
  • 若 bucket 非空，則遍歷整條鏈：
    • 使用 container_of() 從 hlist_node 取回對應的 struct hash_key。
    • 將節點從 hlist 中移除：這透過 next 與 pprev 指標操作來實現。
    • 若 n->pprev == NULL，代表此節點尚未被插入（unhashed），會直接跳過斷鏈處理。
    • 每個節點的 data 與節點本身都會被 free() 掉。
  • 迴圈結束後，釋放 map 本身的記憶體
void map_deinit(map_t *map)
{
    if (!map)
        return;

    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 = n->pprev;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

這段 code 主要是去搜尋 hash table 中有沒有該 key 值。

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

有了 key 值，先透過 hash function 計算出是哪一個 bucket，得到 bucket 的 index 後，用 for 迴圈去走訪整個 hlist，這個 hlist 是由一堆 hash_key 組成，不是 hlist_node，hlist_node 是 hash_key 的成員，用來串接所有 hash_key，所以為了知道該 hash_key 中的 key值，必須先透過 container_of 得到該 hash_key 。若有找到就回傳該 hash_key，沒有就回傳 NULL。

static struct hash_key *find_key(map_t *map, int key)
{
    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;
    }
    return NULL;
}

這個 hash function 的設計方式是將 key 值乘上黃金比例常數，藉此打亂其位元分布、減少碰撞，這是來自 Donald Knuth 在《The Art of Computer Programming》中的建議。bits 則用來控制雜湊表的大小，決定 bucket 的數量。例如當 bits = 10 時，雜湊表會有

210=1024 個 buckets。整個 hash 的結果會將 key 乘上黃金比例後，再將 32-bit 結果右移
(32−bits) 位，也就是右移 22 位，讓 index 落在 [0, 1023] 的範圍內。

// Hash function
#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);
}

如果沒有在 hash table 中找到，在 hash table 中建立該 key 值的 hash_key。

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, 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;
}
  • 由於都是呼叫 hash function 得到 bucket index，所以 AAAA = map->bits 以及 BBBB = map->bits。
  • 為了維護整個 double linklist 的結構，所以 CCCC = first->pprev 以及 DDDD = n->pprev。
  • 為了從 hlist 上移除 n，要先取得 n 的前一個以及下一個 hash_key，EEEE = n->pprev。

待完成

延伸問題

Last changed by 
 
TonyLinX
hard-working Student
0
71

Read more

第一次討論

contributed by TonyLinX

Jun 15, 2025
牛頓法

contributed by TonyLinX

Jun 9, 2025
2025q1 Homework1 (lab0)

作業書寫規範:

Jun 8, 2025
linux2025-homework5

contributed by < TonyLinX >

May 29, 2025
Read more from TonyLinX
Published on HackMD