2024q1 Homework2 (quiz1+2)

contributed< brian049 >

Quiz1

測驗 1

Optimized QuickSort — C Implementation (Non-Recursive)

填空及解釋運作原理

list_tail 函式藉由 while 迴圈迭代來找到 list 的尾端。

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &((*left)->next);    // AAAA = (*left)->next
    return *left;
}

欲求 list 的長度時，使用 while 迴圈迭代並計數來得到長度。

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &((*left)->next);    // BBBB = (*left)->next
    }
    return n;
}

以下程式碼為實作 Quicksort 的主要部分。

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;
        pivot->next = NULL;

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

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

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

主要程式碼當中，一開始設定 pivot 為最左邊的節點，p 為 pivot 的下一個節點。再來判斷除了 pivot 以外的節點是否大於或是小於 pivot 的值，若是大於 pivot 則將該節點加到 right 序列當中，若是小於則加到 left 序列當中。

切割序列之後將整體序列分成三部分，第一部分首尾節點分別是 left 以及 list_tail(&left) ，第二部分為 pivot 單一節點，第三部分則是 right 以及 list_tail(&right)。

測驗 2

Timsort

填空及解釋運作原理

在測驗 2 當中有指出 Timsort 與 merge sort 最大的差異在於「定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度，若長度太短，就用二分插入排序，將 run 後面的元素插入到前面的 run 裡面。」以及合併時採取 Galloping mode，進而降低 cache miss、降低記憶體開銷、降低比較次數。

以下程式碼為 timsort merge 的實作，用 tail 指標指向 head 來達到首尾相接的鏈結串列，若是 a 指向的節點的值小於或等於 b 節點的值，則將 a 指向的節點加到事先宣告的佇列當中，反之則將 b 指向的節點加入佇列，直到 a 或 b 佇列為空。

static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head;
    struct list_head **tail = &head;    // AAAA = &head

    for (;;) {
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = &a->next;    // BBBB = &a->next
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next;    // CCCC = &b->next
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

以下程式碼將 list 佇列接到 tail 後面，並在最後將尾端與 head 相接，形成首尾相接的佇列。

static void build_prev_link(struct list_head *head,
                            struct list_head *tail,
                            struct list_head *list)
{
    tail->next = list;
    do {
        list->prev = tail;
        tail = list;
        list = list->next;
    } while (list);

    /* The final links to make a circular doubly-linked list */
    tail->next = head;    // DDDD = tail->next
    head->prev = tail;    // EEEE = head->prev
}

以下程式碼是主要實作 timsort 的部份。逐一解說，先將環狀佇拆開成單向鏈結，在藉由 find_run 函式來切割出 run，再使用 merge_collapse 函式來對 run 進行檢查並整理，以確保堆疊中的 run 符合 timsort 的性質。

接下來使用 merge_force_collapse 函式對堆疊進行整理，再進行合併並重新接回雙向環狀鏈結。

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
    stk_size = 0;

    struct list_head *list = head->next, *tp = NULL;
    if (head == head->prev)
        return;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

    do {
        /* Find next run */
        struct pair result = find_run(priv, list, cmp);
        result.head->prev = tp;
        tp = result.head;
        list = result.next;
        stk_size++;
        tp = merge_collapse(priv, cmp, tp);
    } while (list);

    /* End of input; merge together all the runs. */
    tp = merge_force_collapse(priv, cmp, tp);

    /* The final merge; rebuild prev links */
    struct list_head *stk0 = tp, *stk1 = stk0->prev;
    while (stk1 && stk1->prev)
        stk0 = stk0->prev, stk1 = stk1->prev;
    if (stk_size <= 1) {    // FFFF = 1
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);
}

Quiz2

測驗 1

Construct Binary Tree from Preorder and Inorder Traversal

填空及解釋運作原理

hlist_add_head 函式新增節點至鏈結的頭部並更新 h 指標。

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first;    // AAAA = h->first
    n->pprev = &h->first;
    h->first = n;
}

