---
# System prepended metadata

title: 2022q1 Homework1 (quiz1)
tags: [linux2022]

---

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

圖解如下

![](https://i.imgur.com/Pljk3VD.png)
![](https://i.imgur.com/ezoBig5.png)
![](https://i.imgur.com/s6Uu6NW.png)

### 類似 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)