2022q1 Homework1 (quiz1)

contributed by < ShawnLu31 >

題目

測驗 1

解題

map_add 分配一個節點空間，並將此節點放入 hash table 。
宣告完 h n 後：

first 指向該 hash table 的欄位的必一個節點，可能是 NULL，因此用 if 確認節點的的存在。

AAA;
if (first)
    first->pprev = &n->next;
h->first = n;
BBB;

對節點執行已知的操作後：

由此可得知　n->pprev 須指到 hlist_head， n->next 須指向原本的首位節點 fisrt。

• AAA => n->next = first;
• BBB => n->pprev = &h->first;
  

Hash table

data struct

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;

/**
 * @key, 儲存陣列 array 的元素
 * @data, 儲存上述元素的索引值
 * @node, 用於 hash table 中 bucket 的實作
 */
struct hash_key {
    int key;    
    void *data;
    struct hlist_node node;
};

建立 hash table

建立 hash table 。

分配 map_t 大小的空間。
依照參數 bits 分配 hlist_head 空間給 ht 指標。
做初始化，將所有 linked list 開頭指標指向 NULL 。
回傳 hash table 的指標 map 。

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 中搜尋並回傳一節點 kn ， 且 kn->key 等於 key 。

將 key 經過 hash function 計算後找到對應的 hlist_head ，依序走訪該 linked list 並檢查目標資料 key 是否存在該 linked list 中。若存在則回傳該節點 kn ，若不存在則回傳 NULL。

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

獲取資料

呼叫 find_key 取得 bucket，回傳 bucket 中儲存的 data (索引值)。

/** 
 * @param map, 目標 hash table
 * @param key, 陣列 nums 中的元素
 * @return void*
 */
void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

儲存資料

若資料不存在於 hash table ，則加入元素資料至 hash table 。

分配節點空間，儲存元素的數值與索引值。
經過 hash function 計算找對對應的　linked list 並加到 linked list 的開頭。

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

清除 hash table

釋放 hash table 的空間。

走訪所有 hash table 的節點，將其從 linked list 移除後釋放其空間。

TODO: why !n->pprev == /* unhashed */ ?

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

Two Sum

給定一陣列 nums 和一個目標值 target ，回傳 nums 的 2 個元素相加會等於 target 的索引值。

建立 hash table map。
依序檢查陣列的元素， map_get 會在 hash table 尋找是否有元素與現在的元素相加為 target 。若存在， p 即為另一元素的索引值。若不存在，則用 map_add 將現在檢查的元素儲存至 hash table。
最後清除 hash table ，並回傳 2 個元素的索引值 ret。

