bitmap.cpp

eC++编译器源码

#pragma BitMap
#include <Errors.h>
boolean TestBit(unsigned int n,unsigned int src);
void EXCL(unsigned int &src,unsigned int cnt);
void INCL(unsigned int &src,unsigned int cnt);

/* By CAK 8-88 *)
(* RPC08-89 numerous changes to GetBit and CheckNBit to improve speed *)
(* This module deals with any kind of bit map that is composed of BITSET
   or something that can be taken to be BITSET  *)
(* Note: Implicit in this module is the idea that a 1 is free, and a
         0 is occupied in the map.    */

const unsigned int numbitsperset = 16;
unsigned int mask[16], check[16];
unsigned int i;

unsigned int Remainder(unsigned int &bar[])
{

  unsigned int i;
  unsigned int j ;

 for(i= HIGH(bar);i>=0;i--)
     {
     if  (bar[i]!=0xFFFF){
           
        j = numbitsperset - 1;
            
        while(TestBit(j,bar[i])) 
	   j=j-1;
            
      return((HIGH(bar)-i)*numbitsperset + (numbitsperset-j-1));
      }
      }
  return((HIGH(bar)+1)*numbitsperset);
  };

int GetBit(unsigned int &bar[],unsigned int start)
{     
      unsigned int cur;  
      unsigned int  at ;  

    cur=start/numbitsperset;
    if (cur>HIGH(bar)) return(-1);
    at=start%numbitsperset;
    do
     {
      if (bar[cur]!=0 )
	do
	{
	   
          if (TestBit(at,bar[cur]))
	    {
	     EXCL(bar[cur], at);
	    return(cur * numbitsperset + at);
	    } 
          at++;
	 } while (true);
	    
      cur++;
      } while(cur<=HIGH(bar));
    return(-1);
    };

void FreeBit(unsigned int &bar[], unsigned int index)
  {
     unsigned int where;
     unsigned int offset;
     where = index/numbitsperset;
     offset = index%numbitsperset;
     if (where > HIGH(bar)){
     SoftwareError("BitMap.FreeBit: index too high");
     } 
     else 
     {
      if (TestBit(offset,bar[where])) 
	    SoftwareError("BitMap.FreeBit: bit already free");
      }
     INCL(bar[where], offset);
  };

 void FreeMap(unsigned int &bar[])
  /* Sets a bitmap to all Free */
  {
     unsigned int i;
     for(i=0;i<=HIGH(bar);i++)
      bar[i] =0xFFFF;
  };


  
void FreeNBit( unsigned int &bar[],unsigned int index,unsigned int count)
  {
      unsigned int i;
   for(i=index;i<=index + count - 1;i++) 
     FreeBit(bar, i);
  };


boolean GetFixBit(unsigned int &bar[],unsigned int index) 
/* Gets a particular bit from the map, TRUE if got it */
  {
  unsigned int where, offset ;
  
  where = index/numbitsperset;
  offset = index%numbitsperset;
  if( where > HIGH(bar)) SoftwareError("BitMap.GetFixBit: Index too high");

  if(TestBit(offset,bar[where])) { 
       EXCL(bar[where], offset);
     return(true);
     }
     else
     return(false);
  };

 boolean CheckNBit(unsigned int &bar[],unsigned int &start,unsigned int count) 
 /* Checks to see if getting N bits is possible, starting in a particular
     position of the map.  Start is changed to position where the bits can
     be gotten. */
  /* Using modified KMP algorithm */
  {
    unsigned int ind, offset;
    unsigned int cur, stopck;
    unsigned int myStart, top;
    
  top = (HIGH(bar)+1)*numbitsperset;
    
  myStart = start;
    
  cur = myStart + count - 1;  /* where we look to match */
  if (count == 0) SoftwareError("BitMap.CheckNBit: Count=0");
  else if (cur >= top) return(false);
   
  stopck = myStart;   /* initial flag */
  do
  {
   do
   {
       ind  = cur/numbitsperset;
       offset =cur%numbitsperset;
       if(!TestBit(offset,bar[ind])) break;
       else if(cur <= stopck) {start = myStart;
	                       return(true);
                                 }
	cur  = cur-1;
   } while(true);
   stopck = myStart + count;  /* know the bits are free before here */
    myStart = cur + 1;  /*skip past where it failed*/
    cur = myStart + count - 1; /* where we look to match */
    if(cur >= top) return(false);
  } while(true);  
  };
 




boolean GetNFixBit(unsigned int &bar[],unsigned int index,unsigned int count) 
{ 
   unsigned int i, j;
 
  if (count==0) SoftwareError("BitMap.GetNFixBit: Count=0");
  else if ((index + count - 1)>= (HIGH(bar)+1)*numbitsperset) 
   SoftwareError("BitMap.GetNFixBit: Index too high or count too large");
    
  for(i= index;i<=index + count - 1;i++)
  {
	if(!(GetFixBit(bar, i))) 
	{
	  if(i == 0)return(false);
	   for(j=index;j<i-1;j++)
	      FreeBit(bar, j);
	   return(false);
	} 
   } 
  return(true);
  };
 
 int GetNBit(unsigned int &bar[],unsigned int start,unsigned int count) 
  /* Gets N bits from the bit map and returns begining index if it found 
     that many, -1 if not. */
 {
    
   if( CheckNBit(bar, start, count))
    {
      
     if(!(GetNFixBit(bar, start, count)))
	SoftwareError("BitMap.GetNBit: Previously free bits are now in use");
         
	return(start);
	 
     } 
  else

     return(-1);

   };


boolean CheckNFixBit(unsigned int &bar[],unsigned int index,unsigned int count)
  /* Checks to see if N bits are available in the map from index to
     index+count-1 bits. */
 {
    unsigned int where, offset;
    unsigned int i;

  if(count==0) SoftwareError("BitMap.CheckNFixBit: Count=0");
    
  for(i =index;i<=index+count-1;i++) 
  {  where = i/numbitsperset;
     if(where > HIGH(bar)) 
        SoftwareError("BitMap.CheckNFixBit: Index too high");
     
     offset = (i%numbitsperset);
     if (!TestBit(offset,bar[where])) return(false);        
   }
  return(true);
  };
  
  boolean CheckBit(unsigned int &bar[], unsigned int &start) 
  /* Checks to see if a bit is available in the map starting at start */
  {
  return ( CheckNBit(bar, start, 1));
  };


 
   boolean CheckFixBit(unsigned int &bar[],unsigned int index) 
  /* Checks to see if there is a bit available at index */
  {
  return(CheckNFixBit(bar, index, 1));
  };
  
 
void BitMap()
{
  int i;
   mask[15] = 0x8000 ;
   check[15]=0x8000 ;
  for(i=14;i>=0;i--)
   {
     check[i]=check[i+1]/2;
     mask[i]=mask[i+1]|check[i];   
   }
};

void INCL(unsigned int &src,unsigned int cnt)
{
   if (cnt<16) src=src|check[cnt];
};
				       
void EXCL(unsigned int &src,unsigned int cnt) 
{
   if (cnt<16) src=src^check[cnt]; 
};
   

boolean TestBit(unsigned int n,unsigned int src) 
   {
   return (check[n]&src)!=0;
   };