---
tags: linux2022
---

# 2022q1 Homework1 (quiz1)
contributed by < [`yuwen`](https://github.com/yyyyuwen) >

> [作業要求](https://hackmd.io/@sysprog/B166rc3Jq)

## 測驗 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** 的操作，且記憶體會減少很多。

digraph {
    rankdir = LR;
    node [shape=record];
    subgraph cluster {
        first;
        label = "hlist_head";
    }
}

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

digraph {
    rankdir = LR;
    node [shape=record];
    subgraph cluster {
        node0[label="{<p>pprev|<n>next}"];
        label = "hlist_node";
    }
}

#### `hash_key` 結構

digraph {
    rankdir = LR;
    node [shape=record];
    subgraph cluster {
        node0[label="key|data|{<p>pprev|<n>next}"];
        label = "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;
}

digraph {
    rankdir = LR;
    node [shape=record];
    subgraph cluster {
        node0[label="bits (size of the hashtable)|<ht>ht"];
        label = "map";
    }
    subgraph {
        node[shape=plaintext, label=NULL]
        NULL1, NULL2, NULL3, NULL4, NULL5
    }
    struct1 [label="<1>hlist_head.first|<2>...|<3>...|<4>...|<5>hlist_head.first" height=1.5]
    
    node0:ht->struct1:1
    struct1:1->NULL1
    struct1:2->NULL2
    struct1:3->NULL3
    struct1:4->NULL4
    struct1:5->NULL5
    
}

### 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](https://hackmd.io/bpf-14GARBu59uLiYwzChQ?both)同學的 g

### map_add