#ifndef BMAP_H

#include <stdlib.h>
#include <assert.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <unistd.h>

/**
 * This structure is the in-memory representation of a bitmap.
 * There are helper functions to query and modify the bitmap's state
 * e.g., set_bit, check_bit.
 */
struct bitmap {
	// the number of bytes in the bitmap (not bits!)
	uint64_t n_bytes;
	
	// Due to padding, the number of valid bits may be less
	// than the number of bits that the bitmap *COULD* represent.
	// n_valid bits is the number of meaningful bits.
	uint64_t n_valid_bits;

	// The actual bitmap. This memory buffer must be malloc'ed and freed
	// by your program during allocate_bitmap(uint64_t num_bits) and
	// free_bitmap(struct bitmap *bmap)
	unsigned char *bits;
};


struct bitmap *allocate_bitmap(uint64_t num_bits);
void free_bitmap(struct bitmap *bmap);
char get_bit(struct bitmap *map, uint64_t i);
void set_bit(struct bitmap *map, uint64_t i);
void unset_bit(struct bitmap *map, uint64_t i);
uint64_t first_unset_bit(struct bitmap *map);



/****
 Debugging utility functions
 ***/
void dump_bitmap(struct bitmap *map); // this may be useful for debugging!

#endif