# 2022q1 Homework4 (quiz4)

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

> [作業要求](https://hackmd.io/@sysprog/HkJ-dN_-q)

## 測驗 1

### 解釋程式碼

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;

    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (EXP1) + 1;       
}

對照 [quiz3 測驗 7](https://hackmd.io/u4lvdDcAQeC8UoQ1dT7LUg?view#%E6%B8%AC%E9%A9%97-7)

## 測驗 3

### 解釋程式碼

struct foo_consumer {
    int (*handler)(struct foo_consumer *self, void *);
    struct foo_consumer *next;
};

struct foo {
    struct foo_consumer *consumers;
    unsigned long flags;
};

#include <stdbool.h>

/*
 * For foo @foo, delete the consumer @fc.
 * Return true if the @fc is deleted sfccessfully
 * or return false.
 */
static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
    struct foo_consumer **con;
    bool ret = false;

    for (con = &foo->consumers; *con; EXP4) {
        if (*con == fc) {
            *con = EXP5;
            ret = true;
            break;
        }
    }

    return ret;
}

這顯然是個從 singly-linked list 移除節點的問題，前面結構中的 `handler` 和 `flags` 都與答題無關。

走訪 list 並使用 indirect pointer 來刪除節點，`EXP4` 應為 `con = &(*con)->next`，而其中的 if statement 用於判斷是否已找到目標，`EXP5` 應為 `(*con)->next`。

解說如下：

1. 初始狀態

digraph {
    rankdir = LR;
    node [shape=record];
    foo [label="foo|{|<n>consumers}"];
    a [label="<b>a|{|<n>next}"];
    b [label="<b>b|{|<n>next}"];
    c [label="<b>c|{|<n>next}"];

    foo:n -> a:b;
    a:n -> b:b;
    b:n -> c:b;

    con -> foo:n [color=blue];
}

假設現在要刪除 b 節點

2. loop 一圈之後

digraph {
    rankdir = LR;
    node [shape=record];
    foo [label="foo|{|<n>consumers}"];
    a [label="<b>a|{|<n>next}"];
    b [label="<b>b|{|<n>next}"];
    c [label="<b>c|{|<n>next}"];
    foo:n -> a:b;
    a:n -> b:b;
    b:n -> c:b;

    con -> a:n [color=blue];
}

接著第二圈的 if statement 會發現已找到目標 `b` 並結束搜尋。

### 分隔 foo 與 foo_consumer 的原因

在 linked list 中，head 與 node 扮演著不同的角色，常見的情況為：

- head：紀錄 list 的資訊
- node：儲存資料

既然目的不同，實作的方式也就不相同，那麼使用不同的定義也是自然而然。

藉由 `head` 的獨立定義，也可以做出把 consumers 分放到不同條 list 的功能等等。

### 探討 kernel 中的案例

## 測驗 4

## 測驗 5