os_kernel/lib/kernel/bitmap.c

#include "bitmap.h"
#include "../string.h"
#include "../../kernel/debug.h"

void bitmap_init(Bitmap *pb)
{
    _memset(pb->bits, 0, pb->btmp_bytes_len);
}
bool bitmap_scan_test(Bitmap *pb, uint32_t bit_idx)
{
    // 判断位图中 bit_idx 位是否为 1
    uint32_t byte_idx = bit_idx / 8; // 向下取整用于索引数组下标
    uint32_t bit_odd = bit_idx % 8;  // 取余用于索引数组内的位
    return (pb->bits[byte_idx] & (BITMAP_MASK << bit_odd));
}
// 在位图中申请连续 cnt 个位,成功则返回起始位下标,失败返回-1
int bitmap_scan(Bitmap *pb, uint32_t cnt)
{
    uint32_t idx_byte = 0; // 用于记录空闲位所在的字节
    while ((0xff == pb->bits[idx_byte]) && (idx_byte < pb->btmp_bytes_len))
    { // 如果字节为 0xff,表示该字节已经被占用,继续向下一个字节查找
        idx_byte++;
    }
    ASSERT(idx_byte < pb->btmp_bytes_len);
    if (idx_byte == pb->btmp_bytes_len)
    { // 该内存池找不到可用空间
        return -1;
    }

    // 若在位图数组范围内的某字节内找到了空闲位，则在字节内逐位查找空闲位的索引
    int idx_bit = 0;
    // 和 pb->bits[idx_byte] 这个字节逐位对比
    while ((uint8_t)(BITMAP_MASK << idx_bit) & pb->bits[idx_byte])
    { // 1 << idx_bit 生成 00010000 这样的数，和 pb->bits[idx_byte]逐位与操作
        idx_bit++;
    }
    int bit_idx_start = idx_byte * 8 + idx_bit; // 空闲位在位图内的下标
    if (cnt == 1)
    {
        return bit_idx_start;
    }
    uint32_t bit_left = (pb->btmp_bytes_len * 8 - bit_idx_start); // 记录还有多少位可以判断
    uint32_t next_bit = bit_idx_start + 1;
    uint32_t count = 1; // 用于记录找到的空闲位的个数

    bit_idx_start = -1; // 先将其置为-1，若找不到连续的位就直接返回
    while (bit_left-- > 0)
    {
        if (!(bitmap_scan_test(pb, next_bit)))
        { // 若 next_bit 为 0
            count++;
        }
        else
        {
            count = 0;
        }
        if (count == cnt)
        { // 若找到连续的 cnt 个空闲位
            bit_idx_start = next_bit - cnt + 1;
            break;
        }
        next_bit++;
    }
    return bit_idx_start;
}
void bitmap_set(Bitmap *pb, uint32_t bit_idx, int8_t value)
{
    ASSERT((value == 0) || (value == 1));
    uint32_t byte_idx = bit_idx / 8; // 向下取整用于索引数组下标
    uint32_t bit_odd = bit_idx % 8;  // 取余用于索引数组内的位

    if (value)
    { // 若 value 为 1, 则 OR 1 到 bitmap[byte_idx] 的 bit_odd 位上
        pb->bits[byte_idx] |= (BITMAP_MASK << bit_odd);
    }
    else
    { // 若 value 为 0, 则 AND 0 到 bitmap[byte_idx] 的 bit_odd 位上
        pb->bits[byte_idx] &= ~(BITMAP_MASK << bit_odd);
    }
}