2022q1 Homework1 (quiz1)

contributed by < TimidCactus >

題目

測驗 1

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

延伸題目1

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

malloc 一個 pointer，裡面放大小和 hash table 的 pointer ， init 成 NULL。
在 DOC 中有看到比宣告 hlist_head array 的宣告，我覺得其實可以在主程式中用那個就好了， hash table 的位置不連續就沒用了，所以一開始就知道了大小，就直接宣告。

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

以前學密碼學的時候有學過這類的東西， hash 用一個大質數可以被免運算後的碰撞，這樣中胴一個桶子裡的機會就會變少，但這個不是質數卻比質數的效果來的好。
這個論文在備讀列中

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

快速找到是那個桶子裡的再一個個比對 key ，並回傳整個 entry 。

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;
    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}

找出該 key 所對應的桶子，再放去第一個，O(1)的時間複雜度。

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

把每一個桶子裡的 node 分割出來，把原來的串也補起來。
但為什麼直接一個 while(ptr) 和 next 先存起來，把 ptr free 掉的操作，怕會存取到未定義記憶體嗎?我未見到有相關操作。