// bitmap.c 
//	Routines to manage a bitmap -- an array of bits each of which
//	can be either on or off.  Represented as an array of integers.

#include "bitmap.h"

//----------------------------------------------------------------------
// BitMap::BitMap
// 	Initialize a bitmap with "nitems" bits, so that every bit is clear.
//	it can be added somewhere on a list.
//	"nitems" is the number of bits in the bitmap.
//----------------------------------------------------------------------

BitMap::BitMap(int nitems) 
{ 
    numBits = nitems;
    numWords = divRoundUp(numBits, BitsInWord);
    map = new unsigned int[numWords];
    if (pthread_mutex_init(&mut,NULL) != 0)
	perror("BitMap:BitMap");
    for (int i = 1; i <= numBits; i++) 
        Clear(i);	
    Mark(numBits);
}

//----------------------------------------------------------------------
// BitMap::~BitMap
// 	De-allocate a bitmap.
//----------------------------------------------------------------------
BitMap::~BitMap()
{ 
    delete map;
}

//----------------------------------------------------------------------
// BitMap::Set
// 	Set the "nth" bit in a bitmap.
//	Makes this entry Unavailable
//	"which" is the number of the bit to be set.
//----------------------------------------------------------------------
void BitMap::Mark(int which) 
{ 
    assert(which >= 0 && which <= numBits);
    map[which / BitsInWord] |= 1 << (which % BitsInWord);
}
    
//----------------------------------------------------------------------
// BitMap::Clear
// 	Clear the "nth" bit in a bitmap. (in other words, it's made available)
//	"which" is the number of the bit to be cleared.
//----------------------------------------------------------------------
void BitMap::Clear(int which) 
{
    assert(which > 0 && which <= numBits);
    map[which / BitsInWord] &= ~(1 << (which % BitsInWord));
}

//----------------------------------------------------------------------
// BitMap::Test
// 	Return TRUE if the "nth" bit is set.
//	"which" is the number of the bit to be tested.
//----------------------------------------------------------------------
bool BitMap::Test(int which)
{
    assert(which >= 0 && which <= numBits);
    
    if (map[which / BitsInWord] & (1 << (which % BitsInWord)))
		return TRUE;
    else
		return FALSE;
}

//----------------------------------------------------------------------
// BitMap::Find
// 	Return the number of the first bit which is clear.
//	As a side effect, set the bit (mark it as in use).
//	(In other words, find and allocate a bit.)
//	If no bits are clear, return -1.
//----------------------------------------------------------------------
int BitMap::Find() 	
{

	pthread_mutex_lock(&mut);      // provides mutual exclusion 

    	for (int i = 1; i <= numBits; i++)
	{
		if (!Test(i)) 
		{
			Mark(i);	// found it,so mark it as busy
			pthread_mutex_unlock(&mut);
		    	return i;
		}
	}
	pthread_mutex_unlock(&mut);
	return -1; // did not find an spot available, return -1

} // end of the Find method

//----------------------------------------------------------------------
// BitMap::NumClear
// 	Return the number of clear bits in the bitmap.
//	(In other words, how many bits are unallocated?)
//----------------------------------------------------------------------

int BitMap::NumClear() 
{
    int count=0;

    for (int i=1; i <= numBits; i++)
		if (!Test(i)) 
			count++;
    return count;
}

//----------------------------------------------------------------------
// BitMap::Print
// 	Print the contents of the bitmap, for debugging.
//
//	Could be done in a number of ways, but we just print the #'s of
//	all the bits that are set in the bitmap.
//----------------------------------------------------------------------

void BitMap::Print() 
{
    printf("Bitmap set:\n"); 
    for (int i = 1; i <= numBits; i++)
	if (Test(i))
	{
	    printf("%d, ", i);
	    if (i%25 == 0)
		printf("\n");
	}
    printf("\n"); 
}

