nachos.kernel.filesys
Class BitMap

java.lang.Object
  extended by nachos.kernel.filesys.BitMap

public class BitMap
extends java.lang.Object

This 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. We represent a bitmap 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 by the number of bits being managed. It is also equipped with fetchFrom() and writeBack() methods for reading a bitmap from, and writing a bit map to, a Nachos file.


Field Summary
(package private) static int BitsInByte
          Number of bits in a byte.
private static int BitsInWord
          Number of bytes in an integer.
private  int[] map
          Bit storage.
private  int numBits
          Number of bits in the bitmap.
private  int numWords
          Number of words of bitmap storage (rounded up if numBits is not a multiple of the number of bits in a word).
 
Constructor Summary
BitMap(int nitems)
          Initialize a bitmap with "nitems" bits, so that every bit is clear.
 
Method Summary
 void clear(int which)
          Clear the "nth" bit in a bitmap.
 void fetchFrom(OpenFile file)
          Initialize the contents of a bitmap from a Nachos file.
 int find()
          Find the first bit that is clear.
 void mark(int which)
          Set the "nth" bit in a bitmap.
 int numClear()
          Return the number of clear bits in the bitmap.
 void print()
          Print the contents of the bitmap, for debugging.
 boolean test(int which)
          Test if the "nth" bit is set.
 void writeBack(OpenFile file)
          Store the contents of a bitmap to a Nachos file.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

BitsInByte

static final int BitsInByte
Number of bits in a byte.

See Also:
Constant Field Values

BitsInWord

private static final int BitsInWord
Number of bytes in an integer.

See Also:
Constant Field Values

numBits

private int numBits
Number of bits in the bitmap.


numWords

private int numWords
Number of words of bitmap storage (rounded up if numBits is not a multiple of the number of bits in a word).


map

private int[] map
Bit storage.

Constructor Detail

BitMap

public BitMap(int nitems)
Initialize a bitmap with "nitems" bits, so that every bit is clear. it can be added somewhere on a list.

Parameters:
nitems - The number of bits in the bitmap.
Method Detail

mark

public void mark(int which)
Set the "nth" bit in a bitmap.

Parameters:
which - The number of the bit to be set.

clear

public void clear(int which)
Clear the "nth" bit in a bitmap.

Parameters:
which - The number of the bit to be cleared.

test

public boolean test(int which)
Test if the "nth" bit is set.

Parameters:
which - The number of the bit to be tested.
Returns:
true if the indicated bit is set, otherwise false.

find

public int find()
Find the first bit that is clear. As a side effect, set the bit (mark it as in use). (In other words, find and allocate a bit.)

Returns:
the bit set, if one was found, otherwise -1.

numClear

public int numClear()
Return the number of clear bits in the bitmap. (In other words, how many bits are unallocated?)

Returns:
the number of clear bits in the bitmap.

print

public void 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.


fetchFrom

public void fetchFrom(OpenFile file)
Initialize the contents of a bitmap from a Nachos file.

Parameters:
file - The file to read the bitmap from.

writeBack

public void writeBack(OpenFile file)
Store the contents of a bitmap to a Nachos file.

Parameters:
file - The file to write the bitmap to.