2024q1 Homework2 (quiz1+2)

contributed by < Shawn531 >

第一週題目

測驗一

在這個測驗中，參考 Optimized QuickSort — C Implementation (Non-Recursive)，實作非遞迴 (non-recursive; iterative) 的快速排序法。

資料型態

這一支程式使用的鏈結串結構體如下，使用了單向串列，有別於 list.h 的雙向串列，而結構體中的 left right 並未使用，因此在此不討論。

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

程式說明

max_level = 2 * n 為堆疊的最大深度，而呼叫這個函式的一開始就會先宣告兩個深度為 2n 的陣列，來保存每個堆疊的開始結束節點，也就是說不管事甚麼情況，這隻程式皆會開出兩個大小為 2n 的空間來做堆疊。

    int n = list_length(list);
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];

進到 while 迴圈後，首先用 L 和 R 獲取當前堆疊的開始和結束節點。之後我們選定基準值 pivot 並保存到 value 中，最一開始的 pivot 都會以最左邊的節點當作 pivot，但這樣或許對部分排序的 list 會造成浪費，因此我認為能夠在 sorting 前加入判斷是否有部分排列的函式來去選擇 pivot，不過也需要對結束條件一起做考慮。

爾後利用 while (p) {...} 處理剩餘的節點，若是大於 value 則放進 right，反之則放進 left。
我們可以將整個 list 依大小分為三個部分，一個是大於 pivot->value 的集合 right 、 pivot 和小於 pivot->value 的集合。這一步驟後我們即可以獲得三個集合。之後left = right = NULL; i += 2; 重置 left 和 right，並移動到下一層次。

可以看到從原本的 [4 1 3 5 2 7] 可以分成 left, pivot, right三堆。

由於 i = i + 2; 因此我們從上一個 iteration 的 right 開始解析，同樣可以在拆成 left, pivot, right，然後到下一個 iteration 時，由於剛剛的 pivot, right 都只有一個節點，因此會依序加到 result 中。

之後我們從 right 解析來看，上一輪的 right 在這一輪又可以分堆成 left, pivot, right，這邊的 left 雖然為 NULL，但在後面步驟會檢查因此不用擔心。

所以整個 list 目前就會像下方這樣，會看到有一個 3 個元素的串列和 3 個 1 個元素的串列，下一次 iteration 的時候，就會把這一些只有一個元素的串列處理並依序加入 result 中:

其實在一般遞迴版本的 quiksort 裡面，到目前為止的步驟都是相似的，差別就是一般是使用遞迴方式實作，而在這段程式碼則使用了 stack 來代替，我認為使用 stack 來代替遞迴的優勢在於，雖然在一開始就必須先開 2 個 2n 的陣列讓他放，而遞迴版本實際上也是用 stack ，只不過它是由 assembler 所產生，因為程式遞迴而產生的組語的大小我認為會比使用 stack 代替的陣列來的小很多，而在運行時間也會優化許多雖然說這取決於編譯器。

回到程式說明的部分，之後我們就會回到迴圈一開始然後 node_t *L = begin[i], *R = end[i];，然後檢查 L 和 R 是不是指向同一個位置，如果不是，就繼續做上述步驟，也就是繼續拆解的意思。如果他們是同一個，那就代表這是最後一個了，該把這個節點加進 result 裡面了，然後 i–，做到最後就可以完成整個排序。如下圖，result 是已經排序好的結果，因此我們只需針對尚未處理過的照著上面的流程走過一遍，即可完成排序。

我們發現發現 4 5 7 現在都是自己一堆了，因此他會被依序加入 result 中，然後我們就可以繼續處理最一開始遺留下來的 left ，接下來的步驟就跟剛剛完全一模一樣了。

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] = head->prev;
            
    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_tail(n, n->value > value ? &right : &left);
            }

            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_tail(L, result);
            i--;
        }
    }
    *list = result;
}

list_tail 要找串列的最後一個元素，理所當然的 AAAA會是 (*left)->next。

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

list_length 透過走訪整條串列計算長度，因此 BBBB 也會是 (*left)->next。

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

使用 Linux 核心風格的 List API 改寫上述程式碼

在測驗一使用到的操作函式 list_add list_tail list_length list_construct list_free 在 list.h 皆有相同功能的操作函式。因此我們可以直接改寫 quick_sort。在此須特別注意的是單向與雙向鏈結串列的處理。

