2024q1 Homework2 (quiz1+2)

contributed by < Wufangni >

第一週測驗題

測驗 1

list_tail

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

找出 list 最尾端的節點，*left 指向 list 中的第一個節點依序往下走，直到 *left->next 遇到 NULL 為止。

list_length

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

與上述方法類似，因為計算總節點數須走完全部節點所以判斷條件到 *left 指到 NULL 為止。

quick_sort

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;
            pivot->next = NULL;
    
            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[0] 和 end[0] 初始值設置為 list 的頭及尾端，分別以 L 及 R 兩個 *node_t 型態包裝，先將掃過 list 將小於 pivot 的節點以 list_add 方式加到 left 前端，若大於 pivot 則加到 right 前端。

• Step 1
  begin[0] 及 end[0] 紀錄 left 頭及尾端節點， begin[1] 及 end[1] 紀錄當前 pivot 節點，begin[2] 及 end[2] 紀錄 right 頭及尾端節點。

• Step 2 重複上一步驟，pivot 變為 L 所在節點。

• Step 3
  此時 begin[3] 及 end[3] 都指向同一節點，表示只有一個節點在 begin[3] 當中(後半部分已完成排序)，將 L 加入 result 前端再繼續往下判斷。

• Step 4
  begin[0] 及 end[0] 不相等，將 list 從頭到尾掃一次，比 pivot 小記錄到 begin[0]，反之則記錄到 begin[2]。

• Step 5
  因 begin[0]~begin[2] 都只有一個節點，依序將 L 加入 result。

改進方法

若遇到特殊情況(例如降冪排序或升冪排序)，每次故左邊第一個做 pivot 會導致 worse case 產生，即時間複雜度為

$O(n^2)$，在挑選 pivot 時參考 ChiTingCheng 同學的改進方案，每輪重新選擇 pivot 時以隨機取代固定挑選，更大程度避免陷入 worse case 。

node_t *pivot = pivot_select(L);

測驗 2

timesort

#include <stdint.h>
#include <stdlib.h>

#include "list.h"
#include "sort_impl.h"

static inline size_t run_size(struct list_head *head)
{
    if (!head)
        return 0;
    if (!head->next)
        return 1;
    return (size_t) (head->next->prev);
}

struct pair {
    struct list_head *head, *next;
};

static size_t stk_size;

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;

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

static void merge_final(void *priv,
                        list_cmp_func_t cmp,
                        struct list_head *head,
                        struct list_head *a,
                        struct list_head *b)
{
    struct list_head *tail = head;

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

    /* Finish linking remainder of list b on to tail */
    build_prev_link(head, tail, b);
}

static struct pair find_run(void *priv,
                            struct list_head *list,
                            list_cmp_func_t cmp)
{
    size_t len = 1;
    struct list_head *next = list->next, *head = list;
    struct pair result;

    if (!next) {
        result.head = head, result.next = next;
        return result;
    }

    if (cmp(priv, list, next) > 0) {
        /* decending run, also reverse the list */
        struct list_head *prev = NULL;
        do {
            len++;
            list->next = prev;
            prev = list;
            list = next;
            next = list->next;
            head = list;
        } while (next && cmp(priv, list, next) > 0);
        list->next = prev;
    } else {
        do {
            len++;
            list = next;
            next = list->next;
        } while (next && cmp(priv, list, next) <= 0);
        list->next = NULL;
    }
    head->prev = NULL;
    head->next->prev = (struct list_head *) len;
    result.head = head, result.next = next;
    return result;
}

static struct list_head *merge_at(void *priv,
                                  list_cmp_func_t cmp,
                                  struct list_head *at)
{
    size_t len = run_size(at) + run_size(at->prev);
    struct list_head *prev = at->prev->prev;
    struct list_head *list = merge(priv, cmp, at->prev, at);
    list->prev = prev;
    list->next->prev = (struct list_head *) len;
    --stk_size;
    return list;
}

static struct list_head *merge_force_collapse(void *priv,
                                              list_cmp_func_t cmp,
                                              struct list_head *tp)
{
    while (stk_size >= 3) {
        if (run_size(tp->prev->prev) < run_size(tp)) {
            tp->prev = merge_at(priv, cmp, tp->prev);
        } else {
            tp = merge_at(priv, cmp, tp);
        }
    }
    return tp;
}

static struct list_head *merge_collapse(void *priv,
                                        list_cmp_func_t cmp,
                                        struct list_head *tp)
{
    int n;
    while ((n = stk_size) >= 2) {
        if ((n >= 3 &&
             run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
            (n >= 4 && run_size(tp->prev->prev->prev) <=
                           run_size(tp->prev->prev) + run_size(tp->prev))) {
            if (run_size(tp->prev->prev) < run_size(tp)) {
                tp->prev = merge_at(priv, cmp, tp->prev);
            } else {
                tp = merge_at(priv, cmp, tp);
            }
        } else if (run_size(tp->prev) <= run_size(tp)) {
            tp = merge_at(priv, cmp, tp);
        } else {
            break;
        }
    }

    return tp;
}

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 <= FFFF) {
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);
}

