# 2022q1 Homework1 (quiz1)
contributed by < `freshLiver` >
###### tags: `linux2022`
## 第一題 - [LeetCode 1. Two Sum](https://leetcode.com/problems/two-sum/)
### Hash Table
#### 建立雜湊表
```c
/**
* @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;
}
```
#### 節點搜尋
```c
/**
* @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;
}
```
#### 資料獲取
```c
/**
* @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;
}
```
#### 資料儲存
```c
/**
* @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` 是否會成立：
```c=
#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;
}
```
測試結果：
```shell
$ 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`）明顯不同。
:::
#### 清除雜湊表
```c
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
```c
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 兩個結構體：
```c
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`
- 所有重複出現的節點皆要移除，而不是只留下一個使其不重複出現
### 遞迴版
```c=
#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` 應為：
```c
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` 相同，皆為：
```c
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` 即可。
### 迭代版
```c=
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` 變數以簡化程式碼
```c
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 *`。
#### 迭代版
##### 主要函式
```c
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;
}
```
##### 轉成雙向鏈結
```c=
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\>
:::
#### 遞迴版
##### 主要函式
```c
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` 連結。
##### 轉成雙向鏈結
```c
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`。
```c
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 快取
```c
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==)
```c
/**
* @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==)
```c
/**
* @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==)
```c
/**
* @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);
}
```
#### 測試程式
```c
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/)
### 說明
#### 尋找雜湊表中是否包含某數
```c
/**
* @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;
}
```
#### 尋找最長連續數列長度
```c=
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
:::
Sign in with Wallet
Connect another wallet