再新增串列陣列時，有遇到以下問題，C90 標準不允許使用 variable length array，因此我將程式碼改為用 malloc配置記憶體。我也試過將 Makefile 的 CFLAGS 改成 C99 的標準，但後來想想這好像不符合規範，因此採用動態配置記憶體的方式。

addop.c:37:5: error: ISO C90 forbids variable length array ‘begin’ [-Werror=vla]
   37 |     element_t *begin[max_level];
      |     ^~~~~~~~~

-   element_t *begin[max_level];
-   element_t *end[max_level];
+   element_t **begin = malloc(max_level * sizeof(element_t *));
+   element_t **end = malloc(max_level * sizeof(element_t *));

# Emit a warning should any variable-length array be found within the code.
# CFLAGS += -Wvla
CFLAGS = -std=c99

目前是將q_quicksort整合進 lab0-c 的專案中，額外開了一個檔案addop.c來存放額外的函式如 shuffle。我有參閱其他同學的作法，很多人的實作方式是將 quicksort 會引用到的 funciton 進行改寫，我的作法是因為舊功能來說，list.h的功能已經相當完善，因此我是針對 quicksort 這個函式做修改，然而在實作方面遇到了一些記憶體洩漏的問題尚未解決，因此先在此記錄，未來待改善。

void q_quicksort(struct list_head *head)
{
    int n = q_size(head);
    char *value;
    int i = 0;
    int max_level = 2 * n;
    // element_t *begin[max_level];
    // element_t *end[max_level];
    element_t **begin = malloc(max_level * sizeof(element_t *));
    element_t **end = malloc(max_level * sizeof(element_t *));
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    // list_entry(head->next, element_t, list)
    begin[0] = list_entry(head->next, element_t, list);
    end[0] = list_entry(head->prev, element_t, list);

    while (i >= 0) {
        element_t *L = begin[i], *R = end[i];
        if (L != R) {
            element_t *pivot = L;
            value = pivot->value;
            struct list_head *p = (&pivot->list)->next;
            (&pivot->list)->next = NULL;

            while (p) {
                struct list_head *n = p;
                p = p->next;
                element_t *node_e = list_entry(n, element_t, list);
                list_add_tail(n,
                              strcmp(node_e->value, value) == 1 ? left : right);
            }

            begin[i] = list_entry(left->next, element_t, list);
            end[i] = list_entry(left->prev, element_t, list);
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = list_entry(left->next, element_t, list);
            end[i + 2] = list_entry(left->prev, element_t, list);

            left->next = right->next = NULL;
            i += 2;
        } else {
            if (L)
                list_add_tail(&L->list, result);
            i--;
        }
    }
    head = result;
    free(begin);
    free(end);
}

測驗二

Timsort

Tim Peters注意到在現實世界的資料中，通常存在著部分已經排序的子序列，這些子序列被稱為 "run"。他的排序策略是先識別這些已排序的子序列，然後通過不斷地合併這些 run 來實現對整個資料範圍的排序。

通過尋找 run 來實現資料的分堆效果，同時注意到單調遞減的 run 會在合併過程中被反轉成遞增的序列。

為了提高合併過程的均衡性，Timsort 定義了一個參數 minrun，表示每個 run 的最小長度。然而在這次的實作中，我們暫時不考慮 minrun，未來可能會引入以進一步提升效能。最佳的效能通常在 run 的數量等於或者略小於 2 的冪時實現，而在 run 數量略大於 2 的冪時，效能會下降。

也不考慮 Galloping mode 的問題，gallping 的特點就是不用從頭開始比對，假設有 A B 兩個排列好的數列，首先尋找 B 的首個元素在 A 中的排序位置，從而確定 A 中有一段是小於 B 的第一位，可以將這部分放回 A，接著尋找剩餘 A 的首個元素在 B 中的位置，如此反覆進行，直到完成排序。這次實作也沒有實現這一個功能，因此會於未來嘗試改進。

程式實作

直接看到主要的函式 timsort ，首先會先檢查 head 並將其轉換為以 null 結尾的單向鏈表，之後開始查找 run 的步驟。find_run的主要功能就是將 run 進行分堆，會先找尋升序的元素直到不再升序為止，此時則會開始找尋降序的元素直到升序為止，如此交替進行便可以找到每一個 run。更新 run 開始節點的 prev 指針，使用 tp 指向的前一個 run 的結束節點，將下一個 run 的開始節點的 prev 指向它。更新 tp 指針使 tp 指向當前 run 的開始節點。然後將 list 指向當前 run 的結束節點的下一個節點，以繼續尋找下一個 run。增加堆疊大小 stk_size。最後使用 merge_collapse 函數對遞增的 run 堆疊進行合併。

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

