# 2022q1 Homework1 (quiz1)
contributed by < `mm0809` >
## 測驗 1
### hlist 的主要結構
```c
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
通常時做出來的 hash map 會有複數個 `hlist_head` ，這邊為了方便表示只畫出一個由 `hlist_head` 構成的 list。觀察下圖可以發現 `hlist` 有幾個特色：
```graphviz
digraph{
node[shape=record]
rankdir=LR
head0[label="hlist_head|<f>first"]
node1[label="hash_key|<h>hlist_node|{<p>pprev|<n>next}"]
node2[label="hash_key|<h>hlist_node|{<p>pprev|<n>next}"]
node3[label="hash_key|<h>hlist_node|{<p>pprev|<n>next}"]
null[shape=plaintext label=NULL]
head0:f->node1:h
node1:n->node2:h
node2:n->node3:h
node1:p->head0:f
node2:p->node1:n
node3:p->node2:n
node3:n->null
}
```
* `hlist_head` 只有 `first` ，沒有 `prev`
* 原因1：我們在使用 `hash table` 時不會有針對 `tail` 的操作。
* 原因2：`hash table` 會希望越少 conflict 越好，這意味著在初始狀態下會有很多個 `hlist_head` ，少一個 `prev` 使得所需的記憶體減半。
* `pprev` 是 pointer to pointer ，並非普通的 `pointer`
* 原因1：因為上述的原因，`hlist_head` 的資料結構與 `hlist_node` 不同，導致第一個 node 無法使用普通的 `hlist_node` pointer 指向 `hlist_head`，必須透過 pointer to pointer to `hlist_node`。
* 原因2：使用普通的 pointer 並不會帶來好處，最多就是在往回 traversal 結點的時候比較方便，但 hash table 沒有這樣的需求。
* 最後一個節點指向 `NULL`
* 原因1： `hlist_head` 和 `hlist_node` 是不同資料結構，因此無法指向 `hlist_head`。
* 原因2：circular list 不會為 hash table 帶來更多便利。
`hlist` 雖捨棄了 lab-0 中 list 很多的特徵，但這些特徵 hash table 都用不上，還可在初始狀態節省一半空間。因此這樣的結構被選為實做 hash table。
### map_init
透過觀察 function `map_init` 以及 struct `hlist_node`, `hlist_head`, `map_t` 可以得知初始化後的結構長這樣：
```graphviz
digraph struct{
node[shape=record]
rankdir=LR
word0 [shape=plaintext, label=map]
struct0 [label="maplist.bits|<ht>maplist.ht"]
struct1 [label="<1>hlist_head.first|<2>...|<3>...|<4>...|<5>head_list.first" height=2]
subgraph {
node[shape=plaintext, label=NULL]
NULL1, NULL2, NULL3, NULL4, NULL5
}
word0->struct0
struct0:ht->struct1:1
struct1:1->NULL1
struct1:2->NULL2
struct1:3->NULL3
struct1:4->NULL4
struct1:5->NULL5
}
```
```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)
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;
}
```
### container_of
```c
#define container_of(ptr, type, member) \
({ \
void *__mptr = (void *) (ptr); \
((type *) (__mptr - offsetof(type, member))); \
})
```
這裡用到了兩個 GNU 提供的 C extension：
* [Statement Exprs](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Statement-Exprs.html#Statement-Exprs)
> This allows you to use loops, switches, and local variables within an expression.
> The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.
* [Typeof](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Typeof.html#Typeof)
> referring to the type of an expression.
`container_of` 的功能是幫助我們從一個 struct 裡面的一個 element 的 address 回推到整個 struct 的起始地址。
但這個版本的 `container_of` 與 lab-0 中的有些微不同。
```c
container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
lab-0 版本中的 `__pmember` 與 `__mptr` 角色定位相同，但是宣告的方式不太一樣。 `__pmember` 先運用了 `__typeof__` 和 null pointer 的方法去取得 member 的 type ，`__mptr` 則是一開始就宣告為 `void*`。 這樣的差異在正常情況下不會有差別，但是當使用者輸入錯參數時後者不會有任何反應，實驗如下。
```c
#include <stddef.h>
#include <stdio.h>
#define container_of(ptr, type, member) \
({ \
typeof(((type *) 0)->member)* __pmember =(ptr); \
((type *) ((void*)__pmember - offsetof(type, member)));\
})
#define container_of_void(ptr, type, member) \
({ \
void * __mptr = (void *) (ptr); \
((type *) (__mptr - offsetof(type, member))); \
})
struct bag {
char apple;
int book;
};
int main(void)
{
struct bag my_bag = {.apple = 'A', .book = 10};
int *book_ptr = &my_bag.book;
printf("a: %c, b: %d\n", my_bag.apple, my_bag.book);
printf("%p \n", (void*)&my_bag);
printf("%p \n", container_of(book_ptr, struct bag, apple));
printf("%p \n", container_of_void(book_ptr, struct bag, apple));
}
```
我的 `book_ptr` 是指向 `bag.book` 但是在使用 `container_of` 時我故意在 member 輸入 `apple`。
```shell
kuan@Athena:~/tmp$ gcc a.c
a.c: In function ‘main’:
a.c:6:51: warning: initialization of ‘char *’ from incompatible pointer type ‘int *’ [-Wincompatible-pointer-types]
6 | typeof(((type *) 0)->member)* __pmember =(ptr); \
| ^
a.c:27:21: note: in expansion of macro ‘container_of’
27 | printf("%p \n", container_of(book_ptr, struct bag, apple));
|
```
經過編譯以後，只有 `container_of` 有跳出警告訊息，這是因為 `container_of_void` 在一開始就把 `ptr` 和 `__mptr` 轉為或宣告為 `void *` ，因此即便 `member` 和 `ptr` 搭不上也不會跳出錯誤訊息。 相反的 `container_of` 則是透過 `type` 與 `member` 取得對應的型態，並且不去對 `ptr` 做其他操作，當使用者輸入錯誤時就會因為兩邊 type 不一樣而在編譯時期收到警告。
### map_get & find_key
```c
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;
}
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
`mep_get` 可以透過 `find_key` 取得 `hash_key` 的 address ，然後在取出 address of data 回傳。這裡有一個細節是 `hash_key` 是 static function，雖然在這題看似沒有影響，但是如果被 include 到其他地方，這意味著使用者不能直接使用 `find_key` 只能透過 `map_get` 去取得目標的 `data。`
### map_add & hash
```c
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
#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);
}
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;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
```
`map_add` 可以把一資料存到對應的 key 裡面。在存入之前要先檢查 `key` 是否已經在 map 裡面。如果沒有的會就會經過 `hash` function 用來選定加入哪個 `hlist`。 因為我們的 `hlist` 數量有限，所以在 `hash` return 之前有做一個 `>> (32 - bits)` 的動作，用來限制住 hash 出來的數字大小。
接著把新的 `hlist_node` 插入再 `hlist_head`之後。
最後在做插入 `hlist` 的時候需要做一個 `if (first)` 的判斷來確認在加入之前是否已經有其他的 node 。 這個問題在 lab-0 的 list 沒有出現是因為當初 list 是 circular 的，這邊的 `hlist` 最後一個 node 必定指向 `NULL` 因此需要做額外的判斷。
### map_deinit
這裡握們要把 `map` 所佔的記憶體空間全部釋放。當初 `malloc` 順序是：
```graphviz
digraph G{
rankdir=LR
node[shape=record]
n1[label=map]
n2[label="map-\>ht"]
n3[label="hlist nodes"]
n1->n2->n3
}
```
但是現在要 `free` 整個 `map` 所以必須倒過來做：
```graphviz
digraph G{
rankdir=LR
node[shape=record]
n1[label=map]
n2[label="map-\>ht"]
n3[label="hlist nodes"]
n1->n2->n3[dir=back]
}
```
```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);
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);
}
```
最內層的迴圈是在 free `hlist` 的結點以及他的 container ，但在最後 `free(map)` 之前應該要先 `free(map->ht)` 才符合前面所講的順序。
為了驗證我的想法，我初始化 `map` 以後立刻呼叫 `map_deinit` ，並且使用 valgrind 檢查。
```c
int main(void)
{
map_t *map = map_init(10);
map_deinit(map);
return 0;
}
```
```shell=
kuan@Athena:~/tmp$ valgrind -q --leak-check=full ./map
==62609== 8,192 bytes in 1 blocks are definitely lost in loss record 1 of 1
==62609== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==62609== by 0x1091BE: map_init (map.c:16)
==62609== by 0x10953A: main (map.c:111)
==62609==
```
在 `free(map)` 前加入 `free(map->ht)` 即可解決
### twosum
```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;
}
```
twosum 要找兩個數字的和為 target 。所以我們以數字本身當作 key 去做 hash。
數字 n 要找 target - n 的數字，所以要以 key = target - n 去 `map` 找。
* 有找到：回傳此數字的 `data`。
* 沒找到：以 key = n 存入 `map`，提供後面的數字查詢。
### Linux 核心 hash table 的設計和實作手法
`hashtable.h` 提供 hash table 的 API ，在其中 hash table 的 bucket 是採用 `hlist` 這個結構。 `hlist` 的相關操作 API 被定義在 `list.h` 。 `hlist` 與 `list` 的差別在於非 circular 結構 以及 `prev` 型態不同。 因此 hash table 提供的 API 頻繁的使用 `list.h` 的 API。
**未完成**
## 測驗 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;
}
```
當 `head` 傳入 `deleteDuplicates` 時有三種狀況：
* `head == NULL`
* `head` 是重複的結點
* `head` 不是重複的結點
第一個 `if` 已經排除 `head == NULL` 的可能性。
最後面的
```c
head->next = deleteDuplicates(head->next);
return head;
```
幫我們解決了 `head` 不是重複的結點的情況。因此中間的 `if` 是要來解決重複節點的。
若`head` 是重複的結點，則 `head->val == head->next->val` ， COND1 必定包含此判定。但是 `head->next` 可能為 `null` ，這會造成在運行時 `head->next->val` 產生錯誤，因此 COND1 為 `head->next && head->val == head->next->val`。
假如在進入 while 迴圈前長這樣：
```graphviz
digraph G{
node[style=circle]
{rank=same n1->n2->n3->n4->n5->NULL}
head->n1
n1[label="10"]
n2[label="10"]
n3[label="10"]
n4[label="17"]
n5[label="99"]
NULL[shape=none]
}
```
在結束後應該長這樣：
```graphviz
digraph G{
node[style=circle]
{rank=same n3->n4->n5->NULL}
head->n3
n3[label="10"]
n4[label="17"]
n5[label="99"]
NULL[shape=none]
}
```
這樣在 `return deleteDuplicates(head->next)` 時才能從 `17` 開始傳進去，同時把 `10` 都淘汰掉。所以 COND2 = `head->val == head->next->val` 。
但還要處理 COND1 類似的問題發生，比如說：
```graphviz
digraph G{
node[style=circle]
{rank=same n1->n2->n3->NULL}
head->n1
n1[label="10"]
n2[label="10"]
n3[label="10"]
NULL[shape=none]
}
```
經過 `while` 時 `head->val == head->next->val` 的判斷會出錯，因為當最後一個 `head` 指向最後一個 `10` 時 `head->next` 是 `NULL`。因此 COND2 應修正為 `head->next && head->val == head->next->val`。
### 迭代版本
```c
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteDuplicates(struct ListNode* head){
if (!head)
return NULL;
struct ListNode **n1, *n2;
for (n1 = &head, n2 = head->next; n2; n2 = n2->next) {
if ((*n1)->val == n2->val) {
while (n2 && (*n1)->val == n2->val)
n2 = n2->next;
*n1 = n2;
if (!n2)
return head;
} else {
n1 = &((*n1)->next);
}
}
return head;
}
```
在這個版本裡我採用 pointer to pointer 的技巧來避免做是否為第一個結點的判斷。
`struct ListNode **n1` 負責更改 pointer 的對象。
`struct ListNode *n2` 負責尋找第一個不重複的結點。
### circular doubly-linked list
## 測驗 3
### LURCache 的主要結構
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
一個 `LRUCache` 裡面有一個 `deadh list` 和數個 `hheads list` 。這兩個 list 的 node entry 都是 `LRUNode` 。
* `dhead` : 依照存取順序排序。
* `hhead` : 根據 `key` 經過 hash 後把帶有資料的 `LRUNode` 存到該 `hhead list` 中。
* `capacity` : 最多可以讓所有 `hheads list` 共有幾個 `LRUNode` 。
* `count` : 目前所有 `hhead list` 共有幾 `LRUNode` 。
每個 `hheads list` 不會有共同的 `node` 。因為 `dhead list` 是用來紀錄存取順序的，因此所有的 `node` 都會被 `dhead lsit` 串聯起來。 在每個 `LRUNode` 裡有兩個 `list_head` ，一個是用來與對應的 `hhead list` 連線，另一個是用來與 `dhead list` 連線。
### lRUCacheCreate
```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;
}
```
`lRUCacheCreate` 用來 allocate 並且初始化帶有 `capacity` 個 `hheads list` 的 `LRUCache` 物件 。在一開始 `dhead/hheads list` 都沒有任何 node 因此要使用 `INIT_LIST_HEAD` ， 使得 `prev` 和 `next` 都指向自己。
```graphviz
digraph G {
rankdir=LR
Cache[shape=record
label=" {lRUCache}|
{hhead}|
{hhead}|
...|
{dhead}"]
}
```
### lRUCachePut
```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;
}
```
`lRUCache(obj, key, value)` 當 `key` 對應的資料純在，就把資料跟新為 `value`。 否則就把 `key-value` 加入到 `lRUCache` 中。
程式碼可以分為以下情況
* `key`存在
* 更新 `key` 對應的 `value` ，並且更新 `dhead` ，把最進更新的 entry 放到第一位
* `key` 不存在
* `count` 以達到最大值 `capacity`
* 以新資料覆蓋最後一個 access 的 `LRUNode`
* 更新 `head list` 和 `dhead list`
* `count` 尚未達到最大值 `capacity`
* allocate 新的 `LRUNode`
* 更新 `head list` 和 `dhead list`
#### 尋找 `key` 是否存在
```c
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;
}
}
```
`dhead` 把所有的 `LRUNode` 都連在一起，很適合用來 traversal 尋找目標。 因此這裡 MMM3 使用 `list_for_each_entry`。
#### `key` 存在
若找到目標 `key` ，更新該 `value` 並且移動到 `dhead` 最前方。
雖然這個 traversal 有更改到 `dhead list` 的順序，但 `list_for_each_entry` 依舊適用，不須使用 `safe` 版本。原因是我們更改 `dhead list` 後就不再需要 traversal 。
#### `key` 不存在
```c
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;
```
##### `count` 達最大值 `capacity`
把最後一個 access 的結點覆蓋掉，且暫時移除節點。
在 MM4 使用 `list_last_entry` 取得 `dhead list` 最後一個 entry。再分別從 `dhead list` 和 `hhead list` 移除。
最後重新加回對應的 `hheads list` 以及插入 `dhead list` 第一個位置。
#### `count` 未達最大值 `capacity`
allocate 一個新的 `LRUNode` 。
最後重新加回對應的 `hheads list` 以及插入 `dhead list` 第一個位置。
### lRUCacheGet
```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;
}
```
再對應的 `hheads list` 中找指定的 `key` ，傳回 `value` 。
`lRUCacheGet` 視為 access 因此還要更新 `dhead list` 。
MM2 為 `list_for_each_entry` 來 traversal 。這裡不使用 `safe` 版本的原因是我們更改 `dhead list` 而 traversal 使用的 `hheads list` 未被更改，且在更改後也沒有繼續 iterate。
### lRUCacheFree
```c
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
根據 `LRUCache` 結構， `dhead list` 把所有的 `LRUNode` 串起來。我們可以使用這個特點來 deallocate 所有 `LRUEntry`。
MMM1 使用 `list_for_each_entry_safe` ，先把目標移除 list ，然後 deallocate 。
### 可改進的地方
#### `hhead` 資料結構改進
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
```
`hheads` 在 `LRUCache` 的腳色是在做 `hash table`。 且在實作其他 function 時 `hhead list` 使用不到對最後一個 list 的操作。 因此可改為使用 `hlist` 的資料結構：
```c
typedef struct {
int capacity, count;
struct list_head dhead;
struct hlist_head hheads[];
} LRUCache;
struct hlist_head {
struct hlist_node *first;
}
struct hlist_node {
struct hlist_node *next, **pprev;
}
```
雖然 `capaticy` 為變數，在多數情況下 `hheads` 在初始時佔 `LRUCache` 大多數的記憶體，這樣的資料結構有助於減少所需的記憶體空間。
## 測驗 4
[LeetCode 128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)
### 主要結構
```c
struct seq_node {
int num;
struct list_head link;
};
// In function `longestConsecutive`
struct list_head *heads = malloc(n_size * sizeof(*heads));
```
`heads` 指向多個 `list_head` ，被當作 `hash table` 使用。
### find
```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;
}
```
把 `num` hash 後得到 `index` 後 traversal 對應的 `list` 尋找目標。目標存在救回傳節點，不存在回傳 `NULL` 。
### longestConsecutive
```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]);
}
}
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;
}
```
一開始先 allocate 有 `n_size` 個 `list_head *` 並初始化。
接著把所有的 `num` 經過 hash 後放到對應的 `list` ，同時避免放入重複的 `num`。
接著開始找連續的數字。先以一個尚未被移除的 `num` 為基準。
```graphviz
digraph GP{
node[shape=record]
nu[shape=none label="num = 5"]
len[shape=none label="len = 1"]
nums[label="...|2(?)|3(?)|4(?)|5(V)|6(?)|7(?)|8(?)|..."]
}
```
接著第一個 `while` 是一直往 `num` 的左邊尋找，直到找不到連續的數字。
LLL 為 `--left`
```graphviz
digraph GP{
node[shape=record]
nu[shape=none label="num = 5"]
len[shape=none label="len = 3"]
nums[label="...|2(X)|3(V)|4(V)|5(V)|6(?)|7(?)|8(?)|..."]
}
```
第二個 `while` 是一直往 `num` 的右邊尋找，直到找不到連續的數字。
RRR 為 `++right`
```graphviz
digraph GP{
node[shape=record]
nu[shape=none label="num = 5"]
len[shape=none label="len = 5"]
nums[label="...|2(X)|3(V)|4(V)|5(V)|6(V)|7(V)|8(X)|..."]
}
```
上述找到的數字都會被從 `list` 中移除。這樣的動作一直重複到所有的數字 `num[]` 都被找過一遍。最後最長的 `len` 就是答案。
Sign in with Wallet
Connect another wallet