c - 使用位图跟踪数组

Question

我有一个大小为 10 的数组

我想跟踪数组中的可用空间，有人告诉我位图是更好的选择。

例如索引 2 和 3 为空，我可以在位图中的索引 2 和 3 处记录位 0

如何创建大小为 10、默认为 0 位的位图？

欢迎有关位图的有用链接。

提前致谢

Answer 1

C 对“位图”类型没有任何一流的支持；你必须自己实现它。非常简单，只需使用一个无符号整数数组和一些按位移位/逻辑运算符即可。

类似于:

typedef struct {
  unsigned int *bits;
  size_t size;
} bitmap;

#define BITS (CHAR_BIT * sizeof (unsigned int))

bitmap * bitmap_new(size_t size)
{
  const size_t length = (size + BITS - 1) / BITS;
  const size_t bytes = length * sizeof (unsigned int);
  bitmap *b = malloc(sizeof *b + bytes);
  if (b != NULL)
  {
    b->bits = (unsigned int *) (b + 1);
    memset(b->bits, 0, length);
    b->size = size;
  }
  return b;
}

bool bitmap_test(const bitmap *b, size_t index)
{
  if (index < b->size)
  {
    const size_t ii = index / BITS;
    const unsigned int ib = index % BITS;
    return (bool) ((b->bits[ii] & (1u << ib)) != 0);
  }
  return false;
}

void bitmap_set(bitmap *b, size_t index)
{
  if (index < b->size)
  {
    const size_t ii = index / BITS;
    const unsigned int ib = index % BITS;
    b->bits[ii] |= (1u << ib);
  }
}

上面的内容未经测试，但您应该了解主要想法。