值得注意的是，若此串列是降序的排列，我們需要將它反轉成升序排列，做法是先初始化一個指針 prev 用於記錄反轉後的前一個節點。do-while 在遞減的 run 中遍歷，將目前節點 list 的 next 指向 prev，然後更新 prev 和 list。最後再將一個list->next 設置為 prev，完成反轉。

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

merge_collapse簡單來說就是在讓堆疊中的 run 進行合併操作，而其中必須符合演算法中的一些規範，才會進行合併，利用這個函式來確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：

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

若不符合則有相對應的 A+(B+C) 或 (A+B)+C 的合併操作，一邊進行 run 的劃分一邊進行 merge 是 Timsort 的獨特設計。

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

merge_at用於在指定的位置 at 合併兩個相鄰的 run。該函數首先計算兩個 run 的大小總和，然後使用 merge 執行實際的合併操作，最後將結果更新到鏈表中。

merge 函数的目的是將兩個已排序的 run 合併成一个更大的有序 run。AAAA 是指向指標的指標，最初指向合併結果的 head 指標，因此AAAA = &head。當比較 a 和 b 的首元素大小時，如果 a 的首元素小於等於 b 的首元素，則將 *tail 設置為 a，並更新 tail 為 &a->next，即指向 a 的下一個節點的指針。這樣做是為了追蹤 run 的尾部。

a 的首元素小於等於 b 的首元素時，BBBB = &a->next，以追蹤 run a 的尾部。a 的首元素大於 b 的首元素時，CCCC = &b->next，以追蹤 run 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 = 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;
}

之後會進到 tp = merge_force_clollapse(priv, cmp, tp);這段程式碼的主要用意是要把剩餘的 run 合併到一起，會強制合併成 1 個或 2 個 run，其基本也是呼叫 merge_at做合併，只是條件不同罷了。

往下看程式碼，主要的功能就是在重建 prev links，但當 stk_size 若是只有一個的話，那他就可以跳過最後的merge_final，直接使用build_prev_link，所以FFFF = 1。build_prev_link的功用在於建立一個雙向鏈結串列，首先將傳入的 tail 的 next 指標連接到 list，建立鏈表的初始連結，之後透過迴圈遍歷整個列表，對每個節點進行處理。而最後的兩行設定了循環列表的頭尾相連。因此DDDD = tail->next，EEEE = head->prev。簡單來說就是將 list連接到tail，因為若stk_size <= 1那就不會有剩餘的狀況，因此將stk0連到head中。

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

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

最後來解析merge_final的目的是將兩個已排序的雙向鏈表合併成一個更大的已排序雙向鏈表（head），基本上跟merge大同小異，差異就是最後的一段build_prev_link，可以透過這個函式將後面剩餘的串列直接加到tail後面。

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

第二週題目

測驗一

Binary Tree

Binary Tree 是一種樹狀結構，其中每個節點最多有兩個子節點，分別稱為左子樹和右子樹。

preorder：
首先訪問根節點，然後遍歷左子樹，最後遍歷右子樹。在遍歷過程中，節點的訪問順序是「root-left-right」。

inorder：
首先遍歷左子樹，然後訪問根節點，最後遍歷右子樹。在遍歷過程中，節點的訪問順序是「left-root-right」。

因此我們就可以利用 preorder 和 inorder 跟在不同的位置，得知目前左子樹和右子樹的範圍，只要走訪完整兩個 order，便可以完整建構一個 binary tree。在這個測驗主要是透過 dfs 深度優先搜索來建立。

資料型態

在這個程式中的結構體主要是利用單向鏈結串列實現，可以看到下圖的圖示說明。

struct hlist_node {
    struct hlist_node *next, **pprev;
};
struct hlist_head {
    struct hlist_node *first;
};
struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};
struct order_node {
    struct hlist_node node;
    int val;
    int idx;
};

除了上面的基本結構外，此測驗也加入了 Hash Table 的概念，基本上就是就是將 hlist_head結構體變成 array，以空間換取時間，圖示說明如下:

binary tree 實作

