---
tags: Linux Kernel
---
# 2022q1 Homework1 (quiz1)
contributed by < `kevinshieh0225` >
> [作業需求](https://hackmd.io/@sysprog/B166rc3Jq)
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1)
部分參考 `freshLiver` 的[筆記](https://hackmd.io/DkeAf1ziR4Ggm4-2G5G0EA?view)作法進行改寫。
## 測驗 1 Hash Map Implementation
Two Sum 是在 leetcode 上的經典首選，讓大家見識到 hash table 演算法的妙用。本測驗希望我們進入到 hash table 內部實作中。
### hash table 實作結構
hash table (HT)的性質如下：輸入特定鍵（key），HT 將回傳其對應的值(value)。基於一對一關係，理想上可使索取的時間複雜度為 O(1)。
在 HT 的實作如下：由於建立一個能含括所有 key 的 HT 是不實際的，故我們先為 key 做編碼，對應到我們建立的有限目錄中，隨後以 linked list (ll)的結構將鍵值串接起來（如同我們先將資料分門別類，隨後從分類中尋找我們要的是否存在）。
(取自 [jserv](https://hackmd.io/@sysprog/linux2022-quiz1))
回到程式碼：map_t 建立 map ，其下會有 an array of hlist_head 。我們前面提到 key 會先編碼後置入目錄對應的 LL ，這裡即可看到我們會建立 $2^{bits}$ 個目錄與 LL 。
hash_key 與 hlist_node 即為 key/value 節點。在透過編碼後 hlist_node 被安插在對應目錄中，在尋鍵時透過尋訪 hlist_node 並以 container_of 取 hash_key 的值。
```c
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;
struct hlist_node { struct hlist_node *next, **pprev; };
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
#define container_of(ptr, type, member) \
({ \
void *__mptr = (void *) (ptr); \
((type *) (__mptr - offsetof(type, member))); \
})
```
### hash table init
我們可以看到 map_t 初始化的過程，可以看到我們同時建立了一個 map_t 與（1 << bits == $2^{bits}$）個 hlist_head，若建立中有失敗則清除內容並返回 NULL。
```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;
}
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);
}
```
### hash encode
執行 hash 的演算法。最後會生成並回傳一個 $[0, 2^{bits}-1]$ 範圍內的無號整數。
```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 find, get
**find_key function**：在 HT 中尋找是否有對應 key 值，若有則回傳對應的 hasy_key * ，若無則回傳 NULL。
這裡首先我們先確認 key 被放在哪一個編碼的 bucket 中，透過 **hash(key, map->bits)** 這個函式取得編碼，並在 array 中取得對應的 hlist_head。接著就是逐一尋訪該 LL 去確認是否有 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;
}
```
**map_get function**：從 HT 中確認是否有對應鍵值，若有則回傳鍵值對應的 value，若無則返還 NULL。
這裡特別的是此 function 的回傳值是 void pointer。這是一種很有彈性的作法，我們可以用 void pointer 去指不同的變數，再把它透過轉型（casting）還原回來。由於我們在這個實作中不確定是否能有對應的回傳鍵值，所以使用這個的方式，若回傳 NULL 即可讓 if-else 更直覺的判斷與執行對應操作。
```c
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
### map_add 與考試答案
**map_add function**：確認是否有在 HT 中有對應鍵值，若有則不執行，無則新增鍵值在 HT 中。
```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 到 BBB 的 程式碼意思是要將新的 hlist_node *n 插入在 hlisthead *h 的 first 位置，其中如果 h->first 早就已經有 hlist_node 時，我就插入兩者之間。
:::info
AAA 應為 (c\) n->next = first
BBB 應為 (a) n->pprev = &h->first
:::
## 測驗 2 : [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
本題透過遞迴的方式實現刪除重複節點的函式。其中：
:::info
COND1 = head.next != null && head.val == head.next.val
COND2 = head.next != null && head.val == head.next.val
:::
為何需要用 if 來包裝和裡面 while 相同的條件式呢？看似重複操作，但其實是因為條件內外執行操作是不同的行為，而必須在新增一個 if(COND1) 來隔離條件。
在 if(COND1) 內的操作是我們已經確定要移除當下重複的節點了，我們用 while 不斷將 head 重新指向其後，並在最後 return 遞迴中 head->next 的 ListNode 在這一番的操作下便可以把所有重複節點在這操作下完全移除。
相比於此，我們看 if(COND1) 外的操作：我們先對 head->next 後的節點進行 deleteDuplicates 的遞迴整理，最後回傳的還是 head node ，光是操作和回傳的形式都不同，而使他必須用 if(COND1) 來做內外切分。
### iterate version
```c
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
struct ListNode **ckp = &head;
struct ListNode *iter = (*ckp)->next;
while (iter) {
if ((*ckp)->val == iter->val) {
do {
iter = iter->next;
} while (iter && (*ckp)->val == iter->val);
*ckp = iter;
if (!iter)
break;
} else {
ckp = &((*ckp)->next);
}
iter = iter->next;
}
return head;
}
```
## 測驗 3 : [146. LRU Cache](https://leetcode.com/problems/lru-cache/)
在 Cache replacement policies 中，Least Recently Used 是一個策略之一。當 Cache 要更新時，將裡頭最後被使用的資料去除並更新。在 LRU 演算法我們面臨的問題是：如何在常數時間內達到兩件目的：如何確認 Cache hit、如何更新使用時間的紀錄。
### LRU Cache 實作原理：Hashmap + DoubleLinkedList
透過 Hashmap 可在常數時間裡「確認是否 Cache hit」；透過 DoubleLinkedList 讓我們在常數時間裡「更新 Cache 紀錄」。
這時可能會有一個問題是：如果要做 DoubleLinkedList 的尋訪，那應該也需要線性時間吧？然而我們如果搭配著 list.h 與 container_of 的技巧：在 Hashmap 與 DoubleLinkedList 上使用**共用**的 list_head 節點，那麼當我要維護 DoubleLinkedList 時，只要從 Hashmap 取得該節點更新；或是當我要刪除最近未使用的節點時，從 DoubleLinkedList 找到最末的節點。
LRUNode 是紀錄在 LRUCache 中的 DoubleLinkedList(DLL) 節點。
我們觀察 LRUCache，dhead 與 hheads[] 分別就是 DLL 的首節點，與第一題類似形式的 Hashmap 實作。
capacity 代表 Cache 的大小， count 代表目前總共有多少筆資料存放其中。
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
### LRU Cache create/free
在 lRUCacheCreate 中我們初始化紀錄使用時間 DLL 的 dhead，和紀錄是否存在其中的 Hashmap hhead[]。
在 lRUCacheFree 中我們也針對這些建立的動態記憶體位置依序釋放。
:::info
MM1 應填入 list_for_each_entry_safe ，在 DLL 中依序釋放節點，並不斷確認下一個節點是否為安全節點。
:::
```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);
}
```
### LRU Cache Get
輸入整數 key，如果其值有在 hashmap 中找到，更新 &obj->dhead 的 DLL結構，把該節點更新到開頭，代表最近使用，並回傳該 lru->value；若未找到則回傳 -1。
這裡可以看到這裡的編碼方式是 key 值除 capacity 得到 $[0, capacity-1]$ 的 hash ，相比前面的編碼來看是比較簡易的實作。
:::info
MMM2 應該是 list_for_each_entry。用該函數去尋訪 &obj->hheads[hash] 中的每個節點來確認是否該資料已存在於 hashmap 中。
:::
```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;
}
```
### LRU Cache Put
```c=
/**
* @brief 插入新的鍵值並更新 Cache
*
* @param *obj LRUCache
* @param key 鍵
* @param value 值
*/
void lRUCachePut(LRUCache *obj, int key, int value)
{
/**
* @ brief 執行 lRUCacheGet 行動：
*
* 確認該 key 是否已存在於 Cache 中
* 尋訪 LRUCache 的 HashTable
* 若存在則更新 DLL 與該節點對應的 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;
}
}
/**
* 確認此時的 Cache 存放容量（count）是否已經達到上限
* if 到達上限，準備更新最近未使用的節點資料
* else 未達到上限，建立新節點並更新 count 的大小
*/
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 節點進行更新
*/
lru->key = key;
list_add(&lru->dlink, &obj->dhead);
list_add(&lru->hlink, &obj->hheads[hash]);
lru->value = value;
}
```
:::info
MMM3 應填入 list_for_each_entry。
:::
:::danger
MMM4 應填寫 list_last_entry 取得 DLL 中最後一個節點，意即是最近未使用的節點。
答案卻是 list_for_each_entry？有點怪。
:::
## 測驗 4 : [128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)
### 程式碼解析
```c
/**
* @brief LL 節點結構
*/
struct seq_node {
int num;
struct list_head link;
};
/**
* @brief 尋訪 HashTable 中是否存在該資料
*
* 對 @num 取絕對值並編碼出所屬欄位
* 尋訪該欄位確認是否存在該筆資料
*
* @param num 目標數值
* @param size HT 大小（欄位大小）
* @param *heads HT 的首節點
* @return if true struct seq_node*; else NULL;
*/
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;
}
```
```c
/**
* @brief 從一組整數陣列中，回傳最長的連續數組
*
* 1. 建立欄位數 = n_size 大小的 HashTable
* 2. 將整數陣列的數值插入進 HashTable 中
* 3. 尋訪最長連續數組
*
* @param *nums 整數陣列
* @param n_size 陣列之大小
*/
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]);
}
}
/**
* @brief 尋訪最長連續數組
*
* length : 搜尋截至目前最長的連續數組
* len : 本次搜索中的連續數組長度
*
* for 迭代過所有的陣列數值
*
* len 重置為 0
* 如果 node 存在於 HT 中，則開始尋找與其相連的連續數組
*
* while 向左 LLL = --left 搜尋連續數組
* 若有則增加 len 長度，並刪除 HT 上該節點
* while 向右 RRR = ++right 搜尋連續數組
* 若有則增加 len 長度，並刪除 HT 上該節點
*
* 比較 length 與 len 的長度進行更新
*
* 最後回傳 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;
}
```
:::info
LLL = \-\-left
RRR = \+\+right
:::
Sign in with Wallet
Connect another wallet