2025q1 Homework2 (quiz1+2)

contributed by < Brianpan >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

Repo: Link

Quiz 1

Q1

題目要寫一個list_insert_before函式, p是指到next指標的地址,所以終止條件是
*p 代表指到的那個元素

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 != NULL; p = &(*p)->next)
        ;
    *p = item;
    item->next = before;
}

延伸問題: 撰寫合併排序
commit

Q2

演算法精神

演算法主要是在做移除符合適當大小的節點,這個設計沒有考慮樹的再平衡
移除的情況有三種

1. 左右子節點皆存在
2. 只有一個左右子節點
3. 沒有左右子節點

情況2,3比較直觀
情況2直接把那個子節點拉上來

block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;

情況3就直接把目標節點從樹中移除

*node_ptr = NULL

情況1的狀況是要思考這個刪除的節點要怎麼取代
有兩種方法

1. 左子樹最大值的節點
2. 右子樹最小值的節點
   本題實作採取1.的做法

接下來找最右節點又有兩種情況

1. 直接是刪除節點的左節點
2. 不是左節點
   是情況1.好解決,我們直接把刪除的節點的指標指給左節點

block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /

情況2.以這個子樹為例我們要刪除9, 我們找到最大右節點5
做以下步驟

• 紀錄9的左右子節點
• 把5節點從樹中移除,這個動作代表5的左節點會取代5的位置
• 把5節點取代9節點的位置

實作中透過指標的指標去間接更新刪除節點的母節點指標

實作

找左子樹最右邊的節點

/*
 * Structure representing a free memory block in the memory allocator.
 * The free tree is a binary search tree that organizes free blocks (of type block_t)
 * to efficiently locate a block of appropriate size during memory allocation.
 */
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 && (*pred_ptr)->right)
            pred_ptr = &(*pred_ptr)->r;

        /* Verify the found predecessor using a helper function (for debugging).
         */
        block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
        assert(expected_pred == *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);
        }
    }
    /* If the target node has one child (or none), simply splice it out. */
    else if ((*node_ptr)->l || (*node_ptr)->r) {
        block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;
    } else {
        /* No children: remove the node. */
        *node_ptr = NULL;
    }

    /* Clear the removed node's child pointers to avoid dangling references. */
    target->l = NULL;
    target->r = NULL;
}

補完程式碼

https://github.com/Brianpan/kernel-hw2/blob/master/q2.c

閱讀筆記

TBD

Q3

QuickSort精神

1. 找一個pivot值,將整個陣列或串列分成兩個部分,左半邊都小於等於pivot,右半邊都大於pivot
2. 向下分成左右兩個子問題,繼續做步驟1的操作,直到只剩下一個元素
3. 合併左右兩邊和pivot成為一個排序的陣列或串列

非遞迴版本實作

概念

想像一個虛擬的堆疊用迴圈迭代確認是否為空
這個例子是用begin,end陣列指到的值
初始狀態是

begin[0] = *list;
end[0] = list_tail(list);

每一輪結束後的更新狀態是

begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);

收斂是當L==R, 像是pivot那一點就是確認已排序

每個回合結束後會i+2,換句話說我們先排右邊的序列

圖解

初始狀態

把pivot節點從串列移除

p處理完節點1

p處理完節點0

p處理完所有節點

更新begin[i], end[i]指標
意義就是下一輪的左右邊界

實作

單向串列版本

連結

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;

    begin[0] = *list;
    end[0] = list_tail(list);

    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;

            while (p) {
                node_t *n = p;
                p = p->next;
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = list_tail(&left);
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = list_tail(&right);

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

雙向串列版本

連結
此版本和單向串列的主要差別

• 只使用一個begin陣列去模擬堆疊
• 每次分割左右兩個串列前要把環狀串列最後指標給移除
• 這個實作最後要把雙向串列的prev指標更新回正確的地址

Quiz2

Q1

題目精神

• 利用list API實作quicksort
• 實作有效亂數

補完程式碼

程式碼

實作quicksort

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

    // get the pivot and remove it from the circular list
    pivot = list_first_entry(head, struct listitem, list);
    list_del(&pivot->list);
    
    // move item to either list_less or list_greater 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
            list_move_tail(&item->list, &list_greater);
    }
    
    // divide part
    // recusively sort left, right sublist
    list_quicksort(&list_less);
    list_quicksort(&list_greater);
    
    // merge phase
    list_add(&pivot->list, head);
    // list_less to the beginning of the list_head
    list_splice(&list_less, head);
    // list_greater to the end of the list_head
    list_splice_tail(&list_greater, head);
}

