2024q1 Homework2 (quiz1+2)

contributed by < yu-hsiennn >

quiz 1

題目

測驗 1

函式功用

void list_add(node_t **list, node_t *node_t): 串 node_t 到 *list 前方
node_t *list_tail(node_t **left): 回傳此串列的最後節點
int list_length(node_t **left): 計算此串列的長度
node_t *list_construct(node_t *list, int n): 串列初始化
void list_free(node_t **list): 釋放串列的記憶體空間
static bool list_is_ordered(node_t *list): 串列是否由小到大排序
void shuffle(int *array, size_t n): 將陣列依據其大小打亂裡面的值

解題過程

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

由函式名稱可以推得，要找的是使串列的尾巴，所以需要跑完整條鏈結串列，故要更新 left 指向的位置， AAAA 則為下一個節點的位置，即 (*left)->next

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

由函式名稱可以推得是要找此串列的長度，故要更新 left 指向的位置， AAAA 則為下一個節點的位置，即 (*left)->next

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

begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;

這邊的 while loop 是在遍歷整條鏈結串列，故 p 應為 p->next
DDDD，EEEE 都是要找目前子串列的尾巴，即 list_tail(left)，list_tail(right)

quick_sort

流程如下：

計算此串列長度 n
創兩個大小為 n 的指標陣列 begin ， end ，初始值設為 begin[0] = *list, end[0] = list_tail(list);
判斷是否 i >= 0，是則進入迴圈
將 L 設為 begin[i]， R 設為 end[i]，並判斷 L 是否等於 R
若不相等則將 L 加進最終結果；相等則把 L 當為 pivot
跑過所有陣列並將小於 pivot 的串到 left 大於的串到 right
更新 begin 陣列內容
重覆 2.~7. 直到跳出迴圈
把結果只回 list 完成排序

以下用圖解來說明：

Round 1

Round 2

Round 3 ~ 5 (從 Begin 及 End 右邊，相等則加進 Result 的前面)

Round 6

最終結果

改進 quick_sort

空間可以不用開到 2 * n

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
-   int max_level = 2 * n;
+   int max_level = 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);
            }

+           if (left) {
+               begin[i] = left;
+               end[i++] = list_tail(&left);
+           }
+           begin[i] = pivot;
+           end[i++] = pivot;
+           if (right) {
+               begin[i] = right;
+               end[i++] = list_tail(&right);
+           }
-           begin[i] = left;
-           end[i] = DDDD;
-           begin[i + 1] = pivot;
-           end[i + 1] = pivot;
-           begin[i + 2] = right;
-           end[i + 2] = EEEE;

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

使用 Linux 核心 `List API` 改寫

最差狀況: 串列數值為小到大，或是大到小
TODO: List API

測驗 2

函式功用

static void create_sample(struct list_head *head, element_t *space, int samples): 創造一個隨機串列
static void copy_list(struct list_head *from, struct list_head *to, element_t *space): 複製 from 的串列到 to 的串列上
int compare(void *priv, const struct list_head *a, const struct list_head *b): 用來當作排序的依據
bool check_list(struct list_head *head, int count): 確認串列是否排序好且是穩定的排序

Timsort 特性

有穩定性
merge 採用2的冪效果最佳
每個 run 都會呈現小到大
設定 minrun 來限制每個 run 的最小長度，若不符合要求，則利用二分搜尋法插入進適合的位置
minrun 會從 32~64 當中挑選一個數字，使其長度除以 minrun 可以等於或是略小於2的冪
合併採取
$A > B + C$ 及
$B > C$ ，只要不滿足任何一式，就會進行合併

解題過程

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 = AAAA;

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

AAAA 應為 head 的起始值，也就是 &head ，後續再改變指向的位置即可
BBBB 及 CCCC 都是再串接新節點後要更新 tail 的最後位置，即 &a->next，&b->next

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 */
    DDDD = head;
    EEEE = tail;
}

根據註解 The final links to make a circular doubly-linked list ，可以知道是要將整條串列變成有迴圈的雙向鏈結串列，而再觀察上面的 do while 可以知道目前 tail 的位置是串列最後一個節點，所以 DDDD 應為 tail->next， EEEE 應為 head->prev

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

根據判斷是可以知道若小於則不做合，只需要重建鏈結串列節點的關係即可，故可以推得 FFFF 為 1

改進程式碼

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 = AAAA;

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

重構部分重複的部分，減少迴圈內 if 的判斷次數

整合進 `lab0-c`

TODO

quiz 2

題目

測驗 1

解題過程

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

根據函式名稱可以推測出是要把新的節點加進串列中，所以 AAAA 應為 h->first

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

