# 2022q1 Homework1 (quiz1)
contributed by < [`chengingx`](https://github.com/chengingx) >
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1)
>
###### tags: `linux2022`
## 測驗 1
LeetCode 編號 1 的題目 [Two Sum](https://leetcode.com/problems/two-sum/) 引入 [hash table](https://en.wikipedia.org/wiki/Hash_table) 實作，並以 Linux 核心程式碼風格呈現
```c
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
AAA;
if (first)
first->pprev = &n->next;
h->first = n;
BBB;
}
```
AAA = n->next = first
BBB = n->pprev = &h->first
:::info
- [X] 解釋上述程式碼運作原理
- [ ] 研讀 Linux 核心原始程式碼
:::
### 運作原理
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
map[label = "map|{bits|<h>ht}"]
ht[label = "Hash table|<m1>hlist_head first[0]|<m2>hlist_head first[1]|...|hlist_head first[n-1]|<mn>hlist_head first[n]"]
f2_hk_1[label = "hash_key | key | data | <m>hlist_node | {<p>pprev | <n>next}"]
f2_hk_2[label = "hash_key | key | data | <m>hlist_node | {<p>pprev | <n>next}"]
f2_hk_3[label = "hash_key | key | data | <m>hlist_node | {<p>pprev | <n>next}"]
fn_hk_1[label = "hash_key | key | data | <m>hlist_node | {<p>pprev | <n>next}"]
fn_hk_2[label = "hash_key | key | data | <m>hlist_node | {<p>pprev | <n>next}"]
NULL_1[shape = plaintext, label = "NULL"]
NULL_2[shape = plaintext, label = "NULL"]
map:h -> ht:m1
ht:m2 -> f2_hk_1:m
f2_hk_1:p -> ht:m2
f2_hk_1:n -> f2_hk_2:m
f2_hk_2:p -> f2_hk_1:n
f2_hk_2:n -> f2_hk_3:m
f2_hk_3:p -> f2_hk_2:n
f2_hk_3:n -> NULL_1
ht:mn -> fn_hk_1:m
fn_hk_1:p -> ht:mn
fn_hk_1:n -> fn_hk_2:m
fn_hk_2:p -> fn_hk_1:n
fn_hk_2:n -> NULL_2
}
```
首先研究構成 hash table 的資料結構 `hlist_node`, `hlist_head`, `map_t`, `hash_key`
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
struct hlist_head {
struct hlist_node *first; // 用來指向 hlist_node 的指標
};
typedef struct {
int bits;
struct hlist_head *ht;
} map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
首先會呼叫到 `map_init` 並由 `bits` 決定 hash table 大小，大小為 $2^{bits}$
```c
#define MAP_HASH_SIZE(bits) (1 << bits)
```
#### map_t *map_init(int bits)
```c
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;
}
```
大小為 $n$ 且 $n = 2^{bits}$
```graphviz
digraph G {
rankdir = LR
node[shape = "record"]
map[label = "{map | {bits | <h>ht}}"]
hash_table[label = " <f0>first[0] | <f1>first[1] | ... | <fn-2>first[n-2]| <fn-1>first[n-1]"]
NULL_1[shape = plaintext, label = "NULL"]
NULL_2[shape = plaintext, label = "NULL"]
NULL_3[shape = plaintext, label = "NULL"]
NULL_4[shape = plaintext, label = "NULL"]
map:<h> -> hash_table:<f0>
hash_table:<f0>->NULL_1
hash_table:<f1>->NULL_2
hash_table:<fn-2>->NULL_3
hash_table:<fn-1>->NULL_4
}
```
有了 `map_t` 之後，透過 `map_get` 看看我要的 `key` 是否在 hash table 中，而這個數據是儲存在 `hash_key`
```c
int *p = map_get(map, target - nums[i]);
```
倘若不在，表示 `p` 是 `NULL`，透過 `map_add` 加入到 `hash table` 中
```c
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
```
#### void map_add(map_t *map, int key, void *data)
首先透過 `find_key` 尋找 `key` 值
```c
struct hash_key *kn = find_key(map, key);
```
找到 `hash_key` 後，將 `nums[i]` 的值與對應的 index 值 `i` assign 到 `kn` 中
```c
kn->key = key, kn->data = data;
```
透過 `hash` 函式得到 hash 值就可以決定要第幾個 `ht`
```c
struct hlist_head *h = &map->ht[hash(key, map->bits)];
```
接著將 `kn` 中 `node` 的位址 assign 給 `n`
```c
struct hlist_node *n = &kn->node, *first = h->first;
```
將 `first` assign 給 `n` 的 `next`
```c
n->next = first
```
```graphviz
digraph G {
rankdir = LR
node[shape = "record"]
kn[label = "{New node | {key | data | {<n>node | <p>pprev | <ne>next}}}"]
kn_old[label = "{Old node | {key | data | {<n>node | <p>pprev | <ne>next}}}"]
h[shape = plaintext, label = "h"]
n[shape = plaintext, label = "n"]
NULL[shape = plaintext, label = "NULL"]
n->kn:<n>[color=red]
map[label = "{map | {bits | <h>ht}}"]
hash_table[label = " {Hash table | {<f0>first[0] | <f1>first[1] | ... | <fn-2>first[n-2]| <fn-1>first[n-1]}}}"]
map:<h> -> hash_table:<f0>
first[shape = plaintext, label = "first"]
first->kn_old:<n>[arrowhead=none, color=red]
h->hash_table:<f1>[color=red]
kn:<ne>->kn_old:<n>
hash_table:<f1>->kn_old:<n>
kn_old:<ne>->NULL
}
```
若 `first` 不為 `NULL`，`n->next` 的位址 assign 給 `first` 的 `pprev`
```c
if (first)
first->pprev = &n->next;
```
```graphviz
digraph G {
rankdir = LR
node[shape = "record"]
kn[label = "{New node | {key | data | {<n>node | <p>pprev | <ne>next}}}"]
kn_old[label = "{Old node | {key | data | {<n>node | <p>pprev | <ne>next}}}"]
h[shape = plaintext, label = "h"]
n[shape = plaintext, label = "n"]
NULL[shape = plaintext, label = "NULL"]
n->kn:<n>[color=red]
map[label = "{map | {bits | <h>ht}}"]
hash_table[label = "{Hash table | {<f0>first[0] | <f1>first[1] | ... | <fn-2>first[n-2]| <fn-1>first[n-1]}}"]
map:<h> -> hash_table:<f0>
first[shape = plaintext, label = "first"]
first->kn_old:<n>[arrowhead=none, color=red]
h->hash_table:<f1>[color=red]
kn:<ne>->kn_old:<n>
hash_table:<f1>->kn_old:<n>
kn_old:<ne>->NULL
kn_old:<p>->kn:<ne>
}
```
接著將 `n` assign 給 `h->first`
```graphviz
digraph G {
rankdir = LR
node[shape = "record"]
kn[label = "{New node | {key | data | {<n>node | <p>pprev | <ne>next}}}"]
kn_old[label = "{Old node | {key | data | {<n>node | <p>pprev | <ne>next}}}"]
h[shape = plaintext, label = "h"]
n[shape = plaintext, label = "n"]
NULL[shape = plaintext, label = "NULL"]
n->kn:<n>[color=red]
map[label = "{map | {bits | <h>ht}}"]
hash_table[label = " <f0>first[0] | <f1>first[1] | ... | <fn-2>first[n-2]| <fn-1>first[n-1]"]
map:<h> -> hash_table:<f0>
first[shape = plaintext, label = "first"]
first->kn_old:<n>[arrowhead=none, color=red]
h->hash_table:<f1>[color=red]
kn:<ne>->kn_old:<n>
hash_table:<f1>->kn:<n>
kn_old:<ne>->NULL
kn_old:<p>->kn:<ne>
kn:<p>->hash_table:<f1>
}
```
最後將 `h->first` 位址 assign 給 `n->pprev`
```c
n->pprev = &h->first
```
```graphviz
digraph G {
rankdir = LR
node[shape = "record"]
kn[label = "{New node | {key | data | {<n>node | <p>pprev | <ne>next}}}"]
kn_old[label = "{Old node | {key | data | {<n>node | <p>pprev | <ne>next}}}"]
h[shape = plaintext, label = "h"]
n[shape = plaintext, label = "n"]
NULL[shape = plaintext, label = "NULL"]
n->kn:<n>[color=red]
map[label = "{map | {bits | <h>ht}}"]
hash_table[label = " <f0>first[0] | <f1>first[1] | ... | <fn-2>first[n-2]| <fn-1>first[n-1]"]
map:<h> -> hash_table:<f0>
first[shape = plaintext, label = "first"]
first->kn_old:<n>[arrowhead=none, color=red]
h->hash_table:<f1>[color=red]
kn:<ne>->kn_old:<n>
hash_table:<f1>->kn:<n>
kn_old:<ne>->NULL
kn_old:<p>->kn:<ne>
kn:<p>->hash_table:<f1>
}
```
#### static struct hash_key *find_key
為尋找 `key` 是否在 `hash table` 中，需要透過 `hash` 函式求得 hash 值，並找到相對應的入口
```c
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
```
`hash` 函式可以在 [linux/hash.h](https://github.com/torvalds/linux/blob/fa2e1ba3e9e39072fa7a6a9d11ac432c505b4ac7/tools/include/linux/hash.h) 中看見
```c
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
:::info
**#define GOLDEN_RATIO_32 0x61C88647 ?**
來源 [What is the meaning of 0x61C88647](https://stackoverflow.com/questions/38994306/what-is-the-meaning-of-0x61c88647-constant-in-threadlocal-java)
0x61C88647 = 1,640,531,527
2,654,435,769 = -1640531527 (signed)
2,654,435,769 =$\dfrac{2^{32}}{\phi}$
其中 $\phi = \dfrac{\sqrt{5}+1}{2}$ 為黃金比例
val * GOLDEN_RATIO_32 可以保證產生出來的 hash 值均勻分佈在 2 的冪上
:::
接著尋訪找到對應的 `key`
```c
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;
}
```
#### void *map_get(map_t *map, int key)
```c
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
```
如果有找到對應的 `key`，就回傳 `data`，也就是其 index 值
#### void map_deinit(map_t *map)
為刪除整個 hash table，對每個 `hlist_head` 進行 traverse
```c
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;) {
...
}
}
```
接著將 `hlist_node` 所對應的 `hash_key` 找出來並 assign 給 `kn`，並把 `p` assign 給 `n`，而 `p` 則走到下一個 `hlist_node`
```c
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next
```
如果 `n->pprev` 不為 `NULL`，`goto bail`，將 `kn` 中的 `data` 與 自己消除
```c
if (!n->pprev) /* unhashed */
goto bail;
bail:
free(kn->data);
free(kn);
```
最後將 `pprev` dereferenced 也就是前一個 node 的 `next`，指向下一個 `n->next`，當 `next` 不為空，也就是下一個也是 node，將其 `pprev` 以此時的 node 的 `pprev`，接著將此時 node 的 `pprev` 與 `next` 指向 `NULL`
```c
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
```
## 測驗 2
[LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
```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;
}
```
由程式碼可以看見需滿足 COND1 才會進入 `/* Remove all duplicate numbers */` 區塊，否則 再次呼叫 `deleteDuplicates(head->next)` assign 給 `head->next`，這時候就能看得出來該如何拆分大問題成小問題
COND1 = head->next && head->val == head->next->val
COND2 = head->next && head->val == head->next->val
:::info
延伸題目
- [X] 嘗試避免遞迴，寫出同樣作用的程式碼
- [ ] 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼
:::
### 迭代版本
與 [Remove Duplicates from Sorted List I](https://leetcode.com/problems/remove-duplicates-from-sorted-list/submissions/) 概念類似，以 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 中提到移除 linked list 的 node 有「品味」的版本概念著手可以寫成以下程式碼
> delete all duplicates such that each element appears only once
```c
struct ListNode* deleteDuplicates(struct ListNode* head){
if (!head)
return NULL;
struct ListNode **ptr = &head;
while (*ptr){
if ((*ptr)->next && (*ptr)->val == (*ptr)->next->val){
*ptr = (*ptr)->next;
} else {
ptr = &((*ptr)->next);
}
}
return head;
}
```
[Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 差別只是在於相同 `val` 的 node 都要刪掉
> delete all nodes that have duplicate numbers
```c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
struct ListNode **ptr = &head;
bool invalid = false;
bool duplicate = false;
while (*ptr){
duplicate = (*ptr)->next && (*ptr)->val == (*ptr)->next->val;
if (duplicate || invalid){
*ptr = (*ptr)->next;
} else {
ptr = &((*ptr)->next);
}
invalid = duplicate;
}
return head;
}
```
圖解如下
### 類似 Linux 核心版本
#### 迭代版本
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
element_t *slow = NULL, *fast = NULL;
bool duplicate = false;
bool invalid = false;
list_for_each_entry_safe (slow, fast, head, list) {
duplicate = slow->list.next != head && (slow->val == fast->val);
if (duplicate || invalid) {
list_del(&slow->list);
}
invalid = duplicate;
}
return true;
}
```
測試程式
```c
int main(){
struct list_head *head = q_new();
int arr[7] = {1, 2, 2, 2, 5, 7, 7};
for (int i = 0; i < 7; i++){
if (!q_insert_tail(head, arr[i]))
break;
}
q_delete_dup(head);
element_t *ptr = NULL;
list_for_each_entry (ptr, head, list)
printf("%d, ", ptr->val);
q_free(head);
return 0;
}
```
## 測驗 3
[LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/)
* LRUCache(int capacity)
* Initialize the LRU cache with positive size capacity.
* int get(int key)
* Return the value of the key if the key exists, otherwise return -1.
* void put(int key, int value)
* Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
* 原本就存在：覆蓋並取代
* 原本不存在：新增
* Cache 沒滿：新增在空格 (key = -1 處)
* Cache 已滿：取代 priority 最小的
### Naive 版本
參考 [【C 語言的 LeetCode 30 天挑戰】第二十四天 (LRU Cache)](https://www.youtube.com/watch?v=0VgqZTtkINY&t=2610s) 實作可以通過 Leetcode 的版本
定義一個 `LRUCache` 內含 `capacity`、`currentPriority` (用於紀錄現在的 priority 值)，與 `Node`，`Node` 含有 `key`、`value`、`priority`，`priority` 越大代表越新
```c
typedef struct {
int key;
int value;
int priority;
} Node;
typedef struct {
Node *nodes;
int capacity;
int currentPriority;
} LRUCache;
```
`lRUCacheCreate` 根據 `capacity` 創建，並將初始 `key` 為 `1`，為空的位子，`currentPriority` 可能會 overflow，因為是無腦加
```c
LRUCache *lRUCacheCreate(int capacity) {
LRUCache *obj = malloc(sizeof(LRUCache) * capacity);
obj->nodes = malloc(sizeof(Node) * capacity);
obj->capacity = capacity;
obj->currentPriority = 0;
for (int i = 0; i < capacity; i++) {
obj->nodes[i].key = -1;
}
return obj;
}
```
`lRUCacheGet` 主要掃過一遍，有 Get 到就需要設定新的 `priority`，並回傳查到的 `value`
```c
int lRUCacheGet(LRUCache *obj, int key) {
for (int i = 0; i < obj->capacity; i++) {
if (obj->nodes[i].key == key){
obj->currentPriority++;
obj->nodes[i].priority = obj->currentPriority;
return obj->nodes[i].value;
}
}
return -1;
}
```
`lRUCachePut` 分成兩種情況，覆蓋 (相同 `key` 值)、新增，而新增要看是新增在空格處 (`key = -1`)，或是 `priority` 最低者
```c
void lRUCachePut(LRUCache *obj, int key, int value) {
// 原本就有: 覆蓋並取代
for (int i = 0; i < obj->capacity; i++) {
if (obj->nodes[i].key == key) {
obj->nodes[i].value = value;
obj->currentPriority++;
obj->nodes[i].priority = obj->currentPriority;
}
}
// 原本沒有: 新增
// 還沒滿: 新增在空格 (key: -1)
for (int i = 0; i < obj->capacity; i++){
if (obj->nodes[i].key == -1) {
obj->nodes[i].key = key;
obj->nodes[i].value = value;
obj->currentPriority++;
obj->nodes[i].priority = obj->currentPriority;
return;
}
}
// 已經滿: 替換掉 priority 最小的做取代
int minIndex = 0;
for (int i = 1; i < obj->capacity; i++){
if (obj->nodes[i].priority < obj->nodes[minIndex].priority){
minIndex = i;
}
}
obj->nodes[minIndex].key = key;
obj->nodes[minIndex].value = value;
obj->currentPriority++;
obj->nodes[minIndex].priority = obj->currentPriority;
}
```
最後 `lRUCacheFree` 釋放記憶體
```c
void lRUCacheFree(LRUCache *obj) {
free(obj->nodes);
free(obj);
}
```
整理 Naive 版本可以改善的地方
* nodes 使用 queue 版本
* 查詢 key 的方式使用 hash table
* currentPriority 考慮 overflow 問題
### 類似 Linux 核心版本
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
* capacity : LRUCache 的容量，`hheads[]` 的 entry 數
* count : 紀錄 `dlink` 的個數，也就是 `dhead` 連了多少 `LRUNode`
* **dhead** : 連接的第一個代表最新的，尾巴則為最舊
* **dlink** : 用來接 dhead 的 link
* **hheads** : hash table 的 head
* **hlink** : 用來接 hash table 的 link
其中 `hheads[]` 採用了 [Arrays of Length Zero](https://web.mit.edu/rhel-doc/3/rhel-gcc-en-3/zero-length.html) 設計，無須定義總數有多少，待會可以看見 `LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));`，用 `capacity * sizeof(struct list_head)` 的方式決定 hash table 有多少 entry
引用 [jim12312321](https://hackmd.io/CeecUbUaTXWN2TlKAU9TCw?both) 的圖，因為畫得很容易懂，值得注意的是這裡省略了 `pprev`，因為是 doubly circular linked list
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
cache[label="{LRUCache|{capacity = 2|count|<d>dhead|<h0>hheads[0]|<h1>hheads[1]}}"]
node_1[label="{LRUNode1|{key|value|<d>dlink|<h>hlink}}"]
node_2[label="{LRUNode2|{key|value|<d>dlink|<h>hlink}}"]
cache->node_1->node_2[weight = 10, style = invis];
cache:d -> node_1:d:w[color="blue"];
cache:h0 -> node_1:h:w;
node_1:d -> node_2:d:w[color="blue"];
cache:h1 -> node_2:h:w;
}
```
`lRUCacheCreate` 用於建立 `LRUCache`，`INIT_LIST_HEAD (struct list_head *head)` 可以初始化 `head`
```c
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
obj->count = 0;
obj->capacity = capacity;
INIT_LIST_HEAD(&obj->dhead);
for (int i = 0; i < capacity; i++)
INIT_LIST_HEAD(&obj->hheads[i]);
return obj;
}
```
`lRUCacheFree` 用於釋放記憶體，而我們要安全的 remove `struct list head`，必須使用 `list_for_each_entry_safe(entry, safe, head, member)`，`n` 就是用來記錄下一個 node 的 (`safe`)
```c
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
> MMM1 = list_for_each_entry_safe
`lRUCacheGet` 根據 `hash` 找尋入口處，很直覺需要使用 `list_for_each_entry`，因為沒有要斷開連結 (我指的是 `hlink`)，不需 safe 版本，當我們有使用到它，就透過 `list_move` 將其 `dlink` 移動到 `dhead` 的第一個，沒有找到返回 `-1`
```c
int lRUCacheGet(LRUCache *obj, int key)
{
LRUNode *lru;
int hash = key % obj->capacity;
MMM2 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
return lru->value;
}
}
return -1;
}
```
> MMM2 = list_for_each_entry
重頭戲在 `lRUCachePut`，
```c
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *lru;
int hash = key % obj->capacity;
// 原本就有: 覆蓋 (key 相同的)
MMM3 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
// 原本沒有: 新增
if (obj->count == obj->capacity) {
// 已滿: remove dhead 的最後一個
lru = MMM4(&obj->dhead, LRUNode, dlink);
list_del(&lru->dlink);
list_del(&lru->hlink);
} else {
// 沒滿: 新增
lru = malloc(sizeof(LRUNode));
obj->count++;
}
lru->key = key;
list_add(&lru->dlink, &obj->dhead);
list_add(&lru->hlink, &obj->hheads[hash]);
lru->value = value;
}
```
> MMM3 = list_for_each_entry
> MMM4 = list_last_entry
:::info
延伸問題
- [x] 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
- [ ] 在 Linux 核心找出 LRU 相關程式碼並探討
:::
## 測驗 4
[LeetCode 128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)
```c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct seq_node {
int num;
struct list_head link;
};
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)
{
int hash, length = 0;
struct seq_node *node;
// 建立 Hash table
struct list_head *heads = malloc(n_size * sizeof(*heads));
// 初始化 Hash table 的 heads
for (int i = 0; i < n_size; i++)
INIT_LIST_HEAD(&heads[i]);
// 將 nums 遍歷一次，沒有在 Hash table 出現過就 add
for (int i = 0; i < n_size; i++) {
if (!find(nums[i], n_size, heads)) {
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]);
}
}
// 將 nums 遍歷一次，並對每個元素的 +-1 進行查找，有找到就繼續找
for (int i = 0; i < n_size; i++) {
int len = 0;
int num;
node = find(nums[i], n_size, heads);
while (node) {
len++;
num = node->num;
list_del(&node->link);
int left = num, right = num;
while ((node = find(LLL, n_size, heads))) {
len++;
list_del(&node->link);
}
while ((node = find(RRR, n_size, heads))) {
len++;
list_del(&node->link);
}
length = len > length ? len : length;
}
}
return length;
}
```
`LLL = --left`
`RRR = ++right`
:::info
延伸問題
- [ ] 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
- [ ] 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼
:::
## 參考資料
* [What is the meaning of 0x61C88647](https://stackoverflow.com/questions/38994306/what-is-the-meaning-of-0x61c88647-constant-in-threadlocal-java)
* [Fibbonachi hashing](https://web.archive.org/web/20161121124236/http://brpreiss.com/books/opus4/html/page214.html)
* [Convert between unsigned and signed](https://onlinetoolz.net/unsigned-signed#base=10&value=2654435769&bits=32)
* [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
* [【C 語言的 LeetCode 30 天挑戰】第二十四天 (LRU Cache)](https://www.youtube.com/watch?v=0VgqZTtkINY&t=2610s)
Sign in with Wallet
Connect another wallet