Try   HackMD

2022q1 Homework1 (quiz1)

contributed by < vacantron >

測驗一

運作原理

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

O(n2);若改用 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 是不是串列中的第一個元素







%0



table

hash_table

 

 

hlist_entry[n]

 



first

hlist_entry[n]

first



table:e->first:e




node0

node0

pprev

next



first:s->node0:w





node1

node1

pprev

next



first:h->node1:w





node0:p->first:s





node0:nx->node1:w





node1:p->first:h





node1:s->node0:e





null

null



node1:nx->null





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 指標指向的節點







%0



head

hlist_entry[n]

*first



node0

list_node_0

**pprev

*next



head:first->node0:list_node






null

null



node0:pprev->head:first





node1

list_node_1

**pprev

*next



node0:next->node1:list_node






node1:pprev->node0:next





node2

list_node_2

**pprev

*next



node1:next->node2:list_node






node2:next->null





node2:pprev->node1: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); }