2022q1 Homework4 (quiz4)

contributed by < tinyynoob >

作業要求

測驗 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

測驗 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. 初始狀態

假設現在要刪除 b 節點

2. loop 一圈之後

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

分隔 foo 與 foo_consumer 的原因

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

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

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

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

探討 kernel 中的案例

測驗 4

測驗 5