第二週測驗題

測驗 1

hlist_add_head

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;
    n->pprev = &h->first;
    h->first = n;
}

• Step1: 如果 h->first 存在，則將此節點的 pprev 指向 &n->next

• Step2: 新增 n 節點的 *next 指向 h->first

• Step3: n 節點的 *pprev 指向 &h->first

• Step4: h->first 指向 n 節點

find

計算 hash 值後用 hlist_for_each 從對應雜湊值 &heads[hash] 開始往下找尋，使用 container_of 找出此節點的實體位置跟 num 進行比對，若相同則回傳該節點的 inx 。

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]) {
        struct order_node *on = container_of(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

node_add

使用 malloc 分配空間給 *on ，填入對應的 val 及 idx 並計算 hash 值，將其加入 &heads[hash] 位置。

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

dfs

利用中序數列創建一個以中序排列的鏈結串列 *in_heads 。

struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
for (int i = 0; i < inorderSize; i++)
    INIT_HLIST_HEAD(&in_heads[i]);
for (int i = 0; i < inorderSize; i++)
    node_add(inorder[i], i, inorderSize, in_heads);

用 find 找到在中序裡的 idx ，使用 pre_low \ pre_high \ in_low \ in_high 分別對左子樹及右子樹做遞迴。

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

• 左子樹

1. pre_low : 為原本自己再加一，根據前序性質為根節點的下一節點。
2. pre_high : 使用 idx - in_low 計算出根節點左子樹節點數，從 pre_low 往後加即為前序最高索引點。
3. in_low : 原先最低索引位置。
4. in_high : 根節點左邊位置。

• 右子樹

1. pre_low : in_high - idx 算出根結點右子樹節點數，再以原最高索引點 pre_high 減掉右邊總數再加回一，代表前序最低索引點位置。
2. pre_high : 原前序最高索引點。
3. in_low : 根節點右邊位置。
4. in_high : 原中序最高索引位置。

測驗 2

Least Recently Used (LRU)

實作出 LRU 策略的雜湊儲存，先介紹 LRUCache 和 LRUNode 兩種結構。

struct hlist_head {
    struct hlist_node *first;
};
struct hlist_node {
    struct hlist_node *next, **pprev;
};
typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

LRUCache 中使用了 list_head 結構的 dhead 用來串接最近一次存取的節點， hhead[] 則用來串接雜湊的 LRUNode 。

lRUCacheCreate

使用 malloc 分配空間給 *cache ，將兩型態為 int 的變數初始值定義完後使用 INIT_LIST_HEAD 初始化 dhead 及 hhead[] 。

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
                             capacity * sizeof(struct hlist_head));
    cache->capacity = capacity;
    cache->count = 0;
    INIT_LIST_HEAD(&cache->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_HLIST_HEAD(&cache->hhead[i]);
    return cache;
}

lRUCacheFree

使用 list_for_each_safe 逐一釋放 dhead 串聯的 LRUNode ， 最後釋放整個 LRUCache 。

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

lRUCacheGet

利用 key 的值除以總容量取餘數算出雜湊值 hash ，從 &obj->hhead[hash] 開始找若此 LRUNode 的值與 key 相符，則從 dhead 中移除，並回傳此 LRUNode 的 value 。

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, node);
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

lRUCachePut

先計算出雜湊值 hash ，從 &obj->hhead[hash] 逐一找尋若有相同資料已存在在 *obj 中則從 &obj->dhead 中移除，無相同值需判斷目前容量是否已滿。
容量已滿的情況，將 dhead 最前端紀錄的 LRUNode (表示最久未被存取的資料)移除，並將新節點加入 &obj->hhead[hash] 位置。
尚有容量則直接分配記憶體空間給新增節點，將其加入 &obj->hhead[hash] 位置並更新 &obj->dhead 。

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);
        if (c->key == key) {
            list_move(&c->link, &obj->dhead);
            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

__ffs

先以 #if BITS_PER_LONG == 64 判斷是否有 64 位元，可一次與 0xffffffff 做 & 判斷是否吋在 set bit ，接著由高往低判斷一次word可前進多少，最後回傳第一個遇到的 set bit 位置。

#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 0) {
        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

使用 BIT_MASK 建立只有第 nr 的 bit 為 1 的 mask ，對 *p 與 ~mask 做 & 得到只有第 nr 個 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;
}

FIND_NTH_BIT

#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)                              \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })