# 2022q1 Homework1 (quiz1)
contributed by < `paul90317` >

## hlist_node 的 pprev 為何用指標的指標
再回答指定題目之前，我想先解答這個問題。
首先先考慮如果 pprev 只是指標時，會有 case 需要分開考慮。
當我們想要刪除 hlist 的第一個 node (node A) 時，我妹需要查看直接到 hlist head 去查找，因為 pprev 的 type 是 struct list_node* ，所以無法指派指標 struct list_head* ，如果只是強行使用 list_head 的 member first，雖然 type 是對的，但是無法直接修改 list_head 的值。

但是當我們把 pprev 變成指標的指標，我們就能藉由把 pprev 指到 head 的 first 的指標，從而改變他的值。

## 測驗 `1`
首先我先透過逐行閱讀的方式加上註解，了解程式碼想幹麻。

#include <stddef.h>
#include <stdlib.h>

struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;

#define MAP_HASH_SIZE(bits) (1 << bits)

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));//貌似想要用 >>bits 代替 mod，避免 mod 煩雜的運算
    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;
}

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

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

#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);//取 prefix，且在之前會成一個 GOLDEN_RATIO_32，避免資料卡太多到同一 node
}

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

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : 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;//kn 是 container，要插入的是 n | first 是第一個 node，不是 head 
    n->next=first;// AAA 應該試想把 node n 插到最前面，不要用 kn，因為是 container
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev=&h->first;// BBB 應該要把 n 的 prev 接到前一個，也就是 head 的 first 的指標，方便刪除 n。
}

* AAA=``(c)`` `n->next=first`
應該試想把 node n 插到最前面，不要用 kn，因為是 container
* BBB=``(a)`` `n->pprev=&h->first`
應該要把 n 的 prev 接到前一個，也就是 head 的 first 的指標，方便刪除 n。

**GOLDEN_RATIO_PRIME**

#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);//取 prefix，且在之前會成一個 GOLDEN_RATIO_32，避免資料卡太多到同一 node
}

首先看到 hash ，mod 對於電腦應該是需要比較多 cycle 才能完成的指令，甚至完成時間根據數字不同每次可能不同，所以 linux 才會採用乘上 `GOLDEN_RATIO_PRIME` 再舉前 `bits` 個 bit 讓運算更快的同時，也能達到 hash key 與要 key 無關的效果，如果沒乘 `GOLDEN_RATIO_PRIME` ，如果 key 都很像，可能會塞到同一 bucket。