---
tags: Linux, linux2022
---
2022q1 Homework1 (quiz1)
===
contributed by < `NOVBobLee` >
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗 1 [LeetCode - Two Sum](https://leetcode.com/problems/two-sum/)
Two sum 若以暴力法，則時間複雜度為 $O(n^2)$ 。若改以使用湊雜表，可降低時間複雜度到 $O(n)$ 以下。以下為使用 Linux 湊雜表結構的湊雜表實作，拆開解釋，最後利用他來完成 Two sum 。
### 湊雜表結構宣告
Linux 的湊雜表使用兩種結構，一為 `hlist_head` ，為湊雜表 bucket 的開頭，是單向鍊結結構，二為 `hlist_node` ，為 bucket 裡的元素連結，是雙向鍊結結構。為何不使用通用的 `list_head` ，其原因在湊雜表為減少碰撞發生，會把 bucket 的數量增大，且不少 bucket 是空的，若使用雙向鍊結結構，一個開頭就需要兩個指標的空間。第二是如果碰撞變少，那麼 bucket 裡的元素數量也不多，不需要像環狀雙向鍊結結構可以從尾部或從頭部兩種方向走訪。
為使 `hlist_node` 的插入刪除方便，其使用雙向鍊結結構。但是 bucket 的開頭與元素連結卻是使用不同的結構，為使雙練鍊結結構與單向鍊結結構結合，且插入刪除不會因為前一個是開頭而需要新的分支， `hlist_node` 改使用的 `pprev` ，指標的指標，非常漂亮。
```graphviz
digraph a {
rankdir=LR;
node[fontname="Helvetica";shape=record;];
edge[style=dashed];
map [
label="bucket 0|bucket 1|bucket 2|<buc>bucket 3|...|bucket n";
xlabel="map_t";
];
hn1 [
label="<n>next|<pp>pprev";
xlabel="hlist_node";
];
hn2 [
label="<n>next|<pp>pprev";
xlabel="hlist_node";
];
end [
label="NULL";
shape=plaintext;
]
map:buc -> hn1;
hn1:n -> hn2;
hn1:pp -> map:buc;
hn2:pp -> hn1:n;
hn2:n -> end;
}
```
而湊雜表本體為 `map_t` ，其包含多個 buckets （ `ht` ），而其數量會使用巨集 `MAP_HASH_SIZE` 來決定，固定為 $2$ 的冪。為何存 `bits` 而非實際數量？是因為湊砸函數 `hash` 頻繁使用到，而實際數量只有在建立和釋放湊雜表的時候用到（ 2 次）而已。
```c
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;
#define MAP_HASH_SIZE(bits) (1 << bits)
```
### 建立空湊雜表
輸入為 `bits` ，代入剛提到的巨集 `MAP_HASH_SIZE` 會得到湊雜表 bucket 要配置的數量。
```c
map_t *map_init(int bits) {
/* 湊雜表空間配置 */
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
map->bits = bits;
/* buckets 開頭空間配置 */
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++)
/* bucket 開頭初始化 */
(map->ht)[i].first = NULL;
} else {
free(map);
map = NULL;
}
return map;
}
```
### 湊雜表元素與相關巨集
湊雜表元素 `hash_key` ，包含一個 `key` ，拿來定位 bucket 的位置，一個 `data` ，存放資料的地址，和 `node` ，與湊雜表連結用。
```c
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
如果我們從 bucket 的開頭出發，得到的會是 `hlist_node` ，這樣要怎麼找到包裝他的容器 `hash_key` ？其方法是使用下面的巨集 `container_of` ，在得知 `hlist_node` 在 `hash_key` 裡的位移量後，可以反推得到容器的開頭位置。
```c
#define container_of(ptr, type, member) \
({ \
void *__mptr = (void *) (ptr); \
((type *) (__mptr - offsetof(type, member))); \
})
```
湊雜函數則是使用以下的函式 `hash` ，用來取得 `key_hash` 的 `key` 值，其使用的是 Fibonacci hashing 。可以看到我們 buckets 的數量用 $2$ 的冪，取 modulo 可以直接使用 bit-shift ，比起使用 modulo 任意數更快。
```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);
}
```
### 搜尋 `hash_key`
輸入 `key` 找尋相對應的 `hash_key` 。
```c
static struct hash_key *find_key(map_t *map, int key) {
/* bucket 開頭位置 */
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
/* 走訪該 bucket 的元素 */
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;
}
```
### 取得 `key` 對應的資料
用 `find_key` 搜尋 `hash_key` 湊砸表元素，找到則返回裡面存的資料 `data` ，否則返回 `NULL` 。
```c
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
### 加入湊砸表元素
此函式為插入新的湊雜表元素用，若 `key` 值已經被使用，則失敗，必須使用沒使用過的 `key` 值。
```c=
void map_add(map_t *map, int key, void *data)
{
/* 檢查是否 key 值重複 */
struct hash_key *kn = find_key(map, key);
if (kn)
return;
/* 建立新的湊雜表元素 */
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
/* 插入到湊雜表對應的 bucket 裡 */
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 與 BBB 填空，在建立新的湊雜表元素後，我們要將其加入到湊雜表中，可以看到 `h` 是湊雜表的 bucket ， `n` 是剛建立的湊雜表元素的連結 `node` ，也就是說要把 `n` 加入 `h` 中。
要幫 `n` 作連結卻沒看到 `n->next` 與 `n->pprev` 的賦值，所以這兩個填空應該與剛提的兩個賦值相關。
然後 `first` 是 bucket 的第一個元素，加上第 18 行 `h->first = n` ，所以 `n` 是要插在 bucket 第一個的位置。又在第 17 行 `first->pprev = &n->next` 會使用到 `n->next` 的值，所以 AAA 應該是 `n->next = first`。
那麼剩下的 BBB 就是要完整雙向鍊結結構，將 `n->pprev` 指到 `h->first` 的位置上，即 `n->pprev = &h->first` 。
### 刪除湊雜表
遍歷湊雜表的 buckets 和 bucket 裡的元素，一一釋放空間。
```c
void map_deinit(map_t *map)
{
if (!map)
return;
/* 走訪湊雜表的 buckets */
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
/* 走訪 bucket 裡的元素 */
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
::: warning
看了一下插入刪除元素的操作，沒看到會有 `if (!n->pprev)` 為真的情況。待查。
:::
### Two sum
給定一數 `target` ，在給定數列 `nums` 中找尋兩個數相加的和為 `target` 的組合。
```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;
/* 一邊插入湊雜表元素，一邊找尋是否有剛好配對的數，在剛才插入的湊雜表元素中 */
for (int i = 0; i < numsSize; i++) {
int *p = map_get(map, target - nums[i]);
if (p) { /* found */
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
bail:
map_deinit(map);
return ret;
}
```
:::info
延伸問題：
1. 解釋程式碼運作原理
2. 研讀 Linux 核心原始程式碼 [include/linux/hashtable.h](https://github.com/torvalds/linux/blob/master/include/linux/hashtable.h) 及對應的文件 [How does the kernel implements Hashtables?](https://kernelnewbies.org/FAQ/Hashtables)，解釋 hash table 的設計和實作手法，並留意到 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 的 GOLDEN_RATIO_PRIME，探討其實作考量
:::
## 測驗 2 [LeetCode - Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
給定一個已排序過的單向鍊結結構，移除重複值的元素，如 1-1-2-3 變成 2-3 。
```c=
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;
}
```
程式碼可以看出是使用遞迴，然後遞迴的結束是回傳 `NULL` 或者返回 `head` 。再來看第二個 if ，若 COND1 為真，則會進入 `remove all duplicate numbers` 的區域，所以可以推測出 COND1 應該跟檢查重複值有關，而且檢查重複值元素的第一個，所以 COND1 應該是 `head->next && head->val == head->next->val` 。
然後繼續推測他是如何移除重複值元素，試想一個例子， 1-2-2-3 會變成 1-3 ，其中 1, 3 要作連結。在將這例子套進程式碼， `1->next` 會進入 `2` 的遞迴，等待回傳 `3` 的指標。而 `2` 的遞迴會進入 COND1 的區塊，這時要把 `head` 要移到哪裡，代入 `head->next` 才可以返回 `3` 的指標？因為返回只有兩種， `NULL` 和 `head` ，所以剛才要帶入的 `head->next` 應該就是 `3` 的指標。也就是說 `head` 應該要移到 `3` 的前一個元素， `2` ，那麼 COND2 區塊就是要把 `head` 移到重複元素的最後一個，那麼應該填 `head->next && head->val == head->next->val` 。
遞迴方式：走訪每一個元素，若有重複值的元素，則尋找下一個不重複值的元素，傳回其指標，跟第一個重複值元素的前一個元素相接。若沒遇到重複值元素，則照原連結方式連接。
改寫成迭代方式，原理跟上面方法一樣，只是我們不能用遞迴的 stack 紀錄前一個不重複值元素的指標，所以加入間接指標 `dup_pprev` 代替。
```c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
struct ListNode *orig_head, **dup_pprev;
if (!head || !head->next)
return head;
orig_head = head;
/* 初始化 */
dup_pprev = &head;
do {
/* 發現有重複值元素 */
if (head->next && head->val == head->next->val) {
/* 直到找到不重複值元素 */
while (head->next && head->val == head->next->val)
head = head->next;
/* 前一個不重複值元素跨過重複值元素，跟找到的不重複值元素連接 */
*dup_pprev = head->next;
} else {
dup_pprev = &(*dup_pprev)->next;
}
head = head->next;
} while (head); /* 走訪所有元素 */
return orig_head;
}
```
:::info
延伸問題：
1. 嘗試避免遞迴，寫出同樣作用的程式碼
2. 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼
- [x] 迭代
- [ ] 遞迴
:::
使用類似 Linux `list_head` 雙向循環鍊結結構的版本（假設 `head` 沒有 `val` 值，只作雙向鍊結結構的開頭）：
```c
struct ListNode {
int val;
struct ListNode *next, *prev;
};
struct ListNode *deleteDuplicates(struct ListNode *head)
{
struct ListNode *orig_head, *next;
int found_dup = 0;
/* 若 head 為 NULL, 空的或只有 1 個元素 */
if (!head || head->next == head || head->next = head->prev)
return head;
orig_head = head;
/* 走訪每一個元素，用 next 暫存下一個元素 */
for (head = head->next, next = head->next;
head != orig_head;
head = next, next = next->next) {
int cmp_result =
(head->next != orig_head) && (head->val != next->value);
/* 若與下一個元素重複值，或前一個元素為重複值元素 */
if (cmp_result || found_dup) {
/* 移除 head */
head->prev->next = next;
next->prev = head->prev;
/* 紀錄是否為重複值元素 */
found_dup = cmp_result;
}
}
return orig_head;
}
```
## 測驗 3 [LeetCode - LRU Cache](https://leetcode.com/problems/lru-cache/)
在 cache 上的管理，因為空間是有限的，所以我們會希望有方法可以符合需求和效率，知道哪些 cache 該留，哪些該捨棄。而 [Least Recently Used, LRU](https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)) 為其中一種，若某一個 cache 很久沒有使用了，那可能之後也不會再使用了。
### 結構宣告
```graphviz
digraph {
rankdir=LR;
node[shape=record;fontname="Helvetica";]
hd [
label="bucket 0|<buc>bucket 1|...|bucket n";
xlabel="hheads";
];
hl1 [
label="key|value|{<p>prev|<n>next}|dlink";
xlabel="LRUNode";
];
hl2 [
label="key|value|{<p>prev|<n>next}|dlink";
xlabel="LRUNode";
];
hd:buc -> hl1:p[dir=both];
hl1:n -> hl2:p[dir=both];
hl2:n -> hd:buc[dir=both];
dd [
label="{<p>prev|<n>next}";
xlabel="dhead";
];
dl1 [
label="key|value|hlink|{<p>prev|<n>next}";
xlabel="LRUNode";
];
dl2 [
label="key|value|hlink|{<p>prev|<n>next}";
xlabel="LRUNode";
];
dd:n -> dl1:p[dir=both];
dl1:n -> dl2:p[dir=both];
dl2:n -> dd:p[dir=both];
}
```
從結構上看來， `LRUCache` 有一個湊雜表 `hheads` 和一個雙向陣列結構的開頭 `dhead` ，有 cache 的上限數量 `capacity` 和已使用的數量 `count` 。而 `LRUNode` 則是 cache 的單元，包括拿來湊雜搜尋用的 `key` 和 cache 儲存的內容 `value` ，還有分別對應 `hheads` 和 `dhead` 用的元素 `hlink`, `dlink` ，其連結方式如上圖。
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
### 建立與移除 cache
給定 cache 得容量 `capacity` ，然後依照其值配置對應的記憶體。最初還沒有使用 cache ，所以 `count` 會是零， `dhead`, `hheads` 分別指向自己，代表還是空的。
```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;
}
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
從結構上來看，要移除 cache `LRUCache` 需要先移除其元素 `LRUNode` ，其連接方式有兩種，若要找到所有元素最快的方法是從 `dhead` 遍歷。而 `dhead` 與 `dlink` 相連，利用 `list_entry` 可以找到對應的 `LRUNode` ，且我們會移除 `dlink` ，所以 MMM1 要使用 `list_for_each_entry_safe` 。
### 讀取 cache
當要讀取某特定的 cache 的時候，需要給該 cache 的 `key` 值，使用湊雜表快速搜尋該 cache 的位置，找到則回傳 cache 儲存的內容 `value` ，否則回傳 $-1$ 。過程中因為要使用 LRU 方法，所以會需要排列雙向鍊結結構的順序，
```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;
}
```
找到 bucket 位置，然後遍歷該 bucket ，依照 LRU 的規則，遍歷方向是 next 的方向。遍歷的變數是 `lru` ，型態為 `LRUNode` ，加上只要查看，沒有要移除節點，所以 MMM2 應該為 `list_for_each_entry` 。
### 存入 cache
輸入資料 `value` 和對應的 `key` 值，將這些內容存入或更新對應 `key` 值的 cache 的元素 `LRUNode` 。但是就如剛才所提的，這些元素是有限的，所以當我們是存入（沒有對應 `key` 值的 cache 元素），遇到已使用的元素數量 `count` 到達上限 `capacity` 時，我們需要利用 LRU 的規則，把最久沒有使用的 cache 元素給移除，然後再插入新的元素。而如果是更新，那只需要移動其元素在雙向鍊結結構裡的位置，以符合 LRU 要求。
```c
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *lru;
int hash = key % obj->capacity;
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) {
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 的區塊是更新元素的區塊，所以會遍歷對應 bucket 裡的元素，依照 LRU 規則，方向為 next 。而 `lru` 為 `LRUNode` 結構，移動完元素位置後就停止遍歷，所以 MMM3 為 `list_for_each_entry` 。
而下一個區塊會檢查 `count` 與 `capacity` ，可以知道是要存入元素。而如果相同，根據 LRU 的規則，那就要先移除最久沒有使用的元素，在雙向鍊結結構的末尾，所以 MMM4 應該為 `list_last_entry` 。移除後將要存入的資料更新上去，然後在加回到 `lRUCache` 中。
:::info
延伸問題：
1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 在 Linux 核心找出 LRU 相關程式碼並探討
:::
## 測驗 4 [LeetCode - Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)
給定一未排序陣列，找出最長連續數列的長度，比如 1-2-5-3-7-8 ，最長連續數列為 1-2-3 ，所以長度是 3 。此處使用湊雜表，在建立完湊雜表（時間複雜度 $O(n)$ ）後，要搜尋數列下一個元素的時間複雜度變為 $O(1)$ ，總時間複雜度為 $O(n)$ 。
### 結構宣告
```graphviz
digraph a {
rankdir=LR;
node[fontname="Helvetica";shape=record;];
edge[style=dashed];
heads [
label="bucket 0|<buc>bucket 1|...|bucket n";
xlabel="heads";
];
hn1 [
label="num|{<pp>pprev|<n>next}";
xlabel="seq_node";
];
hn2 [
label="num|{<pp>pprev|<n>next}";
xlabel="seq_node";
];
end [
label="NULL";
shape=plaintext;
]
heads:buc -> hn1;
hn1:n -> hn2;
hn1:pp -> heads:buc;
hn2:pp -> hn1:n;
hn2:n -> end;
}
```
此為湊雜表的元素， `num` 是陣列的某一位置的數值， `link` 是與湊雜表和湊雜表元素連結的成員。
```c
struct seq_node {
int num;
struct list_head link;
};
```
### 湊雜表元素搜尋
搜尋湊雜表元素，湊砸函數使用到陣列的數值 `num` 和大小 `size` ，得到湊雜值 `hash` 後在對應的 bucket 裡（ `heads[hash]` ）找尋元素，找到則回傳該指標，否則回傳 `NULL` 。
```c
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;
}
```
### 主函式
首先先建立湊雜表，並將陣列數值放入湊雜表中。在來依序取陣列的數值，找尋包含該數值之最長連續數列長度 `len` ，若找到的長度比 `length` 更長，則更新最終最長長度 `length` 。
```c=
int longestConsecutive(int *nums, int n_size)
{
int hash, length = 0;
struct seq_node *node;
struct list_head *heads = malloc(n_size * sizeof(*heads));
/* 初始化湊雜表 */
for (int i = 0; i < n_size; i++)
INIT_LIST_HEAD(&heads[i]);
/* 將陣列的數值放進去，重複的數值略過 */
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]);
}
}
/* 依序取陣列的數值，找尋包含該數值最長連續數列長度
* 若找到長度比 length 更長，則更新 length
* 在找尋的過程中，造訪過得元素會被移除，可以避免無謂的重複找尋 */
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, RRR 剛好是在對稱的位置上，從第 31 行看到 `node` 被移除，也就是 `num` 已經造訪過了，之後應該要往數值的兩邊作找尋，也就是第 34, 39 行。從第 33 行得知 `left` 與 `right` 是 `num` ，所以兩填空應該要為 `--left` 與 `++right` 才會進入迴圈。
:::info
延伸問題：
1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼
:::
### 使用 Linux 核心風格的 hash table 改寫
在 Linux 裡湊雜表元素是使用 `sturct hlist_node` ，這裡替換原本的 `struct list_head` 。
```c
struct seq_node {
int num;
struct hlist_node link;
};
```
在 Linux 裡的湊雜函數是使用 Fibonacci hasing ，輸入一個 key 然後得到 bucket 的位置，這裡我們直接使用 `num` 當 key 值。 `hash_for_each_possible` 會遍歷對應 key 值的 bucket ，這裡替換原本的 `list_for_each_entry` 和 hash 計算。
```c
static struct seq_node *find(int num, struct hlist_head *heads)
{
struct seq_node *node;
/* use nums[i] as key directly */
hash_for_each_possible (heads, node, link, num) {
if (num == node->num)
return node;
}
return NULL;
}
```
最後是主函式，需要建立一個空湊雜表，原本是用迴圈和 `INIT_LIST_HEAD` 初始化，在 Linux 裡則是有 `__hash_init` 可以使用，其湊雜表的大小固定為 $2$ 的冪，所以要先算一下湊雜表的大小，至少是大於 `n_size` 的。補充說明一下，為何不用 `HASH_SIZE` 巨集，因為我們要使用動態配置記憶，這樣導致 `heads` 不是陣列，所以無法使用。另外因為同樣的理由，沒有使用 `hash_init` 和 `DEFINE_HASHTABLE` 。
```c
int longestConsecutive(int *nums, int n_size)
{
int length = 0, bits = 4, ht_size;
struct seq_node *node;
struct hlist_head *heads;
/* hashtable with size 2^bits */
while (n_size > (1 << bits))
++bits;
ht_size = 1 << bits;
heads = malloc(sizeof(struct hlist_head) * ht_size);
__hash_init(heads, ht_size);
for (int i = 0; i < n_size; ++i) {
/* if not found, create and add it in */
if (!find(nums[i], heads)) {
node = malloc(sizeof(struct seq_node));
node->num = nums[i];
/* use nums[i] as key directly */
hash_add(heads, &node->link, nums[i]);
}
}
for (int i = 0; i < n_size; ++i) {
int num, len = 0;
node = find(nums[i], heads);
while (node) {
++len;
num = node->num;
hash_del(&node->link);
int left = num, right = num;
/* search leftward */
while (node = find(--left, heads)) {
++len;
hash_del(&node->link);
}
/* search rightward */
while (node = find(++right, heads)) {
++len;
hash_del(&node->link);
}
length = len > length ? len : length;
}
}
return length;
}
```
剩下的部份有兩個函式有替換，第一個是 `list_add` 插入湊雜表元素，這裡換為 `hash_add` ，不一樣的地方是要多輸入 key 值，也就是他會在裡面算對應的 bucket 位置。而另一個函式是 `list_del` ，利用雙向連結結構， `hash_del` 一樣只需要輸入要移除的元素即可。
Sign in with Wallet
Connect another wallet