# 2022q1 Homework (quiz1)
contributed by <`raysun0729`>
[測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1)
## 測驗一

void map_add(map_t *map, int key, void *data)
{
    //check if key is in the hash table
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;
    //if not found then continue
    //將資料複製至kn
    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;
    /* h 指向hash table中對應 entry 的位址
   * first 指向hash table中對應 entry 的首個節點位址
   * n 指向剛分配的kn中的 node 位址
   * */
    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;
    AAA;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    BBB;
}

`AAA` = `n->next = first`
`BBB` = `n->pprev = &h->first`

觀察得知在第12行前資料皆已存入節點之中，因此12~16行的目的應是將節點加入 linked list 之中。

由於並非circular linked list 的結構，因此將節點從開頭插入，從第13、14行，可看出其目的在於將 first 的 pprev 指向新增之節點。

於是第12行應為先將新增之節點先指向 first ，第13、14行才可以將節點正確串接，第15行將 first 作為新增的節點，而在第16行 BBB 將被新增的節點的 pprev 指回 hlist_head 。
## 測驗二

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

`COND1` = `head->next && head->val == head->next->val`(檢查第一個重複值元素)
`COND2` = `head->next && head->val == head->next->val`(將head移到重複元素的最後一個)

從註解可看出，我們要刪除重覆數值的節點。因此作法上先確定下個節點不為空，並比較當前之節點與下個節點的資料是否相等，若相等則一直將指標往後移，直到當前結點與下個節點不相同並回傳指標，將回傳的指標串接上head

## 測驗三

#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;

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;
    MMM1 (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;
    MMM2 (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;
    MMM3 (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 = MMM4(&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;
}

`MM1` = `list_for_each_entry_safe`
`MM2` = `list_for_each_entry`
`MM3` = `list_for_each_entry`
`MM4` = `list_last_entry`

* `lRUCacheFree` : 要放cache記憶體。所以走訪 linked list，且對當前節點進行操作，執行資源釋放，所以MM1 = `list_for_each_entry_safe`
* `lRUCacheGet` : 我們要找到bucket以讀取特定cache，因為只要查看，沒有要進行操作移除節點，所以 MMM2 應該為 `list_for_each_entry` 。
* `lRUCachePut` : 這邊在 cache 中搜尋資料，將 cache miss 的資料存入 cache 所以進行存放資料的動作。所以 MM3 應該為 `list_for_each_entry`。根據LRU的定義，要移除last reference element，所以 MM4 應為`list_last_entry`
## 測驗四

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

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(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

`LLL`=`--left`；`RRR`=`++right`
待補完...