# 2024q1 Homework2 (quiz1+2)

contributd by < `MiohitoKiri5474` >

## Quiz 1

### 測驗一

#### `AAAA`

`list_tail` 使用間接指標來操作，`left` 需要向後迭代，因此 `AAAA` 會被還原成 `(*left)->next`。

while ((*left) && (*left)->next)
    left = &((*left)->next);
return *left;

#### `BBBB`

`list_length` 同樣使用間接指標，用來查找整個 linked list 中的長度，當中的 `left` 需要向後迭代，因此 `BBBB` 同樣被還原成 `(*left)->next`。

while (*left) {
    ++n;
    left = &((*left)->next);
}

#### `CCCC`

`quick_sort` 以每個區間的第一個元素作為 pivot，且按照 Quick Sort 的排序方式，會將剩餘元素中比 pivot 小者放到 pivot 左邊、比 pivot 大者放到 pivot 右邊，因此這邊的 `CCCC` 會被還原成 `p->next`。

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n );
}

接著會把放在左側的元素放在 `i`、pivot 放 `i + 1`、放在右邊的元素放在 `i + 2`，每次操作結束就會將 index += 2，並且在右側分割完畢後依序退回左側還沒分割的部分、並將已分割且排序好的元素放回 linked list 中保存。重複以上操作直到整個 list 排序完成。

#### `DDDD` & `EEEE`

`begin[]` 和 `end[]` 分別放 linked list 的開頭和結尾，照此邏輯 `DDDD` 和 `EEEE` 分別為 `list_tail(&left)` 和 `list_tail(&right)`

begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);

### 測驗二

#### `AAAA`

`merge()` 一樣也是間接指標，將 `&head` 填入 `AAAA`。

struct list_head *head;
struct list_head **tail = &head;

#### `BBBB` & `CCCC`

經果比較 `a` 和 `b` 後，會將符合條件的節點加入 `tail` 中，並且將 `tail` 向後移動用以後續添加新的節點，因此 `BBBB` 和 `CCCC` 分別填入 `&a->next` 和 `&b->next`。

if (cmp(priv, a, b) <= 0) {
    *tail = a;
    tail = &a->next;
    a = a->next;
    if (!a) {
        *tail = b;
        break;
    }
} else {
    *tail = b;
    tail = &b->next;
    b = b->next;
    if (!b) {
        *tail = a;
        break;
    }
}

#### `DDDD` & `EEEE`

這裡需要將 list 的關係建立好，行成環狀的 linked list。
因此 `DDDD` 和 `EEEE` 為 `tail->next` 和 `head->prev`。

tail->next = head;
head->prev = tail;

#### `FFFF`

在經過最後一次合併時，需要將頭尾連接上形成環狀的 linked list。
因此在堆疊大小小於等於 1 的時候做此操作，`FFFF` 的值為 1。

if (stk_size <= FFFF) {
    build_prev_link(head, head, stk0);
    return;
}

## Quiz 2

### 測驗一

#### `AAAA`

將節點加入到原本的開頭，所以需要將 `n->next` 設為 `h->first`（`AAAA`）。

if (h->first)
    h->first->pprev = &n->next;
n->next = h->first;
n->pprev = &h->first;
h->frst = n;

#### `BBBB` & `CCCC`

為了將指定 hash value 中相同的元素都取出，所以 `hlist_for_each` 開始的起點（`BBBB`）為 `&heads[hash]`
同時為了取得節點的資訊，需要用 `container_of`（或是 `list_entry`）取得。

struct hlist_node *p;
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) {
    struct order_node *on = container_of(p, struct order_node, node);
    if (num == on->val)
        return on->idx;
}

#### `DDDD`

為了將新的元素加入對應 hash value 的欄位中，`DDDD` 應為 `&heads[hash]`。

struct order_node *on = malloc(sizeof(*on));
on->val = val;
on->idx = idx;
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, &heads[hash]);

### 測驗二

#### `EEEE`

第一個 `pprev` 指向 `NULL` 的狀況不存在，因此可以將前一項與後一項相接。`EEEE` 為 `next->prev`。

struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
    next->prev = pprev;

#### `FFFF` & `GGGG`

為了將 `list_head` 中的節點都刪除，`pos` 在 `LRUNode` 結構中的名稱為 `link`，因此 `FFFF` 應該為 link。

而要將這個節點從 linked list 中移除，則需要刪除 `GGGG` 也就是 `&cache->link` 在 linked list 中的關係。

struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
    LRUNode *cache = list_entry(pos, LRUNode, link);
    list_del(&cache->link);
    free(cache);
}
free(obj);

#### `IIII`

要移動節點於 linked list 中的位置，`IIII` 需為 `&cache->link`。

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, &obj->dhead);
        return cache->value;
    }
}

#### `JJJJ` & `KKKK`

同理，為了將 `hlist_node` 中的節點移動位置，需要將其從 `LRUNode` 結構中取出，而他的名稱為 `node`（`JJJJ`）。
而 `KKKK` 則為 `&c->link`。

LRUNode *cache = NULL;
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
    LRUNode *c = list_entry(pos, LRUNode, node);
    if (c->key == key) {
        list_move(KKKK, &obj->dhead);
        cache = c;
    }
}

### 測驗三

#### `AAAA`

這邊是採用二分艘，所以 `AAAA` 應該為 `0xffffffff`。

if ((word & 0xffffffff) == 0) {
    num += 32;
    word >>= 32;
}

#### `BBBB`

藉由位元運算將指定位置的 bit 移除掉，具體作法是先產生一個在指定 bit 為 1 的 `mask`，並且將目前的值與 `~mask` 以 `and` 運算將此 bit 消除，因此 `BBBB` 為 `~mask`。

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= ~mask;
}

#### `CCCC`

這邊是為了避免超出位數，所以是用 `%` 來運算。

if (sz % BITS_PER_LONG)                              \
    tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \