2022q1 Homework1 (quiz1)

contributed by < AmyLin0210 >

2022q1 第 1 週測驗題

q1

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

map_init

在這裡會有一個由 hlist_head 所組成的陣列，若這個陣列的大小為 10 ，那也就表示這裡有相對應的 10 條 hlist。

下面為課堂測驗中的示意圖：

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

map_add

首先會先找到該 key 相對應的雜湊值，再將相對應的節點接到相對應的 hlist 上面。

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

pprev 是指標的指標的好處

現在我們就針對 hash map 是如何連接得來進行討論。
這裡是課堂測驗所提供的示意圖：

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

因為在這裡 hash table 在意的只有，現在如果我想要刪除一個節點，那要怎麼將其前後給連接起，並不在乎是不是能夠拿到前一個節點的位置。我們可以看到 pprev 是一個指標的指標，所指向的位置是前一個節點 next 的位置，這個可以實現我們前面所提到的問題。

如果現在我想要去刪除掉一個節點，我所需要做的事情就只有

將欲刪除的節點後面那個節點的 pprev 更改為該節點的 pprev
把該節點 pprev 的值更改為自己的下一個節點
把該節點刪掉

範例程式碼如下：

void map_del(struct hlist_node *n)
{
    if (!n)
        return;

    if (n->next) {
        n->next->pprev = n->pprev;
    }
    *(n->pprev) = n->next;
    free(container_of(n, struct hash_key, node)->data);
    free(container_of(n, struct hash_key, node));
}

以下是示意圖，若現在想要刪除的節點為 L2：

確認 L2 的 next 是否為 NULL，若不是，則將 L2 的下個節點 (L3) 的 pprev 變更為 L2 的 pprev 的值 (也就是 L1 的 next 的位置)。
將 L2 的 pprev 的值 (也就是 L1 的 next) 改為 L3 的位置
刪除 L2

Before

After

且在特殊情況 (例如該 linked-list 只有一個節點)，此範例程式碼也能處理。
現在假設只有一個節點 (L1) ，且要刪除掉該節點。

由於 L1 的 next 為 NULL，所以不對 L1 的 next 節點做處理。
更改 L1 的 pprev (在這裡為 head 的 first) 的值，由於 L1 的 next 為 NULL，故更改它為 NULL。
刪除掉 L1 這個節點。

Before

After

q2

COND1 = head->next && head->val == head->next->val
COND2 = head->next && head->val == head->next->val

遞迴版本的程式碼：

#include <stddef.h>

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

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

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

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

q3

MMM1 = list_for_each_entry_safe
MMM2 = list_for_each_entry
MMM3 = list_for_each_entry
MMM4 = list_last_entry

在這題裡，是使用 hash table 來使得 LRU 的操作能夠維持在 O(1) 的時間複雜度

資料型態

首先看到資料型態的部份，可以看到有兩個 struct，分別是 LRUCache 與 LRUNode

LRUCache: 儲存 cache 的大小、目前有多少東西存在 cache 裡的資訊
LRUNode: 節點的資訊都儲存在裡面，包含自己的 key、value。

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

在這裡總共會需要維護兩種 list

第一種的開頭是 dhead ，它維護的主要內容是所有節點最後被使用到的時間序，若有節點被使用到，會被更新放置到此 list 的前方，反之若 cache 已經滿了，會從這條 list 的最後方開始移除節點，在這裡將這條 list 稱為 dlist。
第二種主要維護的是 hash table，假設有某個 key 經過 hash 後的結果是 i，那相對應的節點會被儲存於 hhead[i] 所維護的 list 中。在這裡將這種 list 稱為 hlist。

lRUCacheCreate

在 lRUCacheCreate 這個函式裡面，它初始化了這個 Cache 所需要的資料結構。

首先看到第 3 行它宣告了多少的記憶體空間。除了 LRUCache 的大小之外，它還額外的宣告出了 capacity * sizeof(struct list_head) 的空間。回去看看 LRUCache 的資料型態，最後面的變數是 struct list_head hheads[] ，利用了 Arrays of Length Zero 的特性，所以我們能夠透過第 3 行的程式碼，初始化一條 struct list_head 的 array。










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

lRUCachePut

在這裡所做的事情是檢查 key 是否已經存在，若存在就更新 value 與其在 dlist 內的位置，若不存在，就檢查 cache 是否已經滿了，並按照相對應的結果去更新相對應的節點。

在第 5 到第 10 行，它所作的事情就是去確認是否 key 已經存在，若存在了，就更新節點的 value，並將他的位置挪置 dlist 的最前方。

在第 13 行之後，所做的事情就是，若 key 還不存在，那要如何去新增節點。

























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) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = list_last_entry(&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;
}

以下是若 cache 已經滿了、有新的節點要被儲存的示意圖，在這邊假定 cache 的大小只有 2，新的 key 為 2，value 為 2，hash 後的結果為 0。

在最加入新節點前的示意圖如下，粉色的為 dlist，藍色的為 hlist。

現在想要加入新的節點，由於 cache 的空間已經滿了，所以是必要挑出節點移除，在此移除的是 key 為 1， value 為 1 的節點。

lRUCacheGet

這個函式目標是尋找 cache 內特定 key 的值。

首先它會先找到相對應 key 的 hlist，從中尋找該 key 是否存在，若該 key 有存在，就回傳他的值並更新 dlist 內相對應的位置。

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

lRUCacheFree

清掉 cache 所使用到的記憶體空間。
在這邊由於 dlist 與 hlist 所連接起來的節點其實是相同的，所以只要走訪過一次 dlist 並清除節點即可完成。

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

指出其中可改進之處並實作

目前我想到的可改進之處為 hash function。
在原程式碼內的 hash 只是簡單的找餘數，所以很有機會會碰到 collision，待閱讀相關文章後再補齊這部份的內容。

q4

LLL = –left
RRR = ++right

在 longestConsecutive 這個函式裡，下方程式碼內的第 26 行到第 33 行，在這裡做的事情是建 hash table。
首先先利用 find 來確認是否進來的數值已經存在，若已經存在，會回傳已經存在的那個節點，若不存在，會回傳 NULL。

在第 35 到 57 行，目標是找到最長的連續數列。此 hash 出現在第 9 行，就是由數字去 mod 他的 size，所以也就可以知道，如果有連續的數字，那必然會出現在他左右的 hash list 中。
在 45 與 50 行間，分別是往左與往右找，若有找到，就將該 node 給刪除掉，並把 len 加一。




























































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

    return length;
}

2022q1 Homework1 (quiz1)

q1

map_init

map_add

pprev 是指標的指標的好處

q2

q3

資料型態

lRUCacheCreate

lRUCachePut

lRUCacheGet

lRUCacheFree

指出其中可改進之處並實作

q4

Read more

Lockless Multithreaded Logger 實作

2022q1 Homework3 (quiz3)

2022q1 Homework2 (quiz2)

2022q1 Homework1 (lab0)