2022q1 Homework1 (quiz1)

# 2022q1 Homework1 (quiz1) contributed by < `cy023` > > [測驗題](https://hackmd.io/@sysprog/linux2022-quiz1) ## 測驗 `1` ### Hash Table  ```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="{ 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="{ 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="{ 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="{ 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="{ 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="{ 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` :::

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.