# 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 是不是串列中的第一個元素

digraph {
    node [shape=record];
    rankdir=LR
    table [label="hash_table | | | <entry>hlist_entry[n] | "];
    first [label="<e>hlist_entry[n] | <h>first"];
    node0 [label="<d>node0 | {<p>pprev | <nx>next}"];
    node1 [label="<d>node1 | {<p>pprev | <nx>next}"];
    
    table:entry:e -> first:e [arrowhead=none];
    
    first:h -> node1:w;
    node1:p -> first:h [weight=2];
    null [label="null" shape=oval];
    node1:nx -> null;
    first:h:s -> node0:w [style=dashed];
    node0:p -> first:h:s [style=dashed];
    node1:p:s -> node0:nx:e [style=dashed];
    node0:nx -> node1:w [style=dashed];
}

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

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

digraph {
    rankdir=LR
    node [shape=record];
    head [label="hlist_entry[n] | <first> *first"]
    null [label="null" shape=oval]
    node0 [label="<list_node> list_node_0 | { <pprev> **pprev | <next> *next }"];
    node1 [label="<list_node> list_node_1 | { <pprev> **pprev | <next> *next }"];
    node2 [label="<list_node> list_node_2 | { <pprev> **pprev | <next> *next }"];
    
    head:first -> node0:list_node;
    node0:next -> node1:list_node;
    node1:next -> node2:list_node;
    node2:next -> null;
    
    node0:pprev -> head:first;
    node1:pprev -> node0:next;
    node2:pprev -> node1:next;
    
    head->node0[style=invis]
    node0->node1[style=invis]
    node1->node2[style=invis]
}

:::
<br>

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