---
# System prepended metadata

title: 2022q1 Homework1 (quiz1)

---

# 2022q1 Homework1 (quiz1)
contributed by < `cy023` >

> [測驗題](https://hackmd.io/@sysprog/linux2022-quiz1)

## 測驗 `1`
### Hash Table
<!-- Graphviz 初心者 :) -->
```graphviz
digraph hash_table {
    layout=fdp;
    subgraph cluster_0 {
        label="map_t";
        style=filled;
        color=lightgrey;
        node [shape=record,color=black];
        map_t [label="{ bits |<a> ht }", width=1, height=0.2];
    }

    subgraph cluster_1 {
        label="struct hlist_head";
        style=filled;
        color=lightgrey;
        node [shape=record,color=black];
        hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
    }

    subgraph cluster_2 {
        label="struct hlist_node";
        style=filled;
        color=lightgrey;
        node [shape=record,color=black,rankdir=LR];
        hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
    }

    subgraph cluster_3 {
        label="struct hlist_node";
        style=filled;
        color=lightgrey;
        node [shape=record,color=black,rankdir=LR];
        hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
    }

    NULL [shape=plaintext]

    {
        edge[style=solid];
        N1 [pos="0,4!", style=invis]
        N2 [pos="2,1!", style=invis]
        N3 [pos="7,1!", style=invis]
        N4 [pos="10,1!", style=invis]
        N5 [pos="13,1!", style=invis]
        edge[style=invis, rankdir=LR]
        N1 -> N2 -> N3 -> N4 -> N5
    }
    {
        // rankdir=TB;
        edge [style=invis]
        map_t -> N1;
        cluster_1 -> N2;
        cluster_2 -> N3;
        cluster_3 -> N4;
        NULL -> N5;
    }
    // next
    map_t:a -> hlist_head:b -> cluster_2 
    hlist_node0:d -> cluster_3
    hlist_node1:d -> NULL
    
    // pprev
    edge[splines=curved];
    hlist_node0:c -> hlist_head:b [color=lightskyblue4]
    hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
}
```

`map_t` 結構內紀錄 hash table 的欄位數量共 `1 << bits` 個，起始位址 `ht` 指向由 `struct hlist_head *` 型態構成的陣列。

