2022q1 Homework1 (quiz1)

contributed by < cy023 >

測驗題

測驗 `1`

Hash Table

map_t 結構內紀錄 hash table 的欄位數量共 1 << bits 個，起始位址 ht 指向由 struct hlist_head * 型態構成的陣列。

比較特別的地方在 hlist_node 的 **pprev 用了指標的指標，參考第 1 週課堂問答簡記。

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;

包裝了 struct hlist_node 結構的節點，另外包含經過 hash function 的 key 與儲存的資料。

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

初始化 Hash Table

配置 map_t 空間存放 hash table 的 Bucket 大小與起始位址的資訊。

配置 struct hlist_head 型態陣列，共 (1 << bits) 個 Bucket，全都指向 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;
}

釋放 Hash Table 使用空間

依序將每個 Bucket 連接的節點，利用 container_of 找出完整空間後釋放。

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

不太清楚何時會發生 n->pprev 等於 NULL，將此判斷註解仍能通過 LeetCode 測資…


if (!n->pprev) /* unhashed */
    goto bail;

若 Bucket 內還存在 next 節點時，先將節點 remove，next、pprev 都指向 NULL 後再進行記憶體釋放。





struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
    next->pprev = pprev;
n->next = NULL, n->pprev = NULL;

Hash Function

What …?
TODO…

#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 table 內查找，給定 key 值的節點。
先利用 hash function 找到對應 bucket，再於該 bucket 指向的 hlist_node 內尋找(使用 container_of 取得 hash_key 的完整資訊，再與給定 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;
}

給定 key 在 hash table 中查找對應的 data。

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

在 hash table 中新增節點。
配置 struct hash_key 大小的空間，填入 key, data 資訊。
line10 先對 key 值進行雜湊，找到對應的 bucket - h。
line11 新增的 hash_key 節點 n，bucket 內的第一個節點 first。

因為要把 n 插入進 bucket 的第一個節點，所以將新節點的 next 指向 first，若 bucket 不為空 (first 不為 NULL)，將 first->pprev = &n->next;。

n->next = first;

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

h->first = n;

n->pprev = &h->first;

















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

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

測驗 `2`

LeetCode 82. Remove Duplicates from Sorted List II

遞迴版本

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

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

迭代版本

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    
    struct ListNode *p = malloc(sizeof(struct ListNode));
    p->next = head;
    p->val  = head->val - 1;
    
    struct ListNode **indirect = &p;
    struct ListNode *trace = (*indirect)->next;

    while (trace) {
        while (trace && (!trace->next || (trace->next && trace->val != trace->next->val))) {
            indirect = &(*indirect)->next;
            trace = (*indirect)->next;
        }
        while (trace && (*indirect)->next->val == trace->val) {
            // struct ListNode *tmp = trace;
            trace = trace->next;
            // free(tmp);
        }
        (*indirect)->next = trace;
        trace = (*indirect)->next;
    }
    
    head = p->next;
    free(p);
    return head;
}

測驗 `3`

LeetCode 提交版

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

/*------------------------------------------------------------*/
// #include "list.h"
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;
}

static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

#define list_entry(node, type, member) container_of(node, type, member)

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)

#define list_for_each_entry(entry, head, member)                       \
    for (entry = list_entry((head)->next, __typeof__(*entry), member); \
         &entry->member != (head);                                     \
         entry = list_entry(entry->member.next, __typeof__(*entry), member))

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

/*------------------------------------------------------------*/

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;
    list_for_each_entry_safe (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;
    list_for_each_entry (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;
    // hit
    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) { // eviction
        lru = list_last_entry(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else { // miss
        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

測驗 `4`

LeetCode 提交版

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

/*------------------------------------------------------------*/
// #include "list.h"
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;
}

#define list_entry(node, type, member) container_of(node, type, member)

#define list_for_each_entry(entry, head, member)                       \
    for (entry = list_entry((head)->next, __typeof__(*entry), member); \
         &entry->member != (head);                                     \
         entry = list_entry(entry->member.next, __typeof__(*entry), member))

/*------------------------------------------------------------*/

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

LLL --left
RRR ++right

2022q1 Homework1 (quiz1)

測驗 1

Hash Table

初始化 Hash Table

釋放 Hash Table 使用空間

Hash Function

新增節點

測驗 2

遞迴版本

迭代版本

測驗 3

測驗 4

Read more

2022q1 Homework3 (quiz3)

2022q1 Homework2 (quiz2)

2022q1 Homework3 (fibdrv)

2022q1 Homework1 (lab0)

測驗 `1`

測驗 `2`

測驗 `3`

測驗 `4`