/**
 * @param nums, 給定的陣列
 * @param numSize, 陣列大小
 * @param target, 目標值
 * @param returnSize, 回傳的陣列大小，若有解為 2，無解則為 0
 */
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    map_t *map = map_init(10);
    *returnSize = 0;
    int *ret = malloc(sizeof(int) * 2);
    if (!ret)
        goto bail;

    for (int i = 0; i < numsSize; i++) {
        int *p = map_get(map, target - nums[i]);
        if (p) { /* found */
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

研讀 linux 核心程式碼

測驗 2

解題

刪除 Singly-linked list 裡所有重複的節點， 串列可能為空或 NULL 。

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

程式碼被 if 分成三個部分：

1. head 為 NULL 。

處理傳入的串列為 NULL 的情況，可能是原串列為 NULL 或遞迴到串列尾端的終止遞迴條件。

2. head 不為 NULL，且 COND1 成立。

處理刪除重複節點的部分。
COND1 檢查 head head->next 兩節點資料重複時，所以 COND1 為 head->val == head->next->val 。但傳入的 head 可能只有一個節點 (head->next 為 NULL)，所以須檢查 head->next != NULL 。所以 COND1 為

head->next && head->val == head->next->val

再透過 while 迴圈刪除其他重複數值的節點。當 head下一個節點 head->next 重複時，將 head 直接指到下一個節點 head->next ，跳過重複的節點 head 。且與 COND1 相同，走到最後一個節點時， head->next 會為 NULL ，所以 COND2 為

head->next && head->val == head->next->val

離開迴圈後，要繼續尋找並刪除下一個重複節點，所以再次呼叫 deleteDuplicates ，且因為 head 也是重複的節點，所以傳入 deleteDuplicates 的參數為 head->next 。

3. 非上述兩種情形。

因為重複的節點已被第二部分處理完，所以這裡的 head 不會是重複的節點，只需使用 deleteDuplicates 找到 head->next 要接的節點，在回傳 head 。

無遞迴版本

迭代版

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    
    bool is_dup = false;
    struct ListNode **indir = &head;
    for (; *indir;) {
        if ((*indir)->next && (*indir)->val == (*indir)->next->val) {
            (*indir)->next = (*indir)->next->next;
            is_dup = true;
        } else {
            if (is_dup) {
                /* delete the last duplicated node */
                (*indir) = (*indir)->next;
                is_dup = false;
            } else {
                indir = &(*indir)->next;
            }
        }
    }
    
    return head;
}

使用指標的指標 indir 實作迭代版本。
比較兩個節點，若為重複節點則移除後者，直到重複的節點只剩一個(首個重複節點)，並用 is_dup 紀錄此節點是否為剩餘的重複節點。

circular doubly-linked list 改寫

遞迴

void deleteDuplicates(struct list_head *head, struct list_head *l)
{
    if (!head)
        return;
    if (list_empty(head) || list_is_singular(head))
        return;

    if (l == head)
        return;

    if (l->next != head && list_entry(l, ListNode, list)->val == list_entry(l->next, ListNode, list)->val) {
        while (l->next != head && list_entry(l, ListNode, list)->val == list_entry(l->next, ListNode, list)->val) {
            l = l->next;
            list_del(l->prev);
        }
        l = l->next;
        list_del(l->prev);
        deleteDuplicates(head, l);
        return;
    }


    deleteDuplicates(head, l->next);
    return;
}

迭代

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

    if (list_empty(head) || list_is_singular(head))
        return head;

    bool is_dup = false;
    ListNode *node, *next;
    list_for_each_entry_safe (node, next, head, list) {
        if (node->val == next->val) {
            // delete the duplicated node
            list_del(&node->list);
            free(node);
            is_dup = true;
        } else {
            if (is_dup) {
                // delete the last duplicated node
                list_del(&node->list);
                free(node);
                is_dup = false;
            }
        }
    }

    return head;
}

測驗 3

解題

1. MMM1
   觀察得知：

• for 迴圈的巨集。
• 迴圈內部會刪除節點 → safe 版本的巨集。
  MMM1 為 list_for_each_entry_safe

2. MMM2
   觀察得知：

• for 迴圈的巨集。
• 比對節點資料，若比對成功立即結束迴圈 → 不需 safe 保護。
  MMM2 為 list_for_each_entry

3. MMM3
   觀察得知：

• 用途與 MMM2 相同。
  MMM3 為 list_for_each_entry

4. MMM4
   觀察得知：

• 函式，回傳一個節點。
• 在 hash table 容量滿時使用，並移除該回傳節點的連結 → 刪除 LRU 的節點並使用其空間。
  而在 lRUCacheGet 與前段 MMM3 的程式碼中，比對到的節點 (Used) 會使用 list_move 將該節點加入 obj->dhead 的首個節點，因此 obj->dhead 的最後一個節點就是 LRU 的節點。
  MMM4 為 list_last_entry

題目	解答
MMM1	list_for_each_entry_safe
MMM2	list_for_each_entry
MMM3	list_for_each_entry
MMM4	list_last_entry

解釋程式碼

Cache 結構

• capacity, hash table 的容量大小。
• count, 已加入的資料數量。
• dhead, 快取，紀錄存取過資料的 linked list ，開頭為最近存取的資料，尾端則是 LRU 的資料。
• hheads, hash table 。

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;

Node 結構

• key, 儲存的資料，用來計算 hash 值，幫助搜尋。
• value, 儲存的資料。
• hlink, 連接 hash table 的節點。
• dlink, 連接 dhead linked list 的節點。

typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

建立 LRU Cache

/**
 * @brief 建立 cache 資料結構並初始化
 */