以下程式碼藉由雜湊值來查找想要找的數值 num，利用 hlist_for_each 函式來比對，若找到則回傳當前的索引值 idx，沒有找到則回傳 -1。

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &heads[hash]) {    // BBBB = &heads[hash]
        struct order_node *on = list_entry(p, struct order_node, node);    // CCCC = list_entry
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

node_add 函式計算節計算雜湊值，再使用 hlist_add_head 來新增節點至對應雜湊的 heads 位置。

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &heads[hash]);    // DDDD = &heads[hash]
}

測驗 2

LRU cache

填空及解釋運作原理

hlist_del 函式將欲刪除之節點的前一個節點的指標指向欲刪除節點的下一個節點，來達到刪除節點的功能，而若是下一個節點存在，則更新該節點指向前一個節點的指標。

void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
        next->pprev = pprev;    // EEEE = next->pprev
}

lRUCacheFree 函式利用 list_for_each_safe 來遍歷所有節點，並釋放節點所佔用的記憶體。

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, link);    // FFFF = link
        list_del(&cache->link);    // GGGG = &cache->link
        free(cache);
    }
    free(obj);
}

lRUCacheGet 函式作用是在 LRUCache 中找尋指定值，若是找到則將 cache->link 放到最前面也就代表最近有被使用到。

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, HHHH);
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead);    // IIII = &cache->link
            return cache->value;
        }
    }
    return -1;
}

lRUCachePut 函式分成兩部份，上半部找尋欲加入的 key 值是否存在於雜湊表當中，如果存在則將其移動到最前端來表示最近使用過，類似於 lRUCacheGet 函式的操作方式。

未存在於雜湊表時，也就是函式中的下半部，先檢查現有數量是否相等於 capacity，相等則代表快取已滿，此狀況就會刪除最少使用的數據，也就是最後一個節點，刪除後再新增新的 key 以及其 value 進快取。除此之外，若是快取未滿，就會將新的 key 以及其 value 加入到快取當中，並使當前數量 obj->count 加一。

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *c = list_entry(pos, LRUNode, node);    // JJJJ = node
        if (c->key == key) {
            list_move(&c->link, &obj->dhead);    // KKKK = &c->link
            cache = c;
        }
    }

    if (!cache) {
        if (obj->count == obj->capacity) {
            cache = list_last_entry(&obj->dhead, LRUNode, link);
            list_move(&cache->link, &obj->dhead);
            hlist_del(&cache->node);
            hlist_add_head(&cache->node, &obj->hhead[hash]);
        } else {
            cache = malloc(sizeof(LRUNode));
            hlist_add_head(&cache->node, &obj->hhead[hash]);
            list_add(&cache->link, &obj->dhead);
            obj->count++;
        }
        cache->key = key;
    }
    cache->value = value;
}

測驗 3

find_nth_bit

填空及解釋運作原理

ffs 目的是要找到第一個 set 的 bit。在定義中不斷使用 AND 操作來找第一個 1 的 bit 的位置。

static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;

#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 0) {    // AAAA = 0xffffffff
        num += 32;
        word >>= 32;
    }
#endif
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}

__clear_bit 函式主要用於 fns　函式當中，目的是為了在找到第一個 set 的 bit 的時候，能夠透過清除 bitmap 中的指定 bit，並重複使用 fns 函式來找到第 n 個 set 的位置。

bit index 可以透過 BIT_WORD 巨集來獲得，再搭配 addr 記憶體空間，可得出指定 bit 的位元組。且運用 BIT_MASK 巨集得到 mask 用於清除指定 bit。

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= ~mask;    // BBBB = ~mask
}

FIND_NTH_BIT 把原本的資料以每 64 bit 為單位去作裁切，計算每段其中被設置的位元數量，若位元數量大於要找的位元數 n ，就代表目標位元就在該段內，直接返回。反之則將 n 減去位元數並進行下一個迴圈。

#define FIND_NTH_BIT(FETCH, size, num)                          \
    ({                                                          \
        unsigned long sz = (size), nr = (num), idx, w, tmp;     \
                                                                \
        for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
            if (idx * BITS_PER_LONG + nr >= sz)                 \
                goto out;                                       \
                                                                \
            tmp = (FETCH);                                      \
            w = hweight_long(tmp);                              \
            if (w > nr)                                         \
                goto found;                                     \
                                                                \
            nr -= w;                                            \
        }                                                       \
                                                                \
        if (sz % BITS_PER_LONG)    // CCCC = %                  \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })