---
tags: linux2022
---
# 2022q1 Homework (quiz1)
contributed by < `hankluo6` >
> [第 1 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗 `1`
### 運作原理
```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`
`map_add` 將新的節點加入到 hash 中，`find_key` 先從 hash 檢查該 key 是否已經存在，如果已經存在則直接回傳，尚未存在則分配新的記憶體放置 `data`。故可知 `AAA` 及 `BBB` 為將新的節點連接到 hash 上的 linked list，且為插入到 linked list 的前端。
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0> map.ht[0] | <f1> map.ht[1] |<f2> map.ht[2]",height=1.2];
old_data [height=0.4];
"map.ht"[height=0.4,color=white];
node0:f0->old_data [label=first];
old_data->node0:f0 [label=prev];
{ rank="same"; "map.ht"; }
}
```
* add new item
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0> map.ht[0] | <f1> map.ht[1] |<f2> map.ht[2]",height=1.2];
old_data [height=0.4];
new_data [height=0.4];
"map.ht"[height=0.4,color=white];
node0:f0->new_data [label=<<font color="red">first</font>>, color=red];
new_data->node0:f0 [label=<<font color="red">prev</font>>, color=red];
new_data->old_data [label=next];
old_data->new_data [label=prev];
{ rank="same"; "map.ht"; }
}
```
```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);
}
```
`map_deinit` 釋放所有 hash 的記憶體，`for` 迴圈遍歷所有 hash entry，內部在一個一個把 linked list 上的節點及其 data 釋放。在遍歷每個節點時，同時透過指標的指標更改 `head->firt` 及 `next->prev`。
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0>map.ht[0]|{<f1>first.addr|<f2>first}",height=0.4];
data1 [label = "<f0>data1|{<f1>pprev|<f2>next}|<f3>node.addr", height=0.4];
data2 [label = "<f0>data2|{<f1>pprev|<f2>next}|<f3>node.addr", height=0.4];
node0:f2->data1:f0;
data1:f1->node0:f1;
data1:f2->data2:f0;
data2:f1->data1:f3;
"map.ht"[height=0.4,color=white];
}
```
* 刪除的節點 `n` 為 `data1`。
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0>map.ht[0]|{<f1>first.addr|<f2>first}",height=0.4];
data1 [label = "<f0>data1|{<f1>pprev|<f2>next}|<f3>node.addr", height=0.4];
data2 [label = "<f0>data2|{<f1>pprev|<f2>next}|<f3>node.addr", height=0.4];
node0:f2->data1:f0;
data1:f1->node0:f1 [label=pprev];
data1:f2->data2:f0 [label=next];
data2:f1->data1:f3;
"map.ht"[height=0.4,color=white];
"n"[height=0.4,color=white];
{rank=same;"n";data1};
}
```
* 將 `pprev` 的**指標內指向的值**(`map.ht[0].first`)設為 `next`；`next` 的 `prev` 設為 `pprev` 指標的指標，並把 `n` 的 `prev` 及 `next` 設為 `NULL`，最後釋放。
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0>map.ht[0]|{<f1>first.addr|<f2>first}",height=0.4];
data1 [label = "<f0>data1|{<f1>pprev|<f2>next}|<f3>node.addr", height=0.4];
data2 [label = "<f0>data2|{<f1>pprev|<f2>next}|<f3>node.addr", height=0.4];
node0:f2->data2:f0;
data2:f1->node0:f1;
"map.ht"[height=0.4,color=white];
"n"[height=0.4,color=white];
"n"->"map.ht"[color=white];
{rank=same;"n";data1};
{rank=same;node0;"map.ht"};
}
```
### Linux `hashtable`
#### `DEFINE_HASHTABLE` & `DECLARE_HASHTABLE`
```c
#define DEFINE_HASHTABLE(name, bits) \
struct hlist_head name[1 << (bits)] = \
{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
#define DECLARE_HASHTABLE(name, bits) \
struct hlist_head name[1 << (bits)]
```
以 `hlist_head` 當作每個 hash table 上每個 bucket 的 list，其中不用 `list_node` 的原因為不需要用到 circular linked list。`bits` 決定需要 hash table 的大小。
特別要注意的為初始化 `name` 時使用的 `...` 為 GCC extension 的 [Designated Initializers](https://gcc.gnu.org/onlinedocs/gcc/Designated-Inits.html)，可以一次初始化所有 index 為 `HLIST_HEAD_INIT`。
`HLIST_HEAD_INIT` 定義在 `list.h` 內，及初始化 `first` 為 `NULL`。
#### `hash_init`
```c
static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
{
unsigned int i;
for (i = 0; i < sz; i++)
INIT_HLIST_HEAD(&ht[i]);
}
#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
```
專門將 `DECLARE_HASTABLE` 宣告的 hash table 初始化，作用與 `DEFINE_HASTABLE` 相同。
#### `hash_add` & `hash_del`
```c
#define hash_add(hashtable, node, key) \
hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
static inline void hash_del(struct hlist_node *node)
{
hlist_del_init(node);
}
```
`add` 與 `del` 都為呼叫 `hlist` API，其實作皆與 `list_head` 相似。
#### `hash_for_each`
```c
#define hash_for_each(name, bkt, obj, member) \
for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
(bkt)++)\
hlist_for_each_entry(obj, &name[bkt], member)
```
遍歷 hash table **所有**的 entry，`bkt` 表示 bucket，每一次迴圈透過 `hlist_for_each_entry` 遍歷這個 bucket 內的 linked list。
### GOLDEN_RATIO
```c
#define GOLDEN_RATIO_32 0x61C88647
#define GOLDEN_RATIO_64 0x61C8864680B583EBull
```
:::info
註解中的 `phi = (sqrt(5)-1)/2` 指的是 $\phi^{-1}$，為 golden ratio 的倒數。
:::
* $\text{0x61C88647}=\text{1640531527}=2^{32}\times\phi^{-1}=2^{32}\times\frac{\sqrt{5}-1}{2}$
* $\text{0x61C8864680B583EB}=\text{7046029254386353842}\approx2^{64}\times\phi^{-2}=2^{64}\times\frac{3-\sqrt{5}}{2}$
任意數乘上這兩個數再取其高位元可以呈現好的數值分布。在連續的數值中，利用這種 Fibonacci Hashing 方法可以將 hash 後對應的值分散到其他 hash value 的值之間 (將最大區間以 golden ratio 分割的點)。
而現實生活上的 keys 值分布常常會有某種數值分布，類似 $\{K, K+d, K+2d, ..., K+td\}$，例如字串集合 $\{"PART1", "PART2", "PART3"\}$，這種情況利用此種 hash function 的行為就如同計算 $h(0), h(1), h(2)$，便能將 key 值映射到沒有使用過的 value，減少 collision 的機率。
假設 $\theta$ 為一有理數，要將 $\{\theta, 2\theta, 3\theta, ..., n\theta\}$ 的小數部分放到 $[0, 1]$ 之間，則會發現 $(n+1)\theta$ 放置的位置會在由前面的點分割成的線段中最長的線段，而當 $\theta$ 過大或過小時 (接近 0 或 1)，產生的分布區間便會由小而大，並不是均勻分布。
可證明能產生較好的分布的數值為 $\phi^{-1}$ 及 $\phi^{-2}$ (Knuth vol 3, section 6.4, exercise 9.)，故選擇這兩個數計算 hash。
* Reference: [The Art of Computer Programming, section 6.4](https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/The%20Art%20of%20Computer%20Programming%20%28vol.%203_%20Sorting%20and%20Searching%29%20%282nd%20ed.%29%20%5BKnuth%201998-05-04%5D.pdf)
## 測驗 `2`
### 運作原理
#### `COND1`
- `head->next && head->val == head->next->val`
#### `COND2`
- `head->next && head->val == head->next->val`
根據註解可知道第二個 `if` 用來刪除重複的節點，故 `COND1` 應為判斷是否有重複的值。在 `if` block 裡面最後回傳 `head->next`，可知道中間 `while` 迴圈需跳過相同值的節點，最後停在所有有著相同值的節點中的最後一個節點，得出 `COND2`。
### 改寫
```c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
struct ListNode *newhead = malloc(sizeof(struct ListNode));
newhead->next = head;
struct ListNode *prev = newhead;
while (head) {
if (head->next && head->val == head->next->val) {
while (head->next && head->val == head->next->val) {
head = head->next;
}
prev->next = head->next;
} else {
prev = prev->next;
}
head = head->next;
}
return newhead->next;
}
```
## 測驗 `3`
### 運作原理
#### `MM1`
- `list_for_each_entry_safe`
#### `MM2`
- `list_for_each_entry`
#### `MM3`
- `list_for_each_entry`
#### `MM4`
- `list_last_entry`
LRU 由兩個部分組成
* `dhead`：為 doubly-linked list，用來取得 **Least Recently Used** 的 node，靠近頭端部分表示存取時間與當前時間越近，靠近尾端則越遠。
* `hheads`：為 hash map，用來儲存 key 及 value 的資訊，以 `key % capacity` 當作 hash function。
`GET` 操作時，從對應的 hash 值的 list 中尋找，如果有找到，透過 `list_move` 將該 node 移到 `dhead` 的頭端，表示最近使用。故 `MM2` 為 `list_for_each_entry` 遍歷對應 hash 上的 list。
`PUT` 操作時，先檢查該 key 是否有存在 hash map 當中，故 `MM3` 與 `MM2` 相同，如果不存在，則要新建一個新的 node，此時若 LRU 已滿，必須剔除掉最久沒使用的節點，該節點及為 `dhead` 的 tail，故 `MM4` 為 `list_last_entry`。建立完新的節點後，再放到 `dhead` 及對應的 `hhead` 頭端。
`CREATE` 操作時，必須將所有 `list_head` 透過 `INIT_LIST_HEAD` 初始化，把相對應的 `next` 與 `prev` 欄位設定，list 相關巨集才能正確使用。
`FREE` 操作時，因為每個存在於 hash map 的 node 都與 `dhead` 鏈結，所以只要遍歷 `dhead` 釋放所有節點即可。
* 初始化，capacity 為 3
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0> hheads[0]<style></style> | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
"dhead"[height=0.4];
{ rank="same"; node0; "dhead" }
}
```
* push item1 (hash value: 0)
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0> hheads[0] | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
"dhead"[height=0.4];
"item1:hlink"[height=0.4];
"item1:dlink"[height=0.4];
node0:f0->"item1:hlink";
"dhead"->"item1:dlink";
{ rank="same"; node0; "dhead" }
}
```
* push item2 (hash value: 1)，新建立的 node 放到 list 的頭端
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0> hheads[0] | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
"dhead"[height=0.4];
"item1:dlink"[height=0.4];
"item2:dlink"[height=0.4];
node1 [label = "<f0> item1:hlink | <f1> item2:hlink",height=0.8];
node0:f0->node1:f0;
node0:f1->node1:f1;
"dhead"->"item2:dlink"->"item1:dlink";
{ rank="same"; node0; "dhead" }
}
```
* push item3 (hash value: 0)
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0> hheads[0] | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
"dhead"[height=0.4];
"item1:hlink"[height=0.4];
"item1:dlink"[height=0.4];
"item2:dlink"[height=0.4];
"item3:dlink"[height=0.4];
node1 [label = "<f0> item3:hlink | <f1> item2:hlink",height=0.8];
node0:f0->node1:f0->"item1:hlink";
node0:f1->node1:f1;
"dhead"->"item3:dlink"->"item2:dlink"->"item1:dlink";
{ rank="same"; node0; "dhead" }
}
```
* push item4 (hash value: 2)，因為 LRU 空間已滿，將最久未使用的節點 (item1) 移除
```graphviz
digraph linked_list{
rankdir = LR;
node [shape = record];
node0 [label = "<f0> hheads[0] | <f1> hheads[1] |<f2> hheads[2]",height=1.2];
"dhead"[height=0.4];
"item3:dlink"[height=0.4];
"item2:dlink"[height=0.4];
"item4:dlink"[height=0.4];
node1 [label = "<f0> item3:hlink | <f1> item2:hlink | <f2> item4:hlink",height=1.2];
node0:f0->node1:f0;
node0:f1->node1:f1;
node0:f2->node1:f2;
"dhead"->"item4:dlink"->"item3:dlink"->"item2:dlink";
{ rank="same"; node0; "dhead" }
}
```
:::info
`item:dlink` 與 `item:hlink` 為同一個物件中的不同成員
:::
---
## 測驗 `4`
### 運作原理
#### `LLL`
- `--left`
#### `RRR`
- `++right`
`longestConsecutive` 內的第二個 `for` 迴圈將 `nums` 陣列中出現的所有數字以 hash map 存起。第三個 `for` 迴圈遍歷整個陣列，每次迴圈有個 current value 當作基準點，`left` 表示往小於 current value 的方向從 hash map 中尋找；`right` 表示往大於 current value 的方向尋找。因為要尋找**連續**的序列，故每次都以加一或減一的值尋找，得出 `--left` 及 `++right`。每找到一個數字與 current value 為連續序列，則將其從 hash map 中移除，下次迴圈選到相同序列內的數就不需要重新計算。
### 改寫
```c
struct seq_node {
int num;
struct hlist_head link;
};
static struct seq_node *find(int num, int size, struct hlist_head *map)
{
struct seq_node *node;
int hash = num < 0 ? -num % size : num % size;
hash_for_each_possible (node, map, link) {
if (node->num == num)
return node;
}
return NULL;
}
int longestConsecutive(int *nums, int n_size)
{
DEFINE_HASHTABLE(map, n_size);
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];
hash_add(map, node, 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;
hash_del(&node->link);
int left = num, right = num;
while ((node = find(LLL, n_size, heads))) {
len++;
hash_del(&node->link);
}
while ((node = find(RRR, n_size, heads))) {
len++;
hash_del(&node->link);
}
length = len > length ? len : length;
}
}
return length;
}
```
Sign in with Wallet
Connect another wallet