# 2022q1 Homework1 (quiz1)

contributed by < `freshLiver` >

###### tags: `linux2022`

## 第一題 - [LeetCode 1. Two Sum](https://leetcode.com/problems/two-sum/)

### Hash Table

#### 建立雜湊表

/**
 * @brief 建立並初始化一個有 2^bits 個欄位的雜湊表
 *
 * @param bits
 * @return map_t*
 */
map_t *map_init(int bits)
{
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    if (map->ht) {
        // 成功分配空間給雜湊表，初始化所有欄位
        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}

#### 節點搜尋

/**
 * @brief 從雜湊表中尋找並回傳一節點 kn，且 kn.key == @key
 *
 * 將 @key 經過雜湊函數計算後得到所屬欄位，
 * 接著依序走訪該欄位並檢查目標資料 @key 是否存在於該欄位中，
 * 若有找到則回傳包含該資料的節點，若不存在則回傳 NULL。
 *
 * @param map 目標雜湊表
 * @param key 目標節點的 key
 * @return struct hash_key*
 */
static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

#### 資料獲取

/**
 * @brief 從雜湊表中提取 key 與 @key 相符之節點 kn 的資料 data
 *
 * @param map 目標雜湊表
 * @param key 數列 nums 中的某數 k
 * @return void*
 */
void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

#### 資料儲存

/**
 * @brief 建立一節點 kn 來保存 @key 以及 @data
 *
 * @param map 目標雜湊表
 * @param key 數列 nums 中的某數 k
 * @param data k 在數列 nums 中的 index
 */
void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;  // 所有節點的 key 不應重複

    // 分配空間以及將資料複製到該節點
    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;


    /**
     * @brief 將新增的節點插入到對應欄位的首位
     *
     * 首先透過雜湊函式取得目標欄位的地址 h
     * 以及該欄位的首位節點 first
     * 最後再為 h->next, n, first 重新建立連結
     *
     * - 新的節點 n 需要設定 pprev 以及 next
     *      - n->next 指向原本的首位節點 first
     *      - n->pprev 則指向欄位 h 指向首位節點的結構體地址 &h->first
     *
     * - 欄位 h 應指向新的首位節點 n
     * - 原首位節點 first 的 pprev 改指向新節點 n 的 next 的地址 &n->next
     *
     */
    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;

    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}

:::info
> 我自己的發現是 其實你仔細看 n->next = first
> first->pprev = &n->next 等同於 first -> pprev = & first
> n->pprev = &n
> pprev 在這邊的物理意義等於指向自己位址的指標
> 所以下面的 if (!n->pprev) goto bail;
> 意思是 如果指向自己的指標為 null (即自己為空)
> 那麼就跳至最後面處理
>
> 上述可以在 leetcode代換程式碼發現結果不變 , 但我也不能百分百肯定是不是這樣,因為覺得這樣 pprev 變得很奇怪？
>
> by修課同學 Haoyu

如果我的認知沒錯的話，indirect pointer 應該是用來儲存某個「指標的地址」，而這邊的 `**prev` 就應該是用來儲存「前一個節點的 `next` **指標的地址**」。

但這邊的 `first` 是一個指向下個節點的指標，即使在 `n->next = first` 後，也只是這兩個指標指向相同的地址（儲存的值都是下個節點的地址），若是對 `first` 取址的話應該會得到 `first` 這個區域變數的地址，所以 `&first == &n->next` 應該不會成立。

若在這個認知上去思考 `if (!n->pprev)` 成立的情境的話，應該是代表前一個節點的 `next` 的地址為 `NULL`，或是 `pprev` 被手動指向 `NULL`，但我想不通正常操作下什麼時候會發生這個情況。

而我在 LeetCode 測試時把那行 `if (...) goto ...` 移除後結果也是 Accepted。