BBBB 是要遍歷每個節點，故應該要用 &heads[hash]，而 CCCC 是要進去 entry 裡面取值，所以應該為 list_entry

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, DDDD);
}

將新的節點加進串列裡面，DDDD 應為 &heads[hash]

測驗 2

解題過程

LRUChach: 用於 LRU 緩存機制的主體結構。包含下列幾個元素
- capacity: 緩存的最大容量
- count: 當前緩存中項目的數量
- dhead: 一個雙向鏈結串列的頭節點，用於按最近使用順序維持其緩存項目
- hhead[]: 一個 hash 頭節點的數組，用於快速訪問緩存項目
LRUNode: 是緩存中每個項目的結構，包含每個緩存項目的資料
- key: 鍵值
- value: 數值
- node: 用於將此緩存項目連接到 hash 的結構
- link: 用於將此緩存項目連接到雙向鏈結的結構
透過 hhead[] 中的 hash table 可以快速定位一個特定的 LRUNode
dhead 用於指向最近被訪問的值
關係圖如下

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

藉由函式名稱可以知道是要用來移除某個節點，而 *pprev 為前一個節點，所以應該更新 next 的 prev， EEEE 即為 next->pprev

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

FFFF 為 pos 裡面的 LRUNode 中的 link
GGGG 要將此節點從串列中移除，故 &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(IIII, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}
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, JJJJ);
        if (c->key == key) {
            list_move(KKKK, &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;
}

根據函式名稱可以得知是要找快取中是否有這個 key 值，而 pos 會跑雜湊位置中的每個節點，而 HHHH、JJJJ 都會對應到 hlist_node 的內容，根據 LRUNode 結構可以知道兩個都為 node
IIII、KKKK 用於將他們的 link 移到 dhead 的下一個位置，故為 &cache->link、&c->link

TODO (find LRU code in Linux kernel)

測驗 3

解題過程

首先，先觀察巨集的功用

BITMAP_LAST_WORD_MASK(bits): 利用遮罩的方式，來把用不到的位元給過濾掉，因位元的大小可能不是剛好 64-bit
__const_hweight64(w) (__const_hweight32(w) + __const_hweight32((w) >> 32)): 計算 Hamming 權重，即二進位有幾個 1

# example:
word = 1010101010101010101010101010101010101010101010101010101010101010 (64 bits)

Step 1: __const_hweight64
Lower 32 bits: 10101010101010101010101010101010
Upper 32 bits: 10101010101010101010101010101010

Step 2: __const_hweight32
For both Lower and Upper 32-bit parts:
Split into 16-bit parts.
Lower 16 bits: 1010101010101010
Upper 16 bits: 1010101010101010

Step 3: __const_hweight16
For both Lower and Upper 16-bit parts of each 32-bit part:
Split into 8-bit parts.
Lower 8 bits: 10101010
Upper 8 bits: 10101010

Step 4: __const_hweight8
For each 8-bit part:

Bit 0: 1 (1)
Bit 1: 0 (0)
Bit 2: 1 (1)
Bit 3: 0 (0)
Bit 4: 1 (1)
Bit 5: 0 (0)
Bit 6: 1 (1)
Bit 7: 0 (0)
The Hamming weight for each 8-bit part is 4 (since there are four 1s).

Step 5: Sum up the Hamming weights
Each 16-bit part has two 8-bit parts, so its Hamming weight is 4 + 4 = 8.
Each 32-bit part has two 16-bit parts, so its Hamming weight is 8 + 8 = 16.
Finally, the 64-bit word has two 32-bit parts, so its total Hamming weight is 16 + 16 = `32`.

static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;
#if BITS_PER_LONG == 64
    if ((word & AAAA) == 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;
}

由下面的程式可以推論， AAAA 應為 0xffffffff
作用為找到第一個 1 的索引值 (右到左)

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr); // 把第 nr 個 bit 設為 1
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr); // 指向正確要清除的數的位址

    *p &= BBBB;
}

BBBB 將 mask 反向即可清除第 nr 個位元

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

為了不讓 sz 超過 BITS_PER_LONG，故要做 %
用於找到第 N 個設置為 1 的位元

2024q1 Homework2 (quiz1+2)

quiz 1

測驗 1

函式功用

解題過程

quick_sort

改進 quick_sort

使用 Linux 核心 List API 改寫

測驗 2

函式功用

Timsort 特性

解題過程

改進程式碼

整合進 lab0-c

quiz 2

測驗 1

解題過程

測驗 2

解題過程

TODO (find LRU code in Linux kernel)

測驗 3

解題過程

Read more

2024q1 Homework6 (integration)

2024q1 Homework5 (assessment)

2024q1 Homework1 (lab0)

2024q1 Homework4 (quiz3+4)

使用 Linux 核心 `List API` 改寫

整合進 `lab0-c`