owned this note
owned this note
Published
Linked with GitHub
---
tags: linux, kernel
---
# 2022q1 Homework1 (quiz1)
contributed by < `Destiny0504` >
> [題目連結](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗 1
- AAA = n->next = first;
- BBB = n->pprev = &h->first;
``` c
// Leetcode problem 1 Two sum
#include <stddef.h>
#include <stdlib.h>
```
### 宣告用來建立 list 需要用到的 structure
``` 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;
```
### 決定 hash map 的大小並初始化
``` c
#define MAP_HASH_SIZE(bits) (1 << bits)
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 示意圖
```graphviz
digraph{
rankdir = LR;
node1
[
shape = none;
style = none;
label = <<table border="0" cellspacing="0">
<tr><td port="hash0" border="1">hash 0 </td></tr>
<tr><td port="hash1" border="1">hash 1 </td></tr>
<tr><td border="1">hash 2 </td></tr>
<tr><td border="1">hash 3 </td></tr>
</table>>
];
node2
[
shape=record;
height=0
width=0
label="<f0>NULL"
];
node1:hash0->node2
}
```
### 宣告 hash table node 的 structure
``` c
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
### container_of
此巨集能透過指向 structure 中的 member 的 pointer 回推整個 sturcture 的開頭記憶體位置
- 回傳值為指向 structure 記憶體位置的 pointer
``` c
#define container_of(ptr, type, member) \
({ \
void *__mptr = (void *) (ptr); \
((type *) (__mptr - offsetof(type, member))); \
})
```
### Hash function
此函式能將傳入的 val 計算完 hash 後的值並回傳
- 選用一個夠大的數字（ 0x61C88647 ）來 hash ，這麼做可以確保 hash 過後的值並不會太小，導致我們在取前幾個 bits 所得到的值太過接近，進而失去 hash 的效果。
- 變數 bits 可以幫助我們決定要取前面多少個 bit 當作 hash 完的結果。
- e.g. bits = 10 ，我們得到的 hash 值的範圍就會在 0 ~ 1023 之間
``` c
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
### find key
確認 key 所代表的值是否在 map 之中
- 如果在 map 中函式會回傳指向 key 的 pointer ，否則回傳 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;
}
```
- 透過移動 p 所指向的位置來確認 list 是否含有我們要的值。
```graphviz
digraph{
rankdir = LR;
table
[
shape = none;
style = none;
label = <<table border="0" cellspacing="0">
<tr><td port="hash0" border="1">hash 0 </td></tr>
<tr><td port="hash1" border="1">hash 1 </td></tr>
<tr><td border="1">hash 2 </td></tr>
<tr><td border="1">hash 3 </td></tr>
</table>>
];
node1
[
shape=record;
height=0
width=0
label="node1"
];
node2
[
shape=record;
height=0
width=0
label="node2"
];
node3
[
shape=record;
height=0
width=0
label="node3"
];
node4
[
shape=record;
height=0
width=0
label="node4"
];
node5
[
shape=record;
height=0
width=0
label="node5"
];
nullnode
[
shape=record;
height=0
width=0
label="null"
];
p
[
shape=record;
height=0
width=0
label="p"
];
table:hash0->node1
node1->node2
node2->node3
node3->node4
node4->node5
node5->nullnode
p->node1
}
```
### map get
與 find key 的功能相同，差別只在於回傳的資料型別為 void pointer
``` c
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
### map add
將新的值加入 map 中
- 先檢查要加入的值是否已在 map 中，如果已經加入過的話，就不做任何更動。
- 如果確認 key 不在 map 之中，則在 key 應該被加入的 list 中新增一個值為 key 的 node
``` 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 */
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
/* BBB */
n->pprev = &h->first;
}
```
### map deinit
將分配給整個 map 的記憶體釋放，相當於把整個 map 刪除。
- 遍歷整個 map 來將每個 allocated 的 node 的 memory 都釋放。
``` 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);
}
```
### 解決 TwoSum 問題
[Two Sum 問題連結](https://leetcode.com/problems/two-sum/)
``` c
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;
}
```
### Reference
- [GOLDEN_RATIO_32](https://hackmd.io/@ChialiangKuo/quiz6B-hash-table#Hash-Function1)
## 測驗 2
- COND1 = head->next != NULL && head->val == head->next->val
- COND2 = head != NULL && head->next != NULL && head->val == head->next->val
### Singly-linked list 迭代版本
因為原本的題目就是 singly-linked list ，所以不額外實作 listnode
- 如果傳入的 list 為空或是只有一個 node 就直接回傳 head
``` c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
struct ListNode *prev = NULL, *tmp = NULL;
int hold = 0, cur = 0;
if (head == NULL || head->next == NULL)
return head;
```
- 將開頭所有重複的點全部移除，確保現在的 head 是需要被保留的點。這一步做完，如果整個 list 只剩下一個 node 以下，就直接回傳答案。
``` c
while (hold != 1 && head != NULL) {
hold = 1;
while (head->next != NULL && head->val == head->next->val) {
head->next = head->next->next;
hold = 0;
}
if (!hold)
head = head->next;
}
if (head == NULL || head->next == NULL)
return head;
```
- 將剩餘的 duplicate node 全部移除
``` c
prev = head;
tmp = head->next;
while (tmp != NULL) {
hold = 1;
while (tmp->next != NULL && tmp->val == tmp->next->val) {
tmp->next = tmp->next->next;
hold = 0;
}
if (hold) {
prev->next = tmp;
prev = prev->next;
}
tmp = tmp->next;
}
prev->next = tmp;
return head;
}
```
### Doubly-linked list 迭代版本
#### Listnode 節點
``` c
struct listnode {
int val;
struct listnode *next;
struct listnode *prev;
};
```
#### List 所需要的函式
``` c
// 初始化 node
void initnode(struct listnode *head)
{
head->next = head;
head->prev = head;
}
// 在 doubly-linked list 尾端加入新的 node
void add_tail(struct listnode *head, struct listnode *node)
{
head->prev->next = node;
node->prev = head->prev;
head->prev = node;
node->next = head;
}
// allocate 一塊新的 memory 給新的 node 並賦予給定的值
struct listnode *createnode(int data)
{
struct listnode *tmp = malloc(sizeof(struct listnode));
initnode(tmp);
tmp->val = data;
return tmp;
}
// 刪除 doubly-linked list 中的 node
void del_node(struct listnode *node)
{
struct listnode *next = node->next;
struct listnode *prev = node->prev;
prev->next = next;
next->prev = prev;
}
```
#### 從 list 中移除含有重複 val 的 node
``` c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
struct ListNode *tmp = head;
struct listnode *l_head = malloc(sizeof(struct listnode)), *cur = NULL;
int l_size = 0, i = 0, flag = 0;
initnode(l_head);
```
- 因為原本的題目是單向的 linked list ，所以我們要將原本的 linked list 中的所有的值全部加入自己實作的雙向 linked list。
``` c
for (; tmp != NULL; tmp = tmp->next) {
struct listnode *tmpnode = createnode(tmp->val);
add_tail(l_head, tmpnode);
l_size++;
}
```
- 將開頭所有重複的點全部移除。這一步做完，如果整個 list 如果沒有任何 node ，就直接回傳 NULL 。
``` c
for (cur = l_head->next; cur != l_head; cur = cur->next) {
while (cur->next != l_head && cur->val == cur->next->val) {
del_node(cur->next);
l_size--;
flag = 1;
}
if (flag) {
flag = 0;
del_node(cur);
l_size--;
}
}
if (l_head->next == l_head)
return NULL;
```
- 將 head 指向第一個不重複的 node
``` c
for (cur = l_head->next; head->val != cur->val; ){
head = head->next;
}
```
- 利用雙向的 linked list 幫助判斷原本的 node 需不需要被刪除
- 因為雙向的 linked list 可以直接看前一個 node 的值，所以可以直接判斷現在的 node 需不需要被刪除。
``` c
for (tmp = head, cur = l_head->next; tmp->next != NULL;) {
if (tmp->next->val != cur->next->val) {
tmp->next = tmp->next->next;
}
else {
tmp = tmp->next;
cur = cur->next;
}
}
return head;
}
```
## 測驗 3
### 宣告用來建立 list 需要用到的 structure
``` c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
```
### 初始化 cache
分配一塊指定大小 (```capacity```）的 memory ，用來模擬 cache 的運作。obj 中的每一個 index 皆指向一個獨立的 node。每一個 node 皆為一個用來儲存 data 的 cache block。
- 因為 cache 的大小有限，所以儲存資料的 key 會先經過 hash function 在存入對應的 block 。當我們需要拿取資料的時候，也是經過同樣的方式查看對應的 block 是否已有我們要找的資料。
``` 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;
}
```
### 釋放 cache
用 list.h 中實作的 list_for_each_entry_safe(entry, safe, head, member) 來一一釋放分配到的記憶體，達成清空 cache 的效果。
``` 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);
}
```
### 從 cache 中拿出指定的 object
計算出 ```key % obj->capacity``` 後，到對應的 block 檢查我們需要的資料是否在 cache 中。如果有則回傳 block 中的值，
``` 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;
}
```
### 將指定的 object 放入 cache
``` 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;
}
```
## 測驗 4
### 加上可以讀取測試資料的 main funtion 之後的正確答案
#### 定義會用到的 structure 以及 include header file
``` c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct seq_node {
int num;
struct list_head link;
};
```
#### 在同樣的 hash 值的 list 中找尋是否含有要指定的值
用 ```num % size``` 求出的 hash 值，再透過函式傳入的 ```head```，可以拿到整個可能包含 ```num``` 的 list ，接著從 list 中一一檢查是否有要查找的值（ ```num``` )。
``` 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;
}
```
#### 解決 longest consecutive sequece 的 function
- 第一個 for 迴圈
- 這個 for 迴圈是為了初始化整個 hash table
- 第二個 for 迴圈
- 這個迴圈能夠將傳入此函式的 ```nums``` 所含有的數字一一加入 hash table
- 第三個 for 迴圈
- 先指定一個值 ```num``` 再去整個 hash table 尋找是否有跟 ```num``` 相連的數字，最後得出 longest consecutive sequece 的長度。
``` c
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;
}
```
### 讀取 test data
``` c
int main()
{
int ans = 0, *nums = NULL, counter = 0;
// 100 為可以自行調整的參數，此處的 100 代表 100 bytes
nums = malloc(sizeof(int) * 100);
while (scanf("%d", &nums[counter]) != EOF) {
counter++;
}
ans = longestConsecutive(nums, sizeof(int) * counter);
printf("%d\n", ans);
free(nums);
}
```
## Reference
- 測驗三 obj 的 malloc 問題
- structure pointer 在宣告結束的時候就擁有 4 bytes 的空間來儲存記憶體位置了，所以 sizeof(obj) 不會是一個不確定的數字。
- 參考 ：[Scopes of identifier](https://stackoverflow.com/questions/27434326/is-there-anything-wrong-with-something-t-x-mallocsizeofx?fbclid=IwAR0fOAPd2uT92xFCi_EQcJzhAO8ELLut9cp-A7B1swik9LXk1foO4Rs1HzY)
Google Drive
Gist
Clipboard
Sign in with Wallet
