--- tags: linux2022 --- # 2022q1 Homework1 (quiz1) contributed by < `bebo1010` > ## AAA ``` (a) /* no operation */ (b) n->pprev = first (c) n->next = first (d) n->pprev = n ``` 首先我注意到一件事情，(b)和(d)是不可選的選項 pprev 是指標的指標，而 first 和 n 的型態是指標 因此填入(b)和(d)會發生編譯器報錯的問題 接下來我檢查了程式碼，了解缺失的部分就是把新增的 n 放入 list 的步驟 因此`AAA`和`BBB`必定填入`n->next`以及`n->pprev`相關的 code 由於已經有兩個選項遭到刪去，剩下的`n->next = first`就是唯一解 ## BBB ``` (a) n->pprev = &h->first (b) n->next = h (c) n->next = n (d) n->next = h->first (e) n->next = &h->first ``` 接續AAA的作答思路，AAA已經填入`n->next = first`後 BBB應該要填入`n->pprev`有相關的 code 因此直接選(a)回答 ## trace code 時注意到的東西 當下在讀這份程式碼時，我注意到了 hash 的方式，這種 hash 的方式我從來沒有看過的 ```c #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); } ``` `quiz1`這份 code 的 hash 形式是把輸入的值乘上`GOLDEN_RATIO_32`後再向右位移 $32-x$ 個 bits 之後我也去大致翻了一下 linux 的 hash 作法 [link](https://elixir.bootlin.com/linux/v4.7/source/fs/btrfs/btrfs_inode.h#L222) ``` c static inline unsigned long btrfs_inode_hash(u64 objectid, const struct btrfs_root *root) { u64 h = objectid ^ (root->objectid * GOLDEN_RATIO_PRIME); #if BITS_PER_LONG == 32 h = (h >> 32) ^ (h & 0xffffffff); #endif return (unsigned long)h; } ``` 這個 hash 做法又跟`quiz1`內提到的不太相同，但是我也說不上這是什麼寫法 我自己在上學期作業系統的作業內寫過一種 hash ```c struct dummy * db_hash(char *key) { //my hash function, just mod a prime number int hash_value = 0; if(key[1] == '\0' && key[0] == '\0') hash_value = 0; if(key[1] != '\0' && key[0] == '\0') hash_value = (int) key[1]; if(key[1] == '\0' && key[0] != '\0') hash_value = (int) key[0]; if(key[1] != '\0' && key[0] != '\0') hash_value = (int) (key[0] * key[1]); hash_value = hash_value % DB_LENGTH; //DB_LENGTH = 251 return &db[hash_value]; } ``` 這做法是把輸入(預設輸入都是字串)的前兩個字元做`ASCII code`的對應數值相乘後再對預先設定好的 hash table 長度(預先取一個質數)做模除運算 或許我的做法有點冗餘，但我認為整體來說和 linux 的做法可以互相比較一下 可是我不太確定這兩種做法間有什麼實質上的差別(扣除我的 code 寫得太過冗長以外) 或許教授和助教在改這份時可以給我點意見