# 2022q1 Homework (quiz1)
contributed by <`ray90514`>
[題目](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗一
```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;
}
```
這段程式碼的用途是要將 key 加入到 hashtable 裡，而後半段的程式碼是將建立的節點加入給定的 list 。
```c
struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
```
由圖可以看出有四個指標需要修改 `h->first`, `n->pprev`, `n->next`, `first->prev` ，上述程式碼已經修改了兩個，所以 `AAA` 和 `BBB` 是修改 `n` 的兩個指標。
```c
n->pprev = &h->first;
n->next = first;
```
### 延伸問題
程式的運作如下，給定一個 `sum` 及一個數字 `num` ，我們需要看 `sum - num` 是否在陣列裡面，比較快速的作法是對將陣列的數字建成 hashtable ，這樣查找一個數字只需要 $O(1)$ ，確認整個陣列要 $O(n)$ 。這裡有個細節是查找與建立 hashtable 可以同時進行，這樣就一次迴圈就能完成。
## 測驗二
```c
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
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;
}
```
這段程式碼是採用遞迴的方式移除重複的節點的。
```c
head->next = deleteDuplicates(head->next);
```
這一行是將 `head` 與以 `head->next` 為開頭被移除重複節點的串列接在一起，代表 `head->next` 以前都是不重複的。所以中間那段程式碼是要從 `head` 開始移除重複的節點。 `head` 有重複的條件，因為要比較 `head->next` 的值所以要加上判斷不為空指標， `COND1` 就是 `head->next && head->val == head->next->val` ，如果有重複發生，接下來就是要使用迴圈找出所有重複的節點，所以 `COND2` 與 `COND1` 相同。
### 延伸問題
#### 使用迴圈修改程式碼。
```c
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *deleteDuplicates(struct ListNode *head)
{
int is_dup = 0;
struct ListNode *node = head;
struct ListNode **prev = &head;
while (node) {
if(node->next && node->val == node->next->val) {
is_dup = 1;
}
else if (is_dup) {
is_dup = 0;
*prev = node->next;
}
else {
prev = &(*prev)->next;
}
node = node->next;
}
return head;
}
```
`prev` 是一個指標的指標，使用 `node` 走訪整個串列，如果 `node` 和 `node->next` 的值不同就移動 `prev` 和 `node`。
如果 `node` 和 `node->next` 的值相同就跳過重複的節點，直到找到不同的節點，將 `prev` 所指的 `next` 指標指向該節點。
重複以上動作直到所有節點都被走訪過。
#### 以類似 Linux 核心的 circular doubly-linked list 改寫
兩個版本都與原本相似，更改了原本對 `NULL` 的判斷，以及對 `prev` 的處理
```c
struct ListNode {
int val;
struct list_node list;
};
```
遞迴版本。
```c
struct list_node *deleteDuplicates(struct list_node *head)
{
static struct list_node *h = NULL;
if (head == h)
return h;
if(!h)
h = head;
if (head->next != h) {
int val = list_entry(head, ListNode, list)->val;
int val_next = list_entry(head->next, ListNode, list)->val;
if(val == val_next) {
/* Remove all duplicate numbers */
while (head->next != h && val == val_next) {
head = head->next;
val = list_entry(head, ListNode, list)->val;
val_next = list_entry(head->next, ListNode, list)->val;
}
return deleteDuplicates(head->next);
}
}
head->next = deleteDuplicates(head->next);
head->next->prev = head;
return head;
}
```
迴圈版本，將原本指向前一個節點的 `next` 的指標改成指向前一個節點的指標。
```c
struct list_node *deleteDuplicates(struct list_head *head)
{
if (!head)
return NULL;
int is_dup = 0;
ListNode *entry;
ListNode *safe;
struct list_head *prev = head;
list_for_each_entry_safe(entry, safe, head, list) {
if(&safe->list != head && entry->value == safe->value) {
is_dup = 1;
}
else if (is_dup) {
is_dup = 0;
prev->next = &safe->list;
safe->list.prev = prev;
}
else {
prev = prev->next;
}
}
return true;
}
```
## 測驗三
```c
MMM1 (lru, n, &obj->dhead, dlink) {
list_del(&lru->dlink);
free(lru);
}
```
因為這裡面用到了 `list_del` ，可以判斷是帶有 `safe` 的 list 巨集，而 `lru` 是 `LRUNode` ，所以 `MMM1` 是 `list_for_each_entry_safe` 。
```c
MMM2 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
return lru->value;
}
}
```
```c
MMM3 (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
```
`lru` 是 `LRUNode` ，而參數的數量為三個，所以 `MMM2` 和 `MMM3` 是 `list_for_each_entry` 。
```c
if (obj->count == obj->capacity) {
lru = MMM4(&obj->dhead, LRUNode, dlink);
list_del(&lru->dlink);
list_del(&lru->hlink);
}
```
`MMM4` 會回傳一個 `LRUNode` ， 所以可能為 `list_first_entry` 或 `list_last_entry` ，而這段程式碼是在 `LRUCachePut` 裡判斷當空間滿的時後，要挑選一個節點移除，題目是要做 Least Recently Used ，且 `lRUCacheGet` 會將存取到的節點搬到開頭，所以這裡要移除的是尾端的節點，因此 `MM4` 為 `list_last_entry`。
### 延伸問題
LRU 用串列來實作的話，其中一個做法是，當存取節點時將其搬至開頭或尾端，而需要移除或取代時，就從另外一端進行。
考慮到存取時的效率，可以將節點放入 hashtable 。本題的程式碼利用同樣的想法去實作 LRU Cache。
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
`dhead` 是負責處理 LRU 的串列， `hheads[]` 是 hashtable 的部分， `capacity` 紀錄最大的容量， `count` 紀錄現有的容量。這裡的 hash table 使用陣列和串列完成。 `LRUNode` 則儲存需要用的資料與指標。
```c
LRUCache *lRUCacheCreate(int capacity)
```
建立指定容量的 `LRUCache` ，並初始化。
```c
void lRUCacheFree(LRUCache *obj)
```
釋放所有`LRUCache` 及所含節點的空間。
```c
int lRUCacheGet(LRUCache *obj, int key)
```
取得 key 所對應的 value 。先是用 hashtable 直接取得節點，再將該節點移至串列的開頭。
```c
void lRUCachePut(LRUCache *obj, int key, int value)
```
儲存 key 與對應的 value ，先是在 hashtable 中檢查 key 是否已存在，若存在就直接返回值。若不存在且容量沒滿則要建立一個新節點，若是容量滿了則要取代尾端的節點。最後將這個節點放入串列的開頭，以及 hashtable 對應的位置，還有更新 `count`。
#### 改善
使用 `hlist_head` 跟 `hlist_node` 取代原本的 `list_head` ，將原本 list 的巨集換成 hlist 的。
```c
typedef struct {
int capacity, count;
struct list_head dhead;
struct hlist_head hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head dlink;
struct hlist_node hlink;
} LRUNode;
```
以下是測試用的程式碼。`min` 是找出陣列最小值的 index ， `init` 是將陣列初始化為零。測驗方法是放入與最大容量相同的資料，對這些資料做隨機存取。最後確認這些資料被取代的順序是否為 LRU ，使用時間戳的方法進行確認，有一個陣列 `count` 負責紀錄時間戳，每次存取都會更新，時間戳最小者為要被取代的。
```c
int main(int argc, char *argv[]) {
int test_n = 100;
int test_m = 10;
int size = 16;
int *count = malloc(size * sizeof(int));
LRUCache *cache = lRUCacheCreate(size);
srand(0);
for (int j = 0; j < test_m; j++) {
init(count, size);
/* put data */
for (int i = 0; i < size; i++) {
count[i] = i;
lRUCachePut(cache, i, rand());
}
/* random access */
for (int i = size; i < test_n; i++) {
int key = rand() % size;
count[key] = i;
lRUCacheGet(cache, key);
}
/* check the result */
for (int i = 0; i < size; i++) {
int key = size + i;
lRUCachePut(cache, key, rand());
key = min(count, size);
if(lRUCacheGet(cache, key) != -1) {
lRUCacheFree(cache);
free(count);
printf("fail\n");
return 0;
}
count[key] = test_n + 1;
}
}
printf("sucess\n");
free(count);
lRUCacheFree(cache);
return 0;
}
```
## 測驗四
```c
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;
}
```
題目是要找出陣列中最長序列的長度，而這段程式碼是某個數字找出它所處的序列的長度。 `find` 可以找出第一個參數的數字是否存在，所以可以用來尋找某個數字 n 的 ..., n - 2, n - 1, n, n + 1, n + 2, ... 是否存在，以確定序列的長度。 所以 `LLL` 和 `RRR` 各為一個以 `num` 遞增和遞減的表示式，因為 `left` 和 `right` 初始值為 `num` ，所以可能為 `--left` 和 `++right` 或 `++left` 和 `--right` 。
### 延伸問題
程式運作大致如下，對給定陣列內的數字建立不重複的 hashtable ，用這個 hashtable 可以快速得知該數字存不存在。
```c
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]);
}
}
```
接下來找出陣列內的每個數字所在序列長度的最大值，查找方法如上述所說，查找過的數字要從 hashtable 移除，因為是同一序列，再一次遇到可不必查找。
###### tags: `linux2022`
Sign in with Wallet
Connect another wallet