2024q1 Homework2 (quiz1+2)

contribute by < david965154 >

第 1 周測驗題

測驗 1

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

在問題代號 CCCC 迴圈中，目的為：走過每一節點，若其成員 value 大於 pivot 成員的 value ，則分配置鏈結串列 right ，否則為 left ，因此若要走過每一節點，則需以 p = p->next 達成。
觀察最外圈 while 迴圈，可以看到關鍵的

node_t *L = begin[i], *R = end[i];
if (L != R) {
	...

這裡是讓 L 指向 begin[i] ，而 R 指向 end[i] ，下一個判斷式為 if (L != R) ，這裡可以看到當 L 及 R 為同一點即無須進入分配 right 及 left 的區塊，是迴圈結束的關鍵。因此近一步來看 begin[i] 及 end[i] 為何

begin[i] = left;
end[i] = DDDD;

可以看到其實 begin[i] 就是鏈結串列 left ，而因為 left 是指標，指著第一個節點，當然 end[i] 也就是指著鏈結串列 left 的尾部節點，因此要填入 list_tail(left) ， end[i + 2] 則填入 list_tail(right) ，如此一來，可以透過將原始鏈結串列，不斷透過與錨點（pivot）比較大小分左右鏈結串列，依序加入右鏈結串列、錨點再來左鏈結串列，達到 quick sort 的目的。

測驗 2

timsort.c 內函式達成目標

static inline size_t run_size(struct list_head *head)

透過是否有下個節點來回傳該鏈結串列長度，與 queue.c 實作時使用的結構大同小異，但是會在函式 timsort 內先將雙向循環鏈結串列從尾部與頭部斷開成為非循環狀態，因此可以達成這樣的計算判斷式
再來說明 (head->next->prev) 理應要指向一 struct ，但是這裡卻強制轉型為 size_t 型態，因此要從後方函式 find_run 看起，該函式在執行完的最後執行了 head->next->prev = (struct list_head *) len; ，他把 size_t len 轉型為 struct list_head ，再將鏈結串列長度資訊包含在已經斷開的 (head->next->prev) 。這樣在初始放入亂數在鏈結串列時，直接順便計算數量，並包含在鏈結串列內，無須在需要時逐一走訪鏈結串列計算節點數。

補充 std::size_t

std::size_t can store the maximum size of a theoretically possible object of any type (including array).

static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)

這段就是用來 merge 兩個鏈結串列的，透過比較兩個鏈結串列最前方的節點並接上 head 達成。

struct list_head *head;     
struct list_head **tail = AAAA;
...
if (cmp(priv, a, b) <= 0) {
    *tail = a;
    tail = BBBB;
    a = a->next;
    if (!a) {
        *tail = b;
        break;
    }
}
...

tail 用途顯然是用來接續 head 指向的鏈結串列，因此初始會指向指標 head ，若以一般使用 pointer 的方法改寫:

struct list_head *head;
struct list_head *tail = head;
...
if (cmp(priv, a, b) <= 0) {
    if(head) 
        tail = a;
    else 
        tail->next = a;
    
    tail = tail->next;
    a = a->next;
    if (!a) {
        tail = b;
        break;
    }
}
...

這種寫法每次進迴圈皆須做一次比較，若改以第二種方法:在進入 for 迴圈時讓 head 有指向節點，而不是一個指標，因此先做一次 cmp(priv, a, b) ，讓他接上一節點再進入 for 迴圈。不過又會因此多寫一段，若改以指向指標的指標寫，那麼指標 head 與節點 next 接為指標，不必因為 tail 只能指向結構而分兩種情況。

static void build_prev_link(struct list_head *head,
                            struct list_head *tail,
                            struct list_head *list)

這裡是將 list 裡的節點依序接上 tail ，最後再頭尾相連形成雙向循環鏈結串列。

static void merge_final(void *priv,
                        list_cmp_func_t cmp,
                        struct list_head *head,
                        struct list_head *a,
                        struct list_head *b)

這裡也是 merge ，不過是將輸入的單向鏈節串列 merge 後同時轉為雙向鏈節串列，當其中鏈結串列比較完後統一將剩餘單向鏈結串列接至 b 再透過函式 build_prev_link 將 b 後方之單向鏈節串列轉為雙向鏈節串列。

static struct pair find_run(void *priv,
                            struct list_head *list,
                            list_cmp_func_t cmp)

給定一 list 從頭開始選取兩個 list->next 與 list ，若後比前小 ( 即 list->next 比 list 小 ) 則 list 的指標 next 指向 list 原先的 prev 直到又遇到後比前大或 list 沒有 next 節點 ( 即 list->next 比 list 大 ) ，整段迴圈即停止，而若後比前大，則正常移動。同時，兩者在移動的同時皆會計算經過節點數量。
在最後 next 會指向 NULL 或是 與上述順序相反的第一節點 。
最後會產生一單向鏈結串列，而 head 指向其第一節點，的節點的指標 prev 將會指向 NULL ，而將鏈結串列長度資訊包含在不需要的 (head->next->prev) ，也就是第二個節點的指標 prev。
最後透過 struct pair 透過 head 及 next 指向此函式建立的單向鏈結串列及下一次的起點 next ( 即此次單向鏈結串列迴圈結束後的第一個節點 )。

static struct list_head *merge_at(void *priv,
                                  list_cmp_func_t cmp,
                                  struct list_head *at)

這裡也是做 merge ，不過 merge 的兩鏈結串列結構較特殊，其中一鏈結串列為另一鏈結串列的首個節點使用 prev 指向其首個節點，因此有一鏈結串列的走訪方法為 at 往 next 方向移動，而另一鏈結串列為 at->prev 後往 next 方向移動。
兩鏈結串列合併後，將 merge 後之鏈結串列首個節點 prev 指向原先 at->prev 的 prev (即其中一項鏈結串列之原本指向的 prev) 指向的節點，再將鏈結串列第二個節點的 prev 指向鏈結串列長度。

