---
tags: linux2022
---
# 2022q1 Homework1 (quiz1)
contributed by < `Chao-Shun-Cheng` >
## 測驗 `1`
### 程式碼解釋
#### `map_init`
`map_init` 會建立 $2^n$ 個大小的雜湊表，如下圖所示。其中 `ht` 會指向 `2^n * sizeof(struct hlist_head)` 的連續記憶體空間。
```graphviz
digraph feature {
node [shape=box];
struct0 [label="map"];
rankdir=LR;
node [shape="record"];
struct1 [label="{<bits>bits|<ht>ht}"];
struct2 [label="{<one>first|<two>first|<three>first|<four>...|<n>first}"];
struct0->struct1:bits
struct1:ht->struct2:one
}
```
```c=1
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;
}
```
首先第七行用 `malloc` 建立 `hashtable` 所需要的連續記憶體空間，空間大小為 $2^b$ 個 `sizeof(struct hlist_head)`
```c=7
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
```
再來就是進行初始化的部分，使得 `hashtalbe` 都沒指向任何內容。
```C=9
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
(map->ht)[i].first = NULL;
```
#### `find_key`
`find_key` 有兩個輸入參數，分別是 `map` 跟 `key` ，會從 `map` 去尋找有沒有符合的 `key` ，有找到就會回傳對應的 `hash_key` ，否則就回傳 `NULL`。
```c=1
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;
}
```
首先可以看到第二行，`hash` 是雜湊函式，會利用 `key` 去找到 `hash table` 中對應的 `hlist_head`
```c=2
struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
```
```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);
}
```
不同的 `key` 經過雜湊函式計算後可能得到同樣的結果，所以會在用一個 `for` 迴圈去看每個結果的 `key` 是不是跟 `input` 的 `key` 一樣，一樣的話就代表有找到，會回傳找到的 `hash_key`。第三到第七行就是在進行這個功能。
```c=3
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;
}
```
其中 `container_of` 可以從一個結構體中的每個成員，去得到結構體的最前面的地址，詳細可以參考[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
#### `map_get`
`map_get` 搭配 `find_key` 去使用，目的是用來查看是否已經存在。
```c=1
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` 會將資料存進 `hash_table` 當中。
```c=1
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;
}
```
首先看到第三行，如果 `key` 已經存在 `hash_table` 當中，就不用再加進去 `hash_table`。
```c=3
struct hash_key *kn = find_key(map, key);
if (kn)
return;
```
如果找不到則會利用 `malloc` 分配一個 `hash_key` 的空間，並且初始化。
```c=7
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
```
接著利用雜湊函式 `hash` 找出要放置在 `hash_table` 的位置，並用 `h` 指著 `hlist_head`。另外 `n` 指向剛剛建立的 `hash_key` 當中的 `node` 、`first` 則指向 `h` 當中的第一個 `node`。
```c=10
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
```
緊接著要將剛剛建立的 `node` 插入進 `list` 的頭，以下是對應的操作。`n->next` 要指向原本的 `first` ，所以 `AAA` 是 `n->next = first` ；再來要去要去看原本到底有沒有 `first` ，如果本來有，則要調整原本 `first` 的 `pprev` (13、14 行)；最後要將插入的 `node` 的 `pprev` 指回去 `list` ，所以 `BBB` 是 `n->pprev = &h->first`。
```c=12
AAA; // n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
BBB; // n->pprev = &h->first;
```
#### `twoSum`
`twoSum` 利用上面所建立的 `hash table` 的操作來進行實作。
```c=1
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;
}
```
首先利用 `map_init` 初始化 `map` 所需要的空間 (第 3 行)，以及用 `malloc` 建立回傳答案所需要的空間 (第 5 行)。
```c=3
map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
```
接下來是利用一個 `for` 迴圈去建立 `hash_table` 與查找 `key`。如果 `key` 可以從 `hash table` 中找到就回傳答案，如果找不到，就將 `key` 加進去 `hash_table` 當中。
```c=9
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);
}
```
`hash table` 如何使用在 `twoSum` 可以參考 [2022q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz1#2022q1-%E7%AC%AC-1-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)之說明。
## 測驗 `2`
### 程式碼解釋
#### `deleteDuplicates`
`deleteDuplicates` 要可以將所以重複出現的 `Node` 都 `delete` 掉，以下是實作方式。
```c=1
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
if (COND1) { // head->next && head->val == head->next->val
/* Remove all duplicate numbers */
while (COND2) // head->next && head->val == head->next->val
head = head->next;
return deleteDuplicates(head->next);
}
head->next = deleteDuplicates(head->next);
return head;
}
```
首先可以注意到我們需要去比較下一個 `node` 與現在的 `node` 是不是一樣的值，所以要先確定有下一個 `node` ，再去看下一個 `node` 的值，因此 `COND1` 就會是 `head->next && head->val == head->next->val` ；緊接著可以看到有提示 `/* Remove all duplicate numbers */` ，因此可以知道 `while` 迴圈會去把相同的 `node` 都 `delete` 掉。因此 `while` 的條件就會是要有下一個 `node` 並且值是一樣的，因此 `COND2` 就是 `head->next && head->val == head->next->val`。
## 測驗 `3`
### 程式碼解釋
#### `lRUCacheCreate`
`lRUCacheCreate` 會依據 `capacity` 的大小，建立出相對應的空間，並且將 `dhead` 與 `hheads` 進行初始化。
```c=1
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;
}
```
其中在第三行的 `sizeof(*obj)` 其實與 `sizeof(LRUCache)` 是一樣的。
#### `lRUCacheFree`
`lRUCacheFree` 會將 `obj->dhead` 之所有 `Node` 給釋放掉。因此 `MM1` 會是 `list_for_each_entry_safe` 用來去歷遍所有的 `Node entry`。
```c=1
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
#### `lRUCacheGet`
`lRUCacheGet` 會利用 `key` 去看目前的 `hheads` 當中有無一樣的 `key` ，如果有就代表有存在 `cache` 當中。因此 `MM2` 是要用來歷遍 `bucket` 的，所以會是 `list_for_each_entry`。
```c=1
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;
}
```
#### `lRUCachePut`
`lRUCachePut` 可以分成三個部分，首先是已經存在 `cache` 當中，要把 `node` 更新到 `list` 最前面；再來就是如果 `cache` 容量已經滿了，要把最舊的 `node` 移除，並且放進新的 `node`；最後就是還有空間，可以直接放進去新的 `node`。
```c=1
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;
}
```
可以發現這邊就是要找尋是不是已經在 `cache` 當中，因此要歷遍 `bucket` 去看有沒有符合的 `key`。因此 `MM3` 是 `list_for_each_entry`。假如有找到就會進行第七行，將這個 `node` 移至 `list` 最前方。
```c=5
MMM3 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
```
這邊則是判斷還有沒有容量，假如容量不夠，就要移除最舊的 `node`，所以 `MM4` 會是 `list_last_entry` ，用來移除 `list` 中最後面的 `node`。
```c=13
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++;
}
```
## 測驗 `4`
### 程式碼解釋
#### `find`
`find` 會去從 `bucket` 當中去尋找是否有對應的數字 `num`。
```c=1
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;
}
```
#### `longestConsecutive`
`longestConsecutive` 是利用 `hash table` 將資料先分成不同 `bucket` 再找出最長的連續數字。
```c=1
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;
}
```
首先看到這個 `for` 迴圈，會把每個數字經過 `hash fuction` 計算後，放進對應的 `bucket` 當中。
```c=10
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` 迴圈去看每個 `node`。第 23 ~ 26 行會把 `node` 的 `num` 提出來並且移出 `bucket`；緊接在再往 `num + 1` 與 `num - 1` 去尋找是否有對應的 `node`，有的話就繼續找，直到不連續為止。因此可以得知 `LLL` 是 `--num` 而 `RRR` 是 `++num`。
```c=19
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;
}
}
```
Sign in with Wallet
Connect another wallet