# 2022q1 Homework1 (quiz1)
contributed by < `Kevin-Shih` >
## 測驗一 LeetCode 1 Two Sum
### 所用到的結構
- map: hash table

typedef struct { 
    int bits; // 用於紀錄 hash table 大小為 2^bits
    struct hlist_head *ht;
} map_t;

- hlist_node、hlist_head

struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };

- hash_key:

struct hash_key {
    int key; // key = target - nums[i]
    void *data; // nums[i] 的 index `i`
    struct hlist_node node; // 用於串接 hlist
};

先分開來看各個 function 的用途：
### 建立大小為 2^bits 的 hash table

// 計算 hash table 大小為 2^bits
#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;
    // malloc 2^map->bits 個 hlist_head 的大小給 hash table
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    // 成功建立 hash table 時初始化所有 first
    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;
}

### 尋找 key 相同的節點 kn
若有找到則回傳該節點，否則回傳 NULL。
- map_t *map: 對應的 hash table
- int key: 要尋找的 key

static struct hash_key *find_key(map_t *map, int key) {
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    // 走訪 ht[hash(key, map->bits)] 中所有 chain 起來的 list node
    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;
}

假設 hash 後的地址為 `2`：

digraph  "hash list"  {
        node [shape=record];
        rankdir=LR;
        a [label=" map-\>ht | {[0] | [0].first } | {[1] | [1].first } | {[2] | <2>[2].first } | ...}"];
        b [label="{ <pprev> pprev| <key> 1 | <next> next}"];
        c [label="{ <pprev> pprev| <key> 5 | <next> next}"];
        d [label="{ <pprev> pprev| <key> -2 | <next> next}"];
        null;
        p;
        
        a:2:c -> b:key:n         [arrowhead=vee];
        b:pprev:w -> a:2:e       [arrowhead=vee, tailclip=false, color="#808080"];
        b:next:n -> c:key:n      [arrowhead=vee, tailclip=false];
        c:pprev:s -> b:next:s    [arrowhead=vee, tailclip=false, color="#808080"];
        c:next:n -> d:key:n      [arrowhead=vee, tailclip=false];
        d:pprev:s -> c:next:s    [arrowhead=vee, tailclip=false, color="#808080"];
        d:next:e -> null:w       [arrowhead=vee, tailclip=false];
        p -> b:key:s             [arrowhead=vee];
        
}

`find_key()` 會以 pointer `p` 如上圖依序走訪 `1`、`5`、`-2`，並比較 `key` 值是否與輸入的 `@key` 相等，若相等則回傳該 `hash_key` 的位址。

### 取得 key 相同的節點的 data

void *map_get(map_t *map, int key)
{
    // 呼叫前述的 find_key 取得 key 與 @key 相同的節點 address
    struct hash_key *kn = find_key(map, key);
    // 當 kn 有找到 (kn != NULL) 時取得對應 data 的 address
    return kn ? kn->data : NULL;
}

### 將新的 node 加入 hash table
會將新的 node `kn` 插到原先的 fisrt 前面。
- AAA = `n->next = first;`
- BBB = `n->prev = &h->first;`

void map_add(map_t *map, int key, void *data)
{
    // 如果 hash table 中該 @key 已有 key 相等的節點
    // 表示找到答案了，故 return
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    // 為新的節點 malloc 並填入 key 及 data (答案的 index)
    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    // 將該節點接上 hash table 對應的 bucket h
    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;

    n->next = first; // AAA's answer
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->prev = &h->first; // BBB's answer
}

digraph  "hash list"  {
        node [shape=record];
        rankdir=LR;
        a [label=" map-\>ht | {[0] | [0].first } | {[1] | [1].first } | {[2] | <2>[2].first } | ...}"];
        b [label="<key> 1 | { <pprev> pprev |  <next> next }"];
        c [label="<key> 5 | { <pprev> pprev |  <next> next }"];
        d [label="<key> -2 | { <pprev> pprev |  <next> next }"];
        null;
        n; 
        first;
        {rank=min;first}
        n:e -> b:key:n             [arrowhead=vee];
        first:e -> c:key:n             [arrowhead=vee];
        a:2:e -> b:key:w         [arrowhead=vee, weight = 100];
        b:pprev:w -> a:2:e       [arrowhead=vee, tailclip=false, color="#808080"];
        b:next:e -> c:key      [arrowhead=vee, tailclip=false];
        c:pprev:s -> b:next:s    [arrowhead=vee, tailclip=false, color="#808080", weight = 100];
        c:next:e -> d:key      [arrowhead=vee, tailclip=false];
        d:pprev:s -> c:next:s    [arrowhead=vee, tailclip=false, color="#808080", weight = 100];
        d:next:e -> null:w       [arrowhead=vee, tailclip=false];
}