比較特別的地方在 `hlist_node` 的 `**pprev` 用了**指標的指標**，參考[第 1 週課堂問答簡記](https://hackmd.io/5zdyXn6uQMOeSoVBapuVNw?view)。

```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;
```

包裝了 `struct hlist_node` 結構的節點，另外包含經過 hash function 的 `key` 與儲存的資料。

```c
struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};
```

### 初始化 Hash Table
1. 配置 `map_t` 空間存放 hash table 的 Bucket 大小與起始位址的資訊。
    ```graphviz
    digraph {
        subgraph cluster_0 {
        label="map_t";
        style=filled;
        color=lightgrey;
        node [shape=record,color=black];
        map_t [label="{ bits |<a> ht }", width=1, height=0.2];
    }
    }
    ```
2. 配置 `struct hlist_head` 型態陣列，共 `(1 << bits)` 個 `Bucket`，全都指向 `NULL`。
    ```graphviz
    digraph {
        subgraph cluster_1 {
            label="struct hlist_head";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
        }
    }
    ```
```c
#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;
}
```

### 釋放 Hash Table 使用空間

依序將每個 `Bucket` 連接的節點，利用 `container_of` 找出完整空間後釋放。

```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);
}
```

不太清楚何時會發生 `n->pprev` 等於 `NULL`，將此判斷註解仍能通過 LeetCode 測資...
```c=13
if (!n->pprev) /* unhashed */
    goto bail;
```

若 Bucket 內還存在 `next` 節點時，先將節點 `remove`，`next`、`pprev` 都指向 `NULL` 後再進行記憶體釋放。
```c=16
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
    next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
```

### Hash Function
What ...?
TODO...
```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 table 內查找，給定 `key` 值的節點。
先利用 hash function 找到對應 `bucket`，再於該 `bucket` 指向的 `hlist_node` 內尋找(使用 `container_of` 取得 `hash_key` 的完整資訊，再與給定 `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;
}
```

給定 `key` 在 hash table 中查找對應的 data。
```c
void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}
```

在 hash table 中新增節點。
配置 `struct hash_key` 大小的空間，填入 `key`, `data` 資訊。
`line10` 先對 `key` 值進行雜湊，找到對應的 `bucket` - `h`。
`line11` 新增的 `hash_key` 節點 `n`，`bucket` 內的第一個節點 `first`。

因為要把 `n` 插入進 `bucket` 的第一個節點，所以將新節點的 `next` 指向 `first`，若 `bucket` 不為空 (`first` 不為 `NULL`)，將 `first->pprev = &n->next;`。

- `n->next = first;`
    ```graphviz
    digraph hash_table {
        layout=fdp;
        subgraph cluster_0 {
            label="map_t";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            map_t [label="{ bits |<a> ht }", width=1, height=0.2];
        }

        subgraph cluster_1 {
            label="struct hlist_head";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
        }

        subgraph cluster_2 {
            label="node0";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        subgraph cluster_3 {
            label="node1";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        subgraph cluster_4 {
            label="node_new";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node2 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        NULL [shape=plaintext]

        {
            edge[style=solid];
            N1 [pos="0,4!", style=invis]
            N2 [pos="2,1!", style=invis]
            N3 [pos="10,1!", style=invis]
            N4 [pos="13,1!", style=invis]
            N5 [pos="6,3!", style=invis]
            N6 [pos="16,1!", style=invis]
            edge[style=invis, rankdir=LR]
            N1 -> N2 -> N3 -> N4 -> N5 -> N6
        }
        {
            // rankdir=TB;
            edge [style=invis]
            map_t -> N1;
            cluster_1 -> N2;
            cluster_2 -> N3;
            cluster_3 -> N4;
            cluster_4 -> N5;
            NULL -> N6;
        }
        // next
        map_t:a -> hlist_head:b -> cluster_2 
        hlist_node0:d -> cluster_3
        hlist_node1:d -> NULL
        hlist_node2:d -> cluster_2 [color=red]

        // pprev
        edge[splines=curved];
        hlist_node0:c -> hlist_head:b [color=lightskyblue4]
        hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
    }
    ```
- `if (first)
        first->pprev = &n->next;`
    ```graphviz
    digraph hash_table {
        layout=fdp;
            subgraph cluster_0 {
            label="map_t";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            map_t [label="{ bits |<a> ht }", width=1, height=0.2];
        }

        subgraph cluster_1 {
            label="struct hlist_head";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
        }

        subgraph cluster_2 {
            label="node0";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        subgraph cluster_3 {
            label="node1";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        subgraph cluster_4 {
            label="node_new";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node2 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        NULL [shape=plaintext]

        {
            edge[style=solid];
            N1 [pos="0,4!", style=invis]
            N2 [pos="2,1!", style=invis]
            N3 [pos="10,1!", style=invis]
            N4 [pos="13,1!", style=invis]
            N5 [pos="6,3!", style=invis]
            N6 [pos="16,1!", style=invis]
            edge[style=invis, rankdir=LR]
            N1 -> N2 -> N3 -> N4 -> N5 -> N6
        }
        {
            // rankdir=TB;
            edge [style=invis]
            map_t -> N1;
            cluster_1 -> N2;
            cluster_2 -> N3;
            cluster_3 -> N4;
            cluster_4 -> N5;
            NULL -> N6;
        }
        // next
        map_t:a -> hlist_head:b -> cluster_2 
        hlist_node0:d -> cluster_3
        hlist_node1:d -> NULL
        hlist_node2:d -> cluster_2

        // pprev
        edge[splines=curved];
        hlist_node0:c -> hlist_node2:d [color=red]
        hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
    }
    ```
- `h->first = n;`
    ```graphviz

    digraph hash_table {
        layout=fdp;
            subgraph cluster_0 {
            label="map_t";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            map_t [label="{ bits |<a> ht }", width=1, height=0.2];
        }

        subgraph cluster_1 {
            label="struct hlist_head";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
        }

        subgraph cluster_2 {
            label="node0";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        subgraph cluster_3 {
            label="node1";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        subgraph cluster_4 {
            label="node_new";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node2 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        NULL [shape=plaintext]

        {
            edge[style=solid];
            N1 [pos="0,4!", style=invis]
            N2 [pos="2,1!", style=invis]
            N3 [pos="10,1!", style=invis]
            N4 [pos="13,1!", style=invis]
            N5 [pos="6,3!", style=invis]
            N6 [pos="16,1!", style=invis]
            edge[style=invis, rankdir=LR]
            N1 -> N2 -> N3 -> N4 -> N5 -> N6
        }
        {
            // rankdir=TB;
            edge [style=invis]
            map_t -> N1;
            cluster_1 -> N2;
            cluster_2 -> N3;
            cluster_3 -> N4;
            cluster_4 -> N5;
            NULL -> N6;
        }
        // next
        map_t:a -> hlist_head:b1
        hlist_head:b -> cluster_4 [color=red]
        hlist_node0:d -> cluster_3
        hlist_node1:d -> NULL
        hlist_node2:d -> cluster_2

        // pprev
        edge[splines=curved];
        hlist_node0:c -> hlist_node2:d [color=lightskyblue4]
        hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
    }
    ```
- `n->pprev = &h->first;`
    ```graphviz
    digraph hash_table {
        layout=fdp;
            subgraph cluster_0 {
            label="map_t";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            map_t [label="{ bits |<a> ht }", width=1, height=0.2];
        }

        subgraph cluster_1 {
            label="struct hlist_head";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black];
            hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
        }

        subgraph cluster_2 {
            label="node0";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        subgraph cluster_3 {
            label="node1";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        subgraph cluster_4 {
            label="node_new";
            style=filled;
            color=lightgrey;
            node [shape=record,color=black,rankdir=LR];
            hlist_node2 [label="<c> pprev | <d> next", width=1, height=0.2];
        }

        NULL [shape=plaintext]

        {
            edge[style=solid];
            N1 [pos="0,4!", style=invis]
            N2 [pos="2,1!", style=invis]
            N3 [pos="10,1!", style=invis]
            N4 [pos="13,1!", style=invis]
            N5 [pos="6,3!", style=invis]
            N6 [pos="16,1!", style=invis]
            edge[style=invis, rankdir=LR]
            N1 -> N2 -> N3 -> N4 -> N5 -> N6
        }
        {
            // rankdir=TB;
            edge [style=invis]
            map_t -> N1;
            cluster_1 -> N2;
            cluster_2 -> N3;
            cluster_3 -> N4;
            cluster_4 -> N5;
            NULL -> N6;
        }
        // next
        map_t:a -> hlist_head:b1
        hlist_head:b -> cluster_4
        hlist_node0:d -> cluster_3
        hlist_node1:d -> NULL
        hlist_node2:d -> cluster_2

        // pprev
        edge[splines=curved];
        hlist_node0:c -> hlist_node2:d [color=lightskyblue4]
        hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
        hlist_node2:c -> hlist_head:b  [color=red]
    }
    ```

```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;
    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}
```

:::info
AAA = `n->next = first;`
BBB = `n->pprev = &h->first;`
:::

## 測驗 `2`
[LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
### 遞迴版本

```c
struct ListNode* deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    
    if (head->next && head->val == head->next->val) {
        /* Remove all duplicate numbers */
        while (head->next && head->val == head->next->val)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}
```
:::info
COND1 = `head->next && head->val == head->next->val`
COND2 = `head->next && head->val == head->next->val`
:::

### 迭代版本
```c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    
    struct ListNode *p = malloc(sizeof(struct ListNode));
    p->next = head;
    p->val  = head->val - 1;
    
    struct ListNode **indirect = &p;
    struct ListNode *trace = (*indirect)->next;

    while (trace) {
        while (trace && (!trace->next || (trace->next && trace->val != trace->next->val))) {
            indirect = &(*indirect)->next;
            trace = (*indirect)->next;
        }
        while (trace && (*indirect)->next->val == trace->val) {
            // struct ListNode *tmp = trace;
            trace = trace->next;
            // free(tmp);
        }
        (*indirect)->next = trace;
        trace = (*indirect)->next;
    }
    
    head = p->next;
    free(p);
    return head;
}
```

## 測驗 `3`
:::spoiler LeetCode 提交版
```c
#include <stdio.h>
#include <stdlib.h>

/*------------------------------------------------------------*/
// #include "list.h"
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;
}

static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

#define list_entry(node, type, member) container_of(node, type, member)

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)

#define list_for_each_entry(entry, head, member)                       \
    for (entry = list_entry((head)->next, __typeof__(*entry), member); \
         &entry->member != (head);                                     \
         entry = list_entry(entry->member.next, __typeof__(*entry), member))

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

/*------------------------------------------------------------*/

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

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;
    list_for_each_entry_safe (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}   

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    // hit
    list_for_each_entry (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }
    
    if (obj->count == obj->capacity) { // eviction
        lru = list_last_entry(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else { // miss
        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;
}
```
:::

:::info
- MM1 `list_for_each_entry_safe`
- MM2 `list_for_each_entry`
- MM3 `list_for_each_entry`
- MM4 `list_last_entry`
:::

## 測驗 `4`
:::spoiler LeetCode 提交版
```c
#include <stdio.h>
#include <stdlib.h>

/*------------------------------------------------------------*/
// #include "list.h"
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;
}

#define list_entry(node, type, member) container_of(node, type, member)

#define list_for_each_entry(entry, head, member)                       \
    for (entry = list_entry((head)->next, __typeof__(*entry), member); \
         &entry->member != (head);                                     \
         entry = list_entry(entry->member.next, __typeof__(*entry), member))

/*------------------------------------------------------------*/

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;
    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(--left, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(++right, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }
    return length;
}
```
:::

:::info
- LLL `--left`
- RRR `++right`
:::

