2022q1 Homework1 (quiz1)

contributed by < Wallmountain >

Q1

Leetcode 題目 : TwoSum

Structure

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 hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

pprev 的存在不是為了讓程式碼「更簡潔」，有其他更關鍵的作用。

jserv

• 利用指標的指標實作 pprev，讓程式碼更簡潔
• 在 hlist_head 中不需要指標指向前一個 node, 所以將hash table 的 structure 分成 hlist_node 和 hlist_head, 若 hlist_node 中使用指標 struct hlist_node *prev , 則在刪除 node 時， 需要使用 branch 去判斷 prev 是否有指向前一個 node, 故選擇使用指標的指標消除 branch
• data 的 type 為 void * 能夠讓 hash table 去 fit 不同 type 的資料

container_of

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

• 使用 container_of 從指標取得 struct hash_key 的 data 和 key
• offsetof 用來取得子物件在物件中的 offset (in bytes)

map_init

#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 大小 : 2^bit

map_deinit

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

• 走訪 map 中所有的 hlist_head 和 hlist_node
• 每走訪到一個 node, 若 n->next 存在， 便將 n->next->pprev 指向 next node 本身
• 每走訪到一個 node, free 當前的節點

map_get

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

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

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

• hash 為 hash function

map_add

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

• 若 data 不在 hash table 中, 則新增 node 加入 hash table

    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;

• h 為data對應要存入的hash table bucket
• 當要在 hash table 中加入 node 時，因為只有指向頭的指標， 故這邊為 insert node into head

• 以上程式碼分別還少以下兩個操作

將 node->next 指向 head->next

將node->pprev 指向 head->first

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

twoSum

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

若 target - nums[i] 存在 map 中, 則代表找到解

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

否則, 將 nums[i] 加入 map 中

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

延伸題目 2

研讀 Linux 核心原始程式碼 include/linux/hashtable.h 及對應的文件 How does the kernel implements Hashtables?，解釋 hash table 的設計和實作手法，並留意到 tools/include/linux/hash.h 的 GOLDEN_RATIO_PRIME，探討其實作考量

TODO : 持續更新

Q2

Leetcode 題目 : Remove Duplicates from Sorted List II

• 原程式碼

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

延伸問題 1

嘗試避免遞迴，寫出同樣作用的程式碼

• 使用指標的指標, 讓 remove node 不需要 prev node, 也不需要在一開始判斷是否 head==NULL,讓程式碼更簡潔
• 用外層的while 迴圈代替遞迴

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

思考如何寫出更精簡的程式碼，一樣是 indirect pointer 的應用

jserv

延伸問題 2

以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼

遞迴

迭代

Q3

Leetcode 題目 : LRU Cache