# 2022q1 Homework (quiz1)

contributed by <`ray90514`>
[題目](https://hackmd.io/@sysprog/linux2022-quiz1)

## 測驗一

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;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    BBB;
}

這段程式碼的用途是要將 key 加入到 hashtable 裡，而後半段的程式碼是將建立的節點加入給定的 list 。



struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };

由圖可以看出有四個指標需要修改 `h->first`, `n->pprev`, `n->next`, `first->prev` ，上述程式碼已經修改了兩個，所以 `AAA` 和 `BBB` 是修改 `n` 的兩個指標。

n->pprev = &h->first;
n->next = first;

### 延伸問題

程式的運作如下，給定一個 `sum` 及一個數字 `num` ，我們需要看 `sum - num` 是否在陣列裡面，比較快速的作法是對將陣列的數字建成 hashtable ，這樣查找一個數字只需要 $O(1)$ ，確認整個陣列要 $O(n)$ 。這裡有個細節是查找與建立 hashtable 可以同時進行，這樣就一次迴圈就能完成。
## 測驗二

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

這段程式碼是採用遞迴的方式移除重複的節點的。

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

這一行是將 `head` 與以 `head->next` 為開頭被移除重複節點的串列接在一起，代表 `head->next` 以前都是不重複的。所以中間那段程式碼是要從 `head` 開始移除重複的節點。 `head` 有重複的條件，因為要比較 `head->next` 的值所以要加上判斷不為空指標， `COND1` 就是 `head->next && head->val == head->next->val` ，如果有重複發生，接下來就是要使用迴圈找出所有重複的節點，所以 `COND2` 與 `COND1` 相同。

### 延伸問題

#### 使用迴圈修改程式碼。

#include <stddef.h>

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

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    int is_dup = 0;
    struct ListNode *node = head;
    struct ListNode **prev = &head;

    while (node) {
        if(node->next && node->val == node->next->val) {
            is_dup = 1;
        }
        else if (is_dup) {
            is_dup = 0;
            *prev = node->next;
        }
        else {
            prev = &(*prev)->next;
        }
        node = node->next;
    }
    
    return head;
}


`prev` 是一個指標的指標，使用 `node` 走訪整個串列，如果 `node` 和 `node->next` 的值不同就移動 `prev` 和 `node`。


如果 `node` 和 `node->next` 的值相同就跳過重複的節點，直到找到不同的節點，將 `prev` 所指的 `next` 指標指向該節點。


重複以上動作直到所有節點都被走訪過。

#### 以類似 Linux 核心的 circular doubly-linked list 改寫
兩個版本都與原本相似，更改了原本對 `NULL` 的判斷，以及對 `prev` 的處理

struct ListNode {
    int val;
    struct list_node list;
};

遞迴版本。

struct list_node *deleteDuplicates(struct list_node *head)
{
    static  struct list_node *h = NULL;
    
    if (head == h)
        return h;
    
    if(!h)
        h = head;
    
    if (head->next != h) {
        int val = list_entry(head, ListNode, list)->val;
        int val_next = list_entry(head->next, ListNode, list)->val;
        
        if(val == val_next) {
            /* Remove all duplicate numbers */
            while (head->next != h && val == val_next) {
                head = head->next;
                val = list_entry(head, ListNode, list)->val;
                val_next = list_entry(head->next, ListNode, list)->val;
            }
            return deleteDuplicates(head->next);
        } 
    }

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

迴圈版本，將原本指向前一個節點的 `next` 的指標改成指向前一個節點的指標。

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

    int is_dup = 0;
    ListNode *entry;
    ListNode *safe;
    struct list_head *prev = head;

    list_for_each_entry_safe(entry, safe, head, list) {
        if(&safe->list != head && entry->value == safe->value) {
            is_dup = 1;
        }
        else if (is_dup) {
            is_dup = 0;
            prev->next = &safe->list;
            safe->list.prev = prev;
        }
        else {
            prev = prev->next;
        }
    }
    return true;
}

## 測驗三

MMM1 (lru, n, &obj->dhead, dlink) {
    list_del(&lru->dlink);
    free(lru);
}

因為這裡面用到了 `list_del` ，可以判斷是帶有 `safe` 的 list 巨集，而 `lru` 是 `LRUNode` ，所以 `MMM1` 是 `list_for_each_entry_safe` 。

MMM2 (lru, &obj->hheads[hash], hlink) {
    if (lru->key == key) {
        list_move(&lru->dlink, &obj->dhead);
        return lru->value;
    }
}

MMM3 (lru, &obj->hheads[hash], hlink) {
    if (lru->key == key) {
        list_move(&lru->dlink, &obj->dhead);
        lru->value = value;
        return;
    }
}

`lru` 是 `LRUNode` ，而參數的數量為三個，所以 `MMM2` 和 `MMM3` 是 `list_for_each_entry` 。

