A bitmap is a data structure that implements an array of booleans in a very memory efficient way; albeit the time complexity of this implementation isn"t constant, given the fact cpu registers will store the same bytes in them for a prolonged period of time with accesses restricted to the same memory region, this data structure often outperforms others with better time complexity.
typedef struct _bm {
uint8_t *bits;
size_t max_index;
} Bitmap_t;
extern void Bitmap_init(Bitmap_t *bm, size_t sz);
extern uint8_t Bitmap_at(Bitmap_t *bm, size_t index);
extern void Bitmap_set(Bitmap_t *bm, size_t index, uint8_t set_bit);
extern void Bitmap_free(Bitmap_t *bm);#include <stdio.h>
#include <bitmap.h>
int main(void)
{
Bitmap_t bm;
/* initialize bitmap with 8 spaces */
Bitmap_init(&bm, 8);
/* set the first bit */
Bitmap_set(&bm, 0, 1);
/* set the third bit */
Bitmap_set(&bm, 2, 1);
/* set the last bit */
Bitmap_set(&bm, 7, 1);
/* print set bits */
for (int i = 0; i < 8; i++)
putchar((Bitmap_at(&bm, i)) ? "1" : "0");
putchar("\n");
/* free the allocated space in memory */
Bitmap_free(&bm);
return 0;
}