bitmap.cc

Aller à la documentation de ce fichier.

// bitmap.cc
//      Routines to manage a bitmap -- an array of bits each of which
//      can be either on or off.  Represented as an array of integers.
//
// Copyright (c) 1992-1996 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "debug.h"
#include "bitmap.h"

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

Bitmap::Bitmap(int numItems) 
{ 
    int i;

    ASSERT(numItems > 0);

    numBits = numItems;
    numWords = divRoundUp(numBits, BitsInWord);
    map = new unsigned int[numWords];
    for (i = 0; i < numWords; i++) {
        map[i] = 0;             // initialize map to keep Purify happy
    }
    for (i = 0; i < numBits; i++) {
        Clear(i);
    }
}

//----------------------------------------------------------------------
// Bitmap::~Bitmap
//      De-allocate a bitmap.
//----------------------------------------------------------------------

Bitmap::~Bitmap()
{ 
    delete map;
}

//----------------------------------------------------------------------
// Bitmap::Set
//      Set the "nth" bit in a bitmap.
//
//      "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);

    ASSERT(Test(which));
}
    
//----------------------------------------------------------------------
// Bitmap::Clear
//      Clear the "nth" bit in a bitmap.
//
//      "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));

    ASSERT(!Test(which));
}

//----------------------------------------------------------------------
// 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) const
{
    ASSERT(which >= 0 && which < numBits);
    
    if (map[which / BitsInWord] & (1 << (which % BitsInWord))) {
        return TRUE;
    } else {
        return FALSE;
    }
}

//----------------------------------------------------------------------
// Bitmap::FindAndSet
//      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::FindAndSet() 
{
    for (int i = 0; i < numBits; i++) {
        if (!Test(i)) {
            Mark(i);
            return i;
        }
    }
    return -1;
}

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

int 
Bitmap::NumClear() const
{
    int count = 0;

    for (int i = 0; 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() const
{
    cout << "Bitmap set:\n"; 
    for (int i = 0; i < numBits; i++) {
        if (Test(i)) {
            cout << i << ", ";
        }
    }
    cout << "\n"; 
}


//----------------------------------------------------------------------
// Bitmap::SelfTest
//      Test whether this module is working.
//----------------------------------------------------------------------

void
Bitmap::SelfTest() 
{
    int i;
    
    ASSERT(numBits >= BitsInWord);      // bitmap must be big enough

    ASSERT(NumClear() == numBits);      // bitmap must be empty
    ASSERT(FindAndSet() == 0);
    Mark(31);
    ASSERT(Test(0) && Test(31));

    ASSERT(FindAndSet() == 1);
    Clear(0);
    Clear(1);
    Clear(31);

    for (i = 0; i < numBits; i++) {
        Mark(i);
    }
    ASSERT(FindAndSet() == -1);         // bitmap should be full!
    for (i = 0; i < numBits; i++) {
        Clear(i);
    }
}

---