2022q1 Homework1 (quiz1)

contributed by < vacantron >

測驗一

運作原理

如果逐次檢查相加的數值，時間複雜度為

$O(n^2)$；若改用 hash table 記錄差值只與對應的索引，即可將時間複雜度降為

$O(n)$

---

實作

container_of 巨集透過利用 offset_of 巨集從結構體成員的指標計算出結構體的指標

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

從以下定義得知 pprev 為一個指向前一個節點的 next ( 或是 first ) 成員的 indirect pointer

struct hlist_node {
    struct hlist_node *next, **pprev;
};

使用 indirect point 的好處是當我們要從串列中刪除節點 0 時，只要將節點 0 的 pprev 成員指向的指標重新指派給節點 1 的 pprev 成員以及更新 pprev 中指標指向的節點 ( 即前一個元素的 next ( 或是 first ) 指向的節點 ) 即可，不用管節點 0 是不是串列中的第一個元素

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

故 AAA 應填入 n->next = first 讓新增的節點的 next 成員指向原串列的第一個元素
而 BBB 應填入 n->pprev = &h->first 連接新增的節點與串列的 head

outdated

在第 17 行中發現可以藉由更新 indirect pointer 指向的指標的內容來更新上一個節點的 next 指標指向的節點

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