測試程式碼

更改原本的實作,使用比較前後元素確認排序是否成功

i = 0;
list_for_each_entry_safe (item, is, &testlist, list) {
    if (is)
        assert(cmpint(&item->i, &is->i) < 0);
    list_del(&item->list);
    free(item);
    i++;
}

延伸問題

list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting?

stable sorting
假設排序中有兩個元素在比較下是相同的 cmp(a, b) == 0, stable sorting會保證排序後相同排序大小的元素有按照原本的出現順序

$[1_1,2,1_2]$ ->

$[1_1,1_2,2]$

回到原本的問題為什麼無法滿足stable sorting, 那是因為使用list_move就讓原本的順序相反,因為是往前插入

實作整合至lab0c

commit
使用quicksort實作有兩個perf test沒有跑過

分析

TBD

Q2

題目精神

• 認識位元操作API: clz, ctz
• 位元操作
• 計算平方根

clz實作

演算法精神

從長度32開始每次遞迴都把長度減半
終止條件:剩下兩位元時查表
magic number代表在2bit時候的快速查表

• clz(0) : 2
• clz(1) : 1
• clz(2) : 0
• clz(3) : 0

// divide and conquer width
static const int mask[] = {0, 8, 12, 14};
// magic numbers for 2 bits
// 0 -> 2
// 1 -> 1
// 2 -> 0
// 3 -> 0
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]));
    
    // 2 bits left which implies c == 3
    // c = 0 => 16 bits
    // c = 1 => 8 bits
    // c = 2 => 4 bits
    // c = 3 => 2 bits
    if (c == 3)
        return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

64位元是32位元延伸, 先判斷前32位元clz32是否是0, 是則判斷下32位元的clz32值

static inline int clz64(uint64_t x)
{
    return clz32(x >> 32) ? clz32(x >> 32) :
           clz32(x & 0xFFFFFFFF) + 32;
}

計算sqrt

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)) & 0xFFFFFFFE;
    m = 1ULL << shift;

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

演算法精神

TBD
理解中, 要用自己的話說一次
reference

Q3

目標

• 理解hash table實作
• 應用在2sum

這裡是使用linked list方式實作map,這個方式好處是不用碰撞後還要挪元素
(probing)

hlist

linux 用於hash table實作的資料結構include/linux/types.h

struct hlist_head {
    struct hlist_node *first;
}

struct hlist_node {
    struct hlist_node *next, **pprev;
}

map實作

資料結構和巨集

#define MAP_HASH_SIZE(bits) (1 << (bits))
#define GOLDEN_RATION_32 0x61C88647

// definition of the map structs
typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

初始化map

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

湊雜函式

static inline unsigned int hash(unsigned int val, unsigned int bits)
{
    return (val * GOLDEN_RATION_32) >> (32 - bits);
}

取得函式
這裡的處理比較直觀

• 先找到湊雜值所在的串列
• 使用線性搜尋找到鍵值相同的元素

static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    // find exact mach of the key from the hash table's hlist
    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;
}

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);

    return kn ? kn->data : NULL;
}

新增函式
比較值得注意的是從頭插入
需要更新**pprev, *next指標

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    // key exists
    if (kn)
        return;
    
    kn = malloc(sizeof(struct hash_key));
    if (!kn)
        return;
    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;
    // renew pprev of old first node
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}

刪除map
每個map串列逐個刪除
這邊pprev的更新是把它更新成&head, 下一輪再做刪除

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;
            
            // next's pprev to cur's pperv
            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);
}