# 2022q1 Homework1 (quiz1)
contributed by < `cy023` >
> [測驗題](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗 `1`
### Hash Table
<!-- Graphviz 初心者 :) -->
```graphviz
digraph hash_table {
layout=fdp;
subgraph cluster_0 {
label="map_t";
style=filled;
color=lightgrey;
node [shape=record,color=black];
map_t [label="{ bits |<a> ht }", width=1, height=0.2];
}
subgraph cluster_1 {
label="struct hlist_head";
style=filled;
color=lightgrey;
node [shape=record,color=black];
hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
}
subgraph cluster_2 {
label="struct hlist_node";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_3 {
label="struct hlist_node";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
}
NULL [shape=plaintext]
{
edge[style=solid];
N1 [pos="0,4!", style=invis]
N2 [pos="2,1!", style=invis]
N3 [pos="7,1!", style=invis]
N4 [pos="10,1!", style=invis]
N5 [pos="13,1!", style=invis]
edge[style=invis, rankdir=LR]
N1 -> N2 -> N3 -> N4 -> N5
}
{
// rankdir=TB;
edge [style=invis]
map_t -> N1;
cluster_1 -> N2;
cluster_2 -> N3;
cluster_3 -> N4;
NULL -> N5;
}
// next
map_t:a -> hlist_head:b -> cluster_2
hlist_node0:d -> cluster_3
hlist_node1:d -> NULL
// pprev
edge[splines=curved];
hlist_node0:c -> hlist_head:b [color=lightskyblue4]
hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
}
```
`map_t` 結構內紀錄 hash table 的欄位數量共 `1 << bits` 個，起始位址 `ht` 指向由 `struct hlist_head *` 型態構成的陣列。
比較特別的地方在 `hlist_node` 的 `**pprev` 用了**指標的指標**，參考[第 1 週課堂問答簡記](https://hackmd.io/5zdyXn6uQMOeSoVBapuVNw?view)。
```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;
```
包裝了 `struct hlist_node` 結構的節點，另外包含經過 hash function 的 `key` 與儲存的資料。
```c
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
### 初始化 Hash Table
1. 配置 `map_t` 空間存放 hash table 的 Bucket 大小與起始位址的資訊。
```graphviz
digraph {
subgraph cluster_0 {
label="map_t";
style=filled;
color=lightgrey;
node [shape=record,color=black];
map_t [label="{ bits |<a> ht }", width=1, height=0.2];
}
}
```
2. 配置 `struct hlist_head` 型態陣列，共 `(1 << bits)` 個 `Bucket`，全都指向 `NULL`。
```graphviz
digraph {
subgraph cluster_1 {
label="struct hlist_head";
style=filled;
color=lightgrey;
node [shape=record,color=black];
hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
}
}
```
```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 使用空間
依序將每個 `Bucket` 連接的節點，利用 `container_of` 找出完整空間後釋放。
```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);
}
```
不太清楚何時會發生 `n->pprev` 等於 `NULL`，將此判斷註解仍能通過 LeetCode 測資...
```c=13
if (!n->pprev) /* unhashed */
goto bail;
```
若 Bucket 內還存在 `next` 節點時，先將節點 `remove`，`next`、`pprev` 都指向 `NULL` 後再進行記憶體釋放。
```c=16
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
```
### Hash Function
What ...?
TODO...
```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);
}
```
### 新增節點
在 hash table 內查找，給定 `key` 值的節點。
先利用 hash function 找到對應 `bucket`，再於該 `bucket` 指向的 `hlist_node` 內尋找(使用 `container_of` 取得 `hash_key` 的完整資訊，再與給定 `key` 值比較)。
```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;
}
```
給定 `key` 在 hash table 中查找對應的 data。
```c
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
在 hash table 中新增節點。
配置 `struct hash_key` 大小的空間，填入 `key`, `data` 資訊。
`line10` 先對 `key` 值進行雜湊，找到對應的 `bucket` - `h`。
`line11` 新增的 `hash_key` 節點 `n`，`bucket` 內的第一個節點 `first`。
因為要把 `n` 插入進 `bucket` 的第一個節點，所以將新節點的 `next` 指向 `first`，若 `bucket` 不為空 (`first` 不為 `NULL`)，將 `first->pprev = &n->next;`。
- `n->next = first;`
```graphviz
digraph hash_table {
layout=fdp;
subgraph cluster_0 {
label="map_t";
style=filled;
color=lightgrey;
node [shape=record,color=black];
map_t [label="{ bits |<a> ht }", width=1, height=0.2];
}
subgraph cluster_1 {
label="struct hlist_head";
style=filled;
color=lightgrey;
node [shape=record,color=black];
hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
}
subgraph cluster_2 {
label="node0";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_3 {
label="node1";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_4 {
label="node_new";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node2 [label="<c> pprev | <d> next", width=1, height=0.2];
}
NULL [shape=plaintext]
{
edge[style=solid];
N1 [pos="0,4!", style=invis]
N2 [pos="2,1!", style=invis]
N3 [pos="10,1!", style=invis]
N4 [pos="13,1!", style=invis]
N5 [pos="6,3!", style=invis]
N6 [pos="16,1!", style=invis]
edge[style=invis, rankdir=LR]
N1 -> N2 -> N3 -> N4 -> N5 -> N6
}
{
// rankdir=TB;
edge [style=invis]
map_t -> N1;
cluster_1 -> N2;
cluster_2 -> N3;
cluster_3 -> N4;
cluster_4 -> N5;
NULL -> N6;
}
// next
map_t:a -> hlist_head:b -> cluster_2
hlist_node0:d -> cluster_3
hlist_node1:d -> NULL
hlist_node2:d -> cluster_2 [color=red]
// pprev
edge[splines=curved];
hlist_node0:c -> hlist_head:b [color=lightskyblue4]
hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
}
```
- `if (first)
first->pprev = &n->next;`
```graphviz
digraph hash_table {
layout=fdp;
subgraph cluster_0 {
label="map_t";
style=filled;
color=lightgrey;
node [shape=record,color=black];
map_t [label="{ bits |<a> ht }", width=1, height=0.2];
}
subgraph cluster_1 {
label="struct hlist_head";
style=filled;
color=lightgrey;
node [shape=record,color=black];
hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
}
subgraph cluster_2 {
label="node0";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_3 {
label="node1";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_4 {
label="node_new";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node2 [label="<c> pprev | <d> next", width=1, height=0.2];
}
NULL [shape=plaintext]
{
edge[style=solid];
N1 [pos="0,4!", style=invis]
N2 [pos="2,1!", style=invis]
N3 [pos="10,1!", style=invis]
N4 [pos="13,1!", style=invis]
N5 [pos="6,3!", style=invis]
N6 [pos="16,1!", style=invis]
edge[style=invis, rankdir=LR]
N1 -> N2 -> N3 -> N4 -> N5 -> N6
}
{
// rankdir=TB;
edge [style=invis]
map_t -> N1;
cluster_1 -> N2;
cluster_2 -> N3;
cluster_3 -> N4;
cluster_4 -> N5;
NULL -> N6;
}
// next
map_t:a -> hlist_head:b -> cluster_2
hlist_node0:d -> cluster_3
hlist_node1:d -> NULL
hlist_node2:d -> cluster_2
// pprev
edge[splines=curved];
hlist_node0:c -> hlist_node2:d [color=red]
hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
}
```
- `h->first = n;`
```graphviz
digraph hash_table {
layout=fdp;
subgraph cluster_0 {
label="map_t";
style=filled;
color=lightgrey;
node [shape=record,color=black];
map_t [label="{ bits |<a> ht }", width=1, height=0.2];
}
subgraph cluster_1 {
label="struct hlist_head";
style=filled;
color=lightgrey;
node [shape=record,color=black];
hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
}
subgraph cluster_2 {
label="node0";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_3 {
label="node1";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_4 {
label="node_new";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node2 [label="<c> pprev | <d> next", width=1, height=0.2];
}
NULL [shape=plaintext]
{
edge[style=solid];
N1 [pos="0,4!", style=invis]
N2 [pos="2,1!", style=invis]
N3 [pos="10,1!", style=invis]
N4 [pos="13,1!", style=invis]
N5 [pos="6,3!", style=invis]
N6 [pos="16,1!", style=invis]
edge[style=invis, rankdir=LR]
N1 -> N2 -> N3 -> N4 -> N5 -> N6
}
{
// rankdir=TB;
edge [style=invis]
map_t -> N1;
cluster_1 -> N2;
cluster_2 -> N3;
cluster_3 -> N4;
cluster_4 -> N5;
NULL -> N6;
}
// next
map_t:a -> hlist_head:b1
hlist_head:b -> cluster_4 [color=red]
hlist_node0:d -> cluster_3
hlist_node1:d -> NULL
hlist_node2:d -> cluster_2
// pprev
edge[splines=curved];
hlist_node0:c -> hlist_node2:d [color=lightskyblue4]
hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
}
```
- `n->pprev = &h->first;`
```graphviz
digraph hash_table {
layout=fdp;
subgraph cluster_0 {
label="map_t";
style=filled;
color=lightgrey;
node [shape=record,color=black];
map_t [label="{ bits |<a> ht }", width=1, height=0.2];
}
subgraph cluster_1 {
label="struct hlist_head";
style=filled;
color=lightgrey;
node [shape=record,color=black];
hlist_head [label="{<b> first[0] | <b1> first[1] | <b2> first[2] | <b3> ... | <b4> first[\(1 \<\< bits\) - 1]}", width=1, height=0.2];
}
subgraph cluster_2 {
label="node0";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node0 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_3 {
label="node1";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node1 [label="<c> pprev | <d> next", width=1, height=0.2];
}
subgraph cluster_4 {
label="node_new";
style=filled;
color=lightgrey;
node [shape=record,color=black,rankdir=LR];
hlist_node2 [label="<c> pprev | <d> next", width=1, height=0.2];
}
NULL [shape=plaintext]
{
edge[style=solid];
N1 [pos="0,4!", style=invis]
N2 [pos="2,1!", style=invis]
N3 [pos="10,1!", style=invis]
N4 [pos="13,1!", style=invis]
N5 [pos="6,3!", style=invis]
N6 [pos="16,1!", style=invis]
edge[style=invis, rankdir=LR]
N1 -> N2 -> N3 -> N4 -> N5 -> N6
}
{
// rankdir=TB;
edge [style=invis]
map_t -> N1;
cluster_1 -> N2;
cluster_2 -> N3;
cluster_3 -> N4;
cluster_4 -> N5;
NULL -> N6;
}
// next
map_t:a -> hlist_head:b1
hlist_head:b -> cluster_4
hlist_node0:d -> cluster_3
hlist_node1:d -> NULL
hlist_node2:d -> cluster_2
// pprev
edge[splines=curved];
hlist_node0:c -> hlist_node2:d [color=lightskyblue4]
hlist_node1:c -> hlist_node0:d [color=lightskyblue4]
hlist_node2:c -> hlist_head:b [color=red]
}
```
```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;
}
```
:::info
AAA = `n->next = first;`
BBB = `n->pprev = &h->first;`
:::
## 測驗 `2`
[LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
### 遞迴版本
```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;
}
```
:::info
COND1 = `head->next && head->val == head->next->val`
COND2 = `head->next && head->val == head->next->val`
:::
### 迭代版本
```c
struct ListNode *deleteDuplicates(struct ListNode *head)
{
if (!head)
return NULL;
struct ListNode *p = malloc(sizeof(struct ListNode));
p->next = head;
p->val = head->val - 1;
struct ListNode **indirect = &p;
struct ListNode *trace = (*indirect)->next;
while (trace) {
while (trace && (!trace->next || (trace->next && trace->val != trace->next->val))) {
indirect = &(*indirect)->next;
trace = (*indirect)->next;
}
while (trace && (*indirect)->next->val == trace->val) {
// struct ListNode *tmp = trace;
trace = trace->next;
// free(tmp);
}
(*indirect)->next = trace;
trace = (*indirect)->next;
}
head = p->next;
free(p);
return head;
}
```
## 測驗 `3`
:::spoiler LeetCode 提交版
```c
#include <stdio.h>
#include <stdlib.h>
/*------------------------------------------------------------*/
// #include "list.h"
struct list_head {
struct list_head *prev;
struct list_head *next;
};
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
}
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
#define list_entry(node, type, member) container_of(node, type, member)
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
#define list_for_each_entry(entry, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member); \
&entry->member != (head); \
entry = list_entry(entry->member.next, __typeof__(*entry), member))
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
/*------------------------------------------------------------*/
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
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;
}
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);
}
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;
}
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *lru;
int hash = key % obj->capacity;
// hit
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) { // eviction
lru = list_last_entry(&obj->dhead, LRUNode, dlink);
list_del(&lru->dlink);
list_del(&lru->hlink);
} else { // miss
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;
}
```
:::
:::info
- MM1 `list_for_each_entry_safe`
- MM2 `list_for_each_entry`
- MM3 `list_for_each_entry`
- MM4 `list_last_entry`
:::
## 測驗 `4`
:::spoiler LeetCode 提交版
```c
#include <stdio.h>
#include <stdlib.h>
/*------------------------------------------------------------*/
// #include "list.h"
struct list_head {
struct list_head *prev;
struct list_head *next;
};
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
}
#define list_entry(node, type, member) container_of(node, type, member)
#define list_for_each_entry(entry, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member); \
&entry->member != (head); \
entry = list_entry(entry->member.next, __typeof__(*entry), member))
/*------------------------------------------------------------*/
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;
}
```
:::
:::info
- LLL `--left`
- RRR `++right`
:::
Sign in with Wallet
Connect another wallet