首先先看到 hlist_add_head，這段程式碼的功用在於加入節點到串列的第一位，因此首先檢查 h->first是否存在，若不存在需要手動初始化，由於我們要把節點 n 加入到第一個，因此我們要將n->next指向原本串列的第一個，所以AAAA = h->first，再來將n->pprev指向原本的&h->first，最後將 n 放到 h->first。

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

node_add的功能是將節點加入 Hash Table 中對應值的鏈結串列的頭部，hlist_head_add可以理解為將節點加入串列頭部的基本操作，而node_add則需要先透過 Hash Table 找到想要操作的串列，因此 DDDD = &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, DDDD);
}

find主要用來在 Hash Table 查找特定數字的函式。首先計算 Hash Value，決定我們要在哪一個串列做搜索。接著透過 hlist_for_each 遍歷欲搜索的鏈結串列，BBBB = &head[hash]。為了由struct hlist_node *p這個型態映射到order_node，可以使用container_of達到目的，也可以使用list_entry，因此CCCC = container_of。這裡值得注意的是，不同於以往的遍歷鏈結串列搜索 O(n)，透過 Hash Table 的方式進行搜尋可以將搜索時間減少到常數時間 O(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, BBBB) {
        struct order_node *on = CCCC(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

接下來看到最主要建構 binary tree 的函式 dfs，使用遞迴的方式來操作，傳入的參數有:

int *preorder 為 preorder list 的第一個位址。
int pre_low 指該次遞迴的 preorder 下限。
int pre_high 指該次遞迴的 preorder 上限。
int *inorder 為 inorder list的第一個位址。
int in_low 指該次遞迴的 inorder 下限。
int in_high 指該次遞迴的 inorder 上限。
stuct hlist_head *in_heads Hash Table 結構體的位址。
int size Hash Table 的欄位總數

在函式的一開始先決定了中止條件，若上限小於下限則會 return NULL。

    if (in_low > in_high || pre_low > pre_high)
        return NULL;

現在開始建構 binary tree，以範例為例，preorder 為 [3, 9, 20, 15, 7]，inorder 為 [9, 3, 15, 20, 7]。首先配置記憶體給要加入的節點，並把 preorder[pre_low] 加入 tn->val，初始的 pre_low為 0，因為 preorder 的順序為中-左-右，因此第一個元素一定代表了 root，所以我們可以透過find(preorder[pre_low], size, in_heads) 到 inorder list 查找 root 的位置，如此一來在這一遞迴就可以劃清左子樹以及右子數。

    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);，說明一下裡面的參數，preorder 的下限會加一，搜尋範圍則會透過idx - in_low決定，意義就是透過 inorder 的 root 位置和 inorder 下限所形成的範圍，也就是說上一次遞迴左子樹的部分，inorder 則會透過原先的下限 in_low 和上一次遞迴的 root 位置 -1 所決定。當左子樹找完就可以找右子樹。上下限的表示如下圖所示，只要根據目前的位置以及範圍就可以準確圈出上下限。

    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;

最後建構 binary tree 的函式，先定義以及初始化 preorder list 和 inorder list，然後再進行 dfs。

static struct TreeNode *buildTree(int *preorder,
                                  int preorderSize,
                                  int *inorder,
                                  int inorderSize)
{
    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);

    return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
               in_heads, inorderSize);
}

測驗二

LRU Cache

LRU（Least Recently Used） Cache 是一種實作 Cache 的策略，由於 Cache 的容量並不是無限大，因此需要針對元素的使用模式來決定哪些元素應該被保留或丟棄。

簡單來說，LRU Cache 的原則是保持最近使用的元素，淘汰最久未使用的元素。實作方法就是將使用過元素記錄到串列中，如此一來便可實現淘汰最久未使用的元素。通常使用雙向鏈結串列和雜湊表 Hash Table 的結合，在這邊 Hash Table 使用單向鏈結串列實作。雙向鏈結串列用於維護元素的使用順序，而哈希表則用於實現快速的查找和刪除操作，因此可以看到兩種不同的串列型態。

單向鏈結串列 for Hash Table

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

不同於雙向鏈結串列的，**pprev 是一個指標的指標的方式呈現，通常用於在修改鏈表結構時更新前一個節點的next指標。這樣設計的目的是為了能夠在操作中修改前一個節點的next指標，而不需要返回上一個節點，若一樣寫成 *prev 的話，那他在 function 就會變成透過 pass by value 傳遞，造成效率不彰。

