---
tags: Linux Kernel
---

# 2022q1 Homework1 (quiz1)
contributed by < `kevinshieh0225` >
> [作業需求](https://hackmd.io/@sysprog/B166rc3Jq)
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz1)

部分參考 `freshLiver` 的[筆記](https://hackmd.io/DkeAf1ziR4Ggm4-2G5G0EA?view)作法進行改寫。

## 測驗 1 Hash Map Implementation
Two Sum 是在 leetcode 上的經典首選，讓大家見識到 hash table 演算法的妙用。本測驗希望我們進入到 hash table 內部實作中。

### hash table 實作結構
hash table (HT)的性質如下：輸入特定鍵（key），HT 將回傳其對應的值(value)。基於一對一關係，理想上可使索取的時間複雜度為 O(1)。

在 HT 的實作如下：由於建立一個能含括所有 key 的 HT 是不實際的，故我們先為 key 做編碼，對應到我們建立的有限目錄中，隨後以 linked list (ll)的結構將鍵值串接起來（如同我們先將資料分門別類，隨後從分類中尋找我們要的是否存在）。

(取自 [jserv](https://hackmd.io/@sysprog/linux2022-quiz1))

回到程式碼：map_t 建立 map ，其下會有 an array of hlist_head 。我們前面提到 key 會先編碼後置入目錄對應的 LL ，這裡即可看到我們會建立 $2^{bits}$ 個目錄與 LL 。

hash_key 與 hlist_node 即為 key/value 節點。在透過編碼後 hlist_node 被安插在對應目錄中，在尋鍵時透過尋訪 hlist_node 並以 container_of 取 hash_key 的值。

struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;

struct hlist_node { struct hlist_node *next, **pprev; };
struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

#define container_of(ptr, type, member)               \
    ({                                                \
        void *__mptr = (void *) (ptr);                \
        ((type *) (__mptr - offsetof(type, member))); \
    })

### hash table init
我們可以看到 map_t 初始化的過程，可以看到我們同時建立了一個 map_t 與（1 << bits == $2^{bits}$）個 hlist_head，若建立中有失敗則清除內容並返回 NULL。

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

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

### hash encode
執行 hash 的演算法。最後會生成並回傳一個 $[0, 2^{bits}-1]$ 範圍內的無號整數。

#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 find, get
**find_key function**：在 HT 中尋找是否有對應 key 值，若有則回傳對應的 hasy_key * ，若無則回傳 NULL。
這裡首先我們先確認 key 被放在哪一個編碼的 bucket 中，透過 **hash(key, map->bits)** 這個函式取得編碼，並在 array 中取得對應的 hlist_head。接著就是逐一尋訪該 LL 去確認是否有 key 於當中。

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

**map_get function**：從 HT 中確認是否有對應鍵值，若有則回傳鍵值對應的 value，若無則返還 NULL。
這裡特別的是此 function 的回傳值是 void pointer。這是一種很有彈性的作法，我們可以用 void pointer 去指不同的變數，再把它透過轉型（casting）還原回來。由於我們在這個實作中不確定是否能有對應的回傳鍵值，所以使用這個的方式，若回傳 NULL 即可讓 if-else 更直覺的判斷與執行對應操作。

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

### map_add 與考試答案
**map_add function**：確認是否有在 HT 中有對應鍵值，若有則不執行，無則新增鍵值在 HT 中。

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

在 AAA 到 BBB 的 程式碼意思是要將新的 hlist_node *n 插入在 hlisthead *h 的 first 位置，其中如果 h->first 早就已經有 hlist_node 時，我就插入兩者之間。

:::info
AAA 應為 (c\) n->next = first
BBB 應為 (a) n->pprev = &h->first
:::

## 測驗 2 : [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

本題透過遞迴的方式實現刪除重複節點的函式。其中：

:::info
COND1 = head.next != null && head.val == head.next.val
COND2 = head.next != null && head.val == head.next.val
:::

為何需要用 if 來包裝和裡面 while 相同的條件式呢？看似重複操作，但其實是因為條件內外執行操作是不同的行為，而必須在新增一個 if(COND1) 來隔離條件。

在 if(COND1) 內的操作是我們已經確定要移除當下重複的節點了，我們用 while 不斷將 head 重新指向其後，並在最後 return 遞迴中 head->next 的 ListNode 在這一番的操作下便可以把所有重複節點在這操作下完全移除。

相比於此，我們看 if(COND1) 外的操作：我們先對 head->next 後的節點進行 deleteDuplicates 的遞迴整理，最後回傳的還是 head node ，光是操作和回傳的形式都不同，而使他必須用 if(COND1) 來做內外切分。

### iterate version

#include <stddef.h>

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

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    struct ListNode **ckp = &head;
    struct ListNode *iter = (*ckp)->next;
    while (iter) {
        if ((*ckp)->val == iter->val) {
            do {
                iter = iter->next;
            } while (iter && (*ckp)->val == iter->val);
            *ckp = iter;
            if (!iter)
                break;
        } else {
            ckp = &((*ckp)->next); 
        }
        iter = iter->next;
    }
    return head;
}

## 測驗 3 : [146. LRU Cache](https://leetcode.com/problems/lru-cache/)

在 Cache replacement policies 中，Least Recently Used 是一個策略之一。當 Cache 要更新時，將裡頭最後被使用的資料去除並更新。在 LRU 演算法我們面臨的問題是：如何在常數時間內達到兩件目的：如何確認 Cache hit、如何更新使用時間的紀錄。

### LRU Cache 實作原理：Hashmap + DoubleLinkedList

透過 Hashmap 可在常數時間裡「確認是否 Cache hit」；透過 DoubleLinkedList 讓我們在常數時間裡「更新 Cache 紀錄」。

這時可能會有一個問題是：如果要做 DoubleLinkedList 的尋訪，那應該也需要線性時間吧？然而我們如果搭配著 list.h 與 container_of 的技巧：在 Hashmap 與 DoubleLinkedList 上使用**共用**的 list_head 節點，那麼當我要維護 DoubleLinkedList 時，只要從 Hashmap 取得該節點更新；或是當我要刪除最近未使用的節點時，從 DoubleLinkedList 找到最末的節點。

LRUNode 是紀錄在 LRUCache 中的 DoubleLinkedList(DLL) 節點。

我們觀察 LRUCache，dhead 與 hheads[] 分別就是 DLL 的首節點，與第一題類似形式的 Hashmap 實作。
capacity 代表 Cache 的大小， count 代表目前總共有多少筆資料存放其中。

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

### LRU Cache create/free
在 lRUCacheCreate 中我們初始化紀錄使用時間 DLL 的 dhead，和紀錄是否存在其中的 Hashmap hhead[]。
在 lRUCacheFree 中我們也針對這些建立的動態記憶體位置依序釋放。
:::info
MM1 應填入 list_for_each_entry_safe ，在 DLL 中依序釋放節點，並不斷確認下一個節點是否為安全節點。
:::

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

### LRU Cache Get
輸入整數 key，如果其值有在 hashmap 中找到，更新 &obj->dhead 的 DLL結構，把該節點更新到開頭，代表最近使用，並回傳該 lru->value；若未找到則回傳 -1。

這裡可以看到這裡的編碼方式是 key 值除 capacity 得到 $[0, capacity-1]$ 的 hash ，相比前面的編碼來看是比較簡易的實作。

:::info
MMM2 應該是 list_for_each_entry。用該函數去尋訪 &obj->hheads[hash] 中的每個節點來確認是否該資料已存在於 hashmap 中。
:::

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

### LRU Cache Put

/**
 * @brief 插入新的鍵值並更新 Cache
 * 
 * @param *obj LRUCache
 * @param key 鍵
 * @param value 值
 */
void lRUCachePut(LRUCache *obj, int key, int value)
{
    /**
     * @ brief 執行 lRUCacheGet 行動：
     * 
     * 確認該 key 是否已存在於 Cache 中
     * 尋訪 LRUCache 的 HashTable
     * 若存在則更新 DLL 與該節點對應的 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;
        }
    }
    /**
     * 確認此時的 Cache 存放容量（count）是否已經達到上限
     * if 到達上限，準備更新最近未使用的節點資料
     * else 未達到上限，建立新節點並更新 count 的大小
     */
    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 節點進行更新
     */
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

:::info
MMM3 應填入 list_for_each_entry。
:::
:::danger
MMM4 應填寫 list_last_entry 取得 DLL 中最後一個節點，意即是最近未使用的節點。

答案卻是 list_for_each_entry？有點怪。
:::

## 測驗 4 : [128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/description/)

### 程式碼解析

/**
 * @brief LL 節點結構
 */
struct seq_node {
    int num;
    struct list_head link;
};                                                                                                                                                            
/**
 * @brief 尋訪 HashTable 中是否存在該資料
 *
 * 對 @num 取絕對值並編碼出所屬欄位
 * 尋訪該欄位確認是否存在該筆資料
 *
 * @param num 目標數值
 * @param size HT 大小（欄位大小）
 * @param *heads HT 的首節點
 * @return if true struct seq_node*; else NULL; 
 */           
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;
}

/**
 * @brief 從一組整數陣列中，回傳最長的連續數組
 * 
 * 1. 建立欄位數 = n_size 大小的 HashTable
 * 2. 將整數陣列的數值插入進 HashTable 中
 * 3. 尋訪最長連續數組
 * 
 * @param *nums 整數陣列
 * @param n_size 陣列之大小
 */
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]);
        }
    }

    /**
     * @brief 尋訪最長連續數組
     * 
     * length : 搜尋截至目前最長的連續數組
     * len : 本次搜索中的連續數組長度
     * 
     * for 迭代過所有的陣列數值
     * 
     *     len 重置為 0
     *     如果 node 存在於 HT 中，則開始尋找與其相連的連續數組
     * 
     *     while 向左 LLL = --left 搜尋連續數組
     *         若有則增加 len 長度，並刪除 HT 上該節點
     *     while 向右 RRR = ++right 搜尋連續數組
     *         若有則增加 len 長度，並刪除 HT 上該節點
     * 
     *     比較 length 與 len 的長度進行更新
     * 
     * 最後回傳 length
     */
    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;
}

:::info
LLL = \-\-left
RRR = \+\+right
:::