2022q1 Homework1 (quiz1)

contributed by < RoyWFHuang >

tags: linux_class

2022q1 第 1 週測驗題

開發環境為:
OS: ubuntu 20.04
kernel ver: 5.4.0-99-generic
CPU arch: x86_64

roy@roy-ThinkPad-T460s:$ lsb_release -a
No LSB modules are available.
Distributor ID:	Ubuntu
Description:	Ubuntu 20.04.3 LTS
Release:	20.04
Codename:	focal

roy@roy-ThinkPad-T460s:~$ uname -a
Linux roy-ThinkPad-T460s 5.4.0-99-generic #112-Ubuntu SMP Thu Feb 3 13:50:55 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

github linux2022_q1

測驗 1

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;
    /*
    (a) // no operation
    (b) n->pprev = first
    (c) n->next = first
    (d) n->pprev = n
    */
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;  // BBB
                           /*
                           (a) n->pprev = &h->first
                           (b) n->next = h
                           (c) n->next = n
                           (d) n->next = h->first
                           (e) n->next = &h->first
                           */
}

延伸題目:

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

AAA: => no op 原因: 需要先判斷 first 是否有 node 才能決定是否是接在 head node or list node 之後

BBB => head 的frist 接上 node後也必須將 node pprev 接回 h->first

另外

map_t *map_init(int bits)
{
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

需要改成

map_t *map_init(int bits)
{
    map_t *map = calloc(1, sizeof(map_t));
    if (!map)
        return NULL;

用cppcheck or 放上leetcode跑之後會出現下面問題

cppcheck ->

ht.c:28:5: error: Memory leak: map.ht [memleak]
    free(map);

leetcode ->

Line 139: Char 29: runtime error: member access within misaligned address 0xbebebebebebebebe for type 'struct hlist_node', which requires 8 byte alignment [solution.c]
0xbebebebebebebebe: note: pointer points here
<memory cannot be printed>

兩個的問題都是一樣的原因造成, malloc 不會初始化記憶體
所以直接改用calloc( 或者用memset 初始化也可), 不過 malloc 和calloc 是完全不一樣的動作

TODO:
malloc:
先從 glibc 的 source code 來看
calloc:

測驗 2

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

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

    return head;
}

延伸問題:

1. 嘗試避免遞迴，寫出同樣作用的程式碼
2. 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼

測驗 3

void lRUCacheFree(LRUCache *obj)
{
    LRUNode *lru, *n;
    //  MMM1 (lru, n, &obj->dhead, dlink)
    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;
    // MMM2 (lru, &obj->hheads[hash], hlink) {
    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;
    // MMM3 (lru, &obj->hheads[hash], hlink) {
    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 = MMM4(&obj->dhead, LRUNode, dlink);
        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;
}

延伸問題:

1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 在 Linux 核心找出 LRU 相關程式碼並探討

測驗 4

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++;
            list_del(&node->link);

            int left = nums[i], right = nums[i];
            // while ((node = find(LLL, n_size, heads))) {
            while ((node = find(--left, n_size, heads))) {
                len++;
                list_del(&node->link);
            }
            
            // while ((node = find(RRR, n_size, heads))) {
            while ((node = find(++right, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

延伸問題:

1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