下方的 function hlist_add_head 可以看到如果 list 裡面沒有東西的話，則更新 head 的 pprev pointer，將新節點的 next 指標指向原串列的第一個節點，並將新節點的 pprev 指標指向鏈表的頭部指標的地址，最後更新串列的 head pointer，使其指向新的節點 n。

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

接下來看到 hlist_del function，一開始先從節點 n 中取得下一個節點 next 以及前一個節點的 next 指標的地址 pprev，之後更新前一個節點的 next 指標，將其指向下一個節點，就是跳過節點 n的意思，最後如果下一個節點存在，需要把下一個節點的 pprev 指標指向前一個節點的 next 指標的地址。因此EEEE = next->pprev。

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

LRU 實作

雙向串列的部分基本與 lab0-c 一樣，在這邊就不多加討論。
直接看到結構體的部分，定義了兩個結構體，分別是 LRUCache 和 LRUNode。

LRUCache 裡包括了 capacity 表示 LRUCache 的最大容量，count 則表示當前已儲存的 key-value pair 數量。dhead 用來記錄 key-value pair 的使用順序，這個雙向串列的節點就是 LRUNode 的 link 成員。hhead[]是一個 Hash Table 的 hlist_head array，可以加速查找 value。而每個 hhead 大小皆為 capacity。

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

LRUNode 裡面包括了 key 和 value，主要會透過他們去做映射，node 是用於 Hash Table 的節點，link 則是用來記錄 LRU 順序的節點。

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

了解基本結構體後就可以來看函式操作了，有四個函式分別是 lRUCacheCreate lRUCacheFree lRUCacheGet lRUCachePut，比較特別的操作是 lRUCacheGet 和 lRUCachePut。lRUCacheGet的功用是透過傳遞 key 取值，需要判斷 key-value 有沒有在 cache 裡面，有的話 return value ，沒有的話 return -1。lRUCachePut則是要放進去，如果有這對 key-value pair 的話，那麼直接更新 value 即可，如果沒有的話則要從記憶體存取並更新。

lRUCacheCreate首先會根據LRUCache結構體去分配記憶體，使用INIT_HLSIT_HEAD來初始化LRUCache的 head array hhead。

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
                             capacity * sizeof(struct list_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;
}

利用list_for_each_safe走訪已使用過的&obj->dhead雙向鏈結，可以透過 n (下一個節點)來安全的刪除節點，因此 list_del(GGGG) 裡面應為 n->prev 確保不會因為刪除了當前節點而造成斷裂。由於 pos 的資料型態為 list_head，因此在 LRUNode 中pos屬於link成員，list_entry(pos, LRUNode, FFFF)應該填入link。

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

接下來來到了最關鍵的兩個 function，先來分析lRUCacheGet，這個函式是用來讀值，首先先計算 key 的 Hash value，接下來使用 hlist_for_each 走訪 obj->hhead[hash] Hash Table 中的 key-value pair。使用list_entry(pos, LRUNode, HHHH)來獲取 pos 在 LRUNode 的結構，跟上一個函式大同小異，可以透過觀察 pos 資料型態來判斷HHHH = node。若傳入的 key 與 cache->key 相同的話則將此節點移到obj->dhead，用來記錄使用的順序，因此IIII = &cache->link，若已走訪整條串列還沒有找到相同的 key 值，則 return -1。

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

lRUCachePut的功能為更新和寫 cache，一開始同樣要計算 Hash value，一樣透過 hlist_for_each 走訪 obj->hhead[has]，同樣的邏輯JJJJ = node，如果 c->key 和傳入的 key匹配到的話，則同樣的將此節點加入obj->dhead紀錄使用順序，所以KKKK = &c->link，到這為止基本上與lRUCacheGet差不多，然而如果key不匹配的話，我們則要另外做處理。
此時會有兩種狀況，第一種是 cache 還有尚未使用的空間，這邊是使用count和capacity互相比較，若count < capacity，就可以直接將傳入的 key value 新增至串列中，所以我們需要先分配一個節點，把key value 加入，並將他記錄到 obj->dhead中。
第二種狀況則是 cache 已滿，那這時候我們就要考慮要刪除誰了，Least Recently Used 的節點就變成我們需要刪除的對象，如此才有空間把新的加進來，因此可以透過cache = list_last_entry(&obj->dhead, LRUNode, link);將最少用到的節點抓出來，然後把它移到 dhead 的最前面，代表最近被使用過了，然後從 Hash 串列刪除，然後再將新的節點加入 hhead 中。如此一來則可以完成 LRU Cache 的實作。

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

