---
tags: linux2022
---
# 2022q1 Homework1 (quiz1)
contributed by < [`ShawnLu31`](https://github.com/ShawnLu31/2022_linux_quiz1) >
### [題目](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗 1
### 解題
`map_add` 分配一個節點空間，並將此節點放入 hash table 。
宣告完 `h` `n` 後：
`first` 指向該 hash table 的欄位的必一個節點，可能是 `NULL`，因此用 if 確認節點的的存在。
```c
AAA;
if (first)
first->pprev = &n->next;
h->first = n;
BBB;
```
對節點執行已知的操作後：
由此可得知 `n->pprev` 須指到 hlist_head， `n->next` 須指向原本的首位節點 `fisrt`。
- `AAA => n->next = first;`
- `BBB => n->pprev = &h->first;`
### Hash table
#### data struct
```c
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;
```
```c
/**
* @key, 儲存陣列 array 的元素
* @data, 儲存上述元素的索引值
* @node, 用於 hash table 中 bucket 的實作
*/
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
#### 建立 hash table
建立 hash table 。
分配 `map_t` 大小的空間。
依照參數 `bits` 分配 `hlist_head` 空間給 `ht` 指標。
做初始化，將所有 linked list 開頭指標指向 `NULL` 。
回傳 hash table 的指標 `map` 。
```c
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;
}
```
#### 搜尋節點
在 hash table 中搜尋並回傳一節點 `kn` ， 且 `kn->key` 等於 `key` 。
將 `key` 經過 hash function 計算後找到對應的 `hlist_head` ，依序走訪該 linked list 並檢查目標資料 `key` 是否存在該 linked list 中。若存在則回傳該節點 `kn` ，若不存在則回傳 `NULL`。
```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;
}
```
#### 獲取資料
呼叫 `find_key` 取得 bucket，回傳 bucket 中儲存的 `data` (索引值)。
```c
/**
* @param map, 目標 hash table
* @param key, 陣列 nums 中的元素
* @return void*
*/
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
#### 儲存資料
若資料不存在於 hash table ，則加入元素資料至 hash table 。
分配節點空間，儲存元素的數值與索引值。
經過 hash function 計算找對對應的 linked list 並加到 linked list 的開頭。
```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;
}
```
#### 清除 hash table
釋放 hash table 的空間。
走訪所有 hash table 的節點，將其從 linked list 移除後釋放其空間。
:::danger
TODO: why !n->pprev == /* unhashed */ ?
:::
```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);
}
```
#### Two Sum
給定一陣列 `nums` 和一個目標值 `target` ，回傳 `nums` 的 2 個元素相加會等於 `target` 的索引值。
建立 hash table `map`。
依序檢查陣列的元素， `map_get` 會在 hash table 尋找是否有元素與現在的元素相加為 `target` 。若存在， `p` 即為另一元素的索引值。若不存在，則用 `map_add` 將現在檢查的元素儲存至 hash table。
最後清除 hash table ，並回傳 2 個元素的索引值 `ret`。
```c
/**
* @param nums, 給定的陣列
* @param numSize, 陣列大小
* @param target, 目標值
* @param returnSize, 回傳的陣列大小，若有解為 2，無解則為 0
*/
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;
}
```
### 研讀 linux 核心程式碼
## 測驗 2
### 解題
刪除 Singly-linked list 裡所有重複的節點， 串列可能為空或 `NULL` 。
```c
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;
}
```
程式碼被 `if` 分成三個部分：
1. `head` 為 `NULL` 。
處理傳入的串列為 `NULL` 的情況，可能是原串列為 `NULL` 或遞迴到串列尾端的終止遞迴條件。
2. `head` 不為 `NULL`，且 `COND1` 成立。
處理刪除重複節點的部分。
`COND1` 檢查 `head` `head->next` 兩節點資料重複時，所以 `COND1` 為 `head->val == head->next->val` 。但傳入的 `head` 可能只有一個節點 (`head->next` 為 `NULL`)，所以須檢查 `head->next != NULL` 。所以 `COND1` 為
```
head->next && head->val == head->next->val
```
再透過 `while` 迴圈刪除其他重複數值的節點。當 `head`下一個節點 `head->next` 重複時，將 `head` 直接指到下一個節點 `head->next` ，跳過重複的節點 `head` 。且與 `COND1` 相同，走到最後一個節點時， `head->next` 會為 `NULL` ，所以 `COND2` 為
```
head->next && head->val == head->next->val
```
離開迴圈後，要繼續尋找並刪除下一個重複節點，所以再次呼叫 `deleteDuplicates` ，且因為 `head` 也是重複的節點，所以傳入 `deleteDuplicates` 的參數為 `head->next` 。
3. 非上述兩種情形。
因為重複的節點已被第二部分處理完，所以這裡的 `head` 不會是重複的節點，只需使用 `deleteDuplicates` 找到 `head->next` 要接的節點，在回傳 `head` 。
### 無遞迴版本
#### 迭代版
```c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
bool is_dup = false;
struct ListNode **indir = &head;
for (; *indir;) {
if ((*indir)->next && (*indir)->val == (*indir)->next->val) {
(*indir)->next = (*indir)->next->next;
is_dup = true;
} else {
if (is_dup) {
/* delete the last duplicated node */
(*indir) = (*indir)->next;
is_dup = false;
} else {
indir = &(*indir)->next;
}
}
}
return head;
}
```
使用指標的指標 `indir` 實作迭代版本。
比較兩個節點，若為重複節點則移除後者，直到重複的節點只剩一個(首個重複節點)，並用 `is_dup` 紀錄此節點是否為剩餘的重複節點。
### circular doubly-linked list 改寫
#### 遞迴
```c
void deleteDuplicates(struct list_head *head, struct list_head *l)
{
if (!head)
return;
if (list_empty(head) || list_is_singular(head))
return;
if (l == head)
return;
if (l->next != head && list_entry(l, ListNode, list)->val == list_entry(l->next, ListNode, list)->val) {
while (l->next != head && list_entry(l, ListNode, list)->val == list_entry(l->next, ListNode, list)->val) {
l = l->next;
list_del(l->prev);
}
l = l->next;
list_del(l->prev);
deleteDuplicates(head, l);
return;
}
deleteDuplicates(head, l->next);
return;
}
```
#### 迭代
```c
struct list_head *deleteDuplicates(struct list_head *head)
{
if (!head)
return NULL;
if (list_empty(head) || list_is_singular(head))
return head;
bool is_dup = false;
ListNode *node, *next;
list_for_each_entry_safe (node, next, head, list) {
if (node->val == next->val) {
// delete the duplicated node
list_del(&node->list);
free(node);
is_dup = true;
} else {
if (is_dup) {
// delete the last duplicated node
list_del(&node->list);
free(node);
is_dup = false;
}
}
}
return head;
}
```
## 測驗 3
### 解題
1. `MMM1`
觀察得知：
- `for` 迴圈的巨集。
- 迴圈內部會刪除節點 → `safe` 版本的巨集。
`MMM1` 為 `list_for_each_entry_safe`
2. `MMM2`
觀察得知：
- `for` 迴圈的巨集。
- 比對節點資料，若比對成功立即結束迴圈 → 不需 `safe` 保護。
`MMM2` 為 `list_for_each_entry`
3. `MMM3`
觀察得知：
- 用途與 `MMM2` 相同。
`MMM3` 為 `list_for_each_entry`
4. `MMM4`
觀察得知：
- 函式，回傳一個節點。
- 在 hash table 容量滿時使用，並移除該回傳節點的連結 → 刪除 LRU 的節點並使用其空間。
而在 lRUCacheGet 與前段 `MMM3` 的程式碼中，比對到的節點 (Used) 會使用 `list_move` 將該節點加入 `obj->dhead` 的首個節點，因此 `obj->dhead` 的最後一個節點就是 LRU 的節點。
`MMM4` 為 `list_last_entry`
| 題目 | 解答 |
| ----- | -------- |
| MMM1 | list_for_each_entry_safe |
| MMM2 | list_for_each_entry |
| MMM3 | list_for_each_entry |
| MMM4 | list_last_entry |
### 解釋程式碼
#### Cache 結構
- `capacity`, hash table 的容量大小。
- `count`, 已加入的資料數量。
- `dhead`, 快取，紀錄存取過資料的 linked list ，開頭為最近存取的資料，尾端則是 LRU 的資料。
- `hheads`, hash table 。
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
```
#### Node 結構
- `key`, 儲存的資料，用來計算 hash 值，幫助搜尋。
- `value`, 儲存的資料。
- `hlink`, 連接 hash table 的節點。
- `dlink`, 連接 `dhead` linked list 的節點。
```c
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
#### 建立 LRU Cache
```c
/**
* @brief 建立 cache 資料結構並初始化
*/
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
// 初始化變數
obj->count = 0;
obj->capacity = capacity;
// 初始化 dhead 與 hash table
INIT_LIST_HEAD(&obj->dhead);
for (int i = 0; i < capacity; i++)
INIT_LIST_HEAD(&obj->hheads[i]);
return obj;
}
```
#### 新增資料
```c
/**
* @brief 新增資料 (key, value)至 LRUCachee
*
* - 搜尋資料
* - 更新(資料存在)
* 1. 用 Hash(key) hash table 中尋找資料
* 2. 將該節點移至 dhead 首位 (Used)
* 3. 更新 value 資料
*
* - 加入資料
* - 取代(資料不存在，快取已滿)
* 1. 將 LRU 節點從 dhead 移除
* 2. 將 LRU 節點從 hheads 移除
* 3. 放入新的資料
* 4. 該節點重新連結至 dhead 與 hheads
*
* - 新增(資料不存在，快取未滿)
* 1. 配置節點空間
* 2. 放入新的資料
* 3. 該節點重新連結至 dhead 與 hheads
*
* @param obj, LRUCache 物件
* @param key, 用於比對的資料
* @param value, 欲新增的資料
*/
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *lru;
int hash = key % obj->capacity;
// 搜尋資料
list_for_each_entry(lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
// 資料存在，將該節點移至 dhead 首位
list_move(&lru->dlink, &obj->dhead);
// 更新 value
lru->value = value;
return;
}
}
// 新增資料
if (obj->count == obj->capacity) {
// 快取已滿
// 取得 LRU 的節點
lru = list_last_entry(&obj->dhead, LRUNode, dlink);
// 將該節點從 linked list 移除
list_del(&lru->dlink);
list_del(&lru->hlink);
} else {
// 快取未滿
// 配置節點空間
lru = malloc(sizeof(LRUNode));
obj->count++;
}
// 新資料加入節點
lru->key = key;
// 連接至 LRUCache
list_add(&lru->dlink, &obj->dhead);
list_add(&lru->hlink, &obj->hheads[hash]);
// 新資料加入節點
lru->value = value;
}
```
#### 取得資料
```c
/**
* @brief 在 LRUCache 中尋找資料並回傳
*
* 用 key 計算 hash 值並在該 hheads 欄位尋找資料
* 若找到資料回傳 value ，沒找到回傳 -1
*
* @param obj
* @param key
* @return int
*/
int lRUCacheGet(LRUCache *obj, int key)
{
LRUNode *lru;
int hash = key % obj->capacity;
// 走訪 hheads[hash] 欄位的 linked list
list_for_each_entry(lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
// 若找到資料將該節點移至 dhead 首位
list_move(&lru->dlink, &obj->dhead);
return lru->value;
}
}
return -1;
}
```
#### 清除 Cache
```c
/**
* @brief 清除 LRU cache
*
* 刪除 cache 中的節點後，再清除 cache
* 因為 dhead 和 hheads 是共用同樣的節點(LRUNode)
* 只是分別用 dlink, hlink 連接
* 用其中一個來刪除節點即可
*
* @param obj
*/
void lRUCacheFree(LRUCache *obj)
{
LRUNode *lru, *n;
list_for_each_entry_safe(lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
free(obj);
}
```
## 測驗 4
### 解題
```c
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);
}
```
`left` 和 `right` 分別往 `num` 的左右兩側在 hash table 中尋找有連續數值的節點，若找到長度 `len` 加一， 所以 `left` 會隨著迴圈減一， `right` 則會加一。而兩者的初始值都是 `num` ，在尋找前須先減一（加一），避免重複找到 `num` 。
`LLL` 為 `--left` 。
`RRR` 為 `++right` 。
### 解釋程式碼
#### 搜尋數值
在 hash table 中尋找數值是否存在。
根據 `hash` 值到對應的欄位搜尋數值 `num` 是否存在，若存在則回傳該節點，否則回傳 `NULL` 。
```c
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;
}
```
#### 計算最長的連續數值
分成兩部分：
1. 將陣列 `nums` 的元素加入 hash table。
2. 依據 hash table 計算最長的連續數值。
第一部分
迴圈依序檢查陣列 `nums` 的元素，因目標為計算連續的數值，重複的數值只須計入一次，所以需檢查該元素是否以存在 hash table ，若存在，跳過該元素，若不存在則將其加入 hash table 。
```c
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 迴圈依序在 hash table 尋找陣列 `nums` 的元素。若找到 `num` ，表示該數值尚未被計算過，使用 `while(node)` 迴圈計算連續數值長度 `len` 。若 `find` 回傳 `NULL` 表示該數值已被計算過，則跳過此元素，避免重複計算。
`while(node)` 迴圈裡，長度 `len` 加一，刪除 `num` 的節點，避免重複計算。
接著使用 `left` 和 `right` 變數分別向 `num` 的左右兩側尋找連續的數值是否存在， `left` 會隨著迴圈逐漸減一， `right` 逐漸加一。若是找到該數值的節點，使長度 `len` 加一並刪除該節點。
`length` 為該陣列最長連續數值長度， `len` 為單次迴圈計算最長連續數值長度，檢查 `len` 是否大於 `length`，更新 `length` 。
```c
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(--left, n_size, heads))) {
len++;
list_del(&node->link);
}
while ((node = find(++right, n_size, heads))) {
len++;
list_del(&node->link);
}
length = len > length ? len : length;
}
}
```
最後回傳 `length` 。
Sign in with Wallet
Connect another wallet