// bitmap.h 
//	Data structures defining a bitmap -- an array of bits each of which
//	can be either on or off.
//
//	Represented as an array of unsigned integers, on which we do
//	modulo arithmetic to find the bit we are interested in.
//
//	The bitmap can be parameterized with with the number of bits being 
//	managed.


#ifndef BITMAP_H
#define BITMAP_H

#include <stdio.h>
#include <fstream.h>
#include <pthread.h>
#include <assert.h>



// Definitions helpful for representing a bitmap as an array of integers

#define BitsInByte 	8
#define BitsInWord 	32
#define TRUE		1
#define FALSE           0

// These two function were added from nachos/utility.h

#define min(a,b)  (((a) < (b)) ? (a) : (b))
#define max(a,b)  (((a) > (b)) ? (a) : (b))

// Divide and either round up or down 

#define divRoundDown(n,s)  ((n) / (s))
#define divRoundUp(n,s)    (((n) / (s)) + ((((n) % (s)) > 0) ? 1 : 0))

// The following class defines a "bitmap" -- an array of bits,
// each of which can be independently set, cleared, and tested.
//
// Most useful for managing the allocation of the elements of an array --
// for instance, disk sectors, or main memory pages.
// Each bit represents whether the corresponding sector or page is
// in use or free.

class BitMap {

  public:

	BitMap(int nitems);	// Initialize a bitmap, with "nitems" bits
				// initially, all bits are cleared.
    	~BitMap();			// De-allocate bitmap
    
    	void Mark(int which);   // Set the "nth" bit
    	void Clear(int which);  // Clear the "nth" bit
    	bool Test(int which);   // Is the "nth" bit set?
    	int Find();            	// Return the # of a clear bit, and as a side
				// effect, set the bit. 
				// If no bits are clear, return -1.

    	int NumClear();		// Return the number of clear bits

    	void Print();		// Print contents of bitmap
    
  private:

	int numBits;			// number of bits in the bitmap
    	int numWords;			// number of words of bitmap storage
					// (rounded up if numBits is not a
					//  multiple of the number of bits in
					//  a word)
    	unsigned int *map;			// bit storage

	pthread_mutex_t mut;

					// handle to accomplish
					// mutual exclusion

};

#endif // BITMAP_H