測驗三

考慮 find_nth_bit 可在指定的記憶體空間找出第 N 個設定的位元。

fns

首先先來看到fns，要如何在一個 unsigned long 的長度的 word 找到第 N 個設定的位元。傳遞的參數有兩個:

word: The word to search
n: Bit to find

首先當然是先檢查這個 word 是不是有效的，再來我們可以透過__ffs來去尋找第一個被設定的位元，然後我們再透過一個 n--的機制就可以找到第 N 個被設定的位置。值得注意的是我們在找到每一個 1 後，需要用__clear_bit將找到的 bit 清除掉，否則他永遠會找到第一個 bit。

static inline unsigned long fns(unsigned long word, unsigned int n)
{
    while (word) {
        unsigned int bit = __ffs(word);
        if (n-- == 0)
            return bit;
        __clear_bit(bit, &word);
    }

    return BITS_PER_LONG;
}

接下來看到 __ffs，這邊就是在尋找一個 word 的第一個被設定的位元，從最低位開始找會有幾個 0。會先從最低的 32 位開始檢查，若成立 num += 32，word 會右移 32 位，再檢查最低的 16 位，一直檢查到 1 位。檢查的方式是透過與 2 的冪位全 1 做且運算，因此 AAAA = 0xffffffff。

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

__clear_bit的共用是將第 nr 位的 bit 設為 0。使用到了兩個巨集BIT_MASK和BIT_WORD，BIT_WORD的用意在於獲取 nr / BITS_PER_LONG的商數，若nr大於BITS_PER_LONG的話，我們就需要使用獲取的商數對addr做偏移，才能取到我們想要的地方。

#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)

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 &= BBBB;
}

舉例來說，我們要操作的函式為 __clear_bit(66, addr)，所以我們要處理的數字應該是010...100000...000，65 個 0。

所以p會存取到下方這張圖的值。

就可以與 ~mask做且運算，如此一來可以精準的清除掉第 66 個位元的 1 而不會動到其他位元的值，因此BBBB = ~mask。

find_nth_bit

對比 fns 只是在一個 word 內尋找，接下來我們要將範圍擴增到 memory region。說明一下傳遞的參數:

addr: The address to start the search at
size: The maximum number of bits to search
n: The number of set bit, which position is needed, counting from 0

首先若要找的 n 大於 size則會直接 return size。然後會根據small_const_nbits(size)來區分成兩種情況，簡單來說small_const_nbits其實就是在判斷 size是不是小於BITS_PER_LONG，如果 size小於BITS_PER_LONG的話會進到 if statement 裡面，首先我們會使用 *addr & GENMASK(size - 1, 0)讓val只在第 0 bit到第sizebit的位元數為原本的值，範圍外的皆為 0。然後就可以使用fns去尋找。

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)

#define GENMASK(h, l) \
    (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

但若是size大於BITS_PER_LONG則會使用另外一個巨集FIND_NTH_BIT處理，裡面使用一個 for loop 處理，一次處理一個 unsigned long 的長度，也可以分做幾種情況:
if (idx * BITS_PER_LONG + nr >= sz) 代表我們要找的目標已經超出 size，所以會跑到 out 的地方，return sz。
if (w > nr) 其中w = hweight_long(tmp)代表我們再tmp總共觀察到了幾個 1，tmp = addr[idx]，因此可以理解為如果觀察到的 1 的數量大於我們要找的 nr的話，代表我們的目標一定在這個區段內，因此可以直接跳到 found，然後利用 fns再加上已經偏移的地址就可以得到 sz。如果w < nr 代表目標不再這個區段，因此nr -= w。

這一段在說的是如果我們的 sz 不能夠被 BITS_PER_LONG 整除的話，代表最後會有剩餘的 bits，因此我們需要將他擴充為 64 bits，所以CCCC = %。

        if (sz CCCC BITS_PER_LONG)                              \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);

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

2024q1 Homework2 (quiz1+2)

第一週題目

測驗一

資料型態

程式說明

使用 Linux 核心風格的 List API 改寫上述程式碼

測驗二

Timsort

程式實作

第二週題目

測驗一

Binary Tree

資料型態

binary tree 實作

測驗二

LRU Cache

單向鏈結串列 for Hash Table

LRU 實作

測驗三

fns

find_nth_bit

Read more

2024q1 Homework5 (assessment)

2024q1 Homework1 (lab0)

2024q1 Homework4 (quiz3+4)