# 2024q1 Homework2 (quiz1+2)
contributed by <[`hungyuhang`](https://github.com/hungyuhang)>
## 第 1 週測驗題
### 測驗 `1`
觀察程式碼，可以發現 `main` 程式碼做了以下事情：
1. 產生 100000 個數字並且執行 `shuffle` 將其順序打亂
2. 將這 100000 個數字使用 `list_construct` 函式轉換成鏈節串列
3. 使用 `quick_sort()` 函式對鏈節串列進行排序
4. 檢查排序結果並釋放記憶體
#### quick_sort() 函式解析
接下來進一步去觀察 `quick_sort()` 函式。首先透過呼叫 `list_length()` 來取得串列長度。從函式的功能，推測 BBBB = (*left)->next 。
在進入迴圈之前，程式碼先將整個鏈節串列的頭跟尾推入到 `begin` 跟 `end` 這兩個堆疊內：
```c
begin[0] = *list;
end[0] = list_tail(list);
```
從這裡不難看出 `list_tail()` 函式回傳的東西就是 list 的最後一個節點，所以可以推測 AAAA 的值是 `(*left)->next` 。
在主迴圈的一開始，可以看到程式碼會從 `begin` 跟 `end` 這兩個堆疊內取出這次要處理的子鏈節串列的頭尾位置：
```c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
```
並且在內部的迴圈依照數字大小來決定要把每個節點放到 `right` 還是 `left` 上面：
```c
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
為了達成上述的功能，所以在 CCCC 的位置填上 `p->next` 。
完成這個步驟後，鏈節串列會被分成三個串列：
- `left` ：裡面所有節點都比 pivot 還要小
- `pivot` ：裡面只含有 pivot 一個節點
- `right` ：裡面所有節點都比 pivot 還要大
到這裡可以推測：
- DDDD 應該要填入 `list_tail(left)`
- EEEE 應該要填入 `list_tail(right)`
並且程式碼會將這三個串列依序加到 `begin` 跟 `end` 兩個堆疊當中。
可以觀察到程式碼會把長度僅為 1 的 `pivot` 串列也加到堆疊裡面，那當程式碼從堆疊取出的串列長度為 1 的時候怎麼辦呢？以下是程式碼的處理方式：
```c
} else {
if (L)
list_add(&result, L);
i--;
}
```
這段程式處理得很簡潔，就是把這個串列裡的唯一節點加到 `result` 這個串列上面。
因為最後所有的子串列都會被切分成長度為 1 的串列，所以每個節點都會依序被加到 `result` 串列上。
#### 圖解範例
先假設有一個串列，並且排序方式如下：
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
rankdir = LR
n1[label=1]
n2[label=2]
n3[label=3]
n4[label=4]
n5[label=5]
}
n3->n4->n5->n1->n2
}
```
1. 選定 pivot 為串列中第一個元素（也就是 3 ），並且將比 pivot 小的節點加到 left ， 比 pivot 大的節點加到 right ：
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
rankdir = LR
n1[label=1]
n2[label=2]
n3[label=3]
n4[label=4]
n5[label=5]
}
{
left[shape=plaintext,fontcolor=blue]
pivot[shape=plaintext,fontcolor=red]
right[shape=plaintext,fontcolor=blue]
}
left->n1->n2
pivot->n3
right->n4->n5
}
```
2. 隨後將這三個串列加到 stack 裡面，在這個時間點， stack[2] 是堆疊的頂端：
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
rankdir = LR
n1[label=1]
n2[label=2]
n3[label=3]
n4[label=4]
n5[label=5]
}
{
left[label="stack[0]",shape=plaintext,fontcolor=black]
pivot[label="stack[1]",shape=plaintext,fontcolor=black]
right[label="stack[2]",shape=plaintext,fontcolor=black]
}
left->n1->n2
pivot->n3
right->n4->n5
}
```
3. 接下來程式碼會從 stack 的最頂端取出子串列然後重複進行步驟 2 跟 3 的操作
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
rankdir = LR
n1[label=1]
n2[label=2]
n3[label=3]
n4[label=4]
n5[label=5]
}
{
left[label="stack[0]",shape=plaintext,fontcolor=black]
pivot[label="stack[1]",shape=plaintext,fontcolor=black]
right[label="stack[2]",shape=plaintext,fontcolor=black]
righa[label="stack[3]",shape=plaintext,fontcolor=black]
}
left->n1->n2
pivot->n3
right->n4
righa->n5
}
```
4. 當從 stack 頂端取出的串列長度是 1 的話，就將該串列插入到 result 上面。所以節點 3 ， 4 跟 5 會依序被插入到 result 上面：
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
rankdir = LR
n1[label=1]
n2[label=2]
n3[label=3]
n4[label=4]
n5[label=5]
}
{
left[label="stack[0]",shape=plaintext,fontcolor=black]
result[label="result",shape=plaintext,fontcolor=black]
}
left->n1->n2
result->n5->n4->n3
}
```
5. 最後當 stack 被清空之後， result 所指向的串列就會是一個已經排序好的串列：
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
rankdir = LR
n1[label=1]
n2[label=2]
n3[label=3]
n4[label=4]
n5[label=5]
}
{
left[label="stack[0]",shape=plaintext,fontcolor=black]
result[label="result",shape=plaintext,fontcolor=black]
}
result->n5->n4->n3->n2->n1
}
```
### 測驗 `2`
將 Timsort 實作整合進 lab0-c ：[commit 1ca5d00](https://github.com/hungyuhang/lab0-c/commit/1ca5d001ff777fb465a90c36adfce00529833752)
## 第 2 週測驗題
### 測驗 `1`
該函式使用對同一棵二元樹的前序及中序走訪結果，重建此二元樹。
#### 程式碼解析
假設我們有以下輸入：
- `preorder` = [3, 9, 20, 15, 7]
- `inorder` = [9, 3, 15, 20, 7]
```c
for (int i = 0; i < inorderSize; i++)
INIT_HLIST_HEAD(&in_heads[i]);
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
```
在一開始，上方程式碼會建立一個 hash table `in_heads` ，並且將 `inorder` 裡面的元素跟其相對應的位置做成節點並放到 hash table 上面：
```graphviz
digraph G {
rankdir = TD;
splines = false;
node[shape = "record"]
{
rank="same"
hash[label = "<h0>0 | <h1>1 | <h2>2 | <h3>3 | <h4>4"];
tex[label="hash table",shape=plaintext,fontcolor=black];
}
rank="same"
n3[label="{val=3 | idx=1}",fontcolor=black];
n7[label="{val=7 | idx=4}",fontcolor=black];
n9[label="{val=9 | idx=0}",fontcolor=black];
n15[label="{val=15 | idx=2}",fontcolor=black];
n20[label="{val=20 | idx=3}",fontcolor=black];
hash:h0 -> n20 -> n15;
hash:h2 -> n7;
hash:h3 -> n3;
hash:h4 -> n9;
}
```
底下是 hash function ：
```c
int hash = (val < 0 ? -val : val) % size;
```
舉 `inorder[2]` 的 15 為例，依照 hash function ， 15 會被放在第 15 % 5 = 0 個 hash table entry 裡面。
接下來，程式碼會開始遞迴的呼叫 `dfs()` ：
```c
static struct TreeNode *dfs(int *preorder,
int pre_low,
int pre_high,
int *inorder,
int in_low,
int in_high,
struct hlist_head *in_heads,
int size)
{
if (in_low > in_high || pre_low > pre_high)
return NULL;
struct TreeNode *tn = malloc(sizeof(*tn));
tn->val = preorder[pre_low];
int idx = find(preorder[pre_low], size, in_heads);
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
in_low, idx - 1, in_heads, size);
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
idx + 1, in_high, in_heads, size);
return tn;
}
```
輸入的資料結構會長的像下圖：
```graphviz
digraph G {
rankdir = TD;
splines = false;
node[shape = "record"]
pl[label="pre_low",shape=plaintext,fontcolor=black];
ph[label="pre_high",shape=plaintext,fontcolor=black];
il[label="in_low",shape=plaintext,fontcolor=black];
ih[label="in_high",shape=plaintext,fontcolor=black];
{
// rank="same"
preorder[label = "<n3>3 | <n9>9 | <n20>20 | <n15>15 | <n7>7"];
pre[label="preorder",shape=plaintext,fontcolor=black];
}
inorder[label = "<n9>9 | <n3>3 | <n15>15 | <n20>20 | <n7>7"];
in[label="inorder",shape=plaintext,fontcolor=black];
pl -> preorder:n3;
ph -> preorder:n7;
il -> inorder:n9;
ih -> inorder:n7;
preorder -> pre [arrowhead="none"];
inorder -> in [arrowhead="none"];
}
```
其中，`pre_low` ， `pre_high` ， `in_low` ， `in_high` 的用途是把要處理的部份給框起來。在遞迴最頂端的函式呼叫，框起來的部份就是全部的範圍。
接下來，利用 preorder 的特性，我們可以直接得知傳入 `dfs()` 的這棵子樹的 root 就是 `3` 。
拿到 `3` 這個值之後，我們利用 `find()` 函式找出 `3` 這個節點在 `inorder` 的哪個位置。下面是 `find()` 函式的答案：
```diff
static int find(int num, int size, const struct hlist_head *heads)
{
struct hlist_node *p;
int hash = (num < 0 ? -num : num) % size;
- hlist_for_each (p, BBBB) {
- struct order_node *on = CCCC(p, struct order_node, node);
+ hlist_for_each (p, heads + hash) {
+ struct order_node *on = list_entry(p,
if (num == on->val)
return on->idx;
}
return -1;
}
```
這個函式做的事情就是從雜湊表中用 $O(1)$ 的時間複雜度找出節點 {val=3, idx=1} 。這麼一來，我們就可以知道 `3` 在 `inorder` 的位置是 1 （以 `idx` 表示）：
```graphviz
digraph G {
rankdir = TD;
splines = false;
node[shape = "record"]
pl[label="pre_low",shape=plaintext,fontcolor=black];
ph[label="pre_high",shape=plaintext,fontcolor=black];
il[label="in_low",shape=plaintext,fontcolor=black];
ih[label="in_high",shape=plaintext,fontcolor=black];
idx[label="idx",shape=plaintext,fontcolor=blue];
{
// rank="same"
preorder[label = "<n3>3 | <n9>9 | <n20>20 | <n15>15 | <n7>7"];
pre[label="preorder",shape=plaintext,fontcolor=black];
}
inorder[label = "<n9>9 | <n3>3 | <n15>15 | <n20>20 | <n7>7"];
in[label="inorder",shape=plaintext,fontcolor=black];
pl -> preorder:n3;
ph -> preorder:n7;
il -> inorder:n9;
ih -> inorder:n7;
idx -> inorder:n3;
preorder -> pre [arrowhead="none"];
inorder -> in [arrowhead="none"];
}
```
有了以上資訊，就可以算出：
- 左子樹的大小是 1
- 右子樹的大小是 3
如此一來，就可將 `preorder` 跟 `inorder` 分成下面三個部份（其中 root 用粗體標示）：
- `preorder` : [**3**] [9] [20, 15, 7]
- `inorder` : [9] [**3**] [15, 20, 7]
並且再用遞迴的方式來產生左右子樹。而當取得左右子樹之後，就可以接到 root 上面，完成 binary tree 的製作。
### 測驗 `2`
該測驗的程式碼實作了 LRU Cache 的操作，以下是測驗程式碼所實作的函式：
- `lRUCacheCreate()`
- `lRUCacheFree()`
- `lRUCacheGet()`
- `lRUCachePut()`
#### 程式碼解析
##### `lRUCacheCreate(int capacity)`
該程式碼的功能就是建立一個空的 LRU cache 物件。
##### `lRUCacheFree(LRUCache *obj)`
該程式碼會把傳入的 LRU cache 物件給刪除，並且釋放所使用的記憶體。
其中，程式碼會先把 LRU cache 物件裡面 `dhead` 所指向的鏈節串列給刪除，然後再將 LRU cache 物件本身給刪除。
依照上述推導，可以開始推導空格中應該填入的程式碼：
```c
void lRUCacheFree(LRUCache *obj)
{
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, FFFF);
list_del(GGGG);
free(cache);
}
free(obj);
}
```
由於 `pos` 的型別是 `list_head *` ，對照 `LRUNode` 擁有 `list_head` 型別的成員是 `link` ：
```c
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
所以 `FFFF` 需要填入 `link` ：
```diff
- LRUNode *cache = list_entry(pos, LRUNode, FFFF);
+ LRUNode *cache = list_entry(pos, LRUNode, link);
```
而 `list_del()` 要傳入的參數型態是 `list_head *` ，所以我們要傳入的是 `pos` ：
```diff
- list_del(GGGG);
+ list_del(pos);
```
##### `lRUCacheGet(LRUCache *obj, int key)`
> 這裡推測 key 代表的是記憶體位置
這個函式會做兩件事情：
- 從雜湊表尋找要取得的節點
- 找到後把該節點放到 `dhead` 所指向的串列的最前面
以下是程式碼：
```c
int lRUCacheGet(LRUCache *obj, int key)
{
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *cache = list_entry(pos, LRUNode, HHHH);
if (cache->key == key) {
list_move(&cache->link/*IIII*/, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
由於 `pos` 的型別是 `hlist_node` ，對照 `LRUNode` 擁有 `hlist_node` 型別的成員是 `node` ，所以 `HHHH` 需要填入 `node` ：
```diff
- LRUNode *cache = list_entry(pos, LRUNode, HHHH);
+ LRUNode *cache = list_entry(pos, LRUNode, node);
```
而第二個空格要做的事情是把找到的資料節點安插到 `dlist` 的最前面，所以 `IIII` 要填入的是 `&cache->link` ：
```diff
- list_move(IIII, &obj->dhead);
+ list_move(&cache->link, &obj->dhead);
```
##### `lRUCachePut(LRUCache *obj, int key, int value)`
> 這裡推測 key 代表的是記憶體位置，而 value 則是代表該記憶體位置內的資料
這個函是在前半部所作的事情跟 `lRUCacheGet()` 是非常相似的：
- 從雜湊表尋找要放入的節點是否已經存在
- 如果已經存在，則把已存在的節點放到 `dhead` 所指向的串列的最前面
所以以下的填空可以比照 `lRUCacheGet()` 的填空方式：
```diff
hlist_for_each (pos, &obj->hhead[hash]) {
- LRUNode *c = list_entry(pos, LRUNode, JJJJ);
+ LRUNode *c = list_entry(pos, LRUNode, node);
if (c->key == key) {
- list_move(KKKK, &obj->dhead);
+ list_move(&c->link, &obj->dhead);
cache = c;
}
}
```
而這裡是下半部的程式邏輯：
- 如果該節點不存在，而且 LRU Cache 已經滿了：
- 將 cache 裡面 `dhead` 串列的最後一個節點替換成要放入的節點，並且將其安插到 `dhead` 串列的最前面
- 如果該節點不存在，但 LRU Cache 還有空間：
- 在 cache 裡面新增一個節點，並且將其安插到 `dhead` 串列的最前面
- 如果該節點已經存在
- 將該節點的數值用引數 `value` 做更新
- 因為程式碼的前半段已經將這個節點安插到 `dhead` 串列的最前面，所以這邊就不重複做了。
而在 `lRUCachePut()` 裡面會用到 `hlist_del()` 這個函式：
```c
void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
EEEE = pprev;
}
```
以下簡單演示刪除的過程：
假設要將 node 1 從鏈節串列刪除：
```graphviz
digraph G {
rankdir = LR;
//splines = false;
node[shape = "record"]
h[label = "<f>first"];
n0[label = "{<p>pprev | <n>next} | <id>node 0"];
n1[label = "{<p>pprev | <n>next} | <id>node 1"];
n2[label = "{<p>pprev | <n>next} | <id>node 2"];
null[label="NULL",shape=plaintext];
h -> n0;
n0:n -> n1;
n1:n -> n2;
n2:n -> null;
n2:p -> n1:n
n1:p -> n0:n
n0:p -> h
}
```
首先將 `next` 跟 `pprev` 指向 node 1 周圍的節點（ `pprev` 指向的是 node 0 的 `next` 成員）：
```graphviz
digraph G {
rankdir = LR;
//splines = false;
node[shape = "record"]
h[label = "<f>first"];
n0[label = "{<p>pprev | <n>next} | <id>node 0"];
n1[label = "{<p>pprev | <n>next} | <id>node 1"];
n2[label = "{<p>pprev | <n>next} | <id>node 2"];
null[label="NULL",shape=plaintext];
next[label="next",shape=plaintext,fontcolor=blue];
pprev[label="pprev",shape=plaintext,fontcolor=red];
h -> n0;
n0:n -> n1;
n1:n -> n2;
n2:n -> null;
n2:p -> n1:n
n1:p -> n0:n
n0:p -> h
next -> n2;
pprev -> n0:n
}
```
接下來透過 `pprev` 修改 node 0 的 `next` 成員，將其指向 node 2：
```graphviz
digraph G {
rankdir = LR;
//splines = false;
node[shape = "record"]
h[label = "<f>first"];
n0[label = "{<p>pprev | <n>next} | <id>node 0"];
{
rank="same"
n1[label = "{<p>pprev | <n>next} | <id>node 1"];
hidden[shape=point height=0];
}
n2[label = "{<p>pprev | <n>next} | <id>node 2"];
null[label="NULL",shape=plaintext];
next[label="next",shape=plaintext,fontcolor=blue];
pprev[label="pprev",shape=plaintext,fontcolor=red];
h -> n0;
n0:n -> hidden [arrowhead=none];
hidden -> n2;
n1:n -> n2;
n2:n -> null;
n2:p -> n1:n
n1:p -> n0:n
n0:p -> h
next -> n2;
pprev -> n0:n
}
```
最後將 `next` 所指向的節點的 `pprev` 成員指向 node 0 ，即完成刪除的動作：
```graphviz
digraph G {
rankdir = LR;
//splines = false;
node[shape = "record"]
h[label = "<f>first"];
n0[label = "{<p>pprev | <n>next} | <id>node 0"];
{
rank="same"
n1[label = "{<p>pprev | <n>next} | <id>node 1"];
hidden[shape=point height=0];
hidden2[shape=point height=0];
}
n2[label = "{<p>pprev | <n>next} | <id>node 2"];
null[label="NULL",shape=plaintext];
next[label="next",shape=plaintext,fontcolor=blue];
pprev[label="pprev",shape=plaintext,fontcolor=red];
h -> n0;
n0:n -> hidden [arrowhead=none];
hidden -> n2;
n1:n -> n2;
n2:n -> null;
n2:p -> hidden2 [arrowhead=none];
hidden2 -> n0:n;
n1:p -> n0:n;
n0:p -> h;
next -> n2;
pprev -> n0:n
}
```
### 測驗 `3`
#### `find_nth_bit()` 介紹
該程式的功能，是在某一段記憶體空間找到第 n 個 bit 1 的所在位置。以下圖為例，指標 0 指向的位置就是第 0 個 bit 1 ，指標 1 指向的位置是第 1 個 bit 1 ，以此類推。
而當沒有找到第 n 個 bit 1 的時候，程式碼就會回傳該段記憶體空間的大小，在下面這個例子的話，就是 8 。
```graphviz
digraph G {
rankdir = TD;
splines = false;
node[shape = "record"]
p0[label="0",shape=plaintext,fontcolor=black];
p1[label="1",shape=plaintext,fontcolor=black];
p2[label="2",shape=plaintext,fontcolor=black];
p3[label="3",shape=plaintext,fontcolor=black];
{
rank="same"
bitfield[label = "<b7>1 | <b6>0 | <b5>0 | <b4>1 | <b3>1 | <b2>0 | <b1>1 | <b0>0"];
lsb[label="LSB",shape=plaintext,fontcolor=black];
}
p0 -> bitfield:b1;
p1 -> bitfield:b3;
p2 -> bitfield:b4;
p3 -> bitfield:b7;
}
```
#### 程式碼解析
`find_nth_bit()` 的主函式相當的簡潔：
```c
static inline unsigned long find_nth_bit(const unsigned long *addr,
unsigned long size,
unsigned long n)
{
if (n >= size)
return size;
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
return val ? fns(val, n) : size;
}
return FIND_NTH_BIT(addr[idx], size, n);
}
```
這裡可以看到，程式碼使用了 `small_const_nbits()` 這個巨集來判斷是否要用不同的方式來計算第 n 個 bit 的位置。
下面是 `small_const_nbits()` 巨集的定義：
```c
#define small_const_nbits(nbits) \
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
```
依照 C 運算元的優先順序，邏輯上我們可以把上面程式碼視為先運算下面三個式子之後再進行 Logical AND 之後的結果：
- `__builtin_constant_p(nbits)`
- `(nbits) <= BITS_PER_LONG`
- `(nbits) > 0`
參考 [GCC 文件](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fconstant_005fp) ， `__builtin_constant_p(nbits)` 的用途是去判斷 `nbits` 是否為 compile-time constant ，如果是的話就回傳 1 ，反之則回傳 0 。
`BITS_PER_LONG` 則是代表 long 型態的位元數量，在這裡是 64 。
所以這邊可以推得 `small_const_nbits()` 巨集的功能是去判斷輸入 `find_nth_bit()` 的長度參數是否為常數，且該常數是介於 1 到 64 的區間。
___
當程式碼判斷 `size` 為小常數之後，下面的程式碼就會被執行：
```c
unsigned long val = *addr & GENMASK(size - 1, 0);
return val ? fns(val, n) : size;
```
首先解析 `GENMASK` ：
```c
#define GENMASK(h, l) \
(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
```
該巨集會產生以 `h` 跟 `l` 為邊界的遮罩，舉例來說， `GENMASK(59, 4)` 會產出一個 `0x0FFFFFFFFFFFFFF0` 的遮罩。
接下來是 `fns()` ：
```c
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word) {
unsigned int bit = __ffs(word);
if (n-- == 0)
return bit;
__clear_bit(bit, &word);
}
return BITS_PER_LONG;
}
```
該函式的原理相當簡單，假設要找出 `01101011` 中第二個 `1` 的位置（從第零個開始算）：
1. 迴圈透過 `__ffs()` 函式找到第零個 1 並將其刪除：
`word = 01101010`
2. 迴圈透過 `__ffs()` 函式找到第零個 1 並將其刪除，但是因為原本的第零個 1 已經在前一次迭代被刪除了，所以這次刪除的 1 其實是第一個 1 ：
`word = 01101000`
3. 迴圈透過 `__ffs()` 函式找到第零個 1 ，因為前面已經刪掉兩個 1 了，所以這次找到的就是第二個 1 ，也就是我們的目標。
到這邊可以推測，當輸入 `find_nth_bit()` 的 `size` 參數為比較正常的數字時（介於 1 到 64 的數字，常數），這份程式碼並不會用特別的方式來處理問題。
現在來看當 `small_const_nbits()` 回傳值為零的時候程式碼的邏輯：
```c
return FIND_NTH_BIT(addr[idx], size, n);
```
`FIND_NTH_BIT()` 為一巨集，可以被展開成下面的程式碼：
```c
#define FIND_NTH_BIT(FETCH, size, num) \
({ \
unsigned long sz = (size), nr = (num), idx, w, tmp; \
\
for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
if (idx * BITS_PER_LONG + nr >= sz) \
goto out; \
\
tmp = (FETCH); \
w = hweight_long(tmp); \
if (w > nr) \
goto found; \
\
nr -= w; \
} \
\
if (sz CCCC BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
found: \
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
out: \
sz; \
})
```
> `FETCH` 在這裡會被代換成 `addr[idx]` 。
並且以下是 `hweight_long()` 的程式碼：
```c
#define __const_hweight8(w) \
((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
(!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
(!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
(!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))
#define __const_hweight16(w) (__const_hweight8(w) + __const_hweight8((w) >> 8))
#define __const_hweight32(w) \
(__const_hweight16(w) + __const_hweight16((w) >> 16))
#define __const_hweight64(w) \
(__const_hweight32(w) + __const_hweight32((w) >> 32))
static inline unsigned long hweight_long(unsigned long w)
{
return __const_hweight64(w);
}
```
先解析 `__const_hweight8()` ，先單獨取 `(!!((w) & (1ULL << 3)))` 這個程式碼片段來看：
- `(w) & (1ULL << 3)` 是在提取出 `w` 中第三個位元。
- 如果 `w` 的第三個位元為 1 的話，這個式子的結果就會是 `00001000`
- `!!` 的作用則是把原本非零的數字轉換成 0 跟 1
- `00001000` 會變成 1
- `00000000` 會變成 0
所以 `__const_hweight8()` 在做的事情其實就是計算這 8 個位元裡面有幾個 1 。
基於上面的推導，不難看出這系列的巨集以及 `hweight_long()` 的用途就是在算傳入的資料裡面有幾個位元是 1 。
回到 `FIND_NTH_BIT()` ，知道 `hweight_long()` 的用途後，就可以知道這裡的 `for` 迴圈是在找出第 n 個位元 1 是被放在 `addr` 指向的記憶體的哪個位置：
```c
for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
if (idx * BITS_PER_LONG + nr >= sz) \
goto out; \
\
tmp = (FETCH); \
w = hweight_long(tmp); \
if (w > nr) \
goto found; \
\
nr -= w; \
} \
```
而 `for` 迴圈底下的 `if` 判斷式則是用來處理最後一個 word （也就是 `addr[]` 的最後一個），因為上面的 `for` 迴圈不會檢查到這一個 word 。
```c
if (sz CCCC BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
```
從程式碼上下文可以推斷 CCCC 代表的是 `<` ：
```diff
- if (sz CCCC BITS_PER_LONG) \
+ if (sz < BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
```
在最後的 `found` 跟 `out` 程式區塊則會回傳最後的結果。
```c
found: \
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
out: \
sz; \
```
Sign in with Wallet
Connect another wallet