- #17 : `n->next` 接到原先的第一個 node ，`first` 可以為 `NULL`。
- #18~19 : 如果原先的第一個 node 存在，將其 `pprev` 指回 `n`。
:::info
#19 的 first->pprev = &n->next;
是將 `first->pprev` 指向存放 `n->next` 這個 pointer 的位址，而非 `n->next` 這個 pointer 中存放的位址。 因此該行作用相當於將 `first->pprev` 指回 `n`。 (用 `containerof()` 即可取得 `n` 的位址)
:::
- #20 : hash table 中將對應的 `head->first` 指向新的 "first" 也就是 `n`。
- #21 : 將 `n->pprev` 指向 `head`。
:::info
同 #19 的 first->pprev = &n->next;

#21 將 `n->pprev` 指向存放 `&h->first` 這個 pointer 的位址。 (用 `containerof()` 即可取得 `head` 的位址)
:::

看懂 #18~20 的是將新的節點 n 放在 hlist 中的第一個位置就很好推論出 #17 的 AAA 是將 `n->next` 指向原先的 `first`、#21 的 BBB 則是將 `n->pprev` 指向 `&head->first`。
### 清除 hash table

void map_deinit(map_t *map)
{
    // 如果 hash table 不存在就 return
    if (!map)
        return;

    // 對 hash table 中的每個 bucket
    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
        struct hlist_head *head = &map->ht[i];
        // 依序走訪 bucket 中的 node
        for (struct hlist_node *p = head->first; p;) {
            // kn 指向 p 對應的 entry
            struct hash_key *kn = container_of(p, struct hash_key, node);
            struct hlist_node *n = p;
            // p 移到下個 node
            p = p->next;

            // TODO: 這是什麼？
            if (!n->pprev) /* unhashed */
                goto bail;

            // 將 n 移出 hlist
            struct hlist_node *next = n->next, **pprev = n->pprev;
            *pprev = next; // 前一個 node 的 next 接到 n 的 next
            if (next) 
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;
        // 釋放 kn(n) 所佔用的資源
        bail:
            free(kn->data);
            free(kn);
        }
    }
    // 釋放 hash table 本身
    free(map);
}

### 執行 Two Sum
- int *nums: 給定的 int 陣列
- int numsSize: int 陣列的大小
- int target: 目標的總和
- int *returnSize: 成功找到時為 2，失敗時為 0

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    // 建立 1024 個 bucket 的 hash table
    map_t *map = map_init(10);
    *returnSize = 0;
    int *ret = malloc(sizeof(int) * 2);
    // 回傳值的 array malloc 失敗，清除 hash table 後 return
    if (!ret)
        goto bail;
    
    /*
     * 若 target - nums[i] 的 key 不存在於 hash table 中，
     * 則將 nums[i] 作為 key, i 作為 data(index) 加入 hash table，
     * 當下次有 target - nums[i] 的數查找 hash table 時即可找到答案。
     * 
     * 若 target - nums[i] 的 key 存在於 hash table 中，
     * 則對 map_get 回傳的 int pointer 取值存入答案 ret[1]，
     * 另一個答案則是目前的 index i 存入 ret[0] 並將 returnSize
     * 設為 2 表示成功找到，接著釋放 hash table 並回傳 ret 即可。
     */
    for (int i = 0; i < numsSize; i++) {
        int *p = map_get(map, target - nums[i]);
        if (p) { /* found */
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

### GOLDEN_RATIO_PRIME
節錄自[linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h):

/*
 * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and
 * fs/inode.c.  It's not actually prime any more (the previous primes
 * were actively bad for hashing), but the name remains.
 */
#if BITS_PER_LONG == 32
#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32
#define hash_long(val, bits) hash_32(val, bits)
#elif BITS_PER_LONG == 64
#define hash_long(val, bits) hash_64(val, bits)
#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64
#else
#error Wordsize not 32 or 64
#endif

#define GOLDEN_RATIO_32 0x61C88647
#define GOLDEN_RATIO_64 0x61C8864680B583EBull

可以發現 GOLDEN_RATIO_PRIME 在 32 bit 系統(unsigned long 為 32 bit)上為 `0x61C88647` 而在 64 bit 系統上為 `0x61C8864680B583EBull`，兩者皆非時會 error。