# 2022q1 Homework1 (quiz1) contributed by < `Korin777` > ## Q1 ### 延伸題目一 #### 函式功能: 1. map_init 用來建立 hash table `map_t` 的各個 `hlist_head` , `ht` 的數量為2的冪 ```graphviz digraph structs { rankdir=LR node[shape=record] e1 [label=" <first> ht[0].first| <second> ht[1].first | <third> ht[2].first | <forth> ht[3].first"]; node[shape=none]; null_1[label = NULL] e1:first->null_1 e1:second->null_1 e1:third->null_1 e1:forth->null_1 } ``` 2. find_key 查詢 key 存在與否 , 透過 `hash function` 及 `key` 得到特定 `ht[i]` 並遍歷 `ht[i]` 找尋是否存在 `key` , 有的話回傳此 `hash_key` 指標 , 沒有則回傳 NULL 3. map_get 查詢 `key` 的 `data` , 透過 find_key 是否回傳 `hash_key` 指標來決定回傳對應的 `data` 指標或 `NULL` 5. map_add 增加 `ht[i]` 的節點 , 節點會增加在 `ht[i].first` , 先透過 `find_key` 查詢 key 是否存在 , 不存在再增加節點 ```graphviz digraph structs { rankdir=LR node[shape=record]; e1 [label="<p> ht[i].first "]; node[shape=record]; e2 [label=" <h>hlist_node | {<p> pprev | <n>next }"]; node[shape=record]; e3 [label=" <h>hlist_node | {<p> pprev | <n>next }"]; node[shape=none]; NULL [label="NULL"]; e1:p->e2:h; e2:p->e1; e2:n->e3:h; e3:p->e2:n; e3:n->NULL; subgraph cluster_0 { style=filled; color="green"; label="new node"; e2; } } ``` 6. map_deinit 釋放 hash table 所配置過的記憶體 , 每個 `ht[i]` 的各個節點依照由頭到尾的順序釋放 `hash_key->data` 及 `hash_key` , 最後再釋放整個 `map_t` ## Q2 ### 延伸題目一 * `new_head` 為移除重複節點後的 head * `prev_node` 用來修正上個非重複節點的下個節點 ```c struct ListNode *deleteDuplicates(struct ListNode *head) { if (!head) return NULL; struct ListNode *new_head = NULL, *prev_node = NULL; while(head) { while (head->next && head->val == head->next->val) // skip duplicate node head = head->next; if(prev_node) { // fix previous non-duplicate node's next if(prev_node->next != head) prev_node->next = head; else prev_node = head; } if(!new_head && head->next && head->val != head->next->val) { // Init new head new_head = head; prev_node = new_head; } head = head->next; } if(prev_node) { // fix previous non-duplicate node's next if(prev_node->next != head) prev_node->next = head; } return new_head; } ``` ### 延伸題目二 * 將 ListNode 結構改為作業的 circular doubly-linked list 結構 ```c struct list_head { struct list_head *prev; struct list_head *next; }; typedef struct { int value; struct list_head list; } element_t; ``` #### 迭代 * `tmp` 為整數指標 , 用來表示當前的重複數字 * `tmp` 為 NULL 或 `tmp` 和當前 `entry` 的數字不同 , 就看下個 `entry` 的數字是否與當前 `entry` 數字相同 , 來判斷是否該移除當前 節點及釋放對應的記憶體 * `tmp` 和當前 `entry` 的數字相同 , 直接移除當前節點及釋放對應的記憶體 * 若 `tmp` 最後不為 NULL 要釋放 `tmp` 記憶體 ```c void deleteDuplicates(struct list_head *head) { if (!head) return; int *tmp = NULL; element_t *ele, *tmpele; list_for_each_entry_safe (ele, tmpele, head, list) { if (!tmp || tmp != ele->value) { if (ele->list.next && ele->list.next != head) { element_t *elen = list_entry(ele->list.next, element_t, list); if (elen->value == ele->value) { if (!tmp) tmp = malloc(sizeof(int)); tmp = ele->value; list_del(&ele->list); free(ele->value), free(ele); } } } else { list_del(&ele->list); free(ele->value), free(ele); } } if (tmp) free(tmp); return; } ``` #### 遞迴 * `realhead` 傳進 circular doubly-linked list 的 head（不作為 `entry` 存放 `value` 的節點）, 用來判斷 list 是否以遍歷完 * 如果 `head` 與它之後的節點 `value` 重複則移除這段節點 , 並對下個非重複節點呼叫 `deleteDuplicates` ```c void deleteDuplicates(struct list_head *head, struct list_head *realhead) { if (!realhead || list_empty(realhead) || list_is_singular(realhead)) return; element_t *ele, *elen; if(head != realhead && head->next != realhead) { ele = list_entry(head, element_t, list); elen = list_entry(head->next, element_t, list); if (ele->value == elen->value) { /* Remove all duplicate numbers */ while (ele->value == elen->value) { head = head->next; list_del(&ele->list); free(ele->value), free(ele); if(head->next == realhead) { // finish list traversal list_del(&elen->list); free(elen->value), free(elen); return; } ele = list_entry(head, element_t, list); elen = list_entry(head->next, element_t, list); } list_del(&ele->list); free(ele->value), free(ele); return deleteDuplicates(head->next, realhead); } } else // finish list traversal return; return deleteDuplicates(head->next, realhead); } ``` ## Q3 #### 資料結構 * LRUCache 結構如下 , `capacity=5` 為 `hheads` 數量及總共能存的 `LRUNode` 數量 , `count=5` 為目前 `LRUNode` 數量 , 能透過 `dhead` 或 `hheads[i]` 來取得 `LRUNode` ```graphviz digraph structs { rankdir=LR node[shape=record] h1 [label=" <d>dhead |<h0> hheads[0]| <h1> hheads[1] | <h2> hheads[2] | <h3> hheads[3] | <h4> hheads[4]"]; node[shape=record]; e1 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next } | <d>dlink1 | {<p1> prev | <n2>next }"]; node[shape=record]; e2 [label="{key | value } |<h>hlink2 | {<p> prev | <n>next } | <d>dlink2 | {<p1> prev | <n2>next }"]; node[shape=record]; e3 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next } | <d>dlink3 | {<p1> prev | <n2>next }"]; node[shape=record]; e4 [label="{key | value } |<h>hlink1 | {<p> prev | <n>next } | <d>dlink4 | {<p1> prev | <n2>next }"]; node[shape=record]; e5 [label="{key | value } |<h>hlink2 | {<p> prev | <n>next } | <d>dlink5 | {<p1> prev | <n2>next }"]; h1:h0->e1:h e1:n->e2:h h1:h1->e3:h h1:h2->e4:h e4:n->e5:h h1:d->e1:d e1:n2->e2:d e2:n2->e3:d e3:n2->e4:d e4:n2->e5:d } ``` * 透過 `hheads[i]` , 只能拿到屬於這個區塊的 `LRUNode` ```graphviz digraph structs { rankdir=LR node[shape=record]; e1 [label="<h> hheads[i] | {<p> prev | <n>next }"]; node[shape=record]; e2 [label="<h>hlink1 | {<p> prev | <n>next }"]; node[shape=record]; e3 [label="<h>hlink2 | {<p> prev | <n>next }"]; node[shape=record]; e1:n->e2:h; e2:p->e1:h; e2:n->e3:h; e3:p->e2:h; e3:n->hheads; e1:p->hlink2 subgraph cluster_0 { style=filled; color="green"; label="LRUNode"; e2; } subgraph cluster_1 { style=filled; color="yellow"; label="LRUCache"; e1; } subgraph cluster_3 { style=filled; color="green"; label="LRUNode"; e3; } } ``` * 透過 `dhead` 可以遍歷所有的 `LRUNode` , `LRUNode` 越後面表示越久沒用到 ```graphviz digraph structs { rankdir=LR node[shape=record]; e1 [label="<d> dhead | {<p> prev | <n>next }"]; node[shape=record]; e2 [label="<h>dlink1 | {<p> prev | <n>next }"]; node[shape=record]; e3 [label="<h>dlink2 | {<p> prev | <n>next }"]; node[shape=record]; e1:p->dlink2 e1:n->e2:h; e2:p->e1:d; e2:n->e3:h; e3:p->e2:h; e3:n->dhead subgraph cluster_0 { style=filled; color="green"; label="LRUNode"; e2; } subgraph cluster_1 { style=filled; color="yellow"; label="LRUCache"; e1; } subgraph cluster_3 { style=filled; color="green"; label="LRUNode"; e3; } } ``` #### 函式功能 1. lRUCacheCreate 用來建立 `LRUCache` 及其中的 `hheads[]` 2. lRUCacheFree 用來釋放 `LRUCache` 及其所擁有的 `LRUNode` 3. lRUCacheGet 透過 `key` 來取得 `LRUCache` 對應的 `LRUNode->value` , 如果不存在則回傳 -1 4. lRUCachePut * 新增或修改 `LRUNode` * 如果 `key` 存在會修改 `LRUNode->value` , 並將此 `LRUNode->dlink` 移到 `LRUCache->dhead` 最前面 , 表示最近用到 * 如果 `key` 不存在則會看 `LRUCache->count` 是否已達到 `LRUCache->capacity` , 是的話就移除 `LRUCache->dlink` 最後一個 `LRUNode(最久沒用到)` , 並新增新的 `key-value` 到該 `LRUNode` 並加到 `LRUCache->dlink` 及對應的 `LRUCache->hheads[]` , 反之則會配置一個新的 `LRUNode` 空間 ## Q4 ### 延伸問題一 #### 資料結構 題目結構如下 , `nums = [100,4,200,1,3,2]` 、 `n_size=6` , `heads` 數量即為 `n_size` 數 , 每個 `num` 對 `n_size` 取餘數放到對應的 `heads[num < 0 ? -num % size : num % size]` ```graphviz digraph structs { rankdir=LR node[shape=record] h1 [label="<h0> heads[0]| <h1> heads[1] | <h2> heads[2] | <h3> heads[3] | <h4> heads[4] | <h5> heads[5]"]; e1 [label="<num>num=100 |<l>link | {<p> prev | <n>next }"]; e2 [label="<num>num=4 |<l>link | {<p> prev | <n>next }"]; e3 [label="<num>num=200 |<l>link | {<p> prev | <n>next }"]; e4 [label="<num>num=1 |<l>link | {<p> prev | <n>next }"]; e5 [label="<num>num=3 |<l>link | {<p> prev | <n>next }"]; e6 [label="<num>num=2 |<l>link | {<p> prev | <n>next }"]; h1:h0->e3:l e3:n->e1:l h1:h1->e4:l h1:h2->e6:l h1:h3->e5:l h1:h4->e2:l } ``` `heads[i]` 後面連結屬與此區塊的 `seq_node` ```graphviz digraph structs { rankdir=LR node[shape=record]; e1 [label="<h> heads | {<p> prev | <n>next }"]; node[shape=record]; e2 [label="num=200 | <h>link1 | {<p> prev | <n>next }"]; node[shape=record]; e3 [label="num=100 | <h>link2 | {<p> prev | <n>next }"]; node[shape=record]; e1:n->e2:h; e2:p->e1:h; e2:n->e3:h; e3:p->e2:h; e3:n->heads; e1:p->link2 subgraph cluster_0 { style=filled; color="green"; label="seq_node"; e2; } subgraph cluster_1 { style=filled; color="yellow"; label="list_head"; e1; } subgraph cluster_3 { style=filled; color="green"; label="seq_node"; e3; } } ``` #### 函式功能 1. find 用來尋找 `num` 是否存在對應 `heads[i]` 中 , 有就回傳此 `seq_node` , 沒有則回傳 NULL 2. longestConsecutive * 用來找出最長連續整數長度 * 首先配置長度 `n_size` 的 `heads` 並將 `nums` 的數字依序以 `seq_node` 的型態插入對應的 `heads[i]` * 遍歷 `nums` 中的數字 `num` , 如果 `num` 存在於對應 `heads[i]` 中 , 則繼續尋找與 `num` 相連的所有數字 * `left` 及 `right` 初始為 `num` ,`left` 表示比 `num` 小的相鄰數字 , `right` 則表示比 `num` 大的相鄰數字 * 持續將 `left` 減1並查詢其是否存在與對應 `heads[i]` , 存在的話將 `heads[i]` 中的 `left` 移除 , 反之則表示已經沒有比 `num` 小的相鄰數字 , 再來持續將 `right` 加1並查詢 `right` 是否存在與對應 `heads[i]` , 存在的話將 `heads[i]` 中的 `right` 移除 , 反之則表示已經沒有比 `num` 大的相鄰數字 * 更新最長相鄰數字的長度 #### 改進與實作 在 `longestConsecutive` 新增釋放記憶體的 code 避免 memory leak ```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); free(node); int left = num, right = num; while ((node = find(--left, n_size, heads))) { len++; list_del(&node->link); free(node); } while ((node = find(++right, n_size, heads))) { len++; list_del(&node->link); free(node); } length = len > length ? len : length; } } struct seq_node *seq, *tmp; for (int i = 0; i < n_size; i++) list_for_each_entry_safe(seq,tmp,&heads[i],link) list_del(&seq->link), free(seq); free(heads); return length; } ``` ### 延伸問題二 參考 Q1 的 hash table 實作 , 結構改為如下 ```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 hash_key { int key; void *data; struct hlist_node node; }; ``` 沿用 Q1 程式碼 , 並參考 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) `__hlist_del` 函式實作 `map_del` 用來移除 hash table 節點 `hlist_node` ```c void map_del(struct hlist_node *n) { struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; *pprev = next; if(next) next->pprev = pprev; } ``` 修改 `longestConsecutive` , 以 `map_t` 來尋找最長連續整數長度 ```c int longestConsecutive(int *nums, int n_size) { map_t *map = map_init(10); int length = 0; for (int i = 0; i < n_size; i++) { int *p = map_get(map,nums[i]); if(!p) { p = malloc(sizeof(int)); *p = nums[i]; map_add(map,nums[i],p); } } for (int i = 0; i < n_size; i++) { int len = 0; int *num; struct hash_key *hk = find_key(map, i); while (hk) { len++; num = hk->data; int left = *num, right = *num; map_del(&hk->node); free(hk->data); free(hk); while ((hk = find_key(map,--left))) { len++; map_del(&hk->node); free(hk->data); free(hk); } while ((hk = find_key(map,++right))) { len++; map_del(&hk->node); free(hk->data); free(hk); } length = len > length ? len : length; } } map_deinit(map); return length; } ``` [題目連結](https://hackmd.io/@sysprog/linux2022-quiz1)