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：

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
}

• #17 : n->next 接到原先的第一個 node ，first 可以為 NULL。
• #18~19 : 如果原先的第一個 node 存在，將其 pprev 指回 n。

#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。

同 #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:

/*
 * 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。