LRUCache *lRUCacheCreate(int capacity)
{   
    LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
    // 初始化變數
    obj->count = 0;
    obj->capacity = capacity;
    // 初始化 dhead 與 hash table
    INIT_LIST_HEAD(&obj->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_LIST_HEAD(&obj->hheads[i]);
    return obj;
}

新增資料

/**
 * @brief 新增資料 (key, value)至 LRUCachee 
 * 
 * - 搜尋資料
 *     - 更新(資料存在)
 *       1. 用 Hash(key)  hash table 中尋找資料
 *       2. 將該節點移至 dhead 首位 (Used)
 *       3. 更新 value 資料
 * 
 * - 加入資料
 *     - 取代(資料不存在，快取已滿)
 *       1. 將 LRU 節點從 dhead 移除
 *       2. 將 LRU 節點從 hheads 移除
 *       3. 放入新的資料
 *       4. 該節點重新連結至 dhead 與 hheads 
 *     
 *     - 新增(資料不存在，快取未滿)
 *       1. 配置節點空間
 *       2. 放入新的資料
 *       3. 該節點重新連結至 dhead 與 hheads 
 * 
 * @param obj, LRUCache 物件
 * @param key, 用於比對的資料
 * @param value, 欲新增的資料
 */
void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    // 搜尋資料
    list_for_each_entry(lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            // 資料存在，將該節點移至 dhead 首位
            list_move(&lru->dlink, &obj->dhead);
            // 更新 value
            lru->value = value;
            return;
        }
    }
    // 新增資料
    if (obj->count == obj->capacity) {
        // 快取已滿
        // 取得 LRU 的節點
        lru = list_last_entry(&obj->dhead, LRUNode, dlink);
        // 將該節點從 linked list 移除
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        // 快取未滿
        // 配置節點空間
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    // 新資料加入節點
    lru->key = key;
    // 連接至 LRUCache
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    // 新資料加入節點
    lru->value = value;
}

取得資料

/**
 * @brief 在 LRUCache 中尋找資料並回傳
 * 
 * 用 key 計算 hash 值並在該 hheads 欄位尋找資料
 * 若找到資料回傳 value ，沒找到回傳 -1
 * 
 * @param obj
 * @param key
 * @return int
 */
int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    // 走訪 hheads[hash] 欄位的 linked list
    list_for_each_entry(lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            // 若找到資料將該節點移至 dhead 首位
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

清除 Cache

/**
 * @brief 清除 LRU cache
 * 
 * 刪除 cache　中的節點後，再清除 cache
 * 因為 dhead 和 hheads 是共用同樣的節點(LRUNode)
 * 只是分別用 dlink, hlink 連接
 * 用其中一個來刪除節點即可
 * 
 * @param 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); 
}   

測驗 4

解題

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

left 和 right 分別往 num 的左右兩側在 hash table 中尋找有連續數值的節點，若找到長度 len 加一， 所以 left 會隨著迴圈減一， right 則會加一。而兩者的初始值都是 num ，在尋找前須先減一（加一），避免重複找到 num 。
LLL 為 --left 。
RRR 為 ++right 。

解釋程式碼

搜尋數值

在 hash table 中尋找數值是否存在。

根據 hash 值到對應的欄位搜尋數值 num 是否存在，若存在則回傳該節點，否則回傳 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;
}

計算最長的連續數值

分成兩部分：

1. 將陣列 nums 的元素加入 hash table。
2. 依據 hash table 計算最長的連續數值。

第一部分
迴圈依序檢查陣列 nums 的元素，因目標為計算連續的數值，重複的數值只須計入一次，所以需檢查該元素是否以存在 hash table ，若存在，跳過該元素，若不存在則將其加入 hash table 。

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 迴圈依序在 hash table 尋找陣列 nums 的元素。若找到 num ，表示該數值尚未被計算過，使用 while(node) 迴圈計算連續數值長度 len 。若 find 回傳 NULL 表示該數值已被計算過，則跳過此元素，避免重複計算。

while(node) 迴圈裡，長度 len 加一，刪除 num 的節點，避免重複計算。
接著使用 left 和 right 變數分別向 num 的左右兩側尋找連續的數值是否存在， left 會隨著迴圈逐漸減一， right 逐漸加一。若是找到該數值的節點，使長度 len 加一並刪除該節點。
length 為該陣列最長連續數值長度， len 為單次迴圈計算最長連續數值長度，檢查 len 是否大於 length，更新 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(--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;
    }
}

最後回傳 length 。