2022q1 Homework1 (quiz1)

contributed by < yuwen >

作業要求

測驗 1

這題主要是解釋了 Linux Kernal 中 hashmap 的實作，可以從講義得知定義為

struct hlist_head {
    struct hlist_node *first;
};

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

hlist_head 結構

• 只有 first ，並沒有 pprev 。因為在使用 hash table 時並不會有針對 tail 的操作，且記憶體會減少很多。

hlist_node 結構

• pprev 是 indirect pointer ，因為如果和 list_head 一樣使用單純的指標的話在 delete node 時需要考慮 list 的 head 或是 NULL 兩種狀況，因此使用 **pprev 直接存取上一個 node 所在的位址。

hash_key 結構

MAP_HASH_SIZE

這是在計算 hash table 的 size 。由 MAP_HASH_SIZE() 巨集來取得，值為輸入值乘以 2 ，並會紀錄在 map_t 的變數名稱 bits 中。

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_init()

map_init() 的功能是為了動態配置出 table 結構，並將每個 hlist_head 的 first 成員都初始化為 NULL 。

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

find_key

void *map_get 可以透過 static struct hash_key *find_key 取得 hash_key 中的 address，最後回傳 address of data。

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

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

在 find_key 中的 hash function 是利用 golden ratio marco 來定義，參考 tinyynoob同學的 g

map_add