---
tags: linux2022, linux
---
# 2022q1 Homework1 (quiz1)
contributed by < `AmyLin0210` >
> [2022q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz1)
## q1
AAA: `n->next = first`
BBB: `n->pprev = &h->first`
### map_init
在這裡會有一個由 `hlist_head` 所組成的陣列，若這個陣列的大小為 10 ，那也就表示這裡有相對應的 10 條 hlist。
下面為課堂測驗中的示意圖：
```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;
}
```
### map_add
首先會先找到該 key 相對應的雜湊值，再將相對應的節點接到相對應的 hlist 上面。
```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;
}
```
### pprev 是指標的指標的好處
現在我們就針對 hash map 是如何連接得來進行討論。
這裡是課堂測驗所提供的示意圖：
因為在這裡 hash table 在意的只有，現在如果我想要刪除一個節點，那要怎麼將其前後給連接起，並不在乎是不是能夠拿到前一個節點的位置。我們可以看到 `pprev` 是一個指標的指標，所指向的位置是前一個節點 next 的位置，這個可以實現我們前面所提到的問題。
如果現在我想要去刪除掉一個節點，我所需要做的事情就只有
1. 將欲刪除的節點後面那個節點的 `pprev` 更改為該節點的 `pprev`
2. 把該節點 `pprev` 的值更改為自己的下一個節點
3. 把該節點刪掉
範例程式碼如下：
```c
void map_del(struct hlist_node *n)
{
if (!n)
return;
if (n->next) {
n->next->pprev = n->pprev;
}
*(n->pprev) = n->next;
free(container_of(n, struct hash_key, node)->data);
free(container_of(n, struct hash_key, node));
}
```
以下是示意圖，若現在想要刪除的節點為 `L2`：
1. 確認 `L2` 的 `next` 是否為 NULL，若不是，則將 `L2` 的下個節點 (`L3`) 的 `pprev` 變更為 `L2` 的 `pprev` 的值 (也就是 `L1` 的 `next` 的位置)。
2. 將 `L2` 的 `pprev` 的值 (也就是 `L1` 的 `next`) 改為 `L3` 的位置
3. 刪除 `L2`
**Before**
```graphviz
digraph list_add_tail {
nodesep=0.3
rankdir="LR"
node[shape=record]
head [
label = "
<f>first
"
xlabel = "head"
style="filled"
fillcolor="lightblue"
]
L1 [
label = "
{<p> pprev | <n> next}
"
xlabel = "L1"
style="filled"
fillcolor="lightblue"
]
L2 [
label = "
{<p> pprev | <n> next}
"
xlabel = "L2"
style="filled"
fillcolor="pink"
]
L3 [
label = "
{<p> pprev | <n> next}
"
xlabel = "L3"
style="filled"
fillcolor="lightblue"
]
head:f->L1
L1:n->L2
L1:p->head:f
L2:n->L3
L2:p->L1:next
L3:n->NULL
L3:p->L2:next
}
```
**After**
```graphviz
digraph list_add_tail {
nodesep=0.3
rankdir="LR"
node[shape=record]
head [
label = "
<f>first
"
xlabel = "head"
style="filled"
fillcolor="lightblue"
]
L1 [
label = "
{<p> pprev | <n> next}
"
xlabel = "L1"
style="filled"
fillcolor="lightblue"
]
L3 [
label = "
{<p> pprev | <n> next}
"
xlabel = "L3"
style="filled"
fillcolor="lightblue"
]
head:f->L1
L1:n->L3
L1:p->head:f
L3:n->NULL
L3:p->L1:next
}
```
且在特殊情況 (例如該 linked-list 只有一個節點)，此範例程式碼也能處理。
現在假設只有一個節點 (L1) ，且要刪除掉該節點。
1. 由於 `L1` 的 `next` 為 NULL，所以不對 `L1` 的 `next` 節點做處理。
2. 更改 `L1` 的 `pprev` (在這裡為 `head` 的 `first`) 的值，由於 `L1` 的 `next` 為 NULL，故更改它為 NULL。
3. 刪除掉 `L1` 這個節點。
**Before**
```graphviz
digraph list_add_tail {
nodesep=0.3
rankdir="LR"
node[shape=record]
head [
label = "
<f>first
"
xlabel = "head"
style="filled"
fillcolor="lightblue"
]
L1 [
label = "
{<p> pprev | <n> next}
"
xlabel = "L1"
style="filled"
fillcolor="pink"
]
head:f->L1
L1:n->NULL
L1:p->head:f
}
```
**After**
```graphviz
digraph list_add_tail {
nodesep=0.3
rankdir="LR"
node[shape=record]
head [
label = "
<f>first
"
xlabel = "head"
style="filled"
fillcolor="lightblue"
]
head:f->NULL
}
```
## q2
COND1 = head->next && head->val == head->next->val
COND2 = head->next && head->val == head->next->val
遞迴版本的程式碼：
```c
#include <stddef.h>
struct ListNode {
int val;
struct ListNode *next;
};
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;
}
```
## q3
MMM1 = list_for_each_entry_safe
MMM2 = list_for_each_entry
MMM3 = list_for_each_entry
MMM4 = list_last_entry
在這題裡，是使用 hash table 來使得 LRU 的操作能夠維持在 O(1) 的時間複雜度
### 資料型態
首先看到資料型態的部份，可以看到有兩個 struct，分別是 `LRUCache` 與 `LRUNode`
- `LRUCache`: 儲存 cache 的大小、目前有多少東西存在 cache 裡的資訊
- `LRUNode`: 節點的資訊都儲存在裡面，包含自己的 `key`、`value`。
```c
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
在這裡總共會需要維護兩種 list
- 第一種的開頭是 `dhead` ，它維護的主要內容是所有節點最後被使用到的時間序，若有節點被使用到，會被更新放置到此 list 的前方，反之若 cache 已經滿了，會從這條 list 的最後方開始移除節點，在這裡將這條 list 稱為 dlist。
- 第二種主要維護的是 hash table，假設有某個 key 經過 hash 後的結果是 i，那相對應的節點會被儲存於 `hhead[i]` 所維護的 list 中。在這裡將這種 list 稱為 hlist。
### lRUCacheCreate
在 `lRUCacheCreate` 這個函式裡面，它初始化了這個 Cache 所需要的資料結構。
首先看到第 3 行它宣告了多少的記憶體空間。除了 `LRUCache` 的大小之外，它還額外的宣告出了 `capacity * sizeof(struct list_head)` 的空間。回去看看 `LRUCache` 的資料型態，最後面的變數是 `struct list_head hheads[]` ，利用了 [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 的特性，所以我們能夠透過第 3 行的程式碼，初始化一條 `struct list_head` 的 array。
```c=
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;
}
```
### lRUCachePut
在這裡所做的事情是檢查 `key` 是否已經存在，若存在就更新 `value` 與其在 dlist 內的位置，若不存在，就檢查 cache 是否已經滿了，並按照相對應的結果去更新相對應的節點。
在第 5 到第 10 行，它所作的事情就是去確認是否 `key` 已經存在，若存在了，就更新節點的 `value`，並將他的位置挪置 dlist 的最前方。
在第 13 行之後，所做的事情就是，若 key 還不存在，那要如何去新增節點。
```c=
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) {
list_move(&lru->dlink, &obj->dhead);
lru->value = value;
return;
}
}
if (obj->count == obj->capacity) {
lru = list_last_entry(&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 已經滿了、有新的節點要被儲存的示意圖，在這邊假定 cache 的大小只有 2，新的 key 為 2，value 為 2，hash 後的結果為 `0`。
在最加入新節點前的示意圖如下，粉色的為 dlist，藍色的為 hlist。
```graphviz
digraph list_add_tail {
nodesep=0.3
rankdir="LR"
node[shape=record]
dhead [
label = "
{<p> prev | <n> next}
"
xlabel = "dhead"
style="filled"
fillcolor="pink"
]
N1 [
label = "
{key = 4 | value = 4} |
{<p> pprev | <n> next}
"
xlabel = "N1 (dlink)"
style="filled"
fillcolor="pink"
]
N2 [
label = "
{key = 1 | value = 1} |
{<p> pprev | <n> next}
"
xlabel = "N2 (dlink)"
style="filled"
fillcolor="pink"
]
dhead:n->N1
dhead:p->N1
N1:n->N2
N1:p->dhead
N2:n->dhead
N2:p->N1
}
```
```graphviz
digraph list_add_tail {
nodesep=0.3
rankdir="LR"
node[shape=record]
hhead1 [
label = "
{<p> prev | <n> next}
"
xlabel = "hhead[1]"
style="filled"
fillcolor="lightblue"
]
N2 [
label = "
{key = 1 | value = 1} |
{<p> pprev | <n> next}
"
xlabel = "N2 (hlink)"
style="filled"
fillcolor="lightblue"
]
hhead0 [
label = "
{<p> prev | <n> next}
"
xlabel = "hhead[0]"
style="filled"
fillcolor="lightblue"
]
N1 [
label = "
{key = 4 | value = 4} |
{<p> pprev | <n> next}
"
xlabel = "N1 (hlink)"
style="filled"
fillcolor="lightblue"
]
hhead1:n->N2
hhead1:p->N2
N2:n->hhead1
N2:p->hhead1
hhead0:n->N1
hhead0:p->N1
N1:n->hhead0
N1:p->hhead0
}
```
現在想要加入新的節點，由於 cache 的空間已經滿了，所以是必要挑出節點移除，在此移除的是 key 為 1， value 為 1 的節點。
```graphviz
digraph list_add_tail {
nodesep=0.3
rankdir="LR"
node[shape=record]
dhead [
label = "
{<p> prev | <n> next}
"
xlabel = "dhead"
style="filled"
fillcolor="pink"
]
N1 [
label = "
{key = 2 | value = 2} |
{<p> pprev | <n> next}
"
xlabel = "N1 (dlink)"
style="filled"
fillcolor="pink"
]
N2 [
label = "
{key = 4 | value = 4} |
{<p> pprev | <n> next}
"
xlabel = "N2 (dlink)"
style="filled"
fillcolor="pink"
]
dhead:n->N1
dhead:p->N1
N1:n->N2
N1:p->dhead
N2:n->dhead
N2:p->N1
}
```
```graphviz
digraph list_add_tail {
nodesep=0.3
rankdir="LR"
node[shape=record]
hhead1 [
label = "
{<p> prev | <n> next}
"
xlabel = "hhead[1]"
style="filled"
fillcolor="lightblue"
]
hhead0 [
label = "
{<p> prev | <n> next}
"
xlabel = "hhead[0]"
style="filled"
fillcolor="lightblue"
]
N1 [
label = "
{key = 2 | value = 2} |
{<p> pprev | <n> next}
"
xlabel = "N1 (hlink)"
style="filled"
fillcolor="lightblue"
]
N2 [
label = "
{key = 4 | value = 4} |
{<p> pprev | <n> next}
"
xlabel = "N2 (hlink)"
style="filled"
fillcolor="lightblue"
]
hhead1:n->hhead1
hhead1:p->hhead1
hhead0:n->N1
hhead0:p->N2
N1:n->N2
N1:p->hhead0
N2:n->hhead0
N2:p->N1
}
```
### lRUCacheGet
這個函式目標是尋找 cache 內特定 key 的值。
首先它會先找到相對應 key 的 hlist，從中尋找該 key 是否存在，若該 key 有存在，就回傳他的值並更新 dlist 內相對應的位置。
```c
int lRUCacheGet(LRUCache *obj, int key)
{
LRUNode *lru;
int hash = key % obj->capacity;
list_for_each_entry (lru, &obj->hheads[hash], hlink) {
if (lru->key == key) {
list_move(&lru->dlink, &obj->dhead);
return lru->value;
}
}
return -1;
}
```
### lRUCacheFree
清掉 cache 所使用到的記憶體空間。
在這邊由於 dlist 與 hlist 所連接起來的節點其實是相同的，所以只要走訪過一次 dlist 並清除節點即可完成。
```c
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);
}
```
### 指出其中可改進之處並實作
目前我想到的可改進之處為 hash function。
在原程式碼內的 hash 只是簡單的找餘數，所以很有機會會碰到 collision，待閱讀相關文章後再補齊這部份的內容。
## q4
LLL = --left
RRR = ++right
在 `longestConsecutive` 這個函式裡，下方程式碼內的第 26 行到第 33 行，在這裡做的事情是建 hash table。
首先先利用 find 來確認是否進來的數值已經存在，若已經存在，會回傳已經存在的那個節點，若不存在，會回傳 NULL。
在第 35 到 57 行，目標是找到最長的連續數列。此 hash 出現在第 9 行，就是由數字去 mod 他的 size，所以也就可以知道，如果有連續的數字，那必然會出現在他左右的 hash list 中。
在 45 與 50 行間，分別是往左與往右找，若有找到，就將該 node 給刪除掉，並把 `len` 加一。
```c=
struct seq_node {
int num;
struct list_head link;
};
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;
}
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(--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;
}
}
return length;
}
```
Sign in with Wallet
Connect another wallet