---
tags: linux2022
---
# 2022q1 Homework1 (quiz1)
contributed by < `BensonYang1999` >
> [第 1 周測驗題](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗1
### 延伸題目
#### 解釋上述程式碼運作原理
* 資料結構
* `map_t` 包含 `bits` 及 `ht` ，bits儲存hash table的大小( `1<<bits` )，`ht` 為指向 `hlist_head` 的指標
* `hlist_head` 中只有一個指標 `first` ，指向 `hlist_node`
* `hlist_node` 包含 `pprev` 及 `next` ， `pprev` 指向前一個node， `next` 指向後一個node；這裡比較特殊的地方 `pprev` 是用指標的指標，可以快速修改節點的連結。
* `hash_key` 包含 `key, data, node`
```graphviz
digraph {
layout = neato;
splines = curved;
overlap = false;
compound = true;
subgraph map_t {
label = "map_t"
node [shape=record]
node_map [label="{map_t|bits|<ht>ht}" pos="0,-2.5!"]
}
subgraph hlist_head {
label = "hlist_head"
node [shape=record]
node_head [label="{hlist_head.first|<f0>[0]|<f1>[1]|<f2>[2]|<f3>[3]|.\n.\n.\n | [1\<\< bits-1]}" pos="1.5,-3!"]
}
subgraph hlist_node {
label = "hlist_node"
node [shape=record]
node_01 [label="{hlist_node|{<p01>**pprev | <n01>*next}}" pos="4,-2.5!"]
node_02 [label="{hlist_node|{<p02>**pprev | <n02>*next}}" pos="6.5,-2.5!"]
node_10 [label="{hlist_node|{<p10>**pprev | <n10>*next}}" pos="4, -4!"]
}
null1 [label="NULL" shape=box pos="8, -2.5!"]
null2 [label="NULL" shape=box pos="6, -4!"]
// link
node_map:ht -> node_head
node_head:f0 -> node_01
node_01:n01 -> node_02:w
node_02:n02 -> null1
node_head:f1 -> node_10
node_10:n10 -> null2
{
edge [color=gray]
node_01:p01 -> node_head:f0
node_02:p02 -> node_01
node_10:p10 -> node_head:f1
}
}
```
:::info
第一次使用 `graphviz`，對 arrow 的調整還不熟悉，會發生edge與node邊框重疊的問題，不確定要怎麼解決。
:::
:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
不要急著說「第一次使用」，你很快會接觸一堆工具，理工人說話要精準且資訊量充足。
:notes: jserv
:::
* twoSum流程
1. 建立一個map，並設定大小為`10<<bits`
2. 進入迴圈，走訪陣列中的每個數字
1. 先將每個數值都透過`map_get`測試是否有匹配的數值，若匹配成功回傳正確的組合
2. 若找不當組合，則將此數字加入到hash table
3. 將所有創建的記憶體清除
* function說明
* map_init
目的：初始化`map`，建立適當大小的hash table
1. 利用malloc配置空間存放map
```c
map_t *map = malloc(sizeof(map_t));
if (!map)
return NULL;
```
2. 配置hash table的記憶體空間，並將所有head的first指標先指向NULL
```c
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;
```
* find_key
目的：尋找`key`是否存在在hash table中
先找到符合的`head`後，造訪其中的所有`node`，尋找相同`key`的`node`
* map_get
目地：利用`find_key`找到符合的節點後，回傳其原始數值的陣列代碼。
* map_add
目地：將原始數值利用hash轉換後，存入hash table，並紀錄陣列代碼。
詳細步驟：
1. 先確保要插入的值不存在在hash table中 (3~5)
2. 配置空間存放hash_key (7, 8)
3. 找到應當插入的hash table欄位 (10)
4. 找到新節點的記憶體位置n及原本存在欄位中的節點first (11)
5. 將新節點的next指向原本存在欄位中的節點first，因此本位置應填入`n->next = first;` (12)
6. 若原節點存在，須修改該節點的prev (13, 14)
7. 將head接到新節點上 (15)
8. 最後應將新節點的prev連接到head，因此本位置應填入`n->pprev = &h->first;` (16)
```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;
}
```
* map_deinit
目的：把整個map中所有的 `map, hash_key, node` 清空
#### 研讀 Linux 核心原始程式碼及對應的文件，解釋 hash table 的設計和實作手法，並留意到 `GOLDEN_RATIO_PRIME` ，探討其實作考量
* linux 核心利用 Seperate chaining 方式解決衝突
* 利用 number of bits 定義 hash table 的大小
* 利用 golden ratio constants 可有效達成高度隨機
---
## 測驗2
思路：兩個判斷式都須考慮`下一個節點是否存在`以及`此節點與下一個節點是否擁有相同數值`，因此適當的程式碼為`head->next && head->val == head->next->val`
```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;
}
```
### 延伸問題
#### 嘗試避免遞迴，寫出同樣作用的程式碼
* 版本一(for leetcode 83)：建立一個新的指標`node`指向`head`，利用判斷式確認是否有相同的值，當相同時將當前節的`next`接到`next->next`，代表忽略掉下一個節點，當不同時則直接將指標到下一個點
此版本特點在於會保留重複的數字，不會將其全部刪除
```c=
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
struct ListNode *node = head;
while (node->next) {
if (node->val == node->next->val) {
node->next = node->next->next;
}
else {
node = node->next;
}
}
return head;
}
```
* 版本二(for leetcode 82)：利用指標`node`及指標的指標`dnode`，透過迴圈將所有重複的數字跳過，並利用`dnode`把list接到下一個數字
此版本特點在於會將重複的數字全部刪除，不會剩下一個
```c=
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
struct ListNode *node = head, **dnode = &head;
while (node) {
if (node->next && node->val == node->next->val) {
while (node->next && node->val == node->next->val)
node = node->next;
*dnode = node->next; // 將dnode指向的指標（一開始為head)指向的下一個（不重複）的節點
node = node->next;
}
else {
dnode = &((*dnode)->next); // 將dnode指向下一個節點
node = node->next;
}
}
return head;
}
```
#### 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼
---
## 測驗3
## 參考資料
* [graphviz position](https://stackoverflow.com/questions/5343899/how-to-force-node-position-x-and-y-in-graphviz)
Sign in with Wallet
Connect another wallet