Keeping track of array using Bit maps

Question

I have an array of size 10

I want to keep track of the free space in the array and i was told bitmap is a better option.

For e.g index 2 and 3 is empty, i could record bit 0 at index 2 and 3 in the bitmap

How do i create a bitmap of size 10 with default 0 bits?

Helpful links regarding bitmaps are welcomed.

Thanks in advance

Answer 1

C doesn't have any first-class support for a "bit map" type; you're going to have to implement it yourself. It's very simple, just use an array of unsigned integers and some bitwise shifting/logic operators.

Something like:

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);
  }
}

The above is untested but you should get the main idea.