if (obj->count == obj->capacity) {
    lru = MMM4(&obj->dhead, LRUNode, dlink);
    list_del(&lru->dlink);
    list_del(&lru->hlink);
}

`MMM4` 會回傳一個 `LRUNode` ， 所以可能為 `list_first_entry` 或 `list_last_entry` ，而這段程式碼是在 `LRUCachePut` 裡判斷當空間滿的時後，要挑選一個節點移除，題目是要做 Least Recently Used ，且 `lRUCacheGet` 會將存取到的節點搬到開頭，所以這裡要移除的是尾端的節點，因此 `MM4` 為 `list_last_entry`。

### 延伸問題
LRU 用串列來實作的話，其中一個做法是，當存取節點時將其搬至開頭或尾端，而需要移除或取代時，就從另外一端進行。




考慮到存取時的效率，可以將節點放入 hashtable 。本題的程式碼利用同樣的想法去實作 LRU Cache。

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

`dhead` 是負責處理 LRU 的串列， `hheads[]` 是 hashtable 的部分， `capacity` 紀錄最大的容量， `count` 紀錄現有的容量。這裡的 hash table 使用陣列和串列完成。 `LRUNode` 則儲存需要用的資料與指標。

LRUCache *lRUCacheCreate(int capacity)

建立指定容量的 `LRUCache` ，並初始化。

void lRUCacheFree(LRUCache *obj)

釋放所有`LRUCache` 及所含節點的空間。

int lRUCacheGet(LRUCache *obj, int key)

取得 key 所對應的 value 。先是用 hashtable 直接取得節點，再將該節點移至串列的開頭。

void lRUCachePut(LRUCache *obj, int key, int value)

儲存 key 與對應的 value ，先是在 hashtable 中檢查 key 是否已存在，若存在就直接返回值。若不存在且容量沒滿則要建立一個新節點，若是容量滿了則要取代尾端的節點。最後將這個節點放入串列的開頭，以及 hashtable 對應的位置，還有更新 `count`。

#### 改善

使用 `hlist_head` 跟 `hlist_node` 取代原本的 `list_head` ，將原本 list 的巨集換成 hlist 的。

typedef struct {
    int capacity, count;             
    struct list_head dhead;
    struct hlist_head hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head dlink;
    struct hlist_node hlink;
} LRUNode;

以下是測試用的程式碼。`min` 是找出陣列最小值的 index ， `init` 是將陣列初始化為零。測驗方法是放入與最大容量相同的資料，對這些資料做隨機存取。最後確認這些資料被取代的順序是否為 LRU ，使用時間戳的方法進行確認，有一個陣列 `count` 負責紀錄時間戳，每次存取都會更新，時間戳最小者為要被取代的。

int main(int argc, char *argv[]) {
    int test_n = 100;
    int test_m = 10;
    int size = 16;
    int *count = malloc(size * sizeof(int));
    LRUCache *cache = lRUCacheCreate(size);

    srand(0);
    for (int j = 0; j < test_m; j++) {
         init(count, size);
        
        /* put data */
        for (int i = 0; i < size; i++) {
            count[i] = i;
            lRUCachePut(cache, i, rand());
        }

        /* random access */
        for (int i = size; i < test_n; i++) {
            int key = rand() % size;
            count[key] = i;
            lRUCacheGet(cache, key);
        }

        /* check the result */
        for (int i = 0; i < size; i++) {
            int key = size + i;
            lRUCachePut(cache, key, rand());
            key = min(count, size);
            if(lRUCacheGet(cache, key) != -1) {
                lRUCacheFree(cache);
                free(count);
                printf("fail\n");
                return 0;
            }
            count[key] = test_n + 1;
        }
    }
    printf("sucess\n");
    free(count);
    lRUCacheFree(cache);  
    return 0;
}

## 測驗四

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

題目是要找出陣列中最長序列的長度，而這段程式碼是某個數字找出它所處的序列的長度。 `find` 可以找出第一個參數的數字是否存在，所以可以用來尋找某個數字 n 的 ..., n - 2, n - 1, n, n + 1, n + 2, ... 是否存在，以確定序列的長度。 所以 `LLL` 和 `RRR` 各為一個以 `num` 遞增和遞減的表示式，因為 `left` 和 `right` 初始值為 `num` ，所以可能為 `--left` 和 `++right` 或 `++left` 和 `--right` 。

### 延伸問題

程式運作大致如下，對給定陣列內的數字建立不重複的 hashtable ，用這個 hashtable 可以快速得知該數字存不存在。

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]);
    }
}

接下來找出陣列內的每個數字所在序列長度的最大值，查找方法如上述所說，查找過的數字要從 hashtable 移除，因為是同一序列，再一次遇到可不必查找。

###### tags: `linux2022`