> 我的理解是 `**pprev` 變數名稱看起來的確是應該用來儲存「前一個節點的 `next` 指標的地址」
> `first` 指向的是串列的首個節點 `*first = h->first`
> `n->next = first` 就是把 原本串列的首個節點接在 n 這個節點的後面
> `if (first)` 表示串列的首個節點是否存在 , 存在的話
> 將 `first->pprev` 指向 (指向 `n->next` 的位址)
> 而上面才剛修改過 `n-> next` 為 `first`
> 所以 `first -> pprev` 會指向 指向 `first` 的位址
以上為根據程式碼判斷的結論
看起來是我們對於 `first` 的想法不太一樣？
如果我對程式理解有誤 麻煩在幫我指出哪裡有錯誤

首先，我看不太懂你的敘述內容且 `**` 造成 Markdown 格式問題，所以我對你的內文做了些調整。

再來是我實際寫了程式測試了在進行 `new->next = first` 後 `&first == &n->next` 是否會成立：

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

#define print_ptr(p)                             \
    ({                                           \
        printf("%d:Pointer %s\n", __LINE__, #p); \
        printf("\tAddress = %p\n", &p);          \
        printf("\t  Value = %p\n\n", p);         \
    })

#define print_ind_ptr(p)                                  \
    ({                                                    \
        printf("%d:Indirect Pointer %s\n", __LINE__, #p); \
        printf("\tAddress = %p\n", &p);                   \
        printf("\t  Value = %p\n", p);                    \
        printf("\t Target = %p\n\n", *p);                 \
    })


typedef struct NODE {
    struct NODE **pprev, *next;
} hlist_node;
typedef struct HEAD {
    hlist_node *first;
} hlist_head;


int main(int argc, char const *argv[])
{
    hlist_head *head = &(hlist_head){
        .first =
            &(hlist_node){
                .pprev = &head->first,
                .next = NULL,
            },
    };
    hlist_node *first = head->first;
    hlist_node *new = &(hlist_node){.pprev = NULL, .next = NULL};

    print_ptr(head);
    print_ptr(head->first);
    print_ptr(first);
    print_ptr(new);

    new->next = first;
    print_ptr(first);
    print_ptr(new->next);
    if (first) {
        first->pprev = &new->next;
        print_ind_ptr(first->pprev);
    }
    head->first = new;
    new->pprev = &head->first;

    // end
    return 0;
}

測試結果：

$ gcc indirect.c && ./a.out
41:Pointer head
        Address = 0x7ffd4e7ac880
          Value = 0x7ffd4e7ac888

42:Pointer head->first
        Address = 0x7ffd4e7ac888
          Value = 0x7ffd4e7ac8a0

43:Pointer first
        Address = 0x7ffd4e7ac890
          Value = 0x7ffd4e7ac8a0

44:Pointer new
        Address = 0x7ffd4e7ac898
          Value = 0x7ffd4e7ac8b0

47:Pointer first
        Address = 0x7ffd4e7ac890
          Value = 0x7ffd4e7ac8a0

48:Pointer new->next
        Address = 0x7ffd4e7ac8b8
          Value = 0x7ffd4e7ac8a0

51:Indirect Pointer first->pprev
        Address = 0x7ffd4e7ac8a0
          Value = 0x7ffd4e7ac8b8
         Target = 0x7ffd4e7ac8a0

可以看到在 46 行結束後，指標 `first` 指向的地址（變數 `first` 儲存的值）與 `new->next` 指向的地址（變數 `new->next` 的值）相同，但 `first` 的地址（`&first`）與 `new->next` 的地址（`&new->next`）明顯不同。

:::
#### 清除雜湊表

void map_deinit(map_t *map)
{
    if (!map)
        return;

    // 依序檢查雜湊表中的各個欄位
    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
        struct hlist_head *head = &map->ht[i];

        // 依序走訪欄位中所有節點，並釋放它們佔用的資源
        for (struct hlist_node *p = head->first; p;) {
            struct hash_key *kn = container_of(p, struct hash_key, node);

            // n 保存目前節點的地址，p 則移至下一個節點
            struct hlist_node *n = p;
            p = p->next;

            if (!n->pprev) /* unhashed */
                goto bail;

            // 將當前節點 n 移出當前欄位
            struct hlist_node *next = n->next, **pprev = n->pprev;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

            // 釋放節點 n 的資料以及節點本身佔用的資源
        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

:::warning
TODO : `if (!n->pprev) goto bail;` 用途
:::

### 使用雜湊表完成 Two Sum

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    map_t *map = map_init(10);
    *returnSize = 0;


    int *ret = malloc(sizeof(int) * 2);
    if (!ret)
        goto bail;  // 無法分配空間給答案

    /**
     * @brief 利用雜湊表紀錄已看過得數值以及它們的 index
     *
     * 由於目標是要找到 num 與 k 使得 num + k == target
     * 因此檢查到數列 nums 中的數值 num 時
     * 就檢查雜湊表中是否有 key 為 k 的數值存在
     *
     *  Case 1. k 不存在
     *
     *      將 num 作為 key、index 作為 data 新增至雜湊表
     *      若之後遇到另一數 k 時就會因 num 存在而找到解
     *
     *  Case 2. k 存在
     *
     *      代表 k 有在數列 nums 中
     *      因此 k 的節點的資料 *p（代表 k 所在的 index）取出
     *      接著再將 *p 以及當前 index i 作為答案回傳
     *
     */
    for (int i = 0; i < numsSize; i++) {
        // 若雜湊表中有 key 為 k 的節點存在，則 p 不為 NULL
        int *p = map_get(map, target - nums[i]);

        // k 在雜湊表中
        if (p) {
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        // k 不在雜湊表中，將 num (nums[i]) 以及其 index i 加入雜湊表
        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

### Linux 核心 Hash Table 的設計和實作手法

#### `hlist_head` 以及 `hlist_node`

在 [include/linux/types.h](https://github.com/torvalds/linux/blob/master/include/linux/types.h) 中有定義 hlist_head 以及 hlist_node 兩個結構體：

struct hlist_head {
	struct hlist_node *first;
};

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

與 Linux Kernel Linked List API 相比：

- 相似處
- 結構體內都只有定義指向串列節點的指標，應該與 `list_head` 的設計相似，是為了能夠方便擴充。
- 都是用雙向鏈結串列在節點間移動。
- 不同處
- 雜湊表多了 `hlist_head` 作為欄位，而每個欄位都透過 `first` 指向各自的鏈結串列，是透過 Chaining 的方式來處理 Collision。
- 前述的 Chaining List 是**非環狀**的雙向鏈結串列，且 `pprev` 並不是單純指向前一個節點。（使用 indirect pointer 的設計可以參考 [第二週的討論](https://hackmd.io/@sysprog/B1RLIlY19)）
- 雜湊表的欄位數 (`hlist_head` 數量) 在宣告時就決定了（宣告成陣列的形式）。

#### Hash Table 相關實作

`hlist_head` 以及 `hlist_node` 相關基本操作的函式以及巨集則是定義在 [include/linux/hashtable.h](https://github.com/torvalds/linux/blob/master/include/linux/hashtable.h) 以及 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中。

- `DECLARE_HASHTABLE(name, bits)`
- 宣告一個有 $2^{bits}$ 個欄位的雜湊表
- `hash_init(table)`
- 透過 [Designated Initializers](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Designated-Inits.html) 對所有欄位進行初始化。
- `hash_add_head(head, node, key)`
- 新增資料到對應的欄位中
- 也有 `add_before`, `add_behind` 等變化。
- 比較特別的是 `hlist_add_fake` 這個函式，不會新增 `node` 到雜湊表中，只會將 `node->pprev` 指向 `&node->next`。整個 linux 專案[包含定義只出現四次](https://github.com/torvalds/linux/search?q=hlist_add_fake)，不確定實際用途但似乎[與檔案系統有關](https://github.com/torvalds/linux/blob/9f7fb8de5d9bac17b6392a14af40baf555d9129b/include/linux/fs.h#L744)。
- `hash_del(node)`
- 將指定節點從它所在的 Chaining List 中移除。
- 若要 unhash（將 `pprev` 以及 `next` 指向 `NULL`）這個 `node`，則需要使用 `hlist_del_init`。
- `hlist_unhashed(node)`
- 檢查 `node` 是否已被 unhashed。
- `hlist_move_list(new_head, old_head)`
- 用 `old_head` 的 Chaining List 取代 `new_head` 的 Chaining List，並移除 `old_head` 的 `first`。
- `hlist_for_each` 系列巨集
- 與 `list_for_each` 系列相似，用來走訪 Chaining List，也有 entry 以及 safe 版。
- `hlist_for_each_entry_from`
- 從 Chaining List 的指定節點開始走訪剩下的節點，而不是從 `head->first` 開始。
- `hlist_for_each_entry_continue`
- 與 `hlist_for_each_entry_from` 相似，但是從指定節點的**下一個節點**開始繼續走訪。

:::warning
TODO

1. [RCU 是什麼](https://lwn.net/Articles/262464/)
2. `GOLDEN_RATIO_PRIME`
:::

---

## 第二題 - [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

這題的目標是將一個已排序過的 Singly-linked List 中重複的節點移除，需要注意的部份是：

- 串列可能為空或 `NULL`
- 所有重複出現的節點皆要移除，而不是只留下一個使其不重複出現

### 遞迴版

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

在這個程式碼中，可以發現被 `if` 分成了三個部份，且這三個部份的的最後皆以 `return` 結束，分別代表了以下三種情況：

1. 輸入的 `head` 為 `NULL` 時
2. 當 1 不成立且 `COND1` 成立時
3. 非上述兩種情況時

第一個部份是為了處理原串列為 `NULL` 以及遞迴呼叫到串列尾端時的遞迴終止條件。

第二個部份則是為了處理 `head` 與 `head->next` 兩節點資料相同的情況，所以 `COND1` 應該是 `head->val == head->next->val`，但這邊有個陷阱是 `head->next->val` 若是在 `head->next == NULL` 時會出問題，所以必須先檢查 `head->next != NULL`，因此正確的 `COND1` 應為：

head->next && head->val == head->next->val

而進入第二部份的 `if` 之後則是透過 `while` 迴圈跳過所有**連續**重複資料的節點，所以當目前指向的節點 `head` 的資料與其下一個節點 `head->next` 的資料相同時就要跳過目前節點，因此 `COND2` 應該是 `head->val == head->next->val`。同樣的，這邊也有個陷阱是當串列走到尾端時， `head->next` 會是 `NULL`，因此這邊也必須先檢查 `head->next != NULL`，所以正確的 `COND2` 應和 `COND1` 相同，皆為：

head->next && head->val == head->next->val

而在 `while` 迴圈結束後（即 `head->next == NULL || head->val != head->next->val` ），就需要再次透過遞迴呼叫 `deleteDuplicates` 來找到剩餘串列中部重複的節點，但由於 `head` 也是重複的節點，所以傳入 `deleteDuplicates` 的參數應為 `head->next` 才對。

而最後的第三部份則因為 `COND1` 確保了 `head` 的資料不與其他節點重複，所以只需要透過 `deleteDuplicates` 找出 `head->next` 要接到哪個節點，最後再回傳 `head` 即可。

### 迭代版

struct ListNode* deleteDuplicates(struct ListNode* head){
    
    if (!head)
        return NULL;
    
    bool found = false;
    for (struct ListNode **ptr = &head; *ptr;) {    
        
        // same val
        if ((*ptr)->next && (*ptr)->val == (*ptr)->next->val) {
            *ptr = (*ptr)->next;
            found = true;
        }
        else {
            // don't forget to rm last repeated node
            if (found)
                *ptr = (*ptr)->next;
            else
                ptr = &(*ptr)->next;
            found = false;
        }
    }
    return head;
}

這個迭代的實作參考了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)中提到的**有品味的**移除節點的操作，使用了 `ListNode` 的指標的指標來避免額外判斷當前節點是否為 `head`。

#### 增加一個 `bool` 變數以簡化程式碼

struct ListNode* deleteDuplicates(struct ListNode* head){
    
    if (!head)
        return NULL;
    
    bool prev = false, found = false;
    for (struct ListNode **ptr = &head; *ptr; prev = found) {    
        
        found = (*ptr)->next && (*ptr)->val == (*ptr)->next->val;
        
        if (found || prev)
            *ptr = (*ptr)->next;
        else 
            ptr = &(*ptr)->next;
    }
    return head;
}

透過分別使用 `prev` 以及 `found` 來紀錄上一個節點以及目前節點的比較結果，這能讓原本程式碼中第 16 行的 `if` 與第 10 行的 `if` 合併。

### Circular Doubly-linked List 版

與 lab0-c 中要實作的 function `q_delete_dup` 相似，但可以不用刪除節點資料，且儲存的資料型態為 `int` 而不是 `char *`。

#### 迭代版

##### 主要函式

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;

    LIST_HEAD(duplist);

    bool prev = false;
    element_t *ptr = list_entry(head->next, element_t, list), *next = ptr;

    for (bool same; next->list.next != head; ptr = next) {
        next = list_entry(ptr->list.next, element_t, list);
        same = ptr->value == next->value;
        if (same || prev)
            list_move(&ptr->list, &duplist);
        prev = same;
    }

    // don't forget last node
    if (prev)
        list_move(&ptr->list, &duplist);

    return true;
}

##### 轉成雙向鏈結

typedef struct ListNode Node;

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    // build doubly-linked list
    struct list_head doubly;
    INIT_LIST_HEAD(&doubly);

    for (Node *ptr = head; ptr; ptr = ptr->next) {
        element_t *e = malloc(sizeof(element_t));
        e->value = ptr->val;
        e->list.next = NULL;

        list_add_tail(&e->list, &doubly);
    }

    q_delete_dup(&doubly);

    // back to singly
    Node *new = NULL, **pnew = &new;

    element_t *ptr;
    list_for_each_entry (ptr, &doubly, list) {
        Node *n = malloc(sizeof(Node));
        n->val = ptr->value;
        n->next = NULL;

        *pnew = n;
        pnew = &(*pnew)->next;
    }

    return new;
}

:::danger
如果第 23 行的 `*new` 不初始化成 `NULL` 的話，可能在 `doubly` 的元素皆被移除時（例如輸入串列為 `[1,1]` 時）跳出以下錯誤：

> Line 70: Char 15: runtime error: member access within misaligned address 0x000041b58ab3 for type 'struct ListNode', which requires 8 byte alignment [ListNode.c]
0x000041b58ab3: note: pointer points here
\<memory cannot be printed\>
:::

#### 遞迴版

##### 主要函式

typedef struct ListNode Node;

#define assign_and_cmp(ptr, next, p_ptr_entry, p_next_entry) \
    ({                                                       \
        p_ptr_entry = list_entry(ptr, element_t, list);      \
        p_next_entry = list_entry(next, element_t, list);    \
        p_ptr_entry->value == p_next_entry->value;           \
    })

struct list_head *q_delete_dup(struct list_head *head)
{
    if (!head)
        return NULL;

    element_t *ptr, *next;
    if (head->next && assign_and_cmp(head, head->next, ptr, next)) {
        while (head->next && assign_and_cmp(head, head->next, ptr, next))
            head = head->next;
        return q_delete_dup(head->next);
    }

    head->next = q_delete_dup(head->next);
    if (head->next)
        head->next->prev = head;
    return head;
}

把 `list_head` 當作 Singly-linked List 操作，並透過定義巨集讓函式能直接沿用 Singly-linked List 的遞迴函式的結構，只需要額外宣告變數來存取 `element_t` 的資訊，以及要額外處理 `prev` 連結。

##### 轉成雙向鏈結

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    // build doubly-linked list
    struct list_head doubly;
    INIT_LIST_HEAD(&doubly);

    for (Node *ptr = head; ptr; ptr = ptr->next) {
        element_t *e = malloc(sizeof(element_t));
        e->value = ptr->val;
        e->list.next = NULL;

        list_add_tail(&e->list, &doubly);
    }

    // break circular
    doubly.prev->next = NULL;

    // head do not contain data, start from first node
    doubly.next = q_delete_dup(doubly.next);
    if (doubly.next)
        doubly.next->prev = &doubly;

    // make circular
    struct list_head *ptr;
    for (ptr = &doubly; ptr->next; ptr = ptr->next)
        ;
    ptr->next = &doubly;
    doubly.prev = ptr;

    // back to singly
    Node *new = NULL, **pnew = &new;

    list_for_each (ptr, &doubly) {
        element_t *entry = list_entry(ptr, element_t, list);
        Node *n = malloc(sizeof(Node));
        n->val = entry->value;
        n->next = NULL;

        *pnew = n;
        pnew = &(*pnew)->next;
    }

    return new;
}

大致上與迭代版本的相同，但差在由於這邊的遞迴版是沿用單向的遞迴的函式，因此在檢查條件時也是沿用 `!head` 以及 `head->next` ，所以這邊要先把最後一個節點的 `next` 指向 `NULL`，讓串列變成**非環狀**串列，並以首位節點作為開頭進行 `q_delete_dup`，然後在結束時還需要讓串列變回環狀。

#### 測試函式

由於 `deleteDuplicates` 是有被規定的，因此不論是遞迴還是迭代版都可以用相同函式測試 `deleteDuplicates`。

int main(int argc, char const *argv[])
{
    Node *head, **phead = &head;

    int vals[] = {1, 1};

    for (int i = 0; i < (sizeof(vals) / sizeof(vals[0])); ++i) {
        Node *n = malloc(sizeof(Node));
        n->val = vals[i];
        n->next = NULL;

        *phead = n;
        phead = &(*phead)->next;
    }

    deleteDuplicates(head);
    return 0;
}

---

## 第三題 - [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/)

### 說明

#### 建立 LRU 快取

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache;

    // 利用 GNU C Extension 建立可變大小的 LRUCache 結構體物件
    // REF : https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
    cache = malloc(sizeof(LRUCache) + capacity * sizeof(struct list_head));
    cache->capacity = capacity;
    cache->count = 0;

    // 初始化 dhead 以及雜湊表
    INIT_LIST_HEAD(&cache->dhead);
    for (int i = 0; i < capacity; ++i)
        INIT_LIST_HEAD(&cache->hheads[i]);
    return cache;
}

#### 新增資料 (==MMM3==, ==MMM4==)

/**
 * @brief 新增一資料 (key,value) 到快取中
 *
 * TRICK :
 *  新增的資料並非放到原 LRU 節點所在的欄位
 *  實際上與雜湊表概念相同
 *  是將資料放在第 HASH(key) 個欄位
 *  而實際的 Cache 存取紀錄則是由 LRUCache 的 dhead 管理
 *  透過使用雜湊表 hhead 搭配「額外的」環狀雙向鏈結串列 dhead
 *
 *  - 新增資料：
 *      - 加入（資料不存在，Cache 未滿）：
 *          1. 計算 HASH(key) 並將資料加入雜湊表
 *          2. 將該節點加入到 dhead 串列
 *
 *      - 取代（資料不存在，Cache 已滿）：
 *          1. 將 LRU 從 hhead 中移除
 *          2. 將 LRU 從 dhead 中移除
 *          3. 計算 HASH(key) 並將新資料加到雜湊表
 *          4. 將新資料的節點加到 dhead 串列
 *
 *      - 更新（資料存在）：
 *          1. 從雜湊表中尋找該資料的節點
 *          2. 將該節點提昇至 dhead 首位（移除再加入）
 *
 *  - 取得資料：
 *      1. 從雜湊表中尋找該資料的節點
 *      2. 若有找到該資料則將該節點提昇至 dhead 首位
 *      3. 回傳節點
 *
 * @param cache LRUCache 物件的地址
 * @param key 欲新增資料的 key
 * @param value 欲新增資料的 value
 */
void lRUCachePut(LRUCache *cache, int key, int value)
{
    int hash = HASH(key, cache);
    LRUNode *node, *next;

    // MMM3, 只是 move 不需要使用到 safe
    list_for_each_entry (node, &cache->hheads[hash], hlink) {
        if (node->key == key) {
            // 更新該 key 的 value
            node->value = value;
            // 提昇至 dhead 首位
            list_move(&node->dlink, &cache->dhead);
            return;
        }
    }

    // 未滿，直接新增節點
    if (cache->count < cache->capacity) {
        node = malloc(sizeof(LRUNode));
        ++cache->count;
    }

    // 已滿，移除 dhead 中的 LRU
    else {
        // MMM4
        node = list_last_entry(&cache->dhead, LRUNode, dlink);
        list_del(&node->dlink);
        list_del(&node->hlink);
    }

    // 分別將資料加入到雜湊表以及 dhead
    node->key = key;
    node->value = value;
    list_add(&node->dlink, &cache->dhead);
    list_add(&node->hlink, &cache->hheads[hash]);
}

:::danger

**MMM4** 的部份可能是答案錯了，能夠賦值的巨集應該是 `list_entry`, `list_first_entry` 或是 `list_last_entry`，而這邊因為是要獲取 LRU 所以要找的節點應該是 `dhead->prev`，所以答案應為 `list_last_entry` 才正確。

:::

#### 取得資料 (==MMM2==)

/**
 * @brief 從 LRU Cache 取得資料
 *
 * 透過 HASH(key) 計算出雜湊表的欄位索引
 * 接著到該欄位尋找目標的 key
 * 而不是走訪 dhead 中所有節點尋找 key
 *
 * @param cache
 * @param key
 * @return int
 */
int lRUCacheGet(LRUCache *cache, int key)
{
    LRUNode *node;
    // MMM2
    list_for_each_entry (node, &cache->hheads[HASH(key, cache)], hlink)
        if (node->key == key) {
            list_move(&node->dlink, &cache->dhead);
            return node->value;
        }
    return -1;
}

#### 清除快取 (==MMM1==)

/**
 * @brief 清除 LRU Cache
 *
 * 雖然快取紀錄是由 dhead 管理
 * 但 LRUNode 同時包含 dlink 以及 hlink
 * 分別用來指向 dhead 及 hhead 的前後節點
 * 因此實際上 dhead 中的節點與 hhead 中的節點相同
 * 只須刪除一邊的節點即可
 *
 * @param cache
 */
void lRUCacheFree(LRUCache *cache)
{
    LRUNode *node, *next;
    // MMM 1
    list_for_each_entry_safe (node, next, &cache->dhead, dlink) {
        list_del(&node->dlink);
        free(node);
    }
    free(cache);
}

#### 測試程式

static inline void GET_AND_SHOW(LRUCache *cache, int key)
{
    int value = lRUCacheGet(cache, key);
    printf("GET (%d,%d)\n", key, value);
}

int main(int argc, char const *argv[])
{
    LRUCache *cache = lRUCacheCreate(2);

    lRUCachePut(cache, 1, 1);
    lRUCachePut(cache, 1, 1);

    GET_AND_SHOW(cache, 1);
    lRUCachePut(cache, 3, 3);
    GET_AND_SHOW(cache, 2);
    lRUCachePut(cache, 4, 4);
    GET_AND_SHOW(cache, 1);
    GET_AND_SHOW(cache, 3);
    GET_AND_SHOW(cache, 4);

    lRUCacheFree(cache);
    return 0;
}

### 可改進部份

:::warning
TODO
:::

### 探討 Linux 核心中 LRU 相關程式碼

---

## 第四題 - [LeetCode 128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)

### 說明

#### 尋找雜湊表中是否包含某數

/**
 * @brief 找出雜湊表中包含某個數值的節點
 *
 * 會先對 @num 取絕對值並計算出該數所屬的欄位
 * 接著在走訪該欄位、檢查是否包含此數
 *
 * @param num 目標數值
 * @param size 雜湊表大小（有幾個欄位）
 * @param heads 雜湊表
 * @return struct seq_node*
 */
static struct seq_node *find(int num, int size, struct list_head *heads)
{
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

#### 尋找最長連續數列長度

int longestConsecutive(int *nums, int n_size)
{
    // 建立並初始化雜湊表
    struct list_head *heads = malloc(n_size * sizeof(*heads));
    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    // 將每個數字放入雜湊表
    struct seq_node *node;
    for (int i = 0, hash; i < n_size; i++) {
        // 跳過重複數字
        if (!find(nums[i], n_size, heads)) {
            // 使用 modulo 作為雜湊函數，將數字取絕對值計算後放入雜湊表
            hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
            node = malloc(sizeof(*node));
            node->num = nums[i];
            list_add(&node->link, &heads[hash]);
        }
    }

    int global = 0;
    for (int i = 0, num; i < n_size; i++) {
        /**
         * @brief 尋找最長的連續數列 (global 代表目前找到最長的數列長度)
         *
         * Step 1. 檢查當前數字是否在雜湊表中
         *
         *      Y : 跳至 Step 2
         *      N : 跳至 Step 4
         *
         * Step 2. 開始尋找包含此數(num)的連續數列 (local 代表此連續數列長度)
         *
         *      2-1 : 將此數移出雜湊表並將 local + 1
         *
         *      2-2 : 從 num 開始向下尋找最多有幾個相鄰整數 (k>0)
         *
         *        2-2-1 : 尋找雜湊表中是否包含 num-k
         *            Y : ++local, ++k, 將 num-k 從雜湊表中移除
         *            N : 結束此迴圈
         *
         *      2-3 : 類似 2-2，但是從 num+1 往上找
         *
         * Step 3. 如果 local 較大的話就更新 global
         *
         * Step 4. 如果尚未檢查到最後一個數字的話就回到 Step 1
         *
         * TRICK :
         *  由於雜湊表不包含重複數字且在 Step 2 找連續數字時會將找到的數字移除
         *  所以即使 nums 中包含連續或重複數字也只有第一次遇到時會進入第二個迴圈
         *  之後遇到該群連續數列時就只需要檢查雜湊表是否包含該數而已
         *  因此運作起來會像是在計算每群連續數列的長度
         */

        int local = 0;

        if (node = find(nums[i], n_size, heads)) {
            local++;
            num = node->num;
            list_del(&node->link);

            // 從 num-1 向下，因 num 已取出且每次找到應將 left 遞減，故 --left
            for (int left = num; (node = find(--left, n_size, heads));) {
                local++;
                list_del(&node->link);
            }

            // 從 num+1 向上，因 num 已取出且每次找到應將 right 遞增，故 ++right
            for (int right = num; (node = find(++right, n_size, heads));) {
                local++;
                list_del(&node->link);
            }

            global = local > global ? local : global;
        }
    }
    return global;
}

#### 測試程式

:::warning
TODO
:::

### 可改進部份

#### `while(node)` 可改用 `if`

第 56 列的 `if` 原本是 `while(node)`，但是在第 68 列的迴圈結束條件為 `node` 被賦予 `NULL` 時，因此實際上 `while` 只會執行一次，可用 `if` 替代。

#### `while` 迴圈可改用 `for` 迴圈使程式碼更精簡

`left` 與 `right` 只會分別在各自的 `while` 迴圈中使用到，因此可利用 `for` 迴圈進行宣告，使得程式碼更加簡短並縮短 `left` 以及 `right` 的生命週期。

#### `len` 以及 `length` 兩變數名稱有相近含意

原先的 `len` 是用來表示 `Step 2` 中找到的連續數列的長度，而 `length` 則是代表目前找到的最長連續數列的長度，兩個變數名稱相近可能會造成混淆，因此將 `length` 以及 `len` 分別以 `global` 以及 `local` 進行替換。

### Linux 核心風格的 hash table 重新實作

:::warning
TODO
:::