contributed by < [dcciou](https://github.com/dcciou) >

# Q1第一題
## AAAA,BBBB,CCCC

在 list_tail 和 list_length 函數中，我們需要找到方式來traverse鏈結串列。

AAAA: 由於 list_tail 函數需要traverse到串列的尾部，我們會繼續透過每個節點的 next 指標traverse。因此，AAAA 是 (*left)->next，即當前節點的下一個節點。

BBBB: 在 list_length 函數中，我們同樣需要traverse串列，計算長度。所以，BBBB 同樣是指向下一個節點的操作，即 (*left)->next。

CCCC: 在 quick_sort 中提到，當處理當前節點後，我們需要移動到下一個節點來繼續traverse。因此CCCC 是 p->next，表示從當前節點移動到下一個節點。

註:根據[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)，traverse翻成中文有超譯的情形，故採原文。
## DDDD,EEEE

DDDD 和 EEEE 代表在節點在跟pivot value比較後被分配到 left 或 right 之後，用於管理 left 和 right 分區末端邊界的操作。

各函數功能如下:
list_add：將一個節點添加到列表的前面，並更新列表指向新添加的節點。
list_tail：找到列表中的最後一個節點，如果列表為空則回傳 NULL。
list_length：計算列表中節點的數量。
list_construct：創建一個新節點，並將其值設置為給定值，然後將其添加到列表的前面。
list_free：釋放列表中的所有節點。

考慮到這些函數的功能，DDDD 和 EEEE 的目的是：

DDDD：在所有節點與pivot value比較後被分配給 left 分區之後，調用 list_tail 函數。這是因為我們需要找到 left 列表的最後一個節點，以正確設置 left 分區結束的邊界，才能開始對下一個分區進行排序。
因此答案為:

    end[i] = list_tail(&left); 

EEEE：同理，EEEE表示:在節點被分配到 right 分區之後，調用 list_tail 函數。在將節點分配給 right 列表後，找到其最後一個節點是必要的，以正確定義隨後對 right 側進行排序操作的邊界。
因此答案為:

end[i + 2] = list_tail(&right);

## 延伸

# Q1第二題
&head
&a -> next
&b -> next

# Q2第一題
## 填空
AAAA: 將新節點加到 hlist的 頭部，故為 h->first
BBBB: 利用 hash table 來找到每個數字的位置，一開始會從頭開始，故為 &heads[hash]
CCCC: 這是一個 list_entry 的應用，它從 hlist_node 結構中取得包含它的 order_node 結構，故為 list_entry
DDDD: 在 node_add 函式中，應該將新節點添加到對應 hash 值的 hlist_head 中，故為 &heads[hash]。

## 延伸

# Q2第二題
## 運作原理
使用一個 hash table（hhead）來快速定位緩存項目。
使用一個雙向鏈表（dhead）來追蹤訪問順序，表頭部分是最近訪問的項目，表尾部分是最久未訪問的項目。
當訪問一個項目時，如果項目存在於緩存中，它會被移動到雙向鏈表的頭部，表示它被最近訪問過。
當需要新增一個項目到緩存時，如果緩存已滿，則會移除雙向鏈表尾部的項目（最久未訪問），並將新項目插入到表頭。
每個緩存項目（LRUNode）都在雙向鏈表中有一個對應的結點（link），並且在hash table的相應位置有一個節點（node）

## 填空
EEEE: 在 hlist_del 函式中，需要設定下一個節點的 pprev 指標，指向前一個節點的 next 指標的地址，這是從雙向鏈表中刪除節點的一部分操作，故為 next->pprev。
FFFF: 在 lRUCacheFree 函式中，使用 list_entry 將 list_head 轉換為 LRUNode 結構，故為 link。
GGGG: 同上，這裡是刪除節點， list_del 用於將節點從雙向鏈表中移除，故為 &cache->link 。
HHHH: 在 lRUCacheGet 函式中，用 list_entry 將 hash list 節點轉換為 LRUNode 結構，以便能夠訪問 key value pair，故為 node 。
IIII: 這裡用 list_move 函式將節點移動到雙向鏈表的頭部，表示最近被訪問，故為 &cache->link 。
JJJJ: 在 lRUCachePut 函式中，同樣使用 list_entry 進行結構轉換，故為 node 。
KKKK: 將存在的節點移動到雙向鏈表頭部，或創建新節點並添加到鏈表頭部，故為 &c->link 。

# Q2第三題
## 運作原理
__ffs 函數是尋找一個無符號長整型數字最低位的 1 的位元位置。這個函數假設至少有一位是設置為 1 的，因此在使用這個函數之前應該確保該數字不為 0。

__clear_bit 函數是用來清除（設為 0）無符號長整型數字中指定位置的位元。

fns 函數（Find Nth Set bit）是在給定的無符號長整型數字中找到第 N 個設置為 1 的位元位置。

find_nth_bit 函數是在一個記憶體區域中找到第 N 個設置為 1 的位元位置，如果沒有找到，則返回 size。
## 填空
AAAA：此處我們需要用一個 16 進位的數來檢查 word 的前 32 位。在 64 位架構中，故為 0xffffffff。
BBBB：我們要用位元遮罩與原來的值進行 AND 操作來清除指定位元，所以我們需要 NOT mask (~mask)。
CCCC : 如果 sz 是 BITS_PER_LONG 的整數倍，則最後一個字中的所有位元都是有效的，我們不需要對最後讀取的字進行遮罩操作。反之，如果不是整數倍，那麼 sz % BITS_PER_LONG 將會給出非零的餘數，表示最後一個字中只有餘數那麼多位元是有效的，因此利用 % 來決定是否需要對最後一個字進行遮罩操作。