static struct list_head *merge_force_collapse(void *priv,
                                              list_cmp_func_t cmp,
                                              struct list_head *tp)

這裡就是 merge 不同串鏈結串列，不過因為 merge 的對象必須相鄰，因此同時會合併第 2 條鏈結串列的情況下，這裡會選擇較短的先與第 2 條做合併，因此可以達到每次合併都盡量以最少長度合併 (因為合併時所需的最大比較次數為兩鏈結串列之最大長度) ，而避免每次需與越來越長的鏈結串列合併時最大比較次數被該鏈結串列支配的情況。

static struct list_head *merge_collapse(void *priv,
                                        list_cmp_func_t cmp,
                                        struct list_head *tp)

這裡是確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：

1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。

如

$A$ 的長度不大於

$B$ 加

$C$ 的總和（亦即

$A<=B+C$），且

$C$ 的長度小於

$A$，因此會選擇將

$C$ 與

$B$ 進行合併。甚至當需 merge 之鏈結串列超過 4 時 D 也會被納入考慮，如

$D<=C+B$ 。

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)

這裡實際上就是應用各函式，分成四個部分

1. 斷開原始鏈結串列循環，成為非循環單向鏈結串列。
2. 開始透過 find_run 切分子鏈結串列，且在切的時候當切出超過 2 個子鏈結串列會以 merge_collapse 確保堆疊上的 run 長度保持平衡。
3. 在需 merge 子鏈結串列 >=3 時皆以 merge_force_collapse 進行合併。
4. 透過 build_prev_link 建立雙向鏈節並以 merge_final 合併剩餘二雙向鏈節串列。

如此一來便合併完各雙向循環鏈結串列並結束函式。

第 2 周測驗題

測驗 1

在說明如何透過陣列的前序 (preorder) 和中序 (inorder) 形式，建立二元樹前，先來看一下儲存 hash table 的鏈結串列 (不過在這裡沒有用到) 。

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

hlist_node 就是一個由成員 : 指向結構的指標 next 及指向指向結構的指標的指標 pprev 的結構。
詳見 Linux 核心的 hash table 實作

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

這裡需要添加 n 指向的 struct hlist_node 至 h->first 指向的首個節點，而因為指標的指標 pprev 指向前一個節點指向下一個節點的指標 (即指向自身節點的指標) 因此若 h->first 有指向節點，則先將原始 h->first 指向的首個節點的 pprev 指向要新增的節點的 next 指標，為 "退位" 做準備，接下來把 n->next 指向 h->first 和 n->pprev 指向 h->first 的位置，最後將 h->first 指向 n 即完成新增節點至鏈結串列的動作。
接下來就是整段程式碼核心，建立二元樹。

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)

簡單明瞭就是透過 preorder 及 inorder 陣列順序尋找對應位置關係建立二元樹，而 pre_low, pre_high, in_low, in_high 是用來儲存須建立的子樹在陣列中的範圍。

測驗 2

LRUCache *lRUCacheCreate(int capacity)

這裡先創建一個 capacity 數量的 struct list_head 不過這裡的 malloc 配置應該有誤

LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
                             capacity * sizeof(struct list_head));

LRUCache 結構為

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

應要配置 struct hlist_head hhead[] 的空間，且在迴圈內部

for (int i = 0; i < capacity; i++)
        INIT_HLIST_HEAD(&cache->hhead[i]);

這裡會透過函式 INIT_HLIST_HEAD 將 capacity 個 &cache->hhead[i] 初始化，而 INIT_HLIST_HEAD 需要 struct hlist_head *h 作為參數，因此 malloc 應該改成

LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
                             capacity * sizeof(struct hlist_head));

void lRUCacheFree(LRUCache *obj)

這裡就是將所有配置的 cache 做移去並釋放記憶體的動作。

int lRUCacheGet(LRUCache *obj, int key)

給予一 key 值，若在 cache 中找到便移去 obj->dhead 並回傳其 value 。用意是只要最近使用到就移去最近在使用之代表區域。

void lRUCachePut(LRUCache *obj, int key, int value)

這裡前面類似函式 lRUCacheGet ，不過這裡是在給予一 key 值，找到對應的 cache，如果找布袋那就代表需要配置一節點給予放置，因此會判斷 count 是否等於 capacity ，若是則刪除最近沒使用到的，若非則配置一塊新的 LRUNode ，再將其 value 設為傳入參數 value 。

測驗 3

#define FIND_NTH_BIT(FETCH, size, num)    

這裡要找一塊 bit 數為 size 的記憶體區塊，裡面第 num 個被 set 為 1 的位置，而計算時需要將 size 切分為多個 BITS_PER_LONG 再用 macro hweight_long 計算。

static inline unsigned long __ffs(unsigned long word)

計算多少個連續 0 ，即為右移連續零後的第一個 1 之位置。

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)

清除位於指定記憶體位址中指定位的位元值（設置為 0）

static inline unsigned long fns(unsigned long word, unsigned int n)

在 word (一個長整型數值) 中找到第 n 個設置位 (1 的位) 的位置。使用 while 迴圈不斷透過 __ffs 尋找，直到 n 為 0，結束。

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)

使用上面的函式計算，若小於 BITS_PER_LONG 則無需使用函式 FIND_NTH_BIT 計算，直接對指向記憶體位置之值使用 macro GENMASK 產生長度為 size 的 mask，並使用 fns 計算。