# 2024q1 Homework2 (quiz1+2)

contributed by < [`Wufangni`](https://github.com/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 為止。

digraph name{
        node[shape=box]        
        rankdir = LR
        n1[label=node1]
        n2[label=node2]
        
        
        NULL[label=NULL,shape=plaintext]
        n1 -> n2 ->NULL
        {
            rank="same";
            L[label="**left", shape=plaintext, fontcolor=blue]
            left[label="*left", shape=plaintext, fontcolor=blue]
            left -> n1[color=blue]
            L -> left[color=blue];
        }
        {
            rank="same";
            left_n[label="(*left)->next", shape=plaintext, fontcolor=blue]
            left_n -> n2[color=blue]
            ;
        }
        
}

digraph name{
        node[shape=box]        
        rankdir = LR
        n1[label=node1]
        n2[label=node2]
        
        
        NULL[label=NULL,shape=plaintext]
        n1 -> n2 ->NULL
        {
            rank="same";
            L[label="**left", shape=plaintext, fontcolor=blue]
            left[label="*left", shape=plaintext, fontcolor=blue]
            left -> n2[color=blue]
            L -> left[color=blue];
        }
        {
            rank="same";
            left_n[label="(*left)->next", shape=plaintext, fontcolor=red]
            left_n -> NULL[color=red]
            ;
        }
        
}

#### 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 頭及尾端節點。

digraph name{
        node[shape=box]        
        rankdir = LR
        n11[label=7]
        n12[label=5]
        n10[label=4]
        n7[label=2]
        n8[label=3]
        n9[label=1]
        n1[label=4]
        n2[label=1]
        n3[label=3]
        n4[label=5]
        n5[label=2]
        n6[label=7]
        
        n1 -> n2 -> n3 -> n4 -> n5 -> n6
        n7 -> n8 -> n9
        n10
        n11 -> n12
        {
            rank="same";
            
            pivot[label="pivot", shape=plaintext, fontcolor=red]
            L[label="L", shape=plaintext]
            L -> n1
            pivot -> n1[color=red]
        }
        {
            rank="same";
            R[label="R", shape=plaintext]
            R -> n6
        }
        {
            rank="same";
            begin0[label="begin[0]", shape=plaintext]
            begin0 -> n7
        }
        {
            rank="same";
            end0[label="end[0]", shape=plaintext]
            end0 -> n9
        }
        
        {
            rank="same";
            end1[label="begin[1] \\ end[1]", shape=plaintext]
            end1 -> n10
        }
        {
            rank="same";
            begin2[label="begin[2]", shape=plaintext]
            begin2 -> n11
        }
        {
            rank="same";
            end2[label="end[2]", shape=plaintext]
            end2 -> n12
        }
}

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

digraph name{
        node[shape=box]        
        rankdir = LR
        n11[label=7]
        n10[label=5]
        n1[label=7]
        n2[label=5]
        
        
        n1 -> n2 
        n10
        n11
        {
            rank="same";
            
            pivot[label="pivot", shape=plaintext, fontcolor=red]
            L[label="L", shape=plaintext]
            L -> n1
            pivot -> n1[color=red]
        }
        {
            rank="same";
            R[label="R", shape=plaintext]
            R -> n2
        }
        {
            rank="same";
            end1[label="begin[2] \\ end[2]", shape=plaintext]
            end1 -> n10
        }
        {
            rank="same";
            begin2[label="begin[3] \\ end[3]", shape=plaintext]
            begin2 -> n11
        }
}

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

digraph name{
        node[shape=box]        
        rankdir = LR
        n1[label=4]
        n2[label=5]
        n3[label=7]
        
        n1 -> n2 -> n3
        {
            rank="same"; 
            L[label="result", shape=plaintext]
            L -> n1
            
        }
        
}

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

digraph name{
        node[shape=box]        
        rankdir = LR
        n12[label=3]
        n11[label=2]
        n10[label=1]
        n7[label=2]
        n8[label=3]
        n9[label=1]
        
        n7 -> n8 -> n9
        n10
        
        
        {
            rank="same";
            
            pivot[label="pivot", shape=plaintext, fontcolor=red]
            L[label="L", shape=plaintext]
            L -> n7
            pivot -> n7[color=red]
        }
        {
            rank="same";
            R[label="R", shape=plaintext]
            R -> n9
        }
        
        {
            rank="same";
            end0[label="begin[0] \\ end[0]", shape=plaintext]
            end0 -> n10
        }
        {
            rank="same";
            end1[label="begin[1] \\ end[1]", shape=plaintext]
            end1 -> n11
        }
        {
            rank="same";
            end2[label="begin[2] \\ end[2]", shape=plaintext]
            end2 -> n12
        }
}

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

digraph name{
        node[shape=box]        
        rankdir = LR
        
        n1[label=1]
        n2[label=2]
        n3[label=3]
        n4[label=4]
        n5[label=5]
        n6[label=7]
        
        n1 -> n2 -> n3 -> n4 -> n5 -> n6
        
        {
            rank="same";
            
            
            L[label="result", shape=plaintext]
            L -> n1
            
        }
        
}

#### `改進方法`
若遇到特殊情況(例如降冪排序或升冪排序)，每次故左邊第一個做 `pivot` 會導致 worse case 產生，即時間複雜度為 $O(n^2)$，在挑選 `pivot` 時參考 [`ChiTingCheng`](https://hackmd.io/@r36EKfH2TwalEWG_fUuSyg/linux2024-homework2) 同學的改進方案，每輪重新選擇 `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```

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/rJfzk-9T6.png" alt="Image Alt Text" style="width: 70%; height: auto;margin: 10px;">
</div>

- Step2: 新增 n 節點的 ```*next``` 指向 ```h->first```
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/BJuq1b9aa.png" alt="Image Alt Text" style="width: 70%; height: auto;margin: 10px;">
</div>

- Step3: n 節點的 ```*pprev``` 指向 ```&h->first```
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/B1MMxZ5pa.png" alt="Image Alt Text" style="width: 70%; height: auto;margin: 10px;">
</div>

- Step4: ```h->first``` 指向 n 節點
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/HkhOgZ5aa.png" alt="Image Alt Text" style="width: 70%; height: auto;margin: 10px;">
</div>

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

digraph {
rankdir=LR;
subgraph cluster_1{
node [shape=record];
label = "LRUCache"
list_head [label = "<h> dhead|{<next> next|<prev> prev}", group = list];
other[label = "<cap> capacity"]
other2[label = "<count> count"]
hlist_head [label = "<h> hhead[]|...|... |... "];
}
}

digraph {
rankdir=LR;
subgraph cluster_1{
node [shape=record];
label = "LRUNode"

other[label = "<cap> key"]
other2[label = "<count> value"]
list_head [label = "<h> link|{<prev> prev | <next> next}", group = list];
hlist_head [label = "<h> node|{<prev> pprev | <next> next}"];
}
}

#### 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; \
})